R Ledesma-Alonso

D Legendre

Ph Tordjeman

AFM Tip Effect on a Thin Liquid Film

We study the interaction between an AFM probe and a liquid film deposited over a flat substrate. We investigate the effects of the physical and geometrical parameters, with a special focus on the film thickness E, the probe radius R, and the distance D between the probe and the free surface. Deformation profiles have been calculated from the numerical simulations of the Young-Laplace equation by taking into account the probe/liquid and the liquid/substrate interactions, characterized by the Hamaker constants, H pl and H ls . We demonstrate that the deformation of a shallow film is determined by a particular characteristic length λ F = (2πγE 4 / H ls ) 1/2 , resulting from the balance between the capillary force (γ is the surface tension) and the van der Waals liquid/ substrate attraction. For the case of a bulk liquid, the extent of the interface deformation is simply controlled by the capillary length λ C = (γ/Δρg) 1/2 . These trends point out two asymptotic regimes, which in turn are bounded by two characteristic film thicknesses E g = (H ls /2πΔρg) 1/4 and E γ = (R 2 H ls /2πγ) 1/4 . For E > E g , the bulk behavior is recovered, and for E < E γ , we show the existence of a particular shallow film regime in which a localized tip effect is observed. This tip effect is characterized by the small magnitude of the deformation and an important restriction of its radial extent λ F localized below the probe. In addition, we have found that the film thickness has a significant effect on the threshold separation distance D min below which the irreversible jumpto-contact process occurs: D min is probe radius-dependent for the bulk whereas it is film-thickness-dependent for shallow films. These results have an important impact on the optimal AFM scanning conditions.

INTRODUCTION

The current development of nanotechnology is responsible for the emergence of micro-and nanofluidic systems. 1 A large number of these systems are based on the flow of very thin liquid films in confined geometries. 2 Under these conditions, capillary and van der Waals forces are dominant, and as a consequence, the behavior of liquids is strongly dependent on the film thickness. For instance, the flow relaxation time, 3,4 the slip length, 5 and the glass-transition temperature, 6,7 among other properties, are controlled by the characteristic length of confinement.

The properties of a liquid film as function of its thickness, from the molecular to the macroscopic scale, can be studied by means of atomic force microscopy (AFM) as a result of the recent progress of this technique. 8,9 Indeed, noncontact AFM is a useful method for quantifying the local properties of liquid films, 10 identifying the local positions of interfaces, and detecting liquid-phase domains and studying their rheology.

In such experiments, the study of the probe/liquid film interaction is fundamental to understanding the behavior of liquids of different thicknesses. With respect to the extensive work done by means of the surface force apparatus (SFA), we recall that the thickness has been shown to be a fundamental parameter in determining the stability of the film. 11 In addition, it has been proposed, for a liquid nanofilm, 12 that the film thickness should have a significant effect on AFM measurements and also promising applications.

In our previous studies, 13,14 the surface deformation of a bulk liquid in interaction with an AFM tip has been modeled, solved numerically, and validated with experiments. We have shown that the magnitude of the bulk liquid surface deformation and its curvature are functions of the probe/liquid separation distance. When a probe is approached towards the liquid surface below a threshold separation distance, we have found that the liquid undergoes a jump-to-contact phenomenon, which triggers probe wetting. Knowledge of this critical distance, called D min , is essential to determining the experimental optimal conditions for noncontact AFM measurements over liquids. We have demonstrated that a combined approach, based on theory and experiments, leads to a better understanding of the whole phenomenon. In particular, a fine prediction of the Hamaker interaction constant has been deduced from AFM force/distance curves. 13 The aim of this Article is to analyze the effect of the film thickness on the surface deformation. For this purpose, the Young-Laplace equation has been generalized to include the interaction between the liquid film and the underlaying substrate. The present communication is organized as follows: in section 2, we describe briefly the system configuration, together with the corresponding theoretical model, in which molecular interactions and capillarity are included. Section 3 discusses the general surface deformation and the jump-tocontact phenomenon and their dependency on the involved dimensionless parameters in which some of them are thicknessdependent. Several characteristic length scales, naturally arising in the model, are introduced and employed to describe the surface shape. The theoretical analysis allows us to define two critical film thicknesses, marking the boundaries of a shallow film regime and the bulk behavior, which are presented in section 4 and discussed in section 5. Finally, in section 6 the effects of the probe radius and the film thickness are studied quantitatively in order to apply the results when performing AFM measurements.

PROBLEM FORMULATION

Consider a stable liquid film of thickness E deposited over a flat substrate, as shown in Figure 1. When a spherical probe of radius R is placed at a distance D from the liquid free surface, a bump-like shape is observed. Because of the system geometry, the deformation is described by an axisymmetric profile z = η(r), where r and z are the radial and axial coordinates.

On the basis of the Hamaker theory, 15 the attractive interaction potential or pressure field Π pl exerted by the probe over the liquid film is

π Π = - + - H R D z r R 4 3 1 [( ) ] pl pl 3 2 2 2 3 (1)
where H pl is the Hamaker constant of the probe/air/liquid system. Equation 1 is obtained from integrating the Londonvan der Waals interaction potential of the spherical probe over a differential volume of liquid, anywhere outside the probe.

Only the nonretarded interactions are considered in view of the dimensions of common AFM setups. The presence of the substrate provokes, over the liquid film, the potential field Π ls given by

π Π = - + - ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ H E z E 6 1 ( ) 1 ( ) ls ls 3 3 (2)
where H ls is the Hamaker constant of the air/liquid/substrate system. This potential is the difference between the so-called disjoining pressure 16 of the initial state and that of the perturbed state (by the approach of the probe). Furthermore, the capillary pressure difference and the hydrostatic pressure appear in the pressure balance so that the surface shape of the film is described by the generalized Young-Laplace equation

ρ η κγ Π -Δ = + Π g 2 pl ls (3)
where Δρ is the liquid/air density difference, g is the gravitational acceleration, γ is the liquid surface tension, η is the local surface position, and κ is the local mean curvature, which, expressed in axisymmetric cylindrical coordinates, takes the form

κ η η = - + - ⎜ ⎟ ⎡ ⎣ ⎢ ⎢ ⎧ ⎨ ⎩ ⎛ ⎝ ⎞ ⎠ ⎫ ⎬ ⎭ ⎤ ⎦ ⎥ ⎥ r r r r r 2 1 d d d d d d 1 2 1/2 (4)
Using R as the characteristic length scale, we introduce dimensionless variables: D* = D / R the distance from the center of the probe to the originally undeformed free surface, E* = E / R the film relative thickness, r* = r / R and z* = z / R the horizontal and vertical coordinates; and η* = η / R and κ* = κR, the interface position and mean curvature. From eqs 1-4, the dimensionless nonlinear ordinary differential equation describing the free surface position results in

κ η * - Π * + * -Π * = AH B H 2 8 0 a ls o a pl (5)
where

η Π * = * + * - * E E 1 ( ) 1 ( ) ls 3 3 (6a) η Π * = * -* + * - D r 1 [( ) 1] pl 2 2 3 (6b)
Three dimensionless parameters are present in eq 5: the Hamaker constant ratio A = H ls /H pl , the modified Hamaker number H a = 4H pl /(3πγR 2 ), and the Bond number B o = ΔρgR 2 /γ. In AFM setups, the probe radius R is within the range [10 -9 , 10 -7 ] m, and the probe/liquid and liquid/substrate interactions are characterized by Hamaker constants H pl and H ls within [10 -21 , 10 -19 ] J. [17][18][19][20] For air/liquid interfaces, one usually has γ ∈ [10 -2 , 10 -1 ] N/m and Δρ ∈ [10 2 , 10 4 ] kg/m 3 . Consequently, for a film thickness E spanning [10 -10 , ∞] m, the dimensionless parameters are normally found to satisfy A ∈ [10 -2 , 10 2 ], H a ∈ [10 -7 , 10 0 ], and B o ∈ [10 -13 , 10 -8 ].

In particular, considering a PDMS film deposited over a silicon wafer and in interaction with an R = 1 × 10 -8 m silicon AFM probe, the system is characterized by γ = 3.1 × 10 -2 N/m, Δρ = 9.7 × 10 2 kg/m 3 , and H ls = H pl = 4 × 10 -20 J. 13 The nondimensional numbers are then A = 1, H a = 5.48 × 10 -3 , and B o = 3.07 × 10 -11 , and the film relative thickness should span

E* ∈ [10 -2 , ∞].
Equation 5 was solved numerically following a previously developed method 14 in which the supplementary term given by eq 6a, arising from the liquid/substrate interaction, has been introduced. The symmetry condition [η*]′ = 0 at r* = 0, a nearly flat surface profile [η*]′ ≪ 1, and a negligible probe/ liquid interaction potential Π pl * ≈ 0 far from the symmetry axis were maintained as boundary conditions.

To calculate the film deformation analytically, we can write the separation distance D* as a function of the apex position η 0 * and the curvature κ 0 * at r* = 0 as follows where the function f(η 0 *, κ 0 *) is defined as

η η κ * = * + + * * - D f 1 [ ( , )] 0 0 0 1/3 (7)
η κ κ η η * * = * + * - + * * + * - ⎡ ⎣ ⎢ ⎢ ⎛ ⎝ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ ⎤ ⎦ ⎥ ⎥ f H A E E B H ( , ) 2 8( ) 1 1 a o a 0 0 0 3 0 3 0 (8)
D* can also be expressed by introducing ε 0 *, the dimensionless gap between the probe surface and the deformed liquid interface inferred from Figure 1:

