Extraction of the Euclidean skeleton based on a connectivity criterion

doi:10.1016/S0031-3203(02)00098-5

Pattern Recognition

Volume 36, Issue 3, March 2003, Pages 721-729

https://doi.org/10.1016/S0031-3203(02)00098-5 Get rights and content

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 of problems that may influence the extraction of the skeleton. Moreover, most 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 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 of an image.

Introduction

The skeleton is essential for general shape representation. It is a useful means of shape description [1] in different areas, such as content-based image retrieval systems, character recognition systems, circuit board inspection systems, as well as biomedical imagery for shape analysis. The extracted skeleton can be used as a feature to represent the original shape as it has a more compact representation. In real-time image processing, a fast skeletonization algorithm is necessary.

Due to the importance of skeletonization, many approaches for it have been proposed throughout the past decades. Most of the skeletonization algorithms can be simply classified into two essential types. The first type is referred to as thinning algorithms, such as shape thinning [2], [3], [4], [5] and the wave front/grassfire transform [6], [7]. These algorithms iteratively remove border points, or move to the inner parts of an object in determining an object's skeleton. However, the iterative process is a time-consuming operation and requires some terminating criteria. In addition, the uniqueness of the extracted skeleton may be dependent on the initial conditions provided. The second type of algorithm is based on the medial-axis transform, as introduced by Blum [1]. Examples include the line skeleton [8], [9], [10], Voronoi skeleton [11], [12], morphological transform [13], [14], [15], and maximal disk method [16], [17], [18], [19]. As these algorithms search the set of centers and the corresponding radii of the maximal disks contained in an object, they can usually preserve all the information about the object and allow the reconstruction of the object. Although the medial axis transform is a very useful tool and yields an intuitively pleasing skeleton, its direct implementation is usually computationally prohibitive. Moreover, due to the use of discrete space, the extracted skeletons are sensitive to local variations and noise, and there is no guarantee that the extracted medial-axis can preserve the original object's topology. In addition, these algorithms may produce redundant points on determination of the skeleton, and are memory-intensive and require a complex data structure.

In order to efficiently find the maximal disks enclosed in an object, a distance map should be generated before locating the centers of the maximal disks. Different algorithms based on different distance maps have been proposed. Approximate distance maps such as the city-block, chessboard, chamfer distance transform (CDT) [20], etc. can be used to extract the maximal disks. An exact Euclidean distance map can be obtained by using the Euclidean distance. The corresponding skeleton, namely the Euclidean skeleton, is invariant to rotation. However, the Euclidean skeleton will include much more computation due to the square root operation. This problem can be solved by means of the vector distance transform (VDT) [21]. Two sequential Euclidean distance (SED) mapping algorithms, called 4SED and 8SED, have been proposed for the efficient computation of the Euclidean distance map. The signed sequential Euclidean distance (8SSED) [22] mapping algorithm is an extension of the 8SED, which keeps track of the sign component of the vectors. Consequently, this algorithm can greatly reduce the time required to create the distance map. Not only is the shortest distance to the object's boundary determined, but the position of the corresponding point on the boundary is also provided.

Extracting the centers of the maximal disks (CMDs) using a distance map is also complicated. Many algorithms have been proposed for extracting the true CMDs by using different types of distance map. In order to reduce the required runtime, some fast algorithms [16], [18] have been proposed, but they produce some false CMDs. Ge et al. [19] proposed a bounding box-based algorithm followed by an exhaustive search, which is significantly faster than simply using the exhaustive search. However, the algorithm is still rather slow for large objects. Furthermore, the centers of the maximal disks are, in general, not connected because the discrete distance map is used. Some points should be added between the centers of the maximal disks with a linking algorithm, so that the connectivity of the skeleton can be preserved. As this linking process may affect the uniqueness of the skeleton, it is limited to being used for compression purposes.

The connectivity of a skeleton is one of the important concerns for the skeletonization algorithms. Analytically, the boundary of a planar shape can be assumed to be composed of a finite number of real analytic curves. The continuity and path-connectedness of a skeleton can be proven by using the domain decomposition lemma [23]. In this lemma, a planar shape is continuously broken up into simpler pieces that are represented by the maximal disks. The centers of the disks are connected, and so is the skeleton. In the discrete case, it is assumed that the planar shape can be represented by polygons. With the use of the Voronoi diagram [11], [12], a continuous skeleton can also be obtained analytically by the relationship between the skeleton and the Voronoi diagram. In Ref. [10], it is shown that each Voronoi diagram is path-connected and the skeleton is a sub-graph of the Voronoi diagram, so the connectivity of the skeleton is preserved. Consequently, both the continuity and the path-connectedness of a skeleton in discrete and continuous representations have been proven theoretically. However, there is no connectivity criterion for the extraction of the skeleton for efficient implementation.

