Hierarchical Decomposition of Multi-Scale Skeletons

This paper presents a new procedure to hierarchically decompose a multi-scale discrete skeleton. The skeleton is a linear pattern representation that is generally recognized as a good shape descriptor. For discrete images, the discrete skeleton is often preferable. Multi-resolution representations are convenient for many image analysis tasks. Our resulting skeleton decomposition shows two different types of hierarchy. The first type of hierarchy is one of different scales, as the original pattern is converted into an AND-pyramid and the skeleton is computed for each resolution level. The second type of hierarchy is established at each level of the pyramid, by identifying and ranking skeleton subsets according to their permanence, where permanence is a property intrinsically related to local pattern thickness. To achieve the decomposition, both bottom-up and top-down analysis, in the sense of moving from higher to lower resolution, and vice versa, are used. The bottom-up analysis is used to ensure that a part of the skeleton that is connected at a higher resolution level is also connected (if at all present) in the next, lower resolution level. The top-down analysis is used to build the permanence hierarchy ranking the skeleton components. Our procedure is based on the use of (3x3) local operations in digital images, so it is fast and easy to implement. This skeleton decomposition procedure is most effective on patterns having different thickness in different regions. A number of examples of decompositions of multi-scale skeletons (with and without loops) will be shown. The skeletons are, in most cases, nicely decomposed into meaningful parts. The procedure is general and not limited to any specific application.