基于PCA 和三元组的非封闭点云轮廓特征提取方法研究①

吴腾飞 王 挺 邵士亮 尚 哲* 窦鑫可**

(*沈阳理工大学自动化与电气工程学院 沈阳 110159)

(**中国科学院沈阳自动化研究所机器人学国家重点实验室 沈阳 110016)

(***中国科学院机器人与智能制造创新研究院 沈阳 110169)

(****东北大学机械工程与自动化学院 沈阳 110819)

(*****沈阳化工大学信息工程学院 沈阳 110142)

0 引言

点云边界检测是机器人作业中的重要部分,例如用于双臂机器人的抓取和搬运[1]、移动机器人即时定位与地图构建[2]和自主导航[3]。此外,基于深度相机获取的点云图像为缺少拓扑关系的散乱点云,由于仪器或者环境等因素的影响,生成的物体点云图质量低,存在多噪声以及轮廓不清晰等问题,这为边界检测带来困难。为了克服这些困难,散乱点云的边界检测得到了相关学者的广泛研究[4]。

目前,点云边界检测算法包括间接法和直接法2 类[5]。间接法是将三维图像映射到二维平面上进行边界检测,再进一步与原始图像对应,如角度变换方法。Bendels 等人[6]提出了角度准则(angle criterion,AC)边界点检测方法,将邻域内的点投影到其切平面,根据采样点与其近邻点形成的夹角大小对边界点进行判定,但该方法不适用棱线特征点。Chen等人[7]采用加权主成分分析(weighted principal component analysis,WPCA)方法构建点云投影平面,分析投影平面上采样点和近邻点形成的夹角大小提取边界点,然后使用K-means 聚类算法对邻域点法向量进行聚类判断棱线点,利用改进三次b样条方法生成轮廓曲线,但该方法对细节特征检测效果不好。Wang 等人[8]使用改进社会粒子群优化模糊C-均值(improved social particle swarm optimization fuzzy C-means,ISPSO-FCM)算法对点云进行分割,通过计算采样点和邻域点之间的角度差识别出边缘点,然后基于平均曲率计算采样点的局部特征权重检测棱线点,最后采用双向主成分分析(bidirectional principal component analysis,BD-PCA)方法对特征点集进行排序并生成特征线,但该方法不易识特征强度较弱的过渡特征。

另一类方法是直接用三维点云数据来提取三维边缘或直线段特征。Emon 等人[9]拟合近K个近邻点所构成的直线,计算各点到直线距离的标准差选取最优近邻点数量,然后对相邻法线角度差最大的点进行聚类并选取折痕点,最后通过计算近邻点的平均位置点到采样点的欧式距离判别边界点,但边界点识别精度较低。Nurunnabi 等人[10]提出了Zscore 和马氏距离2 种鲁棒统计的点云特征检测算法,该方法基于局部邻域中的非异常点集来估计拟合平面,然后计算平面的法线和曲率检测棱线点,该算法棱线特征提取效果较好。麻卫峰等人[11]采用局部邻域熵最小化实现自适应邻域尺度选择和高斯核函数邻域点加权结合的主成分分析法(principal component analysis,PCA)来提高散乱点云的法向量估算精度,然后根据采样点和近邻点的法向量角度差识别特征点,该方法计算复杂度较高。史红霞等人[12]采用自适应邻域的主成分分析法计算点云法向量,通过使用萤火虫算法(firely algorithm,FA)优化模糊C 均值聚类算法提高边界特征点法向量分割比率,最后采用角度阈值方法对边界点进行剔除与合并。Ni 等人[13]提出了邻域几何属性分析(analysis of geometric properties of neighborhoods,APGN)方法,首先分析查询点邻域几何属性,采用随机抽样一致算法(random sample consensus,RANSAC)和角度准则来检测边缘点和折边点,然后通过区域增长和模拟混合方法提取特征线,该方法提取的边界粗糙。

上述2 类方法多是对现有封闭模型或只对某一类型特征点进行提取,不易对实际场景下包含多种特征类型的非封闭模型进行轮廓提取,且不易对每条轮廓线进行区分。此外,还有学者结合深度学习[14]、群智能优化[15]和神经网络[16]等方法,以获取更好的提取效果。

