空间栅格动态划分的点云精简方法
|
摘要
常规的特征保持点云精简方法需计算全部点云的微分信息,但直接计算高密度或含噪点云的微分信息存在一定偏差,导致点云精简效果不佳。提出一种基于栅格动态划分的点云精简方法。首先对模型进行空间栅格初划分,利用随机采样一致性算法剔除栅格内的干扰点,然后采用最小二乘法对剩余点进行平面拟合并计算平整度值,根据平整度值判别该栅格是否细分,将平坦区域压入大间距栅格内,特征丰富区域划分至小栅格中。针对小栅格内的点引入高斯函数降低远距离点对特征识别贡献的权重,综合曲面变化度和邻域法向量夹角信息共同识别特征点并保留,大栅格内的点根据栅格间距大小采用不同的采样率采样。与随机采样法、栅格法、曲率精简法对比实验结果表明,该方法能较好地保持模型细微特征且避免孔洞的出现,精简后模型的最大偏差为1.502 mm,远小于其他三种方法;随着噪声强度的增加,本文方法的精简误差相对较小且变化平缓,在35dB噪声下,平均偏差仅为随机采样法和栅格法的40%,曲率精简法的50%。
The conventional feature preserving point cloud simplification method needs to calculate the differential information of all point clouds,but there is a certain deviation in the results by direct calculation with the high density or noise-containing point cloud,resulting in poor effect of point cloud simplification.We present a point cloud simplification method based on grid dynamic partitioning.Firstly,the model is divided into space grids in which the interference points are eliminated with the random sample consensus method.Secondly,the flatness value of grid is calculated by using the least squares method in remaining points,judging whether the grid needs to be subdivided according to the flatness value.Thirdly,the flat areas are achieved and pressed into large spacing grid,and the features-rich areas are divided into small grids as well.For the points in small grids,Gaussian function is introduced to reduce the weight of distant points for recognition features,and the feature points are identified by integration of the surface variation and neighborhood normal vector angle information and then retained.Points in the large grid are sampled at different sampling rates according to the grid spacing.Comparative experiments are carried out with the random sampling method,grid method,curvature method and the proposed method.It is shown that this method can maintain the fine features of model and avoid the appearance of holes,and the maximum deviation of the simplified model is 1.502 mm,much smaller than those of the other three methods.Moreover,as the noise intensity increases,the simplification error of this method is small and gentle.Under the noise condition of 35 dB,the average deviation is only 40% of those of random sampling method and grid method,as well as 50% of that of the curvature method.
The conventional feature preserving point cloud simplification method needs to calculate the differential information of all point clouds,but there is a certain deviation in the results by direct calculation with the high density or noise-containing point cloud,resulting in poor effect of point cloud simplification.We present a point cloud simplification method based on grid dynamic partitioning.Firstly,the model is divided into space grids in which the interference points are eliminated with the random sample consensus method.Secondly,the flatness value of grid is calculated by using the least squares method in remaining points,judging whether the grid needs to be subdivided according to the flatness value.Thirdly,the flat areas are achieved and pressed into large spacing grid,and the features-rich areas are divided into small grids as well.For the points in small grids,Gaussian function is introduced to reduce the weight of distant points for recognition features,and the feature points are identified by integration of the surface variation and neighborhood normal vector angle information and then retained.Points in the large grid are sampled at different sampling rates according to the grid spacing.Comparative experiments are carried out with the random sampling method,grid method,curvature method and the proposed method.It is shown that this method can maintain the fine features of model and avoid the appearance of holes,and the maximum deviation of the simplified model is 1.502 mm,much smaller than those of the other three methods.Moreover,as the noise intensity increases,the simplification error of this method is small and gentle.Under the noise condition of 35 dB,the average deviation is only 40% of those of random sampling method and grid method,as well as 50% of that of the curvature method.
引文
[1]Yuan Xiaocui,Wu Lushen,Chen Huawei.Feature preserving point cloud simplification[J].Optics and Precision Engineering,2015,23(9):2666-2676.袁小翠,吴禄慎,陈华伟.特征保持点云数据精简[J].光学精密工程,2015,23(9):2666-2676.
[2]Chen Zhangwen,Da Feipeng.3Dpoint cloud simplification algorithm based on fuzzy entropy iteration[J].Acta Optica Sinica,2013,33(8):0815001.陈璋雯,达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报,2013,33(8):0815001.
[3]Yao Wanqiang,Zheng Junliang,Chen Peng,et al.An octree-based mesh simplification algorithms for 3-dimension cloud data[J].Science of Surveying and Mapping,2016,41(7):18-22.姚顽强,郑俊良,陈鹏,等.八叉树索引的三维点云数据压缩算法[J].测绘科学,2016,41(7):18-22.
[4]Martin R R,Stroud I A,Marshall A D.Data reduction for reverse engineering[C].Proceedings of the 7th conference on Information Geometers,Limited,1997:85-100.
[5]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.
[6]Chen Y H,Ng C T,Wang Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.
[7]Pauly M,Gross M,Kobbelt L P.Efficient simplification of point-sampled surfaces[C].Proceedings of the IEEEConference on Visualization,2002:163-170.
[8]Weir D J,Milroy M J,Bradley C,et al.Reverse engineering physical models employing wrap-around B-spline surfaces and quadrics[J].Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture,1996,210(22):147-157.
[9]Zhou Yu,Zhang Wanbing,Du Farong,et al.Algorithm for reduction of scattered point cloud data based on curvature[J].Transactions of Beijing Institute of Technology,2010,30(7):785-789.周煜,张万兵,杜发荣,等.散乱点云数据的曲率精简算法[J].北京理工大学学报,2010,30(7):785-789.
[10]Zhang Yuhe,Geng Guohua,Wei Xiaoran,et al.Point clouds simplification with geometric feature reservation[J].Journal of Computer-Aided Design and Computer Graphics,2016,28(9):1420-1427.张雨禾,耿国华,魏潇然,等.保留几何特征的散乱点云简化算法[J].计算机辅助设计与图形学学报,2016,28(9):1420-1427.
[11]Liu Ying,Wang Chaoyang,Gao Nan,et al.Point cloud adaptive simplification of feature extraction[J].Optics and Precision Engineering,2017,25(1):245-254.刘迎,王朝阳,高楠,等.特征提取的点云自适应精简[J].光学精密工程,2017,25(1):245-254.
[12]Han H,Han X,Sun F,et al.Point cloud simplification with preserved edge based on normal vector[J].OptikInternational Journal for Light and Electron Optics,2015,126(19):2157-2162.
[13]Wang Lihui,Yuan Baozong.Feature point detection for 3Dscattered point cloud model[J].Sigal Processing,2011,27(6):932-938.王丽辉,袁保宗.三维散乱点云模型的特征点检测[J].信号处理,2011,27(6):932-938.
[14]Chen Y,Yue L.A method for dynamic simplification of massive point cloud[C].IEEE International Conference on Industrial Technology(ICIT),2016:1690-1693.
[15]Zhu Yu,Kang Baosheng,Li Hongan,et al.Improved algorithm for point cloud data simplification[J].Journal of Computer Applications,2012,32(2):521-523+544.朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523+544.
[16]Lee P F,Huang C P.The DSO feature based point cloud simplification[C].IEEE Eighth International Conference on Computer Graphics,Imaging and Visualization,2011:1-6.
[17]Schnabel R,Klein R.Octree-based point-cloud compression[C].Eurographics/IEEE Vgtc Conference on Point-Based Graphics,2006:111-121.
[18]Huang M,Yang F,Zhang J,et al.Point cloud data simplification using movable mesh generation[J].Metallurgical&Mining Industry,2015(9):230-237..
[19]Zhu Junfeng,Hu Xiangyun,Zhang Zuxun,et al.Hierarchical outlier detection for point cloud data using a density analysis method[J].Acta Geodaetica et Cartographica Sinica,2015,44(3):282-291.朱俊锋,胡翔云,张祖勋,等.多尺度点云噪声检测的密度分析法[J].测绘学报,2015,44(3):282-291.
[20]Lei Yuzhen,Li Zhongwei,Zhong Kai,et al.Mismatching marked points correction method based on random sample consensus algorithm[J].Acta Optica Sinica,2013,33(3):0315002.雷玉珍,李中伟,钟凯,等.基于随机抽样一致算法的误匹配标志点校正方法[J].光学学报,2013,33(3):0315002.
[21]Chen Long,Cai Yong,Zhang Jiansheng,et al.Feature point extraction of scattered point cloud based on multiple parameters hybridization method[J].Application Research of Computers,2017,34(9):2867-2870.陈龙,蔡勇,张建生,等.基于多判别参数混合方法的散乱点云特征提取[J].计算机应用研究,2017,34(9):2867-2870.
[22]Zhang Y,Geng G,Wei X,et al.A statistical approach for extraction of feature lines from point clouds[J].Computers&Graphics,2016,56(C):31-45.
[23]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.
[2]Chen Zhangwen,Da Feipeng.3Dpoint cloud simplification algorithm based on fuzzy entropy iteration[J].Acta Optica Sinica,2013,33(8):0815001.陈璋雯,达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报,2013,33(8):0815001.
[3]Yao Wanqiang,Zheng Junliang,Chen Peng,et al.An octree-based mesh simplification algorithms for 3-dimension cloud data[J].Science of Surveying and Mapping,2016,41(7):18-22.姚顽强,郑俊良,陈鹏,等.八叉树索引的三维点云数据压缩算法[J].测绘科学,2016,41(7):18-22.
[4]Martin R R,Stroud I A,Marshall A D.Data reduction for reverse engineering[C].Proceedings of the 7th conference on Information Geometers,Limited,1997:85-100.
[5]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.
[6]Chen Y H,Ng C T,Wang Y Z.Data reduction in integrated reverse engineering and rapid prototyping[J].International Journal of Computer Integrated Manufacturing,1999,12(2):97-103.
[7]Pauly M,Gross M,Kobbelt L P.Efficient simplification of point-sampled surfaces[C].Proceedings of the IEEEConference on Visualization,2002:163-170.
[8]Weir D J,Milroy M J,Bradley C,et al.Reverse engineering physical models employing wrap-around B-spline surfaces and quadrics[J].Proceedings of the Institution of Mechanical Engineers Part B Journal of Engineering Manufacture,1996,210(22):147-157.
[9]Zhou Yu,Zhang Wanbing,Du Farong,et al.Algorithm for reduction of scattered point cloud data based on curvature[J].Transactions of Beijing Institute of Technology,2010,30(7):785-789.周煜,张万兵,杜发荣,等.散乱点云数据的曲率精简算法[J].北京理工大学学报,2010,30(7):785-789.
[10]Zhang Yuhe,Geng Guohua,Wei Xiaoran,et al.Point clouds simplification with geometric feature reservation[J].Journal of Computer-Aided Design and Computer Graphics,2016,28(9):1420-1427.张雨禾,耿国华,魏潇然,等.保留几何特征的散乱点云简化算法[J].计算机辅助设计与图形学学报,2016,28(9):1420-1427.
[11]Liu Ying,Wang Chaoyang,Gao Nan,et al.Point cloud adaptive simplification of feature extraction[J].Optics and Precision Engineering,2017,25(1):245-254.刘迎,王朝阳,高楠,等.特征提取的点云自适应精简[J].光学精密工程,2017,25(1):245-254.
[12]Han H,Han X,Sun F,et al.Point cloud simplification with preserved edge based on normal vector[J].OptikInternational Journal for Light and Electron Optics,2015,126(19):2157-2162.
[13]Wang Lihui,Yuan Baozong.Feature point detection for 3Dscattered point cloud model[J].Sigal Processing,2011,27(6):932-938.王丽辉,袁保宗.三维散乱点云模型的特征点检测[J].信号处理,2011,27(6):932-938.
[14]Chen Y,Yue L.A method for dynamic simplification of massive point cloud[C].IEEE International Conference on Industrial Technology(ICIT),2016:1690-1693.
[15]Zhu Yu,Kang Baosheng,Li Hongan,et al.Improved algorithm for point cloud data simplification[J].Journal of Computer Applications,2012,32(2):521-523+544.朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523+544.
[16]Lee P F,Huang C P.The DSO feature based point cloud simplification[C].IEEE Eighth International Conference on Computer Graphics,Imaging and Visualization,2011:1-6.
[17]Schnabel R,Klein R.Octree-based point-cloud compression[C].Eurographics/IEEE Vgtc Conference on Point-Based Graphics,2006:111-121.
[18]Huang M,Yang F,Zhang J,et al.Point cloud data simplification using movable mesh generation[J].Metallurgical&Mining Industry,2015(9):230-237..
[19]Zhu Junfeng,Hu Xiangyun,Zhang Zuxun,et al.Hierarchical outlier detection for point cloud data using a density analysis method[J].Acta Geodaetica et Cartographica Sinica,2015,44(3):282-291.朱俊锋,胡翔云,张祖勋,等.多尺度点云噪声检测的密度分析法[J].测绘学报,2015,44(3):282-291.
[20]Lei Yuzhen,Li Zhongwei,Zhong Kai,et al.Mismatching marked points correction method based on random sample consensus algorithm[J].Acta Optica Sinica,2013,33(3):0315002.雷玉珍,李中伟,钟凯,等.基于随机抽样一致算法的误匹配标志点校正方法[J].光学学报,2013,33(3):0315002.
[21]Chen Long,Cai Yong,Zhang Jiansheng,et al.Feature point extraction of scattered point cloud based on multiple parameters hybridization method[J].Application Research of Computers,2017,34(9):2867-2870.陈龙,蔡勇,张建生,等.基于多判别参数混合方法的散乱点云特征提取[J].计算机应用研究,2017,34(9):2867-2870.
[22]Zhang Y,Geng G,Wei X,et al.A statistical approach for extraction of feature lines from point clouds[J].Computers&Graphics,2016,56(C):31-45.
[23]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.