Recognition of object classes from range data

We develop techniques for recognizing instances of 3D object classes (which may consist of multiple and/or repeated sub-parts with internal degrees of freedom, linked by parameterized transformations), from sets of 3D feature observations. Recognition of a class instance is structured as a search of an interpretation tree in which geometric constraints on pairs of sensed features not only prune the tree, but are used to determine upper and lower bounds on the model parameter values of the instance. A real-valued constraint propagation network unifies the representations of the model parameters, model constraints and feature constraints, and provides a simple and effective mechanism for accessing and updating parameter values. Recognition of objects with multiple internal degrees of freedom, including non-uniform scaling and stretching, articulations, and sub-part repetitions, is demonstrated and analysed for two different types of real range data: 3D edge fragments from a stereo vision system, and position/surface normal data derived from planar patches extracted from a range image. © 1995.