Point Cloud Data Segmentation Based On Quadric Surface Approach

In the real world of computer digital process, as opposed to the previous two-dimensional images, three-dimensional data possesses its distinct advantages. With the improvement of modern 3D scanning and modeling techniques, 3D data models based on sampling points, namely, point cloud data models have been gradually integrated into many application areas, and further promoted a new development of interdisciplinary field. With its characteristics such as strong detailing ability, and simple storage, 3D point cloud model has been one of the most commonly used three-dimensional objects in CAD/CG. In recent years point cloud processing has become a hot research, such as studies on point cloud data reconstruction, division, boolean operation. Point cloud data segmentation is one of the hot spot in point cloud model research and have been given more and more attention in recent years.The most important feature of point cloud models is that they do not require records and the preservation of topological relations between sampling points. Therefore, compared with the traditional triangularized models, point cloud models can not only greatly reduce the storage requirements but also offer a high degree of flexibility in computation. Our goal is to segment point cloud data only offering geometric information.We use general quadric surface to segment and fit surface on 3D point cloud models. We use Variational Method to segment and fit surface. Variational Method is similar with iterative cluster, using more global information, thus, it has better effects than locally greedy algorithm. This method define a quadric-fitting target function, segment target area into a initial partition, then use Lloyd method (k-means) to iterate and update the partition. Every iteration reduces the value of target function until convergence or a specified number of iterations is reached. At last, we get a partition results and surface fitting of every partition.The paper mainly puts forward new ideas and algorithms as follows:1. Realized point cloud segmentation based on quadric surface approach. We use K-nearest Neighbors search algorithm to solves this issue that the point cloud models have no linking or topological relations, but also can be further used to segment point cloud though Lloyd algorithm;2. Proposed a Point Cloud Simplification Algorithm based on feature information, used in Lloyd algorithm. This method avoids iteration of all sampling points on point cloud models so as to raise the efficiency. Our experimental results show that algorithms reduce the number of iteration, raise the calculation speed.The main solution is the point cloud segmentation directly based on the sampling points of point cloud models. Based on this work, we can further study the interline of two fitting quadric surface, combined with surface feature information, to construct the boundary representation of 3D data.