自适应K-means聚类的散乱点云精简
|
摘要
目的点云精简是曲面重建等点云处理的一个重要前提,针对以往散乱点云精简算法的精简结果存在失真较大、空洞及不适用于片状点云的问题,提出一种自适应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 significant 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 neighborhood 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 flat 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 difference 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 of1/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.
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 significant 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 neighborhood 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 flat 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 difference 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 of1/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.
引文
[1]Sun W,Bradley C,Zhang Y F,et al.Cloud data modelling employing a unified,non-redundant triangular mesh[J].Computer-Aided Design,2001,33(2):183-193.[DOI:10.1016/S0010-4485(00)00088-9]
[2]Martin R R,Stroud I A,Marshal A D.Data reduction for reverse engineering[R].Reccad:Deliverable Document Coperunicus Project,Computer and Automation Institute of Hungarian Academy of Science,1996.
[3]Lee K H,Woo H,Suk T.Point data reduction using 3D grids[J].The International Journal of Advanced Manufacturing Technology,2001,18(3):201-210.[DOI:10.1007/s001700170075]
[4]Kim S J,Kim C H,Levin D.Surface simplification using a discrete curvature norm[J].Computers&Graphics,2002,26(5):657-663.[DOI:10.1016/s0097-8493(02)00121-8]
[5]Han H Y,Han X,Sun F S,et al.Point cloud simplification with preserved edge based on normal vector[J].Optik-International Journal for Light and Electron Optics,2015,126(19):2157-2162.[DOI:10.1016/j.ijleo.2015.05.092]
[6]Shi B Q,Liang J,Zhang X Q,et al.Research on point cloud simplification with preserved features[J].Journal of Xi’an Jiaotong University,2010,44(11):37-40.[史宝全,梁晋,张晓强,等.特征保持的点云精简技术研究[J].西安交通大学学报,2010,44(11):37-40.][DOI:10.7652/xjtuxb201011008]
[7]Chen L,Cai Y,Zhang J S,et al.Feature point extraction of scattered point cloud based on multiple parameters hybridization method[J/OL].Application Research of Computers,2017,34(9).http://www.cnki.net/kcms/detail/51.1196.TP.20160918.1851.036.html.[陈龙,蔡勇,张建生,等.基于多判别参数混合方法的散乱点云特征提取[J/OL].计算机应用研究,2017,34(9).http://www.cnki.net/kcms/detail/51.1196.TP.20160918.1851.036.html.]
[8]Zheng D J,Lu K Q.Quick picking method for 3D piont cloud based on adaptive octree[J].Journal of Mechanical&Electrical Engineering,2016,33(4):417-420,425.[郑德炯,卢科青.基于自适应八叉树的三维点云快速拾取方法研究[J].机电工程,2016,33(4):417-420,425.][DOI:10.3969/j.issn.1001-4551.2016.04.007]
[9]Wu S H,Cheng Y,Zheng Y N,et al.Survey on K-means algorithm[J].New Technology of Library and Information Service,2011,27(5):28-35.[吴夙慧,成颖,郑彦宁,等.K-means算法研究综述[J].现代图书情报技术,2011,27(5):28-35.][DOI:10.11925/infotech.1003-3513.2011.05.05]
[10]Yao Y H,Shi X L.K-means rough clustering algorithm based on optimized initial center[J].Computer Engineering and Applications,2010,46(34):126-128.[姚跃华,史秀岭.一种优化初始中心的K-means粗糙聚类算法[J].计算机工程与应用,2010,46(34):126-128.][DOI:10.3778/j.issn.1002-8331.2010.34.038]
[11]Hansen P,Ngai E,Cheung B K,et al.Analysis of global K-means,an incremental heuristic for minimum sum-of-squares clustering[J].Journal of Classification,2005,22(2):287-310.[DOI:10.1007/s00357-005-0018-3]
[12]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.[DOI:10.1016/j.patrec.2009.09.011]
[13]Shi B Q,Liang J,Liu Q.Adaptive simplification of point cloud using K-means clustering[J].Computer-Aided Design,2011,43(8):910-922.[DOI:10.1016/j.cad.2011.04.001]
[14]Tam G K L,Cheng Z Q,Lai Y K,et al.Registration of 3D point clouds and meshes:a survey from rigid to nonrigid[J].IEEETransactions on Visualization and Computer Graphics,2013,19(7):1199-1217.[DOI:10.1109/tvcg.2012.310]
[15]Xin W,Pu J X.Point cloud integration base on distances between points and their neighborhood centroids[J].Journal of Image and Graphics,2011,16(5):886-891.[辛伟,普杰信.点到邻域重心距离特征的点云拼接[J].中国图象图形学报,2011,16(5):886-891.][DOI:10.11834/jig.20110515]
[2]Martin R R,Stroud I A,Marshal A D.Data reduction for reverse engineering[R].Reccad:Deliverable Document Coperunicus Project,Computer and Automation Institute of Hungarian Academy of Science,1996.
[3]Lee K H,Woo H,Suk T.Point data reduction using 3D grids[J].The International Journal of Advanced Manufacturing Technology,2001,18(3):201-210.[DOI:10.1007/s001700170075]
[4]Kim S J,Kim C H,Levin D.Surface simplification using a discrete curvature norm[J].Computers&Graphics,2002,26(5):657-663.[DOI:10.1016/s0097-8493(02)00121-8]
[5]Han H Y,Han X,Sun F S,et al.Point cloud simplification with preserved edge based on normal vector[J].Optik-International Journal for Light and Electron Optics,2015,126(19):2157-2162.[DOI:10.1016/j.ijleo.2015.05.092]
[6]Shi B Q,Liang J,Zhang X Q,et al.Research on point cloud simplification with preserved features[J].Journal of Xi’an Jiaotong University,2010,44(11):37-40.[史宝全,梁晋,张晓强,等.特征保持的点云精简技术研究[J].西安交通大学学报,2010,44(11):37-40.][DOI:10.7652/xjtuxb201011008]
[7]Chen L,Cai Y,Zhang J S,et al.Feature point extraction of scattered point cloud based on multiple parameters hybridization method[J/OL].Application Research of Computers,2017,34(9).http://www.cnki.net/kcms/detail/51.1196.TP.20160918.1851.036.html.[陈龙,蔡勇,张建生,等.基于多判别参数混合方法的散乱点云特征提取[J/OL].计算机应用研究,2017,34(9).http://www.cnki.net/kcms/detail/51.1196.TP.20160918.1851.036.html.]
[8]Zheng D J,Lu K Q.Quick picking method for 3D piont cloud based on adaptive octree[J].Journal of Mechanical&Electrical Engineering,2016,33(4):417-420,425.[郑德炯,卢科青.基于自适应八叉树的三维点云快速拾取方法研究[J].机电工程,2016,33(4):417-420,425.][DOI:10.3969/j.issn.1001-4551.2016.04.007]
[9]Wu S H,Cheng Y,Zheng Y N,et al.Survey on K-means algorithm[J].New Technology of Library and Information Service,2011,27(5):28-35.[吴夙慧,成颖,郑彦宁,等.K-means算法研究综述[J].现代图书情报技术,2011,27(5):28-35.][DOI:10.11925/infotech.1003-3513.2011.05.05]
[10]Yao Y H,Shi X L.K-means rough clustering algorithm based on optimized initial center[J].Computer Engineering and Applications,2010,46(34):126-128.[姚跃华,史秀岭.一种优化初始中心的K-means粗糙聚类算法[J].计算机工程与应用,2010,46(34):126-128.][DOI:10.3778/j.issn.1002-8331.2010.34.038]
[11]Hansen P,Ngai E,Cheung B K,et al.Analysis of global K-means,an incremental heuristic for minimum sum-of-squares clustering[J].Journal of Classification,2005,22(2):287-310.[DOI:10.1007/s00357-005-0018-3]
[12]Jain A K.Data clustering:50 years beyond K-means[J].Pattern Recognition Letters,2010,31(8):651-666.[DOI:10.1016/j.patrec.2009.09.011]
[13]Shi B Q,Liang J,Liu Q.Adaptive simplification of point cloud using K-means clustering[J].Computer-Aided Design,2011,43(8):910-922.[DOI:10.1016/j.cad.2011.04.001]
[14]Tam G K L,Cheng Z Q,Lai Y K,et al.Registration of 3D point clouds and meshes:a survey from rigid to nonrigid[J].IEEETransactions on Visualization and Computer Graphics,2013,19(7):1199-1217.[DOI:10.1109/tvcg.2012.310]
[15]Xin W,Pu J X.Point cloud integration base on distances between points and their neighborhood centroids[J].Journal of Image and Graphics,2011,16(5):886-891.[辛伟,普杰信.点到邻域重心距离特征的点云拼接[J].中国图象图形学报,2011,16(5):886-891.][DOI:10.11834/jig.20110515]