几何特征系列:Fast Point Feature Histogram(快速点特征直方图)

在几何特征系列的上一篇文章中,介绍了 Point Featrue Histogram。那么根据 PFH 的原理,给定包含 n 个点的点云 P,则计算点云 P 中所有点的 PFH 特征的复杂度为 O({nk^2}),其中 kP 中某一个点(p_i) 的邻域的个数。可见,计算 PFH 特征的效率其实是十分低的,这样的算法复杂度无法实现实时或接近实时的应用。因此,这篇文章将介绍 PFH 的简化加速版本 Fast Point Feature Histogram,在这里简称为 FPFH,中文名译作「快速点特征直方图」。FPFH 能保留 PFH 的大部分特性和获得近似的结果,并能将计算复杂度降为 O(nk)

Fast Point Feature Histogram 的介绍

由于 FPFH 由 PFH 延伸变化而来,因此与 PFH 该几何特征共享着大部分的特性和原理,具体 PFH 的特性和细节可参考回博客中的这篇文章。FPFH 的输入也是具有法线信息的点云,输出是能反映每个点周围邻域相关特征的直方图。但与 PFH 不同的是,会采取一些简化和优化措施来加快 FPFH 的计算速度。通过对比点云的 FPFH 结果,同样可以用来寻找点云内部或不同点云之间的关联关系。需要强调的是,点云的法线质量对于 FPFH 该几何特征的质量也有着非常大的影响。

Fast Point Feature Histogram 的原理

下面具体介绍 FPFH 如何通过简化和优化使计算变得更快的。

  • 首先是对每个点 (p_q),利用与 PFH 相似的方法计算它与它每个邻域之间的三元组\langle \alpha ,\phi ,\theta \rangle ,并统计得到一个 Simplified Point Feature Histogram,即简化的点特征直方图,在这里简称为 SPFH。
  • 接下来的一步是重新确定每个点的 k 邻域,并使用邻近的 SPFH 值来加权计算得到最终 p_q 的直方图,也就是所谓的 FPFH。计算 FPFH 的公式如下:

    FPFH(p_q) = SPFH(p_q) + \frac{1}{k}\sum\limits_{i = 1}^k {\frac{1}{\omega _k}} \cdot SPFH(p_k)

其中权重 \omega _k 依赖于中心点 p_q 与某个近邻点 p_k 在给定的度量空间中的距离,用以衡量点对 ({p_q},{p_k}) 的权重。当然,在这里也可以选用其他的度量方式来设置这个权重。为了理解公式的过程和加权方式,这里将利用下图来作进一步解释,该图表示的是以点 p_q 为中心的 k 邻域影响范围图。

fpfh-diagram

如图所示,给定一个点 p_q,算法首先通过该点与它的邻域(由红色标注的线段连接)计算出该点的 SPFH,并随后依次对点云中的所有点执行这一步。但此时对比 PFH 会发现,缺少了邻域点之间的联系和影响。因此,需要加权其所有邻域点 p_k 的 SPFH 并与 p_q 自身的 SPFH 相结合,从而更新计算得到点 p_q  最终的 FPFH。由图可知,其实这种加权方式会考虑到邻域的邻域。所有这些被考虑到的点对关系在图中以黑色线表示,若点对被考虑的次数越多,黑线则越粗,即代表着有更高的权重,对中心点 p_q 有着更大的影响。

Fast Point Feature Histogram 与 Point Feature Histogram 的对比

FPFH 与 PFH 相比,计算方式大致有以下几个不同的方面:

  1. FPFH 并没有完全考虑某中心点 p_q 邻域内所有的点对关系,所以会丢失一些可能捕获到周围几何特征的信息,从上面的示例图中也能反映出来。
  2. PFH 的特征模型建立在中心点周围的一个精确半径范围内,而 FPFH 还包括半径 r 范围以外的一些额外点(但最大的半径范围不超过 2r )。
  3. SPFH 的获得基于中心点及其邻域所形成的点对,而 PFH 还需要邻域之间的点对, 因此 FPFH 整体的计算复杂度被大大地降低(O(nk)),使其能应用于实时的应用当中。
  4. FPFH 通过引入一种新的加权方式,根据与中心点的空间距离,对中心点的邻域的 SPFH 进行加权,并与中心点自身的 SPFH 相结合,重新捕获到邻域点之间的关联信息和变化。

Fast Point Feature Histogram 的应用

利用 FPFH 除了和 PFH 一样可以进行聚类之外,还能进行点云的配准。最后,下图展示的是利用 FPFH 进行配准的应用结果。

fpfh- registration

图中左侧是两只配准前的 Bunny,右侧则是配准后的结果,可见利用 FPFH 进行配准的结果还是比较理想的。具体的实现细节请参考下方参考文献所给出的这篇文章:Fast Point Feature Histograms (FPFH) for 3D Registration

参考文献

Rusu R B, Blodow N, Beetz M. Fast point feature histograms (FPFH) for 3D registration[C]//Robotics and Automation, 2009. ICRA'09. IEEE International Conference on. IEEE, 2009: 3212-3217.

Fast Point Feature Histograms (FPFH) descriptors. http://pointclouds.org/documentation/tutorials/fpfh_estimation.php

几何特征系列:Shape Diameter Function(形状直径函数). http://lemonc.me/point-feature-histogram.html

Overview and Comparison of Features. https://github.com/PointCloudLibrary/pcl/wiki/Overview-and-Comparison-of-Features#fpfh-fast-point-feature-histogram

LEEMANCHIU

LEEMANCHIU

香港科技大学在读博士研究生,曾是中国科学院大学的硕士研究生
联系邮箱 | Personal Homepage
LEEMANCHIU

Latest posts by LEEMANCHIU (see all)

3 Responses to “几何特征系列:Fast Point Feature Histogram(快速点特征直方图)

  • 博主介绍的特征描述子很详细,学习了,感谢!

  • 点个赞!

  • 博主关于PFH和FPFH两篇文章都写得很好,作为刚入门的萌新,很清楚

发表评论

电子邮件地址不会被公开。 必填项已用*标注