Thi Thanh 
  
Hai Tran 
email: htran@irisa.fr
  
Eric Marchand 
email: marchand@irisa.fr.
  
Real-time keypoints matching: application to visual servoing

Many computer vision problems such as recognition, image retrieval, and tracking require matching two images. Currently, ones try to find as reliable as possible matching techniques with a very little constraint of computational time. In this paper, we are interested in applying image matching technique into robotic problems such as Augmented Reality, Visual Servoing in which the computational time is a critical element. We propose in this paper a real time keypoint based matching method. The novelties of this method include a fast corner detector, a compact corner descriptor based on Principal Component Analysis (PCA) technique and an efficient matching with help of Approximate Nearest Neighbor (ANN) technique. We show that the method gives a very satisfying result on accuracy as well as the computational time. The matching algorithm is applied to command a robot in a visual servoing application. It works at 10-14Hz and is well robust to variations in 3D viewpoint and illumination.

I. INTRODUCTION

When dealing with vision-based robot control, real-time tracking is a fundamental issue. This problem received much interest in the literature and various approach can be considered: tracking based on point of interest [START_REF] Shi | Good features to track[END_REF], 2D features [START_REF] Hager | The XVision system: A general-purpose substrate for portable real-time vision applications[END_REF], [START_REF] Boukir | A local method for contour matching and its parallel implementation[END_REF], 2D templates [START_REF] Hager | Efficient region tracking with parametric models of geometry and illumination[END_REF], [START_REF] Benhimane | Homography-based 2d visual tracking and servoing[END_REF], 3D model [START_REF] Drummond | Real-time visual tracking of complex structures[END_REF], [START_REF] Comport | Robust model-based tracking for robot vision[END_REF], [START_REF] Comport | Real-time markerless tracking for augmented reality: the virtual visual servoing framework[END_REF], etc. A presentation of real-time tracking algorithms for visual servoing purposes is given in [START_REF] Marchand | Feature tracking for visual servoing purposes[END_REF]. Although usually efficient, these methods failed to address two important issues: initialization and failure recovery (which in fact is a re-initialization problem). Addressing all these issues (initialization, tracking, failure recovery) within the same approach can be achieved considering tracking as a recognition or image matching issue.

Image matching consists to automatically establish the correspondence between primitives extracted from two images. First solutions for image matching have been suggested already in the late fifties [START_REF] Hobrough | Automatic stereo plotting[END_REF]. Since then a steady increase in the interest for image matching has occurred. But matching still remains one of the most challenging tasks in the computer vision field. The reason comes not only from the high implicit information contained in the image to be discriminally represented, but also from noise during image acquisition, changes of camera viewpoints, illumination, occlusion, etc. Recently, some keypoints based matching methods obtained impressive results in object recognition/classification [START_REF] Mikolajczyck | Indexing based on scale invariant interest point[END_REF], [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF]. The high precision and the robustness of these methods to some transformations such as scale change, illumination change, rotation are due to a very careful design of keypoint detector as well as keypoint descriptor. Consequently, they are usually time-consuming.

Considering robot control, not only the accuracy is required but also the computation cost. In order to address these issues, a real-time, robust image matching method is proposed. The main idea is to explore advantages from existing matching techniques, adapt them so that a good trade-off between the computational time and the precision can be achieved. In addition, we shift some of computational burdens into offline training. This allows our method meets well requirements of visual servoing task.

The contributions of this paper are found in each step of the matching algorithm:

• Keypoint detection: We propose a criterion which eliminates quickly edge points or points in uniform regions from corner points in an image. This is done from the full-resolution image. • Keypoint description: Each keypoint is described by a compact descriptor (e.g. 20-elements vector). This speeds up significantly the matching. The idea is to use PCA technique to reduce dimensionality of feature space. Eigenspace is pre-built in training phase, so does not take time in running phase. • Keypoint matching: Using ANN technique for point matching is efficient in computational time as well as precision. For each reference image, keypoints, descriptors, and corresponding kd-tree are precomputed. At running time, we detect keypoints and describe them from only current image. This reduces a half of time against some state of the art algorithms. Finally, to validate our approach, the matching/tracking algorithm is used to performed positioning task using visual servoing [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF].

