霍 旺，熊風(fēng)光，韓 燮，況立群

(中北大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山西 太原 030051)

0 引 言

點(diǎn)云關(guān)鍵點(diǎn)的特征描述作為點(diǎn)云配準(zhǔn)與識(shí)別等處理中的關(guān)鍵步驟，有著重要的意義與廣闊的應(yīng)用前景。與網(wǎng)格模型相比，散亂的點(diǎn)云數(shù)據(jù)之間缺少相應(yīng)的拓?fù)潢P(guān)系，對(duì)關(guān)鍵點(diǎn)的描述更加困難?，F(xiàn)有的一些描述算法在運(yùn)行效率、配準(zhǔn)的準(zhǔn)確率及抗噪、抗干擾的能力上仍有不足，需要進(jìn)一步的改進(jìn)提高。

1 相關(guān)工作

針對(duì)最近點(diǎn)迭代(iterative closet point，ICP)算法存在的收斂速度慢、計(jì)算復(fù)雜度高的問題，許多學(xué)者提出了先將點(diǎn)云的關(guān)鍵點(diǎn)配準(zhǔn)，使兩片點(diǎn)云具有良好的初始位置，再利用ICP或其改進(jìn)算法[1,2]對(duì)點(diǎn)云進(jìn)行精配準(zhǔn)的方法。同時(shí)提出了許多優(yōu)秀的關(guān)鍵點(diǎn)描述子算法。但在運(yùn)行效率、算法的魯棒性上，仍未取得令人滿意的效果，需要人們繼續(xù)改進(jìn)和創(chuàng)新。一個(gè)有效的關(guān)鍵點(diǎn)描述子必須滿足以下條件[3]：①描述子應(yīng)具有較強(qiáng)的鑒別力；②描述子應(yīng)具有豐富的描述性和穩(wěn)健的變換不變性；③描述子應(yīng)易于計(jì)算和匹配；④描述子應(yīng)對(duì)噪聲和背景干擾具有較強(qiáng)的穩(wěn)健性。

目前的描述子根據(jù)其描述方式大致可以分為二類：

(1)基于點(diǎn)云空間數(shù)據(jù)點(diǎn)位置分布的方法。Johnson于1999年提出Spin Image(SI)特征是該類的經(jīng)典代表。該方法以關(guān)鍵點(diǎn)為圓心，其法向量為z軸構(gòu)建圓柱參考系，將鄰域點(diǎn)的分布密度作為描述的特征。Spin Image對(duì)遮擋和干擾具有很強(qiáng)的穩(wěn)定性，但對(duì)點(diǎn)云數(shù)據(jù)有一定要求，需要點(diǎn)云均勻分布并且需要較大的存儲(chǔ)空間。隨后Frome提出的3D Shape Context(3DSC)改變了Spin Image投影到二維平面的方式，將鄰域劃分為三維的球形柵格，統(tǒng)計(jì)點(diǎn)云在球形柵格中的特征，其抗噪和抗干擾的性能相比SI均有提高，但進(jìn)行描述子匹配時(shí)需要將場(chǎng)景進(jìn)行旋轉(zhuǎn)，計(jì)算量較大。Rotational Projection Statistics(RoPS)[4-6]是Yulan Guo提出的一種關(guān)鍵點(diǎn)描述子。該方法針對(duì)網(wǎng)格表面，在關(guān)鍵點(diǎn)周圍建立局部坐標(biāo)系，將鄰域點(diǎn)投影到XOY、YOZ和XOZ這3個(gè)2D平面上，并在三平面上建立橫平豎直的單元格，根據(jù)落到每個(gè)單元格的點(diǎn)的數(shù)量，來計(jì)算每個(gè)2D平面上的一系列統(tǒng)計(jì)數(shù)據(jù)(低階中心矩和熵值)從而進(jìn)行描述，并且旋轉(zhuǎn)模型增加不同視點(diǎn)時(shí)的魯棒性。RoPS描述子對(duì)關(guān)鍵點(diǎn)的描述能力和穩(wěn)定性都具有了明顯的提高，但該方法是基于網(wǎng)格模型進(jìn)行地描述，而非針對(duì)大多數(shù)設(shè)備獲取到的三維點(diǎn)云模型，因此需先對(duì)三維點(diǎn)云模型進(jìn)行三角網(wǎng)格化，而且還要執(zhí)行多次旋轉(zhuǎn)操作，描述過程較為復(fù)雜和耗時(shí)。

