Guillaume Caron

Eric Marchand

El Mustapha Mouaddib

Tracking planes in omnidirectional stereovision

Omnidirectional cameras allow direct tracking and motion estimation of planar regions in images during a long period of time. However, using only one camera leads to plane and trajectory reconstruction up to a scale factor. We propose to develop dense plane tracking based on omnidirectional stereovision to answer this issue. The presented method estimates simultaneously the parameters of several 3D planes along with the camera motion in a spherical model formulation. Results show the efficiency of the approach.

I. INTRODUCTION

Motion estimation remains one of the key issue in the development of vision systems. Although the omnidirectional camera geometrical model (central projection model [START_REF] Barreto | Issues on the Geometry of Central Catadioptric Imaging[END_REF]) is now well known, few researches have been done to solve visual tracking problems. Omnidirectional cameras offer a very wide field of view, allowing the perception of landmarks during a long period of time in image sequences, which is an important asset to the precision and robustness of an object tracking process.

Available tracking techniques uses either a 3D model leading mainly to a pose estimation process (eg, [START_REF] Drummond | Real-Time Visual Tracking of Complex Structures[END_REF] in the perspective case and [START_REF] Marchand | Fitting 3D Models on Central Catadioptric Images[END_REF] for central catadioptric image) or 2D features, such as geometrical primitives (point, segments, circles, etc.) or object contours (such as active contours). One can also consider 2D models which can be a reference image (or a template). The goal is to estimate the motion (or warp) between the current image and the reference template. Examples of such approaches are differential tracking methods such as the KLT [START_REF] Baker | Equivalence and Efficiency of Image Alignment Algorithms[END_REF], [START_REF] Benhimane | Homography-based 2D Visual Tracking and Servoing[END_REF], [START_REF] Hager | Efficient Region Tracking With Parametric Models of Geometry and Illumination[END_REF], [START_REF] Lucas | An Iterative Image Registration Technique with an Application to Stereo Vision[END_REF].

In this paper, we consider a such approach within an omnidirectional stereovision sensor.

The warp to be estimated is a homography. This 2D motion model has the advantage to be exact for a plane whatever the camera motions are. This motion model was first defined for perspective camera model but is in fact valid for all central projection cameras [START_REF] Mei | Efficient Homography-Based Tracking and 3-D Reconstruction for Single-Viewpoint Sensors[END_REF], [START_REF] Salazar-Garibay | Visual Tracking of Planes with an Uncalibrated Central Catadioptric Camera[END_REF] of which some omnidirectional ones [START_REF] Baker | A Theory of Single-Viewpoint Catadioptric Image Formation[END_REF].

The central projection model have already been used for plane tracking in omnidirectional monocular images (eg [START_REF] Mei | Efficient Homography-Based Tracking and 3-D Reconstruction for Single-Viewpoint Sensors[END_REF]). This approach is similar to the one proposed in [START_REF] Benhimane | Homography-based 2D Visual Tracking and Servoing[END_REF] although the registration between reference template and current image is done directly on the omnidirectional images. Nevertheless, the image gradients, needed to link image intensities to the variation of the motion, are computed Guillaume Caron and El Mustapha Mouaddib are with Universit de Picardie Jules Verne, MIS laboratory, Amiens, FRANCE; e-mail: {guillaume.caron, mouaddib}@u-picardie.fr Eric Marchand is with Université de Rennes 1, IRISA, INRIA Lagadic, Rennes, France; e-mail: eric.marchand@irisa.fr in the image plane. However, it has been shown [START_REF] Demonceaux | Omnidirectional image processing using geodesic metric[END_REF] that the filtering of omnidirectional images should be done on the spherical image rather than on the omnidirectional planar image. Indeed, the spherical geometry, for these images, is adapted to keep the properties of the convolution product used to compute gradients since it allows a regular sampling of the image whereas this is not possible in the image plane.

This work proposes to formulate the simultaneous tracking of image planar templates, constrained by homographies, directly within the spherical image space. Furthermore, rather than estimate a homography for each plane, we propose to estimate the camera pose, up to a scale factor, and recover the parameters of 3D planes. Based on this new spherical formulation, we then propose to use a stereoscopic catadioptric sensor allowing to perform the complete stereoscopic plane reconstruction, including scale factor, and tracking of spherical image planar regions. These three aspects together are the contribution of this work.

Thanks to the unified spherical projection model, the proposed stereoscopic plane reconstruction and tracking approach is generic and apply to all systems with multiple central cameras. But practically, stereoscopic systems may suffer from synchronization problems and even chromatic inconsistency between cameras. Hopefully, catadioptric omnidirectional stereovision can be achieved using a unique camera and several mirrors which solves the two latter problems. The used stereo catadioptric system is composed by an orthographic camera and four parabolic mirrors. This configuration (Fig. 1) has been proven to be optimal [START_REF] Devendeville | On Omnidirectional Catadioptric Stereovision Design, Iberian Conf. on Pattern Recognition and Image Analysis[END_REF] and the image resolution in stereo tracking results is taken from this work.

The reminder of the paper presents the spherical tracking of a plane in monocular central vision, recalling the camera projection model and the projective transformation of a 3D plane motion before developing the spherical tracking itself. Then, the stereoscopic spherical plane tracking is presented. Finally, tracking results using a single camera and a stereo omnidirectional camera are presented, in static and mobile camera conditions. A conclusion highlighting the contributions of this work closes the paper.

II. SPHERICAL PLANE TRACKING A. Camera model

According to the unified model [START_REF] Barreto | Issues on the Geometry of Central Catadioptric Imaging[END_REF], a central projection camera can be modeled by a first projection on a sphere, with a unit radius and a center (0, 0, ξ) T expressed in the camera frame, followed by a perspective projection on the image plane. Such a model can be defined using a unique parameter ξ which depends intrinsically on the central camera type.

Knowing intrinsic parameters γ = {p x , p y , u 0 , v 0 , ξ}, a 3D point X = (X, Y, Z) T is first projected as X S on the unitary sphere:

X S = (X S , Y S , Z S ) T = pr S (X) = X ρ , Y ρ , Z ρ T (1)
where

ρ = √ X 2 + Y 2 + Z 2 .
Then this point is projected in the image plane as x = (x, y, 1). The relationship between X and x is expressed as:

x = pr ξ (X) with x = X Z+ξρ and y = Y Z+ξρ . (2)
x is the point on the normalized image plane and the image point in pixelic coordinates is obtained by the application of intrinsic parameters matrix u = Kx.

To back-project x to the equivalent sphere, the func-

tion pr -1 ξ (.) is used, knowing β = ξ+ √ 1+(1-ξ 2 )(x 2 +y 2 )
x 2 +y 2 +1 : X S = pr -1 ξ (x) = (βx, βy, β -ξ) T .

B. Projective transformation associated to a 3D plane

The coordinates of a point on the 3D plane in two views (for c 1 and c 2 ) are related by a homography. Considering the rotation c2 R c1 and the translation c2 t c1 between the two camera positions over time, the homography H, defined up to a scale factor [START_REF] Mei | Efficient Homography-Based Tracking and 3-D Reconstruction for Single-Viewpoint Sensors[END_REF], is given by:

H ∝ c2 R c1 - c2 t c1 c1 n T c1 d , c2 t c1 ∈ R 3 and c2 R c1 ∈ SO(3) (3
) where c1 n is the normal to the plane of interest expressed in the first camera frame and c1 d the orthogonal distance from the origin of this coordinates system to the plane. The homography is a 3 × 3 matrix and has 9 parameters, h 1,1 to h 3,3 and 8 degrees of freedom. To fix the scale, h 3,3 is forced to be equal to 1.

According to the unified model, a central camera is modeled by a sphere and the homography H links two corresponding points c1 X S and c2 X S on two spheres, up to a scale factor:

c2 X S = α c2 X S = H c1 X S . (4)
Actually, a homography relates two corresponding view lines and since we are working on the equivalent sphere, the spherical point c2 X S corresponding to c1 X S , after being transfered using H, is:

c2 X S = c2 X S / || c2 X S ||. (5)

C. Plane tracking on the unit sphere

To achieve plane tracking, we propose to use a differential minimization method that aims to compute the homography allowing to transfer spherical points of the reference sphere to the current one minimizing the sum of square differences of spherical image intensities. Even if tracking a plane directly estimating the coefficients of the projective transformation matrix H leads to the minimal set of parameters to estimate, the tracking is here defined in the Euclidean space. Hence, the rotation, translation, plane normal and distance are explicitly estimated. Since the camera motion is the same for all the scene planes, this formulation allows to consider efficiently multi planes tracking (see section II-D).

The criterion to minimize for the plane tracking is then:

Ĥ = arg min h k i=1 I S HX * S,i -I S X * S,i 2 (6)
where X * S is a point of the reference region and the vector of parameters to estimate is h = (n, d, r) T . r is a vector representation of the relative pose and H is computed thanks to these parameters with the equation ( 3).

Considering a feature vector I S (h), the set of spherical image intensities of the region of interest, obtained after the transfer of the reference one using the homography, the error to be regulated is:

e = I S (h) -I * S . (7)
Imposing an exponential decrease of this error, we have ė = -λe. The time variation of the intensity at a given point on the sphere is defined thanks to the Cartesian spherical optical flow constraint equation (OFCE). Assuming a temporal luminance consistency for a moving spherical image point:

I S (X S + ∆X S , t + ∆t) = I S (X S , t). ( 8
)
and if ∆X S is small enough, the OFCE is valid:

