A geometrical approach to model-based vision
Michael Joseph Hopcroft · 1996
This dissertation addresses the problem of recognizing a rigid, planar object described by straight line segments. We would like to determine whether an image contains one or more instances of the object, and if so, report their positions in the image. By modeling the camera as a device that produces an image by applying a scaled orthographic projection to coordinates in the world, we can formulate the problem as one of finding a correspondence between model and image features that is consistent with an affine transformation of the object. To operate reliably, the system must deal with cluttered scenes and poor image quality. In particular, it must not fail when the object in question is partially obscured by other objects. It should not be sensitive to spurious, fragmented, or missing features, and it must accommodate positional errors introduced in the imaging process. Previous approaches have enumerated matchings between model and image features. These approaches suffer from a number of problems. Some systems enumerate matchings which cannot correspond to any pose of the object. Others visit the same matching multiple times. Finally, most systems do not explicitly model positional uncertainty and consequently, cannot guarantee that every instance will be identified. The primary contribution of this work is a combinatorial algorithm that enumerates only those matchings consistent with scaled orthographic projections of the model. The set of consistent matchings is shown to be significantly less complex than the set of all matchings. Searching the set of consistent matchings yields an algorithm guaranteed to detect every instance of an object in a cluttered scene, even in the presence of partial occlusion, feature fragmentation, and positional error. An additional contribution is a recognition system running on a workstation. At the core of the system is a fast and numerically robust implementation of an algorithm that constructs the planar subdivision defined by the boundaries of a set of polygons. Previous implementations of this algorithm were either slow, because they used variable precision arithmetic, or unreliable, because of floating point errors. My implementation, which uses fixed precision arithmetic, has many uses outside of vision.