3D Object Recognition by VC-graphs and Interactive Constraint Satisfaction

We propose a novel approach for recognizing 3D CADmade objects in complex range images containing several overlapped and different objects. Objects are modeled by a graph whose nodes are surfaces and arcs are surface relations. We propose an object-centered graph model, called Visual Constraint graph (VC-graph), with special visual constraints modeling occlusions between object surfaces. The VC-graph is used for recognizing objects from each possible point of view, instead of evaluating many different single-view graphs. The reasoning engine is based on an original extension of the Constraint Satisfaction Problem (CSP) paradigm, called Interactive CSP (ICSP). CSP requires the acquisition of all surfaces before starting constraint propagation; instead, ICSP guides the acquisition of new surfaces only on-demand, without computing useless information and focussing attention only on significant image parts.