∇I T S ẊS + İS = 0. ( 9
)
∇I S is the spatial Cartesian spherical gradient of I S (X S , t). Hence, the time variation of I S is then expressed as:

İS = -∇I T S ẊS . ( 10
)
ẊS can be decomposed as:

ẊS = dX S dt = ∂X S ∂h dh dt = G X S h ḣ = J X S | L X S   ṅḋ v   (11)
where v = (υ, ω) T is the camera relative pose velocity. Jacobian J X S expresses the variation of a spherical point w.r.t. the 3D plane (constrained normal and distance), and L X S is known as the interaction matrix (for a relative pose, here) and is [START_REF] Hamel | Visual servoing of an under-actuated dynamic rigid-body system: An image-based approach[END_REF]:

L X S = 1 ρ (X S X T S -I 3×3 ) [X S ] × . (12)
L X S mainly depends on the coordinates of a spherical point, apart from ρ, which is the distance of the 3D point in the current camera frame (eq. 1). This distance is obtained by intersecting a viewline and the 3D plane. Equations ( 10) and ( 11) lead to the image Jacobian related to I S at spherical point X S :

G I S (X S ) = -∇I T S G X S h . (13)

D. Tracking of several planes

To deal with a moving camera and tracking multiple planes, the problem can be formulated to compute only one relative pose and several normal and distances. In such a case, intensities of a planar region are used to compute their corresponding plane whereas the intensities of all the planar regions are used to compute the relative pose. Hence, the Jacobian linking the variation of image intensities to the camera motion and parameters of p planes is:

G I S =      -∇I (1) S -∇I (2) S . . . -∇I (p) S      T        J (1) X S 0 . . . 0 L (1) X S 0 J (2) X S . . . . . . L (2) X S . . . . . . . . . 0 . . . 0 . . . 0 J (p) X S L (p) X S        (14)
where (i) shows the plane number to which the Jacobian is related to and its corresponding feature set. Then, the error vectors corresponding to each plane are stacked together and are related, thanks to the latter multiple planes Jacobian, to the camera and planes parameters velocity:

V = ṅ(1) ḋ(1) ṅ(2) ḋ(2) . . . ṅ(p) ḋ(p) v T (15)

E. Parameters update

The time variation of planes and relative pose vector is computed thanks to a Levenberg-Marquart (LM) optimization method:

V = -λ (Q + µ diag(Q)) -1 G T I S    I S (h (1) ) -I * S . . . I S (h (p) ) -I * S    (16)
with

Q = G T I S G I S and h (i) = n (i) , d (i) , r T . If µ is
very high, the optimization behaves like a steepest descent whereas a very low value for µ leads equation ( 16) to behave like a Gauss-Newton method. LM is often used since it ensures a better convergence, thanks to a controlled and efficient step. The relative pose is updated at iteration it with the exponential map of se(3) [13] using c2 M it c1 = c2 M it-1 c1 e [v] . Plane parameters are updated by addition of their time variation.

F. Gradients computation on the sphere

Computing ∇I S means to compute the spherical image derivation along X, Y and Z axes. Since the spherical image is a surface which can be minimally parameterized using azimuth and elevation angles, φ and θ, spherical image gradients are computed w.r.t. to these parameters and then transformed to get the "3D" image gradient.

Omnidirectional image filtering is only valid on the equivalent sphere where convolution is commutative with regular sampling. The technique to compute gradients is to use intensities from a spherical neighborhood for the convolution [START_REF] Demonceaux | Omnidirectional image processing using geodesic metric[END_REF].

The two linear neighborhoods

φ N and θ N of length l, considering ∆ φ,θ = arccos(| 0 0 1 .pr -1 ξ ( u 0 + 1 v 0 1 T )|),
are expressed as:

   φ N = θ, φ + k∆ φ T , -l 2 ≤ k ≤ l 2 , k = 0 θ N = θ + k∆ θ , φ T , -l 2 ≤ k ≤ l 2 , k = 0 . ( 17
)
Neighborhoods are then projected on the image plane to retrieve intensities. Nearest neighbor interpolation is done to make the process fast and to allow precomputation of spherical neighbors projected in the image plane for each pixel. These neighborhoods are used with an image derivative filter.

Finally, gradient values I φ , I θ are used to compute I X S , I Y S and I Z S , where I A = ∂I ∂A knowing the Cartesian-polar coordinates transformation, φ = arccos(Z S ) and θ = arctan(Y S /X S ), and using partial derivatives ∂φ,θ ∂X S .

III. STEREOSCOPIC SPHERICAL 3D PLANE TRACKING

Relative pose estimation in a monocular plane tracking, even with several planes, is estimated up to a scale factor. Dealing with a calibrated stereo rig allows to fix the scale and to have planes and relative position in meters.

Figure 2 shows the geometric relations between corresponding points in spherical views. Based on these considerations, the stereoscopic plane tracking has two main stages. First, the search for regions in the three views corresponding to the reference template is made, estimating the 3D plane parameters. Then, for any new stereo image, the relative pose is computed simultaneously to the plane parameters optimization. Therefore, we estimate only a minimal set of parameters.

A. Stereoscopic model

For a stereo rig of N cameras, each camera is modeled using the spherical model. Relative poses of N -1 cameras c j , j = 1..N , of the rig, modeled by homogeneous matrices cj M c1 , are defined w.r.t. the reference one, c 1 . In the present case, since the used stereo sensor for our experiments is composed of one orthographic camera and four parabolic mirrors, we consider a stereo rig of four central cameras (N = 4). Simultaneous intrinsic and extrinsic calibration has been done using an extension of a stereo omnidirectional virtual visual servoing approach [START_REF] Caron | 3D Model Based Pose Estimation For Omnidirectional Stereovision[END_REF].

B. Stereoscopic spherical 3D plane tracking

Tackling planar region tracking in stereovision images, the reference region is defined in the part of the image corresponding to the first camera c 1 . Before tracking the plane over time, dense correspondence is needed in the three other views. It is simultaneously done with the 3D plane reconstruction in a tracking process, thanks to the short baseline of the used stereo sensor.

1) Stereoscopic initialization: For the stereo initialization step, only the plane normal and its orthogonal distance to the reference camera center is computed. Indeed, from homogeneous transformations cj M c1 , rotation and translation from a camera to the reference one are known. Hence, the intensities of the three other views are related to the image of c 1 , merging together the information of the four views to compute one 3D plane expressed in the c 1 frame.

A spherical point of the first camera is transfered to the camera j using equation ( 4) and cj M c1 obtained from the stereo calibration. Merging together the four spherical images in a LM minimization method, leads to the following Jacobian and error vector:

J =   J I S 2 (X S ) J I S 3 (X S ) J I S 4 (X S )   and e =   I S2 ( c2 H c1 X * S ) -I S1 (X * S ) I S3 ( c3 H c1 X * S ) -I S1 (X * S ) I S4 ( c4 H c1 X * S ) -I S1 (X * S )   (
18) where J I S j (X S ) is the Jacobian related to intensity of the j-th spherical image at point X S (eq. ( 11)):

J I S j (X S ) = -∇I T Sj ∂X S ∂N ∂X S ∂d . ( 19
)
Then, the normal and the distance are updated adding their time variation to their previous values and homographies cj H c1 are recomputed after this update using cj R c1 and cj t c1 obtained by calibration, similarly to equation (3).

2) Eight views stereoscopic tracking of several planes: After the stereoscopic initialization step of each plane, their tracking over time is led, estimating the relative pose t M 0 between two stereo rig poses. This relative pose is expressed between the current position at time t and the reference position at time 0 of the reference camera, c 0 1 and c t 1 , of the stereo rig. Hence, at time t, image features of cameras c 2 , c 3 , c 4 are expressed w.r.t. c 1 . Then, the information at time t are linked to the image of camera c 1 at time 0. The information of the four cameras at time 0 are still used to constrain the parameters of the 3D plane.

So, to sum up, the image region of c 0 1 , corresponding to the plane of interest, forms the desired features and the images of c 0 2 , c 0 3 , c 0 4 are used to optimize c1 n and d. c t 1 , c t 2 , c t 3 , c t 4 are used to optimize both the 3D plane parameters and the relative pose of the stereo rig.

Considering the pose c t j M c 0 1 , the pose Jacobian L I S (X S ) related to I S at point X S is:

L I S j (X S ) = -∇I T Sj L X S j . (20)
L X S is defined in equation ( 12). However, L X S of mirrors 2, 3 and 4 are transformed to be expressed in the c 1 frame [5] using the twist transformation matrix, computed thanks to cj M c1 , between velocity vectors of camera 1 and camera j. This leads to the Jacobian G for the stereoscopic tracking of several planes. For brevity, a Jacobian of two planes tracked by a stereo rig of two cameras is shown but it is extendable to any number of planes and cameras (four cameras and two planes in the results). The Jacobian relates spherical image intensities to the 3D planes and the relative pose between current and reference stereo rig positions:

G =               J (1) I S 0 2 (X S ) 0 0 0 J (2) I S 0 2 (X S ) 0 J (1) I S t 1 (X S ) 0 L (1) I S t 1 (X S ) J (1) I S t 2 (X S ) 0 L (1) I S t 2 (X S ) c2 V c1 0 J (2) I S t 1 (X S ) L (2) I S t 1 (X S ) 0 J (2) I S t 2 (X S ) L (2) I S t 2 (X S ) c2 V c1               . (21)
c t j H c 0 1 is the homography, related to the plane of interest between c 1 at time 0 and c j at time t, computed using estimated plane normal and distance and the rotation and translation extracted from c t j M c 0 1 = cj M c1 t M 0 . Finally, Jacobians J I S 0 j are recomputed at each iteration since the 3D plane parameters are always updated.

