基于三维形状匹配的点云分割
|
摘要
随着三维扫描技术的迅猛发展,点云数据的数据量变得异常庞大,这对点云计算的性能提出了更高的要求。因此,如何有效提高算法的执行效率一直是该领域的研究热点和难点。日益增大的数据量隐藏了丰富的三维(3D)形状模型,将形状模型参与到点云计算过程中,为提高点云计算的执行效率提供了一种新的方法和思路。利用3D几何特征分析技术,获取与形状相关的特征参数,并使其参与到点云分割过程中,提出了形状分割方法。利用八叉树算法组织点云数据,发现数据之间的相邻关系,依靠点云数据的密度自适应地双向线性调整八叉树并建立数据索引。使用规则图形建立3D形状模型库,实现模型与分割区域的匹配,进而提取分割区域的形状参数,为提高点云数据计算的精度和速度奠定基础。在分割效果和分割时间上,对比了不同算法,验证了基于形状的点云分割算法的可行性以及稳健性。
With the rapid development of three-dimensional(3D)scanning technique,the huge volume of point cloud has been produced,which puts forward higher requirements for the performance of point cloud computing.Therefore,how to improve the efficiency of the algorithm has become a hot topic in this field.There are rich 3D shape models hidden in the ever-increasing amount of point cloud data.Inspired by the relationship between 3D shape models and the point cloud,we provide a new method to improve the execution efficiency of algorithms about point cloud computing.The 3D geometric feature analysis technology is used to obtain shape-related feature parameters,and the point cloud segmentation algorithm is proposed based on it.We use octree algorithm to organize point cloud and obtain the neighbor relationship.A self adaptive and dual linear octree algorithm is designed based on the density of point clouds to establish the data index.We build a 3D shape library by using regular shape models,and realize the algorithm for matching models with data segmentation regions.Further,we extract the shape parameters of the segmented region,which are the foundation for improving the accuracy and speed of point cloud data processing.Moreover,the segmentation effectiveness and time performance of different algorithms are compared,and the experimental results indicate that the proposed algorithm is feasible and robust.
With the rapid development of three-dimensional(3D)scanning technique,the huge volume of point cloud has been produced,which puts forward higher requirements for the performance of point cloud computing.Therefore,how to improve the efficiency of the algorithm has become a hot topic in this field.There are rich 3D shape models hidden in the ever-increasing amount of point cloud data.Inspired by the relationship between 3D shape models and the point cloud,we provide a new method to improve the execution efficiency of algorithms about point cloud computing.The 3D geometric feature analysis technology is used to obtain shape-related feature parameters,and the point cloud segmentation algorithm is proposed based on it.We use octree algorithm to organize point cloud and obtain the neighbor relationship.A self adaptive and dual linear octree algorithm is designed based on the density of point clouds to establish the data index.We build a 3D shape library by using regular shape models,and realize the algorithm for matching models with data segmentation regions.Further,we extract the shape parameters of the segmented region,which are the foundation for improving the accuracy and speed of point cloud data processing.Moreover,the segmentation effectiveness and time performance of different algorithms are compared,and the experimental results indicate that the proposed algorithm is feasible and robust.
引文
[1]Che E,Olsen M J.Multi-scan segmentation of terrestrial laser scanning data based on normal variation analysis[J].ISPRS Journal of Photogrammetry and Remote Sensing,2018,143:233-248.
[2]Zhao Z Z,Zhang Y J.Building extraction from airborne laser point cloud using NDVI constrained watershed algorithm[J].Acta Optica Sinica,2016,36(10):1028002.赵宗泽,张永军.基于植被指数限制分水岭算法的机载激光点云建筑物提取[J].光学学报,2016,36(10):1028002.
[3]Hoowko E,Wojsz J,Sitnik R,et al.Color-based algorithm for automatic merging of multiview 3Dpoint clouds[J].ACM Journal on Computing and Cultural Heritage,2014,7(3):16.
[4]Li C L,Zhong F,Zhang Q,et al.Accurate and fast3Dhead pose estimation with noisy RGBD images[J].Multimedia Tools and Applications,2018,77(12):14605-14624.
[5]Miyake S,Toda Y,Kubota N,et al.Intensity histogram based segmentation of 3Dpoint cloud using growing neural gas[C]∥International Conference on Intelligent Robotics and Applications,Springer International Publishing,2016:335-345.
[6]Bolles R C,Fischler M A.ARANSAC-based approach to model fitting and its appliAcation to finding cylinders in range data[C]∥International Joint Conference on Artificial Intelligence,1981:637-643.
[7]Fan T J,Medioni G,Nevatia R.Segmented descriptions of 3-D surfaces[J].IEEE Journal on Robotics and Automation,1987,3(6):527-538.
[8]Hu H Y,Cui H G,Dai X.Segmentation of scattered point data based on region growing method[J].Journal of Computer Applications,2009,29(10):2716-2718.胡怀宇,崔汉国,代星.基于区域生长法的散乱点云分区方法[J].计算机应用,2009,29(10):2716-2718.
[9]Pang S Y,Liu Y W,Zuo Z Q,et al.Combination of region growing and TIN edge segmentation for extraction of geometric features on building facades[J].Geomatics and Information Science of Wuhan University,2015,40(1):102-106.庞世燕,刘亚文,左志奇,等.结合区域增长法和TIN边缘分割的建筑物立面几何特征提取[J].武汉大学学报(信息科学版),2015,40(1):102-106.
[10]Dimitrov A,Golparvar-Fard M.Segmentation of building point cloud models including detailed architectural/structural features and MEP systems[J].Automation in Construction,2015,51:32-45.
[11]Nurunnabi A,Belton D,West G.Robust segmentation in laser scanning 3D point cloud data[C]∥International Conference on Digital Image Computing Techniques and Applications(DICTA),2012:1-8.
[12]Nurunnabi A,West G,Belton D.Outlierdetection and robust normal-curvature estimation in mobile laser scanning 3D point cloud data[J].Pattern Recognition,2015,48(4):1404-1419.
[13]Vo A V,Truong-Hong L,Laefer D F,etal.Octree-based region growing for point cloud segmentation[J].ISPRS Journal of Photogrammetry and Remote Sensing,2015,104:88-100.
[14]Velmurugan T,Santhanam T.Computational complexity between K-means and K-medoids clustering algorithms for normal and uniform distributions of data points[J].Journal of Computer Science,2010,6(3):363-368.
[15]Wang S,Sun H Y,Guo H C,et al.Mixed manifold spectral clustering adaptive segmentation method for laser point cloud[J].Acta Optica Sinica,2017,37(10):1011001.王帅,孙华燕,郭惠超,等.激光点云的混合流形谱聚类自适应分割方法[J].光学学报,2017,37(10):1011001.
[16]Xiong F G,Huo W,Han X,et al.Removal method of mismatching keypoints in 3Dpoint cloud[J].Acta Optica Sinica,2018,38(2):0210003.熊风光,霍旺,韩燮,等.三维点云中关键点误匹配剔除方法[J].光学学报,2018,38(2):0210003.
[17]Yan J Z,Qi M Y,Fang L Y,et al.Forecast the distribution of urban water point by using improved DBSCAN algorithm[C]∥International Conference on Intelligent System Design and Engineering Applications,2013:784-786.
[18]Zhang X,Zang A,Agam G,et al.Learning from synthetic models for roof style classification in point clouds[C]∥ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,2014:263-270.
[19]Mahmoudabadi H,Olsen M J,Todorovic S.Efficient terrestrial laser scan segmentation exploiting data structure[J].ISPRS Journal of Photogrammetry and Remote Sensing,2016,119:135-150.
[20]Holz D,Behnke S.Approximate triangulation and region growing for efficient segmentation and smoothing of range images[J].Robotics and Autonomous Systems,2014,62(9):1282-1293.
[21]Boulch A,Guerry J,le Saux B,et al.SnapNet:3Dpoint cloud semantic labeling with 2D deep segmentation networks[J].Computers&Graphics,2018,71:189-198.
[22]Schnabel R,Wahl R,Klein R.Efficient RANSACforpoint-cloud shape detection[J].Computer Graphics Forum,2007,26(2):214-226.
[23]Papazov C,Burschka D.Anefficient RANSAC for 3Dobject recognition in noisy and occluded scenes[C]∥Asian Conference on Computer Vision,2010,6492(1):135-148.
[24]Zuliani M,Kenney C S,Manjunath B S.The multi RANSAC algorithm and its application to detect planar homographies[C]∥IEEE International Conference on Image Processing,2005,3:III-153.
[25]Tran T T,Cao V T,Laurendeau D.Extraction of cylinders and estimation of their parameters from point clouds[J].Computers&Graphics,2015,46:345-357.
[26]Biegelbauer G,Vincze M,Wohlkinger W.Modelbased 3D object detection[J].Machine Vision and Applications,2010,21(4):497-516.
[27]Zhang X M,Wan W G,Xiao L,et al.Mean shift clustering segmentation and RANSAC simplification of color point cloud[C]∥International Conference on Audio,Language and Image Processing,2014:837-841.
[28]Kang Z Z,Li Z.Primitive fitting based on the efficient multiBaySAC algorithm[J].PLoS ONE,2015,10(3):e0117341.
[29]Li L,Yang F,Zhu H H,et al.An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells[J].Remote Sensing,2017,9(5):433.
[30]Overby J,Bodum L,Kjems E,et al.Automatic 3Dbuilding reconstruction from airborne laser scanning and cadastral data using Hough transform[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2004,34(Part B3):296-301.
[31]Rabbani T,von den Heuvel F.Efficient Hough transform for automatic detection of cylinders in point clouds[J].ISPRS Workshop on Laser Scanning,2005,3:60-65.
[32]Tarsha-Kurdi F,Landes F,Grussenmeyer P.Extended RANSAC algorithm for automatic detection of building roof planes from LiDAR data[J].The Photogrammetric Journal of Finland,2008,21(1):97-109.
[33]Liu Y E,Li Z R,Hayward R,et al.Classification of airborne LIDAR intensity data using statistical analysis and Hough transform with application to power line corridors[C]∥Digital Image Computing:Techniques and Applications,2009:462-467.
[34]Hulik R,Spanel M,Smrz P,et al.Continuous plane detection in point-cloud data based on 3D Hough transform[J].Journal of Visual Communication and Image Representation,2014,25(1):86-97.
[35]Hoover A,Jean-Baptiste G,Jiang X,et al.An experimental comparison of range image segmentation algorithms[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(7):673-689.
[36]Várady T,Martin R R,Cox J.Reverse engineering of geometric models:an introduction[J].ComputerAided Design,1997,29(4):255-268.
[2]Zhao Z Z,Zhang Y J.Building extraction from airborne laser point cloud using NDVI constrained watershed algorithm[J].Acta Optica Sinica,2016,36(10):1028002.赵宗泽,张永军.基于植被指数限制分水岭算法的机载激光点云建筑物提取[J].光学学报,2016,36(10):1028002.
[3]Hoowko E,Wojsz J,Sitnik R,et al.Color-based algorithm for automatic merging of multiview 3Dpoint clouds[J].ACM Journal on Computing and Cultural Heritage,2014,7(3):16.
[4]Li C L,Zhong F,Zhang Q,et al.Accurate and fast3Dhead pose estimation with noisy RGBD images[J].Multimedia Tools and Applications,2018,77(12):14605-14624.
[5]Miyake S,Toda Y,Kubota N,et al.Intensity histogram based segmentation of 3Dpoint cloud using growing neural gas[C]∥International Conference on Intelligent Robotics and Applications,Springer International Publishing,2016:335-345.
[6]Bolles R C,Fischler M A.ARANSAC-based approach to model fitting and its appliAcation to finding cylinders in range data[C]∥International Joint Conference on Artificial Intelligence,1981:637-643.
[7]Fan T J,Medioni G,Nevatia R.Segmented descriptions of 3-D surfaces[J].IEEE Journal on Robotics and Automation,1987,3(6):527-538.
[8]Hu H Y,Cui H G,Dai X.Segmentation of scattered point data based on region growing method[J].Journal of Computer Applications,2009,29(10):2716-2718.胡怀宇,崔汉国,代星.基于区域生长法的散乱点云分区方法[J].计算机应用,2009,29(10):2716-2718.
[9]Pang S Y,Liu Y W,Zuo Z Q,et al.Combination of region growing and TIN edge segmentation for extraction of geometric features on building facades[J].Geomatics and Information Science of Wuhan University,2015,40(1):102-106.庞世燕,刘亚文,左志奇,等.结合区域增长法和TIN边缘分割的建筑物立面几何特征提取[J].武汉大学学报(信息科学版),2015,40(1):102-106.
[10]Dimitrov A,Golparvar-Fard M.Segmentation of building point cloud models including detailed architectural/structural features and MEP systems[J].Automation in Construction,2015,51:32-45.
[11]Nurunnabi A,Belton D,West G.Robust segmentation in laser scanning 3D point cloud data[C]∥International Conference on Digital Image Computing Techniques and Applications(DICTA),2012:1-8.
[12]Nurunnabi A,West G,Belton D.Outlierdetection and robust normal-curvature estimation in mobile laser scanning 3D point cloud data[J].Pattern Recognition,2015,48(4):1404-1419.
[13]Vo A V,Truong-Hong L,Laefer D F,etal.Octree-based region growing for point cloud segmentation[J].ISPRS Journal of Photogrammetry and Remote Sensing,2015,104:88-100.
[14]Velmurugan T,Santhanam T.Computational complexity between K-means and K-medoids clustering algorithms for normal and uniform distributions of data points[J].Journal of Computer Science,2010,6(3):363-368.
[15]Wang S,Sun H Y,Guo H C,et al.Mixed manifold spectral clustering adaptive segmentation method for laser point cloud[J].Acta Optica Sinica,2017,37(10):1011001.王帅,孙华燕,郭惠超,等.激光点云的混合流形谱聚类自适应分割方法[J].光学学报,2017,37(10):1011001.
[16]Xiong F G,Huo W,Han X,et al.Removal method of mismatching keypoints in 3Dpoint cloud[J].Acta Optica Sinica,2018,38(2):0210003.熊风光,霍旺,韩燮,等.三维点云中关键点误匹配剔除方法[J].光学学报,2018,38(2):0210003.
[17]Yan J Z,Qi M Y,Fang L Y,et al.Forecast the distribution of urban water point by using improved DBSCAN algorithm[C]∥International Conference on Intelligent System Design and Engineering Applications,2013:784-786.
[18]Zhang X,Zang A,Agam G,et al.Learning from synthetic models for roof style classification in point clouds[C]∥ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems,2014:263-270.
[19]Mahmoudabadi H,Olsen M J,Todorovic S.Efficient terrestrial laser scan segmentation exploiting data structure[J].ISPRS Journal of Photogrammetry and Remote Sensing,2016,119:135-150.
[20]Holz D,Behnke S.Approximate triangulation and region growing for efficient segmentation and smoothing of range images[J].Robotics and Autonomous Systems,2014,62(9):1282-1293.
[21]Boulch A,Guerry J,le Saux B,et al.SnapNet:3Dpoint cloud semantic labeling with 2D deep segmentation networks[J].Computers&Graphics,2018,71:189-198.
[22]Schnabel R,Wahl R,Klein R.Efficient RANSACforpoint-cloud shape detection[J].Computer Graphics Forum,2007,26(2):214-226.
[23]Papazov C,Burschka D.Anefficient RANSAC for 3Dobject recognition in noisy and occluded scenes[C]∥Asian Conference on Computer Vision,2010,6492(1):135-148.
[24]Zuliani M,Kenney C S,Manjunath B S.The multi RANSAC algorithm and its application to detect planar homographies[C]∥IEEE International Conference on Image Processing,2005,3:III-153.
[25]Tran T T,Cao V T,Laurendeau D.Extraction of cylinders and estimation of their parameters from point clouds[J].Computers&Graphics,2015,46:345-357.
[26]Biegelbauer G,Vincze M,Wohlkinger W.Modelbased 3D object detection[J].Machine Vision and Applications,2010,21(4):497-516.
[27]Zhang X M,Wan W G,Xiao L,et al.Mean shift clustering segmentation and RANSAC simplification of color point cloud[C]∥International Conference on Audio,Language and Image Processing,2014:837-841.
[28]Kang Z Z,Li Z.Primitive fitting based on the efficient multiBaySAC algorithm[J].PLoS ONE,2015,10(3):e0117341.
[29]Li L,Yang F,Zhu H H,et al.An improved RANSAC for 3D point cloud plane segmentation based on normal distribution transformation cells[J].Remote Sensing,2017,9(5):433.
[30]Overby J,Bodum L,Kjems E,et al.Automatic 3Dbuilding reconstruction from airborne laser scanning and cadastral data using Hough transform[J].International Archives of Photogrammetry,Remote Sensing and Spatial Information Sciences,2004,34(Part B3):296-301.
[31]Rabbani T,von den Heuvel F.Efficient Hough transform for automatic detection of cylinders in point clouds[J].ISPRS Workshop on Laser Scanning,2005,3:60-65.
[32]Tarsha-Kurdi F,Landes F,Grussenmeyer P.Extended RANSAC algorithm for automatic detection of building roof planes from LiDAR data[J].The Photogrammetric Journal of Finland,2008,21(1):97-109.
[33]Liu Y E,Li Z R,Hayward R,et al.Classification of airborne LIDAR intensity data using statistical analysis and Hough transform with application to power line corridors[C]∥Digital Image Computing:Techniques and Applications,2009:462-467.
[34]Hulik R,Spanel M,Smrz P,et al.Continuous plane detection in point-cloud data based on 3D Hough transform[J].Journal of Visual Communication and Image Representation,2014,25(1):86-97.
[35]Hoover A,Jean-Baptiste G,Jiang X,et al.An experimental comparison of range image segmentation algorithms[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(7):673-689.
[36]Várady T,Martin R R,Cox J.Reverse engineering of geometric models:an introduction[J].ComputerAided Design,1997,29(4):255-268.