基于局部特征描述子的點云配準

傳統的點云配準算法如icp算法在對兩組點云或多組點云進行配準時，一般都需要點云具備比較好的初始對齊姿態，這樣再使用迭代最近點的方法對兩兩點云進行配準。這種點云配準方法在需要對齊點云的應用場景中很常見。但他有比較強的限制條件，需要兩組點云有一個好的初始姿態。否則點云的配準會陷入局部最優解，無法完成點云間對齊。但在很多情況下，兩組點云沒有初始對齊姿態，其初始姿態是完全未知的。這種情況，可以使用局部特征描述子對兩組點云進行描述。局部特征描述子與點云姿態無關，僅與點云及其臨近點云形成的局部特征有關。利用這種信息，可以有效的完成點云的初始配準，為后續基于迭代最近點的精細配準，提供良好的初始姿態。下面根據不同的特征描述，分別介紹特征直方圖(Point Feature Histograms,PFH)、快速點特征直方圖(Fast Point Feature Histograms, FPFH)、視點特征直方圖VFH(Viewpoint Feature Histogram)。并分析他們的區別及優缺點。

引言

一堆離散的樣點，只包含相對于某個坐標系下的位置參數，雖然能在空間中比較好的顯示出物體的樣子來，但對于視覺來說，這是遠遠不夠的。之所以在文章的題目中提到特征，就是希望能用特征的方法，達到視覺識別的功能。

離散點云，除了坐標信息外，最為直觀的特征就是點、法向、曲率，這是最簡單的特征，也是最忠實于原始點云的，這些特征包含了點云的最為詳細的數據，雖然很少直接的使用，但在這個特征的基礎上，可以實現更高層次的識別。計算簡單，速度快是這些基礎特征的特點之一，但是在進行物體識別的時候，在大場景中，擁有相似法向或曲率的區域太多了，這就從一定程度上削弱了它的作用。

1. PFH

1.1 PFH原理

正如點特征表示法所示，表面法線和曲率估計是某個點周圍的幾何特征基本表示法。雖然計算非常快速容易，但是無法獲得太多信息，因為它們只使用很少的幾個參數值來近似表示一個點的k鄰域的幾何特征。然而大部分場景中包含許多特征點，這些特征點有相同的或者非常相近的特征值，因此采用點特征表示法，其直接結果就減少了全局的特征信息。本小節介紹三維特征描述子中的一位成員：點特征直方圖(Point Feature Histograms)，我們簡稱為PFH，本小節將介紹它的理論優勢，從PCL實現的角度討論其實施細節。PFH特征不僅與坐標軸三維數據有關，同時還與表面法線有關。

PFH計算方式通過參數化查詢點與鄰域點之間的空間差異，并形成一個多維直方圖對點的k鄰域幾何屬性進行描述。直方圖所在的高維超空間為特征表示提供了一個可度量的信息空間，對點云對應曲面的6維姿態來說它具有不變性，并且在不同的采樣密度或鄰域的噪音等級下具有魯棒性。點特征直方圖（PFH）表示法是基于點與其k鄰域之間的關系以及它們的估計法線，簡言之，它考慮估計法線方向之間所有的相互作用，試圖捕獲最好的樣本表面變化情況，以描述樣本的幾何特征。因此，合成特征超空間取決于每個點的表面法線估計的質量。如圖1所示，表示的是一個查詢點(Pq) 的PFH計算的影響區域，Pq 用紅色標注并放在圓球的中間位置，半徑為r， (Pq)的所有k鄰元素（即與點Pq的距離小于半徑r的所有點）全部互相連接在一個網絡中。最終的PFH描述子通過計算鄰域內所有兩點之間關系而得到的直方圖，因此存在一個O(k) 的計算復雜性。

圖1 查詢點 的PFH計算的影響區域

為了計算兩點Pi和Pj及與它們對應的法線Ni和Nj之間的相對偏差，在其中的一個點上定義一個固定的局部坐標系，如圖2所示。

圖2 定義一個固定的局部坐標系

為查詢點創建最終的PFH表示，所有的四元組將會以某種統計的方式放進直方圖中，這個過程首先把每個特征值范圍劃分為b個子區間，并統計落在每個子區間的點數目，因為四分之三的特征在上述中為法線之間的角度計量，在三角化圓上可以將它們的參數值非常容易地歸一到相同的區間內。一個統計的例子是：把每個特征區間劃分成等分的相同數目，為此在一個完全關聯的空間內創建有b個區間的直方圖。在這個空間中，一個直方圖中某一區間統計個數的增一對應一個點的四個特征值。

圖3 點云中不同點的點特征直方圖表示法

1.3 PFH的總結