For brevity, details of the LM optimization are not given here but the equation is really similar to equation [START_REF] Salazar-Garibay | Visual Tracking of Planes with an Uncalibrated Central Catadioptric Camera[END_REF]. Finally, without giving much details, a robust estimator based on M-Estimation [START_REF] Huber | Robust Statistics[END_REF] is considered to reject outliers and improve robustness w.r.t. illumination changes, including specularity, and partial occlusion.

IV. RESULTS

The initial plane selection is done manually by clicking four points to define a reference template in the first image. In stereovision images, the selection is only done in the top left mirror. Corresponding regions in other mirrors are automatically found.

The processing is currently real time for only one plane tracked by one camera but the implementation of the method clearly needs to be optimized as the processing time evolves as a function of the number of pixels in tracked regions.

A video presents these results in the research section of the website: http://mis.u-picardie.fr/∼g-caron.

A. Mobile omnidirectional camera

The tracking of several planes is experimented using a paracatadioptric camera acquiring images of 640 × 480 pixels (450 × 450 useful). Figure 3(a) shows the first image with selected planar regions of the processed sequence. The experiment is led with a mobile robot embedding the camera and making a loop, coming back near its original position and continuing its motion along a straight line in a corridor. In this sequence the motion of the planar regions in images is very important as well as perspective effects. Furthermore, each tracked plane is successively partially occluded (Fig. 3(b)) and some specularity appears. Finally, both tracked planes are visible in the major part of the sequence but not in the corridor. To deal with this kind of issue, when camera position is too close from the plane and if its image region surface is too small, the particular plane is no longer tracked.

The tracking succeeds all along the sequence and the estimated camera/robot trajectory (Fig. 3(e)) shows the stability of the estimation, even in presence of partial occlusions. The standard deviation of the Z estimates is 2.64 cm for the complete sequence, 1.5 cm when tracking two planes and 2.19 cm after stopping to track the plane P 1 . To compare, the tracking of plane P 0 only leads to a Z standard deviation of 4 cm for the complete sequence (small instability when partially occluded). Variations of estimated normal parameters (always in the coordinates system of the first camera position) emphasizes also the estimation stability (Fig. 3(c) and 3(d)). Real planes are vertical as the camera axis and, hence, their estimated Z component is 0. X and Y components depends on the orientation of the plane in the first camera frame (Fig. 3(a)).

B. Static stereoscopic omnidirectional camera

In the static or mobile case, images are acquired at a resolution of 800×800 pixels, leading to a diameter of 400 pixels for each mirror, using the four mirrors catadioptric sensor (Fig. 1). In this experiment, the camera is static and a planar object is moved all around the camera (Fig. 4). The tracking is achieved even with important specular reflections on the real planar object (Fig. 4(b)) leading to differences between the current and the reference image template (Fig. 4(a)). The object does not makes a complete turn around the camera, that is why the final rotation angle around the vertical axis is not 0 (Fig. 4(c)).

C. Mobile stereoscopic omnidirectional camera

To evaluate the behavior of the proposed several planes tracking approach, the four view stereo sensor (Fig. 1) is used to recover the motion of the robot embedding it in a pure translation (Fig. 5).

The pure translation experiment aims to show the efficiency of the tracking method w.r.t. important motion between the first (Fig. 5(a)) and the last (Fig. 5(b)) image of the sequence. 230 images are acquired for a total motion of 2.40 m. The estimated trajectory is really near the desired one (Fig. 5(c)) with a final position error, at the farthest from the observed planes, of around 10 cm. This result is obtained without adding a manually measured distance or any other information. The precision of course depends on the calibration precision and the achievement of the tracking which is efficient, here, since it succeeds despite size and orientation variations of tracked regions in images. The tracking also shows its robustness to illumination variations, specially for specularities. Finally, one can note the stability of the estimation which is also emphasized by the stability of the two plane normal vectors (Fig. 5(d)) when they have reached their optimum. This optimum can only be reached when the distance between the current and the reference view is wide enough to reduce uncertainties.

V. CONCLUSION

The tracking of 3D planes in omnidirectional stereoscopic images has been successfully led. The spherical formulation of the problem is theoretically consistent and gives precise results for the tracking as well as for the stereo system motion estimation. A particular omnidirectional stereo camera has been used with properties of perfect synchronization and chromatic similarity. Results also show the robustness of the approach to occlusions. Future work will be focused on a fully automated plane detection and tracking method based on this work. (e) Estimated trajectory with a circled green cross marking the starting position and two sets of a circle and a cross showing the trajectory parts when tracked planes are occluded (red for P 0 and black for P 1 ). The orange cross marks the end of the tracking of P 1 and a straight black line links the start position to the end.

Fig. 1 .

 1 Fig. 1. (a) Mirror part of a stereo sensor composed by (b) an orthographic camera and four coplanar paraboloidal mirrors [7] ; (c) the sensor on the mobile robot (reversed for stability reasons).

Fig. 2 .

 2 Fig. 2. Geometric relations between views. For brevity, a two views stereo rig is presented.

  (c) Evolution of the P 0 normal.(d) Evolution of the P 1 normal.

Fig. 3 .

 3 Fig.3. Curve motion along 11 m with partial occlusion. Planes P 0 and P 1 are simultaneously tracked in a sequence of 900 images until P 1 is no more visible. The rest of the estimation is done with the tracking of P 1 (from the orange cross on trajectory (e)). To have the at the good scale in meter, the distance to P 0 is manually measured from the initial camera position. The final position error is below 1 cm (unmeasurable) and the standard deviation of the estimation of the Z coordinate is about 2.64 cm for the complete estimated trajectory.

  (a) Image 0 / 450 (b) Image 220 / 450 (c) Estimated angles of rotation w.r.t. the reference image.

Fig. 4 .

 4 Fig. 4. Stereoscopic tracking of a plane all around the sensor. The rotation of the planar object is nearly pure around the camera axis (c).

Fig. 5 .

 5 Fig. 5. Straight motion along 2.40 m. The final position error is 10 cm in 3D leading to an error ratio over the path length of around 4%. Note that the smallest plane in images (a) and (b) is not vertical, that is why its Z component is not 0.


Jérôme Ardouin

Anatole Lécuyer

Maud Marchal

Eric Marchand

Design and Evaluation of Methods to Prevent Frame Cancellation in Real-Time Stereoscopic Rendering

Keywords: Stereoscopy, display technology, visualization, stereo compatible volume, clipping H.5.2 [Information Interfaces and Presentation]: User Interfaces-user-centered design, I.3.3 [Computer Graphics]: Picture/Image Generation-display algorithms, I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism-Virtual Reality 1

Frame cancellation comes from the conflict between two depth cues: stereo disparity and occlusion with the screen border. When this conflict occurs, the user suffers from poor depth perception of the scene. It also leads to uncomfortable viewing and eyestrain due to problems in fusing left and right images.

In this paper we propose a novel method to avoid frame cancellation in real-time stereoscopic rendering. To solve the disparity/frame occlusion conflict, we propose rendering only the part of the viewing volume that is free of conflict by using clipping methods available in standard real-time 3D APIs. This volume is called the "Stereo Compatible Volume" (SCV) and the method is named "Stereo Compatible Volume Clipping" (SCVC).

Black Bands, a proven method initially designed for stereoscopic movies is also implemented to conduct an evaluation. Twenty two people were asked to answer open questions and to score criteria for SCVC, Black Bands and a Control method with no specific treatment. Results show that subjective preference and user's depth perception near screen edge seem improved by SCVC, and that Black Bands did not achieve the performance we expected.

At a time when stereoscopic capable hardware is available from the mass consumer market, the disparity/frame occlusion conflict in stereoscopic rendering will become more noticeable. SCVC could be a solution to recommend. SCVC's simplicity of implementation makes the method able to target a wide range of rendering software from VR application to game engine.

INTRODUCTION

In stereoscopic real-time rendering, depth perception problems occur when objects are displayed off screen (negative parallaxes) close to the screen border. This effect has been observed since the early works on stereoscopic movies. Valyus has named the phenomenon frame cancellation [START_REF] Valyus | Stereoscopy[END_REF]. The problem comes from the conflict between two depth cues: stereo disparity tells the user that the perceived object is in front of the screen while the occlusion with the screen border indicates that the screen border is in front of the object. When this conflict occurs, the user suffers poor depth perception of the scene [START_REF] Wartell | Stereoscopic Head-Tracked Displays: Analysis and Development of Display Algorithms[END_REF]. It also leads to uncomfortable viewing and eyestrain due to problems in fusing left and right images [START_REF] Lipton | Vertical surround parallax correction. Stereoscopic Displays and Virtual Reality Systems XIV[END_REF].

Figure 1 illustrates the typical configuration of left and right eye viewing volume for a determined display surface. Intersection of the left and right viewing volume is not subject of frame cancellation while the remaining volume represents location of geometry that leads to disparity/frame occlusion conflict (D/FO conflict). Let it be noticed that the positive parallax volume is not pictured since it is not subject to the frame cancellation problem. In this paper we propose a novel method to avoid frame cancellation in real-time stereoscopic rendering. This method is based on the observation of the stereoscopic viewing volume shape. To solve the D/FO conflict, we propose rendering only the part of the viewing volume that is free of conflict by using clipping methods available in standard real-time 3D APIs. This volume is called "Stereo Compatible Volume" (SCV) and the method is named "Stereo Compatible Volume Clipping" (SCVC).

