Bertrand Delabarre

Eric Marchand

Visual Servoing using the Sum of Conditional Variance

In this paper we propose a new way to achieve direct visual servoing. The novelty is the use of the sum of conditional variance to realize the optimization process of a positioning task. This measure, which has previously been used successfully in the case of visual tracking, has been shown to be invariant to non-linear illumination variations and inexpensive to compute. Compared to other direct approaches of visual servoing, it is a good compromise between techniques using the illumination of pixels which are computationally inexpensive but non robust to illumination variations and other approaches using the mutual information which are more complicated to compute but offer more robustness towards the variations of the scene. This method results in a direct visual servoing task easy and fast to compute and robust towards non-linear illumination variations. This paper describes a visual servoing task based on the sum of conditional variance performed using a Levenberg-Marquardt optimization process. The results are then demonstrated through experimental validations and compared to both photometric-based and entropy-based techniques.

I. INTRODUCTION

Visual servoing uses the information provided by a vision sensor to control the movements of a dynamic system [START_REF] Hutchinson | A tutorial on visual servo control[END_REF], [START_REF] Chaumette | Visual servo control, Part I: Basic approaches[END_REF], [START_REF] Chesi | Visual servoing via advanced numerical methods[END_REF]. This approach requires to extract and track visual information (usually geometric features) from the image in order to design the control law. This difficult tracking process is one of the bottlenecks in the development of visual servoing techniques.

Recent works have tried to circumvent these problems by using directly the information provided by the entire image [START_REF] Nayar | Subspace methods for robot vision[END_REF], [START_REF] Deguchi | A direct interpretation of dynamic images with camera and object motions for vision guided robot control[END_REF], [START_REF] Kallem | Kernel-based visual servoing[END_REF], [START_REF] Collewet | Photometric visual servoing[END_REF], [START_REF] Dame | Mutual information-based visual servoing[END_REF]. Features are no longer extracted from the image. Those works have began with [START_REF] Nayar | Subspace methods for robot vision[END_REF] and [START_REF] Deguchi | A direct interpretation of dynamic images with camera and object motions for vision guided robot control[END_REF], where the images were reduced to eigenspaces. Later works have used directly the whole images. In [START_REF] Collewet | Photometric visual servoing[END_REF], a control law was proposed that minimizes the error between the current image and the desired one. In that case the vector of visual feature in nothing but the image itself and the error to be regulated is the sum of squared differences (the SSD). This approach features many advantages: it does not require any matching or tracking process. Furthermore since the image measurements are nothing but the pixel intensity, there are no error in the feature extraction process leading to a very precise realization of the task.

Nevertheless, considering image intensities is quite sensitive to modification of the environment [START_REF] Collewet | Photometric visual servoing[END_REF] and more robust registration function have to be considered. [START_REF] Collewet | Modeling complex luminance variations for target tracking[END_REF] use a full reflection model to tackle complex illumination changes thus creating the possibility to take into account some non-global illumination changes (occurrence of specularities, lighting B. Delabarre an E. Marchand are with Université de Rennes 1, IRISA, INRIA, Lagadic team, Rennes, France {bertrand.delabarre,marchand}@irisa.fr direction non constant wrt. the surface, etc). But this method is limited since the range of application only applies to illumination conditions that can be represented with the considered model. A more recent approach also considered the mutual information [START_REF] Shannon | A mathematical theory of communication[END_REF] as the similarity measure between desired and current images [START_REF] Dame | Mutual information-based visual servoing[END_REF]. This information theoretic method allows to servo the camera in order to maximize the quantity of information shared by the current and desired image (that is the mutual information which is build by a measure of image entropy [START_REF] Shannon | A mathematical theory of communication[END_REF]). The approach is therefore well suited for a large range of variations such as occlusions, specularities and even different modality images. A drawback of this method is that it is quite complex to compute and therefore computationally expensive.

In this paper we propose a compromise between this two branches. Our method is based on the sum of conditional variance, a measure using the probability distribution functions of the luminance in the image to adapt a template. When considering direct visual servoing method, the choice of the similarity function is fundamental. Between the simplest alignment function that is the sum of squared differences [START_REF] Collewet | Photometric visual servoing[END_REF] and the mutual information [START_REF] Dame | Mutual information-based visual servoing[END_REF], one can consider other metric such as the Zero-mean Normalized Cross Correlation (or ZNCC [START_REF] Irani | Robust multi-sensor image alignment[END_REF]) which has proved to be very robust to linear brightness variation [START_REF] Stephano | ZNCC-based template matching using bounded partial correlation[END_REF] thanks to the normalization embodied into the ZNCC. In this paper, to be able to handle non-linear brightness variation and to have a low computational complexity, we propose to consider, as a similarity function, the sum of conditional variance (or SCV). With respect to the simple SSD function, SCV allows to dynamically adapt the reference image to the illumination conditions of the current image acquired by the camera. The reference image is replaced by an expected image computed using a probabilistic expectation operator (that take into account illumination condition in both current and learned desired image). Let us note that this approach has proved recently to be very efficient in a tracking context as demonstrated in [START_REF] Richa | Visual tracking using the sum of conditional variance[END_REF].

Dynamically adapting the desired image makes the approach able to tackle brutal illumination variations. Furthermore, this approach is computationally very efficient since it is still based on a simple difference between pixels. It is also easy and fast to compute which makes it a good solution for visual servoing tasks involving illumination variations of the scene.

In this paper we will first have a quick reminder of the direct visual servoing methods before describing the new method based on the sum of conditional variance. Several experiments are then exposed, showing the advantages and limitations of the approach.

II. DIRECT VISUAL SERVOING

A. Positioning Task

The aim of a positioning task is to reach a desired pose of the camera r * , starting from an arbitrary initial pose. To achieve that goal, one needs to define a cost function that reflects, in the image space, this error. Most of the time this cost function f is an error measure which needs to be minimized. Considering the actual pose of the camera r the problem can therefore be written as an optimization process:

r = arg min r f (r, r * ) (1)
where r, the pose reached after the optimization process (servoing process), is the closest possible to r * (optimally r = r * ). For example, considering a set of geometrical features s, the task will typically have to minimize the difference between s(r) and the desired configuration s* which leads to:

r = arg min r (s(r) -s * ). (2)
This visual servoing task is achieved by iteratively applying a velocity to the camera. This requires the knowledge of the interaction matrix L s of s(r) that links the variation of ṡ to the camera velocity and which is defined as:

ṡ(r) = L s v (3)
where v is the camera velocity. This equation leads to the expression of the velocity that needs to be applied to the robot. The control law is classically given by:

v = -λL + s (s(r) -s * ) (4)
where λ is a positive scalar.

B. Photometric visual servoing

In the case of direct visual servoing, the feature s becomes the image itself (s(r) = I(r)). This means that the optimization process becomes [START_REF] Collewet | Photometric visual servoing[END_REF]:

r = arg min r (I(r) -I * ) (5)
where I(r) and I * are respectively the image seen at the position r and the template image (both of N pixels). The control law is inspired by the Levenberg-Marquardt (LM) optimization approach. It is given by:

v = -λ(H I + µ diag(H I )) -1 L I (I(r) -I * ) (6)
where λ and µ are positive scalars where H I = L I T L I and L I is the interaction matrix which can be expressed as:

L I = -∇I T L x (7)
and L x is the interaction matrix of a point (see details in [START_REF] Collewet | Photometric visual servoing[END_REF]).

III. VISUAL SERVOING USING THE SUM OF CONDITIONAL VARIANCE A. Sum of Conditional Variance

The works of [START_REF] Collewet | Photometric visual servoing[END_REF] used the sum of squared differences to perform direct visual servoing. The main drawback of this method is that it is based on the hypothesis that the luminance of a point does not vary with time:

I(x + dx, t + dt) = I(x, t) (8)
where x represents the pixel coordinates and dx the motion underwent by the image during the laps of time dt. When performing a visual servoing task, this hypothesis is often violated and, as the light changes in the scene, the task can quickly fail. This is the reason why this paper describes a visual servoing process using the Sum of Conditional Variance (SCV), a measure which was used in [START_REF] Richa | Visual tracking using the sum of conditional variance[END_REF] to track planar object using a KLT like approach with very good results in illumination-varying conditions. As in our case, this measure was used in [START_REF] Richa | Visual tracking using the sum of conditional variance[END_REF] because it no longer relies a simple difference between current and a reference image (or template image). Indeed, the template is dynamically adapted to the illumination conditions of the current image seen at each new iteration. To adapt the template, an expected image Î is defined as:

