基于概率直方图的点云特征描述符算法

朱慧 杨杰

摘要：针对现有点云特征描述符算法提取较慢的问题，提出一种基于概率直方图的点云特征描述符提取方法。该算法首先选中计算点作为中心点，建立一个球形点云区域，在此球形区域内建立局部坐标系，计算球形区域内所有邻域点和原点的模长及与坐标轴的角度，得出概率直方图，作为该点的特征描述符。实验结果表明，该算法能够快速提取出该点的特征，并且能使用此特征在采样一致性初始配准算法中准确的进行点云的配准，配准速度较传统算法有所提升。

关键词：点云描述符;概率直方图;点云配准

中图分类号：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.