η ε * = + * + * D 1 0 0 (9)
In dimensional terms, D -R represents the gap between the probe and the nondeformed film surface. Comparing eq 9 with an expansion of eq 7 gives

ε η κ η κ η κ * = * * - * * + * * - - - f f O f 1 2 [ ( , )] 1 8 [ ( , )] {[ ( , )] } 0 0 0 1/3 0 0 2/3 0 0 1 ( 10
)
which allows us to calculate the magnitude of the gap if f(η 0 *, κ 0 *) is known.

In previous studies, [12][13][14]21 it has been stated that no solution of the problem can be found for distances below the threshold distance D min * because the jump-to-contact phenomenon takes place. This minimum separation distance also marks the critical point at which the maximum apex deformation η 0,max * and the maximum curvature κ 0,max * occur. D min * is obtained directly when dD*/dη 0 * = 0, which applied to eq 7 gives

η η η ′ * = * + * - f f f 1 36 { ( )} [ ( )] {1 [ ( )] } 0,max 2 0,max 8/3 0,max 1/3 (11)
An expression f(η 0 *), which must be used in eq 11 to obtain η 0,max * , exists when it is possible to express the curvature in terms of the apex deformation, κ 0 *(η 0 *). Afterward, once η 0,max * is known, D min * is determined using eq 7.

In the following section, this approach is applied to generate analytical expressions of the maximum deformation η 0,max * and the minimum distance D min * in the asymptotic cases corresponding to E* → 0 (shallow-film limit) and E* → ∞ (thick-film limit).

SURFACE SHAPE

3.1. General Description. Some typical surface profiles obtained numerically are shown in Figure 2 for a radial extension of about 10 times the probe radius. Note that the presented window is much smaller than the capillary length so that the entire interface deformation is not shown. The profiles are reported for a single separation distance of D* = 1.29 and for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1. The relative thickness E* varies over several orders of magnitude in the range of [10 -10 , ∞]. We observe that all of the profiles exhibit a bump-like shape that is roughly parabolic around r* = 0, followed by an exponential-like decay. The profiles obtained for E* > 10 2 are overlapped, indicating the existence of an asymptotic bulk regime. The vertical displacement of the surface weakens in magnitude, and the deformation seems to be confined to a shorter radial extent as E* is reduced. In addition, the curvature of the surface at r* = 0 lowers with decreasing E*.

The corresponding behavior of apex deformation η 0 * at r* = 0 is shown in Figure 3 as a function of the separation distance D*. As observed for infinite film thickness, 14,22 we found a stable and an unstable position of the interface for any film thickness. In Figure 3, we present the stable deformation, corresponding to the minimal free energy of the system, that is present when experiments are performed. Similar hyperbolic evolutions for η 0 * are observed for the different values of E*. When sweeping from right to left, as the curve approaches the threshold distance D min * , the slope increases dramatically until a vertical asymptote is reached. At D min * , the maximum possible apex position η 0,max * is attained. For shorter separation distances, the probe/liquid attraction becomes unconstrained and the socalled jump to contact is observed, which provokes the wetting of the probe in a real situation. Consistent with expectations on physical grounds, a decrease in E* leads to a decrease of D min * along with a shrinkage of η 0,max * as the attractive liquid/substrate potential pulls the liquid film uniformly downward, therefore inhibiting its upward displacement. In other words, when the film thickness is decreased, the jump to contact is shifted to separation distances shorter than that observed for a bulk liquid. Additionally, it is relevant to remark that a reduction of E* provokes a similar effect to that induced by a diminution of H a for the bulk. 14 The corresponding evolution of the apex curvature κ 0 * as a function of the surface deformation η 0 * is shown in Figure 4 for different values of the relative thickness E*. As a general trend, for a given E*, the apex curvature increases along with the associated deformation, showing a nearly constant slope on the presented logarithmic scale. Nevertheless, mainly observed for the curves belonging to E* ≤ 10 -1 , the slope gradually becomes steeper as η 0 * increases and approaches the value of η 0,max * . In most cases, the behavior of each curve seems to be properly described by a power law. For relatively thick films, an exponent of 3 / 2 has been found, 12,13 whereas for shallow films and small deformations an exponent of 4 / 3 is discerned. The theoretical analysis of these two particular power laws is given in section 4.

3.2. Jump to Contact. Now the effect of the film thickness on the jump-to-contact condition is discussed. Figure 5 reports the evolution of the maximum apex position η 0,max * and the minimum separation distance D min * as function of the film relative thickness. Both D min * and η 0,max * show analogous trends. The bulk behavior is characterized by a plateau, which in the presented case takes the values D min * ≈ 1.29 and η 0,max * ≈ 0.09 for thicknesses E* > 10 2 . However, D min * → 1 and η 0,max * → 0 when the limit of E* → 0 is approached. These two asymptotic behaviors are associated with two characteristic film thicknesses that will be discussed in more detail in the following section. For intermediate thicknesses typically varying from 10 -1 to 10 2 , D min * and η 0,max * go through a transition regime associated with noticeable variations due to the film thickness. It is interesting that for the nondimensional parameters considered here η 0,max * never takes larger values than the film relative thickness E*. In other words, η 0,max * /E* < 1.

In Figure 6, interface shape η* at D* = D min * is shown as a function of the radial position r* for different values of E*. As previously discussed, the maximum apex position η 0,max * and the radial extent of the deformation diminish when E* is reduced. As a consequence, the surface profile sharpens, which provokes a dilatation of the curvature at the surface apex. Indeed, as observed in Figure 4, for a fixed value of η 0 *, the apex curvature κ 0 * grows significantly by orders of magnitude when the film relative thickness E* decreases.

On the basis of these results, we can define two behaviors depending on the film thickness. For thin films, the amplitude of the surface deformation is small and restricted to a length scale significantly shorter than the capillary length, clearly indicating the appearance of a localized tip effect. This phenomenon is characterized by a deformation profile of confined radial extent, specifically restricted to the near-field underneath the probe. In contrast, for thick films, the surface deformation of large magnitude is observed up to the capillary length. Hence, the tip effect is not observed for thicknesses above a characteristic value, which is found within E* ∈ [10 2 , 10 3 ], and as a consequence, the deformation corresponds to that of the bulk. 14 3.3. Deformation Length Scales. To understand the localized tip effect and to identify the different length scales arising in this problem, we linearize normalized eq 5 for small surface deformations. Far from the axis, where r* → ∞, the surface is nearly flat, [η*]′ ≪ 1, the probe/liquid interaction potential is negligible, Π pl * ≈ 0, and the liquid/substrate interaction potential, Π ls *, is approximated by the first-order term in eq 6a for [η*] ≪ E*. Therefore, the surface profile in this region is obtained from where the dimensionless capillary length λ C * = λ C /R = (γ/ ΔρgR 2 ) 1/2 and a dimensionless film characteristic length λ F * = λ F /R = (8(E*) 4 /(3AH a )) 1/2 appear. λ F = (2πγE 4 /H ls ) 1/2 corresponds to the radial distance beyond which the liquid/ substrate interaction contributes to the flattening of the liquid surface. A condition for observing the localized tip effect is thus given by λ F ≪ λ C , which is satisfied in the shallow film limit E → 0. As clearly revealed in eq 12, these two length scales are compared through an effective capillary length, λ CF * = 1/((λ C *) -2 + (λ F *) -2 ) 1/2 , that indicates which one of the two mechanisms, gravity or the liquid/substrate interaction, prevails and controls the radial extent of the deformation. In the literature, 12 the inverse of λ CF * has been introduced as an effective Bond number, which indicates when the effect of the substrate is negligible. Indeed, the exact solution of eq 12 is given by

η λ * = * * ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ GK r 0 CF ( 13
)
where K 0 is a zeroth-order modified Bessel function of the second kind and G = η CF * /K 0 (1), with η CF * being the surface deformation at r* = η CF * . For the studied range of parameters, G ≲ 10 -2 and K 0 (1) ≈ 0.42. Thus, for r* ≥ η CF * , η* ≲ 10 -2 and [η*]′ ≲ 10 -3 , demonstrating the validity of the small deformation hypothesis.

In the particular case of an R = 1 × 10 -8 m silicon AFM probe interacting with a PDMS film of thickness E ≈ R deposited over a silicon wafer, the film characteristic length λ F ≈ 2.2 × 10 1 R is much smaller than the corresponding capillary length λ C ≈ 1.8 × 10 5 R.

CHARACTERISTIC FILM THICKNESSES

The characteristic radial length scales are now used to highlight the existence of two characteristic film thicknesses. When the capillary length λ C and the film characteristic length λ F are of the same order of magnitude, film thickness effects are expected to be observed. The first critical film thickness E g is obtained from

λ F * ≈ λ C * π ρ ≃ Δ * ≃ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ E H g E AH B 2 , 3 8 g ls 1/4 g a o 1/4 ( 14
)
E g is a constant of the system, independent of the probe radius R, and E g * = E g /R depends on dimensionless parameters A, H a , and B o . The value of this critical thickness in common AFM setups is

E g ∈ [10 -7 , 10 -6 ] m, corresponding to E g * ∈ [10 0 , 10 3 ].
When the film characteristic length λ F is on the order of the probe radius, the probe/liquid attraction is opposed only by the liquid/substrate attraction. Hence, from λ F * ≈ 1, we find a second critical film thickness E γ that is given by