An abundant amount of work on skeletonization and its application has been conducted, in which a profound theoretical background of the skeleton from different aspects has been provided. The properties of the skeleton, including its thickness, connectivity and reconstructability, have been investigated. In this paper, we propose a new skeletonization algorithm, which is fast, efficient and accurate, to extract a well-connected Euclidean skeleton based on a signed sequential Euclidean distance map. By using the connectivity criterion proposed in this paper, a skeleton point can be determined efficiently and independently by considering a set of points along the object's boundary, which are the nearest contour points to the pixel under consideration and its 8 neighbors.

This paper is organized as follows. In Section 2, skeletonization based on the maximal disk is introduced and the definition of the medial axis transform is provided. Section 3 deals with the effect of discrete problems on the extraction of the skeleton. The concept of the width of a skeleton is established. The connectivity criterion for extracting a skeleton using the Euclidean metric is then proposed. Then, the algorithm is used to resolve different types of boundary segments. Section 4 illustrates and summarizes the implementation of the skeletonization algorithm. Finally, the experimental results and the conclusion are given in 5 Experimental results, 6 Conclusions, respectively.

Section snippets

Skeleton based on the maximal disk

Suppose that the contour C of an object in an image is represented by a continuous closed curve. Inside the contour C, the planar shape F represents the content of the object. The corresponding skeleton S can be determined, as shown in Fig. 1. According to Blum's definition [1], the skeleton S of a planar shape is defined as the locus of the centers of the maximal disks contained inside the planar shape F. The medial axis transform can then be defined as follows:

Definition 1

The medial axis transform is the

The width of skeleton

An ideal skeleton is connected and has zero width. A continuous boundary will produce a path-connected skeleton [23]. However, in real applications, the contour points and the skeleton points must be located at the pixel grids; this induces a lot of discrete problems. The skeleton may not pass through the pixel exactly. Hence, in practice, the skeleton has a non-zero width and all the pixels passed through by the ideal skeleton will be considered to be skeleton pixels. Consider a skeleton point

The skeletonization algorithm

To determine whether a pixel point is a skeleton point, the corresponding nearest contour point for each of the 8 neighboring points will be determined, and the connectivity criterion will then be applied to this set of 8 contour point pairs. The relative positions of the nearest contour points for each pixel can be obtained by using the signed sequential Euclidean distance (8SSED) map. The nearest contour points for each of the 8 neighboring points of the point under consideration can be

Experimental results

In the experiment, the shapes in an image can be extracted by using a contour extraction method called the adaptive snake method [25] or any edge follower method. Based on the extracted contours, the skeletons of the shapes are extracted using our proposed algorithm. The skeletonization performance and the complexity of our proposed algorithm are evaluated in this section. The effect of the threshold values ρ on the extraction of a skeleton will be illustrated. Then, the complexity of our

Conclusions

With the use of the connectivity criterion proposed in this paper, an accurate, simple and efficient algorithm for the extraction of a well-connected Euclidean skeleton is devised with the use of the signed sequential Euclidean distance map. The nearest contour points of the pixel under consideration and its 8 neighbors are generated to form a set of 8 point pairs, which are then used to determine whether the pixel is a skeleton point. This method can generate a connected Euclidean skeleton

About the Author—WAI-PAK CHOI received his B.Eng. in Electronic Engineering from the City University of Hong Kong in 1992. He is now a Ph.D. student in the Department of Electronic and Information Engineering, The Hong Kong Polytechnic University. His research interests are in the areas of image processing and pattern recognition.

References (26)