本文针对由RGB-D 相机采集到的物体点云轮廓提取精度问题,提出了一种适用于非封闭点云模型的轮廓提取方法。该方法利用主成分分析法计算点云局部邻域协方差矩阵和特征向量,进而获得点云法向量和表面曲率,初步用于提取棱线特征点,同时提出一种外边界检测算子,以提取外边界特征点。在获取轮廓特征点的基础上,采用三元组聚类方法分离和提取各条轮廓特征线。

1 点云轮廓特征提取方法

点云轮廓特征提取方法包含2 个阶段,如图1所示,第1 阶段为特征点检测,即对原始点云进行预处理后作为输入点云,采用曲率和法向夹角双判别参数检测模型棱线特征点,然后利用提出的边界检测算子检测外边界特征点;第2 阶段为特征线提取,即通过特征点相邻位置的平均值优化方法对检测出的特征点进行平滑,利用三元组聚类方法检测和分离轮廓曲线,具体步骤为:首先建立近似共线的3 个点为三元组,将三元组进行单链路聚类,再移除和拆分聚类后的三元组实现模型轮廓曲线的分割与提取,最后对分离出的各条边界进行曲线拟合。

图1 轮廓特征提取方法流程

2 轮廓特征点检测

点云表面法向量和曲率可描述散乱点云模型特征信息。根据点云局部邻域分布特征,对其进行主成分分析,求取最小特征值所对应特征向量为各点的法向量,最小特征值的方差贡献率为局部表面曲率;定义第2 主成分方差贡献率为所设计边界检测算子,二者结合进而提取模型轮廓特征点。

2.1 邻域点集几何分布特征

非封闭点云模型的轮廓线包括尖锐棱线和外边界线2 种,且数据点之间没有明显的拓扑关系。使用KD 树(K-dimensional tree,k-d tree)数据结构在搜索范围寻找k个离采样点P最近的点。根据点的分布情况又可为内部点和边界点,内部点的邻域点均匀分布其周围;越靠近边界的点,其近邻点下半部分的点越少;尖锐棱线点在2 个平(曲)面的交界处,特点是该点同两侧的点相比法向量角度变化大;若某一点的近邻点偏向一侧,则该点被认为是边界点。图2 所示为不同类型点的邻域分布情况。

图2 不同点的邻域分布

2.2 主成分分析法

主成分分析是一种常用的数据降维方法,其基本思想是将原坐标系下数据的m维高维特征映射成新坐标系下的n维低维特征。新坐标系下各维度数据量的大小反映在样本特征值的方差上,方差最大的方向作为第一主成分方向,各主成分包含的数据量通常用方差贡献率来衡量。主成分和方差贡献率的提取过程如下。

(1)原始数据中心化。将原始数据表示为n×m维的矩阵X,对X的每一行采用零均值化处理,即减去该行的均值,中心化后X由式(1)表示。

(2)主成分的确定。三维点云数据的样本矩阵为3 ×3 维,其原始数据采样点P(X,Y,Z) 的协方差矩阵C由式(2)表示。

其中Cov(x,y) 为采样点x,y的协方差。根据协方差矩阵C求得特征值并按顺序排列为λ1＞λ2＞λ3,所对应特征向量E=(v1,v2,v3) 即为各个主成分方向。

(3)方差贡献率的求取。

主成分方向上包含的数据量可用对应的特征值来描述,某一特征值所占各特征值之和的比例就是该主成分的方差贡献率,由式(3)表示。

方差贡献率是各主成分分量对原始数据信息保存精度的衡量指标,将方差贡献率控制在一定范围内,在对这些主成分进行压缩或投影时,达到数据损失的可能性降到最小的目的。

2.3 棱线特征点检测

在三维空间中若第3 主成分存在时,由主成分分析法可知,采样点及其邻域点共同组成了一个椭球,如图3 所示,椭球的3 个轴由3 个主成分所决定,特征值的大小也对应轴的长度。

图3 邻域空间椭球

其中,λ3是某一点邻域点集协方差矩阵的最小特征值,其对应的特征向量可作为整个目标点云的表面法向量。若将该主成分上的点抛弃,即忽略偏离近似平面的点,那么剩余点可看作是一个平面点云。对于尖锐边界特征而言,第3 主成分的方差贡献率远大于两侧平面的第3 主成分的贡献率,因此可用第3 主成分方差贡献率定义点云表面曲率变化,如式(4)所示。

