The Representation, Recognition, and Locating of 3-D Objects

The problem of recognizing and locating rigid objects in 3-D space is important for applications of robotics and naviga tion. We analyze the task requirements in terms of what information needs to be represented, how to represent it, what kind of paradigms can be used to process it, and how to implement the paradigms. We describe shape surfaces by curves and patches, which we represent by linear primitives, such as points, lines, and planes. Next we describe algo rithms to construct this representation from range data. We then propose the paradigm of recognizing objects while locat ing them. We analyze the basic constraint of rigidity that can be exploited, which we implement as a prediction and verifi cation scheme that makes efficient use of the representation. Results are presented for data obtained from a laser range finder, but both the shape representation and the matching algorithm are general and can be used for other types of data, such as ultrasound, stereo, and tactile.