基于概率直方圖的點(diǎn)云特征描述符算法

朱慧 楊杰

摘要：針對(duì)現(xiàn)有點(diǎn)云特征描述符算法提取較慢的問題，提出一種基于概率直方圖的點(diǎn)云特征描述符提取方法。該算法首先選中計(jì)算點(diǎn)作為中心點(diǎn)，建立一個(gè)球形點(diǎn)云區(qū)域，在此球形區(qū)域內(nèi)建立局部坐標(biāo)系，計(jì)算球形區(qū)域內(nèi)所有鄰域點(diǎn)和原點(diǎn)的模長(zhǎng)及與坐標(biāo)軸的角度，得出概率直方圖，作為該點(diǎn)的特征描述符。實(shí)驗(yàn)結(jié)果表明，該算法能夠快速提取出該點(diǎn)的特征，并且能使用此特征在采樣一致性初始配準(zhǔn)算法中準(zhǔn)確的進(jìn)行點(diǎn)云的配準(zhǔn)，配準(zhǔn)速度較傳統(tǒng)算法有所提升。

關(guān)鍵詞：點(diǎn)云描述符;概率直方圖;點(diǎn)云配準(zhǔn)

中圖分類號(hào)：TP242.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-1037（2021）01-0059-05

基金項(xiàng)目：

機(jī)器人視覺處理軟件研發(fā)（批準(zhǔn)號(hào)：20193702030779）資助。

通信作者：楊杰，男，副教授，主要研究方向?yàn)榛谖锫?lián)網(wǎng)的嵌入式系統(tǒng)，網(wǎng)絡(luò)并行運(yùn)動(dòng)控制與應(yīng)用圖像識(shí)別技術(shù)等。

點(diǎn)云特征描述符在計(jì)算機(jī)視覺領(lǐng)域中的三維重建[1]、三維識(shí)別[2]以及同步定位與地圖構(gòu)建 （Simultaneous Localization and Mapping，SLAM） [3]中起著重要作用?，F(xiàn)有點(diǎn)云描述符可大致概括為全局描述符（global descriptor）和局部描述符（local descriptor）。Rusu等[4-5]先提出了點(diǎn)特征直方圖（Point Feature Histograms，PFH）特征描述符，維度較高，且計(jì)算量較大;為提升計(jì)算速度，又提出快速點(diǎn)特征直方圖（Fast Point Feature Histograms，F(xiàn)PFH）特征描述符，降低了維度，計(jì)算量小，運(yùn)行速度較快[6-7];Marton等[8-9]提出的基于半徑的平面描述符（ Radius-Based Surface Descriptor，RSD），通過假設(shè)一個(gè)關(guān)鍵點(diǎn)對(duì)位于球體表面，并擬和關(guān)鍵點(diǎn)對(duì)的法線，最后得出對(duì)應(yīng)的球體，并最后保留半徑最大和最小的球體作為其描述符;Tombari等[10-11]提出的方向直方圖特征描述符（Signature of Histograms of Orientations，SHOT），使用球形支撐結(jié)構(gòu)來構(gòu)造相關(guān)拓?fù)湫畔ⅲ撉蝮w劃分為32個(gè)區(qū)域，每個(gè)區(qū)域都會(huì)計(jì)算一個(gè)直方圖，最后組合得到一個(gè)直方圖作為特征描述符。上述的算法都是比較經(jīng)典的點(diǎn)云特征描述符算法[12]，有較高的魯棒性和分辨性，但在點(diǎn)云數(shù)量較大時(shí)，使用時(shí)有特征提取較慢或配準(zhǔn)速度慢的問題，特征提取快慢和算法提取特征的方式有關(guān)，配準(zhǔn)速度快慢則和特征描述符的維數(shù)有關(guān)。為此，本文提出一種在保證特征效果的前提下，也能夠較快匹配的算法，名為球形區(qū)域特征直方圖（Spherical Region Feature Histogram，SRFH）算法，該算法特征描述符有52維，有較高的分辨性，具有較好的配準(zhǔn)效果，同時(shí)維度較低，保證了配準(zhǔn)的速度。

1 求解質(zhì)心坐標(biāo)

2 建立坐標(biāo)系