The organization of the paper is as follows: Section II explains the keypoint detection and their description. Section III describes the matching algorithm. In section IV, experimental results of matching on servoing task will be analyzed. We conclude and give some ideas to improve the actual method in order to obtain higher matching performance in section V.

II. KEYPOINTS DETECTION AND REPRESENTATION

A. Keypoints detection

Keypoint detection is the first step in a process of points matching. By definition, keypoints are points which contain more information than other points in the image. They allow a more compact representation of the image and help to recognize better the scene than all rough pixels.

Fast keypoint detection algorithm have been recently proposed [START_REF] Rosten | Fusing points and lines for high performance tracking[END_REF], [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF]. Following this way, in our work, a point is identified as keypoint where the image signal is significantly different from those of two opposite neighbors. Formally, Given an image I. A point x is not considered as a keypoint if there exists two opposite points p and q such that:

|I(x) -I(p)| ≤ d |I(x) -I(q)| ≤ d ( 1 
)
where d is a sufficient small threshold. p and q are two points on a circle of 16 pixels around the candidate keypoint x, as illustrated in Figure 1.

The criterion (1) will eliminate quickly edge and region responses. To avoid detecting keypoints on skewed edges, we do the test also on two skewed opposite points q + 1, q -1. The test is started from one point on the circle and stopped when it returns true. In this case x is not a keypoint.

Once edge and region responses are eliminated, we reject remaining multiple adjacent responses by keeping only points which have extremal value of Laplacian. The Laplacian is approximated in a very simple manner:

L(x) = ∀(p,q) (I(p) + I(q) -I(x)) (2) 
where p, q are two right opposite points on the 16-circle associated to the considered point x.

Obviously, our detection will be realized more faster than a multi-scales or scale-space approach because only the original image is considered. This makes the method not invariant to scale. However, as we can see in the following, in the context of visual servoing where scale does not change strongly, detected keypoints from image still remain quite repeatable.

B. Invariance to image orientation

By assigning a consistent orientation to each keypoint based on local image properties, the keypoint descriptor can be represented relative to this orientation and therefore achieve invariance to image orientation.

We propose to use a principle similar to the one presented in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] for orientation assignment. Nevertheless, since keypoints are not detected in scale-space, only a histogram of gradient orientation is computed for all points within a region of size 7x7 centered at the keypoint. The orientation histogram has 36 bins covering the 360 degree range of orientation. Each sample added to the histogram is weighted by its gradient magnitude and by a Gaussian-weighted circular window with σ = 3 (radius of 16-circle). The most significant peak in the histogram corresponds to the canonical orientation of local gradient.

The assignment of orientation in this way costs lightly more expensive than the one proposed in [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF] where an orientation which maximizes gradient magnitude is computed. However, the obtained orientations are more stable to noise. 

C. Computation of eigenspace

Considering a set of oriented keypoints, the next step is to compute a descriptor for the local region around a keypoint that is highly distinctive yet is as invariant as possible to variations, such as change in illumination or 3D viewpoint. Obviously, we can extract an intensity region around each keypoint and match these using a correlation measure. However the intensity correlation is too sensitive to noise and the search in such high dimensional space is very time consuming. We propose to use gradient magnitude computed from normalized image which allows an invariance to illumination changes. Furthermore, to reduce high dimensions, Principal Component Analysis (PCA) technique is considered.

PCA is a standard technique which enables to linearlyproject high-dimensional samples onto a low-dimensional feature space, that is called eigenspace. Such method has been shown to be very well-suited to representing keypoint patches [START_REF] Ke | Pca-sift: A more distinctive representation for local image descriptor[END_REF].

