3D模板匹配算法概述

在PPF算法中，我们的目的是希望通过已有模型，能够在一个场景中匹配到和模型相似的目标。这是模板匹配最直观的说法。

图1 PPF算法论文

“Model Globally，, Match Locally”，顾名思义“整体建模，局部匹配”，因此算法是先对模型进行处理，再进行模型与目标匹配。算法流程如下：

（一） 整体建模

根据已建立的3D模型，计算3D模型表面上的特征点对的特征矢量;构建哈希表(Hash

table)，将具有相同特征矢量的点对放在一起，如图2所示。

图2 模型特征点对和哈希表

（二） 局部匹配

• 在场景点云中任意选取一个参考点，假设它在物体的表面上，若假设正确，则在模型上存在一个点与之对应；

• 将这两个参考点配准，需同时将点的位置和法向量对齐。通过变换矩阵将模型的特征点对移动到一个新的空间上的原点，使其法向量轴与该空间的x轴重合。同理，将场景点云的特征点对做相同操作。

图3 模型点云点对特征和场景点云点对特征的配准

（三） 投票

在局部匹配中，我们引入了一个新的空间，现在需要想方法，每个变换中找到一个最优的变换矩阵，使得场景点云中落在模型点云表面的特征点最多，就能求得目标的位姿。论文通过投票机制实现，定义一个二维的数组，行数（row）为模型点云特征点对个数，列数（columns）为按采样步长的旋转角α个数。

• 之前我们在整体建模的过程中计算了模型点云的特征点对，现在我们对场景点云也做一次特征点对的计算；

• 以场景点云的特征点对作为key，去搜索整体建模时计算的哈希表，找到与场景点云特征点对相似的模型点云特征点对；

• 计算出两个点对之间的旋转角α，对二维数组中离散的角度对应位置投票+1；

• 全部计算完后，就可以得到最大票数对应的模型点云特征点对和旋转角。

图4 场景特征点对搜索模型特征点对的哈希表

投票完成后，对于每一个场景点云特征点对，我们都到了一组满足条件的姿态。对于所有的姿态，通过聚类将之分成多个组。计算每个组内所有姿态的分数加权和作为该组的一个评分。每个姿态的分数即为该姿态在投票环节所得的票数。选取分数最高的组的所有姿态的均值作为最终的结果。

图5 PPF算法匹配结果