散乱点云边缘提取.pdf

Computer Engineering and Applications 计算机工程与应用 基金项目基金项目：国家科技支撑计划资助项目（2012BAF12B15），国家自然科学基金资助项目（50975100，51175191，51105150），福建省自然科学基金资助项目（2011H2003，2013J01190，2011J01314）；福建省科技计划项目（项目编号：2008H0085）。作者简介作者简介:刘增艺(1988),男,硕士研究生,研究领域为计算机视觉;江开勇(1961),男,博士,教授，研究领域为计算机视觉，快速成形技术、特种加工技术；林俊义(1977),男,博士研究生,副教授，研究领域为计算机视觉。E-mail: 散乱点云特征边缘交互提取散乱点云特征边缘交互提取 刘增艺，江开勇*，林俊义 LIU Zengyi,JIANG Kaiyong*,LIN Junyi 华侨大学 数字化视觉测量厦门市重点实验室，福建 厦门 361021 Xiamen Key Laboratory of Digital Vision Measurement,Huaqiao University,Xiamen,Fujian,361021,China LIU Zengyi,JIANG Kaiyong,LIN Junyi.Interactive extraction of boundary of specified target feature on scattered point cloud.Computer Engineering and Applications Abstract：A method of interactive extraction of boundary of specified target feature was proposed to extract the boundary of specified target feature from the scattered point cloud with multiple feature boundary.Firstly,the point cloud of specified feature and its surrounding was picked up.The topological relations of scattered point cloud was established with KD tree,then the k-nearest points of each point would be searched.Whether the point is the boundary point was judged by the maximum value of angle difference which calculated by projection points on the least square plane with the k-nearest points.Lastly,one point on the boundary of the specified feature was picked up as the seed point,then according to a fixed direction to search for boundary points,until the entire closed boundary was extracted.Experiments show that,this method can accurately obtain any specified target feature boundary on the scattered point cloud.Key words:scattered point cloud;boundary extraction;interactive;target feature 摘 要：为了在具有多个特征边界的散乱点云上提取指定目标特征边界，提出了一种基于目标特征边界交互提取的算法。首先拾取目标特征及其周围的点云。利用 KD 树建立散乱点云的空间拓扑关系，计算出每个数据点的 k 邻域。然后通过数据点 k 邻域构成的最小二乘平面的投影点角度差，根据角度差的最大值来判断该点是否为边界点。最后再拾取目标特征边界上的某个点作为种子点，按照某一个固定方向搜索边界点，直到搜索整条封闭边界为止。实验表明，该方法能够准确获取散乱点云上任意指定目标特征的边界。关键词：散乱点云；边界提取；交互性；目标特征 doi:10.3778/j.issn.1002-8331.1404-0070 文献标识码文献标识码：A 中图法分类号中图法分类号：TP391.41 1 引言 引言 随着激光测量技术的不断发展，产品模型数字化测量设备的不断推陈出新，使得逆向工程技术得到了长足的发展。通过逆向工程技术可将产品复杂表面离散为无序的三维点，即通常所谓的点云。获得这些点云即可进行反求工程设计，也可进行非接触式测量。点云边界是指能够表达实物特征边界的测量点。边界不仅作为表达曲面的重要几何特征，而且作为求解曲面的定义域，对重建曲面模型的品质和精度起着重要的作用1。散乱点云边界提取在诸多领域里得到广泛的应用，例如逆向工程中的曲面重建、欠采样区域的检测、孔洞修补、曲面几何特征提取、文物的保护与修复等。在三维检测领域里，点云上特征边界提取的准确性决定了该特征检测精度。例如汽车覆盖件上的曲面圆网络出版时间：2014-09-29 15:57网络出版地址：http:/ Computer Engineering and Applications 计算机工程与应用 孔检测，除了用检具检测外，越来越多采用非接触三维扫描检测的方法实现。首先扫描汽车覆盖件的三维点云，然后提取覆盖件上圆孔的边缘三维点，基于曲面圆孔在其轴向的垂直平面上投影必然是圆的原理，在三维空间上寻找该平面以获取曲面圆孔轴线方向，圆孔边缘点投影至该平面利用最小二乘圆拟合法求取圆的尺寸参数（半径、圆心）。所以在散乱点云中提取圆孔的边界的准确性直接影响这圆孔尺寸的检测精度。如何从散乱的点云中提取需要的目标特征边界成为了研究热点2-3。目前，散乱点云边缘提取主要有两种方法4：一种是建立点云的三角网格模型，通过网格的拓扑关系提取点云边界。如果三角网格模型中存在某条边仅属于一个三角面片，则可判定该条边为点云的边界边，该条边的头尾两个点则为边界点。遍历整个三角网格就可以找出点云边界5。该方法简单但点云三角化的算法还不够成熟，难以适应各种点云数据的三角化。同时，三角化算法本身的时间复杂度高，通过三角网格拓扑结构来提取边界在曲面反求过程中效率非常低。另一种方法是直接从散乱点云数据中提取出边界点。Orriols 等6利用递归最小二乘法能够快速的提取曲面边界,不足之处在于得到的边界线不够精确。柯映林7等首先对点云数据进行三维空间划分，建立基于空间栅格的边界提取模型，通过种子边界栅格识别和生长算法以及空间拓扑构型推理算法实现点云数据边界信息的获取，算法受点云密度估计的影响。孙殿柱1等通过引入 R*-tree来建立散乱点云的拓扑索引关系，然后快速获取点云局部型面的参考点集，建立参考点集的基准平面，最后将该点集所有非目标点到基准平面的距离与目标点到基准平面的距离一一比较，识别出点云的边界。胡鑫8 等提出了一种对散乱点云自动分割的方法，利用三角剖分法对点云快速三角化重构网格曲面，然后根据三角网格模型建立散乱点云的拓扑关系，最后根据网格曲面的曲率来确定散乱点云的边界，该方法的提取精度高，但较为耗时。顾园园等9提出了通过构建空间栅格的方法建立点云拓扑关系以求数据点的 k 近邻，然后根据这 k 近邻点的分布均匀性来判别点云边界特征点，从而提取散乱点云边界，该方法能较好的提取孔洞边界，但由于栅格尺寸选取较大时可能会导致本来不相连的点连接在一起。张旭等10提出基于模板的点云边特征提取技术，利用CAD模型上的离散点，通过曲线拟合与截面优化来确定边界点，该方法无需三角化且效率较高。文献11提出一种基于低秩的子空间聚类技术的法向估计算法，通过对点云法向估计来判别平滑区域与尖锐区域的点云特征，从而实现点云边界提取，该方法的抗噪声能力较强，且能保持尖锐特征的原始点云数据，缺点是每个点云数据均需要进行法向估计，运算量大，效率低。文献12 提出了一种基于张量投票理论从非结构化的点云数据可能包含随机噪声中提取的尖锐特征点的点云边界提取方法。文献13根据局部表面拟合多项式计算出点云模型上每个点的主曲率和主方向，用绝对值较大的主曲率标志出潜在特征点进行边界点判断。文献14通过对点云 Voronoi 单元的卷积协方差矩阵进行计算，得到点云曲面上某局部范围内的主曲率主方向以及尖锐边的夹角，进而进行特征点的判断和提取，但计算复杂度较高。文献15提出了基于多尺度算子计算特征点的闭合特征线，将噪声点根据特征点密度大小去除，最获取光滑的特征边界线。对于具有多个特征边界的散乱点云，经常需要提取其中某个特征的边界进行单独测量等操作，运用上述方法均难以实现对局部感兴趣的目标特征边界单独快速提取。针对此问题，本文提出在具有多个特征的散乱点云上交互提取目标特征边界算法。2 算法概述 算法概述 算法概述：首先将点云读入并显示在计算机中，通过鼠标在计算机屏幕上交互框选某个矩形区域，则该矩形区域下的点云被选中。然后对选中的点云的三维点建立KD树的拓扑关系，搜索每个数据点的 k 近邻，根据每个点与k近邻在其拟合平面上投影点的均匀性判断边界点。再次拾取目标边界线上的某个点3 Computer Engineering and Applications 计算机工程与应用 作为种子点，根据一定的边界走向跟踪目标边界。具体的算法流程如下：（1）特征区域点云拾取。利用OpenGL的拾取功能对点云的目标特征区域进行框选，拾取存入到存放三维点的容器中。（2）点云拓扑关系的建立。对目标特征区域所拾取的点云建立KD树，利用KD树搜索每个点的k个最近邻的点。（3）判断边界特征点。将k最近点拟合为最小二乘平面，然后投影到该平面上。平面上的投影点即为一组无序点集，对该点集依夹角的大小排序。排序完成后计算夹角标准差，当标准差值超过设定阈值时,该点判为边界。（4）特征边界线的识别。拾取已提取的边界点上目标边界线上的某个点作为种子点。根据种子点最邻近点搜索方法对边界走向进行判别，进而将边界特征点连接成边界线。2.1 特征区域点云拾取 特征区域点云拾取 通常读入的散乱点云数据都比较庞大而且有多个不同特征，而实际上往往只需要对其中的某个特征进行操作，故而有必要对所需的特征点云区域进行交互选取。对于点云的交互选取，在选择模式下，根据鼠标的位置在 OpenGL 中定义一个狭长视景体。绘制一个对象之前需要对其进行命名，落在此视景体内的物体的名称将被存储在一个堆栈里。通过这个堆栈返回的物体名称即可确定所拾取到的物体16，本文采用该机制利用鼠标在屏幕上绘制矩形框作为拾取框，拾取特征区域的点云。特征点云拾取的效果如图1 所示，红色线框内的点云为所拾取的点云。(a)特征区域局部拾取 (b)特征区域放大图 图 1 特征区域选取 2.2 点云拓扑关系的建立点云拓扑关系的建立 散乱点云呈无规律分布，因此必须建立数据点之间的空间拓扑关系以便于查找每个点的k近邻。k近邻定义为指定点与其余n-1个点的欧氏距离(其中n为散乱数据点的总数)按递增的顺序排列的前k个点。目前搜索k近邻常见的方法有三种：八叉树法、空间栅格法和KD树法17。空间栅格法18算法简单但固定的栅格尺寸不适用于非均匀采样，且栅格尺寸较大时会导致本来不相连的点连接在一起。八叉树法19将指定的三维空间区域划分为八个卦限，每个非叶子结点处存储八个卦限信息。但是八叉树会存在冗余现象，所需存储空间较大，不适用于数量庞大的点云。KD树可以快速确定散乱点云数据中某一个点的邻域，不需要知道点云数据之间的任何拓扑(邻接)关系，故而本文采用KD树建立三维数据点之间的拓扑关系，从而找出各数据点的k近邻。KD树是二叉树的空间推广，两者的区别主要在于KD树的每一层由一个判别值来决定KD树往哪个分支走20。对三维点云组成的三维空间进行KD树构建，三维点表示为：Pi=(xi，yi，zi)，i1,n，构建步骤如下：(1)首先求取所有三维数据点的x、y、z各个分量的中值，分别将对应分量的中值作为KD树第0层，第 l 层和第2 层的判别值。(2)任意一个三维点Pi，KD树的第F层，则有：4 Computer Engineering and Applications 计算机工程与应用 n=F mod3 计算n值来确定判别值是x、y、z中的哪一个分量。当n=0时，取x分量；当n=l时，取y分量；当n=2时，取z分量。(3)当（2）计算取得分量的值小于等于比较划分的判别值时，则将此三维点就划分至左分支；大于判别值时就划分至右分支。(4)循环上述操作，直到所有的三维点都插入到KD树中，则KD树的构建完成。此时所有的三维数据点的拓扑关系建立完毕。2.3 判断边界特征点判断边界特征点 如果点云数据中某点是边界特征点，其k 邻域点的分布将偏向某一侧，如图 2(a)所示；如果是非边界点，则其 k 邻域点将较为均匀地分布在该点的周围，如图 2(b)所示。基于这种原理，可利用数据点及其 k 邻域的分布是否均匀来判断边界特征点。而这种分布的均匀性度量标准采用最大角度差，即当最大角度差超过某一阈值时则判断该点为边界点，否而为内部点。(a)P 点为边界特征点 (b)P 点为内部点 图 2 边界点判别 首先将点P与其k邻域点构造最小二乘平面，然后将点 P 及 k 邻域点投影到该平面上。设 k 邻域点为 Qi，（i0，k-1），取点P 在其 k 邻域点的最近点 Qj，作有向向量PQj作为基准向量；然后取 k 邻域点中的除Qj点外的任意一点 Qm,作有向向量 PQm。计算 PQj与 PQm向量间的夹角（0，），同时计算 PQj与 PQm的叉积向量 nm作为方向判断的基准向量，nm=PQjPQm。分别计算由点 P 到其余 k 邻域点的有向向量 PQi，（i2，k-1），同时计算向量 PQi与基准向量 PQj的夹角 i及叉积矢量 ni。然后再计算 nm与 ni的点积 nmni，当 nmni0 时，i角度保持不变，当 nmni0 时，i=i+。从而得到一个角度序列 s=（1，2k-1）。对角度序列s进行升序排列并加入两个极值角度得到新的角度序列 s=（0，1，2 k-1，2），如图 3 所示，则每相邻线段之间的夹角可通过公式计算得出：Li=i+1-i，其中i0，1，k。图 3 边缘点角度序列 图 4 提取效果 5 Computer Engineering and Applications 计算机工程与应用 当最大夹角 Lmax超过某一阈值时则判断 P 点为边界点，否则为内部点。阈值的大小设定需要根据点云空间分布情况而定，如果边界较为平缓时阈值可设定小一点，如果边界较为尖锐是阈值需设定大一点。阈值的经验值一般设定为/2 左右。设定 k 值为 25，角度阈值取/2 时特征区域的提取效果如图4 所示。2.4 特征边界线的识别特征边界线的识别 用上述方法提取的边界点既有内边界点又有外边界点，如何快速地分离所需要的目标边界点成为研究重点。边界点仍为无序的点云，但不难看出，相连的边界特征点空间拓扑关系上互为 k 邻域点。为了建立点与点之间的空间拓扑关系，需要将提取的边界点重新建立 KD 树，以方便 k 近邻搜索。在内外边界线相距一定距离的情况下，可直接选取距离最近边界点作为待连接的数据点。为了快速分离目标边界，通过鼠标拾取已提取的目标边界上某一个点作为种子点。然后沿着一个固定方向（顺时针或者逆时针方向）通过搜索距离种子点最近的另外一个边界点 Bi，再搜索距离 Bi最近且未搜索的边界点 Bi+1，.，直到又搜索到种子点为止。这样就成功跟踪出所要分离的目标边界点。当目标边缘点不是均匀分布时，利用距离最近点来搜索下一个边界点有可能无法沿着某一个固定方向搜索边界点，造成的后果可能无法再找到种子点连成封闭边界线。为此引入了边界走向，即搜索边界必须沿着某一个固定方向（顺时针或者逆时针）搜索。首先搜索距离种子点 p1最近的 p2点，作有向向量 p1p2；然后搜索离 p2最近且按距离从小到大排序的 6 个点 qi，i 0,5（其中q0 到p2距离最小)；依次作有向向量p2qi，分别计算向量 p2qi与 p1p2向量的夹角，当 的值第一次小于/2 时则将此时的 qi点作为下一个边界点 p3；作有向向量 p2p3，然后重复上述的方法搜索下一个边界点，直到所搜索到的边界点与 p1重合，即可实现从种子点沿着边界走向连接整个封闭的内边界，如图 5 所示。则圆孔边缘点成功提取。图 5 边界搜索走向 3 实验验证实验验证 在上述的研究基础上，在具有多个圆孔特征的汽车覆盖件散乱点云上对圆孔1进行边界提取实验。汽车覆盖件的原始点云如图6(a)所示，该点云有 978864 个三维点，覆盖件上圆孔 1 与圆孔 2 直径均为 30mm。分别做两组实验对比，第一组是对整体点云设置全局角度阈值，设定 k 值为 25，角度阈值为2/3。一次性提取所有的圆孔边界点，提取结果如图 6(b)所示，所有圆孔特征的边界都被提取出来，其中提取圆孔 1 边界点的局部放大图如图 6(c)所示，可以看出圆孔 1 边界点有较多噪声点。另外一组是采用本文算法进行边界提取。首先框选圆孔 1 附近点云区域如图 6(d)所示的黄色区域点云，然后将 k 值固定为25，角度阈值修正为 2/3+/20。对该区域进行边界提取，提取结果如图 6(e)所示。最后对圆孔内边界进行交互提取，提取结果如图 6(f)所示。(a)原始点云 6 Computer Engineering and Applications 计算机工程与应用 (b)全局角度整体提取 (c)全局角度提取圆孔 1 放大图 (d)本文算法圆孔 1 点云区域 (e)本文算法圆孔 1 边界提取 (f)本文算法圆孔 1 边界线跟踪 图 6 圆孔边界提取 实验结果分析：第一组实验中点云上所有特征边界均被提取出来，该过程运行时间为 5517ms，十分耗时，且圆孔 1 提取的边界点有较大的噪声。虽然可通过修正全局角度阈值抑制边界噪声，但每次改变一次全局角度阈值即又重新对整体点云进行边界提取，相当耗时，而且无法直接从点云上所有特征边界点中单独分离圆孔 1 的边界点。第二组实验中对圆孔1点云附近框选的点云区域进行边界提取，耗时仅为 36ms。通过修正角度阈值及交互式边界线跟踪准确地提取了圆孔 1 的边界点。由此可见，采用本文的算法可灵活、准确地提取指定特征边界线。与全局角度阈值提取方法相比具有运行时间短，准确性高，柔性灵活的特点。4 结束语结束语 针对具有多个特征的散乱点云较难直接提取其中的某个目标特征边界（如圆孔边界）问题，提出了利用交互式选取单个目标特征点云进行单独边缘提取。该算法能够有效灵活地对散乱点云上某个感兴趣的特征进行单独边缘提取以便对该边缘做进一步操作。例如可直接应用于交互提取汽车覆盖件点云曲面上被测圆孔的边界，为圆孔的参数检测做好准备。与其它基于整体点云的边界提取再单独地对感兴趣特征边缘精提取的算法相比，具有节省时间，效率高，针对性强的优点。7 Computer Engineering and Applications 计算机工程与应用 参考文献:参考文献:1 孙殿柱，朱昌志，李延瑞散乱点云边界特征快速提取算法J山东大学学报,2009，39(1)：84-86 2 赵吉宾，刘伟军，孙玉文一种自由曲面点云边界的快速直接提取方法J 仪器仪表学报，2007，28(7)：1270-1273 3 刘云峰，柯映林，王秋成等基于特征的反求工程技术研究 计算机集成制造系统，2006，12(1)：3237 4 陈杰，高诚辉，何炳蔚等反求工程三维特征提取技术的研究进展J 中国工程机械学报，2009，7(2)：239-244 5 张丽艳，周儒荣三角网格模型孔洞修补算法研究应用科学学报，2002，20(3)：221224 6 Orriols X,Binefa X.Finding breaking curves in 3D surface.The 1st Iberian Conference on Pattern Recognition and Image Analysis,2003,681-688.7 柯映林，范树迁基于点云的边界特征直接提取技术J机械工程学报2004，40(9)：116-119 8 胡鑫，习俊通，金烨等反求工程中散乱点云数据的自动分割与曲面重构J上海交通大学学报，2004，38(1)：62-65 9 顾园园，姜晓峰，张量曲面重构中带孔洞点云数据的边界提取算法J 苏州大学学报(工科版)，2008，28(2)：56-61 10 张旭，王青，柯映林基于模板的点云边特征提取技术J计算机集成制造系统，2008，14(6)：1175-1181 11 J.Zhang,J.Cao,X.Liu and J.Wang.Point Cloud Normal Estimation via Structural Low Rank Subspace Clustering.Computer&Graphics(SMI 2013),2013.12 Multi-scale tensor voting for feature extraction from unstructured point clouds Original Research Article Graphical Models,Volume 74,Issue 4,July 2012,Pages 197-208.13 PANG，PANGMY，SONGZ Extracting feature curves on point setsJ.International Journal of Information Engineering and Electronic Business，2011，3(3):1-7 14 MRIGOTQ，OVSJANIKOVM，GUIBASLJ Robust Voronoi-based Curvature and feature estimation from point cloudsJ IEEE Trans on Visualization and Computer Graphics，2011，17(6):743-756.15 Xue shu LIU,Chun ning JIN.Feature Line Extraction from Unorganized Noisy Point Clouds 2014 Vol.10(8):3503-3510.16 诸进才，程智勇，黄学飞等基于 OpenGL 拾取技术交互式在机检测软件的开发J机电工程技术，2010，39(5)：13-14 17 禚永盛 散乱点云模型孔洞边界提取算法的研究与实现D南京师范大学，2012 18 朱冒冒，冯祖军，郭建华等三维栅格法在数据点云精简中的应用 上海大学学报：自然科学版，2005，11(3)：242246 19 季振方 基于空间状态八叉树的点云模型表面重建方法：山东大学，2011 20 张琴，蔡勇，常伟杰等基于空间分割的局部KD 树动态构建算法J机械工程师，2010，(12)：30-32