Research On Features Extraction And Simplification From Triangle Mesh Based On Morse Theory

Massive amounts of discrete data on spatial model surface can be gotten in a short time with the development of spatial data collection technology,especially the light detection and ranging technology, LiDAR. It isn’t enough only by improving the computation speed, increasing memory space to meet the actual needs that processing and expressing the increasingly large amounts of data. Choosing an appropriate data structure to express the model surface succinctly and effectively with the maximum information preserving is one of the problems to be solved.Right now, the geometric methods, such as regular grid, contour, especially triangulation are still occupy the leading position when express the model surface, which can express the geometric information of the surface model accurately and measure and analyze conveniently. However, it also lead to many problems, such as large data volume, large amount of data redundancy, computation complexity, and it can’t reveal the surface morphology directly.As a way to express the surface model compactly and simply, topological expression based on Morse theory can express salient features of surface with a small number of critical points and lines. What’s more, the number of feature points consistent with the Euler equation and the surface can be completely segmented by the critical lines or Morse(-Smale) complex.Therefore, Extracting the topological structure from the triangle mesh gets more and more attention in the field of computer graphics, earth science, space information science, medical imaging and so on. However, due to the uncertainty of the data and drawback of the algorithms based on Morse theory, the features extracted usually contain a lot of "pseudo features",which also cause the "oversegmentation" problem.In addition, the topology expression is usually used in qualitative analysis currently for the limited accuracy of the features, which restricts the application of topological expression in reality. Research on how to identify the dominant features accurately from the pseudo features is important for the interactive analysis and visualization, and extending topology expression from qualitative analysis to quantitative calculation.To this aim, the extraction and simplification of features from triangle mesh based on Morse theory is deeply probed in this paper, which mainly includes the massive triangulation construction, topology feature extraction and simplification of small-scale complex terrain surface and 3D model surface. The main work are as follows:1) Briefly review and summarize of the development of the basic theory, current state and existing problems. The classical Morse theory and other related concepts,such as critical point, critical line, Morse(-Smale) complexes, persistence, topological simplification and the their relationships are described firstly.Two discrete forms of Morse theory: discrete Morse theory and piecewise linear Morse theory are introduced to make the classical Morse theory practice in realistic application,especially,the piecewise linear Morse theory is discussed briefly, which is the basis of this research. Then, we review and summarize the development of feature extraction and simplification based on Morse theory, which includes: feature point,critical lines and Morse(-Smale) complexes extraction, topological simplification and so on. The problems of extraction and simplification of features from triangle mesh based on Morse theory are summarized, which are the main research content of this paper. Finally, the technical route and structural arrangements are proposed.2) Introduction of a cutting block algorithm for building a massive of triangulation. As an effective data structure commonly used to express surface modelling, triangle mesh is the basis for topological extraction and expression. The existing algorithms are analyzed systematically firstly. In order to solve the difficulty that existing algorithms can’t give attention to both the capability of time and space when constructing Delaunay triangulation with massive LiDAR point clouds and meet the need of topological analysis in the divided blocks based on Morse theory, according to the property of the decoupled domain decomposition mode, a streaming computation Delaunay triangulation algorithm using cutting block is presented. DeWall(Delaunay wall) is constructed firstly using an improved incremental construction algorithm based on uniform grid to cut an independent point cloud data block with specific size and shape, which is suitable for divide-and-conquer algorithm and can avoid deep recursion and memory overflow. Then the cutting block is triangulated with divideand-conquer algorithm, and a algorithm is proposed to delete the wrong triangulations on the cutting block boundary and the process described above is repeated before the triangulation is constructed. The streaming computation is introduced to control the data inputting memory, triangulating the cutting block one by one and footprint release of triangulations and points cloud, which make the algorithm has a more excellent capability of space. The analysis and experiments show that:①Deep recursion and memory overflow of divide and conquer algorithm are avoided by cutting block. Meanwhile,streaming computation is introduced to further improve the memory utilization. The algorithm obtains a space performance to handle the massive data. ②Each block has a time performance of divide and conquer algorithm and the algorithm has a whole time performance close to O(nlog(δ)), which is superior to the divide and conquer algorithm and suitable for processing points cloud more than ten millions. ③The final triangulation is the sum of the sub-triangulations.The uncoupled nature of each sub-triangulation provide support for topological extraction and analysis based on Morse theory.3) Design and implementation of a algorithm for simplifying and extracting the topological features on small-scale complex terrain. Currently topology expression based on Morse theory is usually used in the qualitative analysis, and the datasets used are usually large-scale or relatively smooth. LiDAR provides accurate data for expressing the small-scale terrain surface and make the quantitative calculation possible. However, the high density of points cloud and fractal feature of the terrain lead to lots of spurious features, which causes the oversegmentation problem.A series of definitions,such as FPI(feature point index), are introduced based on the triangle mesh by simulating the terrain surface surrounding area of the feature points to measure the importance of the feature point; Algorithms for extracting and simplifying dominant features and constructing the multi-level representation of features are proposed. The FPI couldn’t only eliminate importance of feature points effectively,but also the numbers of feature points in each section of FPI value are more evenly distributed, which facilitate to establish the multi-level expression of features.The simplification algorithm based on FPI is superior to the persistence algorithm and the nature principle algorithm.It not only can effectively delete the spurious feature and build up the multi-level expression, but also has good repeatability, noise immunity and robustness. What’s more, the accuracy is less than 2 times the spatial sampling frequency, which meets the accuracy requirement of certain quantitative calculation.Taking advantage of definitions for evaluating the point impotance and definiting a concept of scale of feature point, we achieve the corresponding points recognition and matching by calculating the similarity coefficients based on the triangle mesh.4) Derivation of the methods of extracting and simplifying topological features on 3D surface. The attribute of vertices of triangle mesh changes from the elevation value to the curvature value, the change value of vertex normal, etc. when algorithm based on piecewise linear Morse function extended from 2D terrain surface to 3D surface. The maximum, rising line and descending Morse complex are the true features of 3D surface model, while the minimum, the falling line and ascending Morse complex are no meaningful features,which will reduce the time efficiency of extracting features. What’s more, they will lead to error even mistake when simplify the features, since the topological simplification is based on the duality of the Morse-Smale complex. A significant degree of vertices using the vertex normals is presented and an algorithm for extracting features from 3D surface is derived,which only extract the real topological features.Then a algorithm based on the " separatrix persistence " and the simplify algorithm based on the duality of complex is derived for simplifing single complex which only has descending Morse complex. The new feature extraction algorithm can not only effectively identify topological features, but also avoid extracting the error features and improves the time efficiency.The new simplifying algorithm can effectively remove spurious features, reduced oversegmentation, especially, it can maintain the integrity of Morse complex and the surface of 3D model can be segmented completely.5) Design and development of a prototype system of prototype system of features extraction and simplification from triangle mesh based on Morse theory. Based on the presented algorithms and relative technologies, a prototype system is developed in the Visual Studio 2008 environment by using C++, OSG and MFC.The system’s functions mainly include the implementation and analysis of the algorithms and relative technologies, error analysis and the I/O operation of files. What’s more, the data structure are detailed description. The feasibility, rationality, validity and effectiveness of the system and relative algorithms is verified and analyzed by some typical data.