The paper is organized as follows: section 2 proposes an overview of the existing methods to solve the D/FO conflict, section 3 proposes an analysis of these methods, explaining their limitations and suitability to real-time rendering. Our approach is described in section 4, and then it is evaluated in section 5.

RELATED WORK

Although the problem has been assessed using various technical solutions in stereoscopic movies and other offline computed stereoscopic rendering, fewer methods have been developed with real-time rendering specificities in mind.

Methods from movie industry and offline stereoscopic rendering: Some digital content creation products like Autodesk Maya propose to display the intersection of the 2 view volumes (called safe viewing volume). This technique is meant to help the creators in placing objects in situation free of D/FO conflict [START_REF]Maya Software[END_REF].

The floating window is a common approach. It consists in inserting black bands on the left and right edges of the screen if the displayed content is subject to D/FO conflict [START_REF]Stereoscopic filmmaking whitepaper[END_REF]. The result is that the perceived content appears to be in positive parallaxes related to a virtual sub window positioned in user space (Figure 2).

Other approaches consist in modifying the disparity of the stereo pair globally or close to the screen edge. This can be seen as a local distortion of the 3D space, ensuring zero or positive propose to stretch the stereo pair at the border to insure zero or positive parallaxes while preserving enough negative parallax at the center of the screen so that the viewer experience remains convincing [START_REF] Lipton | Vertical surround parallax correction. Stereoscopic Displays and Virtual Reality Systems XIV[END_REF]. Modifications of the stereo pair disparity are generalized by Lang et al. [START_REF] Lang | Nonlinear Disparity Mapping for Stereoscopic 3D[END_REF] who have proposed operators on disparity maps. They are used in different manners to modify disparity of the stereo pair to achieve effects such as emphasizing subject, shifting the scene depth or magnifying the depth range. Given a stereo pair, a disparity map is computed using sparse feature matching. Operators are applied to this map in the way that tonal transformations are applied to bitmap images. Finally the stereo pair is warped to reflect the new disparity map. This is done by employing retargeting techniques [START_REF] Rubinstein | Improved Seam Carving for Video Retargeting[END_REF], preserving the structure of images in both the spatial and temporal domain. Real-time rendering methods: Mulder et al. have proposed a real-time implementation of the Black Bands through the Cadre Viewing approach [START_REF] Mulder | Enhancing Fish Tank VR[END_REF]. An improvement is also proposed with the Tunnel extension. With an overplayed grid, the tunnel can improve depth perception by providing points easy to fuse.

Ware et al. have introduced the concept of cyclopean scale, presented as a rescale of the viewed scene centered on the midpoint between the user's eyes [START_REF] Ware | Integrating Flying and Fish Tank Metaphors with Cyclopean Scale[END_REF]. Magnitude of the scaling is computed to place the virtual environment just behind the screen. This clearly avoids frame cancellation as it shifts the scene to the positive parallax half space. Combined with interactions, controls of scene scale and translation have to be performed dynamically in an intelligent manner. This problem is assessed by Wartell et al. through various derived approaches, by for example analyzing the depth buffer to compute valid parameters [START_REF] Wartell | Stereoscopic Head-Tracked Displays: Analysis and Development of Display Algorithms[END_REF].

LIMITS OF EXISTING METHODS

In the category of movie design driven methods, black band insertion is certainly the most adapted to real-time rendering. The main drawback occurs in situations where strong negative parallax objects are subject to D/FO conflict. In this kind of configuration, the virtual window can be very small and dramatically reduce the horizontal field of view. The aspect ratio of the view volume is also heavily altered. Another limitation comes from the dependency of the method on scene analysis: to determine the width of black bands we have to test each object against the stereo compatible volume. Also a part of the SCV is discarded along with the problematic portion. Cadre viewing [START_REF] Mulder | Enhancing Fish Tank VR[END_REF] limitations are roughly the same as black bands. The Tunnel extension restricts even more the viewing volume. The stretch method [START_REF] Lipton | Vertical surround parallax correction. Stereoscopic Displays and Virtual Reality Systems XIV[END_REF] and disparity map operators [START_REF] Lang | Nonlinear Disparity Mapping for Stereoscopic 3D[END_REF] are based on the analysis of the disparity of the stereo pair. The disparity map of the stereo pair is usually computed with offline algorithms such as sparse feature matching. A real-time version of these kinds of algorithms could rely on the Z buffer in conjunction with the left to right eye transformation matrix to generate a disparity map. The remaining limitation is the non constant scale of the perceived scene along screen space that could lead to disturbing effects, especially when used with head tracked display. Disparity map operators also are difficult to use in real-time as retargeting techniques imply specific computation and human guided tuning in some cases. Its need of time forward information to maintain consistency in the image structure over time is another weakness for real-time rendering.

Cyclopean scale and its variations differ radically from the above methods because they have been designed to target realtime rendering and real-time interactions. The application has to comply with scale modification of the displayed scene (with head tracked displays, maintaining 1:1 scale is often an important requirement). The type of geometry to which the method applies is also limited to convex objects so exploration of an open environment is not an option. Cyclopean scale restricts the view volume to positive parallax or very low negative parallax values. Since the negative parallax portion of the viewing volume is an area useful for collocated interactions, this point can be considered as another limitation.

A NOVEL APPROACH: STEREO COMPATIBLE VOLUME

CLIPPING

Methods presented in the previous sections are dependent on the displayed content due to the analysis of the scene geometry or the analysis of the disparity of the stereo pair. In real-time rendering, this task has to be automated and executed on each frame, leading to potentially complex and time consuming algorithms.

Definition: In the negative parallax half space, we can define the SCV as the intersection of the left and right view volumes. From a purely geometric point of view, one can solve the D/FO conflict problem optimally by rendering only the SCV.

Approach: Our method does not try to avoid situations where frame cancellation occurs; it simply rejects parts of the viewing volume that are subject to D/FO conflict. By rejecting these regions, SCVC is independent of displayed assets and does not rely on content or stereo pair disparity analysis: wide environments are treated in the same manner as small convex objects. The method also ensures the widest volume is displayed on both positive and negative parallaxes while aspect ratio is maintained. No special modification of the scene like scaling or translation is done. The view volume aspect ratio is not altered either.

Implementation: Clipping is a common method used to discard parts of polygons rendered outside of the view volume. Modern 3D APIs let the programmer add arbitrary clipping planes in the rendering pipeline. To insure that only stereo compatible volume is rendered, we add the left clipping plane of the right eye camera to the clipping planes list when rendering the right image and vice versa. We can notice that the view volume in positive parallaxes' half space is not altered. Implementation using the OpenGL fixed pipeline is straightforward in the case of simple stereoscopic rendering (asymmetric frustums and x axis aligned eyes). The clip plane of interest can be computed using 3 points: center of projection and screen plane top and bottom points (Figure 3.). For non head tracked stereoscopic display, this can be computed once and reused. Cost in terms of computation is marginal for plane equation solving while polygon tests against the additional clip planes stay cost effective when handled by the GPU.

With head tracked displays, the eyes are not necessarily x axis aligned, making the shape of the intersection of the two view volumes more complex. Adding two clipping planes per view is enough to restrict the rendered space to the SCV. In this case, the eyes' relative position determines the clipping planes that have to be used. We can select at each frame the horizontal clipping plane to use with a simple algorithm (we suppose that left and right eyes are not inverted). For the left view volume rendering: if the right eye is higher to the left eye then the bottom clip plane of the right eye view volume has to be added to the clipping planes list. If the right eye is lower to the left eye, add top clip plane of right eye view volume to the clipping planes list.

EVALUATION

Our objective was to compare SCVC with Black Bands (which seems to be the best state-of-the-art approach, a method recommended in movie industry and already successfully adapted to interactive real-time rendering). Cyclopean scale approaches tend to avoid the problem by altering the scene representation (scaling and translation) so they have not been selected.

Participants:

The evaluation was conducted using a panel of 22 participants, 19 males and 3 females aged from 18 to 37, from two groups: naive and initiated users. The 13 naive users had no knowledge of rendering techniques and have very limited experience with stereoscopy. The 9 expert users are university students who have followed real-time rendering courses with explanations of stereoscopic rendering mathematics and algorithms. Subjects suffering from binocular vision pathology were excluded.

Experimental apparatus:

The experiment apparatus consists of a CRT screen and Stereographics™ shutter glasses connected to a computer with an OpenGL stereo enabled graphic board. The user is positioned seated with his head aligned with the screen center at about 80 cm. The test application written with OpenGL fixed pipeline shows a sphere of 6 cm in diameter to the user, moving in the foreground of a plane. The sphere is positioned at 15 cm from the screen plane in the negative parallax half view volume and moves slowly on the x axis with a sine movement from the left to right border. A simple checkerboard texture is used to map the scene objects to let the user fuse left and right images more easily. Care is also taken to set lighting and contrast of the scene at relatively low values to reduce crosstalk (aka ghosting effect) between left and right views. At runtime, the software lets the user toggle the method used by typing a corresponding key. The three methods proposed are Control, SCVC and Black Bands (Figure 4). Procedure: The experiment starts with a phase where the user can switch between methods as he wishes. Then he is asked open questions about the different methods. Finally he is asked to evaluate different criteria for each method by giving them a score. During the question and evaluation phase, the user remains free to switch from one method to another as he likes.

