Multi-view correspondence by enforcement of rigidity constraints

Establishing the correct correspondence between features in an image set remains a challenging problem amongst computer vision researchers. In fact, the combinatorial nature of feature matching effectively hinders the solution of large scale problems, which have direct applications in important areas such as 3D reconstruction and tracking.The solution is obtained by imposing a geometric constraint – rigidity – that selects the matching solution resulting in a rank-4 observation matrix. Since this is a global criterion, issues usually associated to local matching algorithms (such as the aperture problem) do not present an obstacle in this case. The use of a geometric constraint of this type assumes that all feature points are visible in every image, so as to obtain a complete observation matrix.The rank of the observation matrix is a function of the matching solutions associated to each image and as such a simultaneous solution for all frames has to be found. For each frame, correspondence is modeled through a permutation matrix, which also allows for the rejection of wrong candidates. Although each image is matched individually, an iterative algorithm is used to integrate correspondence information associated to all remaining images. Each individual matching process results in a linear problem: the reduced computational complexity allows the solution of large problems in an acceptable time interval.Although the algorithm has intrinsically been designed for calibrated systems, some instances of the uncalibrated case can also be solved provided a convenient bootstrap is available.