πγ ≃ * ≃ γ γ ⎜ ⎟ ⎛ ⎝ ⎜ ⎞ ⎠ ⎟ ⎛ ⎝ ⎞ ⎠ E R H E AH 2 , 3 8 2 ls 1/4 a 1/4 (15)
E γ is a function of the probe radius, scaling as R 1/2 , and E γ * = E γ / R changes with the product of H a and A. Within common AFM setups, this critical thickness is on the order of E γ ∈ [10 -10 , 10 -8 ] m, corresponding to E γ * ∈ [10 -2 , 10 0 ]. We expect to observe different behaviors depending on the film thickness, relative to the aforementioned critical values. They might be useful for marking the boundaries of the arising regimes in which the involved mechanisms alternate their contributions.

In Figure 7, the terms in eq 5 are shown as function of the film thickness E* under the jump-to-contact condition. The presented curves correspond to our reference case for which A = 1, H a = 5.48 × 10 -3 , and B o = 3.07 × 10 -11 . In addition, hydrostatic term B o η* is not shown because its magnitude is very small compared to that of the other terms.

As can be seen on the right-hand side of Figure 7, where E* > E g *, the curvature and the probe/liquid interaction terms are nearly constant. The presence of the substrate can be disregarded because the liquid/substrate interaction term in eq 5 is negligible. Consequently, the deformation of the liquid surface results from the equilibrium between the surface tension and the probe/liquid interaction, and in dimensionless terms, it is determined only by the values of H a and B o , as described in previous studies. 14 Moreover, the minimum separation distance D min * and the maximum apex position η 0,max * do not vary with the film relative thickness E*, as depicted in Figure 5. The surface deformation spreads to the effective capillary length, which is essentially given by the usual capillary length λ CF * ≈ λ C *, because in this case λ F * ≫ λ C *. We shall name this regime the asymptotic "thick-film" behavior.

For a film with an intermediate thickness E γ * < E* < E g *, though the liquid/substrate term continues to be negligible, the curvature term and the probe/liquid interaction are not constant anymore. These two terms increase slowly and simultaneously, remaining in balance, when reducing the film relative thickness E*, as can be discerned from Figure 7. In this case, the deformed surface shape stretches out to the effective capillary length λ CF * , which takes values between the capillary length λ C * and the film characteristic length λ F *. This constraint forces the surface to recover from its deformation, getting back to a flat profile at a radial distance shorter than the capillary length. The resulting restrained interface shape shows a curvature that is greater than that of the deformed bulk. Hence, the surface position results from the interplay of the three involved physical mechanisms: surface tension and probe/liquid interaction forces act directly, whereas liquid/ substrate interaction force appears by means of an implicit modification of the curvature.

On the left-hand side of Figure 7, where E* < E γ *, the curvature term seems to reach a saturated state. Meanwhile, the probe/liquid and the liquid/substrate attraction terms increase monotonically, approaching each other in magnitude as E* decreases from E γ * toward smaller values. Hence, the effect of the proximity of the substrate dominates over that of the surface tension, and the position of the film free surface is retrieved from the equilibrium of the probe/liquid and the liquid/substrate attractive interactions. D min * and η 0,max * change significantly with the film relative thickness E*, as shown in Figure 5. A direct effect of the substrate attraction is observed on the radial span of the surface deformation λ CF * . In this case, λ F * ≪ λ C *; therefore, the effective capillary length is mainly given by the film characteristic length λ CF * ≈ λ F *. Hence, the deformation profiles are sharp, and they are restrained to a very narrow zone around r* = 0. We name this regime the asymptotic "shallow-film" behavior, where the localized tip effect is observed.

FILM THICKNESS ASYMPTOTIC BEHAVIORS

5.1. Thick Film. Considering the limit of a thick film E* > E g *, the surface deformation is controlled by the capillary force and the probe/liquid interaction. The force due to the surface deformation can be taken as

πγ η ≈ * γ F R 0 (16)
Also, the force mutually exerted between the probe and the liquid surface can also be approximated by the force between a sphere and a flat surface: 17

ε ≈ * F H R 6 ( ) pl pl 0 2 (17)
Therefore, when the equilibrium between these two forces is attained, the surface deformation is described by

η ε * ≈ * H 8( ) 0 a 0 2 (18)
In the limit E* → ∞, with the dominant term in eq 8 being the one containing the curvature, the function f(η 0 *, κ 0 *) is given by

η κ κ * * ≃ * f H ( , ) 2 0 0 0 a (19)
which, combined with the first-order approximation of eq 10, results in an expression for ε 0 * in terms of κ 0 *. Taking this within eq 18, one obtains the power law relation of the curvature in terms of the apex deformation

κ πγ η κ η ≃ * ≃ * ⎜ ⎟ ⎛ ⎝ ⎞ ⎠ C H R C H 3 2 , 2 (
)
pl 0 0 3/2 0 a 0 3/2 (20)
which is in agreement with that observed in Figure 4 for large values of E* and has been previously found for the bulk. 12,13 For this case, where H a = 5.48 × 10 -3 and B o = 3.07 × 10 -11 , coefficient C takes a value of 6.37 × 10 -2 . The employment of eqs 19 and 20 in eqs 11 and 7 allows us to forecast the asymptotic bulk behavior shown in Figure 5. 5.2. Shallow Film. We now focus on the particular evolution observed in Figure 4 for shallow films, E* < E γ *, and small deformations. Consequently, according to the relative contributions shown in Figure 7, the first-order surface deformation results from the balance between the probe/liquid and the liquid/substrate interactions. The force due to the liquid/substrate interaction can be taken as

η ≈ * * F H R E ( ) ls ls 0 4 (21)
Equilibrium between this expression and the probe/liquid interaction force, given by eq 17, yields

η ε * ≈ * * E A ( ) 6 ( ) 0 4 0 2 (22)
Now, the dominant term in eq 8 comes from the liquid/ substrate interaction, and the function f(η 0 *, κ 0 *) for η 0 */E* → 0 is given by

η κ η λ * * ≃ * * f H ( , ) ( ) 0 0 0 a F 2 (23)
The asymptotic shallow film behavior is obtained when combining eq 23 with eqs 11 and 7, which is a good approximation of the numerical results displayed in Figure 5.

From the first-order approximation of eq 10, we find an expression for ε 0 * in terms of η 0 *, which when substituted into eq 22 gives

η * ≈ * E A ( ) 24 0 4 (24)
Moreover, from the balance between the two interaction terms in eq 5

- Π * = Π * AH H 1 8 a ls a pl (25)
the free surface shape of the thin film is given by

η η * * -* + * - = * D r E A [( ) 1] 8( ) 3 2 2 3 4 (26)
from which, at r* = 0 and considering D* ≫ η 0 *, we obtain

η * ≃ - * * E A D 8( ) 3 ( 1) 0 4 2 3 (27)
Differentiating eq 26 and evaluating at r* = 0 gives

κ * ≃ - * * E A D 16( ) ( 1) 0 4 2 4 (28)
Finally, by combining the last two relations in order to eliminate D*, we find that

κ η κ η ≃ * ≃ * * ⎜ ⎟ ⎜ ⎟ ⎛ ⎝ ⎞ ⎠ ⎛ ⎝ ⎞ ⎠ ⎛ ⎝ ⎜ ⎜ ⎞ ⎠ ⎟ ⎟ H H E R A E 3 1 , 3 0 ls pl 0 4/3 0 0 4/3 3 3 (29)
which is in agreement with the trend observed in Figure 4 for shallow films and small deformations. Within this regime, the minimum separation distance D min * and the maximum apex position η 0,max * are significantly modified by the film relative thickness E*, in contrast to the thick-film case. Note also that the deformation is dependent on the Hamaker constant ratio, A, but not on the modified Hamaker and Bond numbers.

PROBE SIZE EFFECT

With the purpose of determining the experimental parameters for AFM measurements, the probe size and the film thickness effects are quantitatively studied. Therefore, the dimensional jump-to-contact threshold is analyzed, considering the constant physical properties of the system. The combined effect of H a and E* on the deformation for a given value of H ls = H pl is equivalent to studying the effects of R and E on the free surface displacement. The dimensionless representation depicted in Figure 5a corresponds to the evolution of η 0,max * in terms of E* for a single value H a = 5.48 × 10 -3 . As a consequence, it is possible to reconstruct the dimensional dependency of the maximum apex displacement η 0,max on the film thickness E, but only for R = R 3 = 10 -8 m with parameters γ = 3.1 × 10 -2 N/m and H pl = 4 × 10 -20 J. Additionally, considering the same physical parameters, we solved eq 5 numerically for different values of E and for R 2 = 10 -6 m and R 1 = 10 -4 m. In Figure 8, the maximum apex displacement η 0,max is displayed as a function of the film thickness E for the three probe radii. One notes that the evolution of η 0,max (E) follows similar tendencies: for E < E γ , η 0,max increases linearly with E; for E γ < E < E g , η 0,max grows monotonically as E increases with a slowly declining slope; and finally for E > E g , η 0,max reaches a plateau. Figure 8 points out that for a shallow film E < E γ the maximum apex displacement η 0,max is independent of the probe radius R. A linear dependency of the displacement on the thickness, η 0,max = α 0 E with α 0 ≃ 0.33, is found. Because E γ grows as R 1/2 , the linear regime is extended to a larger range of E. Furthermore, the value of η 0,max at the plateau, characteristic of bulk behavior E > E g , increases with the value of R. As depicted in eq 14, E g is constant for a given set of physical parameters, whatever the value of R. In Figure 8, the free surface displacement of a bulk liquid due to its interaction with a probe of millimetric size, R 0 = 10 -3 m ≈ λ C , is also represented. In the theoretical case in which R = λ C , the two critical film thicknesses collapse into a single value, E g = E γ . As a consequence, the value of η 0,max obtained with R = R 0 in the bulk regime corresponds to the maximum displacement that the liquid surface can attain by increasing the probe radius, even for R > λ C . Hence, for probes of larger radius, the system can be modeled as a film interacting with a flat, solid surface for which the maximum apex displacement is approximately the same as for R ≈ λ C and completely independent of R. Table 1 reports the characteristic parameters computed for the different values of R.