Î(x) = E(I(x) | I * (x)) (9)
where E is an expectation operator and x a pixel in the image. With this expected template computed, a good correlation measure is given by:

SCV = x (I(x) -Î(x)). (10)
The expected image Î is computed from the joint probability distribution between I and I * . Those probabilities are computed from the empirical analysis of I and I * . As they both have the same dynamic d, which usually is 256, for each couple of grey levels i in I and j in I * it is possible to compute:

P II * (i, j) = P (I(x) = i , I * (x) = j ) (11) = 1 N x φ(I(x) -i )φ(I * (x) -j ) (12)
where φ(a) equals 1 if a=0, 0 otherwise and P II * represents the probability that a pixel x takes the value i in I and j in I * . From this joint probability distribution, the probability distributions of I * can easily be found. For example the probability distribution for the apparition of a grey level j in I * is given by:

P I * (j) = i P II * (i, j). (13)
From this probability distribution functions the computation of the expected grey levels in Î becomes, for each grey level j in I * :

Î(j ) = i i P II * (i , j ) P I * (j ) . ( 14
)

B. Analysis of the SCV cost function

In order to assess the suitability of the sum of conditional variance in the case of illumination changes, a comparison of various similarity functions was realized. The comparison between two images (a reference image and a current image) follows the following pattern. On the images, a patch of 100x100 pixels is selected. The patch is extracted from the reference image, creating a reference template. In the current image, patches are extracted by moving a 100x100 window, starting from a translation (tx,ty) equal to (-10,-10) pixels with relation to the position of the template and finishing with (tx,ty) equal to (10,10) pixels. The cost function is then computed between each patch extracted and the template, leading to the shape of the cost function.

When computing the cost functions, histogram binning was used (see more details in section IV-A). The mutual information was computed with 8 bins as in [START_REF] Dame | Mutual information-based visual servoing[END_REF] and the sum of conditional variance with 64 bins. A first comparison was made with both the current and reference image being the same, creating a baseline (see fig 1). This shows the shapes of the functions in the ideal case were the conditions do not vary during the visual servoing. The three cost functions possess a marked optimum when (tx,ty) equals to (0,0) pixels. They also present a smooth shape and no local extrema which make them well suited for optimization processes in nominal conditions. With that baseline established, a second comparison was made. For this comparison, the current image was not the same as the reference but had undergone a variation of the luminance rendering it darker than the reference (see fig 2). This time, the shape of the SSD is greatly impacted with a flatten area resulting in a significant shift in the extremum location which means it is not suitable for an optimization process in this conditions. The MI and SCV on the other hand show only a small attenuation of the slopes around their optimum but stay sharp enough to assure convergence toward the correct position during an optimization process.

Obviously, this analysis considers only 2 dof, whereas in the visual servoing experiments considered in this paper, the 6 camera dof are controlled. Nevertheless these experiments (along with other which can be found in [START_REF] Richa | Visual tracking using the sum of conditional variance[END_REF]) allow to illustrates that SCV is far less sensitive than SSD to illumination variations.

C. SCV-based control law

Using the SCV to measure the difference between I(r) and Î the optimization process becomes:

r = arg min r (I(r) -Î). (15)
Considering the LM approach shown in equation ( 6), the control law becomes:

v = -λ(H S + µ diag(H S )) -1 L SCV (I(r) -Î) (16)
where H S = L SCV T L SCV and L SCV is the interaction matrix associated to the task. Only illumination variations (and not camera pose) impact Î the interaction matrix matrix can be chosen as in [START_REF] Collewet | Photometric visual servoing[END_REF]:

L SCV = ∂I(r) ∂r = -∇I(r) T L x . (17)

IV. EXPERIMENTAL VALIDATIONS

A. Histogram Binning

To compute the probability distribution functions used by the SCV and compute for each new frame the new reference image Î, histogram binning was used. This was done both to smooth the resulting image Î and to decrease the computation time in order to enhance the quality of the servoing task. To compute such histograms a number of bins N c is set, then the source image is scaled:

I(x) = I(x) (N c -1) d -1 . ( 18
)
The histograms are then computed on this scaled image which dynamic is N c, ensuring that they are composed of only N c bins. An other reason for choosing not to use the full dynamic of the image is that computing probabilities from the histograms as in ( 14) results in approximating them. This is the case because an empirical observation of a probability distribution function does not necessarily equal its 'real' distribution. The main problem with those approached probabilities is that they can result in noise in the predicted image when using an important number of bins.

On the other hand, if the chosen number of bins is too low, the resulting image loses a lot of details. See figure [START_REF] Collewet | Modeling complex luminance variations for target tracking[END_REF] for examples.

It is also interesting to note that as the number of bins decreases, so does the precision of the positioning task since more high frequency details are lost. This is why during, the servoing task the number of bins is adapted dynamically. First, the binning is done using 64 bins as the level of detail in the image is sufficient with this number of bins and increases to 256 when close from reach to get more precision. To do that, the value of the SCV at the beginning of the task is kept in memory and the switch is effected when the current SCV reaches a certain percentage of that value.

B. First Experiment: Nominal case

The first experience aims to analyze the behaviour of the SCV approach in a classical case. The positioning task controls all 6 degrees of freedom. The interaction matrix during the servoing is computed assuming that the Z coordinate of each point is constant, in this case it assumed as equal to 70 cm. As for the λ and µ parameters of the optimization, they were empirically chosen as 4 and 0.001 respectively. For the initial pose, the difference was ∆r = {16cm, -20cm, 6cm, -0.27rad, -0.19rad, -0.09rad} with relation to the desired pose. Figure 4 shows the behaviour of the model during the optimization process. In the error image between the current and expected images, a pixel of luminance l=128 (grey pixel) means there is no difference between the two images. The graphics show the evolution of a chosen parameter with relation to the iterations of the algorithm.

Several observations can be made concerning this first experiment. First, the task converges, leading the robot to the good position with a good precision of ∆r * = {0.07mm, 0.16mm, 0.01mm, 1e -4 rad, 2e -5 rad, 1e -4 rad}. The second observation is that the evolution of the camera location is smooth. The SCV also vanishes without being noisy, showing that the SCV is well suited in this case.

C. Second Experiment: Robustness with relation to illumination changes

The goal of this experiment is to show the robustness of our method towards illumination variations in the scene. In order to do that, after acquiring the image at the desired position, the servoing is launched after the lights have been attenuated. The results of this experiment are exposed on figure 5. The initial position was a little bit less complicated with a difference of ∆r = {14cm, -18cm, 1cm, -0.28rad, -0.18rad, -0.03rad} from the desired position, which is still a consequent movement.

In these conditions, the servoing task still converged, thanks to the adaptation of the predicted image to the current one as we can see on figure 5. The final position was reached with a precision of ∆r * = {0.4mm, 0.8mm, 0.9mm, 1e -3 rad, 4e -4 rad, 1e -3 rad} which gives a distance to the desired position of 1.3mm. It is slightly less precise than in the nominal case but it was still a good result compared to the other methods since the SSD diverged and the mutual information showed a repositioning precision of 2.4mm. The graph of SCV also shows around iteration 300 the change in the number of bins which caused an improvement in the precision without impacting the convergence of the task.

D. Third Experiment: Case of a specularity

Finally, a last experiment was done to show the behaviour of the SCV when confronted to specularities. The SCV is not really suited for this purpose, as local variations will change the global probabilities therefore areas where no variations occurred will be treated as areas where variations occurred which will create incoherences in the predicted image. But even if the measure is impacted by specularities, it is interesting to see how the servoing task reacts when confronted to the situation. To realize the experiment, the task was launched again from the position described in creating a specularity in the image. The results of this experiment are shown on figure 6. The predicted image is directly impacted, as the variations in the probability distribution functions due to the specularity are applied to the whole considered area. The evolution of the SCV is also impacted, as the specularity in the image moves depending on the position of the camera. But even though it is lessprecise than in the nominal case, the task still converges with a distance to the goal position of 9mm when the SSD ends up at 15mm in the same conditions and the mutual information at 4mm. The analysis of ∆r trans is really interesting as it shows a shift in the minimum of the SCV because the robot came closer to the desired position before converging with a greater repositioning error.

