基于法向量区域聚类分割的点云特征线提取

doi:10.3969/j.issn.1004-132X.2021.21.004

摘要/Abstract

摘要： 针对逆向工程领域中散乱点云模型过渡线及细节特征线提取不完整问题，提出一种法向量区域聚类的特征线提取方法。采用自适应邻域的主成分分析法估算模型的法向量，利用萤火虫算法优化的模糊C均值聚类算法对法向量的进行聚类实现模型的有效分割。构造点集剔除与合并准则从各分割块边界点集中析取候选特征点，再以局部邻域主轴方向为基准提取特征点。实验结果表明：简单模型的特征线基本可准确完整提取，相对复杂模型的特征线数量提取率可达90%，长度提取率达到了85%。算法具有良好的自适应性和准确性，能有效提取点云模型尖锐特征和细节特征，并尽可能多地保留模型过渡特征。

关键词: 点云数据, 特征线提取, 萤火虫算法, 模糊C均值聚类, 法向量

Abstract: In oder to solve the problems of incomplete extraction of transition lines and detail feature lines of scattered point cloud models in reverse engineering, a method of extracting feature lines was proposed based on normal vector region clustering. Principal component analysis of adaptive neighborhood was used to estimate the normal vector of the model, and the FA optimized FCM clustering algorithm was introduced to cluster the normal vectors for realizing the effective segmentation of the model. The candidate feature points were extracted from the boundary points of each block by constructing the rule of eliminating and merging point sets, and then the feature points were extracted based on the principal axis direction of local neighborhood. Experimental results show that the feature lines of simple models may be extracted accurately and completely, and the extraction rate of the number and the length of feature lines of some complex models may reach 90% and 85%, respectively. The algorithm has good adaptability and accuracy, and may extract sharp features and detail features from the point cloud model, meanwhile getting transition features as much as possible.

Key words: point cloud data, feature line extraction, firefly algorithm(FA), fuzzy C-means(FCM) clustering, normal vector

中图分类号:

TP391

史红霞, 王建民. 基于法向量区域聚类分割的点云特征线提取[J]. 中国机械工程, 2021, 32(21): 2552-2561.

SHI Hongxia, WANG Jianmin. Feature Line Extraction for Point Cloud Based on Normal Vector Region Clustering Segmentation[J]. China Mechanical Engineering, 2021, 32(21): 2552-2561.

参考文献