The building of the eigenspace consists in following steps:

• Extract patches P 1 , P 2 , ..., P M (training patches) in the canonical orientation at each keypoint detected from training images. Each patch is centered and of the same size N × N (with N = 17). If the number of patches is not large enough, we create more patches by using synthesizing technique [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF].

• Represent each patch P i by a vector that is the gradient vector Γ i of (N -2) 2 elements (points at boundary are not taken into account) (see Figure 3). Gradient magnitude is determined by:

G(x) = ∇I 2 x (x) + ∇I 2 y (x) (3) 
where ∇I x (x) (resp. ∇I y (x)) is the image gradient along the x axe (resp. y axe). Fig. 3. Patches are extracted and each is described by a vector of gradient magnitudes.

• Normalize the gradient vector ∀i = 1 . . . M : 

Ω i = Γ i -Ψ with Ψ = 1 M M i=j Γ j • Compute the covariance matrix C: C = 1 M M n=1 Ω n Ω n = AA (4) 
C is a (N -2) 2 × (N -2) 2 matrix. A = [Ω 1 . . . Ω M ] is a (N -2) 2 × M matrix. • Compute

D. Local region description

Once an eigenspace is built, we have a new basis (v 1 , v 2 , ..., v K ) to describe patches. Computing keypoint descriptor in the eigenspace follows these steps:

• Step 1: subtract gradient magnitude vector Γ by the average vector

Ψ : Ω = Γ -Ψ • Step 2: project Ω onto eigenspace: Ω = K i=1 w i v i with w i = v i Ω • Step 3: represent Ω as a K-elements vector: Ω = (w 1 . . . w K )
Each patch is represented as a K-elements vector Ω which is considerably smaller than the original vector Γ (eg. 20 against 39×39=1521 with patch size N = 41). Obviously, this representation is more compact than the original one and thus allows a faster search using nearest neighbors algorithm. In addition, it tolerates intra-class variations and recognizes better the extra-class variation. Figure 4 illustrates how a patch is described in eigenspace. At left, we have an input is a gradient magnitude map. At right, we show 4 eigenpatches corresponding to 4 first eigenvectors in the basis. The input vector is a linear combination of these eigenvectors. The multiplicative coefficients w i form a vector descriptor for the patch in eigenspace.

III. KEYPOINTS MATCHING

To match points in two images, keypoints are detected (section II-A) and projected (section II-D) onto pre-built eigenspace (section II-C). Basically, matching keypoints now consists in searching for the nearest neighbor. Nevertheless, for efficiency issue specific algorithms have to be considered.

A. Approximate nearest neighbor based point matching

In the nearest neighbor problem a set of data points coded as by descriptor in K-dimensional space are given. These points are preprocessed into an appropriate structure, so that given any query point Ω, the nearest points to Ω can be reported as quickly as possible. Although nearest neighbor searching can be performed efficiently in low-dimension spaces, search time grows exponentially as a function of dimension [START_REF] Indyk | Nearest Neighbors in high dimensional spaces[END_REF].

To efficiently match two sets of points, we use approximate nearest neighbor technique proposed by Mount [START_REF] Arya | An optimal algorithm for approximate nearest neighbor searching[END_REF], [START_REF] Mount | ANN programming Manual[END_REF]. The idea is to organize feature points into a kd-tree structure and compute the nearest neighbors approximately. The similarity between two feature points in eigenspace is measured by:

|| Ω -Ω k || = K i=1 1 e i (w i -w k i ) 2 (5) 
Computing the approximate nearest neighbors allows to achieve significantly faster running times although it can undergo some matching errors. We overcome this error by using second-closest neighbor criterion, as proposed in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Concretely, a match is considered as a correct match when it has the closest neighbor significantly closer than the closest incorrect match. All matches in which the second-closest ratio is greater than some threshold r will be rejected.