协方差矩阵的最小特征值对应于最小相关性的维度,若平面点的协方差矩阵最小特征值为0,则表面曲率变化值为0;σn值越大,数据点所在曲面的曲率越大,该点为尖锐棱线特征点的概率越大。

同时,数据点和邻域点的法向量夹角也可以描述其所在局部曲面的变化情况,可用法向量夹角作为尖锐特征点的另一判断条件。因为采用主成分分析估算得到的点云法线具有二义性[11],所以需要引入一个视点pv,通过判断采样点法向量与视点和采样点所组成向量的夹角,使法向量朝向都趋于视点方向,当·(pv-pi)＞0 时,方向不变,否则方向取反。

已知采样点pi的近邻点为qj,近邻点法向量为nj,定义θi为采样点pi的法向量ni与近邻点的法向量nj夹角和的平均值,可用式(5)表示为

在实际环境中,深度相机获取的点云模型其平坦表面也会有一定的曲率变化,若σn大于设定阈值,可降低简化曲面带来的误差,将点标记为潜在特征点。然后再判断潜在特征点中各点的法向量夹角θi的变化程度是否大于设定阈值,若θi大于阈值,则将点进一步划分为尖锐特征点,否则舍弃该点。

2.4 边界检测算子

三维物体的立体性特点和深度相机从单一视角采集图像的原因,导致物体点云形状缺失,使原来内部折边变成外边界,其邻域点集也发生了变化。

当舍弃第3 主成分上的点时,椭球退化成一个椭圆,这时邻域点集的分布有以下3 种情况。

(1)当采样点pi为内部点时,邻域点分布在其周围,第1 主成分为椭圆长轴,第2 主成分为短轴,此时的椭圆短轴长度最大,如图4 所示。

图4 内部点邻域分布

(2)当采样点pi为内部点且靠近边界时,采样点下方的邻域点越来越少,此时所形成的椭圆短轴缩小,形状相较于内部点更为扁平,第1 主成分或第2 主成分的贡献率与内部点相比变小,如图5 所示。

图5 靠近边界点邻域分布

(3)当采样点为边界点时,近邻点只分布在采样点一侧,即采样点另一侧点集缺失,由主成分构成的椭圆进一步缩小,短轴长度达到最小,此时观察点在邻域内分布情况可得知第2 主成分量分远比内部点要小,如图6 所示。

图6 边界点邻域分布

根据点在不同位置的近邻域第2 主成分方差贡献率的变化,可定义边界检测算子如式(6)所示。

当Ab小于某一阈值γ时,即可认为该点为边界点。

3 轮廓特征线提取

使用边界检测方法可以较好地提取出轮廓点,但是目前的边界点并不是轮廓点,且棱线边界和外边界没有明显的区分,需要对轮廓点进行优化。三元组聚类方法是将曲线检测问题重新表述为点三元组上的聚类问题,对三元组进行距离测量,进而检测和分离点云中的曲线。

3.1 轮廓点优化

通过近邻点的位置平均进行轮廓点优化,减少周围干扰点的影响,达到曲线平滑的目的。查询每个点的K 邻域,计算邻域内每个点的平均坐标值,将该坐标值近似替换目标点的位置,式(7)所示。可对采样点P邻域进一步细化,如果近邻点到P点的距离小于设定阈值,则判定该点为点P邻域点,如式(8)所示。当分布在采样点P邻域内的点较稀疏时,点P的位置几乎保持不变;在近邻点稠密的区域,平均后的新采样点将会偏移至曲线中间。

3.2 轮廓曲线检测

三元组聚类方法是建立3 个近似共线点的组,即三元组[17]。然后对三元组进行分层聚类,用三元组聚类的标签标记其中的每个点,将三元组聚类转换为点聚类;每个聚类代表一个轨迹,不属于任何三元组的点被标记为噪声,属于多个三元组的点被标记为跳跃点。具体步骤如下。

(1)在边界点集中找到近似共线点的三元组。边界点集中近似共线的三个点集合称为三元组,假设每个采样点为三元组的中间点B,在该点K个邻域点内寻找端点A和C。如图7 所示。

图7 点三元组

设点云中点A、B和C的下标索引为i、j、k,即三元组所构成的α角定义如式(9)所示。

若三元组所构成α角的余弦值不在阈值a范围内,则舍弃该三元组,保留剩余三元组中角度最小的组。