［1］张靖,周明全,张雨禾，等.基于马尔科夫随机场的散乱点云全局特征提取［J］.自动化学报，2016,42(7):1090-1099.
ZHANG Jing，ZHOU Mingquan，ZHANG Yuhe，et al. Global Feature Extraction from Scattered Point Clouds Based on Markov Random Field［J］. Acta Automatica Sinica, 2016,42(7):1090-1099.
［2］李彩林,陈文贺,胡善明,等.采用八叉树和OSG分页结点的海量点云三维可视化［J］.计算机工程与应用，2019，55 (21):234-239.
LI Cailin，CHEN Wenhe，HU Shanming，et al. Massive Point Cloud Visualization Using Octree and OSG Paging Nodes［J］. Computer Engineering and Applications, 2019, 55 (21):234-239.
［3］孙世为,王耕耘,李志刚.逆向工程中多视点云的拼合方法［J］.计算机辅助工程,2002,11 (1):8-12.
SUN Shiwei, WANG Gengyun, LI Zhigang. A Combination Methond for Multiple-view Point Clouds in Reverse Engineering［J］. Computer Aided Engineering, 2002,11 (1):8-12.
［4］周嘉俊,李勇,何明,等.机载激光雷达点云多层次建筑物的三维重建［J］.遥感信息, 2019 , 34 (5):76-80.
ZHOU Jiajun, LI Yong, HE Ming, et al. Three Dimensional Reconstruction of Multi-level Buildings from Aiborne LiDAR Point Clouds ［J］.Remote Sensing Information, 2019,34(5):76-80
［5］裴书玉,杜宁,王莉,等.基于自适应分层的文物点云数据压缩算法［J］.计算机应用研究, 2018,35(11):3500-3503.
PEI Shuyu, DU Ning, WANG Li, et al. Adaptive Slicing-based Compression Algorithm with Cultural Relics Point Clouds［J］. Application Research of Computers, 2018,35(11):3500-3503.
［6］LU X W, AI Y F, TIAN B. Real-time Mine Road Boundary Detection and Tracking for Autonomous Truck［J］. Sensors,2020, 20 (4):1121.
［7］DEMARSIN K,VANDERSTRAETEN D,VOLODINE T. Detection of Closed Sharp Edges in Point Clouds Using Normal Estimation and Graph Theory ［J］.Computer Aided Design, 2007, 39(4):276-283.
［8］刘倩,耿国华,周明全,等. 基于三维点云模型的特征线提取算法［J］.计算机应用研究, 2013,30(3):933-937.
LIU Qian, GENG Guohua, ZHOU Mingquan, et al. Algorithm for Feature Line Extraction Based on 3D Point Cloud Models［J］. Application Research of Computers, 2013,30(3):933-937.
［9］贺彤,熊风光,韩燮,等.一种基于协方差矩阵的点云特征曲线提取算法［J］.计算机工程，2018,44(3):275-280.
HE Tong, XIONG Fengguang, HAN Xie, et al. A Feature Curve Extraction Algorithm for Point Cloud Based on Covariance Matrix［J］. Computer Engineering, 2018,44(3):275-280.
［10］PAULY M, KEISER R, GROSS M. Multi-scale Feature Extraction on Point-sampled Surfaces［J］. Computer Graphics Forum, 2003,22(3):281-289.
［11］陈华伟, 袁小翠,吴禄慎,等.基于曲率突变分析的点云特征线自动提取［J］.光学精密工程,2019,27(5):1218-1228.
CHEN Huawei, YUAN Xiaocui, WU Lushen, et al. Automatic Point Cloud Feature-line Extraction Algorithm Based on Curvature Mutation Analysis［J］. Optics Precision Engineering, 2019, 27(5):1218-1228.
［12］徐卫青,陈西江,章光，等.一种基于高斯映射的三维点云特征线提取方法［J］.激光与光电子学进展,2019,56(9):175-181.
XU Weiqing, CHEN Xijiang, ZHANG Guang, et al. Method for Extraction of Feature Lines of Three-dimensional Laser Point Cloud Based on Gaussian Map［J］. Laser & Optoelectronics Progress, 2019,56(9):175-181.
［13］XU J Y, ZHOU M Q, WU Z K, et al. Robust Surface Segmentation and Edge Feature Lines Extraction from Fractured Fragments of Relics［J］. Journal of Computational Design and Engineering, 2015,2(2):79-87.
［14］张雨禾,耿国华,魏潇然.散乱点云谷脊特征提取［J］.光学精密程, 2015, 23(1):310-318.
ZHANG Yuhe, GENG Guohua, WEI Xiaoran. Valley-ridge Feature Extraction from Point Clouds［J］. Optics Precision Engineering, 2015, 23(1):310-318.
［15］程效军,方芳.基于形态学的散乱点云轮廓特征线提取［J］.同济大学学报(自然科学版), 2014,42(11):1738-1743.
CHENG Xiaojun, FANG Fang. Morphology-based Scattered Point Cloud Contour Extraction ［J］.Journal of Tongji University(Natural Science), 2014, 42(11):1738-1743.
［16］庞旭芳,庞明勇,肖春霞.点云模型谷脊特征的提取与增强算法［J］.自动化学报,2010,36 (8):1073-1083.
PANG Xufang, PANG Mingyong, XIAO Chun-xia. An Algorithm for Extracting and Enhancing Valley-ridge Features from Point Sets ［J］. Acta Automatica Sinica, 2010,36 (8):1073-1083.
［17］HE G Z,YANG J. Application of the Slicing Technique to Extract the Contour Feature Line［J］. Cluster Computing, 2019,22(6):13937-13943.
［18］ZHANG W N, CHEN L W, XIONG Z Y, et al. Large-scale Point Cloud Contour Extraction via 3D Guided Multi-conditional Generative Adversarial Network［J］. ISPRS Journal of Photogrammetry and Remote Sensing, 2020, 164:97-105.
［19］林洪彬,刘彬,张玉存.基于多尺度张量分解的点云结构特征提取［J］.中国机械工程,2012,23(15):1833-1839.
LIN Hongbin, LIU Bin, ZHANG Yucun. Structural Feature Extraction from Point Clouds Based on Multi-scale Tensor Decomposion［J］.China Mechanical Engineering, 2012,23(15):1833-1839.
［20］林睦纲,刘芳菊,童小娇. 一种基于萤火虫算法的模糊聚类方法［J］.计算机工程与应用, 2014, 50(21):35-38.
LIN Mugang, LIU Fangju, TONG Xiaojiao. Fuzzy Clustering Algorithm Based on Firely Algorithm［J］. Computer Engineering and Applications, 2014,50(21):35-38.
［21］DUNN J C. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-separated Clusters［J］. Journal of Cybernetics, 1973,3(3):32-57.
［22］施法中.计算机辅助几何设计与非均匀有理B样条［M］.北京:北京航空航天大学出版社，1994:17-25.
SHI Fazhong. Computer Aided Geometric Design& Non-uniform Rational B-spline［M］. Beijing:Beijing University of Aeronautics and Astronautics Press, 1994:17-25.
［23］DEMANTKE J, MALLET C, DAVID N, et al. Dimensionality Based Scale Selection in 3D LiDAR Point Clouds［C］∥The ISPRS Workshop on Laser Scanning. Calgary, 2011:97-102.
［24］叶春明.一种新颖的仿生群智能优化算法:萤火虫算法［J］.计算机应用研究，2011,28(9):3295-3297.
YE Chunming. Novel Bioinspired Swarm Intelligence Optimization Algomrithm Firefly Algorithm［J］. Application Research of Computers, 2011,28(9):3295-3297.
［25］ZHANG Y J, WANG W N, ZHANG X N, et al. A Cluster Validity Index for Fuzzy Clustering ［J］.Information Sciences, 2008, 178(4):1205-1218.
［26］任前程.一种点云特征线提取方法［J］.激光与光电子学进展,2019,56(6):229-235.
REN Qiancheng. Method for Extraction of Point Cloud Features Line［J］. Laser & Optoelectronics Progress, 2019,56(6):229-235.
［27］徐俊,达飞鹏.一种基于局部描述符的三维人脸识别方法［J］.模式识别与人工智能, 2012,25(1):45-53.
XU Jun, DA Feipeng. 3D Face Recognition Based on Local Descriptor［J］. Pattern Recognition and Artificial Intelligence, 2012,25(1):45-53.
［28］李金涛,程效军.建筑物立面点云直线段特征提取方法［J］.中国激光,2019,46(11):287-298.
LI Jintao, CHENG Xiaojun. Straight Line Segment Feature Extraction Method for Building Facade Point Cloud Data［J］.Chinese Journal of Lasers, 2019,46(11):287-298.
［29］王晓辉,吴禄慎,陈华伟,等.基于区域聚类分割的点云特征线提取［J］.光学学报,2018,38(11):66-75.
WANG Xiaohui, WU Lushen, CHEN Huawei, et al. Feature Line Extraction from a Point Cloud Based on Region Clustering Segmentation［J］.Acta Optica Sinica, 2018,38(11):66-75.
［30］WEBER C, HAHMANN S, HAGEN H. Sharp Feature Detection in Point Clouds［C］∥IEEE International Conference on Shape Modeling and Applications. Aix-en-Provence, 2010:175-186.
［31］胡佳贝,刘喆,张鹏飞,等. 基于离散Morse理论的散乱点云特征提取［J］.光学学报，2019,39(6):232-241.
HU Jiabei, LIU Zhe, ZHANG Pengfei,et al. Feature Extraction of Scattered Point Clouds Based on Discrete Morse Theory［J］. Acta Optica Sinica, 2019,39(6):232-241.

