基于FPFH的點云特征點提取算法

賈 薇 舒 勤* 黃燕琴

1(四川大學電氣信息學院 四川 成都 610065)2(漳州職業技術學院 福建 漳州 363000)

0 引 言

隨著三維掃描技術的快速發展，通過激光掃描技術獲得的點云模型成為近幾年幾何模型的通用表達形式[1]。目前，三維模型特征提取已成為計算機視覺、數字幾何處理技術中的研究熱點[2]。

Kim[3]利用移動最小二乘法擬合局部三次曲面計算曲率和主方向，通過計算曲率沿主方向的極值點來提取點云脊谷特征點，可以較好地檢測模型細節特征。Wang等[4]通過移動最小二乘法計算曲率，再將曲率絕對值較大點標定為點云脊谷特征點。龐旭芳等[5]使用類似的方法提取出曲率較大的點后通過特征點投影得到增強特征點，最后對特征點進行平滑后生成特征線。Gumhold等[6]使用平均曲率計算鄰向圖邊的懲罰權重大小，通過最小化鄰向圖邊的權重來提取特征點。上述方法都是通過擬合局部平面來計算曲率，再在此基礎上提取脊谷特征點，但是算法的時間代價高。Pauly等[7]將多尺度分類算子作為算法核心，使用局部鄰域的大小作為離散尺度參數，計算在不同尺度下一點為特征點的可能性。Demarsin等[8]利用PCA計算離散點云法向量，根據法向變化對點云數據進行分類，將相對較小的點簇作為特征區域，最后通過構造最小生成樹得到特征線。Daniels等[9]利用魯棒最小二乘的概念，在點的鄰域內進行曲面擬合，將點投影到多個曲面交點得到增強特征點，最后連接并平滑特征線。張雨禾等[10]提出一種基于密度空間聚類的散亂點云特征提取方法，將反K近鄰的尺度作為點密度，引入特征的全局約束性信息，建立新的特征識別準則。然而法線和曲率只是點的近鄰的幾何特征估計，不能捕獲點云模型的細節特征，且上述方法都是針對某一類特征進行特征點提取，在處理模型時，難以提取完整的多種類型的特征點。

快速點特征直方圖(FPFH)通過參數化查詢點與鄰域點之間的空間差異，形成一個多維直方圖對點的幾何屬性進行描述，由Rusu等[11]于2008年提出。該方法有較好的抗噪性能，廣泛用于機器人目標定位、點云分割和點云配準的研究中。然而針對點云特征點提取技術，還未出現引用FPFH方法的文獻。

針對以上問題，本文提出一種基于FPFH的提取點云特征點的新方法。將FPFH引入點云特征點提取技術中，并提出FPFH各子區間均值這一參數概念。通過判斷各點FPFH各區間值與均值的距離大小提取初始特征點；根據掃描的點云模型數據排列特點，提出判斷特征點鄰近點夾角的方法對初始特征點進行優化；采用基于投影點夾角的方法對點云輪廓特征進行增強。實驗結果表明，該方法簡單高效，無須計算點云曲率特征，為點云特征提取提供了新思路；提取出的特征點不僅可以反映模型脊谷細節特征，還可以完整地表征模型的輪廓信息。

1 法向量估算

法向量作為點云必不可少的屬性之一，其估計方法在點云數據處理中具有重要的位置。目前，基于PCA的法向量估計被廣泛使用，該方法由Hoppe等[13]在基于有向距離函數的表面重建法中提出。

由于散亂點云不具備拓撲信息，首先提取點云K近鄰點構建局部鄰域。設點r的K近鄰為{r1,r2,…，rk}，則協方差矩陣可以表示為：

(1)

對協方差矩陣C進行特征值分解,對應C最小特征值的特征向量即為點r的法向量。

需要注意的是，算出的法向只得到了法向量所在直線，而沒有確定以直線的哪個方向為法向量的最終方向[11]，本文用文獻[13]的方法對法向進行調整，調整后的法向均指向模型外側。

2 特征點初提取

2.1 快速點特征直方圖原理

