基于概率直方圖的點云特征描述符算法

朱慧 楊杰

摘要：針對現有點云特征描述符算法提取較慢的問題，提出一種基于概率直方圖的點云特征描述符提取方法。該算法首先選中計算點作為中心點，建立一個球形點云區域，在此球形區域內建立局部坐標系，計算球形區域內所有鄰域點和原點的模長及與坐標軸的角度，得出概率直方圖，作為該點的特征描述符。實驗結果表明，該算法能夠快速提取出該點的特征，并且能使用此特征在采樣一致性初始配準算法中準確的進行點云的配準，配準速度較傳統算法有所提升。

關鍵詞：點云描述符;概率直方圖;點云配準

中圖分類號：TP242.6

文獻標志碼：A

文章編號：1006-1037（2021）01-0059-05

基金項目：

機器人視覺處理軟件研發（批準號：20193702030779）資助。

通信作者：楊杰，男，副教授，主要研究方向為基于物聯網的嵌入式系統，網絡并行運動控制與應用圖像識別技術等。

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

1 求解質心坐標

2 建立坐標系

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

3 建立3D直方圖

3.1 分割象限

如圖3所示，球形區域內的所有的鄰域點由新建坐標系分割到8個象限當中，設某個鄰域點Pt和球心Pc組成的向量為vt，方向是由Pc指向Pt，x，y，z三個坐標軸的方向向量為i，j，k。

3.2 計算角度直方圖

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

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

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

3.3 計算模長直方圖

除角度外還計算了向量vt的模長以增強特征描述符的辨別性。模長的取值范圍為[0，r]，其中，r為球形區域的半徑，將[0，r]均分成25個初始值為0的方格，每個鄰域點的向量的模長匹配對應方格，對應方格的數值加1/k，k為球形區域內鄰域點的個數，最后得到一個直方圖，即一個25維的向量，如表2所示。將表1，表2兩個直方圖合并成一個直方圖，即最后得到一個52維的向量，將此向量作為當前點的特征描述符。

4 實驗結果與分析

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

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

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

5 結論

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

參考文獻

[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]權美香，樸松昊，李國.視覺SLAM綜述[J].智能系統學報，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] 吳飛，趙新燦，展鵬磊，等.自適應鄰域選擇的FPFH特征提取算法[J].計算機科學，2019，46（2）：266-270.