The combined analysis of Figures 6 and8 shows that the localized tip effect is observed only for shallow films for which E < E γ . As a consequence, when R increases, the localized tip effect is observed at larger thicknesses as a result of the relation between E γ and R. Within this regime, the linear dependency of η 0,max on E can be understood by considering that the confined liquid behaves as a linearly elastic solid. This is in agreement with the linear relationship observed between the displacement and the thickness of confined materials undergoing a constant force test. [START_REF] Tordjeman | Squeeze elastic deformation and contact area of a rubber adhesive[END_REF] In conclusion, the localized tip effect is characterized by a constant deformation η 0,max /E = α 0 . In the particular case of A = 1, the value α 0 ≈ 0.33 is found.

A film with a very small thickness compared to the size of the probe (R ≫ E) corresponds to E < E γ , so the surface deformation at the jump-to-contact results from the balance between the probe/liquid and the liquid/substrate interactions. Considering the geometric decomposition, D min = R + η 0,max + ε 0,min , we can deduce from Figure 5 that the surface displacement and the gap are comparable in magnitude, η 0,max ≈ ε 0,max . Thus, taking into account the dependency η 0,max = α 0 E, we find that the gap is much smaller than the probe radius, ε 0,min ≪ R. Therefore, eq 1 can be condensed to where α 1 = 1 -(1 + α 0 ) -3 . The balance between these two simplified potentials gives

ε α ≃ - A E [ ] 0,min 1 1/3 (32)
Using this result, a linear evolution of the gap between the probe surface and the originally flat surface is yielded:

α α -≃ + - D R A E { [ ] } min 0 1 1/3 (33)
In Figure 9, D min -R is shown as a function of E for different values of R. D min -R behaves essentially the same way as η 0,max , shown in Figure 8. The only difference is that the magnitude of D min -R is slightly superior to that of η 0,max , for the same value of E. The linear dependency described by eq 33 is verified in Figure 9 for small values of E.

The value of gap D min -R should be respected when performing AFM measurements because it indicates the experimental set point needed to avoid the jump to contact and the wetting of the probe. For example, colloidal AFM probes, with a radius of R = R 2 = 10 -6 m, must be used at a distance of D min -R ≳ 10 -8 m when scanning, whereas for common AFM probes with R = R 3 = 10 -8 m, we should use D min -R ≳ 10 -9 m, which is 1 order of magnitude closer to the interface.

CONCLUSIONS

We have studied the interaction between an AFM probe and a liquid film deposited over a flat substrate. The competition between probe/liquid and liquid/substrate attraction determines the equilibrium position of the liquid surface. The radial extent of the deformation reaches the effective capillary length λ CF , which takes values between the capillary length λ C and the film characteristic length λ F . When the deformation extends up to λ CF ≈ λ C , gravity is responsible for the flattening of the surface. However, when λ CF ≈ λ F , the liquid/substrate attraction is the mechanism that restrains the deformation.

From these two characteristic length scales, the existence of two characteristic film thicknesses, E γ and E g , is pointed out. E γ depends on the liquid/substrate interaction constant and the liquid surface tension, also scaling as R 1/2 . In contrast, E g is independent of the probe radius R, taking a constant value for a given set of physical properties of the system.

For shallow films (i.e., E < E γ ), the maximum apex displacement varies linearly with the film thickness η 0,max = α 0 (A)E and is independent of R. In addition, a localized tip effect is revealed, which is characterized by a deformation of localized radial extent λ CF ≈ λ F and small amplitude. For thick films (i.e., E > E g ), no tip effect is observed, and η 0,max takes a fixed value independent of the film thickness E but given by the probe radius R.

From a practical point of view with the aim of performing AFM experiments, E γ emerges as the relevant characteristic thickness, which can be used to separate two regimes: a linear regime for E < E γ where η 0,max and D min are controlled by film thickness E and a plateau regime for E > E γ where η 0,max and D min are mainly determined by probe radius R.

Corresponding Author

*E-mail: dominique.legendre@imft.fr; philippe.tordjeman@ imft.fr. Phone: +(33)0534322858. Fax: +(33)0534322991.

Notes

The authors declare no competing financial interest. 1, as well as the value of E g . The horizontal line (---) is the solution of eq 7 for D min -R, considering the thick-film approximation already described in Figure 8 for R 0 ≳ λ C ≈ 10 -3 m.

Figure 1 .

 1 Figure 1. Surface deformation of the liquid film interacting with a spherical probe.

Figure 2 .

 2 Figure 2. Surface profiles of the film η* obtained from solving eq 5, at a constant D* = 1.29, for different values of E* and for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1.

Figure 3 .

 3 Figure 3. Apex position η 0 * of the air/liquid interface as a function of D* for different values of E* and for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1. (•) Numerical solutions of eq 5 and (---) extreme values D min * and η 0,max * .

Figure 4 .

 4 Figure 4. Apex mean curvature κ 0 * as a function of η 0 * obtained for different values of E* and for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1. (•) Numerical solution of eq 5 and (---) extreme values κ 0,max * and η 0,max * .

Figure 5 .

 5 Figure 5. (a) η 0,max * and (b) D min * , as functions of E*, for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1. (•) Numerical solution of eq 5 and asymptotic approximations for (---) E* > E g * and (-) E* < E γ *, with E g * = 9.05 × 10 1 and E γ * = 2.13 × 10 -1 . The approximations are obtained by applying eqs 19 and 20 for thick films and eq 23 for shallow films to eqs 11 and 7 in sequence. The characteristic thicknesses, E g * and E γ *, are defined in eqs 14 and 15, respectively.

Figure 6 .

 6 Figure 6. Surface profiles of the film η* obtained from solving eq 5 at D* = D min * for different values of E* and for H a = 5.48 × 10 -3 , B o = 3.07 × 10 -11 , and A = 1.

Figure 7 .

 7 Figure 7. Absolute value of the different terms Y j from eq 5 for which ∑ Y j = 0 as functions of E* at D* = D min * and for A = 1, H a = 5.48 × 10 -3 , and B o = 3.07 × 10 -11 . The hydrostatic term B o η*, which is not represented herein, remains on the order of 10 -11 . The critical film thicknesses are E γ * = 2.13 × 10 -1 and E g * = 9.05 × 10 1 .

Figure 8 .

 8 Figure 8. Maximum apex displacement η 0,max as a function of the film thickness E for H ls = H pl = 4 × 10 -20 J and different values of the probe radius R (R 1 = 10 -4 m, R 2 = 10 -6 m, and R 3 = 10 -8 m). The values of E γ , corresponding to the different values of R, are summarized in Table1, as is the value of E g . The horizontal line (---) is the solution of eq 11, considering the thick-film approximation given by eqs 19 and 20 for R 0 ≳ λ C ≈ 10 -3 m.

( 1 )

 1 Bhushan, B., Ed. Springer Handbook of Nanotechnology; Springer: New York, 2004. (2) Bocquet, L.; Charlaix, E. Nanofluidics: from bulk to interfaces. Chem. Soc. Rev. 2010, 39, 1073-1095. (3) Li, T.-D.; Riedo, E. Nonlinear viscoelastic dynamics of nanoconfined wetting liquids. Phys. Rev. Lett. 2008, 100, 106102. (4) Riedel, C.; Sweeney, R.; Israeloff, N.; Arinero, R.; Schwartz, G.; A., A.; Tordjeman, P.; Colmenero, J. Imagining dielectric relaxation in nanostructured polymers by frequency modulation electrostatic force microscopy. Appl. Phys. Lett. 2010, 96, 213110. (5) Maali, A.; Bhushan, B. Measurement of slip length on superhydrophobic surfaces. Philos. Trans. R. Soc. A 2012, 39, 2304-2320. (6) Kim, J.; Jang, J.; Zin, W. Estimation of the thickness dependence of the glass transition temperature in various thin polymer films. Langmuir 2000, 16, 4064-4067. (7) Grohens, Y.; Hamon, L.; Reiter, G.; Soldera, A.; Holl, Y. Some relevant parameters affecting the glass transition of supported ultrathin polymer films. Eur. Phys. J. E 2002, 8, 217-224. (8) Butt, H. J.; Cappella, B.; Kappl, M. Force measurements with the atomic force microscope: technique, interpretation and applications. Surf. Sci. Rep. 2005, 59, 1-152. (9) Yaccot, A.; Koenders, L. Aspects of scanning force microscope probes and their effects on dimensional measurements. J. Phys. D: Appl. Phys. 2008, 41, 103001. (10) Ondarcuhu, T.; Aime, J.-P. Nanoscale Liquid Interfaces: Wetting, Patterning and Force Microscopy at the Molecular Scale; Pan Stanford Publishing: Singapore, 2013. (11) Christenson, H. Capillary condensation due to van der Waals attraction in wet slits. Phys. Rev. Lett. 1994, 73, 1821-1824. (12) Quinn, D.; Feng, J.; Stone, H. Analytical model for the deformation of a fluid-fluid interface beneath an AFM probe. Langmuir 2013, 29, 1427-1434. (13) Ledesma-Alonso, R.; Legendre, D.; Tordjeman, P. Nanoscale deformation of a liquid surface. Phys. Rev. Lett. 2012, 108, 106104. (14) Ledesma-Alonso, R.; Tordjeman, P.; Legendre, D. Multiscale deformation of a liquid surface in interaction with a nanoprobe. Phys. Rev. E 2012, 85, 061602. (15) Hamaker, H. C. The London-Van der Waals attraction between spherical particles. Physica 1937, 4, 1058-1072. (16) de Gennes, P.-G.; Brochard-Wyart, F.; Quere, D. Capillarity and Wetting Phenomena: Drops, Bubbles, Pearls, Waves; Springer: New York, 2004. (17) Israelachvili, J. N. Intermolecular and Surface Forces, 3rd ed.; Academic Press: Burlington, MA, 2011. (18) Bergstrom, L. Hamaker constants of inorganic materials. Adv. Colloid Interface Sci. 1997, 70, 125-169. (19) Visser, J. On Hamaker constants: a comparison between Hamaker constants and Lifshitz-van der Waals constants. Adv. Colloid Interface Sci. 1972, 3, 331-363. (20) Mougin, K.; H., H. Wetting of liquid films at nanoscale heterogeneous surfaces. Europhys. Lett. 2003, 61, 660-666. (21) Cortat, F. P.; Miklavcic, S. J. How closely can a solid approach an air-water surface without becoming wet? Phys. Rev. E 2003, 68, 052601. (22) Wang, Y. Z.; Wang, B.; Xiong, X.; Zhang, J. Spherical solid model system: exact evaluation of the van der Waals interaction between a microscopic or submacroscopic spherical solid and a deformable fluid interface. Surf. Sci. 2011, 605, 528-538.

