基于曲率突变分析的点云特征线自动提取
|
摘要
点云特征线提取是点云模型重构的基础,国内外对此从边缘检测、特征线跟踪和面域分析等方面展开了研究,但由于存在模型多样性、点云数据噪声和不完整性、特征复杂性等问题,看似简单的特征线自动化提取很难实现。从曲率突变点隐含了点云特征线这一论断出发,借鉴图像处理中的区域分割和边缘检测思想,提出了特征线提取中的聚类、细化、分段和排序方案。在具体实现中分别提出了基于连通区域聚类的备选点集分离算法,基于局部影响区域腐蚀的点集细化算法,以及基于组合搜索准则和主成分分析(PCA)双向搜索的特征线分支截断和排序算法。在对比实验中,确定了算法关键参数曲率突变点比例w和方向夹角阈值θT的推荐值,并与类似算法对比能提取更多的特征点;在模型实验中,简单几何模型的特征线提取正确率达到了100%,复杂机械零件模型和艺术品模型的特征线提取正确率均达到了85%以上,取得了预想的棱线和特征轮廓线提取效果。算法具有通用性和可扩展性,通过程序优化可获得更好的特征提取效果。
Point cloud feature-line extraction is the basis of point cloud model reconstruction.Globally,the research on feature-line extraction from point clouds has been conducted in terms of edge detection,feature line tracking,and surface analysis.However,this seemingly simple operation is actually difficult to realize because of problems such as varied models,point cloud noise and imperfection,and feature complexity.Starting from the assertion that curvature mutated points imply the feature line of a single point cloud,this study presented a clustering,refinement,segmentation,and sorting scheme for feature-line extraction.This scheme was based on the idea of regional segmentation and edge detection in image processing.In the specific implementation of this scheme,this study proposed an alternative point set segmentation algorithm based on connection region clustering,apoint set thinning algorithm based on locally influenced area corrosion,and a feature line branching truncation and sorting algorithm based on combinatorial search criteria and principal component analysis bidirectional search.Recommended values of the two key parameters,that was,curvature-mutated point ratio w and directional angle thresholdθT,were determined by conducting a comparative experiment.The proposed method could also extract a greater number of feature points as compared to the similar algorithm.The anticipated contour extraction effect was achieved through model experiments,in which the accuracy ratio of the feature-line extraction for models of simple geometry and complex mechanical parts,as well as artwork models,are 100%and 85%,respectively.The algorithm has the characteristics of generality and extendibility,thus enabling an improved feature extraction effect to be obtained through program improvement.
Point cloud feature-line extraction is the basis of point cloud model reconstruction.Globally,the research on feature-line extraction from point clouds has been conducted in terms of edge detection,feature line tracking,and surface analysis.However,this seemingly simple operation is actually difficult to realize because of problems such as varied models,point cloud noise and imperfection,and feature complexity.Starting from the assertion that curvature mutated points imply the feature line of a single point cloud,this study presented a clustering,refinement,segmentation,and sorting scheme for feature-line extraction.This scheme was based on the idea of regional segmentation and edge detection in image processing.In the specific implementation of this scheme,this study proposed an alternative point set segmentation algorithm based on connection region clustering,apoint set thinning algorithm based on locally influenced area corrosion,and a feature line branching truncation and sorting algorithm based on combinatorial search criteria and principal component analysis bidirectional search.Recommended values of the two key parameters,that was,curvature-mutated point ratio w and directional angle thresholdθT,were determined by conducting a comparative experiment.The proposed method could also extract a greater number of feature points as compared to the similar algorithm.The anticipated contour extraction effect was achieved through model experiments,in which the accuracy ratio of the feature-line extraction for models of simple geometry and complex mechanical parts,as well as artwork models,are 100%and 85%,respectively.The algorithm has the characteristics of generality and extendibility,thus enabling an improved feature extraction effect to be obtained through program improvement.
引文
[1]聂建辉,刘烨,高浩,等.基于符号曲面变化度与特征分区的点云特征线提取算法[J].计算机辅助设计与图形学学报,2015,(12):2332-2339.NIE J H,LIU Y,GAO H,et al..Feature line detection from point cloud based on signed surface variation and region segmentation[J].Journal of Computer-Aided Design&Computer Graphics,2015,27(12):2332-2339.(in Chinese)
[2]谢晓尧,葛邵飞.基于MLS点云模型特征的提取算法[J].沈阳工业大学学报,2014,(3):308-315.XIE X R,GE S F.Feature extraction algorithm for point cloud model based on MLS[J].Journal of Shenyang University of Technology,2014,(3):308-315.(in Chinese)
[3]NI H,LIU X,NING X,et al..Edge detection and feature line tracing in 3D-point clouds by analyzing geometric properties of neighborhoods[J].Remote Sensing,2016,8(9):710.
[4]DEMARSIN K,VANDERSTRAETEN D,VOLO-DINE T,et al..Detection of closed sharp edges in point clouds using normal estimation and graph theory[J].CAD Computer Aided Design,2007,39(4):276-283.
[5]李宝,程志全,党岗,等.一种基于RANSAC的点云特征线提取算法[J].计算机工程与科学,2013,(2):147-153.LI B,CHENG ZH Q,DANG G,et al..ARANSAC-based line features detection algorithm for point clouds[J].Computer Engineering&Science,2013,(2):147-153.(in Chinese)
[6]程效军,方芳.基于形态学的散乱点云轮廓特征线提取[J].同济大学学报(自然科学版),2014,42(1):1738-1743.CHENG X J,FANG F.Morphology-based scattered point cloud contour extraction[J].Journal of Tongji University(Natural Science),2014,42(1):1738-1743.(in Chinese)
[7]周明全,袁洁,耿国华,等.基于轮廓线特征点的交互式文物拼接[J].光学精密工程,2017,25(6):1597-1606.ZHOU M Q,YUAN J,GENG G H,et al..Interactive reassembly of fractured fragments based on feature points of contour line[J].Opt.Precision Eng.,2017,25(6):1597-1606.(in Chinese)
[8]LIU X,JIN C.Feature line extraction from unorganized noisy point clouds[J].Journal of Computational Information Systems,2014,10(8):3503-3510.
[9]ZhANG Y,GENG G,WEI X,et al..A statistical approach for extraction of feature lines from point clouds[J].Computers and Graphics(Pergamon),2016,56:31-45.
[10]NIE J H.Extracting feature lines from point clouds based on smooth shrink and iterative thinning[J].Graphical Models,2016,(84):38-49.
[11]PARK M K,LEE S J,LEE K H.Multi-scale tensor voting for feature extraction from unstructured point clouds[J].Graphical Models,2012,74(4):197-208.
[12]MARK P,RICHARD K,MARKUS G.Multiscale feature extraction on point-sampled surfaces[J].Computer Graphics Forum,2010,22(3):281-289.
[13]刘倩,耿国华,周明全,等.基于三维点云模型的特征线提取算法[J].计算机应用研究,2013,(3):933-937.LIU Q,GENG G H,ZHOU M Q,et al..Algorithm for feature line extraction based on 3Dpoint cloud models[J].Application Research of Computers,2013,(03):933-937.(in Chinese)
[14]张文景,许晓鸣,丁国骏,等.一种基于曲率提取轮廓特征点的方法[J].上海交通大学学报,1999(5):86-89.ZHANG W J,XU X M,TING G J,et al..Approch to extract feature points on boundary based on curvature[J].Journal of Shanghai Jiaotong University,1999(5):86-89.(in Chinese)
[15]余飞祥,黄翔,李泷杲.基于扫描线点云的飞机蒙皮边界特征提取[J].计算机集成制造系统,2017,23(4):701-707.YU F X,HUANG X,LI S G,et al..Aircraft skin boundary extraction based on scan line point cloud[J].Computer Integrated Manufacturing System,2017,23(4):701-707.(in Chinese)
[16]ALTANTSETSEG E,MURAKI Y,MATSUY-AMA K,et al..Feature line extraction from unorganized noisy point clouds using truncated Fourier series[J].Visual Computer,2013,29(6-8):617-626.
[17]WANG C,KANG D,ZHAO X,et al..Extraction of feature points on 3D meshes through data gravitation[C].Intelligent Computing Theories and Application:12th International Conference,ICIC2016,Lanzhou,China,August 2-5,2016,Proceedings,Part II[M].Springer International Publishing,2016,601-612.
[18]TSUCHIE S,HIGASHI M.Extraction of surface-feature lines on meshes using normal tensor framework[J].Computer-Aided Design and Applications,2014,11(2):172-181.
[19]张雨禾,耿国华,魏潇然.散乱点云谷脊特征提取[J].光学精密工程,2015,23(1):310-318.ZHANG Y H,GENG G H,WEI X R.Valley-ridge feature extraction from point clouds[J].Opt.Precision Eng.,2015,23(1):310-318.(in Chinese)
[20]袁小翠,陈华伟.点云模型特征面分割与识别[J].计算机工程,2018,44(11):245-250.YUAN X C,CHEN H W.Feature surface segmentation and recognition for scattered point cloud[J].Computer Engineering,2018,44(11):245-250.(in Chinese)
[21]王鹏,杨文超,孙长库,等.舌面彩色三维点云的舌体分割及舌裂纹提取[J].红外与激光工程,2017,46(S1):S117004.WANG P,YANG W C,SHUN C K,et al..Tongue segmentation and crack extraction of tougue3Dcolor point cloud[J].Infrared and Laser Engineering,2017,46(S1):S117004.(in Chinese)
[2]谢晓尧,葛邵飞.基于MLS点云模型特征的提取算法[J].沈阳工业大学学报,2014,(3):308-315.XIE X R,GE S F.Feature extraction algorithm for point cloud model based on MLS[J].Journal of Shenyang University of Technology,2014,(3):308-315.(in Chinese)
[3]NI H,LIU X,NING X,et al..Edge detection and feature line tracing in 3D-point clouds by analyzing geometric properties of neighborhoods[J].Remote Sensing,2016,8(9):710.
[4]DEMARSIN K,VANDERSTRAETEN D,VOLO-DINE T,et al..Detection of closed sharp edges in point clouds using normal estimation and graph theory[J].CAD Computer Aided Design,2007,39(4):276-283.
[5]李宝,程志全,党岗,等.一种基于RANSAC的点云特征线提取算法[J].计算机工程与科学,2013,(2):147-153.LI B,CHENG ZH Q,DANG G,et al..ARANSAC-based line features detection algorithm for point clouds[J].Computer Engineering&Science,2013,(2):147-153.(in Chinese)
[6]程效军,方芳.基于形态学的散乱点云轮廓特征线提取[J].同济大学学报(自然科学版),2014,42(1):1738-1743.CHENG X J,FANG F.Morphology-based scattered point cloud contour extraction[J].Journal of Tongji University(Natural Science),2014,42(1):1738-1743.(in Chinese)
[7]周明全,袁洁,耿国华,等.基于轮廓线特征点的交互式文物拼接[J].光学精密工程,2017,25(6):1597-1606.ZHOU M Q,YUAN J,GENG G H,et al..Interactive reassembly of fractured fragments based on feature points of contour line[J].Opt.Precision Eng.,2017,25(6):1597-1606.(in Chinese)
[8]LIU X,JIN C.Feature line extraction from unorganized noisy point clouds[J].Journal of Computational Information Systems,2014,10(8):3503-3510.
[9]ZhANG Y,GENG G,WEI X,et al..A statistical approach for extraction of feature lines from point clouds[J].Computers and Graphics(Pergamon),2016,56:31-45.
[10]NIE J H.Extracting feature lines from point clouds based on smooth shrink and iterative thinning[J].Graphical Models,2016,(84):38-49.
[11]PARK M K,LEE S J,LEE K H.Multi-scale tensor voting for feature extraction from unstructured point clouds[J].Graphical Models,2012,74(4):197-208.
[12]MARK P,RICHARD K,MARKUS G.Multiscale feature extraction on point-sampled surfaces[J].Computer Graphics Forum,2010,22(3):281-289.
[13]刘倩,耿国华,周明全,等.基于三维点云模型的特征线提取算法[J].计算机应用研究,2013,(3):933-937.LIU Q,GENG G H,ZHOU M Q,et al..Algorithm for feature line extraction based on 3Dpoint cloud models[J].Application Research of Computers,2013,(03):933-937.(in Chinese)
[14]张文景,许晓鸣,丁国骏,等.一种基于曲率提取轮廓特征点的方法[J].上海交通大学学报,1999(5):86-89.ZHANG W J,XU X M,TING G J,et al..Approch to extract feature points on boundary based on curvature[J].Journal of Shanghai Jiaotong University,1999(5):86-89.(in Chinese)
[15]余飞祥,黄翔,李泷杲.基于扫描线点云的飞机蒙皮边界特征提取[J].计算机集成制造系统,2017,23(4):701-707.YU F X,HUANG X,LI S G,et al..Aircraft skin boundary extraction based on scan line point cloud[J].Computer Integrated Manufacturing System,2017,23(4):701-707.(in Chinese)
[16]ALTANTSETSEG E,MURAKI Y,MATSUY-AMA K,et al..Feature line extraction from unorganized noisy point clouds using truncated Fourier series[J].Visual Computer,2013,29(6-8):617-626.
[17]WANG C,KANG D,ZHAO X,et al..Extraction of feature points on 3D meshes through data gravitation[C].Intelligent Computing Theories and Application:12th International Conference,ICIC2016,Lanzhou,China,August 2-5,2016,Proceedings,Part II[M].Springer International Publishing,2016,601-612.
[18]TSUCHIE S,HIGASHI M.Extraction of surface-feature lines on meshes using normal tensor framework[J].Computer-Aided Design and Applications,2014,11(2):172-181.
[19]张雨禾,耿国华,魏潇然.散乱点云谷脊特征提取[J].光学精密工程,2015,23(1):310-318.ZHANG Y H,GENG G H,WEI X R.Valley-ridge feature extraction from point clouds[J].Opt.Precision Eng.,2015,23(1):310-318.(in Chinese)
[20]袁小翠,陈华伟.点云模型特征面分割与识别[J].计算机工程,2018,44(11):245-250.YUAN X C,CHEN H W.Feature surface segmentation and recognition for scattered point cloud[J].Computer Engineering,2018,44(11):245-250.(in Chinese)
[21]王鹏,杨文超,孙长库,等.舌面彩色三维点云的舌体分割及舌裂纹提取[J].红外与激光工程,2017,46(S1):S117004.WANG P,YANG W C,SHUN C K,et al..Tongue segmentation and crack extraction of tougue3Dcolor point cloud[J].Infrared and Laser Engineering,2017,46(S1):S117004.(in Chinese)