對于點云中的任意兩點，其距離關(guān)系和方向關(guān)系（兩點的法線方向）可以用來描述這一對點，并且描述的特征點具有可區(qū)分性。

由此，我們定義一個四維向量F，來描述這一對點的PPF特征：

四維F包含一個長度，三個角度F即POINT PAIR FEATURE

model是預(yù)先做好的，用來匹配scene中的目標object。可以從CAD模型轉(zhuǎn)換得來，或者借助深度設(shè)備獲得。一般的步驟是對model進行下采樣，通常采用voxel grid的方法。目的是減少計算，提高效率。對model中所有可能的點對，計算PPF特征，得到大量的四維向量。將這些四維向量存儲起來，用于后面match時候的查找。

如何對計算出來特征點的描述子進行存儲比較有效率？借助哈希表。F下取整作為索引。索引怎么創(chuàng)建？使用如下的急撒U呢公式：

x1-x4表示剛才所說的四維向量F，給與步長△，下取整。這樣就構(gòu)件了一個“索引”到“F”的對應(yīng)關(guān)系，我們就能把剛才計算得到的特征F整合到一些區(qū)間（同一區(qū)間中點對具有相似的特征）。

長度步長和角度步長△怎么選？

長度步長:取模型直徑的0.05倍（模型直徑可以通過求包圍盒相關(guān)操作得到）

角度步長：π/15

實際上這一節(jié)主要做兩個工作：1、求出模型中所有點對的PPF特征，2、求出F的哈希表索引，按照索引將所有的PPF特征存儲在哈希表（如下圖），用于后續(xù)match階段查找。

這一部分屬于線上部分。模型的部分描述子的計算以及存儲都是可以提前做好的。

對于場景點云，數(shù)量肯定要遠大于MODEL點云，我們隨機選取場景中五分之一的點作為reference points，對于每一個reference point，計算他和其余場景所有點的點對特征F。

理解文章中所謂的局部坐標系是關(guān)鍵。對于場景中的一對點對，我們計算出他的PPF：Fs，以此為索引查找model的哈希表，假如查找成功，便得到了一些特征差不多的模型中的點對。以模型中的與場景點對匹配的一個點對為例，我們需要把，模型點對和場景點對統(tǒng)一到同一個坐標系下，（這個坐標系人為是永恒不變的global coordinate）如圖所示

讓參考點重合，參考點的法線重合，這很容易做到，因為參考點和參考點點的法線都是已知的，也因為如此，圖中的變換關(guān)系Tsg，Tmg都是可求的。此時場景點對的位姿與模型點對的位姿差一個角度α，通過α，能最終算出來場景點對和模型點對的變換關(guān)系。如下式子（s表示場景，m代表model，g代表假設(shè)的一個公共坐標系）：

總結(jié)起來:對于場景中的一個參考點sr，與場景中的其他點si，配成點對，算F，查找哈希表，找到一對點mr、mi，執(zhí)行上圖的變換，得到α。 文章中稱（mr，α）為參考點sr的一個局部坐標系，上述部分是以一對場景點和一對模型點為例的，如果這個（mr，α）是絕對可靠的，我們完全可以利用上面的變換求出模型在場景中的位姿；但是，一對點對的決定往往是極度不可靠的，我們需要對所有點對執(zhí)行上述操作，得到大量的不同的（mr，α），然后進行投票，票數(shù)最高的（mr，α），能決定真實位姿，用它來解算位姿。這就是下面要講的廣義霍夫變換投票方式。

位姿是投票投出來的，如何投票產(chǎn)生的？上面已經(jīng)說了，對于一個場景參考點sr，它的一個場景點對srsi的PPF特征有可能可以找到相對應(yīng)的模型點對mrmi（srsi與mrmi的PPF特征近似），找到以后，sr與mr匹配，得到一個旋轉(zhuǎn)角α，一旦我們有mr，有α，就可以求位姿。現(xiàn)在，建立一個二維矩陣：橫坐標為α，縱坐標為mr。對于一個場景參考點sr，他有大量的點對srsi（i∈scene cloud），對所有的srsi求PPF，由此找到哈希表對應(yīng)的mr’mi’，同時得到一個α’。那么，我們就在建立的二維矩陣上，投一個票。對這一個場景參考點sr的所有點對srsi都進行這個操作，最后就得到了一個投票表。（注意：這個投票表示針對這個特定的參考點sr的），表一定有一個峰值，這個峰值對應(yīng)的mr’’，α'’便是這個場景參考點sr的最佳局部坐標系，由mr’’，α'’算出的來的位姿，視為最理想位姿（假設(shè)這個場景參考點sr一開始就在場景目標中，而不是在場景中其他的物體上）

多說一句，投票矩陣怎么建立？縱坐標是模型點數(shù)，因為我們在線下階段對模型中的所有點對都求取了PPF，所以任何一個模型點都可以是mr；橫坐標是α，其值是（2π/△angle），并上取整。（△angle仍取π/15）

那么，我們在之前說到，場景參考點選scene中點數(shù)量的五分之一，對于每一個sr，都有一個投票表，都可以算出一個位姿?，F(xiàn)在需要聚類獲得最準確的結(jié)果。（因為并不是所有的sr都是在目標物體上，畢竟sr是隨機取樣的），把相近的位姿放到一起作為一類（這些位姿在旋轉(zhuǎn)和平移上不超過一個既定閾值），這個類有一個分數(shù)（分數(shù)=類中所有位姿在上一階段的投票數(shù)之和），分數(shù)最高的類，我們將類中的pose取平均，認定為最終的pose。同時，scene中可能有不止一個的目標，我們?nèi)シ謹?shù)最高的兩個類，作為結(jié)果

同時為了提高算法效率，在計算α?xí)r候做了一些改進，正常來說，sr與mr重合并且兩者的法向量重合以后，計算srsi與mrmi角度，這樣每次匹配都得重新計算一次，比較麻煩。將α分成兩部分，一部分αm，是model的那一部分，所有的mrmi的αm可以線下提前算好，存起來，用的時候直接用；另一部分αs，是scene的那一部分，對于所有srsi，線上的時候只需要計算一次，存起來，后面用到就直接調(diào)用。

總結(jié)：PPF方法在bin-picking問題中具有強大的生命力，即使在深度學(xué)習(xí)盛行的今天，其算法性能仍然是不亞于深度學(xué)習(xí)方法。 正是因為其優(yōu)越性，后續(xù)很多學(xué)者對PPF做了大量的改進，無論宏觀微觀，PPF的模樣仍然沒有明顯的變化。Kiforenko等人對今年來所有的PPF變種進行了徹底的對比和分析，大家可以去查閱。 近年比較好的一篇PPF文章由Vidal等人發(fā)表在Sensors（2018），其對PPF整體的各個細節(jié)精準的改進，算法性能也有所提高。這篇文章后續(xù)給大家分享。

目前微信交流群不斷壯大，由于人數(shù)太多，目前有兩個群，為了鼓勵大家分享，我們希望大家能在學(xué)習(xí)的同時積極分享，將您的問題或者小總結(jié)投稿發(fā)到群主郵箱主郵箱dianyunpcl@163.com。