An efficient algorithm for the extraction of a Euclidean skeleton

Abstract

The skeleton is essential for general shape representation but the discrete representation of an image presents a lot of problems that may influence the process of skeleton extraction. Some of the methods are memory-intensive and computationally intensive, and require a complex data structure. In this paper, we propose a fast, efficient and accurate skeletonization method for the extraction of a well-connected Euclidean skeleton based on a signed sequential Euclidean distance map. A connectivity criterion that can be used to determine whether a given pixel inside an object is a skeleton point is proposed. The criterion is based on a set of points along the object boundary, which are the nearest contour points to the pixel under consideration and its 8 neighbors. The extracted skeleton is of single-pixel width without requiring a linking algorithm or iteration process. Experiments show that the runtime of our algorithm is faster than those of using the distance transformation and is linearly proportional to the number of pixels of an image.