3D模板匹配算法概述

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

圖1 PPF算法論文

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

（一） 整體建模

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

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

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

（二） 局部匹配

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

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

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

（三） 投票

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

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

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

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

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

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

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

圖5 PPF算法匹配結(jié)果