Data collected: A subjective questionnaire was proposed in which participants had to grade from 1 (low appreciation) to 7 (high appreciation) the three techniques (SCVC, Control and Black Bands) according to 5 subjective criteria: (a) Relief Quality, (b) Relief Quality at Borders, (c) Aesthetic, (d) Eye Strain perceived and (e) Global Appreciation. Figure 5 shows the results concerning the grades (Likert-scale) obtained by the three different techniques for each of the subjective criteria.

Results: A one-way ANOVA was performed on the three different methods (SCVC, Control and Black Bands). A significant effect was found for all criteria, except Eye Strain criterion (F(2,21)=2.31, p-value=0.109). Concerning Relief Quality criterion, a significant effect was found (F(2,21)=4.75, p-value=0.012). A post-hoc analysis using Tukey's procedure showed that the grading for SCVC method was significantly higher than for Control method (p-value=0.02) and Black Bands method (p-value=0.03). There was no significant adjusted p-value between Control and Black Bands methods.

Concerning Relief Quality at Borders criterion, a significant effect was found (F(2,21)=9.15, p-value=0.0003). A post-hoc analysis using Tukey's procedure showed that the grading for SCVC method was significantly higher than for Control method (p-value=0.001) and Black Bands method (p-value=0.001). There was no significant adjusted p-value between Control and Black Bands methods.

Concerning Aesthetic criterion, a significant effect was found (F(2,21)=7.69, p-value=0.001). A post-hoc analysis using Tukey's procedure showed that the grading for SCVC method was significantly higher than for Control method (p-value=0.0006). There were no significant adjusted p-values between Control and Black Bands methods, and SCVC and Control methods.

Concerning Global Appreciation criterion, a significant effect was found (F(2,21)=12.018, p-value < 0.0001). A post-hoc analysis using Tukey's procedure showed that the grading for SCVC method was significantly higher than for Control method (p-value=0.0004) and Black Bands method (p-value=0.0001). There was no significant adjusted p-value between Control and Black Bands methods. Discussion: The Black Bands method score is surprisingly low. The marks seem to tell us that the method does not solve the problem and that the perception at the screen border is even worse than when no treatment is applied. We think that this could be explained by the use of a CRT screen with white surrounds for the evaluation. When applied to projected images in dark rooms (theaters), the black bands make the user fuse the black band edges with image edges of the same color and luminosity. Besides, users' comments have also highlighted the modification of the view volume by the Blacks Bands, one declaring "I feel like I'm looking at a 9/16 TV".

The SCVC results confirm that SCVC solves the D/FO conflict problem giving a better depth perception of the sphere in situations when it is partially occluded by the screen borders. Some users have complained of the "slicing" effect induced by the clipping. This can be disturbing depending on the experience the application designers want to give to the user. For applications centered on photorealism or visual attractiveness, the slicing effect might represent a drawback. Some improvements are possible to minimize this problem. For instance, sliced edges could be filled or progressively dissolved. Clipping along a plane orthogonal to the screen is another option, although it would make the method dependent on scene analysis to define the clipping plane. Future work is now necessary to improve this aspect of the method. Nevertheless, applications that do not focus on aesthetic aspects, such as in CAD software, could already benefit from SCVC directly.

CONCLUSION

Frame cancellation is a common problem we face in stereoscopic displays. Recent solutions investigated in the movie sector are not easily applicable to real-time rendering and the few methods designed to target VR still suffer from drawbacks and are not always applicable to every environment. We have proposed SCVC, a novel method that solves the problem in a different manner: it only renders the part of the viewing volume that is free of D/FO conflict. This approach does not rely on the analysis of the stereo disparity or the analysis of the scene geometry.

A subjective evaluation conducted with 22 participants has shown scores in favor of SCVC for various criteria. SCVC notably improved global appreciation and user's depth perception near the screen edges.

At a time when stereoscopic capable hardware is available from the mass consumer market, the D/FO conflict will become more noticeable. Thanks to its simplicity of implementation, SCVC could target a wide range of rendering software from VR applications to game engines and CAD softwares.

Future work concerns integration of SCVC with realistic rendering. Programmable graphic pipeline could be of help to refine clipped edge rendering though effects like fading or appropriate filling. An advanced evaluation has to be conducted, using a collection of static scenes in conjunction with subjective and quantitative evaluation methods for the eye strain parameter [START_REF] Kennedy | Simulator sickness questionnaire: an enhanced method for quantifying simulator sickness[END_REF]. The influence of surrounds in the Black Bands method is another point to clarify. An experimental campaign confronting different display setups (projector, monitor) and evaluation conditions (dark, bright rooms) should also be conducted.

Figure 1 .

 1 Figure 1. Top view of the left and right camera volumes. Light gray: stereo compatible volume. Dark gray: volume subject to disparity / frame occlusion conflict.

  : {jardouin, alecuyer, mmarchal, emarchand}@inria.fr parallaxes in areas where frame cancellation occurs. Lipton et al.

Figure 2 .

 2 Figure 2. Black bands. The part of the virtual sphere subject to frame cancellation is discarded by restricting the viewing volume with black bands.

Figure 3 .

 3 Figure 3. SCVC method: Perspective representation of left eye view volume and left clip plane of right eye view volume. This clip plane is used to clip polygons during the rendering of the left view.

Figure 4 .

 4 Figure 4. Stereoscopic images in the 3 experimental conditions:Black Bands (state of the art method), SCVC, and Control (no treatment). A reader comfortable with cross eye stereo can fuse left and right images to see the effects.

Figure 5 .

 5 Figure 5. Results for the subjective questionnaire for the three different techniques (1) SCVC (white), (2) Control (light grey) and (3) Black Bands (dark grey), with respect to a Likert-scale grading. The subjective criteria are (a) Relief Quality, (b) Relief Quality at Borders, (c) Aesthetic, (d) Eye Strain perceived and (e) Global Appreciation. Each boxplot is delimited by the quartile (25% and 75% without outliers) of the distribution of the condition over the individuals. The median is also represented for each technique.

Table 1 .

 1 Properties and limitations of existing methods for solving disparity/frame occlusion conflict.

		Black Bands	Border	Disparity
		[5][8]	stretching [3]	Map [6]
	Scene scale alteration	No	Yes (at borders)	Yes	Yes
	View Vol. aspect ratio alteration	Yes	No	No	No

IEEE Symposium on 3D User Interfaces 2011 19-20 March, Singapore 978-1-4577-0064-4/11/$26.00 ©2011 IEEE


Andrea Cherubini

Fabien Spindler

Franc ¸ois Chaumette

A Redundancy-Based Approach For Visual Navigation With Collision Avoidance

Keywords: Navigation systems, Visual Servoing, Autonomous driving

We propose an autonomous vehicle guidance framework which combines visual navigation with simultaneous obstacle avoidance. The method was originally designed in [1], but real outdoor experiments and major improvements have been added in this paper. Kinematic redundancy guarantees that obstacle avoidance and navigation are achieved concurrently. The two tasks are realized both in an obstacle-free and in a dangerous context, and the control law is smoothened in between. The experiments show that with our method, the vehicle can replay a taught visual path while avoiding collisions.

I. INTRODUCTION

A great amount of robotics research focuses on vehicle guidance, with the ultimate goal of automatically reproducing the tasks usually performed by human drivers [2 -6]. In many works, information from visual sensors is used for localization [7 -9] or navigation [START_REF] Bonin-Font | Visual navigation for mobile robots: a survey[END_REF]. In the case of autonomous navigation, an important task is obstacle avoidance, which consists of generating a collision-free trajectory to the goal [START_REF] Minguez | Motion planning and obstacle avoidance[END_REF]. If bypassing is impossible, the vehicle must decelerate to prevent collision [START_REF] Wada | A deceleration control method of automobile for collision avoidance based on driver's perceptual risk[END_REF]. A classical technique for avoidance is the potential field method [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF], which is often associated to a global path planner.

The framework presented in our work does not require a global model of the environment (e.g., based on geometric primitives). It enables execution of a sensor-based task, with simultaneous collision avoidance. We focus on following a visual path, represented by a database of ordered key images [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF]. The task is therefore defined in the image space, and not in the pose space, and it is divided into subtasks, each consisting of reaching the next key image in the database. This scheme, which is quite common in the robotics community [14 -17], has been rarely extended to take into account obstacles.

Obstacle avoidance has been integrated in navigation frameworks in [18 -22]. The authors of [START_REF] Ohya | Vision-based navigation by a mobile robot with obstacle avoidance using a single-camera vision and ultrasonic sensing[END_REF] use a model-based vision system with retroactive position correction. In [START_REF] Yan | Mobile robot indoor navigation using laser range finder and monocular vision[END_REF], a laser range finder and monocular vision enable navigation in an office environment. Simultaneous obstacle avoidance and path following is presented in [START_REF] Lapierre | Simultaneous path following and obstacle avoidance control of a unicycle-type robot[END_REF], where the geometry of the path (a curve on the ground) is perfectly known. The authors of [START_REF] Lamiraux | Sensor-based trajectory deformation: application to reactive navigation of nonholonomic robots[END_REF] deform the desired trajectory to avoid sensed obstacles. In practice, all these methods are based on the environment 3D A. Cherubini, F. Spindler and F. Chaumette are with INRIA Rennes -Bretagne Atlantique, IRISA, Campus de Beaulieu 35042, Rennes, France. {firstname.lastname}@inria.fr model, including, e.g. walls and doors. An exception is [START_REF] Folio | A redundancy-based scheme to perform safe vision-based tasks amidst obstacles[END_REF], where redundancy enables reactive obstacle avoidance, without requiring any 3D model.