V. CONCLUSION In this paper we described a new way to achieve direct visual servoing. This approach is based on a similarity measure issued from the information theory called the sum of conditional variance (SCV). Compared to photometric visual servoing method [START_REF] Collewet | Photometric visual servoing[END_REF], it performs similarly in nominal cases, when large occlusions or specularities appear in the scene and better when the illumination conditions are nonlocally changing. Compared to mutual information based visual servoing [START_REF] Dame | Mutual information-based visual servoing[END_REF], the range of application is narrower for the SCV as it is less robust towards local variations and is not multi-modal. But it is easier to compute and less computationally expensive when the number of bins used for the servoing task increases. This makes it a very good compromise when performing direct visual servoing. As SCV is computed based on the image histograms, it is non-invariant to local changes. This problems could be addressed for example by using sub-regions histograms as it was mentioned in [START_REF] Hermosillo | Variational methods for multimodal image matching[END_REF] or using M-estimators in the control law [START_REF] Comport | Statistically robust 2D visual servoing[END_REF].

Fig. 1 .Fig. 2 .

 12 Fig. 1. Cost function in nominal case. Here the displayed current patch is the one resulting of tx = 0 and ty = 0 pixel.

Fig. 3 .

 3 Fig. 3. Influence of the number of bins on the predicted image when far from reach. On the left, with 8 bins the image is flattened and has lost a lot of high frequencies. 256 bins introduces more noise when the difference between I and I * increases than 64. The frame on the borders represent the area in the image which is not included in the computation.

Fig.

  Fig. Behaviour of the model in a classical case.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Behaviour the model in a the case of illumination variations. The evolution of the SCV shows around iteration 210 gain in precision thanks to the increase in the number of bins used.


João Paulo Lima

Hideaki Uchiyama

Veronica Teichrieb

Eric Marchand

Texture-Less Planar Object Detection and Pose Estimation Using Depth-Assisted Rectification of Contours

Keywords: Pose estimation, texture-less objects, augmented reality, RGB-D cameras

This paper presents a method named Depth-Assisted Rectification of Contours (DARC) for detection and pose estimation of textureless planar objects using RGB-D cameras. It consists in matching contours extracted from the current image to previously acquired template contours. In order to achieve invariance to rotation, scale and distortions, a rectified representation of the contours is obtained using the available depth information. DARC requires only a single RGB-D image of the planar objects in order to estimate their pose, opposed to some existing approaches that need to capture a number of views of the target object. It also does not require to generate warped versions of the templates, which is commonly needed by existing object detection techniques. It is shown that the DARC method runs in real-time and its detection and pose estimation quality are suitable for augmented reality applications.

INTRODUCTION

This paper proposes a technique for texture-less planar object detection and pose estimation using information provided by an RGB-D camera. Since the method makes use of depth data for obtaining a rectified representation of contours extracted from the RGB image, it is named Depth-Assisted Rectification of Contours (DARC). It shall be demonstrated that this normalized representation is invariant to rotation, scale and perspective distortions. It is obtained by transforming the contour points to a canonical view. Once the contours are rectified, they can be directly matched by computing their similarity using chamfer distance [START_REF] Barrow | Parametric correspondence and chamfer matching: two new techniques for image matching[END_REF]. This allows finding correspondences between contours extracted from a query image and previously obtained rectified contours from a single template image of each object, without needing to compute perspective warps from the reference images. Based on these correspondences, accurate pose estimation and augmentation of texture-less planar objects in real-time is possible.

There are some object detection and pose estimation techniques suitable for non-textured objects that make use of depth data [START_REF] Hinterstoisser | Gradient response maps for real-time detection of textureless objects[END_REF][6] [START_REF] Park | Texture-less object tracking with online training using an RGB-D camera[END_REF]. However, such methods need to capture several views of the target object, while the DARC technique needs only an RGB-D image of the planar object taken from a single view for estimating its pose.

DEPTH-ASSISTED RECTIFICATION OF CONTOURS

First, contours are extracted from the query RGB image using the Canny edge detector [START_REF] Canny | A computational approach to edge detection[END_REF]. Then, for each extracted contour, the 3D points that correspond to the 2D points of the contour and its inner contours are selected. In the remainder of this paper, the set of points that belong to a contour or its inner contours is named contour group. Then, for each contour group, the corresponding 3D points of the 2D contour points are used to estimate the normal and orientation of the contour group via Principal Component Analysis (PCA). The centroid of the 3D contour points is computed, which is invariant to affine transforms. A covariance matrix is computed using and , and its eigenvectors and corresponding eigenvalues are computed and ordered in ascending order. The normal vector to the contour group plane is [START_REF] Berkmann | Computation of surface geometry and segmentation using covariance techniques[END_REF]. If needed, is flipped to point towards the viewing direction. Contour group orientation is given by and , which can be seen as the and axis, respectively, of a local coordinate system with origin at [START_REF] Berkmann | Computation of surface geometry and segmentation using covariance techniques[END_REF]. There are four possible orientations given by combinations of the and axis with different signs. It only makes sense to consider all four orientations if mirrored or transparent objects might be detected. Otherwise, only two orientations are enough, which are given by using both flipped and non-flipped as the axis and computing the axis as the cross product of and .

In order to allow matching instances of the same contour group observed from different viewpoints, they are normalized to a common representation. Translation invariance is achieved by writing the coordinates of the 3D contour points relative to the centroid . Rotation invariance is obtained by aligning and with the and global axes, respectively. Since the 3D contour points are in camera coordinates, they are scale invariant. Perspective invariance is obtained by aligning the inverse of the normal vector to the global axis. This way, the rectified contour points can be computed as follows:

.

The rectified points should lie on the plane ( ). Since two or four orientations given by and are considered, each one is used to generate a different rectification of a contour group. All these rectifications are taken into account in the matching phase. In some cases the estimated orientation is not accurate. However, this is still sufficient for matching and pose estimation purposes.

After being rectified, query contour groups can be matched to a previously rectified template contour group. This is done by comparing each rectified query contour group with the rectified template contour group, considering the different orientations computed. First, a match is rejected if the upright bounding rectangles of the rectified contour groups do not have a similar size. Then, it is computed a coarse pose that maps the 3D unrectified template contour group to the 3D unrectified query contour group. Given the rotation and translation that rectify the template contour group and the rotation and translation * email: {jpsml, vt}@cin.ufpe.br † email: {Hideaki.Uchiyama, Eric.Marchand}@inria.fr that rectify the query contour group, the coarse pose is obtained by: . The 3D unrectified template contour group is transformed using the coarse pose and then projected onto the query image. After that, the upright bounding rectangle of the projected points is computed and compared with the upright bounding rectangle of the 2D query contour group. If they are not close to each other or their are not similar, the match is discarded.

The similarity between template contour group projection and 2D query contour group is given by their chamfer distance [START_REF] Barrow | Parametric correspondence and chamfer matching: two new techniques for image matching[END_REF]:

, where is the number of points in the template contour group, is the -th template contour point and is the query distance transform truncated to a value . For each query contour group, the template contour group orientation with smallest chamfer distance is marked as a candidate match.

If there is a candidate match for a given query contour group, then a refined pose of the contour group is estimated from the previously computed coarse pose using the Levenberg-Marquardt algorithm. The query distance transform is used to compute the residuals. Finally, the chamfer distance between the template contour group and query contour group is calculated using the refined pose. If it is below a threshold, then the match is considered as correct.

In the current implementation, a single contour group is used for defining the pose of a given object. If the object contains several disjoint contour groups, one of these has to be selected for being used as template.

RESULTS

In order to evaluate DARC, some image sequences were captured using an RGB-D camera and synthetic RGB-D images were also generated. All the experiments were performed with 640x480 images. hardware used in the evaluation was a Microsoft Kinect for Xbox 360 and a laptop with Intel Core i7 720QM @ 1.60GHz processor and 6GB RAM.

Figure 1 shows some results obtained with DARC for detection and pose estimation of different planar objects. It can be seen that DARC can deal with significant changes in rotation and scale as well as with perspective distortions. The contour groups used as templates are the octagon of the stop sign together with its inner contours, the continent frontier of the map and the outer square of the logo together with its inner contours. Similarly to [START_REF] Lee | Depth-assisted real-time 3D object detection for augmented reality[END_REF], the use of depth information allows DARC to distinguish objects that have the same shape but different sizes, as illustrated in Figure 2. The virtual objects are rendered with a different color and size depending on the size of the detected object. Detection methods that are based solely on RGB data are not able to differentiate, for example, between a small object at a close distance and a big object at a far distance when their projections have the same shape and size. The DARC method runs at ~20 fps while detecting a single template and then the frame rate declines linearly as the number of detected templates increases.

CONCLUSION

