Noise-resistant Digital Euclidean Connected Skeleton for graph-based shape matching

• We propose a propagation algorithm to obtain a skeleton with “good properties”.
• Our algorithm combines RDMA and Laplacian of Gaussian filtering.
• The complexity is linearly proportional to the number of pixels of image.
• Our method is compared to three existing methods.

The skeleton is an essential shape descriptor providing a compact representation of a shape that can be used in the context of real object recognition. However, due to the discretization, the required properties to use it for graph matching (homotopy to the shape, consequently connectivity, thinness, robustness to noise) may be difficult to obtain simultaneously. In this paper, we propose a new skeletonization algorithm having all these properties, based on the Euclidean distance map. More precisely, the algorithm cleverly combines the centers of maximal balls included in the shape and the ridges of the distance map. Post-processing is then applied to thin and prune the resulting skeleton. We compare the proposed method to three fairly recent methods and demonstrate its good properties.