Skeleton Extraction Using Reeb Graph Based On Feature Points

Aiming at the current conflict between the accuracy and complexity which exists incurrent skeleton extraction algorithm, a new algorithm of skeleton extraction based on featurepoints and Reeb graph theory is proposed. The algorithm can ensure the accuracy, reduce thecomputing complexity, and improve the speed and the efficiency of skeleton extraction.The Floyd algorithm is used in the feature points extraction algorithm, which is used inskeleton extraction and proposed by Julien Tierny. For its high computing complexity,analgorithm for extracting the two-longest-geodesic-points of models based on theshortest-distance with the center point is proposed to take place of the Floyd algorithm. Inthe view of the problem of determining the feature points'extraction value for differentmodels, two algorithms for feature points'extraction self-accommodated value is proposed.One is called Direct-Value Algorithm, which set the value based on experimental results; theother is called Neighbor-Value Algorithm that set the value as the average of the adjacentedges length. Both algorithms work well and could meet the needs of skeleton extraction.Which a sufficient analyzing was done on the flow of skeleton extraction, this paperpresents the design precept as a whole and implementation technology. By using featurepoints and defining an appropriate mapping function, we finish model braches calculation.This paper presents an algorithm, which called Topology Algorithm, to extract skeleton points.An algorithm for deleting redundant point is also proposed.Experiment results show that the method could improve the efficiency and can ensure theaccuracy, reduce the computing complexity and improve the speed of skeleton extraction.