Research On Skeleton Pruning Algorithms With Continuty

Image resources that can be obtained and utilized are increasing dramatically with the development of modern technology. It is urgent demand to detect and recongnize objects from images by using the theories and techniques of the image analysis and understanding in civil life, industry, and military fields. And it's also the key issues in Computer Vision, Artificial Intelligence, Image Processing and other areas.Object representation and recognition techniques are kernel issues in the image analysis and understanding, in which the appropriate object representations are the groundwork and the different types of the representations will largely result in the different recognition strategies. The shape, as the most common features of the image, contains lots of visual informations. And the skeleton, as a global and simplified topology information derived from the shape, is a powerful tool to object representing and the following recognition, and is easy to calculate the similarity of objects. This paper aims to find a practical method to extract skeletons that have strong robustness to the noise and maintain the continuity excellently from contour.This paper firstly presents the lasted researches in the skeleton extraction at home and abroad. And then the five typical extraction methods are described and analyzed, with which some common problems existing in the current skeleton extraction algorithms are summarized. The defects, such as uncontinuous, redundant branches and the unfairness, restrict the further practical application of the skeleton. Based on the previous researches, we choose to obtain the perfect skeletons in terms of the pruning strategy on the class skeletons with natural continuity, in which the focus is to find a new significant measure for skeleton points.Then, a contour length significant metric, CLSM, based skeleton pruning approach is proposed, which employs the minimum distance of the nearest contour pixels of a skeleton pixel as its significance measure.This metric is shown exhibiting features of significance representation, superfluous hairy branch differentiation, and fairness. An algorithm is devised in order to prove the effectiveness of the metric. To ease the search for the nearest contour pixels of a skeleton pixel, all the contour pixels are organized into a kdtree. Complexity analysis combined with experimental practice shows that the complexity of the algorithm is about nlogn, the complexity of building the kdtree, where n is the number of contour pixels. Applying the approach to skeletons generated by morphological thinning, with certain smoothing on the nearest contour pixels search and distance computation, well-pruned skeletons have been obtained. The experiments not only demonstrate the excellent characteristics, but also shows that the approach has high stability and strong noise removal capability.Next, the skeleton tree is applied to CLSM. Although the algorithm of combining CLSM and the kdtree has achieved the desired well-pruned skeletons, we expect more than these, that is the well descriptions of the result skeletons for the following recognitions or matching of objects. Based on the analysis and improvements of the skeleton tree, the original skeleton is organized into a struction of tree, in which, each node will be measured by CLSM and a CLSM threshold will be used to pruning some redundant nodes from the tree. Obviously, the skeleton pruned is still in the tree, and can be used to the subsequent identification directly. Based on a firm mathematical MAT theory and the Domain Decomposition Lemma, an algorithm is designed to complete the CLSM calculations of all the nodes in the tree merely costing the linear complexity. And the algorithm is applied to the morphological skeletonization of images from a standard data set, the Part B of the MPEG-7 CE-Shape-1 data set. Experimental results show that the algorithm not only efficiently achieved the well-pruned skeletons, but also the threshold can be changed to obtain the multi-scale skeletons, providing further facility for recognitions in different accurancy. Additionally, the node in the tree can also embody some other important informations, such as the corrensponding supporting points in the border of the skeleton point. Thus a complete pruning algorithm for the morphological skeleton is achieved. Although the proposed scheme is carried out only on the morphological skeleton this paper, it is clear that a desired skeleton can be obtained on all original skeletons with continuity, but only a little chang is needed in the specific algorithms.Finally, the whole work of this paper and the future research are concluded and discussed.