如圖2所示，在原本的球形區(qū)域里又重新劃分了一個(gè)小的球形區(qū)域，二者同心。

3 建立3D直方圖

3.1 分割象限

如圖3所示，球形區(qū)域內(nèi)的所有的鄰域點(diǎn)由新建坐標(biāo)系分割到8個(gè)象限當(dāng)中，設(shè)某個(gè)鄰域點(diǎn)Pt和球心Pc組成的向量為vt，方向是由Pc指向Pt，x，y，z三個(gè)坐標(biāo)軸的方向向量為i，j，k。

3.2 計(jì)算角度直方圖

如圖4所示，將向量vt和x軸組成的夾角設(shè)為α，和y軸組成的夾角β，和z軸組成的夾角γ。

由于算出來的夾角范圍是[0，π]，而需要的角度是[0，2π]，所以根據(jù)不同的象限對(duì)結(jié)果進(jìn)行修正

由式（10）、（11）、（12）求出球形區(qū)域內(nèi)所有鄰域點(diǎn)Pn的三個(gè)角度，每個(gè)角度的取值范圍是[0，360°]，每120°為一個(gè)格，將其均分成3格，則α，β，γ各分成3格，共有3×3×3個(gè)方格，每個(gè)方格初始值為0，求出所有鄰域點(diǎn)Pn的三個(gè)角度值，每個(gè)鄰域點(diǎn)Pn匹配對(duì)應(yīng)方格，則對(duì)應(yīng)方格的值加1/k，k為球形區(qū)域內(nèi)鄰域點(diǎn)的個(gè)數(shù)，再將所有的鄰域點(diǎn)Pn與方格一一匹配，最終得到一個(gè)直方圖，直方圖的值得大小代表落在對(duì)應(yīng)區(qū)間點(diǎn)的概率，得到的直方圖可以表示為一個(gè)27維的向量，如表1所示。

3.3 計(jì)算模長(zhǎng)直方圖

除角度外還計(jì)算了向量vt的模長(zhǎng)以增強(qiáng)特征描述符的辨別性。模長(zhǎng)的取值范圍為[0，r]，其中，r為球形區(qū)域的半徑，將[0，r]均分成25個(gè)初始值為0的方格，每個(gè)鄰域點(diǎn)的向量的模長(zhǎng)匹配對(duì)應(yīng)方格，對(duì)應(yīng)方格的數(shù)值加1/k，k為球形區(qū)域內(nèi)鄰域點(diǎn)的個(gè)數(shù)，最后得到一個(gè)直方圖，即一個(gè)25維的向量，如表2所示。將表1，表2兩個(gè)直方圖合并成一個(gè)直方圖，即最后得到一個(gè)52維的向量，將此向量作為當(dāng)前點(diǎn)的特征描述符。

4 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在CPU為AMD Ryzen7 4800H@2.9GHz，內(nèi)存大小是16GB的PC上，于Ubuntu20.04的系統(tǒng)下，基于PCL V1.11.0點(diǎn)云庫(kù)的條件下開發(fā)進(jìn)行，使用點(diǎn)云為斯坦福大學(xué)的bunny模型。為比較提出算法效果，和目前效果較好的FPFH，SHOT以及RSD算法進(jìn)行比較，并統(tǒng)一將鄰域半徑設(shè)置為0.01，分別統(tǒng)計(jì)各算法特征提取及配準(zhǔn)時(shí)間，以及配準(zhǔn)的得分，得分越小，證明配準(zhǔn)誤差越小，反之，則配準(zhǔn)誤差越大。

配準(zhǔn)時(shí)使用的算法為采樣一致性初始配準(zhǔn)（Sample Consensus Initial Aligment，SAC-IA）算法[6]，從不同算法配準(zhǔn)效果圖可以較容易的看出，圖5（b）、圖5（c）的配準(zhǔn)效果不是很完美，有些地方匹配不準(zhǔn)確，相比較圖5（d）、圖5（e）的配準(zhǔn)效果則好了很多，目標(biāo)點(diǎn)云和源點(diǎn)云幾乎完全重合。

