Morphological decomposition of 2-d binary shapes into modestly overlapped octagonal and disk components

One problem with several leading morphological shape representation algorithms is the heavy overlapping among the representative disks of the same size. A shape component formed by grouping connected disk centers may use many heavily overlapping disks to represent a simple shape part. Sometimes, these representative disks form complicated structures. A generalized skeleton transform was recently introduced which allows a shape to be represented as a collection of modestly overlapped octagonal shape parts. However, the generalized skeleton transform needs to be applied many times. Furthermore, an octagonal component is not easily matched up with another octagonal component. In this paper, we describe a octagon-fitting algorithm which identifies a special maximal octagon for each image point in a given shape. This transform leads to the development of two new shape decomposition algorithms. These algorithms are more efficient to implement; the octagon-fitting algorithm only needs to be applied once. The components generated are better characterized mathematically. The disk components used in the second decomposition algorithm are more primitive than octagons and easily matched up with other disk components from another shape. The experiments show that the new decomposition algorithms produce as efficient representations as the old algorithm for both exact and approximate cases. A simple shape-matching algorithm using disk components is also demonstrated.