Fast affine point matching: an output-sensitive method

A model-based recognition method that runs in time proportional to the actual number of instances of a model that are found in an image is presented. The key idea is to filter out many of the possible matches without having to explicitly consider each one. This contrasts with the hypothesize-and-test paradigm, commonly used in model-based recognition, where each possible match is tested and either accepted or rejected. For most recognition problems the number of possible matches is very large, whereas the number of actual matches is quite small, making output-sensitive methods such as this one very attractive. The method is based on an affine invariant representation of an object that uses distance ratios defined by quadruples of feature points. A central property of this representation is that it can be recovered from an image using only pairs of feature points