(2)基于關(guān)鍵點(diǎn)及其鄰域點(diǎn)之間幾何關(guān)系的方法。這類方法比較有代表性的是Rusu R.B提出的Point Feature Histogram(PFH)特征和改進(jìn)算法Fast Point Feature Histogram(FPFH)等相關(guān)算法[7,8]。該方法是將關(guān)鍵點(diǎn)鄰域內(nèi)每一對(duì)點(diǎn)建立達(dá)布坐標(biāo)系(Darboux frame)，計(jì)算法向量與坐標(biāo)系的夾角，形成能描述關(guān)鍵點(diǎn)鄰域關(guān)系的直方圖。FPFH算法的優(yōu)點(diǎn)是算法簡(jiǎn)單、計(jì)算速度快，缺點(diǎn)是抗噪性差。Signature of Histogram of Orientations(SHOT)[9]特征描述了鄰域內(nèi)不同空間位置點(diǎn)的法向量與局部坐標(biāo)系的夾角關(guān)系。其具有很好的抗噪性，但描述子的維數(shù)達(dá)到了352維之巨，因此計(jì)算時(shí)間較長(zhǎng)。

本文提出一種建立在局部坐標(biāo)系的基礎(chǔ)上，首先對(duì)關(guān)鍵點(diǎn)的鄰域點(diǎn)進(jìn)行區(qū)間劃分，然后對(duì)各個(gè)區(qū)間內(nèi)鄰域點(diǎn)與投影到特定平面上的投影點(diǎn)所形成的各個(gè)梯形進(jìn)行360°旋轉(zhuǎn)，最后通過計(jì)算經(jīng)旋轉(zhuǎn)后得到的空間模型的體積的數(shù)值對(duì)該區(qū)間進(jìn)行描述，形成一個(gè)對(duì)關(guān)鍵點(diǎn)的多區(qū)間體積值進(jìn)行表述的描述子。本文提出的描述子描述的也是關(guān)鍵點(diǎn)及其鄰域點(diǎn)之間幾何關(guān)系。描述子利用了局部坐標(biāo)系，因此具有良好的旋轉(zhuǎn)平移不變性；同時(shí)，關(guān)鍵點(diǎn)及其鄰域點(diǎn)投影形成的幾何模型的體積計(jì)算方法簡(jiǎn)單易行、效率高，并且最終所形成的描述子的低維度性有利用后期描述子的匹配。

2 描述子建立過程

(1)獲取關(guān)鍵點(diǎn)p的鄰域點(diǎn)。以關(guān)鍵點(diǎn)p為球心，R為半徑建立一個(gè)p的鄰域球，記為S，包含在該球內(nèi)的所有點(diǎn)即為p的鄰域點(diǎn)，記為Nbhd(p)。本文采用KD-Tree進(jìn)行空間鄰域點(diǎn)搜索，加速關(guān)鍵點(diǎn)的鄰域點(diǎn)的查找速度。

(1)

(2)

圖1 空間的幾何區(qū)間

圖2 任一空間區(qū)域側(cè)視圖

