Generation of the Euclidean skeleton from the vector distance map by a bisector decision rule

The Euclidean skeleton is essential for general shape representation. This paper provides an efficient method to extract a well-connected Euclidean skeleton by a neighbor bisector decision (NBD) rule on a vector distance map. The shortest vector which generates a pixel's distance is stored when calculating the distance map. A skeletal pixel is extracted by checking the vectors of the pixel and its 8 neighbors. This method succeeds in generating a well-connected Euclidean skeleton without any linking algorithm. A theoretical analysis and many experiments with images of different sizes also shows the NBD rule works excellent. The average complexity of the method with the NBD rule algorithm and the vector distance transform algorithm is linear in the number of the pixels.