H Blum et al.
Shape description using weighted symmetric axis features
Pattern Recognition
(1978)
S.S.O Choy et al.
Notenew single-pass algorithm for parallel thinning
Comput. Vision Image Understanding
(1995)
F.L Bookstein
The line skeleton
CGIP
(1979)
R.L Ogniewicz et al.
Hierarchic Voronoi skeletons
Pattern Recognition
(1995)
J.W Brandt et al.
Continuous skeleton computation by Voronoi diagram
CVGIP: Image Understanding
(1992)
P.E Trahanias
Binary shape recognition using the morphological skeleton transform
Pattern Recognition
(1992)
C Arcelli et al.
Euclidean skeleton via centre-of-maximal-disc extraction
Image Vision Comput.
(1993)
R Kimmel et al.
Skeletonization via distance maps and level sets
Comput. Vision Image Understanding
(1995)
F Nilsson et al.
Notefinding the minimal set of maximum disks for binary objects
Graphical Models Image Process.
(1997)
P.E Danielsson
Euclidean distance mapping
Comput. Graphics Image Process.
(1980)

W.P Choi et al.

An adaptive contour model for highly irregular boundaries

Pattern Recognition

(2001)

D Shaked et al.

Pruning medial axes

CVIU

(1998)

B.K Jang et al.

One-pass parallel thinninganalysis, properties, and quantitative evaluation

IEEE PAMI

(1992)

Cited by (120)