在計(jì)算Regionk中兩相鄰鄰域點(diǎn)及其投影點(diǎn)所形成的梯形旋轉(zhuǎn)后的模型的體積Vk,i時(shí)，可將該模型拆分為一個(gè)空心圓柱體Modelk,i,1和一個(gè)中間為空心圓柱的圓臺(tái)Modelk,i,2。Modelk,i,1的體積Vk,i,1可用式(4)進(jìn)行計(jì)算，其中，hk,i,1代表的Modelk,i,1的高，rk,i-1和rk,i分別代表Modelk,i,1的內(nèi)、外半徑，均可通過式(6)進(jìn)行計(jì)算。Modelk,i,2的體積Vk,i,2可由圓臺(tái)的體積Vk,i,3與圓柱的體積Vk,i,4相減而得，見式(7)。式(8)用于計(jì)算體積Vk,i,3,其中hk,i,2代表圓臺(tái)的高，rk,i-1和rk,i分別代表圓臺(tái)的內(nèi)、外半徑，也通過式(6)進(jìn)行計(jì)算。式(9)用于計(jì)算體積Vk,i,4，其中hk,i,2代表空心圓柱的高，通過式(10)進(jìn)行計(jì)算，rk,i-1代表圓柱的半徑。另外，rk,0=0，hk,0,1=R

(3)

(4)

(5)

(6)

Vk,i,2=Vk,i,3-Vk,i,4

(7)

(8)

(9)

hk,i,2=hk,i-1,1-hk,i,1

(10)

(6)依據(jù)步驟(5)，計(jì)算關(guān)鍵點(diǎn)p的其它m-1個(gè)維度的數(shù)值，最終組成一個(gè)m維的描述子。

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)采用與PFH、FPFH、SHOT描述子在運(yùn)行時(shí)間、旋轉(zhuǎn)平移魯棒性、抗噪性和降采樣方面進(jìn)行對(duì)比分析。三維模型使用斯坦福大學(xué)的標(biāo)準(zhǔn)三維模型庫中的Bunny、Armadillo和Happy Buddha，以增加不同模型情況下的對(duì)比性。本文所提出的描述子代碼采用VS2013平臺(tái)+PCL庫實(shí)現(xiàn)，且PFH、FPFH、SHOT在PCL中有開源代碼，可以很方便地進(jìn)行對(duì)比分析；另外，本實(shí)驗(yàn)中設(shè)定m為24，點(diǎn)云的法向量是基于最近的10個(gè)鄰近點(diǎn)獲取的，鄰域半徑R為18倍的點(diǎn)云分辨率。

3.1 運(yùn)行時(shí)間分析

表1是實(shí)驗(yàn)用的模型信息，記錄了各模型中點(diǎn)的個(gè)數(shù)和獲取到的關(guān)鍵點(diǎn)的個(gè)數(shù)，本文利用PCL中提供的HarrisKeypoint3D類將提取到Harris 3D角點(diǎn)作為關(guān)鍵點(diǎn)。表2記錄了4種描述子的維數(shù)和在不同模型下生成關(guān)鍵點(diǎn)的描述子所需運(yùn)行時(shí)間的對(duì)比。從表2可以看出本文提出的描述子無論是維數(shù)、計(jì)算時(shí)間都較小，意味著所需的存儲(chǔ)空間較小、計(jì)算效率更高、實(shí)時(shí)性將更好，其原因是本文所提出的描述子只需要計(jì)算關(guān)鍵點(diǎn)處的局部坐標(biāo)系和各鄰域內(nèi)的體積和，不需要計(jì)算其它額外的參數(shù)(如：法向量、網(wǎng)格等)，所以運(yùn)行時(shí)間大大縮短。最終的運(yùn)行時(shí)間只與關(guān)鍵點(diǎn)的多少有關(guān)，而和模型的點(diǎn)數(shù)等其它參數(shù)無關(guān)。

表1 實(shí)驗(yàn)?zāi)Ｐ托畔?/p>

表2 各個(gè)方法不同模型的運(yùn)行時(shí)間

