FEG STRUCTURES FOR REPRESENTATION AND RECOGNITION OF 3-D POLYHEDRAL OBJECTS

The paper proposes a fast O (n(2.5)) recognition algorithm for partial ly occluded 3D polyhedral objects, where n is the number of the polyhe dron vertices. Our approach is based on the generate and test mechanis m using the alignment approach as its basic recognition tool. The firs t stage is to align one face of the unknown polyhedron with one face o f one library model (generate). The second stage is a recursive test p rocedure that checks the matching of the remaining faces. A new struct ure called FEG-Face Edge Graph is introduced. This structure stores in formation about the 2D coordinates of each face and the identity of it s adjacent faces. A very low complexity is achieved by using a divide and conquer strategy. Instead of trying to recognize the whole object at once, we divide it and conquer (recognize) it face by face. This is done by reducing the recognition problem to generalized subgraph matc hing problem in which two subgraphs are equal not only when they are i somorphic, but also when they represent the same part of the same obje ct. A special mechanism handles false splitting and false merging of a djacent faces as a result of wrong segmentation. The process lends its elf to hierarchical parallel processing in that the matching with each library model may be carried out independently, and also for each mod el-processing at the pixel level may also be done in parallel. We eval uated our approach with several real range data images as well as some synthetic objects. Four of these cases are reported here.