Weld crack detection and quantification using laser thermography, mask R-CNN, and CycleGAN
2022, Automation in Construction
Citation Excerpt :
Fig. 7 outlines how the crack length and width are estimated from the detection image previously obtained from Mask R-CNN. In the first step, the centerline is estimated from each crack mask within the detection image using a medial axis transform (MAT) [31]. First, the edge contour of the crack mask is obtained using the Canny edge detection method [32].
Steel members are susceptible to cracking, and a number of non-destructive testing (NDT) techniques are used for crack detection. However, these NDT techniques are not only labor intensive but also time consuming. In particular, inspection of welded areas requires surface treatment, and data must be interpreted by experienced engineers to differentiate cracks from weld patterns. In this study, an automated weld crack detection and quantification system was developed by integrating laser thermography, Mask R-CNN, and CycleGAN. The developed system comprises a laser heat source, an IR camera, and a control unit. The laser applied heating to the target surface, and the resulting thermal radiation emitted from the surface was measured using an IR camera. Subsequently, the thermal images were processed for crack detection using Mask R-CNN, and for crack quantification using medial axis transform. The detection and quantification performance of the developed system were validated through laboratory and field tests.
Building outline extraction from als point clouds using medial axis transform descriptors
2020, Pattern Recognition
Automatic building extraction and delineation from airborne LiDAR point cloud data of urban environments is still a challenging task due to the variety and complexity at which buildings appear. The Medial Axis Transform (MAT) is able to describe the geometric shape and topology of an object, but has never been applied for building roof outline extraction. It represents the shape of an object by its centerline, or skeleton structure instead of its boundary. Notably, end points of the MAT in principle coincide with corner points of building outlines. However, the MAT is sensitive to small boundary irregularities, which makes shape detection in airborne point clouds challenging. We propose a robust MAT-based method for detecting building corner points, which are then connected to form a building boundary polygon. First, we approximate the 2D MAT of a set of building edge points acquired by the alpha-shape algorithm to derive a so-called building roof skeleton. We then propose a hierarchical corner-aware segmentation to cluster skeleton points based on their properties which are the so-called separation angle, radius of the maximally inscribe circle, and defining edge point indices. From each segment, a corner point is then estimated by extrapolating the position of the zero radius inscribed circle based on the skeleton point positions within the segment. Our experiment uses point cloud datasets of Makassar, Indonesia and EYE-Amsterdam, The Netherlands. The average positional accuracy of the building outline results for Makassar and EYE-Amsterdam is 65 cm and 70 cm, respectively, which meet one-meter base map accuracy criteria. The results imply that skeletonization is a promising tool to extract relevant geometric information on e.g. building outlines even from far from perfect geographical point cloud data.
Skeletal saliency map computation based on projection symmetry analysis
2020, Graphical Models
Skeleton is one of the simplest but powerful tools for shape representation and analysis, which encodes the original shape by one less dimension but can retain the topological information well. Inspired by the observation that the skeleton also serves as a symmetry axis, we propose to compute the skeleton by symmetry analysis of the given shape. In implementation, we define the skeletal saliency map by using the projection symmetry measurement. Firstly, the primitive boundary is extracted. Then, for each pixel p in the shape, we project its four neighboring pixels onto the boundary. The saliency of p is estimated by the maximum distance along the boundary between the two projections. Finally, a clean skeleton is reported by a simple truncation operation. The proposed method can produce a two-pixel-wide skeleton with correct topology and avoid any additional post-processing. Furthermore, it is also robust to boundary noise. Extensive experiment results validate these nice properties of the proposed method, which shows that it outperforms the state-of-the-art methods.
A vision-based approach for autonomous crack width measurement with flexible kernel
2020, Automation in Construction
A quantitative description of cracks is the primary key for examining the safety of structures. Vision-based crack detection has been recently developed to avoid visual inspection, which demands massive labor. For the analysis of a crack based on digital images, several width measurement methods have been investigated. However, the verification of the methods was carried out with irregular surfaces of which the ground truths of the widths were subjective. In this study, a vision-based approach for crack width measurement is proposed, implemented and validated by comparison of the widths which are numerically calculated and analytically featured, respectively. The main skeleton of cracks is extracted by pruning based on the partition of the boundaries of the cracks. A flexible kernel is proposed to calculate the propagation direction of the cracks, and its angular resolution is investigated in terms of the size of the kernel. For calculating the angular resolution, an algorithm for generating the possible skeleton patterns for crack propagation is developed. The verification of the width measurement method shows the existence of the proper range for the coefficient used in determining the size of the kernel. After the verification, the method is implemented for the crack width measurement using the coefficient range selected based on the results of the verification. The flexible kernel with the coefficient in the range provides improved results compared to constant kernels or kernels with the coefficients out of the range.
Learning–based vertebra localization and labeling in 3D CT data of possibly incomplete and pathological spines
2020, Computer Methods and Programs in Biomedicine
We present a fully automatic system based on learning approaches, which aims to localization and identification (labeling) of vertebrae in 3D computed tomography (CT) scans of possibly incomplete spines in patients with bone metastases and vertebral compressions.
The framework combines a set of 3D algorithms for i) spine detection using a convolution neural network (CNN) ii) spinal cord tracking based on combination of a CNN and a novel growing sphere method with a population optimization, iii) intervertebral discs localization using a novel approach of spatially variant filtering of intensity profiles and iv) vertebra labeling using a CNN-based classification combined with global dynamic optimization.
The proposed algorithm has been validated in testing databases, including also a publicly available dataset. The mean error of intervertebral discs localization is 4.4 mm, and for vertebra labeling, the average rate of correctly identified vertebrae is 87.1%, which can be considered a good result with respect to the large share of highly distorted spines and incomplete spine scans.
The proposed framework, which combines several advanced methods including also three CNNs, works fully automatically even with incomplete spine scans and with distorted pathological cases. The achieved results allow including the presented algorithms as the first phase to the fully automated computer-aided diagnosis (CAD) system for automatic spine-bone lesion analysis in oncological patients.
Deep convolutional neural network-based segmentation and classification of difficult to define metastatic spinal lesions in 3D CT data
2018, Medical Image Analysis
This paper aims to address the segmentation and classification of lytic and sclerotic metastatic lesions that are difficult to define by using spinal 3D Computed Tomography (CT) images obtained from highly pathologically affected cases. As the lesions are ill-defined and consequently it is difficult to find relevant image features that would enable detection and classification of lesions by classical methods of texture and shape analysis, the problem is solved by automatic feature extraction provided by a deep Convolutional Neural Network (CNN). Our main contributions are: (i) individual CNN architecture, and pre-processing steps that are dependent on a patient data and a scan protocol – it enables work with different types of CT scans; (ii) medial axis transform (MAT) post-processing for shape simplification of segmented lesion candidates with Random Forest (RF) based meta-analysis; and (iii) usability of the proposed method on whole-spine CTs (cervical, thoracic, lumbar), which is not treated in other published methods (they work with thoracolumbar segments of spine only).
Our proposed method has been tested on our own dataset annotated by two mutually independent radiologists and has been compared to other published methods. This work is part of the ongoing complex project dealing with spine analysis and spine lesion longitudinal studies.

View all citing articles on Scopus

About the Author—KIN-MAN LAM received his Associateship in Electronic Engineering from The Hong Kong Polytechnic University (formerly called Hong Kong Polytechnic) in 1986. He won the S.L. Poa Scholarship for overseas studies and was awarded an M.Sc. degree in communication engineering from the Department of Electrical Engineering, Imperial College of Science, Technology and Medicine, England, in 1987. In 1993, he undertook a Ph.D. program in the Department of Electrical Engineering at the University of Sydney, Australia, and won an Australia Postgraduate Award for his studies. He completed his Ph.D. studies in August 1996, and was awarded the IBM Australia Research Student Project Prize.