點云模型中，任意點pq的點特征直方圖(PFH)計算規則如下：以點pq為圓心，構造半徑為r的球形區域，尋找點pq的K近鄰(見圖1)。

圖1 PFH計算的影響范圍

假設球體內兩點ps、pt的法向為ns、nt，以ps法向ns為u軸，根據右手定則建立局部坐標系uvw如圖2所示。

圖2 建立局部坐標系

將uvw局部坐標系平移到點pt，設pt的法向nt與坐標軸v的夾角為α，nt在平面uw的投影與u的夾角為θ，ns與點pt、ps連線的夾角為φ。

α=v·nt

(2)

(3)

(4)

PFH計算過程中點的影響區域如圖1所示，依次計算球體內兩點之間的α、φ、θ值，將三個特征值的取值范圍分別劃為等分的b個子區間，共形成3b個區間。再分別統計每個落入子區間的數量，最終根據各子區間數量所占總數的百分比來構建查詢點pq的點特征直方圖。

由于PFH的計算復雜度高，文獻[11]提出快速點特征直方圖(FPFH)算法，對PFH進行簡化，在保留PFH特性的同時，提高了運算效率。FPFH特征計算的影響區域如圖3所示，只計算pq與K近鄰的PFH值，稱為SPSH，然后分別計算pq鄰域點的SPFH值，最后進行加權計算，得到最終的FPFH值：

(5)

式中：ωi是點pq到鄰域點pi的歐式距離。

圖3 FPFH計算的影響范圍

2.2 基于FPFH的特征點初提取

FPFH值中涵蓋了點云的局部特征信息，三個特征值間接反映了點云的平均曲率和幾何特征，本文將曲率閾值提取特征點的方法推廣到FPFH，對點云模型特征點進行初提取。

由于FPFH是基于法向之間的關系建立起來的，考慮了法向方向之間所有的相互作用，因此特征點與非特征點的FPFH值存在明顯差異，可利用此特性提取點云初始特征點。

由于在三維模型中，大部分所在表面較為平緩，因此，可用FPFH在各子區間的均值代替非特征點的FPFH各區間的值，引入點云模型FPFH各區間的均值，記為MFPFH：

(6)

在此基礎上計算每一點的FPFH各區間的值與MFPFH的歐式距離：

(7)

式中：f代表直方圖子區間個數；pi表示點云的FPFH第i個區間的值；ui表示點云第i個區間的MFPFH值。若d超出閾值，則標記為特征點。

3 特征點優化與增強

通過閾值提取出的點云數據中，不僅包含特征點，還包含了部分非特征點。本節首先采用判斷特征點臨近點夾角的方法對脊谷特征點進行優化，再通過判斷點云鄰近投影點相鄰向量夾角大小的方法來增強模型整體輪廓特征。

3.1 脊谷特征點優化

脊點和谷點作為曲面上局部區域內曲率沿主方向變化的極值點，充分表征了對應曲面的重要幾何形狀特征。點云模型數據由大型掃描儀掃描獲得，圖4(a)為典型的點云模型，其內部排列規則如圖4(b)所示。可以看出，點云脊谷特征點的最臨近點均勻分布于其兩側，距特征點的距離幾乎相等，基于此特點和脊谷點的凹凸性，本文提出判斷特征點臨近點夾角大小的方法對脊谷特征點進行優化。

(a) 點云模型 (b) 局部放大圖圖4 典型點云模型

如圖5所示，若點云為脊谷特征點，則特征點與兩近鄰點向量之間的夾角較小，特征越尖銳，夾角越小；若點云為非特征點，則特征點與近鄰點向量之間的夾角較大。根據此原理，可對提取出的特征值進行優化，剔除曲率較小的特征點。

圖5 特征點與非特征點夾角圖

3.2 邊界特征點增強

Q為內部點 Q為邊界點圖6 邊界點判別

4 實 驗

