We consider model-based object localization based on local geometric feature matching between the model and the image data. The method is based on geometric constraint analysis, working in transformation space. We present a formal method which guarantees finding all feasible matchings in polynomial time. From there we develop more computationally feasible algorithms based on conservative approximations of the formal method. Additionally, our formalism relates object localization, affine model indexing, and structure from multiple views to one another.

This paper considers a model-based approach to identifying and locating known 3D objects in 2D images of a scene containing them via geometric feature matching of model and image data represented in terms of local geometric features. The problems of finding feature correspondences in the presence of geometric uncertainty, missing, and spurious data features are explicitly handled. The fundamentally geometric and combinatorial elements of the feature matching problem are made explicit, and a formulation based on computational geometry is used to achieve a polynomial-time matching approach for which the author can guarantee completeness and correctness. This paper deals primarily with the case of planar objects undergoing full 3D motion and scaled-orthographic projection.

We present several new geometric methods for relative stereo and motion reconstruction using a discrete set of point correspondences. We suppose that the epipoles are known but do not assume any knowledge of the cameras' intrinsic or extrinsic parameters. In each case, we choose a set of five points as a basis for projective space and perform reconstruction relative to these five points. We also present a new technique for reprojection without reconstruction. We have implemented the proposed methods and present several examples using real images.>

The author focuses on the central problem of image and model feature matching. In particular he defines a model of the geometrical uncertainty of image features, and devises a tractable algorithm for determining all feasible sets of feature correspondences given the uncertainty tolerances. A key insight into the matching problem provided by this work is that the search for a matching should be guided by analysis of (feasible) transformation space rather than the space of feature correspondences. This is because the author is only interested in maximal feasible match-sets and not the exponentially many subsets of them as found by correspondence space search.>

The authors describe several fundamentally useful primitive operations and routines and illustrate their usefulness in a wide range of familiar version processes. These operations are described in terms of a vector machine model of parallel computation. They use a parallel vector model because vector models can be mapped onto a wide range of architectures. They also describe implementing these primitives on a particular fine-grained machine, the connection machine. It is found that these primitives are applicable in a variety of vision tasks. Grid permutations are useful in many early vision algorithms, such as Gaussian convolution, edge detection, motion, and stereo computation. Scan primitives facilitate simple, efficient solutions of many problems in middle- and high-level vision. Pointer jumping, using permutation operations, permits construction of extended image structures in logarithmic time. Methods such as outer products, which rely on a variety of primitives, play an important role of many high-level algorithms.>

An approach to 2D model-based object recognition is developed, suitable for implementation on a highly parallel SIMD (single-instruction, multiple data stream) computer. Object models and image data are represented as contour features. Transformation sampling is used to determine the optimal model-feature-to-image-feature transformation by sampling the space of possible transformations. Only a small part of this space need actually be sampled due to the constraints placed on transformations by individual matches of image features to model features. The procedure requires O(Kmn) processors and O(log/sup 2/ (Kmn)) time, where m is the number of model features, n is the number of image features, and K depends on the size of the image. The procedure works well and is extremely robust in the presence of occlusion. An implementation of the procedure on the Connection Machine is described, and some experimental results given.>