Recognizing 3-D objects using surface descriptions

The authors provide a complete method for describing and recognizing 3-D objects, using surface information. Their system takes as input dense range date and automatically produces a symbolic description of the objects in the scene in terms of their visible surface patches. This segmented representation may be viewed as a graph whose nodes capture information about the individual surface patches and whose links represent the relationships between them, such as occlusion and connectivity. On the basis of these relations, a graph for a given scene is decomposed into subgraphs corresponding to different objects. A model is represented by a set of such descriptions from multiple viewing angles, typically four to six. Models can therefore be acquired and represented automatically. Matching between the objects in a scene and the models is performed by three modules: the screener, in which the most likely candidate views for each object are found; the graph matcher, which compares the potential matching graphs and computes the 3-D transformation between them; and the analyzer, which takes a critical look at the results and proposes to split and merge object graphs