Figure 9 .

 9 Figure 9. D min -R as a function of the film thickness E for H ls = H pl = 4 × 10 -20 J and different values of the probe radius R (R 1 = 10 -4 m, R 2 = 10 -6 m, and R 3 = 10 -8 m). The values of E γ corresponding to the different values of R are summarized in Table1, as well as the value of E g . The horizontal line (---) is the solution of eq 7 for D min -R, considering the thick-film approximation already described in Figure8for R 0 ≳ λ C ≈ 10 -3 m.

Table 1 .

 1 Values of the Dimensionless Parameters, the Characteristic Film Thicknesses, and the Bulk Apex Displacement for the Different Probe Radii and for the Given Physical Properties a

	R	[m]	R 0 ≈ λ C (10 -3 )	R 1 (10 -4 )	R 2 (10 -6 )	R 3 (10 -8 )
	H a	[1]	5.48 × 10 -13	5.48 × 10 -11	5.48 × 10 -7	5.48 × 10 -3
	B o	[1]	3.07 × 10 1	3.07 × 10 3	3.07 × 10 7	3.07 × 10 11
	E g	[m]		9.05 × 10 -7
	E γ R	[m]	6.73 × 10 -7	2.13 × 10 -7	2.13 × 10 -8	2.13 × 10 -9
	η 0,max (bulk)	[m]	2.83 × 10 -8	1.72 × 10 -8	4.31 × 10 -9	9.18 × 10 -10

a γ = 3.1 × 10 -2 N/m, Δρ = 9.7 × 10 2 kg/m 3 , and H pl = H ls = 4 × 10 -20 J.

-11 , and A = 1. (•) Numerical solutions of eq 5 and (---) extreme values D min * and η 0,max * .

-3 , and B o = 3.07 × 10 -11 . The hydrostatic term B o η*, which is not represented herein, remains on the order of 10 -11 . The critical film thicknesses are E γ * = 2.13 × 10 -1 and E g * = 9.05 × 10 1 .


Mathieu Acher
email: mathieu.acher@inria.fr

Mauricio Alférez
email: mauricio.alferez@inria.fr

José A Galindo
email: jagalindo@inria.fr

Pierre Romenteau
email: pierre.romenteau@inpixal.com

Benoit Baudry
email: benoit.baudry@inria.fr

ViViD: A Variability-Based Tool for Synthesizing Video Sequences

Keywords: D.2.2 [Software Engineering]: Design tools and techniques, D.2.5 [Testing and Debugging]: Testing tools, D.2.13 [Reusable Software]: Domain engineering Algorithms, Design, Experimentation, Multimedia Variability Modeling, Combinatorial Interaction Testing, Prioritization, T-wise, Video Generation

We present ViViD, a variability-based tool to synthesize variants of video sequences. ViViD is developed and used in the context of an industrial project involving consumers and providers of video processing algorithms. The goal is to synthesize synthetic video variants with a wide range of characteristics to then test the algorithms. We describe the key components of ViViD (1) a variability language and an environment to model what can vary within a video sequence;

(2) a reasoning back-end to generate relevant testing configurations; (3) a video synthesizer in charge of producing variants of video sequences corresponding to configurations. We show how ViViD can synthesize realistic videos with different characteristics such as luminances, vehicles and persons that cover a diversity of testing scenarios.

INTRODUCTION

Acquisition, processing and analysis of video sequences has many applications in our modern society [START_REF] Parker | Algorithms for image processing and computer vision[END_REF][START_REF] Ponce | Computer vision: a modern approach[END_REF]. Some application examples are surveillance systems, computeraided medical imaging systems, traffic control, and mobile robotics. Such systems are software-intensive and rely on signals captured by video cameras, which are then processed through a chain of algorithms. Signal processing algorithms are assembled in different ways, depending on the goal of image recognition (e.g., patterns identification, objects tracking). The algorithms produce information helpful for humans or subject to subsequent analysis. For example, algorithms could determine rectangles that cover the zone of a specific object in a scene. This information is useful for human observers that can react accordingly, e.g., to trigger alarms when tracking the movement of a vehicle or a person.

Problem. Numerous algorithms for video analysis have been and will be developed -each specialized in a specific task (e.g., segmentation, object recognition). Even for a category of algorithm, many alternatives exist; a one-sizefits-all solution capable of handling the diversity of scenarios and signal qualities is hardly conceivable. An algorithm may excel in tracking a vehicle in a desert but completely fails when the luminance is low or some distractors are present in the video scene. Another algorithm may be less performant in a normal situation, but more robust when luminance is changed and distractors are added. The diversity of situations poses a challenge for both developers and users of video algorithms. For consumers (users), the practical problem is to determine what algorithms are likely to fail or excel in certain conditions before the actual deployment in realistic settings. For providers (developers), how to have confidence and produce evidence that the algorithms are capable of handling certain situations?

A fundamental and common challenge is the testing of algorithms. Practitioners face severe difficulties to get an input test suite (i.e., a set of video sequences) large and diverse enough to test (e.g., benchmark) the algorithms. The current practice is indeed to find out some existing videos or film video sequences outside. The effort of manually collecting videos is highly consuming in resources and economically not viable. In addition, practitioners have limited control over the scenarios covered or not by the set of video sequences. We give more details in Section 2 about the industrial context and problem. As a result, the major challenge for testing the algorithms remains: How to obtain a suitable and comprehensive input set of video sequences? Solution: ViViD. In this paper, we present ViViD, a variability-based video sequences synthesis tool. ViViD is based on variability modeling techniques and languages for synthesizing video variants -only video sequences that fulfill some criteria are generated. The first criterion to generate a set of video sequences (a.k.a., a test data set) is that any pair of values of features/attributes (e.g., luminance mean=72, tilt motion=0.4) will be covered in at least one video sequence. ViViD can also prioritize the input data sets according to one or more optimization functions, for example, synthesis time or any ad-hoc function. ViViD is a comprehensive solution with a textual editor (integrated in Eclipse), solvers, and a connection with an industrial video generator in charge of synthesizing video sequence variants. ViViD is build in a way that mimic feature model automated analysis [START_REF] Benavides | Automated analysis of feature models 20 years later: a literature review[END_REF] process to obtain only meaningful video sequences. Previous research proposed to use different metrics to optimize test-suites for concrete users needs in variabilityintensive systems [START_REF] Henard | Multi-objective test generation for software product lines[END_REF][START_REF] Johansen | An algorithm for generating t-wise covering arrays from large feature models[END_REF][START_REF] Perrouin | Pairwise testing for software product lines: comparison of two approaches[END_REF]. These approaches allowed assigning more importance to some inputs than others when testing. However, they only focused on functional testing of the main system features without considering different testing objectives including quality attributes as part of the testing space. Other evolutionary-based approaches do not consider testing aspects [START_REF] Sayyad | Scalable product line configuration: A straw to break the camel's back[END_REF].

The intended audience of the demonstration are twofold. First, SPL practitioners and researchers can learn a new variability modeling language with advanced language constructs (e.g., attributes, meta-information, deltas over values) and an efficient reasoning backend to support combinatorial testing and multi-objective prioritization. ViViD is built upon the theoretical foundations exposed in [START_REF] Galindo | A variability-based testing approach for synthesizing video sequences[END_REF] and our industrial experience in designing a variability language https://github.com/ViViD-DiverSE/VM-Source. Second, the application of an SPL-based tool in an original domain (video) and in an industrial context can be of interest both for researchers and practitioners. We will demonstrate how ViViD can synthesize numerous realistic video variants (see Figure 1).

AN INDUSTRIAL PROBLEM IN THE VIDEO DOMAIN

