The Research On Key Technologies Of Skeletonization Based On Distance Transform

3D object recognition is an important task in the area of Computer Vision. It has been widely used in CAD, IC design, path planning, digital city, medical image processing and military object recognition. It can roughly be separated into two parts, which is character extraction and pattern matching. The work in this thesis is supported by the National Nature Science Foundation of China(No.60273099), and the main target is to research and develop a novel skeleton algorithm.Firstly, the whole process of 3D object recognition is summarized, the partition of character extraction is attached more importance to, and skeleton is introduced. Then, the definitions of skeleton are given in detail, and the popular skeleton algorithms are reviewed. Through comparing, the algorithm based on the Euclidean Distance Transform is selected to be the most efficient sort, it is the major task in this thesis.Second, two big problems in traditional algorithms based on the Euclidean Distance Transform are solved. The first problem is the calculating of the Euclidean Transform. The relation of the Euclidean Transform and skeleton is analyzed in detail, a new algorithm for Euclidean Distance Transformation of an n-dimensional digitized picture is given. The second problem is 3D data voxelization. A voxelization algorithm from mesh data to volume data is proposed, which make it possible to apply the 2D skeleton algorithm into the 3D area.Third, a hierarchical connected skeletonization algorithm is proposed, which settled the connectivity and the 1-pixel width problems, which arise frequently in traditional algorithms. The traditional skeletonization algorithms based on the distance transform do not guarantee the connectivity property, saddle points should be added to solve the connectivity problem. The skeleton is obtained by growing from the skeleton seed with 1-pixel width restricted by the Distance Transform. The connectivity is easily assured, and the hierarchical control can be achieved from the growing process. Finally, we review the entire work.