It was presented the DARC technique, which performs detection and pose estimation of texture-less planar objects by making use of depth data available in RGB-D consumer devices. DARC works in real-time and proved to be robust to in-plane and out-ofplane rotations, scale and perspective deformations, providing a pose with reasonable accuracy for AR applications.

Index

  Terms: I.4.8 [Image Processing and Computer Vision]: Scene Analysis-Depth Cues, Range Data, Tracking; H.5

Figure 1 :

 1 Figure 1: Augmentation of a traffic sign (top left) under different poses using DARC.

Figure 2 :

 2 Figure2: Distinction of objects with the same shape and different sizes using DARC. The bigger stop sign is augmented with a bigger green teapot, while the smaller stop sign is augmented with a smaller blue teapot.

Acknowledgements. This work is financially supported by the CAPES/INRIA/CONICYT STIC-AmSud project ARVS and by CNPq (process 141705/2010-8). Special thanks go to Mário Gonçalves, for lending a Kinect device.


Antoine Petit

Eric Marchand

Keyvan Kanani

VISION-BASED DETECTION AND TRACKING FOR SPACE NAVIGATION

This paper focuses on navigation issues for space autonomous, uncooperative rendezvous with targets such as satellites, space vehicles or debris. In order to fully localize, using a vision sensor, a chaser spacecraft with respect to a target spacecraft or debris, a visual model-based detection and tracking technique is proposed. Our tracking approach processes complete 3D models of complex objects, of any shape by taking advantage of GPU acceleration. From the rendered model, correspondences are found with image edges and the pose estimation task is then addressed as a nonlinear minimization. For detection, which initializes the tracking, pose estimation is based on foreground/background segmentation and on an efficient contour matching procedure with synthetic views, over a few initial images. Our methods have been evaluated on both synthetic images and real images.

INTRODUCTION

The active removal of heavy space debris (typically larger than 1000kg) has been identified as a key development to control the growth in the debris population and to limit the risk for active satellites. In that context, ESA has recently launched projects such as the Geostationary Servicing Vehicle (GSV) or the RObotic GEostationary orbit Restorer (ROGER), both tasked to capture, inspect, assist or re-orbit satellites in trouble. Astrium has been working on optimization and implementation of sensors and navigation solutions onboard a Debris Removal Vehicle with the main objective to ensure high safety proximity maneuvers. Here we focus on algorithms which achieves 3D visual detection and tracking of a complex target, based on its 3D model and using a monocular camera, and which allows estimation of the chaser state with respect to a target spacecraft or debris.

Our approach has been tested on real images, such as Soyuz-TMA rendezvous with ISS and Atlantis space shuttle pitch maneuver, to demonstrate its robustness to real data. A test campaign on simulated images (Spot family satellites) has also been carried out to quantitatively show the performances and robustness of both tracking and associated navigation.

3D model-based tracking

Common model-based approaches use either point [START_REF] Bleser | Real-time 3d camera tracking for industrial augmented reality applications[END_REF], edge features [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF][START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] or a combination of both [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF]. Edge features offer a good invariance to illumination changes or image noise and are particularly suitable with poorly textured scenes. For such class of approaches, the pose computation is achieved by minimizing the distance between the projected edges of the 3D model and the corresponding edge features in the image, extracted thanks to a 1D search for gradient maxima along the model edge normals. Weighted numerical nonlinear optimization techniques are used for the minimization. To reject outliers, methods like RANSAC [START_REF] Bleser | Real-time 3d camera tracking for industrial augmented reality applications[END_REF] or M-Estimators [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF][START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] are common trends to make the algorithm robust to occlusions and illumination variations.

Most of these approaches process 3D models which are made-up of lines. But achieving the model projection in the image has limitations and some problems appear when dealing with objects made of cylindrical, spherical, curved or complex shapes. Furthermore, complete polygonal models for complex objects can be too heavy and need to be manually redesigned to keep the most relevant edges of the scene and to make the algorithm computationally efficient.

A first challenge of our solution is to process a complete polygonal 3D model. In this sense, the whole information from the geometrical shape of any kind of scene can be used and a heavy phase of a manual redesign of the model is completely avoided. Our method relies on the use of the graphics process units (GPU) and of a 3D rendering engine. This allows to automatically manage the projection of the model and to determine the visible and prominent edge from the rendered scene. Such method has also been considered in [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF]. An advantage of these technique is to automatically handled the hidden face removal process and to implicitly handle auto occlusions. A second challenge is to improve the robustness by combining both depth and texture edges and by including multiple hypothesis in the edge matching process.

3D model-based detection

As the tracking procedure works frame by frame, an initial estimate of the pose has to be provided. In the literature, many object recognition methods consist in learning and classifying 2D bag of features extracted from various views of the query object ( [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF][START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]). As they have proven their efficiency for 2D textured objects for many recognition tasks, it is quite unadapted to our case, as we consider poorly textured or untextured 3D objects. Besides, real training images are hardly to be obtained for our applications. For these reasons we propose to rely on the shape and saliency of our object through a set of synthetic views obtained from the 3D model. Our detection method, while being generic and quite unsupervised, can be computationally heavy and too coarse when considering a single query image ([4, 12, 9]), and the tracking could then be lost. Therefore we propose to spread our detection strategy over a sequence of several images. This would enable to keep tracking the object and refine its pose within this sequence. In this way, our approach is similar to [START_REF] Toshev | Shapebased object recognition in videos using 3d synthetic object models. Computer Vision and Pattern Recognition[END_REF]. The overall purpose is to robustly match each image with a prototype view of the model, with respect to a position, an orientation in the image and a scale, which are estimated through a particle filtering framework. An initial coarse estimate of these parameters is necessary and is found thanks to a segmentation of the foreground object from the background.

The remainder of the paper is organized as follows. Section 2 gives an overview of the proposed method for tracking and Section 3 for detection. Some experimental results are given in Section 4.

3D MODEL BASED TRACKING

Classical approaches

Our problem is restricted to model-based tracking, using a 3D model of the target. The purpose is to compute the camera pose which provides the best alignment between edges of the projected model and edges extracted in the image.

Such approaches have proved to be very efficient and various authors have proposed different formulation of the problem (eg, [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF][START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF]). Although one can find some difference in these various solution, the main idea is the following. Given a new image, the 3D model of the scene or the target is projected in the image according to the estimated previous camera pose r. Each projected line l i (r) = pr(L i , r) of the model is then sampled leading to a set of 2D points {x i }. Then from each sample point x i a 1D search along the normal of the projected edge is performed to find a corresponding point x ′ i in the image.

In order to compute the new pose, the distances between points x ′ i and the projected lines l i are minimized with respect to the following criteria [START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] :

∆ = i ρ(d ⊥ (l i (r), x ′ i )) (1)
where d ⊥ (l i (r), x ′ i ) is the distance between a point x ′ i and the corresponding line l i (r) projected in the image from a pose r. ρ is a robust estimator, which reduces the sensitivity to outliers. his is a non-linear minimization process with respect to the pose parameters r. In [START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], the minimization process follows the Virtual Visual Servoing framework similar to Gauss-Newton approach.

Our purpose to consider complex shape targets, textured or untextured, leads to forget the notion of 3D sharp edges as in [START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] or in our previous work [START_REF] Petit | Visionbased space autonomous rendezvous : A case study[END_REF] and to consider only 3D points that belongs indifferently to sharp edges or to the "occlusion boundaries" or rims, or to texture edges. Two issues have then to be considered: complex model projection and 3D points selection.

The tracking algorithm in our method is structured as follows:

• Projection of the detailed model with respect to the pose r k computed for the previous image I k . To achieve this process we rely on the graphics libraries (openGL) that allows to perform quickly this projection regardless the complexity of the model thanks to the use of the GPU.

• From this projection we generate 3D measurement points X i by extracting edges from the depth and texture discontinuities of the rendered model.

• We then search for corresponding edge points x ′ i in image I k+1 . To allow a better robustness, we propose a multiple hypothesis version of the algorithm.

• Last step is to estimation of the pose r k+1 which minimizes the errors d(x i , x ′ i ) between the point extracted from the image x ′ i and the projection of the selected 3D points x i (r) = pr(X i , r), with the following criteria:

∆ = i ρ(d(x i (r), x ′ i )) (2)

Generation of 3D measurement points

As in [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], at each acquired image I k+1 , the model is rendered and projected using an openGL rendering engine, with respect to the previous pose r k .