表3中的SRFH為本文提出算法，對(duì)表3的Score分析可知，F(xiàn)PFH和SHOT算法的分值較高，證明其配準(zhǔn)誤差較大，且FPFH和SHOT算法在特征提取上耗時(shí)較長(zhǎng)，但FPFH在配準(zhǔn)時(shí)間上耗時(shí)最短;RSD和本文提出的算法在特征則提取耗時(shí)較短，且Score較小，配準(zhǔn)誤差小，但RSD在配準(zhǔn)時(shí)間上耗時(shí)較長(zhǎng)。比較描述符維度和配準(zhǔn)時(shí)間可知，二者呈正相關(guān)。綜上比較，本文提出的算法在特征提取時(shí)間及配準(zhǔn)效果上表現(xiàn)最好，且在配準(zhǔn)時(shí)間也有著優(yōu)異的表現(xiàn)。該算法使用較低維度的描述符，保證了特征提取速度，同時(shí)描述符較高的分辨性，使得配準(zhǔn)時(shí)的誤差較低，證明本文提出的算法在效率和穩(wěn)健性方面具有一定的優(yōu)勢(shì)。

5 結(jié)論

目前的三維點(diǎn)云描述符算法在提取速度及配準(zhǔn)效果在單方面效果較好，但綜合性能較差，未能二者兼顧，本文提出的三維點(diǎn)云描述符算法較傳統(tǒng)算法SHOT及RSD等在速度方面有15%以上的提升，同時(shí)擁有較好的效果，能夠兼顧速度及效果，具有更好的實(shí)用性。但是本文算法對(duì)于參數(shù)的選取有較高的要求，日后可以進(jìn)行自適應(yīng)的參數(shù)選取，無需人為手動(dòng)選參數(shù)。

參考文獻(xiàn)

[1]XU Y， TUTTAS S， HOEGNER L， et al. Reconstruction of scaffolds from a photogrammetric point cloud of construction sites using a novel 3D local feature descriptor[J]. Automation in Construction， 2018， 85：76-95.

[2]HOSSEIN R， ARIF M， DU H， et al. Histogram of oriented principal components for cross-view action recognition[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence， 2016， 38（12）：2430-2443.

[3]權(quán)美香，樸松昊，李國(guó).視覺SLAM綜述[J].智能系統(tǒng)學(xué)報(bào)，2016，11（6）：768-776.

[4]BURGARD W， DILLMANN R， PLAGEMANN C， et al. Persistent point feature histograms for 3D point clouds[C]//Proc 10th Int Conf Intel Autonomous Syst （IAS-10）. Baden-Baden， Germany. 2008： 119-128.

[5]RUSU R B. Semantic 3D object maps for everyday manipulation in human living environments[J]. KI-Kunstliche Intelligenz， 2010， 24（4）：345-348.

[6]RUSU R B， BLODOW N， BEETZ M. Fast point feature histograms （FPFH） for 3D registration[C]//2009 IEEE International Conference on Robotics and Automation. IEEE， 2009： 3212-3217.

[7]RUSU R B， COUSINS S. 3D is here： Point cloud library （pcl）[C]//2011 IEEE International Conference on Robotics and Automation， Shanghai， 2011： 1-4.

[8]MARTON Z C， PANGERCIC D， BLODOW N， et al. General 3D modelling of novel objects from a single view[C]//2010 IEEE/RSJ International Conference on Intelligent Robots and Systems， Taiwan， 2010： 3700-3705.

[9]MARTON Z C， PANGERCIC D， BLODOW N， et al. Combined 2D-3D categorization and classification for multimodal perception systems[J]. The International Journal of Robotics Research， 2011， 30（11）： 1378-1402.

[10] TOMBARI F， SALTI S， STEFANO L D. Unique signatures of histograms for local surface description[C]// 11th European Conference on Computer Vision， Berlin， Heidelberg， 2010： 356-369.

[11] TOMBARI F， SALTI S， STEFANO L D. A combined texture-shape descriptor for enhanced 3D feature matching[C]// 18th IEEE International Conference on Image Processing， Brussels， 2011： 809-812.

[12] 吳飛，趙新燦，展鵬磊，等.自適應(yīng)鄰域選擇的FPFH特征提取算法[J].計(jì)算機(jī)科學(xué)，2019，46（2）：266-270.