注意本文實(shí)驗(yàn)出現(xiàn)了PFH比FPFH快的情況。其原因是實(shí)驗(yàn)采用的是對(duì)關(guān)鍵點(diǎn)而不是整個(gè)點(diǎn)云進(jìn)行的描述。根據(jù)FPFH的原理相當(dāng)于擴(kuò)大了鄰域搜索半徑，但由于計(jì)算的關(guān)鍵點(diǎn)數(shù)目較少，F(xiàn)PFH提高的效率不能彌補(bǔ)擴(kuò)大半徑的帶來的劣勢(shì)。故而會(huì)出現(xiàn)下表中PFH比FPFH快的情況，但這并不影響對(duì)結(jié)果的分析。

3.2 旋轉(zhuǎn)平移的魯棒性分析

在三維點(diǎn)云獲取過程中經(jīng)常由于物體形狀、設(shè)備等限制，不能獲取連續(xù)的、視點(diǎn)不變的點(diǎn)云，經(jīng)常帶有一定的旋轉(zhuǎn)角度。因此，描述子旋轉(zhuǎn)平移的魯棒性是評(píng)價(jià)一個(gè)描述子的重要標(biāo)準(zhǔn)。

匹配準(zhǔn)確率=正確匹配的描述子對(duì)的數(shù)目/匹配的描述子對(duì)的數(shù)目

(11)

圖3為3個(gè)模型在不同描述子下的旋轉(zhuǎn)平移不變的魯棒性分析結(jié)果。從圖3中可以看出本文提出的描述子與其它描述子相比，對(duì)旋轉(zhuǎn)平移具有更好的穩(wěn)定性。在旋轉(zhuǎn)較大角度時(shí)仍有較高的準(zhǔn)確率，同時(shí)針對(duì)不同模型表面都能有較好的表現(xiàn)。分析原因主要有：一是本文采用基于關(guān)鍵點(diǎn)建立局部坐標(biāo)系的方式進(jìn)行描述，本身局部坐標(biāo)系具有良好的旋轉(zhuǎn)平移魯棒性；二是采用模型幾何體積分布的方式對(duì)局部點(diǎn)云進(jìn)行描述，只要是模型的幾何結(jié)構(gòu)不發(fā)生變化，經(jīng)旋轉(zhuǎn)平移后仍能保持局部點(diǎn)云的體積分布不變。

3.3 抗噪性分析

在三維點(diǎn)云數(shù)據(jù)的獲取過程中，由于人為、環(huán)境的干擾或者掃描設(shè)備本身的設(shè)計(jì)缺陷、精度限制等問題，使得獲取到的點(diǎn)云數(shù)據(jù)多帶有一定的噪聲。因此，需要對(duì)點(diǎn)云加入高斯噪聲，并進(jìn)行旋轉(zhuǎn)平移魯棒性檢驗(yàn)來考察描述子的抗噪性能。

圖3 旋轉(zhuǎn)平移的魯棒性分析

圖4 抗噪性分析

從圖4可以看出相較于其它描述子而言，本文所提出的描述子具有很好抗噪性，究其緣由，還是因?yàn)楸疚乃岢龅拿枋鲎觾H僅是描述關(guān)鍵點(diǎn)的空間幾何體積，只要是噪聲沒有對(duì)模型的幾何結(jié)構(gòu)產(chǎn)生重大的影響，描述子的穩(wěn)定性就不會(huì)發(fā)生太多變化。

3.4 不同采樣率分析

生產(chǎn)、生活中，經(jīng)常會(huì)有采樣設(shè)備的硬件、配置不同等情況，獲取的點(diǎn)云的采樣率也不盡相同。因此，基于不同采樣率，實(shí)驗(yàn)測(cè)試描述子的性能顯得尤為重要。

本次實(shí)驗(yàn)的過程為：給定一個(gè)模型M、一個(gè)真實(shí)的旋轉(zhuǎn)平移矩陣Rt，M進(jìn)行采樣率為δ的降采樣后的模型記為Mδ，Mδ在Rt的映射下的模型為Mδ′；然后按照3.2中的實(shí)驗(yàn)依據(jù)模型M、Mδ′和旋轉(zhuǎn)平移矩陣Rt進(jìn)行旋轉(zhuǎn)平移魯棒性分析。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 多采樣率分析

