Ordered structural shape matching with primitive extraction by mathematical morphology

摘要

Structural shape matching procedures begin by decomposing the shapes to be matched into primitive parts, and extracting the properties of and relationships among these primitives. The resultant structural descriptions are matched to structural models, usually via a tree search whose time is exponential in the number of primitives. In this paper we introduce a new fast method of structural shape matching called ordered structural matching, which has polynomial time complexity instead of exponential. The approach presented also uses mathematical morphology to rapidly decompose the shapes into primitives to be used in the matching. The primitives so produced are pieces of the original shape, but not necessarily those pieces that a human would select. The method has been tested on the toy task of determining which plastic shapes match the shapes of the holes in a child's six sided toy box. It is also directly applicable to the inspection and manipulation of certain airplane parts.