Self-organizing maps for the skeletonization of sparse shapes

This paper presents a method for computing the skeleton of planar shapes an d objects which exhibit sparseness (lack of connectivity), within their ima ge regions. Such sparseness in images may occur due to poor lighting condit ions, incorrect thresholding or image subsampling. Furthermore, in document image analysis, sparse shapes are characteristic of texts faded due to agi ng and/or poor ink quality. Due to the lack of pixel level connectivity, co nventional skeletonization techniques perform poorly on such (sparse) shape s. Given the pixel distribution for a shape, the proposed method involves a n iterative evolution of a piecewise-linear approximation of the shape skel eton by using a minimum spanning tree-based self-organizing map (SOM). By c onstraining the SOM, to lie on the edges of the Delaunay triangulation of t he shape distribution, the adjacency relationships between regions in the s hape are detected and used in the evolution of the skeleton. The SOM, on co nvergence, gives the final skeletal shape. The skeletonization is invariant to Euclidean transformations. The potential of the method is demonstrated on a variety of sparse shapes from different application domains.