B. Outliers rejection using RANSAC

Apart from using of second-closest criterion, we add a more robust criterion to reject outliers matching. Specifically, once keypoints from two images have been matched, a robust estimation of the multi-view geometry that links the two images is computed using RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with application to image analysis and automated cartography[END_REF].

More precisely, an homography a H b links the projection of matched point a x i and b x i : ∀i, a x i = a H b b x i (for planar scenes) where a x i and b x i are points 2D homogeneous coordinates and a H b is a 3 × 3 matrix. At each iteration of RANSAC, the homography a H b is estimated using the method presented in [START_REF] Malis | 2 1/2 D visual servoing with respect to unknown objects through a new estimation scheme of camera displacement[END_REF] which requires at least 4 couples of points for planar scene or 8 for non-planar scene. Although the computed homography is not used in the current version of our system, this method allows to reject efficiently the remaining outliers.

IV. EXPERIMENTAL RESULTS

A. Context of experiments

The aim of the experiments is to validate if the proposed matching algorithm is sufficiently fast and reliable for visionbased control applications. The considered task is to control the end-effector of a robot to achieve a positioning task. This is a classical problem in robotic (eg. grasping task). It consists in 2 steps. In the first learning step, the camera is moved to its desired position. The desired image I d of the target corresponding to this position is acquired. We then detect keypoints from this image, project them onto the prebuilt eigenspace and organize them into kd-tree structure. As the eigenspace is pre-built at learning phase, this step takes only around tens millisecond, depending on if the object is complex or not. Note that we do not need to build eigenspace in this phase because the nature eigenspace does not influence strongly the matching result (as well indicated in [START_REF] Ke | Pca-sift: A more distinctive representation for local image descriptor[END_REF]).

After some unknown displacements of the camera or the object, the robot is controlled so that that the current image features reach their desired position in the image. This is done by detecting and describing keypoints from the current image then applying matching algorithm to search correspondences. The error of position of matched points are used to command 6-d.o.f of the robot. The positioning task ends when the error is smaller than a given threshold. At convergence, the camera is located at the same position wrt to the object in learning phase.

These processes have been tested at IRISA-INRIA Rennes on a gantry robot and have been implemented using the ViSP package [START_REF] Marchand | ViSP for visual servoing: a generic software platform with a wide class of robot control skills[END_REF].

B. Visual servoing

We consider the generic positioning task. The goal of visual servoing is essentially to minimize the error ∆ = ss * between a set of visual features s, that depends of the actual camera location, and a set of desired visual features s * . The control law that performs ∆ minimization is usually handled using a least square approach [START_REF] Hutchinson | A tutorial on visual servo control[END_REF].

In our case, s * describes the set of points extracted from the desired image I d using the method presented in Section II-A. Assuming that n points have been detected in I d , we then have s * = (x * 1 , y * 1 , . . . , x * n , y * n ) . s contains information about the matched points in the current image I. Obviously the number m of matched point is such that m ≤ n. s is then defined as s * = (x 1 , y 1 , . . . , x n , y n ) with (x i , y i ) = (0, 0) if point (x * i , y * i ) has not been matched. Since non matched points must not be considered in the control law we also defined a diagonal n × n matrix D. D = diag(. . . , ω i , . . .) with ω i = 0 if point (x * i , y * i ) has not been matched, and 1 otherwise. The control law is given by [START_REF] Comport | Statistically robust 2d visual servoing[END_REF]:

v = -λ(DL) + D(s -s * ). ( 6 
)
where v is the computed camera velocity and L s is the interaction matrix related to the point [START_REF] Espiau | A new approach to visual servoing in robotics[END_REF].

C. Results

Two experiments are reported, the former (named "marvels experiment") consider a positioning task wrt to a planar scene with textured posters, while the latter (named "castle experiment") consider a positioning task wrt a complex 3D object. Figures 5 and7 shows the reference and initial image of the positioning tasks along with match points. As mentioned, one of the interest of such tracking by matching approach is that initialization (ie, matching between s and s * ) which is usually a tough problem in visual servoing is, here, a trivial issue. Partial or total occlusion is also easily handled (only the number of matched points decreases).

