基于点对特征的三维点云匹配算法*

易 杰， 李 蹊， 易辉成， 刘 苗， 钟 凯， 胡 兴

(1.湖南工业职业技术学院，湖南 长沙 410208；2.华中科技大学 材料成形与模具技术国家重点实验室，湖北 武汉 430074；3.湖南航天天麓新材料检测有限责任公司，湖南 长沙 410600)

0 引 言

三维物体识别旨在实现三维场景中目标物体的检测及定位，在工农业已得到了广泛的应用[1]。目前，三维物体识别方法主要有两大类：基于全局特征的识别方法[2]和基于局部特征的识别方法[3]。全局特征识别方法需要从场景中将待检测的物体分割出来，然后将该物体与要搜索的目标物体表面的全部或最显著的几何特征进行对比，从而把场景中的目标物体识别出来；而局部方法则是由局部信息来识别整体，只需要从场景中提取出关键点、面片等局部特征并与要搜索的目标物体进行比对就可以把场景中的目标物体识别出来。两类方法各有特点，但在有遮挡和混叠的场景中识别效果均不理想。

在全局特征识别方法方面，Rabbani T[4]等人使用广义霍夫变换的变体来识别物体，由于恢复三维姿态计算量巨大，该方法仅适用于立方体、球体等形状简单的物体；Park I K[5]通过对物体的模式进行比对从而识别出场景中的目标物体，该方法的计算量较大，需采用GPU进行加速。

在局部特征识别方法方面，Chua C[6]等人提出了一种基于点签名的三维物体识别方法，将点签名作为匹配依据从而识别出场景中的目标物体，该方法对噪声比较敏感，且易出现误匹配；Rusu R B[7]等人提出了一种基于点特征直方图的三维物体识别方法，通过比对直方图上的统计信息从而把场景中的目标物体识别出来，但该方法同样存在计算量大、识别速度较慢的问题。

为了保证三维物体在有遮挡和混叠场景中的识别效果，本文提出一种基于点对特征的三维点云匹配算法，此算法融合基于点对特征的全局模型描述和基于快速投票方案的局部曲面匹配方法，无需对场景进行分割，对遮挡和混叠具有良好的适应性。

1 基于点对特征的全局模型描述构建

点对特征[8]可以用来描述两个点的相对位置以及法线方向。对于任意两个点m1,m2以及它们各自的法矢量n1,n2，令差矢量d=m2-m1，并且定义特征F为

F(m1,m2)=(‖d‖2,∠(n1,d),∠(n2,d),

∠(n1,n2))

(1)

点对特征F的4个分量如图1所示。

图1 点对特征

全局模型描述表示从点对特征空间到模型的映射，具体来说是把四维点对特征映射到具有相似特征向量的点对(mi,mj)∈M2上。图2显示了全局模型描述构建的过程，具有相似特征的模型点对会被存储在哈希表的同一个槽中，场景特征Fs(sτ,si)作为哈希表的钥匙可以把与它相似的所有模型特征Fm(mi,mj)在一定的时间内搜索出来。

图2 全局模型描述

2 基于快速投票方案的局部曲面匹配

2.1 基于投票方案的目标姿态生成

对于场景上的任意一个参考点sτ∈S，如果该参考点处在要检测的目标物体之上，则一定会存在一个来自模型上的点mτ∈M与之对应。只要将这两个点以及其法线对齐，再围绕场景参考点sτ的法线旋转一定的角度即可让模型和场景对齐，从而生成目标物体的姿态。模型到场景的刚性变换由模型上的一个参考点mτ和一个旋转角α来表示，(mτ,α)即为模型相对于场景参考点sτ的局部坐标为

(2)

图3为投票方案的具体过程：1)把场景参考点sτ和场景中的任意其它点si组成点对，并计算特征向量Fs(sτ,si)；2)将具有相似特征向量的模型点对(mτ,mi)∈M2存储在哈希表的同一个槽中，并把场景点对的特征向量Fs(sτ,si)作为哈希表的钥匙对哈希表进行检索，返回具有相似特征向量的模型点对；3)对于上述返回的每一个模型点对，通过求解式(2)计算旋转角α；4)旋转角α计算出来之后，在二维累加器上给局部坐标(mτ,α)投上一票。

