摘要
目的点云精简是曲面重建等点云处理的一个重要前提,针对以往散乱点云精简算法的精简结果存在失真较大、空洞及不适用于片状点云的问题,提出一种自适应K-means聚类的点云精简算法。方法首先,根据k邻域计算每个数据点的曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离,据此运用多判别参数混合的特征提取方法识别并保留特征点,包括曲面尖锐点和边界点;然后,对点云数据建立自适应八叉树,为K-means聚类提供与点云密度分布相关的初始化聚类中心以及K值;最后,遍历整个聚类,如果聚类结果中含有特征点则剔除其中的特征点并更新聚类中心,计算更新后聚类中数据点的最大曲率差,将最大曲率差大于设定阈值的聚类进行细分,保留最终聚类中距聚类中心最近的数据点。结果在聚类方面,将传统的K-means聚类和自适应K-means聚类算法应用于bunny点云,后者在聚类的迭代次数、评价函数值和时间上均优于前者;在精简方面,将提出的精简算法应用于封闭及片状两种不同类型的点云,在精简比例为1/5时fandisk及saddle模型的精简误差分别为0.29×10^(-3)、-0.41×10^(-3)和0.037、-0.094,对于片状的saddle点云模型,其边界收缩误差为0.030 805,均小于栅格法和曲率法。结论本文提出的散乱点云精简算法可应用于封闭及片状点云,精简后的数据点分布均匀无空洞,对片状点云进行精简时能够保护模型的边界数据点。
Objective With the rapid development of 3D scanning technology in the field of reverse engineering, point clouds that are obtained by 3D scanning devices are commonly dense and disordered. These characteristics of point clouds result in a large number of redundancy data. Moreover, subsequent point processing work, such as smoothing, meshing, and surface reconstruction becomes difficult and inefficient. Therefore, point cloud simplification is a considerably signifi- cant prerequisite for smoothing, meshing, surface reconstruction, and other follow-up point cloud processing works. In recent years, point cloud simplification algorithms based on feature preserving method can obtain a better simplified effect than algorithms based on nonselective reduction method presented, which have been widely utilized in several studies.However, the existing algorithms for point cloud simplification still have some inevitable shortcomings, including a large lack of fidelity to the origin, hole generation, and inadaptability to flaky point clouds. This study presents a simplification algorithm of scattered point cloud based on an adaptive K-means clustering, aiming to solve the problems in the existing aforementioned simplified algorithms. Method The curvature, average vector angle between points, the K-nearest neigh- borhood points, the distance from the point to its K-nearest neighborhood gravity center, and the average distance from the point to its K-nearest neighborhood points for each data point are calculated. The feature discriminant parameter and feature discriminant threshold are defined based on the four parameters regarded as the most important by the proposed algorithm. A point is recognized as a feature point when its value of discriminant parameter is greater than the threshold value. Thus, the feature extraction based on multiple parameters hybridization method is adopted to identify and preserve these feature points, including surface sharp and boundary points. Then, an adaptive octree is established for the point cloud to allow the K-means to initialize cluster centers and k value, which are related to the density distribution of the point cloud. Finally, if the clustering results contain the feature points, then the feature points in the clustering are removed and the cluster centers are updated. In general, cluster members in fiat areas are sufficiently similar to each other in the spatial and feature domain. Thus, the cluster center can be employed to represent the cluster. However, in high curvature areas, the cluster members may not be similar to each other in the spatial and feature field because of highly detailed features. Therefore, the cluster will be subdivided to preserve the detail features when the maximum curvature difference between data points in the cluster is greater than the threshold value. The clustering subdivision will continue until the maximum curvature differenee is smaller than the threshold value or when only one data point in the cluster is observed. The nearest point to the cluster center is preserved to represent the cluster after the clustering subdivision. Result In view of clustering, the bunny point cloud is considered as an example for the comparison of traditional K-means clustering algorithm and adaptive K-means clustering algorithm. The comparison result shows that the adaptive K-means clustering algorithm can obtain better data in terms of number of iterations, evaluation function value, and runtime compared with K-means clustering algorithm. In the aspect of simplification, the proposed reduction algorithm is applied to two types of point clouds ( i. e. , closed-boundary and flaky point clouds). The experimental results show that when the simplification ratio has the value of 1/5, the reduction errors of the fandisk and saddle models are 0. 29 × 10-3, -0.41 × 10-3, and 0. 037, -0. 094. Moreover, the boundary shrinkage error of the saddle model is 0. 030 805. The aforementioned error values are less than the error values of the grid simplification method and the curvature simplification method. Conclusion The proposed scattered point cloud simplification algorithm can be used for closed-boundary and flaky point clouds. Moreover, the simplified point cloud is well-distributed in space and can avoid holes. The boundary points of the model can also be protected when the algorithm is applied on the flaky point cloud model.
出处
《中国图象图形学报》
CSCD
北大核心
2017年第8期1089-1097,共9页
Journal of Image and Graphics
基金
四川省教育厅科研基金项目(14ZB0111)
教育部共建重点实验室"制造过程测试技术实验室"开放基金项目(14tdzk06)~~
关键词
点云精简
八叉树
K—means聚类
片状点云
边界点
point cloud simplification
octree
K-means clustering
flake point cloud
boundary points