Frédéric Sur

Nicolas Noury

Marie-Odile Berger

Image point correspondences and repeated patterns

Keywords: Point correspondence problem, repeated patterns, perceptual aliasing, double nail illusion, a-contrario model, generalized RANSAC, SIFT, ASIFT Mise en correspondance de points d'intérêt, motifs répétés, aliasing perceptuel, illusion des deux ongles, modèle a-contrario, RANSAC généralisé, SIFT, ASIFT

Matching or tracking interest points between several views is one of the keystones of many computer vision applications. The procedure generally consists in several independent steps, basically interest point extraction, then interest point matching by keeping only the "best correspondences" with respect to similarity between some local descriptors, and final correspondence pruning to keep those that are consistent with a realistic camera motion (here, consistent with epipolar constraints or homography transformation.) Each step in itself is a delicate task which may endanger the whole process. In particular, repeated patterns give lots of false correspondences in descriptor-based matching which are hardly, if ever, recovered by the final pruning step. We discuss here the specific difficulties raised by repeated patterns in the point correspondence problem. Then we show to what extent it is possible to address these difficulties. Starting from a statistical model by Moisan and Stival, we propose a onestage approach for matching interest points based on simultaneous descriptor similarity and geometric constraint. The resulting algorithm has adaptive matching thresholds and is able to pick up point correspondences beyond the nearest neighbour. We also discuss Generalized RANSAC and we show how to improve Morel and Yu's ASIFT, an effective point matching algorithm to make it more robust to the presence of repeated patterns.

Introduction

A large part of computer vision literature is based on the matching of interest points between several views. "Matching" means that one has to detect interest points across several images that correspond to the same actual 3D point. This is often achieved by taking into account local descriptors, i.e. an encoding of the grey values from the vicinity of an interest point. While only a rough matching is needed in e.g. the image retrieval context (it is accepted that some correspondences are not correct), photography stitching [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF] and most multiple views structure and motion applications [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF] (see e.g Snavely et al.'s Phototourism and Bundler [START_REF] Snavely | Modeling the world from internet photo collections[END_REF]) call for an accurate matching step.

In this report we focus on the problem of correspondence finding between two views. Let us consider two views from the same 3D scene taken by a moving camera. A popular way to tackle this problem consists in the following steps:

1. In both views, extract interest points along with a descriptor of the local photometry.

2. Match them by taking into account some (dis-)similarity measure over the descriptors.

3. Prune the correspondences by finding out the most consistent set with respect to the geometry imposed by a realistic camera motion.

4. Estimate the camera motion between the two views. Then make the set of correspondences "denser" by relaxing the matching step 2 and taking into account this estimation. (This step is often referred to as "guided matching".)

5. Estimate the refined camera motion based on this final set of correspondences.

Interest point extraction in step 1 can be achieved by Harris-Stephens corner detector [START_REF] Harris | A combined corner and edge detector[END_REF], extrema of the Laplacian or of the determinant of Hessian [START_REF] Lindeberg | Feature detection with automatic scale selection[END_REF] in scale-space, etc. Following the seminal work by Mohr and Schmid [START_REF] Schmid | Local greyvalue invariants for image retrieval[END_REF] a large amount of methods have emerged to attach to each interest point a local photometric descriptor, (quasi-) invariant to contrast change and to a large class of deformations. One of the most successful algorithms is probably Lowe's SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], which is based on this idea. See the reviews [START_REF] Aanaes | Interesting interest points[END_REF][START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF][START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF][START_REF] Moreels | Evaluation of features detectors and descriptors based on 3D objects[END_REF].

Step 2 is certainly one of the very shortcomings of the method. It is indeed difficult to endow the space of descriptors with a handy metric. Putting a threshold over the Euclidean distance between descriptors to define correspondences simply does not work. A popular way [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to define a set of correspondences is instead to keep the nearest neighbour, and optionally impose that the ratio of the distances between the nearest and the second nearest neighbour is below some threshold (obviously smaller than 1.) The nearest neighbour is indeed all the more relevant as the ratio is low. It works quite well even using the Euclidean distance. However, since most descriptors (and especially SIFT) are made of gradient orientation histograms, some authors propose to change the Euclidean distance to some distance that is somewhat more adapted to histograms. We can mention (by increasing computational complexity) χ 2 distance, Ling and Okada's diffusion distance [START_REF] Ling | Diffusion distance for histogram comparison[END_REF], Earth Mover's Distance (EMD, see the seminal work by Rubner et al. [START_REF] Rubner | The Earth Mover's Distance as a metric for image retrieval[END_REF], Rabin et al. [START_REF] Rabin | A statistical approach to the matching of local features[END_REF], or Ling and Okada [START_REF] Ling | An efficient Earth Mover's Distance algorithm for robust histogram comparison[END_REF].) For the sake of historical completeness, let us also mention correlation methods (e.g. [START_REF] Zhang | A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry[END_REF] and more recently [START_REF] Tordoff | Guided-MLESAC: faster image transform estimation by using matching priors[END_REF]), that do not need descriptors to build point correspondences. However, RR n°7693 these latter methods suffer from the lack of invariance and are preferentially kept for small baseline stereovision.

Once a set of tentative correspondences has been defined from both images, step 3 aims at selecting a subset made of correspondences that are consistent with the underlying geometric model. In the pinhole camera model, the so-called epipolar geometry is encoded in the fundamental matrix (or the essential matrix if intrinsic parameters are known) [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF], except if the camera motion is restricted to a rotation around its optical center, or if the 3D points are coplanar, in which case a homography (a planar projective transformation) maps interest points from one image to the other one. Since correspondences are spoilt by outliers (that is, correspondences between parts of images that look alike, but do not correspond to the same actual 3D object), robust statistics are called for, such as e.g. LMedS or M-estimators [START_REF] Torr | The development and comparison of robust methods for estimating the fundamental matrix[END_REF][START_REF] Zhang | Determining the epipolar geometry and its uncertainty: a review[END_REF]. The most popular choice is certainly RANSAC [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] and methods derived from it (MSAC and MLESAC [START_REF] Torr | MLESAC: A new robust estimator with application to estimating image geometry[END_REF], MAPSAC [START_REF] Torr | Bayesian model estimation and selection for epipolar geometry and generic manifold fitting[END_REF], PROSAC [START_REF] Chum | Matching with PROSAC -progressive sample consensus[END_REF] to only cite a few.) The RANSAC paradigm deserves some attention in this discussion. RANSAC is an iterative procedure, that is based on two steps: a) draw a minimal sample to estimate the model, and b) build a subset of correspondences that is consistent with this model. This latter set is called consensus set. In the end, the "most consistent" set is kept. Consistency is measured by basically counting the cardinality of the consensus set (original RANSAC) or by some more sophisticated fitness measure (MSAC, MLESAC.) When running RANSAC-like algorithms, the user needs to tune several parameters by hand, which may be quite tricky. Recently, Moisan and Stival [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] have proposed a new RANSAC-like procedure to estimate the two-view geometry. Their algorithm is based on a statistical measure which does not need parameter tuning and is shown to behave as well as state-of-the-art methods with large rates of outliers. We will come back to this in section 4.