(2)三元组的分层聚类。每个三元组通过2 个向量来描述,如式(10)和式(11)所示。将每个三元组作为一个单独的聚类开始,如果2 个聚类之间的距离小于设定自动阈值,则每次迭代中合并2 个聚类为1 个聚类。三元组的矢量表示如图8 所示。

图8 三元组的矢量表示

(3)最后通过移除较小聚类和通过分裂具有大间隙的聚类来进一步区分。将每个聚类中三元组数小于阈值m的聚类标记为噪声,根据聚类之间的间隙宽度分离并标记不同聚类,通过移除这些噪声和标记聚类将所属不同特征线的点区分开来。

4 实验结果与分析

本节将通过实验评估边界算法的有效性,使用InterCore i5 处理器作为上位机,所采用的深度相机是英特尔的RealSense D435,在Ubuntu 16.04 中基于PCL(point cloud library)和C++语言环境中对物体点云进行测试。本文实验数据来源于现有设备采集和PCL 官方点云示例以及PCLAIM@ SHAHE Shape Repository 数据库中的Fandisk 模型。

根据本文所用模型,通过测试各个参数组合来设置合理的参数范围,从而确定本文轮廓特征提取方法的参数值,设置见表1。

表1 参数列表

4.1 点云预处理

深度相机采集原始物体点云数据,因为相机视场角,造成所得到的数据存在缺失,同时也获取到除目标点云外包括背景或桌面等干扰环境信息,以及由于相机本身硬件、操作和环境等因素带来的影响。原始点云数据还会包含一些离群点,而且原始点云还存在着密度大、直接对其进行处理计算量大、速度慢等问题,所以需要对原始点云数据进行预处理,具体步骤如图9 所示。

图9 预处理步骤

首先对原始点云使用x和z方向上的直通滤波去除背景环境信息,使用统计学滤波去除离群点,采用体素栅格化滤波降低点云密度以提高后续点云处理算法的效率;其次对目标点云进行分割,采用随机抽样一致性算法检测点云图中的平面点云,将属于支撑平面中的点去除;最后对过平面分割后的点云进行欧式聚类分割,可将桌面上的多个物体分割为不同点云集对分割出的点云,从而提取出完整的待处理点云。

4.2 特征点检测方法对比

为了进一步验证特征点检测方法的可行性,选取由深度相机采集到的点云模型和Fandisk 点云模型进行特征点提取,并将本文算法所提取的点云轮廓特征点分别与文献[18]和[19]进行对比,提取结果如图10～12 所示。

图10 纸盒模型特征点提取

图10(a)是使用深度相机采集到的纸盒模型点云,该点云既包含棱线特征点,也包含外边界点,特征明显。文献[18]方法不能完整地检测出外边界点,棱线点存在误判。文献[19]能较好地提取出轮廓点,但其中一个角点不能完整识别。本文方法更加精确地提取了棱线特征点和外边界点。

图11(a)使用的是PCL 官方提供的牛奶模型点云,该点云由于采集视角原因具有尖锐棱线点和边界点,尖锐特征部分包含弱曲率点。文献[18]方法检测出的外边界在角点处有缺失且包含内部点,棱线特征点提取粗糙,仍然有部分缺失。文献[19]能较好地提取出轮廓点,但边界点和棱线点提取精度欠佳。本文方法完整地获取了牛奶模型的轮廓特征点,且提取较为精确。

图11 牛奶模型特征点提取

图12(a)所示点云是经过裁剪后的Fandisk 模型,该模型同时具有尖锐棱线、边界特征点和弱曲率点,特征点提取较难。文献[18]采用传统PCA 算法识别尖锐特征点,可见该方法存在非棱线特征点的误判。文献[19]的方法不易识别特征强度逐渐变弱的特征点,导致一些平滑过渡的特征点提取不完整。而本文方法对边界特征点和棱线特征点提取相对完整,存在较少的冗余数据点,识别效果相对较好。

图12 Fandisk 模型特征点提取

表2 展示3 种模型在文献[18]、文献[19]以及本文方法上的特征点(边界点和棱线点)和时间效率比较。文献[18]方法获取的非特征点较多导致精度降低,文献[19]能较好地提取出模型特征点,但精度有待提高,本文方法完整提取轮廓边界的同时,其时间效率也优于文献[18]和文献[19]方法。

