在PPF算法中，我們的目的是希望通過已有模型，能夠在一個(gè)場(chǎng)景中匹配到和模型相似的目標(biāo)。這是模板匹配最直觀的說法。

圖1 PPF算法論文

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

（一） 整體建模

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

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

圖2 模型特征點(diǎn)對(duì)和哈希表

（二） 局部匹配

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

? 將這兩個(gè)參考點(diǎn)配準(zhǔn)，需同時(shí)將點(diǎn)的位置和法向量對(duì)齊。通過變換矩陣將模型的特征點(diǎn)對(duì)移動(dòng)到一個(gè)新的空間上的原點(diǎn)，使其法向量軸與該空間的x軸重合。同理，將場(chǎng)景點(diǎn)云的特征點(diǎn)對(duì)做相同操作。

圖3 模型點(diǎn)云點(diǎn)對(duì)特征和場(chǎng)景點(diǎn)云點(diǎn)對(duì)特征的配準(zhǔn)

（三） 投票

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

? 之前我們?cè)谡w建模的過程中計(jì)算了模型點(diǎn)云的特征點(diǎn)對(duì)，現(xiàn)在我們對(duì)場(chǎng)景點(diǎn)云也做一次特征點(diǎn)對(duì)的計(jì)算；

? 以場(chǎng)景點(diǎn)云的特征點(diǎn)對(duì)作為key，去搜索整體建模時(shí)計(jì)算的哈希表，找到與場(chǎng)景點(diǎn)云特征點(diǎn)對(duì)相似的模型點(diǎn)云特征點(diǎn)對(duì)；

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

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

圖4 場(chǎng)景特征點(diǎn)對(duì)搜索模型特征點(diǎn)對(duì)的哈希表

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

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