We face the challenge of synthesizing a high number of diverse video sequences variants in an industrial project. The MOTIV project aims at evaluating computer vision algorithms such as those used for surveillance or rescue operations. A targeted scenario is usually as follows. First, airborne or land-based cameras capture on-the-fly videos. Then, a video processing chain analyzes video sequences to detect and track objects, for example, survivors in a natural disaster. Based on that information the operation manager triggers a rescue mission quickly based on the video sequence analysis information.

Two companies are part of the MOTIV project as well as the DGA (the French governmental organization for defense procurement). The two companies develop and provide numerous algorithms for video analysis. The diversity of scenarios and signal qualities poses a difficult problem for all the partners of MOTIV: which algorithms are best suited given a specific application? From the consumer side (the DGA), how to choose, select and combine the algorithms? From the provider side (the two companies), how to guarantee that the algorithms meet a large variety of situations? How to propose innovative solutions able to handle new situations?

Our partners need to collect video sequences to test their video analysis solutions and different detection algorithms. Synthesizing a high diversity of video sequences is difficult as there are many ways in which a video can change (e.g., physical properties, types and number of objects, backgrounds). Yet, synthesizing video sequences is still more feasible than filming them in real environments. Our partners calculate that an initial input data set of 153000 video sequences (of 3 minutes each), corresponds to 320 days of video footage and requires 64 years of filming outside (working 2 hours a day). These numbers were calculated at the starting point of the project based on the previous experiences of the partners. A related problem to the difficulty of synthesizing video sequences is that practitioners ignore what kinds of situations are covered or not by the set of video sequences. Therefore, it is not possible to ensure the quality of the video analysis solutions and detection algorithms in all situations. Overall, more automation and control are needed to synthesize video sequence variants and cover a diversity of testing scenarios.

THE ViViD TOOL

We promoted the use of variability techniques to address the problem: (1) a variability model to formally document what can vary within a video sequence; (2) an exploitation of the variability model to generate a certain number of testable configurations; (3) a synthesis of video variants corresponding to configurations.

We developed a tool, called ViViD, in close collaboration with the industrial partners of MOTIV. A website with all the components of ViViD is available at https: //github.com/ViViD-DiverSE/.The ViViD tool supports a novel approach that improves the current practice of filming different video sequences. We describe this tool by means of its functionality, architecture and special features.

Functionality

The main functionality of ViViD are as follows:

• support of variability modeling with a dedicated language, called VM. We design the language throughout different iterations https://github.com/ ViViD-DiverSE/VM-Source with the partners. In particular the language can be used for modeling physical, numerical properties of videos while the information of the variability model can be exploited by a video generator;

• reasoning support to prioritize pair-wise configurations while maximizing or minimizing ad-hoc objective functions. The rationale is that the number of valid configurations in a variability model can be huge. Practitioners thus need efficient techniques to get a relevant and representative subset. Combinatorial techniques are applied to produce a subset that covers many kinds of situations. Objective functions help practitioners to focus on certain kinds of situations (e.g., by prioritizing some features)

• support for synthesizing video sequences. We reuse the video generator developed by the industrial partner.

The generator is written in Lua1 language. There are extra activities that support the creation of the core assets that compose video sequences. For example, an engineering effort is needed to model 3D objects and creating masks to allow to overlap moving objects in the background. We take those extra activities as prerequisites of the ViViD tool. They are not part of the tool demonstration and out of the scope of the paper.

Architecture and Main Components

Figure 2 relates the above mentioned actions to the ViViD tool chain. We mark with red the video property luminance mean and its trace through the entire tool chain.

In the variability model specified with the VM language, luminance mean was modeled as a real attribute of the feature signal quality. The attribute will automatically receive a value in each one of the configurations, for example, the upper-most Lua configuration file assigns a value of 72.55 to the signal quality.luminance mean of the configuration file for one video sequence variant. Finally, the video sequences generator has functions in charge of producing a video sequence with the features and attribute values established in the configuration files. The ViViD tool chain is composed of three main tools:

VM model editor

VM interpreter and configuration files customizer

The VM interpreter and configuration files customizer is a complex piece of code that supports three main activities: i) to parse the VM model , ii) to translate the VM model to a Constraint Satisfiability Problem (CSP) to prioritize pair-wise video sequences configurations while maximizing or minimizing ad-hoc objective functions, and iii) to calculate and compose one video sequence by each one of the N Lua configuration files.

The VM interpreter was created as a Java application that communicates with an advanced CSP solver called Choco (http://www.emn.fr/z-info/choco-solver/) to calculate optimal video sequences configurations.

The information about the configurations is stored internally by the VM model and can be displayed in different formats: i) the VM language format for configurations, and ii) the Lua configuration files format. The first format is useful to create extra configurations manually or to visualize multiple configurations in a same file using a nice and abbreviated concrete syntax (e.g., grouping value assignments by attribute instead by feature). The second format is useful for the video sequences generator as this is the format that it reads faster.

Video sequences generator

The video sequences generator is composed of an editor and video manipulation libraries created entirely in C code and the embeddable scripting language Lua. The reason for using Lua tools is that it is very suitable to be used in small devices as it runs fast and it is considered very lightweight (the entire Lua language engine source contains around 20000 lines of C code).

Lua combines simple procedural syntax with powerful data description constructs based on associative arrays and extensible semantics. Lua is dynamically typed, runs by interpreting bytecode for a register-based virtual machine, and has automatic memory management with incremental garbage collection. These characteristics made Lua ideal for configuration, scripting, and rapid prototyping activities required by the ViViD tool.

Special Features in Action

One of the special features in the ViViD tool chain is the large support for variability modeling in the video domain. The domain is characterized by the presence of parameters with values defined in continuous domains (e.g., real numbers), and the use of configurable copies of objects, called multi-features (e.g., multiple vehicles and people).

Listing 1 shows a small example of the video sequences variability model written in the VM language that is part of the ViViD tool. The VM language is special as domain experts can specialize advanced variability models by including additional information. The most common types of additional information are:

• default values that help to complete partial configura- • deltas to discretise real domains,

• controlled descriptions in natural language about the model itself, features, attributes and constraints,

• multi-ranges and multi-deltas that allow to use several ranges and deltas to define the domain of the values of an attribute (e.g., luminance mean in Line 12 has three ranges),

• meta-information annotations such as: not translatable -@NT (tags a purely informative element, such as the scene comment in Line 9), not decidable -@ND (a element that does not help to differentiate (visually) one video sequence from other, such as cost in Line 11), and runtime -@RT (a feature or attribute that vary only at runtime, such as vehicle speed in Line 20), and

• objective functions, such as generating only low cost video sequence configurations, as shown in Line 23-25.

A website with the VM grammar, full-fledged editor and user guide is available at http://mao2013.github.io/VM/.

CONCLUSIONS

We presented ViViD, a tool that synthesizes video sequence variants. ViViD is based on variability techniques: (1) a variability language and an environment to model what can vary within a video sequence; (2) variability-aware generation of relevant, testing configurations. A video generator produces variants of video sequences corresponding to configurations. ViViD can synthesize realistic videos with different characteristics (e.g., variations of luminance, adding of vehicles and persons) to cover a diversity of testing scenarios.

We are developing ViViD with industrial partners in the context of a research project (MOTIV). We are now in the process of launching a large-scale testing experience involving hundreds of video sequences -something not possible at the beginning of the project. The ViViD tools has different licenses, while the VM language and the VANE tool are distributed as open source, the video-sequence generator has a close license. Those free parts of the tool can be found in the tool website and are being integrated in FaMiLiar [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF].

We hope that the demonstration of the ViViD tool and its design can inspire other practitioners to apply variability modeling, combinatorial testing, multi-objective prioritization and product synthesis techniques in other original domains and industrial contexts.

Figure 1 :

 1 Figure 1: Six variants of video sequences synthesized with ViViD

Figure 2 :

 2 Figure 2: ViViD Tool chain

9 @

 9 NT string sequence . comment 10 @RT int vehicle . speed [ 0 .. 1 3 0 ] delta 5 default 4 0 11 @ND int *. cost [ 0 .. 1 0 0 0 ] default 1 n e r a t e _ l o w _ c o s t _ c o n f i g u r a t i o n s { 25 min (sum (*. cost ) ) 26 } 27 Configurations: // . . . Listing 1: Example variability model written in the VM language tions,

http://www.lua.org/

Acknowledgements

This works was financed by the project MOTIV of the Direction Générale de l'Armement (DGA) -Ministère de la Défense, France.


Bach Van Pham

Artur Maligo

Simon Lacroix

ABSOLUTE MAP-BASED LOCALIZATION FOR A PLANETARY ROVER

Navigating autonomously several kilometers in a planetary context without any communication with Earth operators raises several challenges. Among those, precise localization is of essential importance, and the availability of orbital data yields the possibility to estimate absolute position information. This paper proposes an approach that exploits a priori Digital Elevation Maps derived from orbiter data and on-board stereo imagery to estimate the absolute rover position. The approach extends the classic particle-filter based global localization scheme to the context of planetary rovers, where the environment is not structured. The article details the various required functions, the way each particle likelihood is evaluated, and means to manage a short number of particles. Experimental results illustrates the approach.

INTRODUCTION

Autonomous long range navigation for a planetary rover calls for a localization approach whose drift is boundedotherwise the rover is not able to reach its goal or follow the planned itinerary. Localization using dead-reckoning techniques such as inertial navigation, wheel odometry or visual odometry [START_REF] Howard | Real-time stereo visual odometry for autonomous ground vehicles[END_REF] do not suffice for long range navigation as they eventually drift over time or the distance travelled. By memorizing and exploiting the detected landmarks, SLAM approaches (see e.g. [2] in a planetary context) reduce the drift of dead-reckoning approaches, however navigating over long ranges does not yield loopclosures, and hence the drift remains unbounded.