图3 投票方案流程

上述过程都完成后，投票数最高的局部坐标即为最优局部坐标。一般来说，最优局部坐标对应的姿态就是目标物体在场景中的真实姿态，但出于稳定性的考虑，那些投票数较高的局部坐标也在本文作者考虑范围之内。

2.2 基于聚类和迭代最近点的目标姿态优化

采样生成的目标姿态并不完全等于目标物体在场景中的真实姿态，需要通过聚类来提高目标姿态的准确性。

姿态聚类即把平移和旋转的差异都不超过设定阈值的姿态聚在一起，然后再对这些姿态取平均值作为最终的姿态。聚类的投票数为该聚类中所有姿态投票数的总和，对投票数最高的聚类中的姿态求平均值就可以得到最终的姿态。同上一节，出于稳定性的考虑，那些投票数较高的聚类也在本文考虑范围之内。

经过聚类之后，目标姿态的准确性得到了提高，但与真实的姿态相比仍然存在一些差距，需要通过迭代最近点(ICP)对目标姿态做进一步的优化，即实现目标姿态点云和场景点云的配准。

2.3 基于Kd-Tree算法的目标姿态筛选

由于投票数较高的姿态都有可能是目标物体在场景中真实的姿态，因此需要对这些姿态进行筛选，从而把真实的目标姿态判断出来。考虑到真实的目标姿态点云与场景点云部分重合，即匹配点数目较多；而虚假的目标姿态点云则相反。因此，利用Kd-Tree最近邻搜索统计目标姿态点云与场景点云匹配点的个数，当大于某一阈值时就可以认为该姿态是真实的姿态。值得注意的是，这里提到的匹配点指的是相对距离以及法线夹角都比较小的点对。

Kd-Tree有半径查询以及K近邻查询两种查询方式，下面以半径查询为例对目标姿态筛选算法的流程进行介绍。距离阈值表示为DistanceThreshold，法线夹角的阈值表示为AngleThreshold，匹配点数目的阈值表示为NumThreshold。

基于Kd-Tree的目标姿态筛选算法的具体实现步骤如下：

1)读取目标姿态点云Ptarget和场景点云Pscene；

2)将Ptarget中的任意一个点pi作为查询点，Pscene作为被查询的对象；

3)在Pscene中找出满足‖dist(pi,si)‖2

5)遍历Ptarget上的点，统计匹配点的总数，记为num,判断num≥NumThreshold是否成立，若成立，则该姿态是目标物体在场景中真实的姿态。

3 实验验证

本文采用华中科技大学快速制造中心研发的PowerScan面结构光三维测量设备获取点云数据进行实验验证。所用设备由2个工业相机和1个数字光栅投影仪组成，单次测量范围为500 mm×400 mm，单次测量误差为±0.03 mm。

3.1 实验方案设计

设计了无遮挡和混叠以及有遮挡和混叠两类场景进行对比。目标物体选为三通管，如图4所示。

图4 三通管

3.2 实验结果与分析

本文算法的识别效果如图5所示。

图5 识别效果

对于不同复杂程度的场景，本文算法的识别率和识别时间如表1所示。

表1 不同场景的识别率和识别时间

表1可知，本文算法在无遮挡和混叠的场景中识别率很高，在有遮挡和混叠的场景中识别率略有降低，但依然处在一个较高的水平；此外，本文算法的识别时间均小于4 s，识别速度较快，如果不通过ICP进行配准那么识别时间均小于1 s，识别速度就很快。

综上，本文的算法在有遮挡和混叠的场景中识别效果较为理想，具备一定的抗遮挡和混叠性能。

4 结 论

提出了一种基于点对特征的三维点云匹配算法。该算法融合了基于点对特征的全局模型描述和基于快速投票方案的局部曲面匹配方法，从而有效规避了全局方法和局部方法各自的不足。实验结果表明，所提算法对于有遮挡和混叠的场景识别效果较为理想。