Once a consensus set has been found, step 4 consists in estimating the geometry between the two views, by computing the fundamental matrix or homography. Then an optional stage follows: new correspondences are found by searching them along the epipolar lines. This step gives a set of correspondences which is hopefully distributed across both images in a "denser" fashion. This should allow a more reliable re-estimation of the geometry, based on this final set of correspondences. This is the goal of step 5 where many methods have been proposed [START_REF] Faugeras | The Geometry of Multiple Images[END_REF][START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Zhang | Determining the epipolar geometry and its uncertainty: a review[END_REF]. We do not elaborate on these steps in the present paper. However, whatever the ingenuity of steps 4 and 5, the set of corresponding points from steps 1-3 has to be good enough so that camera motion can be reliably estimated.

The reader can easily see that putting all these steps together is practically a difficult task. It indeed involves setting a lot of parameters, and a wrong choice for one of them may endanger the whole process.

Besides, repeated patterns bring specific problems. Repeated patterns are common in man-made environments (just think of windows on a façade or manufactured goods as cars in outdoor environments.) If the matching step is just based on the nearest neighbour conditioned by the distance ratio between the nearest and second nearest neighbour (as in standard SIFT matching, see step 2), it is obvious that repeated patterns are likely to be discarded at this early stage (since the ratio would be always close to 1.) Moreover, there is no insurance that the correspondence that is still kept is correct, as illustrated on figure 1. Although some methods are better than other towards this point (for example [START_REF] Rabin | A statistical approach to the matching of local features[END_REF]) it is still very difficult to match repeated patterns in a reliable fashion. This is a crucial issue in many applications, as e.g. in structure from motion where it yields "catastrophic failures" in the reconstruction of the scene [START_REF] Roberts | Structure from motion for scenes with large duplicate structures[END_REF].

Figure 1: Loria image pair. SIFT interest points are marked with a cross, the green segment represents the apparent motion with the matching feature in the other image. On the left, the standard SIFT matching algorithm (NN-T in text) fails at identifying reliable matching interest points on the carpet. Thus, no subsequent pruning algorithm will succeed in drawing out the true correspondences. On the right, the proposed a-contrario approach using both photometric and geometric constraints (here a homography) finds correct correspondences in spite of the large number of repeated patterns.

The first contribution of this report is to discuss the specific problems raised by repeated patterns in the point correspondence problem (section 2.) Section 3 presents related work. The aim of the rest of the report is to illustrate how and to what extent the problems induced by repeated patterns can be overcome. Section 4 proposes a statistical a-contrario framework to replace steps 2 and 3 (and partly 4) to select correspondences beyond the nearest neighbours. The whole method is summarized in section 5 where the algorithmic choices are motivated. Section 6 is about experimental assessment and proof of concept. In particular, we also discuss a Generalized RANSAC which is also able to pick up non-nearest neighbour correspondences but necessitates tuning several parameters. We explain in section 7 how ASIFT [START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF], a very effective point matching algorithm robust to extreme viewpoint change, can be made more robust to repeated patterns. For the sake of completeness, the proofs of some propositions are given in appendix.

Repeated patterns: the curse of perceptual aliasing

As mentioned in the introduction, deciding correspondences between interest points based on a nearest neighbour criterion on descriptors is not sound when repeated patterns are present. The problem is that patches around interest points yield descriptors that are as much invariant as possible to viewpoint changes. Thus numerous descriptors from repetitive structures are very similar, making it impossible to infer correct correspondences only based on the conveyed information.

Let us remark that this phenomenon is strongly related to the so-called perceptual aliasing from the control of systems theory. This term was coined by Whitehead and Ballard [START_REF] Whitehead | Learning to perceive and act by trial and error[END_REF] to describe the fact that a robot may possibly not distinguish between RR n°7693 different states of the world due to the limited accuracy of its sensors. Let us quote Whitehead and Ballard [START_REF] Whitehead | Learning to perceive and act by trial and error[END_REF]: "Perceptual aliasing can be a blessing or a curse. If the mapping between the external world and the internal representation is chosen correctly, a potentially huge state space (with all its irrelevant variation) collapses into a small simple internal state space. Ideally, this projection will group world situations that are the same with respect to the task at hand. But, if the mapping is not chosen carefully, inconsistencies will arise and prevent the system from learning an adequate control strategy." In the point correspondence framework, representing a world state (here: an actual 3D point) with a single internal state (here an invariant descriptor) is a desirable feature so that point matching under large viewpoint change is easily tractable. However, the presence of repeated structures makes different 3D points be internally represented by a set of very similar descriptors. It is then very hard, and sometimes impossible, to infer correspondences consistent with the true image registration from these confused representations.

For example, figure 2 shows point correspondences from which it is clearly impossible to get a consistent set. The left image in figure 1 is another example. Remark that we could increase the scale of the patches which yield the almost identical descriptors, until they are distinguishable from one another, as in e.g. [START_REF] Vedaldi | Local features, all grown up[END_REF]. However, this strategy would deteriorate the robustness to occlusion or clutter, as well as the invariance to viewpoint change, since this is based on the hypothesis that a similarity or affine transformation is a local approximation of a projective transformation. Most of the time it is still possible to get a consistent set of correspondences from an image pair, in the sense that it can be the consequence of a plausible camera motion, just based on the information of the invariant descriptors, but not correct compared to the ground truth. Such an example can be seen on figure 3: the largest set of point correspondences consistent with a homography is actually not correct and consists of shifted patterns. In this case, the standard approach (considering photometric and geometric information independently) does not succeed in recovering from perceptual aliasing. The reason is that nearest neighbour matching tends to associate patches with the same absolute size (in pixels) because of the limited invariance of the descriptors to scale change.

Let us also remark that a certain amount of perceptual aliasing cannot be resolved just from images. For example, in figure 3 we implicitly assume that the correct motion is the minimal one, although a 90 • rotation of the cube would be possible.

RR n°7693

Figure 3: Synthetic cube. Top: SIFT correspondences (nearest neighbour + distance ratio criterion). Some correct correspondences can be seen. Bottom: the largest set consistent with a homography between the two images. As we can see, the 15 correspondences are not correct and map to shifted patterns.

Another situation is characteristic of scenes with repeated patterns. Even if the camera motion is properly estimated, lots of false correspondences can occur "by chance". For example in figure 4, we can see false correspondences on the carpet that are kept because they satisfy the nearest neighbour matching, and also the epipolar constraint, in the sense that each interest point lie on the associated epipolar line of its counterpart. This situation is particularly worrying in Structure from Motion applications: correspondences between repeated patterns may give a potentially large number of spurious reconstructed 3D points by triangulation.

This situation was known in the psychovision community from the eighties, and is named the double nail illusion after a nice article by Krol and van de Grind [START_REF] Krol | The double-nail illusion: experiments on binocular vision with nails, needles, and pins[END_REF]. It is illustrated by figure 5 in the context of two-view geometry. We can see that any set of repeated patterns lying on an epipolar plane is likely to give arbitrary point correspondences. Some point correspondence problems are thus intrinsically ambiguous if the information is restricted to the invariant descriptors. It is illustrated by a purely theoretical reasoning here, but wrong correspondences due to repeated patterns are common in practical two-view problems, as in figure 4. Note that scale invariance discards any depth-related information (by making it impossible to decide based on relative size of the features), in a similar way as the vergency trap in the original double nail illusion [START_REF] Krol | The double-nail illusion: experiments on binocular vision with nails, needles, and pins[END_REF]. Incorporating the scale information in the matching process as in [START_REF] Triggs | Epipolar constraints for multiscale matching[END_REF] or the relative position of the interest points [START_REF] Schmid | A structured probabilistic model for recognition[END_REF] should probably help disambiguating such situations. Another possibility would be to to group the repeating structure beforehand (in order to use the groups as non-repeated features) as in [START_REF] Leung | Detecting, localizing and grouping repeated scene elements from an image[END_REF][START_REF] Schaffalitzky | Planar grouping for automatic detection of vanishing lines and points[END_REF][START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF][START_REF] Tuytelaars | Noncombinatorial detection of regular repetitions under perspective skew[END_REF]. To the best Figure 4: Loria corridor. Nearest neighbour matching, followed by epipolar RANSAC. Correct correspondences can be seen on the walls, and a large number of false ones on the carpet. The epipolar lines in the right image associated with points A and B (from the left image) naturally go through the corresponding point. The same holds for point C whose corresponding point in the right image is not correct. However, the camera motion is properly estimated: for example the epipolar line associated with point D actually go through the corner of the doorway in the other image, in spite that no correspondence is detected in its neighbourhood. Here, the correspondences on the carpet are kept because they satisfy simultaneously the nearest neighbour matching and the epipolar constraint. The "multiple" nail illusion. We consider here two views of a 3D scene with repeated patterns. The image plane is represented between the optical center and the scene. Even if the two cameras are calibrated (and thus the epipolar constraints is known), some situations cannot be distinguished just from the information contained in the invariant descriptors. Here, the three black dots in both images are interest points with almost identical descriptors (because they correspond to repeated patterns), and since they lie on a common epipolar plane they can be associated in any of the six possibilities, yielding any of the six possible respective positions in the 3D scene (two are shown here.) Of course, only a single possibility is physically feasible. Let us remind that the scale associated with the interest points is not taken into account in the descriptor based matching. of our knowledge, this possibility has not been yet investigated further. The aim of the strategy used in section 7 for ASIFT is actually to disambiguate double nail illusion by enforcing relative positions in both images.

The double nail illusion yields false correspondences between repeated patterns. In some situations, it can even trap the matching algorithm and return a model with epipolar lines which do not correspond to the camera motion and which actually are vanishing lines (see figure 6.) The phenomenon is explained in figure 7. Note that this situation is related to the so-called auto-epipolar matching by Mundy and Zisserman [START_REF] Mundy | Repeated structures: Image correspondence constraints and 3D structure recovery[END_REF]. In this latter paper, the authors argue that a single view of a duplicate object at two different positions is equivalent to two views of a single object, thus it is possible to define epipolar lines. Auto-epipolar matching is the case where corresponding points lie on the same epipolar line. Figures 6 and7 actually correspond to auto-epipolar matching. Let us remind that the geometric model is usually fitted with RANSAC: the degenerate situation gives the largest consensus set and wins over smaller but correct sets of correspondences. The direction of the vanishing / epipolar lines corresponds to the direction of the longest 3D lines containing repeated patterns, yielding the largest auto-epipolar matching.

In this discussion we have pointed out that independently considering descriptor similarity and geometric constraint yields difficulties in the point correspondence problem. In the following section we present related works that aim at overcoming these difficulties. We come back to the double nail illusion in sections 6 and 7. Correspondences here satisfy both descriptor similarity and epipolar constraints. However, many false correspondences can be seen (on the lower pair, correspondences can be seen with the fourth windows which is not visible in the first image), and the epipolar lines (in yellow) correspond to vanishing lines, yielding an incorrect camera pose estimation. Figure 7: Trapped by the double nail illusion: illustration. Starting with the two views of the unknown 3D scene (repeated patterns on a vertical plane), the interest points (black dots) are not correctly associated. From these correspondences, the position of the 3D points is (incorrectly) inferred at the red disks. Consequently, the scene is not seen as planar, and there is no ambiguity on the retrieved epipolar geometry. Due to the auto-epipolar matching, the epipolar lines are here vanishing lines of the scene, and the epipoles are vanishing points.

Related work

Reliably matching interest points is a question which is often brought up by the literature. Several articles try to overcome the difficulties arising from the two-step correspondence finding (as described in the introduction) by circumventing it. To address the problem of "correspondence-free" structure from motion, a possibility is to use brute force techniques (i.e. considering all possible correspondences among extracted interest points), guided by some heuristics.

To the best of our knowledge, correspondence searching without prior photometric matching was for the first time extensively studied by Dellaert et al. [START_REF] Dellaert | MCMC, and chain flipping for structure from motion with unknown correspondence[END_REF]. However, their approach is purely combinatorial. They explicitly "adopt the commonly used assumption that all features x j are seen in all images, i.e. there are no spurious measurements and there is no occlusion" [START_REF] Dellaert | MCMC, and chain flipping for structure from motion with unknown correspondence[END_REF]. We believe that the basic assumption is too restrictive to deal with occlusion and point misdetection, which often arise in practice. A recent paper [START_REF] Georgel | Simultaneous in-plane motion estimation and point matching using geometric cues only[END_REF] by Georgel et al. suggests how it could be possible to solve the two-view correspondence problem without any photometric information. Basically, it consists in smartly discretizing the set of essential matrices that enforce the geometric constraints. However, in their framework the combinatorial burden is seriously restricted by the set of possible camera motions between the two views, which restricts the degrees of freedom of the essential matrix from 5 to 2.

A way to reduce the computational complexity is to use photometric information along geometric constraints. Domke and Aloimonos [START_REF] Domke | A probabilistic notion of correspondence and the epipolar constraint[END_REF] present a solution which consists in establishing an a priori probabilistic model for the correspondence distribution, computed for every image pixel. They do not need any preliminary matching step between interest points. Since the 5D space of all possible motions (in the calibrated case) must be explored, this approach has a heavy computational cost as in [START_REF] Dellaert | MCMC, and chain flipping for structure from motion with unknown correspondence[END_REF], although speeding up is possible when a preliminary motion estimation is known. The same basic idea was used before by Roy and Cox [START_REF] Roy | Motion without structure[END_REF], who compute the photometric likelihood that points lie on the corresponding epipolar line, and aim at maximizing it over all possible motions. A similar idea is presented by Antone and Teller [START_REF] Antone | Scalable extrinsic calibration of omni-directional image networks[END_REF] in the context of omni-directional image networks. They indeed estimate the baseline between two views by considering all possible feature correspondences satisfying epipolar constraints. They propose to solve this high-complexity problem by constraining the search through feature similarity.

Another way of incorporating photometric and geometric constraint for structure and motion estimation has been investigated by Stein and Shashua in [START_REF] Stein | Model-based brightness constraints: on direct estimation of structure and motion[END_REF]. Optical flow provides photometric information but suffers from the well known aperture problem which is painful for scenes with long straight edges (and also suffers from the constant intensity assumption, which is on the contrary overcome by contrast invariant descriptors such as SIFT.) To avoid this, the authors of [START_REF] Stein | Model-based brightness constraints: on direct estimation of structure and motion[END_REF] propose to build the so-called tensor brightness constraint which is based on both the optical flow and the trifocal tensor which encodes the geometry between three views [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF]. However, as every method based on the optical flow, this cannot be extended to large transformations between views, which would make the optical flow estimation unreliable. No explicit point correspondence is needed. Some very recent works discuss the use of Radon transform for correspondencefree motion estimation. Lehmann et al. [START_REF] Lehmann | Correspondence-free determination of the affine fundamental matrix[END_REF] focus on the determination of the affine fundamental matrix (that corresponds to the case of orthographic camera model.) The Fourier transform of different views are related through the parameters of the motion of the camera since image rotation and translation lead to spectrum rotation and phase RR n°7693 change. Motion parameters are retrieved by matching lines in the Fourier domain with a dedicated EM algorithm. Experimental results are promising; for the moment this approach is intrinsically restricted to the orthographic model which is less complex than the full epipolar model. However occlusions are not handled. The same idea is used by Makadia et al. [START_REF] Makadia | Correspondence-free structure from motion[END_REF]; the Fourier transform is used to generate a global likelihood function on the space of all observable camera motions, which appears to be (quite) easily tractable in the Fourier domain, although a careful discretization is needed. Results mainly concern catadioptric cameras.

All of the preceding "correspondence-free" models compute the camera motion by global view matching and are therefore not robust to occlusions and to small overlaps between images. Explicitly using interest points allows to deal with these latter shortcomings. From this point of view, we can cite recent works [START_REF] Chum | Matching with PROSAC -progressive sample consensus[END_REF][START_REF] Goshen | Balanced exploration and exploitation model search for efficient epipolar geometry estimation[END_REF][START_REF] Tordoff | Guided-MLESAC: faster image transform estimation by using matching priors[END_REF] which take into account photometric similarity to guide the search for correspondences that are consistent with camera motion. In these articles, which all propose improvements of the RANSAC algorithm, the goal is mainly to speed up the search for a consensus set. The common idea is to use the similarity between descriptors to guide the search: sampling is no more uniform as in classic RANSAC but is weighted by the similarity prior. However, a first step consisting in a photometric matching is still needed, and the problem of repeated patterns is not really tackled. Let us precise that in their paper about Guided-MLESAC [START_REF] Tordoff | Guided-MLESAC: faster image transform estimation by using matching priors[END_REF], Tordoff and Murray mention the possibility of getting rid of the photometric matching step by incorporating the photometric information in the prior. Although no evidence is given, it should theoretically also improve their algorithm when facing repeated patterns.

Disambiguating correspondences when repeated patterns are present can be achieved by taking account of the local organization of the interest points. Deng et al. [START_REF] Deng | Reinforcement matching using region context[END_REF] associate SIFT descriptors with a region context descriptor which encodes the relative position of nearby interest points. Their so-called "reinforcement matching" directly takes into account geometric information from the "region context". As in our algorithm, matching is not restricted to nearest neighbours. Hence, to some extent, it should be able to disambiguate a certain amount of perceptual aliasing, although no evidence is given in [START_REF] Deng | Reinforcement matching using region context[END_REF]. In the same spirit, Aguilar et al. [START_REF] Aguilar | A robust Graph Transformation Matching for non-rigid registration[END_REF] propose a matching process which is based on the observation that the relative position of the interest points is preserved in both views, provided the viewpoint change is limited. Thus they define in each view a K-nearest neighbour graph. Point correspondences are obtained by matching the two graphs: outliers are detected if the graphs are locally non-isomorphic. This method seems promising and shows better results than the popular Softassign algorithm [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF]: it is generic and robust to repeated patterns, although the geometric constraints are not explicitly enforced. This has been recently used to improve Morel and Yu's ASIFT [START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF] with respect to repeated patterns in [START_REF] Brese | An improved ASIFT algorithm for matching repeated patterns[END_REF].

While very few generic point matching algorithms explicitly tackle the repeated pattern problem, some authors first group features sharing the same aspect [START_REF] Leung | Detecting, localizing and grouping repeated scene elements from an image[END_REF][START_REF] Schaffalitzky | Planar grouping for automatic detection of vanishing lines and points[END_REF][START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF][START_REF] Tuytelaars | Noncombinatorial detection of regular repetitions under perspective skew[END_REF]. For example, Schaffalitzky and Zisserman [START_REF] Schaffalitzky | Planar grouping for automatic detection of vanishing lines and points[END_REF] determine vanishing lines in a single image, by pairing aligned repeated patterns. By detecting repeated structures in building façades, it is possible to achieve pose estimation in urban scenes [START_REF] Schindler | Detecting and matching repeated patterns for automatic geo-tagging in urban environments[END_REF].

The very recent work by Serradell et al. [START_REF] Serradell | Combining geometric and appearance priors for robust homography estimation[END_REF] shares several common points with the proposed a-contrario method. They make use of geometric and appearance priors to guide homography searching. While we also use appearance prior (which we call "photometric constraint" in section 4.3), our geometric prior is much simpler since it is derived by the random sampling of the tentative correspondences as in RANSAC. Although Serradell et al.'s method needs several algorithmic choices it gives promising RR n°7693 results with repeated patterns and even strong viewpoint changes. It is not limited to the nearest neighbour when matching interest points.

4 An a-contrario model for point correspondences under epipolar constraint and photometric consistency

In this section we propose a method based on a statistical a-contrario model. Since the seminal paper by Desolneux, Moisan and Morel [START_REF] Desolneux | Meaningful alignments[END_REF], these models have been the subject of a large amount of literature. The books [START_REF] Cao | A theory of shape identification[END_REF] and [START_REF] Desolneux | From Gestalt theory to image analysis: a probabilistic approach[END_REF] and the references therein give a comprehensive account of their use in many different computer vision problems. In [START_REF] Cao | A unified framework for detecting groups and application to shape recognition[END_REF] and [START_REF] Musé | An a contrario decision method for shape element recognition[END_REF] several a-contrario models are designed for correspondence finding between two views. Nevertheless, these models deal with geometrical shapes under affine transformations instead of interest points under epipolar and homographic constraints as in the framework presented here.

The idea behind a-contrario models is that independent, structure-less random features can produce structured groups only with a very small probability. This claim is sometime called the Helmholtz principle in the a-contrario literature. The model proposed in this report is based on Moisan and Stival's a-contrario RANSAC [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] and on Rabin et al.'s a-contrario model for SIFT-like descriptor matching via an Earth Mover's Distance [START_REF] Rabin | A statistical approach to the matching of local features[END_REF][START_REF] Rabin | MAC-RANSAC : reconnaissance automatique d'objets multiples[END_REF]. The first paper [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] focuses on geometric constraints and assumes that correspondences between interest points are given by some prior step. It also gives an indication of how to find out correspondences based on geometry and photometry (the so-called "colored rigidity" criterion.) Our contribution consists in generalizing Moisan and Stival's algorithm to incorporate both epipolar constraint and photometric consistency. We also specify the implementation and build up heuristics to make the matching task tractable. The latter papers [START_REF] Rabin | A statistical approach to the matching of local features[END_REF][START_REF] Rabin | MAC-RANSAC : reconnaissance automatique d'objets multiples[END_REF] prove that Earth Mover's Distance is better than existing dissimilarity measures between SIFT features, and investigate several a-contrario approaches.

Let us give some notations. We assume that two views (images I 1 and I 2 ) from the same scene are given. For each image, some algorithm (for example SIFT) gives a set of interest points, along with a descriptor. Let us note (x i , D(x i )) 1≤i≤N1 (resp. (y j , D(y j )) 1≤j≤N2 ) the N 1 (resp. N 2 ) couples from I 1 (resp. I 2 ) such that x i (resp. y j ) is the coordinate vector of an interest point, and D(x i ) (resp. D(y j )) is the corresponding local descriptor. Depending on the circumstances, we denote x i the interest point itself, its pixel coordinates, or its homogeneous coordinates in the projective plane.

We assume to be within the scope of the pinhole camera model. In this framework, if x i and y j are the projections in I 1 and I 2 of the same 3D point, then y j lies on the epipolar line associated with x i . This line is represented by F • x i , where F is the fundamental matrix from I 1 to I 2 . Conversely, x i has to lie on the epipolar line F T • y j since the fundamental matrix from I 2 to I 1 is the transpose matrix F T . However, if the camera has just been rotated around its optical center between the two views, or if interest points lie on a common plane, then the fundamental matrix is not defined. In this case, there is a 2D projective transformation (a homography) H such that y j = H(x i ) and x i = H -1 (y j ).

If the local descriptors were invariant to projective transformations, then D(x i ) and D(y j ) should be theoretically identical. However, such an invariance is practically unreachable without 3D information. With the additional assumption that the 3D scene is locally planar, then invariance to homographies is just needed. Such an approach is used e.g. in [START_REF] Molton | Locally planar patch features for real-time structure from motion[END_REF]. Most of the time, a weaker invariance is still satisfying, namely invariance to affine transformations [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF] or to zoom+rotation (similarity) transformations which is easier to handle in practice, as in Lowe's SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Consequently, the descriptors D(x i ) and D(y j ) are "similar" but not identical as soon as the viewpoint change does not exactly amount to an affine or similarity transformation.

The problem of interest is therefore to find a subset S of {1, . . . , N 1 }×{1, . . . , N 2 } and a fundamental matrix F or a homography H from I 1 to I 2 such that:

1. The distance between corresponding descriptors is below some threshold δ D , ensuring that the local image patches are alike:

∀(i, j) ∈ S, d D (D(x i ), D(y j )) ≤ δ D . (1)
2. The distance between a point and the epipolar line associated with the corresponding point is below some other threshold δ G (and vice versa), ensuring that the epipolar constraint is satisfied:

∀(i, j) ∈ S, d G (x i , y j , F ) := max{d G (y j , F •x i ), d G (x i , F T •y j )} ≤ δ G . (2)
Alternatively for the homography constraint:

∀(i, j) ∈ S, d G (x i , y j , H) := max{d G (y j , H(x i )), d G (x i , H -1 (y j ))} ≤ δ G . (3)
Remark that symmetrization with respect to I 1 and I 2 in equations ( 2) and (3) could have been achieved in other manners. Here, the product-distance is used.

In the sequel we shall give a definition of both distances (or dissimilarity measures) d D and d G . The proposed statistical framework automatically balances geometry and photometry, and also automatically derives both thresholds δ D and δ G relatively to a set S.

The a-contrario model

Before specifying distances d D and d G , we explain the statistical model that will help us in making decisions. In the a-contrario method, groups of features are said to be meaningful if their probability is very low under the hypothesis H 0 that the features are independent. Independence assumption makes the probability computation easy, since joint laws are simply products of marginal laws which can be reliably estimated with a limited number of empirical observations. Without independence assumption, joint law estimation would indeed come up against the curse of dimensionality. In the statistical hypothesis testing framework, this probability is called a p-value: if it is low (typically below 5%), then it is likely that the group of interest does not satisfy independence assumption H 0 . There must be a better explanation than independence for this group, and this explanation should emphasize some common causality. Here, pairs of features form a meaningful group because interest points from a pair actually correspond to the same 3D point, and the motion of all interest points between the two views is consistent with the motion of the camera.

Let us assume that a set S of correspondences is given, as well as a fundamental matrix or a homography A and two thresholds δ G and δ D as in equations ( 1) and ( 2).

The probability that should be estimated is: 2) or [START_REF] Antone | Scalable extrinsic calibration of omni-directional image networks[END_REF].

