基于FPFH的點(diǎn)云特征點(diǎn)提取算法

賈 薇 舒 勤* 黃燕琴

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

0 引 言

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

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

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

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

1 法向量估算

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

由于散亂點(diǎn)云不具備拓?fù)湫畔ⅲ紫忍崛↑c(diǎn)云K近鄰點(diǎn)構(gòu)建局部鄰域。設(shè)點(diǎn)r的K近鄰為{r1,r2,…，rk}，則協(xié)方差矩陣可以表示為：

(1)

對(duì)協(xié)方差矩陣C進(jìn)行特征值分解,對(duì)應(yīng)C最小特征值的特征向量即為點(diǎn)r的法向量。

需要注意的是，算出的法向只得到了法向量所在直線，而沒有確定以直線的哪個(gè)方向?yàn)榉ㄏ蛄康淖罱K方向[11]，本文用文獻(xiàn)[13]的方法對(duì)法向進(jìn)行調(diào)整，調(diào)整后的法向均指向模型外側(cè)。

2 特征點(diǎn)初提取

2.1 快速點(diǎn)特征直方圖原理

點(diǎn)云模型中，任意點(diǎn)pq的點(diǎn)特征直方圖(PFH)計(jì)算規(guī)則如下：以點(diǎn)pq為圓心，構(gòu)造半徑為r的球形區(qū)域，尋找點(diǎn)pq的K近鄰(見圖1)。

圖1 PFH計(jì)算的影響范圍

假設(shè)球體內(nèi)兩點(diǎn)ps、pt的法向?yàn)閚s、nt，以ps法向ns為u軸，根據(jù)右手定則建立局部坐標(biāo)系uvw如圖2所示。

圖2 建立局部坐標(biāo)系

將uvw局部坐標(biāo)系平移到點(diǎn)pt，設(shè)pt的法向nt與坐標(biāo)軸v的夾角為α，nt在平面uw的投影與u的夾角為θ，ns與點(diǎn)pt、ps連線的夾角為φ。

α=v·nt

(2)

(3)

(4)

PFH計(jì)算過程中點(diǎn)的影響區(qū)域如圖1所示，依次計(jì)算球體內(nèi)兩點(diǎn)之間的α、φ、θ值，將三個(gè)特征值的取值范圍分別劃為等分的b個(gè)子區(qū)間，共形成3b個(gè)區(qū)間。再分別統(tǒng)計(jì)每個(gè)落入子區(qū)間的數(shù)量，最終根據(jù)各子區(qū)間數(shù)量所占總數(shù)的百分比來構(gòu)建查詢點(diǎn)pq的點(diǎn)特征直方圖。

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

(5)

式中：ωi是點(diǎn)pq到鄰域點(diǎn)pi的歐式距離。

圖3 FPFH計(jì)算的影響范圍

2.2 基于FPFH的特征點(diǎn)初提取

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

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

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

(6)

在此基礎(chǔ)上計(jì)算每一點(diǎn)的FPFH各區(qū)間的值與MFPFH的歐式距離：

(7)

式中：f代表直方圖子區(qū)間個(gè)數(shù)；pi表示點(diǎn)云的FPFH第i個(gè)區(qū)間的值；ui表示點(diǎn)云第i個(gè)區(qū)間的MFPFH值。若d超出閾值，則標(biāo)記為特征點(diǎn)。

3 特征點(diǎn)優(yōu)化與增強(qiáng)

通過閾值提取出的點(diǎn)云數(shù)據(jù)中，不僅包含特征點(diǎn)，還包含了部分非特征點(diǎn)。本節(jié)首先采用判斷特征點(diǎn)臨近點(diǎn)夾角的方法對(duì)脊谷特征點(diǎn)進(jìn)行優(yōu)化，再通過判斷點(diǎn)云鄰近投影點(diǎn)相鄰向量夾角大小的方法來增強(qiáng)模型整體輪廓特征。

3.1 脊谷特征點(diǎn)優(yōu)化

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

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

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

圖5 特征點(diǎn)與非特征點(diǎn)夾角圖

3.2 邊界特征點(diǎn)增強(qiáng)

Q為內(nèi)部點(diǎn) Q為邊界點(diǎn)圖6 邊界點(diǎn)判別

4 實(shí) 驗(yàn)

FPFH是基于點(diǎn)云法向之間的關(guān)系建立起來的，法向估算的精確程度取決于搜索半徑的大小，因此法向搜索半徑rn對(duì)FPFP具有一定影響。圖7、圖8是在改變法向搜索鄰域范圍大小的情況下，特征點(diǎn)和非特征點(diǎn)FPFH值變化，其中t為鄰域搜索范圍內(nèi)的點(diǎn)數(shù)，t越大，代表鄰域搜索半徑越大。在鄰域半徑較小時(shí)，特征點(diǎn)與非特征點(diǎn)差別較小，這是因?yàn)猷徲蛩阉靼霃竭^小，法向估計(jì)結(jié)果不準(zhǔn)確；隨著法向搜索半徑的增大，非特征點(diǎn)的FPFH值無明顯變化，而特征點(diǎn)FPFH值出現(xiàn)較大的跳躍，在t=30后趨于穩(wěn)定。整體來說，在合適鄰域范圍內(nèi)，特征點(diǎn)與非特征點(diǎn)的FPFH值存在較大差異。因此，本文將t設(shè)為35，可以得到較理想的結(jié)果。

圖7 不同法線搜索鄰域下特征點(diǎn)的FPFH值

圖8 不同法線搜索鄰域下非特征點(diǎn)的FPFH值

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

圖9 Armadill模型實(shí)驗(yàn)結(jié)果

圖10 bunny模型實(shí)驗(yàn)結(jié)

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

(a) 模型特征點(diǎn) (b) 輪廓點(diǎn)加強(qiáng)

(c) 本文整體效果 (d) 曲率閾值檢測(cè)法圖11 快樂佛模型實(shí)驗(yàn)結(jié)果

(a) 模型特征點(diǎn) (b) 輪廓點(diǎn)加強(qiáng)

(c) 本文整體效果 (d) 曲率閾值檢測(cè)法圖12 龍模型實(shí)驗(yàn)結(jié)果

表1為本文方法與文獻(xiàn)[4]的曲率閾值檢測(cè)法在其他模型上提取的特征點(diǎn)對(duì)比。

表1 本文方法與文獻(xiàn)[4]方法提取特征點(diǎn)數(shù)對(duì)比

可以看出，本文方法在前兩個(gè)模型上提取出的特征點(diǎn)數(shù)明顯多于文獻(xiàn)[4]的曲率閾值檢測(cè)法，數(shù)據(jù)差主要來自模型輪廓特征點(diǎn)，文獻(xiàn)[4]方法雖然可以較好地提取出脊谷特征點(diǎn)，但是冗余數(shù)據(jù)較多，在對(duì)模型細(xì)節(jié)特征的提取上效果較差。

5 結(jié) 語(yǔ)

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

實(shí)驗(yàn)結(jié)果表明，本文方法簡(jiǎn)單、有效，可以有效提取點(diǎn)云特征點(diǎn)，與其他方法相比，能更好地體現(xiàn)模型的細(xì)節(jié)特征與輪廓特征。然而，在提取初始點(diǎn)云特征點(diǎn)時(shí)，不同模型需要設(shè)置不同的閾值，如何改進(jìn)對(duì)閾值的設(shè)置是下一步研究的目標(biāo)。