Extraction of the Euclidean skeleton based on a connectivity criterion

Wai Pak Choi, Kin Man Lam, Wan Chi Siu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The skeleton is essential for general shape representation. The commonly required properties of a skeletonization algorithm are that the extracted skeleton should be accurate; robust to noise, position and rotation; able to reconstruct the original object; and able to produce a connected skeleton in order to preserve its topological and hierarchical properties. However, the use of a discrete image presents a lot ofproblems that may influence the extraction of the skeleton. Moreover, most ofthe 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 is proposed, which can be used to determine whether a given pixel is a skeleton point independently. The criterion is based on a set of point pairs along the object boundary, which are the nearest contour points to the pixel under consideration and its 8 neighbors. Our proposed method generates a connected Euclidean skeleton with a single pixel width without requiring a linking algorithm or iteration process. Experiments show that the runtime of our algorithm is faster than the distance transformation and is linearly proportional to the number of pixels ofan image.
Original languageEnglish
Pages (from-to)721-729
Number of pages9
JournalPattern Recognition
Volume36
Issue number3
DOIs
Publication statusPublished - 1 Mar 2003

Keywords

  • Distance transform
  • Maximal disk
  • Medial axis transform
  • Skeletonization

ASJC Scopus subject areas

  • Computer Vision and Pattern Recognition
  • Signal Processing
  • Electrical and Electronic Engineering

Cite this