p(S, A, δ G , δ D ) := Pr ∀(i, j) ∈ S, d G (x i , y j , A) ≤ δ G and d D (D(x i ), D(y j )) ≤ δ D | H 0 (4) with d G as in equations (
Let us also assume that the transformation A is estimated from a minimal subset of S as in the RANSAC paradigm. This means in the case where A = F is a fundamental matrix that a subset s from S made of m = 7 correspondences is used to estimate F [START_REF] Zhang | Determining the epipolar geometry and its uncertainty: a review[END_REF]. Remark that it would also be possible to use the 8-point linear method [START_REF] Longuet-Higgins | A computer program for reconstructing a scene from two projections[END_REF] with a slight adaptation. In the case where A = H is a homography A, m = 4 points are needed in s. In the sequel, S\s is the set of correspondences in S that are not in s. Definition 1 Considering (x i , D(x i )) and (y j , D(y j )) as random variables, we define hypothesis H 0 as: and(d G (x i , y j , A)) (i,j)∈S\s are mutually independent random variables.

1. (d D (D(x i ), D(y j ))) (i,j)∈S ,
2. (d G (x i , y j , A)) (i,j)∈S\s are identically distributed and their common cumulative distribution function is

f G 3. (d D (D(x i ), D(y j ))) (i,j
)∈S are identically distributed and their common cumulative distribution function is f D .

Of course, (d G (x i , y j , A)) (i,j)∈s are also identically distributed but do not follow the same distribution function f G as variables from S\s since A is estimated from s, leading to the conditions d G (y j , A(x i )) ≃ 0 and d G (x i , A -1 (y j )) ≃ 0 for every (i, j) ∈ s.

As a consequence, it is possible to estimate the probability from equation (4):

Proposition 1 p(S, A, δ G , δ D ) = f D (δ D ) k f G (δ G ) k-m ( 5
)
where k is the cardinality of S, and m the cardinality of s.

Proof: it is straightforward to derive:

p(S, A, δ G , δ D ) = (i,j)∈S\s Pr d G (x i , y j , A) ≤ δ G • (i,j)∈S Pr d D (D(x i ), D(y j )) ≤ δ D (6) = f D (δ D ) k f G (δ G ) k-m (7)
Equation ( 6) comes from point 1 in definition 1 and equation ( 7) from points 2 and 3.

In the hypothesis testing paradigm, the null hypothesis H 0 is rejected as soon as p(S, A, δ G , δ D ) is below the predetermined significance level (typically 5%.) However, it would mean here that, all things being equal, large groups S would be favoured since this yields small probabilities in equation [START_REF] Brown | Automatic panoramic image stitching using invariant features[END_REF]. Following the a-contrario method, we do not directly deal with the probabilities but rather with the so-called Number of False Alarms (NFA), which permits to get rid of the arbitrary significance level. The NFA corresponds to the average number of groups consistent with A, δ G , δ D under hypothesis H 0 . The NFA is estimated by multiplying the probability of a false alarm p(S, A, δ G , δ D ) by the number of possible events. Here, there are min{N 1 , N 2 }m choices for k ≥ m, N1 k choices for the interest points in image 1, N2 k choices for the interest points in image 2, k! choices for the correspondences, k m choices for the minimal set to estimate A. Each minimal set s possibly leads to Q = 3 fundamental matrices (7-point algorithm [START_REF] Hartley | Projective reconstruction and invariants from multiple images[END_REF]) or Q = 1 homography.

Definition 2 We say that a set S of correspondences is ε-meaningful if there exists 1. two thresholds δ G and δ D such that:

∀(i, j) ∈ S, d G (x i , y j , A) ≤ δ G , (8)
∀(i, j) ∈ S, d D (D(x i ), D(y j )) ≤ δ D , (9)
2. a transformation A evaluated from m points from S;

such that:

NFA(S, A, δ G , δ D ) := Q (min{N 1 , N 2 } -m) k! N 1 k N 2 k k m f D (δ D ) k f G (δ G ) k-m ≤ ε (10) where k is the cardinality of S, m = 4 and Q = 1 if A is a homography, m = 7 and Q = 3 if A is a fundamental matrix.
Since f D and f G are non-decreasing, the following proposition comes as a corollary of this definition.

Proposition 2 A set S of correspondences is ε-meaningful if there exists a transformation A estimated from m correspondences among S such that:

NFA(S, A) := Q (min{N 1 , N 2 } -m) k! N 1 k N 2 k k m f D (δ D ) k f G (δ G ) k-m ≤ ε (11) with δ G = max (i,j)∈S max{d G (y j , F • x i ), d G (x i , F T • y j )}, δ D = max (i,j)∈S (d D (D(x i ), D(y j ))
, and k the cardinality of S.

The aim of the algorithm discussed in section 5 is to find the most (or a very) meaningful set of correspondences, that is to say the set of correspondences S with the lowest (or a very low) NFA(S). Equation ( 11) balances the trade-off between the probability f D (δ D ) k f G (δ G ) k-m and the number of possible sets of size k among the N 1 interest points from image 1 and N 2 interest points from image 2. If δ D and δ G are fixed, when k grows, the first one vanishes while the latter one tends to increasing (see proposition 3 section 9) Definition 2 was outlined in [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] (colored rigidity) but was neither investigated further nor implemented.

In the following sections we specify the choice for distances d D and d G , and associated cumulative distribution functions f D and f G . Note that the a-contrario framework, as it has been presented, is valid as long as f D (resp. f G ) is a cumulative distribution function for distance d D (resp. d G ).

Modelling the geometric constraint

In the case of epipolar constraint (A = F ), Moisan and Stival [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] propose to define d G (y, F • x) as the Euclidean distance between y and the epipolar line F • x. The function f G is then defined as (with a slight abuse, see below):

f G (d euc (y, F • x)) = 2D S d euc (y, F • x) (12)
where D and S are respectively the diameter and surface area of both images (mildly assumed here to have the same size.) This choice comes from an a-contrario model which is more specific than the one from the previous section. In their paper, Moisan and Stival not only assume independence, but also that interest points are uniformly distributed in images. This leads them to estimate the probability that some random point (drawn from a uniform distribution) falls at a distance less than δ from an epipolar line. It is easy to see via a simple geometric argument that this probability is bounded above by 2D S δ. See figure 8. With equation (2), we derive here:

Pr(d G (x, y, F ) ≤ δ G ) = Pr(max{d G (y, F • x), d G (x, F T • y)} ≤ δ G ) (13) = 2D S δ G 2 (14)
by assuming that the Euclidean distances between y and F •x and between x and F T •y are independent, following the a-contrario framework.

As we have seen earlier, f G (δ G ) is balanced by the probability f D (δ D ) related to the photometric constraint. We decide to parametrize the distribution f G by actually using:

f G (δ G ) = 2D S δ G 2α (15)
RR n°7693

We discuss the influence of this α parameter in section 6.1.1.

Let us note that 2D S δ G may be larger than 1 since it is actually an upper bound of the cumulative distribution function. In order to speed-up the search, we decide to a priori eliminate groups such that this probability is larger than 5%. For typical 500 × 500 images, this corresponds to δ G > 12.5 pixels.

In the case of homography constraint (A = H), we have just to adapt the definition of f G (δ G ) from a point-line correspondence (equation ( 15)) to a point-point correspondence, for example with:

f G (δ G ) = πδ 2 G S 2α . (16)
Indeed, πδ 2 G /S is the probability for a random point uniformly distributed across an image (surface area S) fall at a distance less than δ G from a fixed point. The same kind of model was used in a different context in [START_REF] Buades | A note on multi-image denoising[END_REF] and in [START_REF] Rabin | MAC-RANSAC : reconnaissance automatique d'objets multiples[END_REF].

Modelling the photometric constraint

We define here d D and f D , namely the distance between local photometric descriptors and the associated cumulative distribution function.

Since the space of descriptors is neither isotropic nor homogeneous, it is well known (see for example [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]) that it is a bad idea to measure the proximity between descriptors by a simple Euclidean distance. This observation leads to the nearest neighbour matching approach. Because of the above-mentioned heterogeneousness, any "good" metric over descriptors should not be evaluated as a norm as ||D(x) -D(y)||.

On the contrary, it should take into account the vicinity of D(x) in order that the value of d D (D(x), D(y)) has the same meaning in terms of "perceptual proximity" for every pair of descriptors (D(x), D(y)).

Rabin et al. [START_REF] Rabin | A statistical approach to the matching of local features[END_REF] exploit this point of view by defining an a-contrario model dedicated to SIFT-like descriptor matching. Their approach has the advantage of automatically deriving distance thresholds that adapt to the descriptor of interest. Unlike the a-contrario model proposed in this report, they do not take into account the geometric constraints. Taking our inspiration from [START_REF] Rabin | A statistical approach to the matching of local features[END_REF], and based on previous works [START_REF] Musé | An a contrario decision method for shape element recognition[END_REF][START_REF] Noury | Fundamental matrix estimation without prior match[END_REF][START_REF] Noury | Modèle a contrario pour la mise en correspondance robuste sous contraintes épipolaires et photométriques[END_REF], we define:

d D (D(x), D(y)) = φ D(x) (dist(D(x), D(y))) (17)
where dist is some distance (or dissimilarity measure) over the descriptor space (Euclidean distance or a more sophisticated one as specified in the sequel), φ D(x) is the cumulative distribution function of dist(D(x), D(•)) when D(•) spans the set of descriptors in image I 2 . Note that, provided φ D(x) is exactly known and dist(D(x), D(y)) is actually a realization of the underlying random process, then d D (D(x), D(y)) is uniformly distributed over the unit interval [0, 1] (see proposition 5, section 9.) This distance therefore automatically adapts to the heterogeneousness of the descriptor space as a "contextual dissimilarity measure".

However, φ D(x) is not known, and the SIFT descriptors have high dimensionality (typically 128.) In addition, SIFT descriptors are made of N = 16 histograms of dimension m = 8. Rabin et al. [START_REF] Rabin | A statistical approach to the matching of local features[END_REF] exploit these remarks to reduce the dimensionality by using the following definition for the distance between descriptors, provided a suitable RR n°7693 distance dist between histograms:

dist(D(x), D(y)) = N i=1 dist(D i (x), D i (y)). (18)
Let us note for every

i ∈ [1, N ], ϕ D i (x) the distribution function of dist(D i (x), D i (•)
). Following the discussion in [START_REF] Rabin | A statistical approach to the matching of local features[END_REF] and under independence assumption, φ D(x) is defined as:

φ D(x) (δ) = δ 0 N i=1 ϕ D i (x) (t)dt ( 19
)
where ⊗ is the convolution product. Indeed, dist(D(x), D(y)) appears as the sum of N random variables whose probability distribution is indeed the convolution product of the N marginal distributions under independence assumption.

In practice, the distribution function ϕ D i (x) is empirically estimated over the set of all D i (y) when y spans the set of the interest point extracted from image I 2 .

We have d D (D(x), D(y)) = φ D(x) (dist(D(x), D(y))) from equation [START_REF] Georgel | Simultaneous in-plane motion estimation and point matching using geometric cues only[END_REF]. In order to fulfill requirements of section 4.1, we still need to define the cumulative distribution function f D . Since

f D (t) = Pr(φ D(x) (dist(D(x), D(y))) ≤ t) = t (20)
if f D(x) is continuous and increasing (this is a classic property of cumulative distribution functions, see section 9), we simply set here f D (t) = t.

We still have to define dist, that is to say the distance between sub-histograms of each descriptor (equation [START_REF] Gold | A graduated assignment algorithm for graph matching[END_REF].)

Rabin et al. recently proposed in [START_REF] Rabin | A statistical approach to the matching of local features[END_REF] to use Earth Mover's Distance (EMD), which is especially well adapted for histogram comparison. The intuitive meaning of EMD is that it corresponds to the minimum cost that an Earth Mover has to pay to reshape a histogram into another one, given the cost c i,j to move a unit of material from bin i to bin j. More specifically, most local photometric descriptors (and especially SIFT) are made of histograms of the gradient direction which is distributed along the circular interval [0, 2π). Consequently, it is sound to use a metric that behave well with respect to these circular histograms. We use here the efficient circular EMD by Rabin et al. [START_REF] Rabin | A statistical approach to the matching of local features[END_REF], denoted CEMD.

5 Discussion of the a-contrario model and algorithm

Discussing the NFA criterion

We can see from equation [START_REF] Deng | Reinforcement matching using region context[END_REF] that α in f G (equations ( 15) or ( 16)) permits to balance between the geometric and photometric probabilities. These probabilities have not the same order of magnitude: the first one varies around 10 -5 while the latter one may be around 10 -20 . Thus α behaves as a normalization parameter, which is set once and for all to 5 after the discussion of section 6.1.1.

The sets with small NFA are the most relevant ones, as soon as the NFA is below 1. In this section we show that searching for an ε-meaningful set is realistic, given the RR n°7693 complexity of the problem and the probabilities at hand. This discussion completes the comments on the so-called colored rigidity in [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF]. For the sake of simplicity, we consider here the epipolar constraint case and assume

N 1 = N 2 = N .
Let us note

M (k, N ) := 3(N -7)k! N k 2 k 7 . (21)
Figure 9 shows the graph oflog 10 (M (k, N ))/k vs k for several typical values of N . From equation [START_REF] Deng | Reinforcement matching using region context[END_REF], this gives the maximal value for the logarithm of

f D (δ D )f G (δ G ) 1-7/k ≃ f D (δ D )f G (δ G ) so that the corresponding group S is 1-meaningful (in the case N 1 = N 2 = N .) One has indeed: NFA(S) ≤ 1 iff log 10 f D (δ D )f G (δ G ) 1-7/k ≤ -log 10 (M (k, N ))/k. (22)
One can see that the NFA criterion meets two requirements that are naturally expected:

• When N is fixed, the smaller the k, the smaller the latter probability product should be. This situation can be met when dealing with a large rate of outliers and seeking meaningful groups with k small with respect to N . Since f D and f G are non-decreasing, this means that thresholds δ D and δ G must be stricter in this case.

• When k/N is fixed, the larger N , the smaller the probability product (and hence the stricter the thresholds.) This is handy when looking for correspondences in fixed size images: the denser tentative correspondences are, the more accurate they should be with respect to geometric and photometric criteria.

Speeding up the search for meaningful sets

When looking for the most meaningful group of correspondences (either under fundamental matrix or under homography), a naive approach would consist in testing all possible sets of correspondences. However, if N = 100 features are extracted in each image, there are

N k=0 k! N k 2 ≃ 10 164 (23)
such sets (as already remarked in [START_REF] Antone | Scalable extrinsic calibration of omni-directional image networks[END_REF].) Since testing all possible sets is out of question, a heuristic-driven search is called for. First (section 5.2.1), we use some (large) threshold on the photometric constraint to restrict the set of tentative correspondences for a given interest point from image I 1 . Since the set of possible correspondences is still huge, we use a random sampling method, i.e. a RANSAC-like heuristic (section 5.2.2.)

Combinatorial reduction

In order to reduce the computational burden, we do not consider all possible correspondences y 1 , . . . , y N2 in image I 2 for an interest point x i from image I 1 , but only the set of tentative correspondences y j1 , . . . , y j N i such that the distance between the associated descriptors is below some threshold. Of course, this matching threshold should just allow to prune the set of possibilities for algorithmic complexity purpose. Thus it should be large enough so that the true matching decision is not made at this step, while eliminating clearly non-relevant correspondences.

In order to avoid arbitrary thresholds, we use the handy a-contrario framework given by [START_REF] Rabin | A statistical approach to the matching of local features[END_REF]. In this latter case y j is a tentative correspondence to x i if, with notations of equation [START_REF] Georgel | Simultaneous in-plane motion estimation and point matching using geometric cues only[END_REF]:

N 1 N 2 d D (D(x i ), D(y j )) ≤ ε. ( 24
)
The value of ε does not depend on the experimental setup and is carefully discussed in [START_REF] Rabin | A statistical approach to the matching of local features[END_REF]. Note that proposition 5 (section 9) argue about the auto-adaptability of this quantity to the considered descriptors. We set in this report ε = 10 -2 which gives a reasonable amount of tentative correspondences. This choice is motivated in section 6.1.2. In practice, we get between 0 and 30 tentative correspondences for each x i in a typical image.

Random sampling algorithm

At this stage each interest point x i from image I 1 is matched to a set of N i tentative correspondences y j1 , . . . , y j N i in image I 2 . Now, the aim is to pick up one (or zero) y j(i) from this list. Since the algorithmic complexity is still too large, we use a random sampling algorithm. It is a two-step iterative algorithm, which we describe for the two cases of interest (fundamental matrix F or homography H):

A draw a sample made of seven correspondences for estimating F , or four for H B look for the most meaningful group made from a subset of the preceding tentative correspondences, consistent with F or H.

A. Drawing a seven-or four-correspondence sample. Seven (or four) points x i are uniformly drawn, and then are associated to a tentatively corresponding point y j(i) .

Since it gives good experimental results and reduces the computational burden, we use nearest neighbour matching (in the sense of the photometry.)

The fundamental matrix is then estimated via the non-linear "seven-point algorithm" [START_REF] Hartley | Projective reconstruction and invariants from multiple images[END_REF][START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF], and in the case of the homography, it is estimated by the Direct Linear Transform and the resulting linear system is solved by Singular Value Decomposition.

Remark that the SIFT algorithm may extract several keypoints at the same location but with different orientations or scales. In order to avoid degenerated cases, we check that the minimum sample does not contain such points. We have experimentally checked that these multiple points do not introduce noticeable bias in the computation of the NFA.

B. Seeking meaningful groups. Correspondences are added to the previous seven ones to form a group as meaningful as possible. We make use of the following heuristic, which consists in iterating the following stages. 1. For every x i , select:

y j(i) = argmin yj k {f D (d D (D(x i ), D(y j k ))) • f G (d G (A, x i , y j k ))} (25)
and sort correspondences (x i , y j(i) ) in increasing order along this latter value, in order to obtain a series of nested groups made of k = 7, 8, 9, . . . , N 1 correspondences.

This step can produce correspondences between N > 1 x i 's to a single y j , which should not happen. Therefore, we decide to keep among these correspondences a single one, namely (x i , y j(i) ) such that the above-mentioned probability product is minimized.

2. Compute the NFA for each one of the above-mentioned nested groups and select the most meaningful one.

3. Sort correspondences (x i , y j(i) ) in increasing order along f G (δ G (A, x i , y j(i) )) to build up a new set of nested groups, compute the NFA and select the most meaningful one.

4. Return the most meaningful group found out by either step 2 or 3.

Steps 1 and 2 obviously do not ensure that the obtained group is the most meaningful one with a fixed F matrix (unlike the a-contrario RANSAC algorithm from [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF] where the geometric criterion only is used.) This heuristic aims at driving the search. It is based on the fact that, provided k is fixed, the most meaningful group minimises the product f D (δ D )f G (δ G ). Note that Step 1 allows selecting correspondences among non-nearest neighbours. We have experimentally remarked that Step 3 often allows to discard false correspondences that are introduced with a low k in Step 1 because the photometric distance is very good and overwhelms the (poor) geometric distance. Using successive heuristics to test set of correspondences is sound since the lowest NFA is sought, whatever the way the group is built.

Let us remark that F (or H) is never reestimated over the whole set in this algorithm; the current F or H is estimated from a minimum sample. The aim is indeed here to get a set of correspondences, and not to estimate a registration from this set.

About the number of iterations

Note that in step A, we draw the minimum sample s only from the nearest neighbours. As in every RANSAC scheme, assuming that the outlier rate is r among the nearest neighbours, the number of iterations N should be

N ≥ log(1 -p) log(1 -r |s| ) ( 26
)
where p is the probability to get at least one sample s made of inliers. Estimating r online has been the subject of a large literature; we will not elaborate on it in this report, and we decide to take N = 20, 000 iterations in all experiments, so that the returned group is actually the most meaningful one with a high confidence.

In step A, we could also have avoided biasing the algorithm by the nearest-neighbour choice as in [START_REF] Zhang | Generalized RANSAC framework for relaxed correspondence problems[END_REF]. It would have been possible to pick up for each i the corresponding point y j(i) by drawing it randomly in the set y j1 , . . . , y j N i where y ji has weight K/d D (D(x i ), D(y ji )) (K is a normalization parameter.) This scheme would preferably select nearest neighbours but also permits non-nearest neighbours among the minimum sample. However, the outlier rate is significantly larger for non-nearest neighbours (which can be verified in experiments, see table 3); this latest scheme thus needs much more iterations (although it is difficult to quantify) while it does not improve the results.

Algorithm

To sum up the discussion, the whole algorithm is given here. We consider that two views of the same 3D-scene are given. (a) choose seven (resp. four) points x i and pick up the seven (resp. four) corresponding points y j(i) (heuristic A from 5.2.2), (b) compute the three possible fundamental matrices F from these seven correspondences and goes to (c) for each one of these matrices, (resp. compute the homography H from these four correspondences and goes to (c))

(c) select the most meaningful group (heuristic B from 5.2.2.)

In the end, return the most meaningful group ever encountered.

Let us remark that the proposed probabilistic model and algorithm are not specific to SIFT descriptors and can be easily adapted to other invariant histogram-based descriptors.

Experiments

We test now point matching under epipolar constraint (fundamental matrix) or homography when repeated patterns are present.

Computation time of the a-contrario algorithm (section 5.

3) is about 30-40 seconds for typical 500 × 500 images (≃ 5 seconds for 200 × 200 images.) Speeding-up would be possible via multi-core programming and improving estimation of the photometric distribution function (the ϕ D i (x) in equation ( 19)), e.g. by subsampling the dataset in a Monte-Carlo estimation.

The experiments are organized in the following way. Section 6.1 investigates the role of the two parameters of the algorithm, namely α (section 4.2) and ε (section 5.2.1.) Section 6.2 discusses that the proposed a-contrario model permits to retrieve correspondences even when a large number of repeated patterns are present in the scene, and compare it to a Generalized RANSAC able to pick correspondences beyond the nearest neighbour.

All these experiments show that the matching thresholds (δ D and δ G ) are automatically derived and actually vary, and that we are able to select correspondences that are not photometric nearest neighbours. Of course, these latter correspondences are never taken into account in the popular approach based on nearest neighbours described in section 1. Now, Generalized RANSAC with the correct parameters give similar results in most experiments.

In most illustrations of the a-contrario model, the correspondences are represented by a straight segment from the interest point, whose length is the apparent motion of the point in a view to the corresponding point in the other view.

Sensitivity of the a-contrario model to the parameters

We test here the influence of the parameters α (from section 4.2) and ε (from section 5.2.1.)

Influence of α

Equations ( 15) and [START_REF] Fischler | Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[END_REF] shows us that the smaller α, the smaller the contribution of the geometric constraint in the NFA. One could imagine that, starting from a group of correspondences with cardinality k, photometric threshold δ D and geometric threshold δ G , dividing α by two would yield an equally meaningful group of correspondences, that is to say with the same k, δ D and a new δ

′ G such that 2D/A•δ G = (2D/A • δ ′ G ) 1/2
. However, this would imply δ ′ G = 0.001 pixel, for 500 × 500 images and for the standard value δ G = 0.5 pixel. Such a small value for δ ′ G is simply not reachable. As a matter of fact, a smaller α yields a set of correspondences less constrained by the geometry, and more by the photometric resemblance of the descriptors. On the contrary, a larger α should yield groups of correspondences that meet the geometric constraint well, however the photometric constraint may be too loosened in this case. In this latter case the geometry may not correspond to the reality. Note also that the geometric and photometric constraints are balanced by the number of corresponding points as explained in section 5.1: a small group can win over a large one if the photometric (small α) or geometric (large α) constraint is tightly enforced. From this heuristic discussion, we see that a trade-off must be met. This situation is illustrated by figures 10 (epipolar constraint) and 11 (homography constraint) in a situation where the camera motion is a rotation around the center of the cube.

RR n°7693

Figure 10: Influence of the α parameter, epipolar constraint. Top: α = 3. There are 138 correspondences (between left and middle images; 31 of them are not nearest neighbours.) In this case, the geometric constraint is not enforced in a strong enough way. The most meaningful group corresponds to the situation where a lot of correspondences are found along the dominant direction of the lattice of repeated patterns (vanishing lines as shown in right image, see section 2.) Bottom: α = 5. There are 148 correspondences (47 are not nearest neighbours), and the retrieved epipolar pencil is now consistent with the camera motion. Note a false correspondence on the top of the cube that is consistent with respect to photometry (matches between repeated patterns) and geometry (matches along an epipolar line) as in figure 6.

RR n°7693

Figure 11: Influence of the α parameter, homographic constraint. Top: α = 1. 31 correspondences are retrieved between left and right images (4 are not nearest neighbours.) We can see that they are correct (i.e. between perceptually similar features), but shifted. Let us recall that SIFT has not a perfect invariance to scale change. Here, the most similar descriptors between the two images are the ones with the same absolute scale. Such correspondences are possible here because of the large amount of repeated patterns. A standard pair of images under different viewpoints is less likely to show repeated patterns that have the same absolute scale. Here, the photometric constraint has a too strong influence on the NFA, and is not balanced by the geometric constraint. Bottom: α = 3. 91 correspondences are retrieved ( .46 (.08) -20.5 (.17)

Table 1: Influence of α on the retrieved sets of correspondences, with the same images as in figure 10. From left to right, α, Nb. of points is the cardinality of the retrieved set, δ G , and log(δ D ). Standard deviation are indicated between brackets (average over 100 runs.) Up to α = 6, the larger α, the smaller δ G . When α is between 6 and 10, the accuracy does not decrease anymore because there are only a few matches with a distance to the epipolar line less than 0.4. Then the balance in the NFA furnishes groups with still lower NFA, but with the same k, δ G , δ D . The same experiment with the homography constraint gives similar results (not shown here.)

Table 1 provides some statistics when α grows (and thus the geometric constraint has more importance.) One can see that when α grows from 1 to 5 the number of retrieved correspondences grows, the geometric accuracy is better (distance to the epipolar line), while the photometric constraint becomes looser. Note that α larger than 6 does not yield significant changes in the most meaningful set of correspondences. From this table and other experiments, we decide to set in all following experiments α = 5 once and for all.

In the previous experiments, ε was set to 10 -2 .

Influence of ε

We test here the influence of the ε parameter (section 5.2.1). Since the SIFT descriptors are invariant to zoom+rotation only, a bias will appear in the probabilities as soon as the viewpoint change is too strong, as in every SIFT-based method. We therefore consider a small motion between two views, so that the non-invariance of SIFT to viewpoint interferes as least as possible. The test is led here with the fundamental matrix model. As an illustration, figure 12 shows some results with a varying ε. Table 2 gathers some statistics about this experiment. Concerning the influence of ε (namely the parameter of the "combinatorial reduction step"), one can see that reducing it subsequently reduces the number of tentative correspondences among which the most meaningful set is sought, while having almost no impact on the cardinality of this set. In other words, decreasing the value of ε speeds up the search while discarding mainly false correspondences. Note that at least 20-25% of the matches are not nearest neighbours. Once again, it would have been impossible to retrieve them with the classic SIFT nearest neighbour matching. the four distances between descriptors that are tested, the six values of ε in the range 1 -10 -10 , the number of tentative correspondences retrieved after the combinatorial reduction step (section 5.2.1), the cardinality of the most meaningful group (average over 100 runs, standard deviation in brackets), and the average proportion of nearest neighbours among this group of correspondences.

ε = 1 ε = 10 -2 ε = 10 -4 ε = 10 -6 ε = 10 -8 ε = 10 -10
Figure 12: Synthetic images. In this experiment, we search for the most meaningful group consistent with a fundamental matrix between two for six values of ε. We only show here the first view, the blue segment corresponds to the apparent motion of an interest point (localized by a cross) between the two views. One can see that some false correspondences are still retrieved. A careful examination shows that they actually lie along the associated epipolar line, and simply cannot be detected in a two-view matching. In all experiments (whatever the distance and ε as in table 2), the average distance to the epipolar line is about 0.2-0.3 pixel. 343 SIFT keypoints were extracted from image 1, and 321 from image 2.

From these results and other experiments on realistic images, we decide to set in the sequel ε = 10 -2 , which leads to a good trade-off between complexity reduction and size of the most meaningful group.

Point correspondences and perceptual aliasing

We consider here images with repeated patterns, in the light of section 2. In particular, we discuss the a-contrario algorithm and a Generalized RANSAC detailed in the following section.

A Generalized RANSAC algorithm

This section presents a Generalized RANSAC algorithm, inspired by Zhang and Kosecka [START_REF] Zhang | Generalized RANSAC framework for relaxed correspondence problems[END_REF].

Standard RANSAC takes as input the tentative one-to-one point correspondences given by a preliminary step based on descriptor similarity. If this step is relaxed so that each interest point x in the first image has K tentative correspondences y 1 . . . y K in the second, then the following algorithm is able to extract a set of correspondences consistent with a homography or the epipolar constraint. It consists in iterating the following operations: (here y(x) is one of the y 1 . . . y K associated to y i ) 1. Draw a minimum sample (x, y(x)) to estimate H (or F ).

2. Knowing H (or F ) associate each x to a single y(x) among the tentative correspondences.

3. Count the number of correspondences (x, y(x)) such that d(x, y(x), H) (or d(x, y(x), F ), as in equations ( 2) or ( 3)) is less than a pre-determined threshold δ GR .

In the end, the largest consensus set is returned.

We decide to associate in step 1 the x to their nearest neighbour y(x) among the tentative correspondences y i (in the sense of the descriptor proximity) and in step 2 to define y(x) among the y i as minimizing the distance d.

In [START_REF] Zhang | Generalized RANSAC framework for relaxed correspondence problems[END_REF] it is suggested to randomly sample the x and y(x), and different strategies are given. We found that taking the nearest neighbour in step 2 significantly reduces the number of needed iterations. It is a sound hypothesis since in tractable cases, most correct correspondences are still among nearest neighbours, as we will see in the experiments.

Note that our aim here is not to compete with state-of-the-art RANSAC algorithms in terms of computational load, we just design a proof-of-concept algorithm to compare with the a-contrario models. Building a competitive Generalized RANSAC would necessitate strategies as like as in PROSAC [START_REF] Chum | Matching with PROSAC -progressive sample consensus[END_REF] for example. Let us discuss an example of the properties of Generalized RANSAC. As we have seen on figure 3, in some examples the nearest neighbour + threshold condition inevitably yields erroneous sets of correspondences. In figure 13, we show that when relaxing the tentative correspondences to the nearest neighbours (without any condition on the distance ratio), then it is possible to find a correct set of correspondences. Of course, a large number of iterations is needed since the outlier rate significantly increases. Here, about 31,000 iterations are needed to get a correct set (average over 10 runs). However, when searching among K = 5 first nearest neighbours, only about 13,000 iterations are needed. For example, the group shown in figure 13 (bottom) is made of 43 correspondences of rank 1, 25 of rank 2, 24 of rank 3, 14 of rank 4, 7 of rank 5. The subset of rank 1 correspondences is beaten by the erroneous set shown in figure 13 (top) which is made of 49 matches. Thus less iterations are needed when searching beyond the nearest neighbour. When searching among K = 10 first nearest Figure 13: Generalized RANSAC. About 800 SIFT keypoints are extracted from both images. The distance threshold δ GR is set to 1. Top and middle: K = 1 and homography constraint. False large consensus set can be retrieved, here 49 matches (top.) However, ensuring a large enough number of iterations in Generalized RANSAC makes it possible to find correct sets, here 60 matches (middle.) Bottom: K = 5. 113 correspondences are retrieved here, only 43 are ranked first; less iterations are needed. neighbours (not shown), about 6, 000 iterations are needed to get a correct set among which less than 50% are nearest neighbours. In this case there are only 4 correspondences between 7th and 10th nearest neighbours. In spite that each pattern is repeated more than 10 times, this means that the invariant descriptors are actually not repeated more than 5-6 times. This is due to their limited invariance and also to the fact that their extraction scale is such that they convey information which makes them distinguishable.

Figure 14 shows the correspondences with the a-contrario model. The advantage is that the distance thresholds and number of tentative correspondences kept are automatically derived. Figure 14: A-contrario RANSAC. Apparent motion of the interest points between the two views. All correspondences are correct. Here δ G was determined as 2.6 pixels. Among the 111 matches, 67 are nearest neighbours, 20 second nearest neighbours, 10 third nearest neighbours, and the rest behind fourth and eleventh.

Point correspondences and the curse of perceptual aliasing

The aim of this section is to show that the proposed method allows us to obtain more correspondences than a standard robust matching criterion when confronted with repeated patterns. Indeed, a significant part of the matched interest points does not come from the nearest neighbour descriptor, but from correspondences with a higher rank. We compare the proposed algorithm with a usual method using steps 2 and 3 presented in section 1, that is: NN-T matching (Euclidean distance, threshold on the ratio set to 0.6 as in Lowe's code), followed by a robust selection with the a-contrario RANSAC from [START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF]. The use of this two-step scheme is called NN-T+O, our method AC for a-contrario. We also compare with Generalized RANSAC of section 6.2.1.

Repeated patterns and homography. We first use the homography as the geometric constraint. When confronted to repeated patterns, the number of matches selected with NN-T is small, as shown in the right image of figure 15: repeated features are generally discarded at this early stage, and of course cannot be retrieved by the subsequent RANSAC. Our method, as shown in the left image of figure 15, retrieves much more correspondences. The numerous extra correspondences coincide with matches which are not nearest neighbour for the descriptor distance. From table 3, we can see that while 128 features are matched, 42 are ranked first, and 86 have higher ranks.

Table 3 also shows that if the tentative correspondences were defined as nearest neighbours (without any limitation over the distance ratio), then it should be possible to get a consistent set of correspondences with classic RANSAC. There are indeed a good amount of correspondences with rank 1. However, the outlier rate is in this case very large, and would call for a large number of iterations. In addition, the RANSAC process could be trapped by shifted patterns as illustrated in section 2.

Let us also remind that the a-contrario algorithm automatically adapts the thresholds to the complexity of the scene: in the Monkey image pair (1, 500 × 1, 200 images) δ G was derived as 3.1 pixels, in Loria (800 × 800 images) as 2.1 pixels and in Flat Iron (500 × 400 images) as 7.8 pixels. Using these values as distance threshold δ GR in Generalized RANSAC naturally yields similar results, but this parameter is hard to infer. 16 (756 vs 598.) Remark the strong perceptual aliasing in these pairs. As noted in figures 1 and 16 the NN-T+O method does not succeed at all in Loria and Flatiron experiments. Ranks larger than 2 are all the more frequent as the scene contains repeated patterns, and cannot be retrieved by the NN-T+O method, or any method limited to nearest neighbour matching. Repeated patterns and epipolar constraint. In this section, we test the behaviour of the AC algorithm under epipolar constraint. Since the epipolar constraint acts more "gently" than the homographic one (it is a point/line constraint), some false correspondences are simply unavoidable, as formalized by the double nail illusion of section 2.

Number of correspondences

Figure 17 shows a situation with a repetitive texture were almost no false correspondence. Small baseline matching gives good results thanks to the limited invariance of the descriptors. The nearest neighbour is more likely to be the correct one, unlike the larger baseline case shown in figure 4. However, as soon as the baseline grows, Generalized RANSAC as well as a-contrario matching gives false correspondences due to the confused distance between descriptors yielding interest points satisfying epipolar constraint "by chance". Large baseline matching is addressed in section 7.

Figure 18 shows the result of the AC method. It yields more correspondences than the NN-T+O method (not shown here, 92 vs 29), distributed in a denser fashion across the views. Nevertheless, a careful examination shows that many correspondences are not correct, in spite that the keypoints actually lie near their epipolar lines, because of the above-mentioned reason. This still permits an accurate estimation of the epipolar pencil. We select corresponding points (x, y) by hand in both views (especially in areas where almost no correspondence is retrieved with NN-T+O), and draw the associated epipolar lines. The line F x (resp. F T y) should meet the point y (resp. x.) Here F is re-estimated over the consensus set retrieved by NN-T+O or AC. The reestimation consists in minimizing the Sampson metric [START_REF] Hartley | Multiple View Geometry in Computer Vision[END_REF][START_REF] Zhang | Determining the epipolar geometry and its uncertainty: a review[END_REF].

In addition to the problem with false correspondences due to repeated patterns along epipolar lines, some point matching problems are very difficult to solve because the repeated patterns yield degenerate motion estimation, as explained in section 2. For example, in figure 19 one can see that the most meaningful group consists in wrong correspondences among points that match in a dominant plane along lines parallel to an edge of the cube. Let us also note that the stricter point-point constraint from the homography case (compare figure 19 to figure 15) enables to retrieve a consistent set, unlike in the epipolar constraint case. Figure 18: Loria building. AC method (epipolar constraint) between the top and bottom views. 92 correspondences can be seen. In particular, the repeated left-hand windows are all retrieved and not shifted. However, many "unavoidable" false correspondences are also retrieved, as the ones between the structures of the left-hand façade which are indeed shifted along the epipolar lines (compare to the position of the windows; the same phenomenon appears on the right-hand façade.) Nevertheless, one can see from the hand-picked correspondences (in yellow) that the associated (reestimated) epipolar lines are much closer. The distance is less than 5 pixels, except from one point on the parallelipedic structure on the foreground which is still at 15 pixels. It is logical to find a poorer accuracy on this structure since a very small amount of points is extracted from it, and since its apparent motion is quite different from the motion of the background. 7 Improving ASIFT with respect to repeated patterns As mentioned earlier, small baseline matching is quite easy even in the presence of repeated patterns since the nearest neighbour matching already gives good results. Large viewpoint changes are much more challenging. Several assessment papers [START_REF] Aanaes | Interesting interest points[END_REF][START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF][START_REF] Moreels | Evaluation of features detectors and descriptors based on 3D objects[END_REF] have extensively compared the most standard interest points / region descriptors, from SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] to Harris / Hessian Affine [START_REF] Mikolajczyk | Scale & affine invariant interest point detectors[END_REF] to MSER [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF]. Now, the authors of [START_REF] Moreels | Evaluation of features detectors and descriptors based on 3D objects[END_REF] conclude: "no detector/descriptor combination performs well with viewpoint changes of more than 25-30 • ." This is confirmed by the authors of a very recent survey [START_REF] Aanaes | Interesting interest points[END_REF]. All of these methods are thus prone to fail at a certain point. A more successful approach has been recently proposed by several authors (e.g. [START_REF] Lepetit | Keypoint recognition using randomized trees[END_REF][START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF]), in which viewpoint simulation is used to attain affine invariance. These papers demonstrate that this dramatically improves the number of matches between two views compared to MSER or Harris/Hessian Affine, especially with a strong viewpoint change.

In Morel and Yu's ASIFT [START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF], affine invariance of image descriptors is attained by remarking from Singular Value Decomposition that any affine mapping A (with positive determinant) can be decomposed as

A = λR ψ t 0 0 1 R φ (27)
where λ > 0, R ψ and R φ are rotation matrices, φ ∈ [0, 180 o ), t 1.

Since SIFT is scale and rotation invariant, a collection of affine invariant (ASIFT) descriptors of an image I is obtained by extracting SIFT features from the simulated images I t,φ with

I t,φ = t 0 0 1 R φ (I). (28)
Indeed, the location of the SIFT keypoints is virtually covariant with any scale and rotation change λR ψ applied to I t,φ , and the associated descriptor does not change.

From [START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF], it is sufficient to discretize t and φ as: The next step is to match ASIFT features between two images I and I ′ . A two-scale approach is proposed in [START_REF] Morel | ASIFT: A new framework for fully affine invariant image comparison[END_REF]. First, the I t,φ and I ′ t ′ ,φ ′ are generated from downsampled images (factor 3), then SIFT features extracted from each pair (I t,φ , I ′ t ′ ,φ ′ ) are matched via the standard algorithm from [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], namely that nearest neighbours are selected provided the ratio of the distance between the nearest and the second nearest is below some threshold. The deformations corresponding to the M pairs (M typically set to 5) that yield the largest number of matches are used on the full-resolution I and I ′ , giving new SIFT features that are matched by the same above-mentioned criterion. The interest points obtained from the correspondences are then placed in I and I ′ , provided already-placed correspondences are at a distance larger than √ 3. This strategy is used to limit the computational burden and also prevents redundancy between SIFT features from different deformations. A subsequent step consists in eliminating spurious correspondences with RANSAC by imposing epipolar constraints.

t ∈ {1, √ 2
Since ASIFT is based on nearest neighbour matching, it is subject to the curse of double nail illusion, as well as any nearest neighbour based algorithm. See figure 20. However, the idea behind ASIFT is that the world is locally planar, and since affine transformations are first order approximations of homographies, affine simulation is expected to ease the matching of features lying on the same 3D plane. Instead of Left: standard nearest neighbour matching. Right: ASIFT (software from [START_REF] Yu | ASIFT: An Algorithm for Fully Affine Invariant Comparison[END_REF]). Nearly all correspondences on the left façade are not correct, as well as a lot on the right. The a-contrario method has a similar behaviour (not shown.) The image pair is all the more difficult as the aspect of the left façade changes a lot between the two views. Image pair from the Zürich Building Database. using nearest neighbour matching without any geometric information, it seems natural to enforce homographic constraint. Actually, enforcing the homography constraint helps solving the double nail illusion, as explained in figure 21. Thus, we propose as a proof-of-concept to replace the nearest neighbour matching when comparing simulated images by a Generalized RANSAC (section 6.2.1) enforcing a homography constraint. Note that in [START_REF] Noury | How to overcome perceptual aliasing in ASIFT?[END_REF] the use of the presented a-contrario matching was investigated, and the authors of [START_REF] Brese | An improved ASIFT algorithm for matching repeated patterns[END_REF] have independently suggested to use graph matching. Nevertheless, graph matching does not explicitly enforce a geometric constraint.

Two images I and I ′ being given, the proposed Improved-ASIFT algorithm would consist in the following steps:

1. Generate the I t,φ and I ′ t ′ ,φ ′ (viewpoint simulation.) 2. Extract SIFT features from all simulated images.

3. Match SIFT features: for each pair from step 1, extract a group of correspondences with Generalized RANSAC enforcing the homography constraint. The algorithm here works at a fixed resolution, and thus do not take advantage of the multi-resolution scheme implemented in original ASIFT. The main difference is to RR n°7693 Figure 21: Adding homography constraint helps recovering from the double nail illusion. Compared to figure 5, adding a homography constraint between the interest points in the two views selects a single possibility. It comes down to imposing the relative positioning of the interest points from a view to the other one. Now, if one of the correspondences is seen as an outlier (marked as 'o' in the schemes), it is still possible to get (here) two shifted sets of correspondences which are equally plausible. In both cases, the three remaining correspondences are still consistent with the ordering imposed by the homography. However, this situation is possible if the subset of correspondences is only made of repeated patterns. In most realistic cases, non-repeated features incorporated in the group consistent with the homography help disambiguating the shifting.

replace in step 3 nearest neighbour matching by homography Generalized RANSAC. However, if there is a too dominant plane in the scene, then it is difficult to extract a consistent set of correspondences on a small piece of plane if the threshold δ GR is set to a small value. Therefore, δ GR is set here to, typically, 4-5 pixels. If some false correspondences are introduced here, they are likely to be discarded by step 5.

Figure 22 shows the result of improved ASIFT on a building image from the Zürich Building Database. Compared to image 20, we can see that the correspondences are this time correct.

In the very challenging image pair of figure 23 we are also able to get a lot of correspondences (all correct).

Figures 24 and25 show the correspondences obtained with two views from Oxford's house sequence. The baseline is quite large, and nearest neighbour approaches do not give any correspondence. With the improved ASIFT we are able to recover from the double nail illusion, while standard ASIFT yield many false correspondences between the chimneys and the white bricks over the windows. For the improved ASIFT we have hidden the textured background and ground in order to get rid of the problem with the dominant planes mentioned above.

Conclusion

In a discussion on the influence of repeated patterns on the two-view correspondence problem, we have emphasized the double nail illusion. We have designed an a-contrario model and a Generalized RANSAC for point matching which are both able to pick up correspondences beyond the nearest neighbours, permitting to get correct sets of correspondences in challenging situations. The a-contrario approach automatically balances in the NFA both photometric and geometric matching thresholds without any user intervention. It gives results similar to the Generalized RANSAC, but does not necessitate tuning various parameters.

The limited invariance of local image descriptors yield incorrect correspondences between repeated patterns when the viewpoint change is too strong. In this case, we have also explained how to improve ASIFT, yielding an algorithm robust to wide viewpoint changes, even with repetitive textures. We obtain more correspondences than in the standard SIFT matching which often simply fails. This can be helpful in e.g. object recognition (more correspondences means an increased confidence) or in structure and motion applications (for a denser 3D map.) However, the localization accuracy of these extra correspondences has still to be investigated, especially for ASIFT since they come from simulated views.

Figure 2 :

 2 Figure 2: Flatiron image pair. SIFT correspondences (nearest neighbour + distance ratio criterion). It is simply impossible to extract a consistent set of correspondences.

  Figure 5:The "multiple" nail illusion. We consider here two views of a 3D scene with repeated patterns. The image plane is represented between the optical center and the scene. Even if the two cameras are calibrated (and thus the epipolar constraints is known), some situations cannot be distinguished just from the information contained in the invariant descriptors. Here, the three black dots in both images are interest points with almost identical descriptors (because they correspond to repeated patterns), and since they lie on a common epipolar plane they can be associated in any of the six possibilities, yielding any of the six possible respective positions in the 3D scene (two are shown here.) Of course, only a single possibility is physically feasible. Let us remind that the scale associated with the interest points is not taken into account in the descriptor based matching.

Figure 6 :

 6 Figure 6: Trapped by the double nail illusion: examples. Correspondences here satisfy both descriptor similarity and epipolar constraints. However, many false correspondences can be seen (on the lower pair, correspondences can be seen with the fourth windows which is not visible in the first image), and the epipolar lines (in yellow) correspond to vanishing lines, yielding an incorrect camera pose estimation.

Figure 8 :

 8 Figure 8: Moisan and Stival's model[START_REF] Moisan | A probabilistic criterion to detect rigid point matches between two images and estimate the fundamental matrix[END_REF]: considering uniformly distributed points within an image I of size N x × N y , the probability that a point falls at a distance ≤ δ to a straight line with length L is approximately 2δL/(N x N y ). If D denotes the length of the diagonal of I and S its surface area, then S = N x N y and L ≤ D. Consequently, the probability is bounded from above by 2D/S • δ.

Figure 9 :

 9 Figure 9:log 10 (M (k, N ))/k vs k, for several values of N . This gives the order of magnitude of the logarithm of f D (δ D ) • f G (δ G ) so that it is still possible to find a 1-meaningful set of correspondences. (Best seen in color.)

1 .

 1 Use SIFT algorithm to extract interest points and (zoom+rotation / contrast change) invariant descriptors from each view: (x i , D(x i )) i∈{1,...N1} and (y j , D(y j )) j∈{1,...N2} . 2. For every i ∈ {1, . . . N 1 }, (a) build the empirical distance d D (section 4.3, equation (17)), (b) define a set of tentative correspondences (section 5.2.1.) 3. Iterate (N = 20, 000, see section 5.2.3):

Figure 15 :

 15 Figure 15: Monkey, homographic constraint. Two images with repeated patterns. On the left, the proposed AC model, most of the patterns lying on the dominant plane are detected (segments represent the apparent motion between the two views.) On the right, the second image but with correspondences from NN-T (both colors) and NN-T+O (inliers in blue, outliers in red.) Many more correspondences are retrieved with the AC algorithm. Generalized RANSAC gives similar results.

Figure 16 :

 16 Figure16: Flat Iron, homographic constraint. 13 matches can be found with AC method, all of them are correct. Here NN-T+O does not give any consistent group. Note the strong perceptual aliasing and the quite strong illumination and viewpoint changes.

Figure 17 :

 17 Figure 17: Corridor, epipolar constraint. AC method (left) retrieves 423 correspondences. 405 correspondences have rank 1, 13 rank 2, 2 rank 3, 1 rank 4, 1 rank 6, 1 rank 10. NN-T+O method (right) retrieves 295 out of 316 NN-T matches. The additional correspondences are on the carpet and on the wall. 1,269 keypoints were extracted from image 1, 1,360 from image 2. The Generalized RANSAC gives similar results.

Figure 19 :

 19 Figure 19: Monkey, epipolar constraint. Failure case study. The recovered geometry corresponds to the vanishing lines. In that case, the point / line constraint does not solve the ambiguity intrinsic to perceptual aliasing, and thus gives false correspondences. A few hand inserted points in red show the epipolar lines pencil, which corresponds to the pattern alignment along the vanishing lines, and not to the true motion. See the discussion of section 2.

, 2, 2 √ 2 ,

 22 4} and φ = {0, b/t, . . . , kb/t} with b = 72 o and k = ⌊t/b • 180 o ⌋.

Figure 20 :

 20 Figure 20: False correspondences due to repeated patterns and epipolar constraint.Left: standard nearest neighbour matching. Right: ASIFT (software from[START_REF] Yu | ASIFT: An Algorithm for Fully Affine Invariant Comparison[END_REF]). Nearly all correspondences on the left façade are not correct, as well as a lot on the right. The a-contrario method has a similar behaviour (not shown.) The image pair is all the more difficult as the aspect of the left façade changes a lot between the two views. Image pair from the Zürich Building Database.

4 .

 4 Keep only the matched SIFT keypoints from the I t,φ 's and I ′ t ′ ,φ ′ 's, among the N largest sets of correspondences.5. Discard possible false correspondences: epipolar RANSAC.The output is a set of corresponding points of interest.

Figure 22 :

 22 Figure 22: Improved ASIFT: Zürich Building. Improved ASIFT yields 151 correspondences, only 89 of them are nearest neighbours. The six largest set of correspondences retrieved by the homography Generalized RANSAC (coming from different pairs of simulated views) are shown on the top of the figure. They actually correspond to features lying on the same piece of plane.

Figure 23 :

 23 Figure 23: Improved ASIFT: cube. In this synthetic cube experiments, the two largest set of correspondences consistent with a homography are shown on the top. Each of them correspond to a side of the cube. On the bottom, 100 correspondences are shown (among a total of 324, only 142 are nearest neighbours.)

Figure 24 :

 24 Figure 24: Improved ASIFT: house. Top: the two largest set of correspondences consistent with a homography. Bottom: the 49 correspondences (only 33 are nearest neighbours.) The textured background and ground are hidden in this proof-of-concept experiment.

Figure 25 :

 25 Figure 25: ASIFT: house. ASIFT [65] gives here 104 correspondences; many of them are not correct because of the double nail illusion, e.g. between interest points on the two chimneys, or on the light-coloured bricks over the windows.

  [START_REF] Stein | Model-based brightness constraints: on direct estimation of structure and motion[END_REF] are not nearest neighbours): the influence of the geometry is now strengthen and the algorithm provides a larger group, which is now correct.

	α	Nb. of points geometry	photometry
			δ G in pixel log(δ D )
	1	149.2 (1.8)	.71 (.12)	-40.4 (.5)
	2	151.6 (3.8)	.70 (.14)	-39.5 (1.1)
	3	162.1 (8.1)	.58 (.12)	-33.6 (3.2)
	4	164.2 (5.2)	.49 (.13)	-30.5 (1.8)
	5	172.3 (10)	.46 (.11)	-26 (4.2)
	6	183.5 (6.2)	.49 (.09)	-21.2 (1.9)
	7	182.9 (5.3)	.47 (.10)	-20.7 (.48)
	8	183.7 (4.9)	.46 (.08)	-20.6 (.28)
	9	184.5 (4.5)	.46 (.08)	-20.5 (.28)
	10 185 (4.8)

Table 2 :

 2 Synthetic images. Influence of ε. From left-most column to right-most one:

	e ε	# tentative corr. # most meaning. group % of rank 1 corr.
	1	2027	219.5 (6.4)	76.1
	10 -2	1409	220.6 (4.9)	76.2
	10 -4	999	218.3 (3.9)	76.6
	10 -6	663	202.7 (3.0)	78.4
	10 -8	407	172.8 (2.8)	85.5
	10 -10	274	146.2 (2.2)	90.3

Table 3 :

 3 Number of occurrences of the n-th nearest neighbours selected by the AC method (homography case.) Monkey corresponds to figure 15 (412 vs 445 extracted keypoints), Loria to figure 1 (2,562 vs 2,686), Flat Iron to figure

	Rank Monkey Loria	Flat Iron
	1	42	98	8
	2	23	32	3
	3	17	29	1
	4	11	18	1
	5	8	20	0
	6	8	19	0
	7	4	11	0
	8	8	5	0
	9	3	13	0
	10	2	8	0
	11	0	15	0
	12	2	7	0
	>12	0	37	0
	Total	128	312	13

RR n°7693

9 Appendix: some proofs Proposition 3 Let N be an integer and let us note for every integer 7 ≤ k ≤ N :

Then the series (M (k, N )) k is increasing between k = 7 to k = k 0 , and decreasing for k ≥ k 0 , where

Proof: Computing the ratio between two consecutive terms,

This ratio is larger than 1 if and only if

is the smallest root of P . The second root is indeed larger than N , and k ≤ N .

This proposition justifies the remark just after proposition 2 (in the case

In the text, we also make use of the following classic proposition.

Proposition 4 If X is a real random variable and F is its cumulative distribution function, then for any non-negative real number x:

and the equality holds if F is continuous and increasing.

Proof: Let us denote F -1 (x) = arg inf t∈R {F (t) ≥ x}, which exists because F is non-decreasing. Then one can see that F (t) ≤ x if and only if t ≤ F -1 (x). Successively:

and the equality holds if F is continuous and increasing since in this case F -1 is the inverse of F .

Proof of the remark about d D in section 4.