Our goal is to obtain a set of 3D points X i that belong to target rims, edges and visible texture from the rendered textured scene and the depth buffer. Our approach follows [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF] and is related to the techniques of silhouette generation of polygonal models described in [START_REF] Isenberg | A developer guide to silhouette algorithms for polygonal models[END_REF].

Edge extraction using depth and texture discontinuities. From the depth or Z-buffer, which corresponds to the depth values of the scene according to the camera location at each pixel point (Figure 1(a)), we can determine the discontinuities which suit the geometrical appearance of the scene. Therefore, we apply a second order differential operator, such as a Laplacian filter, to these computed Z values, resulting in a binary edge map of the visible scene ((Figure 1(b)). In our approach, we have implemented the filtering computations on the GPU through shader programming, resulting in a much lower computational time.

In case of highly textured scenes, geometrical edges are not sufficient and ambiguities with texture edges arise, which results in false matching and thus local minima during the pose estimation process. An improvement of our method is then to combine the depth discontinuities with texture discontinuities. The rendered textures of the 3D model are thus processed by a classical Canny edge algorithm and the obtained edges are added to the ones generated from the depth buffer. Generation of 3D measurement points. Given the edge map of the complete scene, the 3D coordinates of the edge points in the scene can be computed thanks to the Z-buffer and the pose used to project the model. As dealing with the whole edge map can be computationally intensive, we can sample it along x and y coordinates of the image in order to keep a reasonable number of these edge measurement points.

Besides, the tracking phase (see Section 2.B) requires the orientation of the edge underlying a measurement point x i . For the texture edges, it is done within the Canny al-gorithm on the rendered textures. For the depth edges, we compute the Sobel gradients along x and y on a grey level of the normal map of the scene. The normal map of the scene associates the [R,G,B] value of each pixel location to the coordinates in the world frame of the normal to the corresponding surface in the scene (see Figure 1(d)). These basic image processing steps, as well as the retrieval of the normal map, are also processed on the GPU.

Pose Estimation and low level tracking

Tracking from edge measurement points. The measurement points are then processed to track corresponding edges in the image. In a similar manner to [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF][START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF][START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], we perform a 1D search along the normal of the underlying edge (Figure 2 and Figure 1(c)) of each x i . A common approach is to choose the pixel with the maximum gradient as the matching edge point x ′ i in the image.

Minimization of a distance to a line. Once correspondences are established, the goal is then to estimate the new pose r k+1 that realigns the measurement points with their matching observed image points x ′ i . This task is addressed by minimizing the errors d(x i (r), x ′ i ). As in [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF][START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF][START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], our approach considers the distance between the projected 3D line l i (r) underlying the projected 3D measurement point X i (r) and the selected matching point x ′ i in the image (see Figure 2). Criteria (2) becomes:

∆ = i ρ(d ⊥ (l i (r), x ′ i ))) ( 3
)
where ρ is a robust estimator used to reject outliers (Tuckey estimator), and d ⊥ (l i (r), x ′ i ) is the distance between a point x ′ i and the corresponding line l i (r). It has to be noted that for sharp edges the 3D point X i (r) is not modified when we modify r. This is no longueur the case for points X i (r) that belong to an occlusion rim. Nevertheless, since the camera motion between two successive images is very small, this approximation has no impact on the efficiency of the approach.

The optimization technique is similar to the virtual visual servoing framework described in [START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], which relates this optimization problem to a visual servoing issue.

Multiple hypothesis solution.

In order to improve the robustness of the pose estimation and to avoid problems due to ambiguities between edges, it is possible to consider and register different hypothesis corresponding to potential edges. They correspond to different local extrema of the gradient along the scan line. As in [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF][START_REF] Teulière | Using multiple hypothesis in model-based tracking[END_REF], we choose the hypothesis which has the closest distance to the projected 3D line l i during the minimization process. The cost function becomes : where points x ′ i,j are the selected candidates for each measurement point x i .

∆ = i ρ(min j d ⊥ (l i (r), x ′ i,j )) (4)

3D-MODEL BASED DETECTION AND POSE ESTIMATION

Here is addressed the issue of initializing our tracking algorithm, for a poorly textured object, with a potentially cluttered background or not. The proposed solution only relies on the 3D model of the object. The pose estimation by detection is achieved over a few initial successive images. The overview of the method is described as follows (and see Figure 3) :

• Offline learning stage : it aims at building a hierarchical model view graph leading to prototype views V of the model.

• Online detection stage :

-Segmentation of the object using a real-time bilayer segmentation technique. By computing binary moments of the extracted silhouette, an initial estimate of its center of gravity (x c , y c ), its orientation θ and its area A.

-For each prototype view, a particle filter with respect to the state x = [x c y c θ A] T is set.

-Through a Bayesian framework, at each frame the most likely prototypical view V and its corresponding estimate xv are determined, providing the complete pose.

-When a view reaches a sufficient fitting probability with respect to the others, the process is stopped. The pose is thenrefined by traversing through the hierarchical view graph.

Hierarchical model view graph

Generation of synthetic views. The purpose of the method is to match an input image with a synthetic view generated from the 3D model with respect to a similarity metric. These synthetic views thus have to cover the whole 6D search space. We propose, as in [START_REF] Christopher | A similarity-based aspect-graph approach to 3d object recognition[END_REF][START_REF] Ulrich | Cad-based recognition of 3d objects in monocular images[END_REF][START_REF] Reinbacher | Pose estimation of known objects by efficient silhouette matching[END_REF][START_REF] Toshev | Shapebased object recognition in videos using 3d synthetic object models. Computer Vision and Pattern Recognition[END_REF], to generate these views on a view sphere centered on the 3D model, parametrized by two DoF (latitude and longitude). These is performed by setting virtual cameras at uniformly spaced viewpoints (Figure 3 left). From this rendered views, we extract their contours by processing the corresponding depth buffer of the scene through a Laplacian filter. Thus, in a different manner to [START_REF] Toshev | Shapebased object recognition in videos using 3d synthetic object models. Computer Vision and Pattern Recognition[END_REF], we do not only consider the silhouette contours but also the crease contours of the object.

Building a hierarchical view graph. Since this process can be computationally challenging when considering the whole database, we iteratively cluster the views into a hierarchical view graph. At the first level of hierarchy, we build clusters within disjoint neighborhoods in the spherical space, in order to cope with memory requirements. This is done by comparing the views with each other in each neighborhood with respect to an edgebased similarity metric. The result is a set of clusters, each represented by a prototype model view. It defines the first level of our hierarchy. We proceed in the same way with these views. Thus we can iteratively build successive hierarchical levels with this method until a reasonable number (around 30) of prototype model views is reached.

Segmentation and silhouette extraction

As matching the model views with the images gives two DoF (lattitude and longitude around the object), a solution is proposed to estimate the four other parameters, which are the position and orientation of the object in the image, and its scale or area in the image. It relies on the segmentation of the silhouette of the object, which is supposed to be moving in the image. However these parameters are often coarsely computed due for example to some cluttered background, occlusions so it is necessary to adapt and refine them in order to find a consistent best match among the few prototype model views.

A Bayesian Framework for matching input images to prototype model views

Our problem consists in aligning the prototype views to the input images and finding the most likely one. It has appeared relevant to reason on several input images considering that the results provided by segmentation can be too coarse. Besides, as this detection method can be computationally challenging, the process is spread over a few frames instead of focusing only on the first frame with more exhaustive and costlier process and risking to loose track of the moving object in the next frames. In order to assure a smooth transitions between the prototype model views throughout the image sequence, a bayesian framework is proposed to determine the most likely view V j k , along with the parameters x = xc ŷc θ Â T , estimated through particle filtering, at each frame I k (see Figure 3).

EXPERIMENTAL RESULTS

Implementation

The rendering process of the 3D polygonal and textured model relies on OGRE (Object-oriented Graphics Rendering Engine). The library avoids to use explicitly the underlying system libraries (Direct3D or OpenGL). We have considered shader programming for some image processing steps during the rendering and edge generation phases. This is done using OpenGL Shading Language (GLSL), supported by OGRE. Regarding hardware, an NVIDIA NVS 3100M graphic card has been used, along with a 2.8GHz Intel Core i7 CPU.

For tests procedures, we have performed experiments on both real and synthetic image sequences. They consist in evaluations of the algorithm described in the previous sections, for the texture and untextured cases and for the single and multiple hypothesis solutions.

Tests on real images