從圖5可以清晰看出本文所提出的描述子，在采樣率為3/4左右時(shí)，具有良好的效果，在采樣率為1/2左右時(shí)，性能接近于其它描述子，而當(dāng)采樣率為1/4左右時(shí)，性能差于其它描述子，其原因是本文的描述子在分辨率下降較多的情況下，內(nèi)部幾何結(jié)構(gòu)發(fā)生較大改變，體積計(jì)算產(chǎn)生較大的誤差，影響了描述子的性能。

4 本文描述子的應(yīng)用

將本文所提出描述子應(yīng)用于點(diǎn)云配準(zhǔn)中，實(shí)現(xiàn)多視角下點(diǎn)云的對(duì)齊操作。實(shí)驗(yàn)數(shù)據(jù)為斯坦福大學(xué)提供的不同視角下的兔子的點(diǎn)云模型，包括從0°、45°、90°、180°、270°和315°的6個(gè)不同視角下掃描的點(diǎn)云。其中兩片點(diǎn)云的配準(zhǔn)過程為：

(1)載入視角相鄰的兩片點(diǎn)云(如：0°、45°)記為source、target，并分別提取Harris 3D角點(diǎn)作為關(guān)鍵點(diǎn)集合keys_src和keys_tgt，利用本文提出的方法對(duì)關(guān)鍵點(diǎn)進(jìn)行描述，獲得兩組描述子集合feature_src和feature_tgt，其中關(guān)鍵點(diǎn)集合中的關(guān)鍵點(diǎn)與描述子集合中的描述子是一一對(duì)應(yīng)的；

(2)隨機(jī)選取feature_src中的3個(gè)描述子fs0、fs1和fs2，置入集合fs中，利用KD-Tree在feature_tgt中為fs0搜索5個(gè)最近的描述子，并隨機(jī)選取一個(gè)描述子ft0作為fs0對(duì)應(yīng)描述子，依次計(jì)算出fs1的對(duì)應(yīng)描述子ft1，fs2對(duì)應(yīng)描述子ft2，將ft0、ft1和ft2置入集合ft中；

(3)找到fs0、fs1和fs2對(duì)應(yīng)的關(guān)鍵點(diǎn)ks0、ks1和ks2，依次連接該3點(diǎn)形成3條邊并計(jì)算它們的歐式距離，分為記為d_ks01、d_ks12和d_ks20，同理計(jì)算ft0、ft1和ft2對(duì)應(yīng)關(guān)鍵點(diǎn)所形成3條邊的歐式距離，分別記為d_kt01、d_kt12和d_kt20，依次計(jì)算對(duì)應(yīng)邊距離的相似比，即min(d_ks01/d_kt01，d_kt01/d_ks01)、min(d_ks12/d_kt12，d_kt12/d_ks12)和min(d_ks20/d_kt20，d_kt20/d_ks20)，如果相似比均大于一定閾值(本文為0.8)時(shí)則繼續(xù)步驟(4)，否則退回到步驟(2)；

(4)利用步驟(3)找到的3對(duì)關(guān)鍵點(diǎn)、和，計(jì)算出旋轉(zhuǎn)矩陣平移Rt；

(6)循環(huán)n次(本文為50000)執(zhí)行步驟(2)～步驟(5)，選取最小fitness時(shí)的旋轉(zhuǎn)平移矩陣作為最終的旋轉(zhuǎn)平移矩陣。根據(jù)這個(gè)旋轉(zhuǎn)平移矩陣可以將source變換到target同一坐標(biāo)系下，完成根據(jù)關(guān)鍵點(diǎn)對(duì)點(diǎn)云的配準(zhǔn)工作。

