Attributed hypergraph representation and recognition of 3-d objects for computer vision

This thesis presents a robot vision system which is capable of recognizing objects in a 3-D scene and interpreting their spatial relation even though some objects in the scene may be partially occluded by other objects. In my system, range data for a collection of 3-D objects placed in proximity is acquired by laser scanner. A new algorithm is developed to transform the geometric information from the range data into an attributed hypergraph representation (AHR). The AHR is a unique representation of 3-D object which is invariant to orientation. A hypergraph monomorphism algorithm is used to compare the AHR of objects in the scene with the complete AHR of a set of prototypes in a database. Through a hypergraph monomorphism, it is possible to recognize any view of an object and also classify the scanned objects into classes which consist of similar shapes. The system can acquire representation for unknown objects. Several AHR's of the various views of an unknown object can be synthesized into a complete AHR of the object which can then be included in the model database. A scene interpretation algorithm is developed to locate and recognize objects in the scene even though some of them are partially occluded. The system is implemented in PASCAL on a VAX11/750 running VMS, and the image results are displayed on a Grinnell 270 display device.