Our scheme also exploits redundancy. A robot is redundant when it has more DOFs than those required for the primary task [START_REF] Chiaverini | Kinematically redundant manipulators[END_REF]; then, a secondary task can also be executed.

Here, we focus on this problem: a wheeled vehicle, equipped with an actuated pinhole camera and with a forward-looking range scanner, must follow a visual path represented by key images, without colliding with the ground obstacles. The camera detects the features required for navigating, while the scanner senses the obstacles (in contrast with other works, such as [START_REF] Kato | An obstacle detection method by fusion of radar and motion stereo[END_REF], only one sensor is used to detect the obstacles).

As in [START_REF] Folio | A redundancy-based scheme to perform safe vision-based tasks amidst obstacles[END_REF], we guarantee that obstacle avoidance has no effect on visual navigation. However, our controller is compact, and the transition between safe and dangerous contexts is operated only for the secondary task, while in [START_REF] Folio | A redundancy-based scheme to perform safe vision-based tasks amidst obstacles[END_REF], three controllers are needed, and the transitions are more complex.

Although the approach was designed in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF], the contributions of this paper are various. Here, we experimentally validate the scheme, and to our knowledge, this is the first time that obstacle avoidance and outdoor visual navigation are merged directly at the control level. Many changes were necessary in order to adapt the system in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF] to the real world: in particular, the linear velocity, which was constant in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF], had to be varied to improve visual tracking and security (it must diminish in dangerous situations). As a consequence, the task dimension and context definition also had to be modified. Under these real world constraints, we have designed a compact general controller, which provides visual navigation, obstacle circumnavigation, and collision avoidance by deceleration.

II. PROBLEM CHARACTERISTICS

The reader is referred to Fig. 1 for the definitions below. We define the robot frame F R (R, X , Y , Z ) (R is the robot center of rotation), image frame F I (O, x, y) (O is the image center), and camera frame F C (C, X, Y, Z) (C is the optical center). The robot control inputs are:

u = [v ω φ]
These are, respectively, the linear and angular velocities of the vehicle, and the camera pan angular velocity. We use the normalized perspective camera model:

x = X Z , y = Y Z We assume that |ϕ| ≤ π
2 , that C belongs to the camera pan rotation axis, and that the path can be tracked with continuous v (t) > 0. This ensures safety, since only obstacles in front of the robot can be detected by our range scanner. The distance between R and C is denoted by δ ≥ 0.

ω v 2 columns X Y δ Z X' Z' C R x y O Y' ϕ ϕ . X' Z' c 1 c 2 c 3 f c,2 f c,1 f R Y' f c,3 α (a) (b) (c)
The visual path that the robot must follow is represented as a database of ordered key images, such that each neighboring pair contains some common static visual features. First, the vehicle is manually driven along a taught path, with the camera pointing forward (ϕ = 0), and all the images are saved. Harris points [START_REF] Harris | A combined corner and edge detector[END_REF] are detected in the first image, and a modified Kanade-Lucas-Tomasi (KLT) algorithm [START_REF] Shi | Good features to track[END_REF] tracks the features in successive images, to generate the database of N key images I 1 , . . . , I N (Fig. 2) that represents the path. Then, during autonomous navigation, the current image, noted I, is compared with the database, to drive the vehicle velocity. SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] are used to initialize the KLT algorithm, which tracks the features while the taught path is replayed. Visual navigation is divided into N subtasks, each consisting of driving the current image I to the next key image Î. To check whether Î has been reached, we perform a coarse threeview pose calculation between the previous, current and next key images. As soon as Î is reached, a topological transition is made, and the tracker is reinitialized: the next image in the set becomes the desired one, and so on, until I N is reached. More details on these algorithms are in [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF].

Along with the visual path following problem, which we have tackled in [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF] and in [START_REF] Cherubini | Comparing appearance-based controllers for nonholonomic navigation from a visual memory[END_REF], here we consider obstacles which are present on the path, but not in the database, and sensed by the range scanner. For obstacle modeling, as in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF], an occupancy grid, shown in Fig. 1(c), is used: it is linked to F R , with cell sides parallel to the X and Z axes. Its forward and lateral extensions are smaller than the scanner radial range, to ignore obstacles that are too far away to jeopardize the robot. The grid is built from the latest 2K + 1 scans. For each cell centered at c = [X Z ] , we define the 2K + 1 occupancies r at the j-th oldest iteration as:

r j (c) = {0, 1}, j = 0, . . . , 2K + 1
We set r j = 1 if an obstacle has been sensed in c at the j-th iteration prior to the current one, and 0 otherwise. Then, we associate to each cell a coefficient µ (c), obtained by linear combination of the occupancies, weighed with a normalized Gaussian filter that smoothens the cell effect over time:

µ (c) = 2K+1 j=0 e -(j-K) 2 /K √ Kπ r j (c)
The filter maximum weight is set at the K-th latest scan, to avoid the control inputs overshoot at a new obstacle detection (an issue which existed in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF]). If the robot velocity is negligible with respect to the scanner acquisition frequency, and K is reasonably small, the effect of motion on the occupancies can be ignored, and the above model is consistent with the current robot position. Later in this paper, we will explain how the occupancy grid is utilized in our controller, and we will show that the above assumptions are appropriate in our setup.

III. REDUNDANCY FRAMEWORK FOR 2 TASKS

We hereby recall the redundancy-based controller used in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF], and originally introduced in [START_REF] Hanafusa | Analysis and control of articulated robot arms with redundancy[END_REF]]. We name s 1 ∈ IR k the primary task vector, and u ∈ IR m the control inputs. Redundancy exists when m > k, and enables handling a secondary task, s 2 ∈ IR m-k . The tasks dynamics are related to the control inputs by:

ṡi = J i u, i = 1, 2 (1)
where J 1 and J 2 are the task jacobians, respectively of size k × m and (m -k) × m. We assume that both have full rank.

With the Projected Gradient method [START_REF] Chiaverini | Kinematically redundant manipulators[END_REF], the solution of (1), for tracking the primary task is:

u = J + 1 ṡ * 1 + P 1 h (2)
In the above equation:

• J + 1 = J 1 J 1 J 1 -1
is the m × k Moore-Penrose pseudoinverse of J 1 , i.e., a particular solution of:

J 1 J + 1 = I; • ṡ * 1 ∈ IR k is the required primary task error evolution; • h ∈ IR m is an arbitrary control input; • P 1 = I -J +
1 J 1 projects h on the kernel of J 1 ; hence, P 1 h has no effect on the primary task. Vector h can be used to apply a command that will carry out at best the secondary task s 2 , without disturbing s 1 .

Introducing ( 2) in (1) (with i = 2), we obtain:

ṡ2 = J 2 J + 1 ṡ * 1 + J 2 P 1 h In [29], h is derived from this equation to track ṡ * 2 : h = (J 2 P 1 ) + ṡ * 2 -J 2 J + 1 ṡ * 1 (3)
Plugging into (2), we obtain:

u = J + 1 ṡ * 1 + P 1 (J 2 P 1 ) + ṡ * 2 -J 2 J + 1 ṡ * 1
The term J 2 P 1 gives the available range for s * 2 to be performed without affecting s 1 , while ṡ * 2 -J 2 J + 1 ṡ * 1 is the secondary task function, without the part J 2 J + 1 ṡ * 1 accomplished by the first task. Since P 1 is Hermitian and idempotent (it is a projection operator), the above equation becomes:

u = J + 1 ṡ * 1 + h (4)
with h defined in (3). The desired evolution of the task errors can be written:

ṡ * i = ṡi -λ i (s i -ŝi ) , i = 1, 2 (5)
with ŝi and ṡi indicating the desired values of the i-th task, and of its first derivative, and λ i > 0 the associated gain. Controller (4) has the following properties.

• It guarantees convergence of the primary task. Replacing (4) in (1) yields: [START_REF] Nunes | Introducing Perception, Planning, and Navigation for Intelligent Vehicles[END_REF], this is equivalent to the linear system:

ṡ1 = ṡ * 1 Considering (
ṡ1 -ṡ1 = -λ 1 (s 1 -ŝ1 )
for which, as desired, ŝ1 , ṡ1 is an exponentially stable equilibrium, since λ 1 > 0.

• The secondary task s 2 has no effect on the primary task, since h is projected onto the null space of J 1 . • The secondary task s 2 is realized at best, under the constraint that it does not affect the primary task. In this work, the desired specifications are: 1) orienting the camera to maximize the similarity of I with the next key image Î in the database, 2) making the vehicle progress forward along the path, 3) avoiding collision with the obstacles, while remaining near the 3D taught path. For our system, m = 3. We will fulfill a primary task of dimension k = 1 (orienting the camera), and use the 2 remaining degrees of freedom for a secondary task s 2 ∈ IR 2 that realizes the two other specifications. We discern two contexts (safe and dangerous). To smoothen transitions, we design an obstacle activation function:

H : C → [0, 1]
where the context C indicates the danger represented by detected obstacles. The definition of H will be given later.

• In the safe context (H = 0), since no obstacles are present, it is not necessary to deform the taught path. We use ω for the primary task (i.e., to orient the camera for image tracking). Then, we can set ϕ = 0, as was done during teaching. Moreover, the linear velocity v must be reduced in the presence of sharp turns, to ease the visual tracking of quickly moving features in the image. Hence, we formulate the secondary task as:

v = v s φ = -λ 2 ϕ ∀ (s 1 , ṡ1 ) ∈ IR × IR (6)
The function v s , which defines the linear velocity in the safe context, will be given later. Condition (6) will be guaranteed by control input h s , defined just below. • In the dangerous context (H > 0), obstacles are present.

Sometimes (H < 1), these can be circumnavigated, while tracking the visual features. In this case, the robot should reduce its velocity, and avoid collision by orienting its heading to a desired value α. The value of α is related to the obstacles position (see Fig. 1(c)), and defined later in the paper. The secondary task is:

v < v s ω = λ 2 α ∀ (s 1 , ṡ1 ) ∈ IR × IR (7)
This condition provokes a deformation of the taught 3D path. Correspondingly, the camera pan angle must be actuated to maintain visibility of the database features (i.e., the primary task). If the obstacles are too near to be circumnavigated (H = 1), the vehicle should stop:

v = 0 ∀ (s 1 , ṡ1 ) ∈ IR × IR (8)
Conditions [START_REF] Yamaguchi | Vehicle Ego-Motion Estimation and Moving Object Detection using a Monocular Camera[END_REF], and (8) will be guaranteed by control input h d , defined below. A smooth transition between the inputs associated to the two contexts can be achieved by setting, in (4):

h = Hh d + (1 -H) h s to obtain:    u = J + 1 ṡ * 1 + Hh d + (1 -H) h s h d = (J d P 1 ) + ṡ * d -J d J + 1 ṡ * 1 h s = (J s P 1 ) + ṡ * s -J s J + 1 ṡ * 1 (9)
In the above equation:

• ṡ * d,s are the desired secondary tasks dynamics, in the dangerous and safe context; recalling [START_REF] Nunes | Introducing Perception, Planning, and Navigation for Intelligent Vehicles[END_REF], they are:

ṡ * d = ṡd -λ 2 (s d -ŝd ) ṡ * s = ṡs -λ 2 (s s -ŝs ) (10)
• J d,s are the corresponding jacobian matrices. In Sect. V, controller (9) will be instantiated for the problem of visual navigation with obstacle avoidance.

IV. SYSTEM MODELING

In this section, we define precisely the variables that have been introduced above. In particular, we will show how the linear velocity v s for maximal visibility is designed, and how we use the occupancy grid to derive the robot heading for avoidance α, and the activation function H for varying between the safe and dangerous contexts.

A. Linear Velocity For Maximal Visibility

As we mentioned above, features can be lost in the presence of sharp turns. Hence, we relate the vehicle linear velocity v to the weighted difference between the abscissa of the centroids in the current image (x), and in the next (x), and second next ( x) key images 1 :

v s = V 2   1 + tanh   π - 2x + x -3x γ     (11)
This function has an upper bound V > 0, and smoothly decreases to 0, as the abscissa difference grows. Its inflection point is determined by positive parameter γ.

B. Modeling The Obstacles

Obstacle avoidance is derived by using vortex potential fields [START_REF] De Luca | Local Incremental Planning for Nonholonomic Mobile Robots[END_REF]. For each cell c, we define the potential:

U c = µ (c) c
where c is the distance2 of the cell from R. In practice, for two occupied cells with equal µ (c) = 0, the nearest one will yield the highest potential. We define the vortex field for each cell simply as the rotor of U c :

f c = f c,X f c,Z =     ± ∂U ∂Z ∓ ∂U ∂X     = µ (c)      ∓ Z c 3 ± X c 3     
The signs of f c,X and f c,Z depend on the cell abscissa: positive (negative) X will induce a clockwise (counterclockwise) vortex, so that the field always points forward. The fields f c,i generated by all the n cells c i are then superimposed to obtain the total field:

f = n i=1 f c,i
The orientation α ∈ -π 2 , π 2 of this field (see Fig. 1) is:

α = 0 if f = 0 -ATAN2 (f X , f Z ) otherwise
As in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF] and [START_REF] De Luca | Local Incremental Planning for Nonholonomic Mobile Robots[END_REF], this is the desired heading for obstacle circumnavigation in dangerous situations (see [START_REF] Yamaguchi | Vehicle Ego-Motion Estimation and Moving Object Detection using a Monocular Camera[END_REF]). However, α is not indicative of the chances of successful circumnavigation. For this, we use the field norm:

|f | = f 2 X + f 2 Z
which is a good metric for evaluating the obstacle distance, and reducing v accordingly, in order to fulfill [START_REF] Yamaguchi | Vehicle Ego-Motion Estimation and Moving Object Detection using a Monocular Camera[END_REF] and [START_REF] Zhou | Autonomous Visual Self-localization in Completely Unknown Environment using Evolving Fuzzy Rule-based Classifier[END_REF]. In summary, to assess the context danger, we consider both α and |f |, and using two empirically tuned thresholds ρ and such that 0 < ρ < , we design the activation function as:

H =    κ |α| if |f | <= ρ κ |α| + (1 -κ |α|) |f |-ρ -ρ if |f | ∈ ]ρ, [ 1 if |f | >=
Note that H = 0 if no obstacle is detected (since both |f | and α are null in that case), and it is bounded by 1. For small |f |, H is determined only by α: the obstacles are 'far enough' to be circumnavigated using [START_REF] Yamaguchi | Vehicle Ego-Motion Estimation and Moving Object Detection using a Monocular Camera[END_REF], and parameter κ ∈ 0, 2 π weighs the danger provoked by the field orientation3 . On the other hand, for large |f | ≥ , the obstacles are 'too near': H = 1 and the robot stops. We use a linear function to guarantee continuity in between. Parameters ρ and are tuned to determine the three intervals. For example, small values of make the approach more conservative, since the robot will stop in the presence of farther obstacles.

V. CONTROL SCHEME

A. Primary Task: Camera Orientation

We do not take directly into account occlusions, or feature position, and assume that the visible features are homogeneously distributed in the environment. Then, the task of maximizing the similarity between current image I, and next key image Î, can be achieved with only one visual feature: the abscissa x of the centroid of the points matched on I and Î [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF]. Hence, for s 1 , we use:

s 1 = x, ŝ1 = x, ṡ1 = 0
which, replaced in (5), yields:

ṡ * 1 = λ 1 (x -x)
Assuming static features, the corresponding primary task Jacobian is:

J 1 = [j v j ω j φ] , (12)
where an approximation of the components is (see [START_REF] Cherubini | Comparing appearance-based controllers for nonholonomic navigation from a visual memory[END_REF]):

j v = -sin ϕ+x cos ϕ Z j ω = δ(cos ϕ+x sin ϕ) Z + 1 + x 2 j φ = 1 + x 2 (13)
As in [START_REF] Cherubini | Comparing appearance-based controllers for nonholonomic navigation from a visual memory[END_REF], to avoid depth estimation, which can be unreliable, we set the depth to a fixed value Z.

The Moore-Penrose pseudoinverse of J 1 is:

J + 1 = [j v j ω j φ] j 2 v + j 2 ω + j 2 φ
Since j φ = 0, ∀x ∈ IR (see ( 13)), J + 1 is full rank. The projecting operator P 1 can also be derived:

P 1 = 1 j 2 v + j 2 ω + j 2 φ   j 2 ω + j 2 φ -j v j ω -j v j φ -j v j ω j 2 v + j 2 φ -j ω j φ -j v j φ -j ω j φ j 2 v + j 2 ω   B.
Safe Secondary Task: Taught Path Following

In the safe context, since path deformation is not necessary, the robot must follow at best the 3D taught path. Thus, as it was during teaching, the camera pan should point forward (i.e, the pan angle should be set to 0, with null angular speed at the equilibrium). To maximize visibility, the linear velocity should be reduced when the path curvature is large. These two requirements can be formulated by using:

s s = t 0 v(t)dt ϕ , ŝs = t 0 v(t)dt 0 , ṡs = v s 0
which, replaced in [START_REF] Bonin-Font | Visual navigation for mobile robots: a survey[END_REF], yields:

ṡ * s = v s -λ 2 ϕ
Since deriving s s yields [v φ] , the corresponding secondary task Jacobian is:

J s = 1 0 0 0 0 1
and we obtain:

(J s P 1 ) + =   1 0 -jv jω - j φ jω 0 1   , J s J 1 + = [j v j φ] j 2 v + j 2 ω + j 2 φ

C. Secondary Task In The Dangerous Context: Safety

In the dangerous context, the secondary task consists of aligning the robot with f (i.e., shifting its heading by α, with null angular speed at the equilibrium), and reducing the linear velocity, if the obstacles are 'too' near. Denoting with θ the current robot orientation, this is done by using:

s d = t 0 v(t)dt θ , ŝd = t 0 v(t)dt θ + α , ṡd = 0 0
which, replaced in [START_REF] Bonin-Font | Visual navigation for mobile robots: a survey[END_REF], yields:

ṡ * d = 0 λ 2 α
Since deriving s d yields [v ω] , the corresponding secondary task Jacobian is:

J d = 1 0 0 0 1 0
and we obtain:

(J d P 1 ) + =   1 0 0 1 -jv j φ -jω j φ   , J d J 1 + = [j v j ω ] j 2 v + j 2 ω + j 2 φ

D. Complete Control Design

Let us now use the variables defined above, to instantiate our controller [START_REF] Schleicher | Real-Time Hierarchical Outdoor SLAM Based on Stereovision and GPS Fusion[END_REF] for visual navigation:

     v = (1-H) v s ω = (1-H) λ1(x-x)-jvvs+λ2j φϕ jω + Hλ 2 α φ = H λ1(x-x)-λ2jωα j φ -(1-H) λ 2 ϕ (14)
This control law has the following nice properties. 1) In the safe context (H = 0), [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF] becomes:

   v = v s ω = λ1(x-x)-jvvs+λ2j φϕ jω φ = -λ 2 ϕ (15)