對(duì)每?jī)蓚€(gè)相鄰的點(diǎn)云片依次執(zhí)行上面的操作，最終可以將6片點(diǎn)云都變換到同一坐標(biāo)系下，得到完整的模型。本文的配準(zhǔn)結(jié)果如圖6所示。

圖6 基于本文所提出的描述子的配準(zhǔn)

從圖6可以看出，配準(zhǔn)結(jié)果還是相對(duì)較好的?；旧衔呛狭送米颖旧淼奈恢茫m然耳朵等處有些誤差，但仍在可接受的范圍內(nèi)。達(dá)到了粗配準(zhǔn)的要求，可以為后續(xù)精確配準(zhǔn)提供良好的初始條件。

5 結(jié)束語

本文提出了一個(gè)基于關(guān)鍵點(diǎn)鄰域旋轉(zhuǎn)體積特征的描述方法。實(shí)驗(yàn)結(jié)果表明，針對(duì)不同點(diǎn)云模型都具有非常好的旋轉(zhuǎn)平移魯棒性，同時(shí)具有描述過程中所需存儲(chǔ)空間較小，運(yùn)行速度快的優(yōu)勢(shì)。在模型具有噪聲、采樣率差別較小的情況下仍有良好的表現(xiàn)。比PFH、FPFH和SHOT等描述子運(yùn)行的更快，更穩(wěn)定，且應(yīng)用在多片點(diǎn)云的粗配準(zhǔn)上也達(dá)到了較好的效果，為下一步的精配準(zhǔn)做了良好的鋪墊。但是在模型采樣率差別較大的情況下，效果并不理想，接下來的研究可以針對(duì)此問題進(jìn)行改進(jìn)。

[1]Chen J,Belaton B.An improved iterative closest point algorithm for rigid point registration[J].Communications in Computer & Information Science,2014,481:255-263.

[2]Tagliasacchi A,Schr?der M,Tkach A,et al.Robust articulated-ICP for real-time hand tracking[J].Computer Graphics Forum,2015,34(5):101-114.

[3]GUO Yulan,LU Min,TAN Zhiguo,et al.Survey of local feature extraction on range images[J].Pattern Recognition and Artificial Intelligence,2012,25(5):783-791(in Chinese).[郭裕蘭,魯敏,譚志國(guó),等.距離圖像局部特征提取方法綜述[J].模式識(shí)別與人工智能,2012,25(5):783-791.]

[4]Guo Y,Sohel F,Bennamoun M,et al.Rotational projection statistics for 3d local surface description and object recognition[J].International Journal of Computer Vision,2013,105(1):63-86.

[5]Guo Y,Bennamoun M,Sohel FA,et al.3D free form object recognition using rotational projection statistics[C]//Applications of Computer Vision.FL:IEEE,2013:1-8.

[6]Guo Y,Sohel F A,Bennamoun M,et al.RoPS:A local feature descriptor for 3D rigid objects based on rotational projection statistics[C]//International Conference on Communications,Signal Processing, and Their Applications.Sharjah:IEEE,2013:1-6.

[7]Rusu RB,Bradski G,Thibaux R,et al.Fast 3D recognition and pose using the Viewpoint Feature Histogram[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems.Taipei:IEEE,2014:2155-2162.

[8]Li P,Wang J,Zhao Y,et al.Improved algorithm for point cloud registration based on fast point feature histograms[J].Journal of Applied Remote Sensing,2016,10(4):045024.

[9]Salti S,Tombari F,Di stefano L.Shot:Unique signatures of histograms for surface and texture description[J].Computer Vision and Image Understanding,2014,125(8):251-264.

[10]Zaharescu A,Boyer E,Horaud R.Keypoints and local descriptors of scalar functions on 2d manifolds[J].International Journal of Computer Vision,2012,100(1):78-98.

[11]Petrelli A,Stefano LD.On the repeatability of the local refe-rence frame for partial shape matching[C]//IEEE International Conference on Computer Vision.Barcelona:ICCV,2011:2244-2251.