Research On Similarity Measurement Of Linear Skeleton

With the wide application of computer vision and rapid development in automation, graphics recognition has become a focus of current research. People are increasingly demanding in its related technologies, especially in virtual reality, industrial simulation, science computing visualization, etc. Supported by the National Natural Science Foundation of China (No.60273099)——"New method study of 3D graphics recognition based on generalized conditional skeleton", the work of this paper is to do research on similarity measurement of linear skeleton. An effective linear skeleton topological similarity measure algorithm based on skeleton tree model and the elementary research of shape similarity measurement are presented in this paper, which achieved some creative fruits in the difficult problem of skeleton matching.In this dissertation the background of skeleton definition and extraction, the related theory of similarity measurement and current graphics recognition methods are firstly summarized.Then a novel skeleton tree model is established. Transform the skeleton of objects into a tree structure in which the hierarchy of the tree and the connection relations of the nodes reflect the skeleton's topological characteristics. Especial rules are given for the establishment of circular skeleton tree. As for complicated objects multi-scale skeleton trees are established to reflect the object's topological characteristics from approximately to precisely. At the same time a series of root nodes choosing rules are given for multi-class matching.After that a linear skeleton topological similarity measure algorithm based on skeleton tree is detailed. Define a Topology Signature Vector by the eigenvalue sum of the skeleton tree's adjacency matrix and compute the distance of matching node pair by the difference of the TSV. Then establish the best matching relations between skeleton tree nodes and define the matching distance of two skeleton trees as the sum of the distance of matched node pairs. The matching distance of skeleton trees represents the topological distance of skeletons. The topological similarity of linear skeletons is denoted by this topological distance value. This algorithm achieved good experiment results for the general planar graphics in low computing and time complexity. As for complicated objects, the idea of multi-class matching of complicated objects using multi-scale skeleton trees is put forward to make the algorithm have wider applicability. In addition the shape similarity measurement is researched. After a series of orientation transformations including coordinate translation, rotation and scaling the matching distance function of skeleton branches is defined by some important shape characteristics such as the maximum radius of skeletons' inscribed circles and the number of skeleton nodes in skeleton branches. Then establish the best matching relations between skeleton branches and define the shape matching distance of skeletons as the sum of the distance of matched skeleton branches. The experiment results of simple planar graphics are satisfactory.Finally, this thesis makes a summarization of the entire work and points out the future research direction.