在PPF算法中，我們的目的是希望通過已有模型，能夠在一個場景中匹配到和模型相似的目標。這是模板匹配最直觀的說法。

圖1 PPF算法論文

“Model Globally，, Match Locally”，顧名思義“整體建模，局部匹配”，因此算法是先對模型進行處理，再進行模型與目標匹配。算法流程如下：

（一） 整體建模

根據已建立的3D模型，計算3D模型表面上的特征點對的特征矢量;構建哈希表(Hash

table)，將具有相同特征矢量的點對放在一起，如圖2所示。

圖2 模型特征點對和哈希表

（二） 局部匹配

? 在場景點云中任意選取一個參考點，假設它在物體的表面上，若假設正確，則在模型上存在一個點與之對應；

? 將這兩個參考點配準，需同時將點的位置和法向量對齊。通過變換矩陣將模型的特征點對移動到一個新的空間上的原點，使其法向量軸與該空間的x軸重合。同理，將場景點云的特征點對做相同操作。

圖3 模型點云點對特征和場景點云點對特征的配準

（三） 投票

在局部匹配中，我們引入了一個新的空間，現在需要想方法，每個變換中找到一個最優的變換矩陣，使得場景點云中落在模型點云表面的特征點最多，就能求得目標的位姿。論文通過投票機制實現，定義一個二維的數組，行數（row）為模型點云特征點對個數，列數（columns）為按采樣步長的旋轉角α個數。

? 之前我們在整體建模的過程中計算了模型點云的特征點對，現在我們對場景點云也做一次特征點對的計算；

? 以場景點云的特征點對作為key，去搜索整體建模時計算的哈希表，找到與場景點云特征點對相似的模型點云特征點對；

? 計算出兩個點對之間的旋轉角α，對二維數組中離散的角度對應位置投票+1；

? 全部計算完后，就可以得到最大票數對應的模型點云特征點對和旋轉角。

圖4 場景特征點對搜索模型特征點對的哈希表

投票完成后，對于每一個場景點云特征點對，我們都到了一組滿足條件的姿態。對于所有的姿態，通過聚類將之分成多個組。計算每個組內所有姿態的分數加權和作為該組的一個評分。每個姿態的分數即為該姿態在投票環節所得的票數。選取分數最高的組的所有姿態的均值作為最終的結果。

圖5 PPF算法匹配結果