Next: The Scott and Longuet-Higgins Up: Uncalibrated Stereo Correspondence Previous: Introduction

The correspondence problem

Due to its inherent combinatorial complexity and ill-posedness, feature correspondence is one of the hardest low-level image analysis tasks. The problem can be stated as finding pairs of features in two (or more) perspective views of a scene such that each pair correspond to the same scene point.

Early works in this field was done notably by Ullman [ 12 ] and Marr and Poggio [ 4 ]. In particular, Ullman put forward his minimal mapping theory to implement three intuitive local criteria for establishing good global mapping , namely similarity , proximity (other things being equal, choose the closest) and exclusion (only one-to-one matchings are allowed). As Marr pointed out, by simple local interactions a good global mapping effect can often be achieved.

These early works were inspired by psychology and neurophysiology and indeed provided some new insight into our visual system too. Since then, a vast amount of work has been done on the subject (too many to cite here; for a review see [ 1 ], Ch. 6).

Most methods have a sometime complicate algorithmic formulation. For tasks such as estimating the fundamental matrix - where only a few tens of initial matches are needed - leaner methods would perhaps be more suitable.