场景点云中小孔洞边界提取算法

王宪伦，丁文壮，孙旭祥

(青岛科技大学 机电工程学院，山东 青岛 266100)

0 引言

随着计算机技术的快速发展，计算速度得到快速提升。作为最直观反映客观位置的点云信息运用范围越来越大，复杂性要求越来越高，在场景获取、位置测量、三维重建、逆向开发[1]方面，点云处理成为场景感知的重要手段。

安装在移动机器人上的深度相机常常需要通过获取点云信息来定位，其中孔洞信息经常是一些定位的关键信息，例如集装箱上的吊装孔位。何学铭等[2]利用最大角度准则、半圆盘度量准则、形状度量准则，通过三者加权来判断为边界点的概率，但是却难以选择恰当的权重系数。陆帆等[3]提出了利用反距离权重加权等效合力和点云密度作为目标点为边界点的判定条件，但是其普遍性较差。王春香等[4]对点云模型的孔洞形成原因及孔洞类型进行了分析和总结, 就边界识别方法做出了详细的介绍和归纳。孙殿柱等[5]提出一种基于曲面局部形貌标架的点云特征识别方法。通过标架夹角的差异性，对曲面样本形貌进行量化分析，区分平滑、边界、棱边及尖角等特征区域，实现对中心样点属性的稳健判别，但是其算法就孔洞边界提取而言开销较大。TABIB R A等[6]使用深度学习的框架来识别边界特征。MINEO C等[7]优化了现有的边界点检测算法并提出了BPD算法。

本文对半圆盘准则和最大角度准则易受噪声影响的问题，提出了双半圆盘准则。本文利用质心点位置将圆盘划分为双半圆盘，通过双半圆盘中投影点数目的比值来判断边界点，噪声的影响会成比例缩小，鲁棒性较好，能够快速、稳健地实现边界提取。

1 点云数据预处理

1.1 点云滤波

1.2 点云降采样

本文采用体素化网格的方法实现下采样来减少点的数量，同时保证点云的形状特征不变。点云几何结构不仅是宏观的几何外形，也包括其微观的排列方式[9-10]，比如横向相似的尺寸、纵向相同的距离等。随机下采样虽然效率比体素栅格[11]滤波器高，但会破坏点云微观结构。

2 点云边界检测算法

2.1 计算切平面

根据目标点P及其在半径为r的范围内的近邻点构造在目标点P处的局部切平面。半径r的选择应当至少为两倍的体素格对角线长度，局部切平面的构造方法采用最小二乘法来拟合切平面[12]，假设切平面方程为

Ax+By+Cz+D=0

(1)

变形为

(2)

z=m1x+m2y+m3

(3)

令S=m1x+m2y+m3，近邻点数目为k，则

(4)

由近邻点拟合切平面即：各个近邻点到切平面的距离的平方和最小，所以应取上述公式的最小值，为此要得到m1、m2、m3的最佳参数估计，所以令

(5)

其中i=1,2,3，所以有

(6)

将上述方程组整理成矩阵的形式为

(7)

对上述方程组求解，即可得到切平面方程。

2.2 计算切平面投影点

将目标点P的近邻点投影到切平面上，其具体步骤为: 建立平面ω过点P且平行于切平面，通过带入点P的坐标可以得到ω的平面方程，进而获得平面ω的法向量n(nx,ny,nz)，设目标点P的近邻点其中之一P0(x0,y0,z0)在平面ω上对应点为P′0(x′0,y′0,z′0)，可以建立方程式(8)。

(8)

将上述两式带入ω的平面方程即可解出P′0(x′0,y′0,z′0)的值。

2.3 双半圆盘算法具体实现

将目标点P的近邻点P0,P1,…，Pk投影到平面ω上得到其各自的对应点P′0,P′1,…，P′k。由于近邻点所在的空间为球体，且平面ω过球心，所以ω平面的感兴趣区域为一块圆形区域，如图1所示。

图1 双圆盘建立示意图

求取投影在圆形范围内投影点的质心坐标，经过质心点(图1中空心点)和圆形中心点(图1中黑色点)来建立直线方程l0(图1中短直线)。求取过圆心并且垂直于l0的直线ld(图1中直线ST)。直线ld将圆形区域分为两个半圆盘，将坐标点带入直线ld的方程来判断点在直线上方或者直线下方，分别对直线上方和下方的点的数目进行统计，在上下两个半圆盘点数目统计时遵循下列原则：恰好位于直线上的点不纳入计数范围，如果某一半圆盘上的投影点的个数为0，则设置该半圆盘的最终参数为0.25，反之，该半圆盘的参数等于该半圆盘上投影点的个数。半圆盘投影点的个数之和应当大于2，认定小于2的为边界离散点。对两个半圆盘参数进行排列大小得到amax、amin，通过两者之比得到参数ka，通过给定参数ka的阈值来判定是否为边界点。n1、n2分别为两个半圆盘上投影点的个数，a1、a2分别为两个半圆盘的参数。综上所述，边界点条件满足下式：