Figure 6 (resp. Figure 8) show the camera velocity (Figure 6ab and8ab) and the norm of the error ss * which decreases as expected. Let us note that this is rough results. The extracted position of the matched points are not filtered which may introduce noise in vector s and then in the computed camera velocity. Kalman filter may be easily considered to cope with this issue.

Table I gives some informations about the computational time at each operation in the matching algorithm. In general the matching works at 10Hz on a Pentium IV, 2.6GHz. When these images are quite similar (robot near to desired position), the speed increases to 14Hz. The last experiment (Figure 9) demonstrates the good behavior of our system when partial or complete occlusions occur (see also the video). When the occlusion is complete, no match are found and the robot stops. When occlusion ends, new matches are found and visual servoing continue. In this paper, a method for tracking by matching has been proposed. Thanks to the definition of a very simple but efficient keypoint detector, efficient keypoint description and matching, this method is showed to be very efficient for realtime application like visual servoing. The matching algorithm works at 10-14Hz and is well robust to 3D viewpoint as well as illumination changes. Efficient has a price, the number of points detected and matched is smaller than in some state of the art literature methods, but it is enough for applications such as visual servoing or pose estimation.

In comparison with some existing matching methods such as SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], PCA-SIFT [START_REF] Ke | Pca-sift: A more distinctive representation for local image descriptor[END_REF], [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF], in term of computational time, our method is significantly faster than SIFT or PCA- SIFT thanks to the very fast keypoint detector. Compared to method proposed by Lepetit et al. [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF], our method are lightly more time consumming at step of computing canonical orientations. A quantitative comparision of recognition rate betweeen methods should be performed. The performance of the tracking by matching algorithm can be improved at some following directions. Keypoints should be detected and matched in scale space in order to give reliable result when scale are different. Specifically, training images (desired image) can be processed at several scales. At runtime, the current image will be matched with all smoothed image and the best match will be taken into account. Multi-scales approach saves times better than scalespace approach because all computations for desired image 

1 qFig. 1 .

 11 Fig. 1. Tests for a keypoint. Two opposite neighbors p and q of candidate point x are on the 16-circle.

Fig. 2 .

 2 Fig.2. Keypoints points detected from a building image. Each keypoint is assigned one canonical orientation. The descriptor is built using the local patch (blue squares) around the keypoint, in the canonical orientation.

Figure 2

 2 Figure 2 shows keypoints detected from an image of buildings. Each keypoint is assigned an orientation, depicted in the Figure by a red arrow. We can see that almost keypoints represent corners of buildings in the scene. They are quite similar but the descriptors built in respective canonical orientations are discriminant.

Fig. 4 .

 4 Fig. 4. Vector of gradient magnitudes is a linear combination of eigenvectors.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Initial (top) and reference (bottom) image for the marvel experiment. Green lines link two matched point.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Initial (top) and reference (bottom) image for the castle experiment. Green lines link two matched point.

Fig. 9 .

 9 Fig. 9. Six images of the marvel sequence. Note that multiple occlusions are done (partial or complete). When the occlusion is complete, no match are found and the robot stops. When occlusion ends, new matches are found and visual servoing continue.

  the eigenvalues e i of C and the corresponding eigenvectors v i by applying Singular Value Decomposition technique (SVD) on the covariance matrix C.

• Finally, keep only K eigenvectors corresponding to K largest eigenvalues. These vectors create a new basis of eigenspace of K dimensions. K = 20 is chosen experimentally which is small enough to allow a good discriminant descriptor of keypoints.

TABLE I COMPUTATIONAL

 I TIME FOR IMAGE MATCHING.

http://www.irisa.fr/lagadic