From 1990 to 1993, Dr. Lam was a lecturer at the Department of Electronic Engineering of the Hong Kong Polytechnic University teaching various subjects on computer architecture and parallel processing. In October 1996, he was appointed as an Assistant Prof. at The Hong Kong Polytechnic University, and has been an Associate Professor since October 1996. Dr. Lam was a member of the Technical Program Committee of the IEEE Symposium on Circuits and Systems (ISCAS’97). He was also the Secretary of the Hong Kong Special Session for the China Fourteenth National Conference on Circuits and Systems in April 1998, and the Secretary of the 2001 International Symposium on Intelligent Multimedia, Video and Speech Processing in May 2001. He was also a Program Committee Member of the 2002 Conference on Visual Communications and Image Processing.

Currently, Dr. Lam is the Secretary of the IEEE Hong Kong Chapter of Signal Processing, the Secretary of the 2003 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2003), and the Principal Member of Technical Programs of the 2002 Seventh International Conference on Control, Automation, Robotics and Vision (ICARCV 2002). In addition, Dr. Lam is a Guest Editor for the Special Issue on Biometric Signal Processing, EURASIP Journal on Applied Signal Processing. His current research interests include video processing, computer vision and architecture, digital TV and pattern recognition.

About the Author–WAN-CHI SIU received the Associateship from The Hong Kong Polytechnic University (formerly called the Hong Kong Polytechnic), the MPhil degree from The Chinese University of Hong Kong and the Ph.D. degree from Imperial College of Science, Technology & Medicine, London, in 1975, 1977 and 1984, respectively. He was with The Chinese University of Hong Kong between 1975 and 1980. He then joined The Hong Kong Polytechnic University as a Lecturer in 1980 and has become Chair Prof. since 1992. He took up administrative duties as Associate Dean of Engineering Faculty between 1992 and 1994 and Head of Department of Electronic and Information Engineering between 1994 and 2000. Prof. Siu has been Director of Centre for Multimedia Signal Processing and Dean of Engineering Faculty of the same university since September 1998 and September 2000, respectively. He has published over 200 research papers, and his research interests include digital signal processing, fast computational algorithms, transforms, image and video coding, and computational aspects of pattern recognition and neural networks.

Prof. Siu is a Member of the Editorial Board of the Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology and the EURASIP Journal on Applied Signal Processing. He was a Guest Editor of a Special Issue of the IEEE Transactions on Circuits and Systems, Pt.II published in May 1998, and was also an Associate Editor of the IEEE Transactions on Circuits and Systems, Pt.II between 1995 and 1997. Prof. Siu was the general chair or the technical program chair of a number of international conferences. In particular, he was a Co- Chair of the Technical Program Committee of the IEEE International Symposium on Circuits and Systems (ISCAS’97) and the General Chair of the 2001 International Symposium on Intelligent Multimedia, Video & Speech Processing (ISIMP’2001) which were held in Hong Kong in June 1997 and May 2001, respectively. Prof. Siu is now the General Chair of the 2003 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’2003) which will be held in Hong Kong. Between 1991 and 1995, Prof. Siu was a member of the Physical Sciences and Engineering Panel of the Research Grants Council (RGC), Hong Kong Government, and in 1994 he chaired the first Engineering and Information Technology Panel to assess the research quality of 19 Cost Centers (departments) from all universities in Hong Kong.

Prof. Siu is a Chartered Engineer, a Fellow of the IEE and the HKIE, and a Senior Member of the IEEE, and has also been listed in Marquis Who's Who in the World, Marquis Who's Who in Science and Engineering and other citation biographies.

View full text

Extraction of the Euclidean skeleton based on a connectivity criterion

Abstract

Introduction

Section snippets

Skeleton based on the maximal disk

The width of skeleton

The skeletonization algorithm

Experimental results

Conclusions

Pattern Recognition

Comput. Vision Image Understanding

CGIP

Pattern Recognition

CVGIP: Image Understanding

Pattern Recognition

Image Vision Comput.

Comput. Vision Image Understanding

Graphical Models Image Process.

Comput. Graphics Image Process.

Pattern Recognition

CVIU

One-pass parallel thinninganalysis, properties, and quantitative evaluation

IEEE PAMI