The image error is controlled only by ω, as in [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF] and [START_REF] Cherubini | Comparing appearance-based controllers for nonholonomic navigation from a visual memory[END_REF], where obstacles were not considered. The secondary task of maximal visibility (6), instead, is achieved by inputs v and φ: the linear velocity is reduced to improve tracking according to [START_REF] Minguez | Motion planning and obstacle avoidance[END_REF], while the camera is driven forward, to ϕ = 0. 2) In the dangerous context (H ≈ 1), a good approximation of ( 14) is:

   v = (1-H) v s ω = λ 2 α φ = λ1(x-x)-λ2jωα j φ
In this case, the primary task is executed by φ, while the secondary task of safety (7-8) is controlled by the 2 other degrees of freedom: the linear velocity is reduced (and even zeroed, for H = 1), while the angular velocity aligns the robot with f . The camera velocity compensates the robot rotation, to keep the features in view. Note that, for large Z, and small image error, φ ≈ -ω (since, from (13), j ω ≈ j φ), which is an expected behavior. 3) Since j φ = 0, ∀x ∈ IR, for ( 14) to be well defined when the centroid is visible, it is sufficient that j ω = 0, which is guaranteed, since |ϕ| ≤ π 2 , by choosing Z > δ 2 , as we have proved in [START_REF] Cherubini | A redundancy-based approach for obstacle avoidance in mobile robot navigation[END_REF]. Moreover, in [START_REF] Cherubini | Comparing appearance-based controllers for nonholonomic navigation from a visual memory[END_REF], we have shown that overestimating Z with respect to its real value, is more effective than underestimating it, in terms of navigation performance.

VI. EXPERIMENTAL RESULTS

Experiments have been carried out on a CyCab vehicle, set in car-like mode (i.e., using only the front wheels for steering). The robot is equipped with a coarsely calibrated 70 • field of view, B&W camera mounted on a TRACLabs Biclops Pan/Tilt head (the tilt angle is null, to keep the optical axis parallel to the ground), and with a 4-layer, 110 • scanning angle, laser SICK LD-MRS. The offset between R and C is δ = 0.7 m, and we set Z = 15 m, to prevent singularities in [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF]. We build the grid by projecting the laser readings from the 4 layers on the ground, and limiting its size to 1.5 m on each side, and 5 m in front. The linear velocity is designed with V = 0.4 ms -1 and γ = 225. The velocity has been limited for Control scheme ( 14) has been validated in the three experiments, which are shown in Fig. 3, as well as in the video at: www.irisa.fr/lagadic/demo/demo-cycab-vis-navigation/obstAv.avi.

In each case, after having manually driven CyCab to acquire the image database, two setups (safe and dangerous) are tested. First, no obstacle is present: since H is constantly null, ( 15) is used, with fixed forward-looking camera (ϕ = 0). Then, some obstacles (including pedestrians) are present, near and on the taught path, and the robot must deal with them, during navigation; in addition to endangering the robot, the obstacles may occlude the features. The replayed paths, estimated from odometry and snapshots, are outlined on the left in Fig. 3, both in the safe (yellow) and dangerous (red) setup. Since the focus here is on obstacle avoidance, and accuracy of obstaclefree navigation has been proved in [START_REF] Šegvić | A mapping and localization framework for scalable appearance-based navigation[END_REF], the taught path is not drawn. Giving a general interpretation of the results is hard, since many factors intervene (e.g., obstacles and visual features positions). Nevertheless, in all the experiments, the robot follows the path without colliding, and in spite of occlusions (although a minimal number of visual features is obviously required). Although some portions of the replayed 3D path are far from the taught one, these motions are indispensable to avoid collisions. In the following, we detail the experiments.

The first path (used in experiment 1) is 60 m long, and composed of N = 34 key images. Three obstacles are on the path, and the robot is able to overtake them all (the first and third on the left, the second on the right), and reach the last key image. For the dangerous setup, snapshots are shown on top of Fig. 3, and v, ω, φ and ϕ are plotted 4 in Fig. 4. The iterations, with H > 0 are highlighted in yellow. CyCab is initially near a wall parallel to the Z axis, which is too far to be considered in the grid. This shows the utility of ignoring lateral data, which would have made the vehicle curve farther from the path. The first obstacle is detected at iteration 60: the vector field f generates a positive rotation (green in Fig. 4), compensated by the camera pan, and v is reduced. The obstacle is overtaken while maintaining feature visibility. Then, since the path is free, the pan angle (blue) is reset to 0 , until the second obstacle detection, which triggers a negative ω, and positive φ. Afterwards, H is activated again by the third obstacle, which is overtaken on the left (iteration 300), while decelerating. The activation function is canceled at iteration 360, and the variables are then driven by [START_REF] Argyros | Robot homing by exploiting panoramic vision[END_REF]. The average vehicle velocity v, is slightly reduced, from 0.39 ms -1 in the safe setup, to 0.35 in the presence of obstacles. The image error with respect to the visual database, averaged over the In experiment 2, a gray car is parked on the path, and a barrier blocks the road halfway through. Snapshots of the experiment are shown in the center of Fig. 3, and the velocities are plotted in Fig. 5. The car is overtaken on the left at iterations 120-190, while the robot slows down (black curve). Then, as soon as the street is free again, the robot accelerates and returns on the path, while the camera is reset forward. The barrier is more difficult to deal with. In fact, when detected, it is centered on the Z axis and orthogonal to it (see grids on the right of Fig. 3); this induces α = 0 and drives the robot towards the barrier. However, as the CyCab approaches the barrier, the norm of vector field f increases, and eventually becomes greater than , to make H = 1 and stop the robot. Note that when there is no obstacle, v ≈ V , because, in contrast with experiment 1, the taught path here is straight, leading to v s ≈ V , from [START_REF] Minguez | Motion planning and obstacle avoidance[END_REF]. The value of v, averaged over the path diminishes, from 0.39 ms -1 in the safe setup, to 0.34 in the dangerous one. This time, the average image error does not vary in the two setups (13 pixels in both cases).

In experiment 3, although the gray car and barrier are not present, three persons are standing on the path. On Fig. 3 (bottom), we show some snapshots of the experiment, while the velocities are plotted in Fig. 6. From iteration 50 to 120, the activation function is triggered by the detection of the pedestrians. This generates a counterclockwise angular velocity (the persons are overtaken on the left), and a slight deceleration. Afterwards, since the street is free again, the robot accelerates and returns on the path, which this time is completed up to the last key image, since the barrier has been removed. Just like in experiment 2, when there is no obstacle, v ≈ V , since the path is straight. The average linear velocity (v = 0.38 ms -1 ), is almost the same as in the safe setup (0.39), and so is the average image error (12 pixels).

VII. CONCLUSIONS

We have designed and implemented a framework with simultaneous obstacle avoidance and vision-based navigation for an outdoor vehicle. It merges techniques from redundancy, potential fields, and visual servoing, and guarantees visual navigation, obstacle bypassing, and collision avoidance by deceleration. The method is validated in outdoor experiments, with real obstacles, such as parked cars and pedestrians. In the future, we plan to take into account moving obstacles, as well as visual occlusions provoked by the obstacles. We also plan to test other obstacle modeling techniques, such as the 'tentacles' presented in [START_REF] Hundelshausen | Driving with tentacles -Integral structures of sensing and motion[END_REF].

Fig. 1 .

 1 Fig. 1. Top view of the robot (orange), equipped with an actuated camera (blue). (a) Reference frames. (b) Obstacle-induced vortex fields, and control variables (v, ω, φ). (c) Occupancy grid and potential field f construction.

2 .

 2 Fig.

Fig. 3 .

 3 Fig. 3. Top to bottom: experiments 1 to 3. Left: reconstruction of the replayed path with (red) and without (yellow) obstacles. Right: snapshots (above) and grids (below) in the presence of obstacles. The red vectors show the orientation of f .

5 Fig. 4 .

 54 Fig.[START_REF] Zhang | Driving skill characterization: A feasibility study[END_REF]. Relevant variables in experiment 1: v (black, in ms -1 ), ω (green, in rad s -1 ), ϕ (blue, in rad) and φ (red, in rad s -1 ). The iterations with non-null H are highlighted in yellow.

Fig. 5 .

 5 Fig.5. Relevant variables in experiment 2: v (black, in ms -1 ), ω (green, in rad s -1 ), ϕ (blue, in rad) and φ (red, in rad s -1 ). The iterations with non-null H are highlighted in yellow.

Fig. 6 .

 6 Fig.6. Relevant variables in experiment 3: v (black, in ms -1 ), ω (green, in rad s -1 ), ϕ (blue, in rad) and φ (red, in rad s -1 ). The iterations with non-null H are highlighted in yellow.

978-1-4244-9974-8/11/$26.00 ©2011 IEEE

When the next image is the final one, we use x = x, since the second next image is undefined.

Designing the grid without the cell at R = [0 0] (where obstacles are not detectable by the range scanner), guarantees that Uc is non-singular.

To guarantee H ≤ 1, parameter κ must be chosen smaller than 2 π .

The smooth trend of v at the beginning and end of the 3 experiments is due to the acceleration saturation that is carried out at the control low-level.

ACKNOWLEDGMENTS

This work was funded by the ANR CityVIP project.