This paper presents a method for computing the skeleton of planar shapes and objects which exhibit sparseness (lack of connectivity), within their image regions. Such sparseness in images may occur due to poor lighting conditions, incorrect thresholding or image subsampling. Furthermore, in document image analysis, sparse shapes are characteristic of texts faded due to aging and/or poor ink quality. Due to the lack of pixel level connectivity, conventional skeletonization techniques perform poorly on such (sparse) shapes. Given the pixel distribution for a shape, the proposed method involves an iterative evolution of a piecewise-linear approximation of the shape skeleton by using a minimum spanning tree-based self-organizing map (SOM). By constraining the SOM to lie on the edges of the Delaunay triangulation of the shape distribution, the adjacency relationships between regions in the shape are detected and used in the evolution of the skeleton. The SOM, on convergence, 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.
Bibliographical noteFunding Information:
Manuscript received December 1, 1998; revised August 27, 1999. This work was supported by the NSF under Grants IRI-9410003 and IRI-9502245. R. Singh and N. P. Papanikolopoulos are with the Artificial Intelligence, Robotics, and Vision Laboratory, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455 USA. V. Cherkassky is with the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA. Publisher Item Identifier S 1045-9227(00)01198-X.