Morphological decomposition of 2-D binary shapes into convex polygons: A heuristic algorithm

In many morphological shape decomposition algorithms, either a shape can on ly be decomposed into shape components of extremely simple forms or a time consuming search process is employed to determine a decomposition. In this paper, we present a morphological shape decomposition algorithm that decomp oses a two-dimensional (2-D) binary shape into a collection of convex polyg onal components. A single convex polygonal approximation for a given image is first identified. This first component is determined incrementally by se lecting a sequence of basic shape primitives. These shape primitives are ch osen based on shape information extracted from the given shape at different scale levels. Additional shape components are identified recursively from the difference image between the given image and the first component. Simpl e operations are used to repair certain concavities caused by the set diffe rence operation. The resulting hierarchical structure provides descriptions for the given shape at different detail levels. The experiments show that the decomposition results produced by the algorithm seem to be in good agre ement with the natural structures of the given shapes. The computational co st of the algorithm is significantly lower than that of an earlier search-b ased com ex decomposition algorithm. Compared to nonconvex decomposition al gorithms, our algorithm allows accurate approximations for the given shapes at low coding costs.