三维识别与位姿估计——Surafce Matching

一、什么是点对特征——PPF？

对于点云中的任意两点，其距离关系和方向关系（两点的法线方向）可以用来描述这一对点，并且描述的特征点具有可区分性。

由此，我们定义一个四维向量F，来描述这一对点的PPF特征：

四维F包含一个长度，三个角度F即POINT PAIR FEATURE

二、什么是model globally？如何操作？

model是预先做好的，用来匹配scene中的目标object。可以从CAD模型转换得来，或者借助深度设备获得。一般的步骤是对model进行下采样，通常采用voxel grid的方法。目的是减少计算，提高效率。对model中所有可能的点对，计算PPF特征，得到大量的四维向量。将这些四维向量存储起来，用于后面match时候的查找。

如何对计算出来特征点的描述子进行存储比较有效率？借助哈希表。F下取整作为索引。索引怎么创建？使用如下的急撒U呢公式：

x1-x4表示刚才所说的四维向量F，给与步长△，下取整。这样就构件了一个“索引”到“F”的对应关系，我们就能把刚才计算得到的特征F整合到一些区间（同一区间中点对具有相似的特征）。

长度步长和角度步长△怎么选？

长度步长:取模型直径的0.05倍（模型直径可以通过求包围盒相关操作得到）

角度步长：π/15

实际上这一节主要做两个工作：1、求出模型中所有点对的PPF特征，2、求出F的哈希表索引，按照索引将所有的PPF特征存储在哈希表（如下图），用于后续match阶段查找。

三、什么是match locally？如何实现？

这一部分属于线上部分。模型的部分描述子的计算以及存储都是可以提前做好的。

01

场景PPF计算

对于场景点云，数量肯定要远大于MODEL点云，我们随机选取场景中五分之一的点作为reference points，对于每一个reference point，计算他和其余场景所有点的点对特征F。

02

local coordinate

理解文章中所谓的局部坐标系是关键。对于场景中的一对点对，我们计算出他的PPF：Fs，以此为索引查找model的哈希表，假如查找成功，便得到了一些特征差不多的模型中的点对。以模型中的与场景点对匹配的一个点对为例，我们需要把，模型点对和场景点对统一到同一个坐标系下，（这个坐标系人为是永恒不变的global coordinate）如图所示

让参考点重合，参考点的法线重合，这很容易做到，因为参考点和参考点点的法线都是已知的，也因为如此，图中的变换关系Tsg，Tmg都是可求的。此时场景点对的位姿与模型点对的位姿差一个角度α，通过α，能最终算出来场景点对和模型点对的变换关系。如下式子（s表示场景，m代表model，g代表假设的一个公共坐标系）：

总结起来:对于场景中的一个参考点sr，与场景中的其他点si，配成点对，算F，查找哈希表，找到一对点mr、mi，执行上图的变换，得到α。 文章中称（mr，α）为参考点sr的一个局部坐标系，上述部分是以一对场景点和一对模型点为例的，如果这个（mr，α）是绝对可靠的，我们完全可以利用上面的变换求出模型在场景中的位姿；但是，一对点对的决定往往是极度不可靠的，我们需要对所有点对执行上述操作，得到大量的不同的（mr，α），然后进行投票，票数最高的（mr，α），能决定真实位姿，用它来解算位姿。这就是下面要讲的广义霍夫变换投票方式。

03

Generalize hough-like voting scheme

位姿是投票投出来的，如何投票产生的？上面已经说了，对于一个场景参考点sr，它的一个场景点对srsi的PPF特征有可能可以找到相对应的模型点对mrmi（srsi与mrmi的PPF特征近似），找到以后，sr与mr匹配，得到一个旋转角α，一旦我们有mr，有α，就可以求位姿。现在，建立一个二维矩阵：横坐标为α，纵坐标为mr。对于一个场景参考点sr，他有大量的点对srsi（i∈scene cloud），对所有的srsi求PPF，由此找到哈希表对应的mr’mi’，同时得到一个α’。那么，我们就在建立的二维矩阵上，投一个票。对这一个场景参考点sr的所有点对srsi都进行这个操作，最后就得到了一个投票表。（注意：这个投票表示针对这个特定的参考点sr的），表一定有一个峰值，这个峰值对应的mr’’，α‘’便是这个场景参考点sr的最佳局部坐标系，由mr’’，α‘’算出的来的位姿，视为最理想位姿（假设这个场景参考点sr一开始就在场景目标中，而不是在场景中其他的物体上）

多说一句，投票矩阵怎么建立？纵坐标是模型点数，因为我们在线下阶段对模型中的所有点对都求取了PPF，所以任何一个模型点都可以是mr；横坐标是α，其值是（2π/△angle），并上取整。（△angle仍取π/15）

04

位姿聚类

那么，我们在之前说到，场景参考点选scene中点数量的五分之一，对于每一个sr，都有一个投票表，都可以算出一个位姿。现在需要聚类获得最准确的结果。（因为并不是所有的sr都是在目标物体上，毕竟sr是随机取样的），把相近的位姿放到一起作为一类（这些位姿在旋转和平移上不超过一个既定阈值），这个类有一个分数（分数=类中所有位姿在上一阶段的投票数之和），分数最高的类，我们将类中的pose取平均，认定为最终的pose。同时，scene中可能有不止一个的目标，我们去分数最高的两个类，作为结果

核心

同时为了提高算法效率，在计算α时候做了一些改进，正常来说，sr与mr重合并且两者的法向量重合以后，计算srsi与mrmi角度，这样每次匹配都得重新计算一次，比较麻烦。将α分成两部分，一部分αm，是model的那一部分，所有的mrmi的αm可以线下提前算好，存起来，用的时候直接用；另一部分αs，是scene的那一部分，对于所有srsi，线上的时候只需要计算一次，存起来，后面用到就直接调用。

总结：PPF方法在bin-picking问题中具有强大的生命力，即使在深度学习盛行的今天，其算法性能仍然是不亚于深度学习方法。 正是因为其优越性，后续很多学者对PPF做了大量的改进，无论宏观微观，PPF的模样仍然没有明显的变化。Kiforenko等人对今年来所有的PPF变种进行了彻底的对比和分析，大家可以去查阅。 近年比较好的一篇PPF文章由Vidal等人发表在Sensors（2018），其对PPF整体的各个细节精准的改进，算法性能也有所提高。这篇文章后续给大家分享。