一种散乱点云的均匀精简算法
|
摘要
针对散乱点云数据密度大、重建时间长、效率低等问题,提出了一种散乱点云的均匀精简算法。该算法基于开源C++编程库点云库(PCL),利用PCL的体素化栅格类创建一个K邻域三维体素栅格,结合包围盒法对输入的点云数据进行K邻域距离计算和法线估计,确定每个小立方栅格的重心,并以其来近似显示这个小立方栅格内所有的数据点,达到精简点云的目的,最后利用贪婪三角投影类对精简后的点云实现三角网格面重建并显示其效果。实验结果表明,该算法在充分保留点云数据几何特征的前提下,能有效滤除部分点云数据冗余量,且精简结果比较均匀,避免了大规模精简所出现的空白区域,提高了重建效率。
Aiming at the problems of high density,long reconstruction time and low reconstruction efficiency for scattered point cloud data,a new uniform simplification algorithm for scattered point cloud data is proposed.This algorithm is based on the open-source C++ programming library point cloud library(PCL).Firstly,a K-nearest neighborhood voxel grid is built by voxel grid class in PCL.Next,according to the bounding box algorithm the K-nearest neighborhood distance of the point cloud data is calculated and the normal of the point cloud data is estimated.Then the barycenter of each small voxel grid is established,which replaces all point cloud data in the voxel grid to achieve point cloud simplification.Finally,the simplified point cloud data is reconstructed and displayed with triangular mesh by greedy projection triangulation class.The experimental results show that in the premise of fully retaining geometric characteristics of point cloud data,the proposed algorithm can effectively remove partial redundancy of the point cloud data and simplify the data uniformly without large-scale blank area,and the reconstruction efficiency is improved.
Aiming at the problems of high density,long reconstruction time and low reconstruction efficiency for scattered point cloud data,a new uniform simplification algorithm for scattered point cloud data is proposed.This algorithm is based on the open-source C++ programming library point cloud library(PCL).Firstly,a K-nearest neighborhood voxel grid is built by voxel grid class in PCL.Next,according to the bounding box algorithm the K-nearest neighborhood distance of the point cloud data is calculated and the normal of the point cloud data is estimated.Then the barycenter of each small voxel grid is established,which replaces all point cloud data in the voxel grid to achieve point cloud simplification.Finally,the simplified point cloud data is reconstructed and displayed with triangular mesh by greedy projection triangulation class.The experimental results show that in the premise of fully retaining geometric characteristics of point cloud data,the proposed algorithm can effectively remove partial redundancy of the point cloud data and simplify the data uniformly without large-scale blank area,and the reconstruction efficiency is improved.
引文
[1]Deng Wenjun,Ye Jingyang,Zhang Tie.Acquisition and denoising algorithm of laser point cloud oriented to robot polishing[J].Acta Optica Sinica,2016,36(8):0814002.邓文君,叶景杨,张铁.面向机器人磨抛的激光点云获取及去噪算法[J].光学学报,2016,36(8):0814002.
[2]Wan Yan,Hu Guilan,Dong Guosheng,et al.3Dbody scanning measurement techniques based on Kinect[J].Journal of Donghua University(Natural Science),2015,41(1):78-83.万燕,胡桂兰,董国胜,等.基于Kinect的三维人体扫描测量技术[J].东华大学学报(自然科学版),2015,41(1):78-83.
[3]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.
[4]Chen Zhangwen,Da Feipeng.3Dpoint cloud simplification algorithm based on fuzzy entropy iteration[J].Acta Optica Sinica,2013,33(8):0805001.陈璋雯,达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报,2013,33(8):0805001.
[5]Han H,Han X,Sun F,et al.Point cloud simplification with preserved edge based on normalvector[J].OptikInternational Journal for Light and Electron Optics,2015,126(19):2157-2162.
[6]Nie Lekui,Sun Dianzhu,Bo Zhicheng,et al.A out-of-core rapid uniform reduction algorithm for massive scattered point cloud[J].Manufacturing Automation,2015,37(11):64-66.聂乐魁,孙殿柱,薄志成,等.海量散乱点云out-of-core快速均匀精简算法[J].制造业自动化,2015,37(11):64-66.
[7]Kim S J,Kim C H,Levin D,et al.Surface simplification using a discrete curvature norm[J].Computer and Graphics,2002,26(5):657-663.
[8]Zhao P C,Wang Y,Hu Q W.A feature preserving algorithm for point cloud simplification based on hierarchical clustering[C].IEEE International Geoscience and Remote Sensing Symposium,2016:5581-5584.
[9]Lee P F,Huang C P.The DSO feature based point cloud simplification[C].8th International Conference on Computer Graphics,Imaging and Visualization,2011:12317058.
[10]Wang L,Chen J,Yuan B.Simplified representation for 3Dpoint cloud data[C].IEEE 10th International Conference on Signal Processing,2010:1271-1274.
[11]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.朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523.
[12]Yang Qiuxiang,Yang Xiaoqing,Du Jian.Point cloud simplification algorithm based on Hausdorff distance and segmentation[J].Computer Engineering and Design,2016,37(8):2105-2109.杨秋翔,杨小青,杜健.基于Hausdorff距离的点云分片精简算法[J].计算机工程与设计,2016,37(8):2105-2109.
[13]Li H,Xu P,Shen Y.A self-adaption fast point cloud simplification algorithm based on normal eigenvalues[C].IEEE7th International Congress on Image and Signal Processing,2015:929-937.
[14]Zhang Shunlan,Mo Jianwen,Zou Lulu.Point cloud simplification algorithm based on K-neighbor and normal accuracy[J].Journal of Wuhan University of Technology(Transportation Science and Engineering),2014,38(3):572-575.张顺岚,莫建文,邹路路.基于K近邻和法向精度的点云精简算法[J].武汉理工大学学报(交通科学与工程版),2014,38(3):572-575.
[15]Chen Xijiang,Zhang Guang,Hua Xianghong.Point cloud simplification based on the information entropy of normal vector angle[J].Chinese J Lasers,2015,42(8):0814003.陈西江,章光,花向红.基于法向量夹角信息熵的点云简化算法[J].中国激光,2015,42(8):0814003.
[16]Ge Yuankun,Li Rong,Li Hailun.Study of point cloud data reduction algorithm integrating space partition and curvature[J].Application Research of Computers,2012,29(5):1997-2000.葛源坤,黎荣,李海伦.空间分割与曲率相融合的点云精简算法研究[J].计算机应用研究,2012,29(5):1997-2000.
[17]Liu Tao,Xu Zheng,Sha Chengmei,et al.Curvature estimation of scattered point cloud data based on bounding box method[J].Science Technology and Engineering,2009,9(12):3333-3336.刘涛,徐铮,沙成梅,等.基于包围盒法的散乱点云数据的曲率精简[J].科学技术与工程,2009,9(12):3333-3336.
[18]Cai Zhimin,Wang Yanmin,Huang Ming.Guass mean curvature simplification algorithm based on KD tree for scattered point cloud data[J].Bulletin of Surveying and Mapping,2013(s1):44-46.蔡志敏,王晏民,黄明.基于KD树散乱点云数据的Guass平均曲率精简算法[J].测绘通报,2013(s1):44-46.
[19]Wiemann T,Kai L,Hertzberg J.Optimizing triangle mesh reconstructions of planar environments[J].IFAC-Papers On Line,2016,49(15):218-223.
[20]Gao Xiangmin.Research and implementation of triangular mesh processing algorithm for scattered point cloud model[D].Nanjing:Nanjing Normal University,2011:32-57.高向敏.散乱点云模型三角网格化处理算法的研究与实现[D].南京:南京师范大学,2011:32-57.
[2]Wan Yan,Hu Guilan,Dong Guosheng,et al.3Dbody scanning measurement techniques based on Kinect[J].Journal of Donghua University(Natural Science),2015,41(1):78-83.万燕,胡桂兰,董国胜,等.基于Kinect的三维人体扫描测量技术[J].东华大学学报(自然科学版),2015,41(1):78-83.
[3]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.
[4]Chen Zhangwen,Da Feipeng.3Dpoint cloud simplification algorithm based on fuzzy entropy iteration[J].Acta Optica Sinica,2013,33(8):0805001.陈璋雯,达飞鹏.基于模糊熵迭代的三维点云精简算法[J].光学学报,2013,33(8):0805001.
[5]Han H,Han X,Sun F,et al.Point cloud simplification with preserved edge based on normalvector[J].OptikInternational Journal for Light and Electron Optics,2015,126(19):2157-2162.
[6]Nie Lekui,Sun Dianzhu,Bo Zhicheng,et al.A out-of-core rapid uniform reduction algorithm for massive scattered point cloud[J].Manufacturing Automation,2015,37(11):64-66.聂乐魁,孙殿柱,薄志成,等.海量散乱点云out-of-core快速均匀精简算法[J].制造业自动化,2015,37(11):64-66.
[7]Kim S J,Kim C H,Levin D,et al.Surface simplification using a discrete curvature norm[J].Computer and Graphics,2002,26(5):657-663.
[8]Zhao P C,Wang Y,Hu Q W.A feature preserving algorithm for point cloud simplification based on hierarchical clustering[C].IEEE International Geoscience and Remote Sensing Symposium,2016:5581-5584.
[9]Lee P F,Huang C P.The DSO feature based point cloud simplification[C].8th International Conference on Computer Graphics,Imaging and Visualization,2011:12317058.
[10]Wang L,Chen J,Yuan B.Simplified representation for 3Dpoint cloud data[C].IEEE 10th International Conference on Signal Processing,2010:1271-1274.
[11]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.朱煜,康宝生,李洪安,等.一种改进的点云数据精简方法[J].计算机应用,2012,32(2):521-523.
[12]Yang Qiuxiang,Yang Xiaoqing,Du Jian.Point cloud simplification algorithm based on Hausdorff distance and segmentation[J].Computer Engineering and Design,2016,37(8):2105-2109.杨秋翔,杨小青,杜健.基于Hausdorff距离的点云分片精简算法[J].计算机工程与设计,2016,37(8):2105-2109.
[13]Li H,Xu P,Shen Y.A self-adaption fast point cloud simplification algorithm based on normal eigenvalues[C].IEEE7th International Congress on Image and Signal Processing,2015:929-937.
[14]Zhang Shunlan,Mo Jianwen,Zou Lulu.Point cloud simplification algorithm based on K-neighbor and normal accuracy[J].Journal of Wuhan University of Technology(Transportation Science and Engineering),2014,38(3):572-575.张顺岚,莫建文,邹路路.基于K近邻和法向精度的点云精简算法[J].武汉理工大学学报(交通科学与工程版),2014,38(3):572-575.
[15]Chen Xijiang,Zhang Guang,Hua Xianghong.Point cloud simplification based on the information entropy of normal vector angle[J].Chinese J Lasers,2015,42(8):0814003.陈西江,章光,花向红.基于法向量夹角信息熵的点云简化算法[J].中国激光,2015,42(8):0814003.
[16]Ge Yuankun,Li Rong,Li Hailun.Study of point cloud data reduction algorithm integrating space partition and curvature[J].Application Research of Computers,2012,29(5):1997-2000.葛源坤,黎荣,李海伦.空间分割与曲率相融合的点云精简算法研究[J].计算机应用研究,2012,29(5):1997-2000.
[17]Liu Tao,Xu Zheng,Sha Chengmei,et al.Curvature estimation of scattered point cloud data based on bounding box method[J].Science Technology and Engineering,2009,9(12):3333-3336.刘涛,徐铮,沙成梅,等.基于包围盒法的散乱点云数据的曲率精简[J].科学技术与工程,2009,9(12):3333-3336.
[18]Cai Zhimin,Wang Yanmin,Huang Ming.Guass mean curvature simplification algorithm based on KD tree for scattered point cloud data[J].Bulletin of Surveying and Mapping,2013(s1):44-46.蔡志敏,王晏民,黄明.基于KD树散乱点云数据的Guass平均曲率精简算法[J].测绘通报,2013(s1):44-46.
[19]Wiemann T,Kai L,Hertzberg J.Optimizing triangle mesh reconstructions of planar environments[J].IFAC-Papers On Line,2016,49(15):218-223.
[20]Gao Xiangmin.Research and implementation of triangular mesh processing algorithm for scattered point cloud model[D].Nanjing:Nanjing Normal University,2011:32-57.高向敏.散乱点云模型三角网格化处理算法的研究与实现[D].南京:南京师范大学,2011:32-57.