FPFH是基于點云法向之間的關系建立起來的，法向估算的精確程度取決于搜索半徑的大小，因此法向搜索半徑rn對FPFP具有一定影響。圖7、圖8是在改變法向搜索鄰域范圍大小的情況下，特征點和非特征點FPFH值變化，其中t為鄰域搜索范圍內的點數，t越大，代表鄰域搜索半徑越大。在鄰域半徑較小時，特征點與非特征點差別較小，這是因為鄰域搜索半徑過小，法向估計結果不準確；隨著法向搜索半徑的增大，非特征點的FPFH值無明顯變化，而特征點FPFH值出現較大的跳躍，在t=30后趨于穩定。整體來說，在合適鄰域范圍內，特征點與非特征點的FPFH值存在較大差異。因此，本文將t設為35，可以得到較理想的結果。

圖7 不同法線搜索鄰域下特征點的FPFH值

圖8 不同法線搜索鄰域下非特征點的FPFH值

為驗證本文方法的有效性，在MATLAB上進行實驗驗證。設參數t為鄰域搜索點的個數。圖9為Armadill模型，取t=35，共提取出特征點6 727個。Armadill模型中有較多的細節特征，如眼睛、嘴巴等，可以看出，該方法在細節特征提取上表現較好，能完整地提取出模型的輪廓特征。圖10為bunny模型，該模型為經典點云模型，取t=35，共提取出特征點6 055個，結果表明，該方法較好地提取出bunny的特征點，如前腿、耳朵、身上紋理特征等都被提取出。

圖9 Armadill模型實驗結果

圖10 bunny模型實驗結

為驗證本文方法的優越性，將本文算法與文獻[4]算法進行對比分析。文獻[4]為提取點云特征點典型的曲率閾值檢測法，且在文獻[5]中也有采用此方法，首先通過移動最小二乘計算曲率，再設置閾值，將曲率絕對值較大的點標定為特征點。圖11為斯坦福快樂佛模型實驗結果，曲率閾值檢測法提取出脊谷特征點14 130個，本文方法提取出脊谷特征點13 226個。從圖11(d)可以看出，曲率閾值檢測法雖然能較完整地提取出脊谷點，但是曲率在計算中存在誤差，因此提出的特征點所含噪點較多。圖12為龍模型，文獻[4]方法提取出脊谷特征點8 270個，本文提取出脊谷特征點9 387個，從龍頭和脊背部分數據可看出，本文方法能更好地提取出模型的尖銳與細節特征，而且模型的輪廓信息更完整。從整體效果來看，本文方法能夠更加精確地提取出點云細節特征點，而且能傳達模型的輪廓信息，特征點更完整。

(a) 模型特征點 (b) 輪廓點加強

(c) 本文整體效果 (d) 曲率閾值檢測法圖11 快樂佛模型實驗結果

(a) 模型特征點 (b) 輪廓點加強

(c) 本文整體效果 (d) 曲率閾值檢測法圖12 龍模型實驗結果

表1為本文方法與文獻[4]的曲率閾值檢測法在其他模型上提取的特征點對比。

表1 本文方法與文獻[4]方法提取特征點數對比

可以看出，本文方法在前兩個模型上提取出的特征點數明顯多于文獻[4]的曲率閾值檢測法，數據差主要來自模型輪廓特征點，文獻[4]方法雖然可以較好地提取出脊谷特征點，但是冗余數據較多，在對模型細節特征的提取上效果較差。

5 結 語

點云特征提取是點云處理的關鍵底層技術，針對現在大部分文獻都采用曲率和法向作為切入點的現狀，本文提出了基于FPFH的點云特征點提取方法。采用PCA估算法向向量，計算點云的FPFH值；引入模型FPFH值在各子區間的均值，根據點云FPFH各區間值與均值的歐式距離提取出初始特征點；根據凹凸點與兩臨近點夾角大小對脊谷特征點進行優化，再對模型輪廓特征進行加強。

實驗結果表明，本文方法簡單、有效，可以有效提取點云特征點，與其他方法相比，能更好地體現模型的細節特征與輪廓特征。然而，在提取初始點云特征點時，不同模型需要設置不同的閾值，如何改進對閾值的設置是下一步研究的目標。