The recognition technique is based on the the assumption that robustly extractable, semi-invariant key features, which are subsequently verified in local context, can be efficiently recovered from image data. More specifically, the keys must posses the following characteristics. First, they must be complex enough not only to specify the configuration the object, but to have parameters left over that can be used for indexing. Second, the keys must have a substantial probability of detection if the object containing them occupies the region of interest (robustness). Third, the index parameters must change relatively slowly as the object configuration changes (semi-invariance). From a computational standpoint, true invariance is desirable, and a lot of research has gone into looking for invariant features. Unfortunately, such features seem to be hard to design, especially for 2-D projections of general 3-D objects. Many classical features do not satisfy these criteria. Line segments are not sufficiently complex, full object contours are not robustly extractable, and simple templates are not semi-invariant.
A basic conflict that must be resolved is that between feature complexity and robust detectability. In order to reduce multiple matches, key features must be fairly complex. However, if we consider complex features as arbitrary combinations of simpler ones, then the number of potential high-level features undergoes a combinatorial increase as the complexity increases. This is clearly undesirable from the standpoint of robust detectability, as we do not wish to consider or store exponentially many possibilities. The solution is not to use arbitrary combinations, but to base the higher level feature groups on structural heuristics such as adjacency and good continuation. Such perceptual grouping processes have been extensively researched in the last few years. The additional distinctiveness needed to reduce multiple matches is obtained via the local verification process once the keys have been extracted.
Our current implementation is designed to recognize 3-D objects on the basis of their shape, using a set of 2-D views as the underlying representation. The features used in the current system are based on automatically extracted contours. Specifically, a curve-finding algorithm. is run on an image, producing a set of segmented contour fragments broken at points of high curvature. The strongest curves are selected as key features, and these are embbedded in a local context consisting of a fixed-size template constructed with the endpoints of the base curve occupying canonical points in the template. All image curves that intersect the normalized template are mapped into it with a code specifying their orientation relative to the base curve. Global properties such as total curvature and compactness of the base curve serve as initial index parameters into the database. The local contextual verification of a candidate template involves taking the model template curve points and verifying that a curve point with similar orientation lies nearby in the candidate template. Essentially this amounts to directional correlation.
Back to recognition page
Back to Randal Nelson's home page