Next: The correspondence problem Up: Uncalibrated Stereo Correspondence Previous: Uncalibrated Stereo Correspondence

Introduction

The problem of feature correspondence across two or more images is well known to be of crucial importance for many images analysis tasks. Reliable inter-image feature correspondence - and its closely related problem of image registration - is needed, just to cite a few, by structure-from-stereo approaches, motion analysis and tracking, image mosaicing, object pose and self-motion estimation.

Recently, there has been a boost of interest in the correspondence estimation problem due to the development of the Fundamental Matrix theory [ 3 ] and its tremendous practical implications in the analysis of uncalibrated stereo pairs and image sequences. If the fundamental matrix is known, reliable and fast feature correspondence can be obtained in general situations. However, in order for the fundamental matrix to be computed, one needs a good initial set of feature correspondences (either lines, points or both [ 11 ]).

There are two schools of thought for solving the feature correspondence problem. In the first one, features are detected in one image and then correspondences for each of them are sought for in the second image, generally via multi-scale techniques. In the second approach, which the present work addresses, features are detected independently in both images and then matched up usually by relaxation (see, e.g., the classic [ 6 ]). Incidentally, recent state-of-the-art work on the fundamental matrix estimation [ 14 , 11 ] follows this latter avenue for achieving initial correspondences.

This paper proposes a new neat and simple algorithm for achieving feature correspondence across pairs of images. Despite the well-known combinatorial complexity of the problem, this work shows that an acceptably good solutions can be obtained directly by singular value decomposition of an appropriate correspondence strength matrix.

The approach is largely inspired by the clever algorithm proposed by Scott and Longuet-Higgins for finding corresponding features in planar point patterns [ 8 ], which has been overlooked in this area, probably because of intrinsic limitations in its ``pure'' form. This paper shows that by using a new mixed geometric and intensity-based correspondence strength function, the method becomes of practical use as general-purpose, robust uncalibrated feature matching method. Experimental evidence is presented and discussed along with some proposed enhancements.