The availability of high resolution orbiter imagery, such as provided by the HIRISE camera of the Mars Reconnaissance Orbiter, yields the possibility to develop map-based absolute localization approaches for planetary rovers, with a precision that is independent of the travelled distance. In this paper, we propose an approach which allows to localize the rover within a known map ("absolute navigation") with a precision of the order of 2 meters. The proposed system uses on-board stereo vision and a global Digital Elevation Map (DEM) of 1m resolution, similar to the DEM derived from HIRISE imagery.

The approach relies on the use of a particular filter, as often proposed for map-based localization approaches, and the two main contributions are (i) the estimation of each localization hypothesis likelihood using an on-board built DEM from range data, and (ii) a specific management of the particles to maintain tractable computation times.

Outline the next section presents previous work on absolute navigation in planetary contexts, and the principle of particle filter approaches to map-based localization. Section 3 is the heart of the paper: it depicts the way a particle filter is designed to efficiently yield precise absolute position estimates. Section 4 presents field trials, using aerial imagery to mimic orbiter maps. Section 5 concludes the article, and presents an adaptation required to exploit the approach in Earth environments.

BACKGROUND

Absolute localization in planetary contexts

Skyline-based approaches First attempts to estimate the global position of the rover using global DEM relied on skyline matching [3,4]: the principle is to match a perceived skyline with a database of skylines pre-computed on the basis of the DEM. The database encodes skyline signatures, that are matched with the skyline extracted from a panoramic image taken by the rover. This solution has proved to efficiently find the global position of the rover in the "lost-in-space" situation, i.e. when the rover has no information on its initial position. It yields an estimation accuracy of 100-150 meter on a 30 m/pixel DEM [5], but the DEM must cover an area be large enough to allow the prediction of the skyline. Also the approach is not effective if the rover is within very rough areas or narrow corridors, where the horizon is hardly detectable.

Feature-based approaches [6] presents and approach that exploits large rocks extracted from the high resolution satellite images. Surface rocks are extracted from the 3D point cloud produced by the on-board stereo camera [7], and the rover position is determined by finding a 2D transformation that gives the maximum number of matches between the rocks detected from the two sources. In order to reduce the search area for the 2D transformation, the authors propose to firstly match the local DEM with the global DEM. Experiments presented in [6] show that the system is capable of matching rock with a success rate of up to 50 percent. This approach is limited by the nature of the terrain: desert areas with no rocks, or on the contrary very rough ares, in which rocks are hardly defined are difficult to handle.

[8, 9] proposed the use of a LIDAR to estimate the global position of the rover. An initial global DEM is processed to obtain a global database: topographic peaks (local maxima) are extracted with morphological operators, and a similar process is used to extract the topographic peaks from the local DEM. Peak matches are established with the "DARCES" process: several hypotheses of 3 matches are firstly obtained by comparing the inter-distance of the peaks. Then, these hypotheses are compared to each other to select the one with the 2D transformation that gives the higher number of matches. The estimation is then passed to a SLAM module. The experimental results obtained with 1.5 km range and 360 degree LIDAR scan give an average precision of 22 meter with a global DEM of 17 m/pixel resolution. Other noteworthy work compare global and local DEM with spin-images [10]. Note however that planetary contexts preclude the use of LIDARs, due to their heavy weight and high power consumption. In addition, LIDARs provide data at much longer ranges than stereovision, making this approaches hardly applicable to planetary rovers.

Map-based localization using a particle filter

A well-known framework used to estimate the global position of a robot is provided by Monte Carlo Localization (MCL) [11], also called particle filter. In this method, the posterior probability density function corresponding to the robot global position is approximated by a set of samples, the so-called particles. By doing this, MCL can take into account the multiple possible positions that arise in the lost-in-space problem. Particles are associated to weights which are computed using an observation model and a prior global map of the environment. In [12], an urban context implementation of the method is proposed, in which the authors use a Route Network Description File (RNDF) as the prior map. RNDF maps provide specific information about the roads structure and thus can be efficiently used to localize vehicles in this context. In another urban environment example [13], infrared reflectivity maps of road surfaces are built, and LIDAR sensors are used to acquire reflectivity information that are then matched with the maps data. Both approaches make use of urban oriented prior models and matching techniques, which are clearly not adapted to planetary unstructured landscapes.

Outdoor generic environments are considered in [14], where the authors show that observation models can be learned directly from the alignment between the prior map and the sensors data. However, this alignment is computed using high quality GPS information, which is not available in a planetary context. A variation of the particle filter, the Rao-Blackwellized particle filter [START_REF] Doucet | Rao-blackwellised particle filtering for dynamic bayesian networks[END_REF][START_REF] Grisetti | Improved techniques for grid mapping with rao-blackwellized particle filters[END_REF], is often used in SLAM applications where each particle has its own global map to which observations are compared. In our problem, the prior global map is provided by an orbiter and such a variation is not adapted.

PROPOSED APPROACH

In our approach, a local DEM is built from stereovision data gathered by the rover, and is matched to the global DEM provided by the orbiter. We chose a particle filter estimation scheme to cope with the fact that the robot initial position parameters can be totally unknown, or only bounded, without any further information. For computation efficiency purposes, instead of sampling particles in a continuous space, our implementation considers a discretized space. Additionally, particles carry an uncertainty with them, modelled by a Gaussian distribution. The discretized sampling and the Gaussian nature of particles is used to manage them as the rover moves.

Discretized Particle Filter

Given a map M , odometry measurements u and observations z, the key idea of the particle filter is to estimate the posterior density of the current rover state x k based on all the information available: p(x k |z 1:k , u 0:k , M ). The state is often chosen as x = [x, y, θ], in environments where we a planar surface assumption can be made, or as x = [x, y, z, ψ, θ, φ], in outdoor complex environments. The posterior is computed in three steps: (i) prediction, where particles are sampled according to a motion model, (ii) update, where the compute particle weights are computed using a likelihood function given by an observation model, and (iii) re-sampling, where particles are resampled according to their previously computed weights. Our discrete particle filter, however, includes an initialization step and adds an extra sampling step after the prediction, as further explained in this section.

Unlike the classic particle filter, where particles are sampled in a continuous manner, we choose to sample them in a discrete manner. The discrete space has the same (x, y) resolution as the global DEM, while the angular resolution of the heading can be defined arbitrarily 1 . In the discretized filter, only one particle is assigned to a discrete position: this is is done by merging particles that occupy the same cell, as shown Figure 1.a). This is meant to reduce the number of particles, as there would be no difference between the predicted observations of particles belonging to the same cell. The discrete position of a particle i is defined according to its coordinates (x i , y i ) and its heading θ i :

S i = (⌊ (x i -x O ) r x ⌋, ⌊ (y i -y O ) y x ⌋, ⌊ θ i r θ ⌋) (1)
were x O , y O is the origin of the global map, r x , r y is the resolution of the global map, and r θ is the angular resolution of the heading. This discretization principle is similar to the one of grid-based Markov localization approaches [START_REF] Burgard | Integrating global position estimation and position tracking for mobile robots: the dynamic markov localization approach[END_REF][START_REF] Burgard | Estimating the absolute position of a mobile robot using position probability grids[END_REF], with the difference that such approaches consider all cells and angles, while our particle filter only maintains the state of existing particles. In addition to the discretization process, our filter models the uncertainty associated to a particle by a Gaussian distribution. This technique complements the filter and could be seen as a way of modeling the information loss caused by the discretization. The uncertainty is also taken into account in the additional sampling step, when particles are added next to particles whose distributions have high variances, as illustrated Figure 1.b).

Algorithm Outline

The overall algorithm consists of 5 steps. The initialization is only applied at the beginning of the mission or when the filter is reset. The other four steps, run sequentially and repeatedly, are prediction, sampling, update and re-sampling. Apart from the sampling step which is specific to our implementation, these are the classic particle filters steps.

1. Initialization: To avoid convergence to a wrong local maximum, the correct position of the rover must be occupied by one of the initial particles. To ensure this, a full search is performed and the likelihood of all the discrete cells is evaluated with the same mapmatching process used in the update step of the algorithm. Particles are then generated in the positions that obtained the highest likelihoods. 2. Prediction: when a new motion measurement u k is received, the position of each particle i is modified according to:

x i k = x i k-1 ⊕ u k (2)
In our experiments, we use the Visual Odometry (VO) DROID [START_REF] Harris | Active vision. chapter Geometry from visual motion[END_REF] motion measures. The Gaussian distribution of each particle is modified by simply adding the VO variances. In the classic particle filter, particles would be sampled according to this motion measures and its associated uncertainty. Here, however, we represent this uncertainty explicitly in the Gaussian distribution, and hence we can directly increase the distribution variances to take the uncertainty into account. The sampling step complements this operation and uses the Gaussian modeling to sample additional particles around highly uncertain ones.

3. Sampling: this step is introduced to add new particles and ensure that the rover actual position is still represented by one of the considered particles. Given a particle i, its Gaussian distribution standard deviations are compared with the coordinate resolution and with the angular resolution. If the standard deviation is sufficiently large, new particles are created in the discrete positions around the original one (Figure 1.b). After this process, the Gaussian distribution of the particle i and the newly created particles are reset to half of the global resolution and angular resolution. New particles are added in a deterministic manner, which is not the case in normal sampling operations where particles would be sampled in a random manner. By doing this, we ensure that the filter will always consider all the possible positions.