[1]	姜万录, 王浩楠, 朱勇, 王振威, 董克岩, . 变分模态分解消噪与核模糊C均值聚类相结合的滚动轴承故障识别方法[J]. 中国机械工程, 2017, 28(10): 1215-1220,1226.
[2]	张淑清, 胡永涛, 李盼, 包红燕, 姜万录, 钱磊. 基于MEMD互近似熵及FCM聚类的轴承故障诊断方法[J]. 中国机械工程, 2015, 26(19): 2613-2618.
[3]	郑红波, 张江雯, 谭小俊, 秦绪佳, 陈嵩辉. 点云数据的二次曲面几何测量方法[J]. 中国机械工程, 2014, 25(11): 1545-1549.
[4]	欧璐, 于德介. 基于拉普拉斯分值和模糊C均值聚类的滚动轴承故障诊断[J]. 中国机械工程, 2014, 25(10): 1352-1357.
[5]	石琴, 马洪龙, 丁建勋, 龙建成, 凌翔. 改进的FCM聚类法及其在行驶工况构建中的应用[J]. 中国机械工程, 2014, 25(10): 1381-1387.
[6]	杨继全1, 朱玉芳1, 2, 李静波1, 施建平1. 基于空间点云数据的异质材料零件动态建模方法[J]. 中国机械工程, 2012, 23(20): 2453-2458.
[7]	王洋, 段桂江. 基于二维需求空间的产品质量特性定位[J]. 中国机械工程, 2012, 23(13): 1518-1523.
[8]	牟鲁西, 尹周平, 熊有伦. 一种多传感器测量系统全局标定方法[J]. 中国机械工程, 2012, 23(12): 1428-1432.
[9]	黄胜利, 卜昆, 程云勇, 周丽敏. 涡轮叶片密集点云数据与CAD模型配准方法 [J]. 中国机械工程, 2011, 22(14): 1699-1703.
[10]	闫龙, 赵正旭, 周以齐. 基于形态学算法的摄影测量数据噪声滤波[J]. 中国机械工程, 2008, 19(1): 48-51.