表2 方法特征提取和时间对比

4.3 特征线提取结果有效性分析

为验证本文方法的可行性和有效性,对采集到的纸盒、水杯和牛奶点云模型进行轮廓特征点提取和特征线检测。特征点提取的结果如图13～15 所示。

图13 水杯模型特征线提取

图13(a)是对圆柱形水杯采集所得模型图。该模型结构简单,由一个半封闭曲面和圆形平面构成。图13(b)是模型经滤波、分割等预处理步骤所得物体点云集,具有边界特征和棱线特征。图13(c)为水杯模型特征点提取结果,表明本文方法能很好地提取模型轮廓特征点。从图13(d)中可以看出三元组聚类方法能精确检测出所属不同棱线和边界的特征点。

图14 为纸盒点云特征点提取结果。该点云同样是一个非封闭模型,既包含明显棱线特征又包含外边界特征。从图14(c)特征提取结果可以看出,本文方法对尖锐特征和边界特征均有较好的提取效果。图14(d)所示为三元组检测特征线结果,表明该方法能有效地检测和分离由特征点所组成曲线的集合。

图14 纸盒模型特征线提取

图15 模型相比图13、图14 中2 个模型结构相对复杂,外边界锯齿较为突出,2 个相邻平面之间过渡平滑,相交处的特征点法向量方向相近,曲率变化较小。图15(c)表明本文方法不仅较好地提取出边界特征点,而且对相对平滑处的棱线特征点提取较为完整。图15(d)表明三元组聚类方法对偏离曲线的点也能精确检测并标记为干扰点,在曲线的端点处用标记跳跃点方式来分离不同曲线,同时对曲线较多的模型也能精确检测和分离轮廓曲线。

图15 牛奶模型特征线提取

为了对本文方法的特征点和特征线提取结果进行定量评价,计算各模型特征点提取率和其所组成特征曲线长度提取率。轮廓特征点提取率由精确率和误识别率[13]计算所得,其中精确率prc为被正确提取的特征点占实际模型中特征点总数的比值;误识别率pmr为被错误识别的特征点占实际模型中特征点总数的比值。精确率和误识别率的计算公式如下:

式中,Nrc表示正确提取的特征点数;Nmr表示错误提取特征点数;Noc表示模型特征点总数。

每条特征线长度提取率为检测出线段长度和已知模型实际长度的比值,模型特征线总长度提取率为各条特征线段长度提取率的平均值[12]。因为实际采集获得的非封闭点云模型边界线可能为曲线,长度不易获得,所以对曲线边界点进行直线拟合近似估算曲线长度。拟合结果如图16～18 所示。模型特征线总长度提取率与单条特征线长度提取率的关系如下:

图16 水杯模型轮廓线拟合

图17 纸盒模型轮廓线拟合

图18 牛奶模型轮廓线拟合

式中,dm为第m条特征线的长度提取率(m=1,2,…,Tn);lm为拟合成该条特征线长度;Lm为该条特征线的实际长度;D为模型特征线总长度提取率。

各模型特征线定量评价结果如表3 所示。

表3 模型特征线提取率

由表3 可以看出,水杯模型的特征点得到了精确的提取,在曲线部分有少数特征点误判;纸盒模型的精确率prc较低是因为所提取特征点存在漏检,但所提取的点误识别率较低;由于牛奶模型的外边界存在曲率不同的点,所以边界点误识别率较高。3 种模型的提取精确率prc和特征线长度提取率D均在90%以上,表明本方法对实际点云模型的特征点和特征线提取有较好的效果。

5 结论

本文针对场景采集和现有的非封闭散乱点云轮廓提取问题,提出了一种轮廓边界提取方法并设计了一种边界检测算子。通过计算邻域点集的协方差矩阵分析数据点的曲率和邻域点的法向量夹角,获取尖锐棱线特征点;根据分析数据点在三维空间的分布情况,定义了一种边界检测算子,可以简单快速地检测出边界特征点;最后采用三元组聚类方法检测和分离轮廓曲线。实验结果表明,该方法不仅能有效获取物体点云的轮廓特征点,而且可对不同棱线进行标记区分,所设计的边界检测算子具有良好的检测精度和较高的运行效率,能够满足实际环境下对物体点云提取轮廓边界的需求。