點特征的描述子一般是基于點坐標、法向量、曲率來描述某個點周圍的幾何特征。用點特征描述子不能提供特征之間的關系，減少了全局特征信息。因此誕生了一直基于直方圖的特征描述子：PFH–point feature histogram（點特征直方圖）。

PFH通過參數化查詢點和緊鄰點之間的空間差異，形成了一個多維直方圖對點的近鄰進行幾何描述，直方圖提供的信息對于點云具有平移旋轉不變性，對采樣密度和噪聲點具有穩健性。PFH是基于點與其鄰近之間的關系以及它們的估計法線，也即是它考慮估計法線之間的相互關系，來描述幾何特征。

PFH的缺點：

計算復雜度高。已知點云P中有n個點，假設點云均勻密度，每點在鄰域半徑r內平均可以選到k個近鄰，該算法對每個點來說計算PFH的時間復雜度為O(k^2)，那么它的點特征直方圖（PFH）的理論計算復雜度就是 O(nk2)。對于實時應用或接近實時應用中，密集點云的點特征直方圖（PFH）的計算，O(nk2)的計算復雜度實在不敢恭維，是一個主要的性能瓶頸。

2. FPFH

2.1 FPFH原理

快速點特征直方圖(Fast Point Feature Histograms, FPFH)是PFH計算方式的簡化形式。它的思想在于分別計算查詢點的k鄰域中每一個點的簡化點特征直方圖(Simplified Point Feature Histogram,SPFH)，再通過一個公式將所有的SPFH加權成最后的快速點特征直方圖。FPFH把算法的計算復雜度降低到了O(nk) ，但是任然保留了PFH大部分的識別特性。

FPFH計算過程：

只計算每個查詢點Pq和它鄰域點之間的三個特征元素（參考PFH），在這里不同于PFH：PFH是計算鄰域點所有組合的特征元素，而這一步只計算查詢點和近鄰點之間的特征元素。如下圖，第一個圖是PFH計算特征過程，即鄰域點所有組合的特征值（圖中所有連線，包括但不限于Pq和Pk之間的連線），第二個圖是FPFH的計算內容，只需要計算Pq（查詢點）和緊鄰點（圖2中紅線部分）之間的特征元素。可以看出降低了復雜度我們稱之為SPFH（simple point feature histograms）。

2.2 FPFH與PFH的主要區別

FPFH沒有對全互連點的所有鄰近點的計算參數進行統計，因此可能漏掉了一些重要的點對，而這些漏掉的對點可能對捕獲查詢點周圍的幾何特征有貢獻。PFH特征模型是對查詢點周圍的一個精確的鄰域半徑內，而FPFH還包括半徑r范圍以外的額外點對（但不超過2r的范圍）；因為采用權重計算的方式，所以FPFH結合SPFH值，重新捕獲鄰近重要點對的幾何信息；由于大大地降低了FPFH的整體復雜性，因此FPFH有可能使用在實時應用中。

3. VFH

3.1 VFH原理

視點特征直方圖VFH(Viewpoint Feature Histogram)描述子，它是一種新的特征表示形式，應用在點云聚類識別和六自由度位姿估計問題。下圖展示了VFH識別和位姿估計的一個例子。已知一組訓練樣本數據（除最左端的點云之外的首行，底行），學習了一個模型，然后使用一個點云（左下方）來查詢/測試這個模型。從左下方開始，匹配結果從左到右是按照最好到最壞的順序排列的。

視點特征直方圖（或VFH）是源于FPFH描述子（見Fast Point Feature Histograms (PFH) 描述子）。由于它的獲取速度和識別力，我們決定利用FPFH強大的識別力，但是為了使構造的特征保持縮放不變性的性質同時，還要區分不同的位姿，計算時需要考慮加入視點變量。我們做了以下兩種計算來構造特征，以應用于目標識別問題和位姿估計：

擴展FPFH，使其利用整個點云對象來進行計算估計（如下圖所示），在計算FPFH時以物體中心點與物體表面其他所有點之間的點對作為計算單元。2. 添加視點方向與每個點估計法線之間額外的統計信息，為了達到這個目的，我們的關鍵想法是在FPFH計算中將視點方向變量直接融入到相對法線角計算當中。

通過統計視點方向與每個法線之間角度的直方圖來計算視點相關的特征分量。注意：并不是每條法線的視角，因為法線的視角在尺度變換下具有可變性，我們指的是平移視點到查詢點后的視點方向和每條法線間的角度。第二組特征分量就是前面PFH中講述的三個角度，如PFH小節所述，只是現在測量的是在中心點的視點方向和每條表面法線之間的角度，如下圖所示。

因此新組合的特征被稱為視點特征直方圖（VFH）。下圖表體現的就是新特征的想法，包含了以下兩部分：

1. 一個視點方向相關的分量

2. 一個包含擴展FPFH的描述表面形狀的分量

如有侵權，聯系刪除