4. Update: in our application we use a pair of stereo cameras and thus our observations z k consist of the acquired 3D point clouds. These measurements are not directly used but are merged within a local DEM m k centered around the rover. We keep updating the local DEM with new observations and analyzing its quality before actually using it in the likelihood calculation (details on the local map building process are given in section 4.2). Using the global DEM, we define a predicted local map t i k for each particle i using its associated position x i k . The likelihood of a particle i is evaluated with the computation of the Zero mean Normalized Cross-Correlation score (ZNCC) of the DEMs:

ZN CC i k = 1 n -1 x,y (m k (x, y) -mk )(t i k (x, y) -ti k ) σ m k σ t i k (3)
where (x, y) is the index of the non-empty cells of the local map m k , t i k is the predicted map for particle i, and mk , ti k , σ m k and σ t i k are respectively the means and standard deviations of the local and the predicted DEMs. Simpler scores could have been used (e.g. the Sum of Absolute Differences), but ZNCC proved to give more discriminant measures. Since ZNCC scores belong to [-1; 1], negative values are set to zero to avoid assigning negative weights to particles. The weight of the particle i is updated using

w i k = w i k-1 * ZN CC i k (4)
5. Re-Sampling: as in [START_REF] Doucet | Rao-blackwellised particle filtering for dynamic bayesian networks[END_REF][START_REF] Grisetti | Improved techniques for grid mapping with rao-blackwellized particle filters[END_REF]2], the effective number of particles is calculated by

N ef f = 1 N i=1 ( wi k ) 2 (5)
where wi k represents the normalized particles weights. If the value of N ef f is smaller than N 2 , the re-sampling operation is carried out and particles are re-sampled with probabilities given by their weights. Weights are then reinitialized to 1 N . Figure 2.b) shows the remaining particles after applying a few iterations of the filter: they converged around the actual robot position, near a steep slope.

EXPERIMENTS

Generation of a global DEM with a UAV

Our experiments were carried on in a sand quarry. To mimic the resolution of the global DEM of a plane-tary mission (namely 1 m/pixel resolution with HIRISE DEM), we used a UAV to build a global DEM of the test area from a sequence of aerial images (Figure 3). The global DEM is built thanks to a commercial bundle adjustment software, that produces 5 cm/pixel DEM and orthoimage (Figure 4). Ground markers whose position has been assessed with a cm-accuracy RTK-GPS have been used to geo-reference the global map, and finally the global DEM is down-sampled to 1 m/pixel.

Trials

Parameter setup

We used the robot Rimmer of RAL Space [START_REF] Woods | Seeker autonomous long range rover navigation for remote exploration[END_REF], that was manually driven in the mapped area of the sand quarry. The stereovision bench is a Point Grey Bumblebee VGA system, tilted down of 15 o . The rover speed is 0.2 m/second, and the pictures are acquired at 5 Hz (according to a requirement of the VO). The VO, stereovision, DEM building and absolute localization algorithms run on-board of a Core i7 2GHz Linux PC.

Stereovision runs at 1 Hz on VGA images, and the 3D points within a range of 15 meters from the rover are retained 2 , and merged in a local 1 m/pixel resolution DEM of 30 × 30m 2 . This size has been defined considering two factors: it requires very little memory and makes the absolute localization run faster, and within such a range, the errors of VO have a negligible impact on the building of the DEM.

We assume that the absolute heading (yaw) angle of the rover is known thanks to the use of a Sun sensor, which is mimicked with GPS ground truth measures, that yield a heading precision of ±3 degrees. However, our approach can handle no prior heading information, at the cost of more computational time. The filter update step is only applied when two requirements are satisfied: with respect to the previous update, the rover must move far enough and the local DEM must have been significantly updated. The particles position and Gaussian distribution are however continuously updated as the rover moves. All of the tests presented here were made with the lost-in-space situation, the search is made on the entire global map. For all tests, the initial number of particles is 500, and the maximum number of particle allowed is 1000.

Results

Estimation error

To estimate global position of the rover, we calculate the mean and standard deviation of the global position of the particles. Figure 5 illustrates the estimation results obtained with (case A) and without (case B) heading information. It is important to note that the heading information is only used in the particle initialization step. The top image in Figure 5 shows that the estimation error of case A initially is higher than case B. In reality, this initial error depends on the shape of the global DEM or more concretely on the similarity between the local DEM and some particular regions in the global DEM. Then, as the rover starts to move, the error of case A raises: this is a particular case, caused by the fact that a cluster of wrong particles are removed, which here shifts the mean position further away from the true position.

Figure 5 bottom shows the evolution of the standard deviation. In contrast to the rise of the estimation error due to the shift of the mean position, the reduction in the standard deviation value means that the particles converge. The standard deviation values shows that the algorithm in case A converges faster and stabilises after 58 meters of traveled distance, in comparison of 78 meters of case B. Once the estimation is stabilised (with an error of about 1.0 m), there is no difference between the two cases. The algorithm has naturally more chance to converge with prior heading data, but it does not necessarily converges faster: the convergence rate depends much more on the shape of the traversed terrain.

Influence of the angular resolution The angular resolution plays a very important role. Fine angular resolution allows better result both in global position and in absolute heading estimation. A coarse angular resolution, in contrast, needs less computational time. The top image in Figure 6 compares the estimation result of 3 , 5 and 10 degrees angular resolution with the case without prior heading information. As shown in the plot, the case with 3 degrees angle converges a little faster than the other cases, whereas the average estimation error of the 3 cases is almost similar. However, there are some turn-on-thespot moments when the yaw estimation error raises, the cases with 3 and 5 degrees angle work better than the one with 10 degrees.

Performance The particle initialization is run used once and is by far the most computational expensive step. Computations depend on the size and resolution of the local and global DEMs and on the angular resolution. discretization. Table 1 presents the initialization run time for the 3, 5, 10 degrees angular resolutions, with and without prior heading information. It shows that the angular resolution has no influence when prior heading information is used.

The time required by the particle updates are much smaller, and reaches at most 0.1 seconds for the worst cases.

Figure 7 shows the number of particle used during three tests without prior heading data. All tests are initialized with 500 particles. Once the rover moves, the Gaussian distribution are updated using the VO estimation, and new particles are generated by decomposing this Gaussian distribution, while wrong particles are removed during the re-sampling step. These generations and removals of the particles cause the zig-zag appearance of the curves, which is more marked with 3 degrees angular angle, as more particles are generated given the same Gaussian distribution.

CONCLUSION

Discussion

Absolute localization is an essential functionality for autonomous long range navigation of planetary rovers, but has received little attention. Skyline matching approaches are rather suited for flat areas with mountainous landscapes on the horizon, where the skyline is well defined, whereas feature-based approaches require the presence of easily extractable features. The approach proposed in this paper complements well with these approaches, as it works particularly well on areas with strong terrain reliefs. An ideal absolute localization system would required the integration of the three approaches: one could then define a pre-processing of the global DEM that would state where each approach is expected to behave well. Experiment results show that the method can provide localization estimate with 2m accuracy on a 1m resolution global DEM. In addition, the adaptations made to the particle filter yield a system with a low computation footprint. There remain however some drawbacks: during the initialization phase, the actual position of the rover must be among the particle candidates, and like any particle filter based method, good particles can be removed during the re-sampling phase.

Future Work

The proposed algorithm has been adapted to urban environments and to the use of panoramic long range LIDAR. Figure 8 presents results obtained on a 0.1 m/pixel DEM of a parking lot built by the robot during a learning phase during which cm-accuracy GPS was available. Two different resolutions of the global DEM are used: a global DEM with 1 m/pixel resolution is exploited to initialize the particles, and a global DEM with 0.1 m/pixel is used to update the particles. To further reduce computations, a Hough-based ground extraction algorithm segments 3D point of the local 30 × 30m 2 DEM into ground and offground points, and only off-ground 3D points are used to update the particles.

Figure 1

 1 Figure 1. a): comparison between continuous particles (left), and discretized ones (right). b): Gaussian uncertainty and particle sampling by decomposition.

  Figure 2. a) initialization of particles. b) distribution of particles along a steep slope (the ground truth is the red spot on both images).

Figure 3 .

 3 Figure 3. Examples of aerial images used to generate the global DEM

Figure 5 .

 5 Figure 5. Absolute localization results with ("case A") and without ("case B") heading information with 1 m/pixel resolution global DEM and 3 degrees angular resolution.

Figure 6 .

 6 Figure 6. Influence of the angular resolution: results with 3, 5 and 10 degrees angular resolutions, without prior heading information.

Figure 7 .

 7 Figure 7. Number of particles during 3 without-priorheading-data tests.

Table 1 .

 1 Initialization time with 3, 5, 10 degrees angular resolutions, with and without prior heading information.

		Known heading	Unknown heading
	Ang. res.	3 o	5 o	10 o	3 o	5 o	10 o
	Run-time(s) 4.78 4.77 4.75 186.95 111.29 56.76

The roll and pitch angles are nor considered, assuming that they are precisely provided by the inertial navigation sensors of the rover.

The Bumblebee stereo bench has a 24cm baseline, and points below 15m have errors compatible with a 1 m/pixel DEM.

ACKNOWLEDGMENTS

Most of the work presented in this paper were sponsored by the ESA-founded SEEKER project [20] with the participation of Roke Manor, Scisys, RAL Space, MDA, BAE System and LAAS-CNRS.