The first example deals with the tracking of the Soyuz TMA-12 spacecraft during its rendezvous phase with the International Space Station (ISS). With its three different modules, the main body of the spacecraft is of complex shape, with curved and fuzzy edges, but the solar arrays tend to facilitate the tracking. Here the tracking procedure consists in only using the depth discontinuities in the rendered scene to generate the visible and prominent edges (see Figure 1(d)), and the single hypothesis solution has shown to be sufficient for this sequence. Despite uncertainties over the camera internal parameters, the 3D model consistency, the cluttered background and the low quality of the video, the tracking phase is successfully achieved (see Figures 5(a)-5(d)). For detection, we observe that as the segmentation is not very precise (Figure 4 The second example concerns the Atlantis Space shuttle performing a pitch maneuver for its rendezvous with the ISS. An untextured 3D model of the spacecraft has been processed for the tracking, together with the multiple hypothesis registration process and a Kalman filter with a constant velocity model on the pose parameters. Figure 6 shows the results of the detection procedure. The segmentation phase (Figure 6

Tests on synthetic images

The evaluation has been performed using a ray-tracing simulator developed by Astrium for space environments.

We focus here on the case of the Spot satellite family.

For space debris removal concerns, we consider an arbitrary rotation for the target attitude and a chaser spacecraft is supposed to be located on a similar orbit, with a slightly different eccentricity in order to make the chaser fly around the target (Figure 8(a)), in the x Orbz Orb plane of the orbital frame (see Figure 8(b)). The chaser is also equipped with a camera filming the target and a spot light to lighten the target.

Computational costs

Thanks to the implementation of several image processing phases on the GPU, the execution time could be considerably reduced. The whole algorithm can be processed at around 15 fps when relying on depth edges. The multiple hypothesis solution does not affect much computations. Including texture information makes the process costlier, since more points are considered, with a 7 fps framerate for the Spot sequence. The detection technique runs at 0.5 fps.

CONCLUSION

This paper presents detection and tracking methods suited for complex, textured or untextured objects in deep space environments, for space rendezvous and space debris removal purposes. The tracking relies on the generation of visible and salient edges from the 3D complete polygonal model, projected using a rendering engine. Information from both geometrical and texture discontinuities are used. This technique avoids the heavy and restrictive processing of a 3D line model. The method is similar to the classical approaches as it consists in the realignment of the generated model edges with edges detected in the image. A model-based detection framework has also been designed to initialize the tracking, through a Bayesian edge matching procedure over a few initial images. From the tests carried out on real images, our approach qualitatively presents satisfactory results, for both tracking and detection phases. Thanks to the realistic image simulator, performances can be measured, showing the relevance of the approach. The implementation proves to be computationally efficient.

Figure 1 :

 1 Figure 1: On (a) is represented the z-buffer of the rendered 3D model using Ogre3D, from which the edge map is computed (b).This edge map is then sampled to extract measurement points, reprojected on the current image and from them a 1D search along the edge normal is performed to find a matching edge point in the acquired image (c). (d) shows the normal map of the scene.

Figure 2 :

 2 Figure 2: Moving edge principle: from the initial pose r0, 1D search along the projected contour underlying the measurement point. Distance of a point x ′ i to a corresponding line l i (r) within the minimization process.

Figure 3 :

 3 Figure 3: Framework of the detection process. Synthetic views of the model are generated on a view sphere. Transitions between model views follow a Markov jump model.

  (a)), it takes five input images (three are shown here, Figures 4(b)-4(d)) to match with a sufficiently likely model view along with acceptable state parameters to initialize the tracking.

Figure 4 :

 4 Figure 4: Detection for the Soyuz sequence. From the coarse segmentation phase (a) and an unfitted model view (b) the process converges to a consistent one (d).

Figure 5 :

 5 Figure 5: Tracking relying on depth edges for the Soyuz sequence.

Figure 6 :Figure 7 :

 67 Figure 6: Detection for the Atlantis sequence

Figure 8 :

 8 Figure 8: Chaser and target (Spot) orbits in the Earth reference frame

Figure 9 :

 9 Figure 9: The segmentation of the target (a) is quite coarse due to the cluttered background. We observe the detection, which takes 8 images to converge (4 are shown here, (b)-(e)) and the tracking ((f)-(m)), relying on depth and texture edges, with multiple hypothesis and Kalman filtering.

Figure 10 :

 10 Figure10: Estimated camera pose parameters of the target over all the sequence, along with the ground truth, for the single and multiple hypothesis solutions, together with a Kalman filter or not.


Antoine Petit

Eric Marchand

Keyvan Kanani

Tracking complex targets for space rendezvous and debris removal applications

In the context of autonomous rendezvous and space debris removal, visual model-based tracking can be particularly suited. Some classical methods achieve the tracking by relying on the alignment of projected lines of the 3D model with edges detected in the image. However, processing complete 3D models of complex objects, of any shape, presents several limitations, and is not always suitable for real-time applications. This paper proposes an approach to avoid these shortcomings. It takes advantage of GPU acceleration and 3D rendering. From the rendered model, visible edges are extracted, from both depth and texture discontinuities. Correspondences with image edges are found thanks to a 1D search along the edge normals. Our approach addresses the pose estimation task as the full scale nonlinear minimization of a distance to a line. A multiple hypothesis solution is also proposed, improving tracking robustness. Our method has been evaluated on both synthetic images (provided with ground truth) and real images.

I. INTRODUCTION

A. Context : active removal of heavy space debris

The active removal of heavy space debris (typically larger than 1000kg) has been identified as a key development to control the growth in the debris population and to limit the risk for active satellites. In that context, Astrium has been working on optimization and implementation of sensors and navigation solutions onboard a Debris Removal Vehicle with the main objective to ensure high safety proximity maneuvers. In particular, special attention has been paid to the design of autonomous, vision-based navigation solutions for uncooperative rendezvous with space debris. In this paper we focus on an algorithm which achieves 3D tracking of complex target and allows fine estimation of chaser states with respect to a target spacecraft or debris.

This tracking algorithm has been tested on real images, such as Soyuz-TMA rendezvous with ISS and Atlantis space shuttle pitch maneuver to demonstrate its robustness on real data. A test campaign on simulated images has also been carried out to quantitatively show the performances and robustness of both tracking and associated navigation.

B. 3D model based tracking

In order to estimate the pose of a camera with respect to a specific scene, common model-based approaches use either point [START_REF] Bleser | Real-time 3d camera tracking for industrial augmented reality applications[END_REF], edge features [START_REF] Lowe | Fitting parameterized three-dimensional models to images[END_REF], [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF], [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] or a combination of both [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF], [START_REF] Rosten | Fusing points and lines for high performance tracking[END_REF]. Edge features offer a good invariance to illumination changes or image noise and are particularly A. Petit is with INRIA Rennes -Bretagne Atlantique, Lagadic Team, France, Antoine.Guillaume.Petit@inria.fr E. Marchand is with Université de Rennes 1, IRISA, Lagadic Team, France, Eric.Marchand@irisa.fr Keyvan Kanani is with Astrium, Toulouse, France suitable with poorly textured scenes, whether the scene is in industrial, outdoor or indoor environments. For such class of approaches, the pose computation is achieved by minimizing the distance between the projected edges of the 3D model and the corresponding edge features in the image, extracted thanks to a 1D search for gradient maxima along the model edge normals. Weighted numerical nonlinear optimization techniques like Newton-Raphson or Levenberg-Marquardt are usually implemented for the minimization. To reject outliers, methods like RANSAC [START_REF] Bleser | Real-time 3d camera tracking for industrial augmented reality applications[END_REF] or the use of M-Estimators such as the Tuckey estimator [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF], [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] are common trends to make the algorithm robust to occlusions and illumination variations. But the robustness deteriorates when ambiguities between different edges occur, especially between geometrical and texture edges of the scene. One way to address this issue has been to fuse the information of edge features with information given by particular keypoints [START_REF] Pressigout | Real-time hybrid tracking using edge and texture information[END_REF] or by other sensors [START_REF] Klein | Tightly integrated sensor fusion for robust visual tracking[END_REF]. Other solutions have considered multiple hypothesis for potential edge-locations in the image [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF], [START_REF] Teulière | Using multiple hypothesis in model-based tracking[END_REF].

Regarding implementation purposes, most of these approaches process 3D models which are made-up of segments. But achieving the model projection in the image has limitations and some problems appear when dealing with objects made of cylindrical, spherical, curved or complex shapes. Furthermore, provided complete polygonal models for complex objects can be too heavy and need to be manually redesigned to keep the most relevant edges of the scene and to make the algorithm computationally efficient.

A first challenge of the solution proposed in this paper is to process a complete polygonal 3D model, in order to track the object in the image and to estimate the camera pose. In this sense, the whole information from the geometrical shape of any kind of scene can be used and a heavy phase of a manual redesign of the model is completely avoided. Our method relies on the use of the graphics process units (GPU) and of a 3D rendering engine. This allows to automatically manage the projection of the model and to determine the visible and prominent edges from the rendered scene. Such method has also been considered in [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], [START_REF] Reitmayr | Going out: robust model-based tracking for outdoor augmented reality[END_REF]. An advantage of these technique is to automatically handle the hidden face removal process and to implicitly handle auto occlusions. A second challenge is to improve the robustness by combining both depth and texture edges and by including multiple hypothesis in the edge matching process.

The remainder of the paper is organized as follows. Section II presents the common approaches in 3D modelbased tracking and gives an overview of the proposed method. Section III explains how complex 3D models can be handled efficiently, Section IV details the tracking and pose estimation processes. Some experimental results are given in Section V.

II. CLASSICAL 3D MODEL BASED TRACKING

APPROACHES

Our problem is restricted to model-based tracking, using a 3D model of the target. The purpose is to compute the camera pose which provides the best alignment between edges of the projected model and edges extracted in the image.

Such approaches have proved to be very efficient and various authors have proposed different formulations of the problem (eg, [START_REF] Lowe | Fitting parameterized three-dimensional models to images[END_REF], [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF], [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF]). Although one can find some differences in these various solutions, the main idea is the following. Given a new image, the 3D model of the scene or the target is projected in the image according to the estimated previous camera pose r. Each projected line l i (r) = pr(L i , r) of the model is then sampled, leading to a set of 2D points {x i,j }. Then from each sample point x i,j a 1D search along the normal of the projected edge is performed to find a corresponding point x ′ i,j in the image. In order to compute the new pose, the distances between points x ′ i,j and the projected lines l i are minimized with respect to the following criteria [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] :

∆ = i j ρ(d ⊥ (l i (r), x ′ i,j )) (1)
where d ⊥ (l i (r), x ′ i,j ) is the distance between a point x ′ i,j and the corresponding line l i (r) projected in the image from a pose r. ρ is a robust estimator, which reduces the sensitivity to outliers. This is a non-linear minimization process with respect to the pose parameters r. In [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], the minimization process follows the Virtual Visual Servoing framework, similar to the Gauss-Newton approach.

One of the drawbacks of these methods is that the 3D model is usually made of segments, which implies dealing with simple objects or manually pre-processing the CAD model.The approach presented in this paper considers the direct use of a complete but non necessarily polygonal model, which can be textured or untextured.

Considering complex shape targets leads to forget the notion of 3D sharp edges as in [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF] or in our previous work [START_REF] Petit | Vision-based space autonomous rendezvous : A case study[END_REF] and to deal only with 3D points that belongs indifferently to sharp edges or to the "occlusion boundaries" or rims [START_REF] Koenderink | Solid shape[END_REF]. Two issues have then to be considered: complex model projection and 3D points selection.

The tracking algorithm in our method is structured as follows:

• Projection of the detailed model with respect to the pose r k computed for the previous image I k . To achieve this process we rely on the graphics libraries (openGL) that allows to perform quickly this projection regardless the complexity of the model, thanks to the use of the GPU. • From this projection we generate 3D measurement points X i by extracting edges from the depth and texture discontinuities of the rendered model.

• We then search for corresponding edge points x ′ i in image I k+1 . To allow a better robustness, we propose a multiple hypothesis version of the algorithm.

• The last step is to estimate the pose r k+1 which minimizes the errors d(x i , x ′ i ) between the points extracted from the image x ′ i and the projection of the selected 3D points x i (r) = pr(X i , r), with the following criteria:

∆ = i ρ(d(x i (r), x ′ i )) (2)

III. GENERATION OF 3D MEASUREMENT POINTS

As in [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], [START_REF] Reitmayr | Going out: robust model-based tracking for outdoor augmented reality[END_REF], at each acquired image I k+1 , the model is rendered and projected using the openGL rendering engine (which takes advantage of the computer GPU), with respect to the previous pose r k .

Our goal is to obtain a set of 3D points X i that belong to target rims, edges and visible textures from the rendered depth buffer and textured scene. Our approach follows [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF] and is related to the techniques of silhouette generation of polygonal models described in [START_REF] Isenberg | A developer guide to silhouette algorithms for polygonal models[END_REF].

A. Edge extraction using depth discontinuities

From the depth or Z-buffer, which corresponds to the depth values of the scene according to the camera location at each pixel point (Figure 1(a)), we can determine the discontinuities which suit the geometrical appearance of the scene.

Therefore, we apply a second order differential operator, such as a Laplacian filter, to these computed Z values, resulting in a binary edge map of the visible scene ((Figure 1(b)). In our approach, we have implemented the filtering computations on the GPU through shader programming, resulting in a much lower computational time, due to the parallel structure of the process.

B. Edge extraction using texture discontinuities

In case of highly textured scenes, geometrical edges are not sufficient and ambiguities with texture edges arise, which results in false matching and thus local minima during the pose estimation process. An improvement of our method is then to combine the depth discontinuities with texture discontinuities. The rendered textures of the 3D model are thus processed by a classical Canny edge algorithm and the obtained edges are added to the ones generated from the depth buffer.

C. Generation of 3D measurement points

Given the edge map of the complete scene, the 3D coordinates of the edge points in the scene can be computed thanks to the Z-buffer and the pose used to project the model. As dealing with the whole edge map can be computationally intensive, we can sample it along x and y coordinates of the image in order to keep a reasonable number of these edge measurement points.

Besides, the tracking phase (see Section IV.A) requires the orientation of the edge underlying a measurement point x i . For the texture edges, it is done within the Canny algorithm on the rendered textures. For the depth edges, we compute the Sobel gradients along x and y on a gray-level image of the normal map of the scene. The normal map of the scene associates the [R,G,B] value of each pixel location to the coordinates in the world frame of the normal to the corresponding surface in the scene (see Figure 1(d)). As the rendering phase can suffer from aliasing, the gray-level image of the normal map is filtered using a Gaussian kernel before computing its Sobel gradients. These basic image processing steps, as well as the retrieval of the normal map, are also processed on the GPU by composing vertex and fragment shaders, significantly optimizing computations.

IV. POSE ESTIMATION AND LOW LEVEL TRACKING

A. Tracking from edge measurement points

The measurement points are then processed to track corresponding edges in the image. In a similar manner to [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF], [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], we perform a 1D search along the normal of the underlying edge (Figure 2 and Figure 1(c)) of each x i (r k ). A common approach is to choose the pixel with the maximum gradient as the matching edge point x ′ i in the image.

B. Minimization of a distance to a line

Once correspondences are established, the goal is then to estimate the new pose r k+1 that realigns the measurement points with their matching observed image points x ′ i . This task is addressed by minimizing the errors d(x i (r), x ′ i ). As in [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF], [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], [START_REF] Wuest | Tracking of industrial objects by using cad models[END_REF], our approach considers the distance between the projected 3D line l i (r) underlying the projected measurement point x i (r) (projected from the 3D point X i ) and the selected matching point x ′ i in the image (see Figure 2).

Criteria (2) becomes:

∆ = i ρ(d ⊥ (l i (r), x ′ i ))) (3)
where ρ is a robust estimator used to reject outliers (Tuckey estimator), and d ⊥ (l i (r), x ′ i ) is the distance between the point x ′ i and the corresponding line l i (r). It has to be noted that for sharp edges the 3D point X i (r) is not modified when we modify r. This is no longueur the case for points X i (r) that belong to an occlusion rim. Nevertheless, since the camera motion between two successive images is very small, this approximation has no impact on the efficiency of the approach. The optimization technique is similar to the virtual visual servoing framework described in [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], which relates this optimization problem to a visual servoing issue. A key requirement is to compute the 3D equation of the line l i in the world frame in order to perform its projection during the minimization process. We achieve this by first expressing the polar coordinates (ρ xi , θ xi ) of l i (r k ) in the image, with ρ xi the distance between the projected line l i (r k ) and the center of the image and θ xi the angle between the image frame and the line (Figure 2):

x cos θ xi + y sin θ xi = ρ xi , ∀(x, y) ∈ l i (r k ) (4)
From the model rendering phase, we know θ xi from the gradient computations detailed in Section III.C and we can compute ρ xi , since x i (r k ) ∈ l i (r k ). Then, thanks to the normal map (see Figure 1(d)) the equation of the model surface underlying l i is retrieved, and it is finally straightforward to obtain the 3D equation of l i . l i can thus be projected with respect to the pose r, updating ρ xi and θ xi , and the error d ⊥ (l i (r), x ′ i ), which can be derived as follows:

d ⊥ (l i (r), x ′ i ) = ρ xi -ρ x ′ i . (5)
In the sense of the virtual visual servoing framework [START_REF] Comport | Realtime markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], the robust control law that moves the velocity skew v of the virtual camera in order to minimize d ⊥ (l i (r), x ′ i ) is given by:

v = -λ(DL d ⊥ ) + Dd ⊥ (l i (r), x ′ i ) (6)
where L + d ⊥ is the pseudo inverse of L d ⊥ , the interaction (or Jacobian) matrix of the feature d ⊥ (l i (r), x ′ i ), which links v to the velocity of the features in the image (see [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF] for its complete derivation, in the case of a distance to a line). λ is a proportional gain that ensures an exponential decrease of the error and D is a weighting matrix associated to the Tuckey robust estimator. Finally, the new pose r k+1 , represented by its homogeneous matrix c k+1 M o , can be computed using the exponential map [START_REF] Ma | An invitation to 3-D vision[END_REF]:

c k+1 M o = c k+1 M c k c k M o = e -vc k M o (7)

C. Multiple hypothesis solution

In order to improve the robustness of the pose estimation and to avoid problems due to ambiguities between edges, it is possible to consider and register different hypothesis corresponding to potential edges. They correspond to different local extrema of the gradient along the scan line. As in [START_REF] Vacchetti | Combining edge and texture information for real-time accurate 3d camera tracking[END_REF], [START_REF] Teulière | Using multiple hypothesis in model-based tracking[END_REF], we choose the hypothesis which has the closest distance to the projected 3D line l i during the minimization process. The cost function becomes :