(9)

凡是满足上式的点则认为是边界点，遍历点云中的所有点，得到边界点的索引。

3 内边界判定条件

经过上节可以将边界点提取出来，然后通过聚类[13]分类出各个边界所包含的边界点的索引vi。分别用2.1节中所提到的最小二乘法求取各个vi所对应边界的切平面，将该边界所对应的边界点投影到边界点切平面ωp上。对投影点用广度优先搜索算法(BFS)[14]进行边界点排序。搜索求取该边界所对应边界点邻域内点的质心，邻域半径的选取参考2.1节中半径r值，计算得到由质心指向边界点的单位向量ui，然后将各个边界点所对应的单位向量ui也投影到切平面ωp上，并将得到的投影点按照搜索最近点的方法来连接成多边形，示意图如图2所示。其中A、B、C、D、E、F、G代表边界点，其对应的向量代表ui。

图2 边界点及其对应向量

假设该边界上的边界点个数为kω，取其中任意一点为起始点kω/4，取为一个步长，得到4个边界点及其对应向量ui，求取任意相邻的两向量沿着向量延长线方向的交点。如果交点和质心点所构成向量与目标点和质心点所构成向量方向一致，即向量各元素符号相同，则认为是内边界点。随后沿顺时针或者逆时针定向取另外间隔相等的4个点，依次执行上述判断。如果超过一定比例的点都满足向量延长线交点条件，则认为该边界为内边界。

4 实验验证

本实验采用PCL(point cloud library)，Visual Studio 2015，kinect2.0平台来获取点云数据。为了直观地表达本文提出的双半圆盘准则，本文采用基于Opencv3.4.7和Visual Studio 2015平台的C++语言来直观地测试该准则,计算机采用Inter Core i5-6400CPU内存为12 GB。在实验中创建了空白图片然后将图片分为40×60的格子，并分别在格子中随机生成黑色点来代表投影点，随机截取其中一块并去掉外围点和内孔点，采用上述算法对其边界点检测，结果图如图3所示。图3中：列为a、b、c；行为1、2、3。(1a)、(2a)、(3a)为随机生成的待检测图；(1b)、(2b)、(3b)为本文改进的边界点检测结果图；(1c)、(2c)、(3c)为半圆盘准则的边界点检测结果图(本刊黑白印刷，相关疑问请咨询作者)。

图3 边界点检测实验结果图

图4为各个点对应算法判定值的区间分布图，图4中表明本文算法(双半圆盘准则)和半圆盘准则边界点检测算法结果，圆圈点表示外边界点，星号点表示内边界点。本实验中采用半圆盘边界检测算法检测边界点数目略微多于本文算法的原则。由结果可知，本文算法边界点检测结果更好，边界点均匀程度更好，并且能够在一定程度上排除噪声点所带来的影响，因而其鲁棒性更高。对本文算法提出范围为0.6～3.4共28个区间，半圆盘准则为从0～28共28个区间，对其进行归一化得到区间分布点数直方图。由图4可知：本文算法边界点范围为>2.0，对应图中的>14的值；半圆盘准则为>0.255R的数值，实验中R值为28，即>7.13的为边界点。经上述分析，本文提出的边界点判定方法使得边界点和非边界点分界明显，而半圆盘方法边界点和非边界点分布密集，不易区分。

图4 各个投影点对应判定值结果分布区间图

实验结果表明质心点位置精度对边界点检测结果具有较大的影响，可以通过改变ka值进行多次实验来获取较好的检测边界点的效果，图4所示为ka=2.0时的结果。通过多次实验表明本算法稳定、有效且计算效率较高。

5 结语

通过多次实验表明本算法稳定、高效、检测结果较好，可以有效地将边界点检测出来，达到预期目标。该算法在多次实验后可以确定在值的选择范围上本算法的有效范围较小，相比于文献[2]可以快速地确定适当的值。相比于文献[5]而言，该算法具有更简洁的运算原则，因而计算速度更快，对硬件要求更低。在多次实验中发现，偶然会出现检测结果出错的情况，并且内边界检测比外边界检测更困难(可能曲率较小的原因)，出现这种现象原因猜测为简单将圆盘分为两个半圆，应该是根据密度不同将圆盘分为两个区域，再统计投影点数目进行比较可以得到较好的效果。总体来讲，该算法简单、快速、稳定，噪声的影响较小，可以快速地实现边界点的提取。