基于鄰域旋轉(zhuǎn)體積的關(guān)鍵點描述子及其應(yīng)用

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

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

0 引 言

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

1 相關(guān)工作

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

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

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

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

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

2 描述子建立過程

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

(1)

(2)

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

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

在計算Regionk中兩相鄰鄰域點及其投影點所形成的梯形旋轉(zhuǎn)后的模型的體積Vk,i時，可將該模型拆分為一個空心圓柱體Modelk,i,1和一個中間為空心圓柱的圓臺Modelk,i,2。Modelk,i,1的體積Vk,i,1可用式(4)進行計算，其中，hk,i,1代表的Modelk,i,1的高，rk,i-1和rk,i分別代表Modelk,i,1的內(nèi)、外半徑，均可通過式(6)進行計算。Modelk,i,2的體積Vk,i,2可由圓臺的體積Vk,i,3與圓柱的體積Vk,i,4相減而得，見式(7)。式(8)用于計算體積Vk,i,3,其中hk,i,2代表圓臺的高，rk,i-1和rk,i分別代表圓臺的內(nèi)、外半徑，也通過式(6)進行計算。式(9)用于計算體積Vk,i,4，其中hk,i,2代表空心圓柱的高，通過式(10)進行計算，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)，計算關(guān)鍵點p的其它m-1個維度的數(shù)值，最終組成一個m維的描述子。

3 實驗結(jié)果及分析

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

3.1 運行時間分析

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

表1 實驗?zāi)Ｐ托畔?/p>

表2 各個方法不同模型的運行時間

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

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

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

匹配準確率=正確匹配的描述子對的數(shù)目/匹配的描述子對的數(shù)目

(11)

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

3.3 抗噪性分析

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

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

圖4 抗噪性分析

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

3.4 不同采樣率分析

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

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

圖5 多采樣率分析

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

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

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

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

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

(3)找到fs0、fs1和fs2對應(yīng)的關(guān)鍵點ks0、ks1和ks2，依次連接該3點形成3條邊并計算它們的歐式距離，分為記為d_ks01、d_ks12和d_ks20，同理計算ft0、ft1和ft2對應(yīng)關(guān)鍵點所形成3條邊的歐式距離，分別記為d_kt01、d_kt12和d_kt20，依次計算對應(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)時則繼續(xù)步驟(4)，否則退回到步驟(2)；

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

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

對每兩個相鄰的點云片依次執(zhí)行上面的操作，最終可以將6片點云都變換到同一坐標系下，得到完整的模型。本文的配準結(jié)果如圖6所示。

圖6 基于本文所提出的描述子的配準

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

5 結(jié)束語

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

[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).[郭裕蘭,魯敏,譚志國,等.距離圖像局部特征提取方法綜述[J].模式識別與人工智能,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.