∆ = i ρ(min j d ⊥ (l i (r), x ′ i,j )) (8)
where points x ′ i,j are the selected candidates for each measurement point x i .

V. EXPERIMENTAL RESULTS

A. Implementation

The rendering process of the 3D polygonal and textured model relies on OGRE (Object-oriented Graphics Rendering Engine), which is a scene-oriented, flexible 3D rendering engine [START_REF]Ogre3d[END_REF]. The library avoids to explicitly use the underlying system libraries (Direct3D or OpenGL). As presented in Section III, we have considered shader programming for some image processing steps during the rendering and edge generation phases. This is done using OpenGL Shading Language (GLSL), supported by OGRE, which enables classic shading techniques such as composition of successive shaders. The remainder of the algorithm has been implemented thanks to the ViSP library [START_REF] Marchand | ViSP for visual servoing: a generic software platform with a wide class of robot control skills[END_REF]. Regarding hardware, an NVIDIA NVS 3100M graphic card has been used, along with a 2.8GHz Intel Core i7 CPU.

For tests procedures, we have performed experiments on both real and synthetic image sequences. They consist in evaluations of the algorithm described in the previous sections, for the texture and untextured cases and for the single and multiple hypothesis solutions.

B. Tests on real images

The first example deals with the tracking of the Soyuz TMA-12 spacecraft during its rendezvous phase with the International Space Station (ISS). This manned flight is intended to transport crew members of the ISS. With its three different modules, the main body of the spacecraft is of complex shape, with curved and fuzzy edges, but the solar arrays tend to facilitate the tracking. Here the tracking procedure consists in only using the depth discontinuities in the rendered scene to generate the visible and prominent edges (see Figure 1(d)), and the single hypothesis solution has shown to be sufficient for this sequence. Despite the uncertainties over the camera internal parameters, the 3D model consistency, the cluttered background and the low quality of the original video, the tracking is successfully achieved (see Figures 5(a)-5(d) and provided video).

The second example concerns the Atlantis Space shuttle performing a pitch maneuver for its rendezvous with the ISS, for the STS-135 mission. An untextured 3D model of the spacecraft has been processed for the tracking, together with the multiple hypothesis registration process and a Kalman filter with a constant velocity model on the pose parameters. This target also presents a complex shape, with cylindrical and curved parts, such as the fuselage or the engines.

C. Tests on synthetic images

The evaluation has been performed using a realistic raytracing simulator developed by Astrium for space environments, and which enables to simulate rendezvous or approaches with spacecrafts, satellites or space debris. We focus here on the case of the Spot satellite family. Spot are earth observation satellites whose orbit is approximately polar, circular, sun-synchronous, at an altitude of around 830 kilometers, and with an inclination of 98.7 degrees (see Figure 3). For space debris removal concerns, we consider an arbitrary rotation for the target attitude and a chaser spacecraft is supposed to be located on a similar orbit, with a slightly different eccentricity in order to make the chaser fly around the target (Figure 4). The chaser is also equipped with a camera filming the target and a spot light to lighten the target, especially during sun eclipses. As it can be observed on Figure 6, the tracking presents good performances throughout the whole sequence. In order to quantify the different results, we separately evaluate the accuracy of rotation and translation components of an estimated camera pose r with respects to the true pose r * , as we can be provided with Ground Truth. The results for the single (SH) and multiple hypothesis (MH) approaches, relying on both depth and texture edges, and with or without Kalman filtering are represented on Figure 7. They show that when using multiple hypothesis along with the Kalman filter, translation and rotation errors can be kept small, especially when the target is far from the chaser with low luminosity (see Figure 6(d)), and when the solar panels flip in the image (see Figure 6(c)), leading to some local minima for the single hypothesis solution.

D. Computational costs

Thanks to the implementation of several image processing phases on the GPU using shaders, the execution time for these phases has been considerably reduced. With this improvement, the whole algorithm can be processed at a 17 fps framerate for the Atlantis sequence, at 15 fps for the Soyuz sequence, and at 12 fps for the Spot synthetic sequence when relying on depth edges. The multiple hypothesis solution, since we are using 3 candidates per measurement point, does not affect much computations. Including texture information makes the process costlier, since more points are considered, with a 7 fps framerate for the Spot sequence.

VI. CONCLUSION

This paper presents a generic tracking and pose estimation method suited for complex, textured or untextured objects in deep space environments, for space rendezvous and space debris removal purposes. It relies on the generation of visible and salient edges from the 3D complete polygonal model, projected and rendered using a rendering engine. Information from both geometrical and texture discontinuities are used. This technique avoids the heavy processing of 3D lines out of a 3D line model, which is problematic when dealing with curved forms and computationally costly. For pose estimation, the method is similar to the classical approaches as it consists in the realignment of the generated model edges with edges detected in the image. From the tests carried out on real images, our approach qualitatively presents satisfactory results. Thanks to the realistic image simulator, performances can be measured, showing the relevance of the approach. The implementation proves to be computationally efficient, especially through the processing of some phases on the GPU. As ambiguities between edges can occur in detailed scenes, leading to local minima and unstable tracking when using a single registration technique, considering multiple hypothesis improves the robustness of our approach. Further works would aim at implementing a detection strategy in order to initialize the frame-by-frame tracking. It would also rely on the 3D model of the target.

Fig. 1 :

 1 Fig.1: On (a) is represented the z-buffer of the rendered 3D model using Ogre3D, from which the edge map is computed (b).This edge map is then sampled to extract measurement points, reprojected on the current image and from them a 1D search along the edge normal is performed to find a matching edge point in the acquired image (c). (d) shows the normal map of the scene.

Fig. 2 :

 2 Fig. 2: Moving edge principle: from the initial pose r k , 1D search along the projected contour underlying the measurement point. Distance of a point x ′ i to a corresponding line l i (r) within the minimization process.

  Figures 5(e)-5(h) shows the tracking properly performed over the sequence, with a robustness to some illumination changes (see provided video). The multiple hypothesis solution and the Kalman filter are necessary to handle the shuttle flip in the image (around Figure 5(g)). The estimated camera pose parameters are represented on Figure 5(i).

Fig. 3 :

 3 Fig. 3: Spot sun-synchronous orbit.

Fig. 4 :

 4 Fig. 4: Chaser and target (Spot) orbits in the Earth reference frame.

Fig. 5 :

 5 Fig. 5: Tracking relying on depth edges for the Soyuz ((a)-(d)) and Atlantis sequences ((e)-(h)). Pose parameters for the Atlantis sequence are represented on (i).

Fig. 6 :Fig. 7 :

 67 Fig. 6: Tracking relying on depth and texture edges, with multiple hypothesis and Kalman filtering. The tracking is properly performed throughout the sequence.