Relaxation technique

 

Using these distances, the most natural process to achieve the matching is to select the pairs whose distance is lower than the one of all the possible pairs a nd . But this technique may eliminate a lot of matches which could have been good matches. So we keep only matches associated to small distances and we eliminate the possible remaining ambiguities by using a relaxation technique which works with semi-local constraints [16], [10], [14].

The rate of correct matches overshoots the most of the time, though matched images are very different (important rotations, different points of view, affine illumination transformations).

In order to deal with important sets of points and to obtain dense depth maps, we have also implemented a incremental version of this algorithm introducing geometric constraints:

• The epipolar constraint can be computed incrementally. At each iteration of the algorithm the matching process can be constrained using an epipolar geometry computed from the matches resulting of the preceding iteration. [16], [10] (of course, no constaint can be taken into account at the first iteration).
• A local semi-planarity constraints can be introduced with the help of an incremental Delaunay Tringulation [15], [2]. At each iteration of the algorithm the Delaunay Tringulation is updated.

The general idea pursued here is to begin with a small number of matches at the first iteration (typically hundred matches) in order to obtain a reliable starting point, then adding new points to be matched knowing geometric constraints. This way to proceed is robust and reduce greatly the computational time required for the whole matching process (scrore of comparison of invariant vectors and relaxation). For more details of this algorithm, the reader can refer to [5].