HIERARCHICAL SHAPE DESCRIPTION BASED UPON CONVEX HULLS OF CONCAVITIES

A method for describing shape is discussed. The technique is specifically intended for use in the automatic visual inspection of flat industrial artifacts, where the shapes are normally very stable but occasionally defects are encountered which display either small overall changes or severe local changes. To represent a given shape, a treelike structure is derived in which the nodes represent convex polygons. The root of the tree is the convex hull of the figure. Nodes in the first level correspond to the convex hulls of the concavities; those in the second level are the convex hulls of metaconcavities, and so on. The generation of standardized trees is discussed so that tree/shape matching may be accomplished with a minimum of computational effort.