几何特征系列:Fast Point Feature Histogram(快速点特征直方图)
在几何特征系列的上一篇文章中,介绍了 Point Featrue Histogram。那么根据 PFH 的原理,给定包含 个点的点云 ,则计算点云 中所有点的 PFH 特征的复杂度为 ,其中 是 中某一个点 的邻域的个数。可见,计算 PFH 特征的效率其实是十分低的,这样的算法复杂度无法实现实时或接近实时的应用。因此,这篇文章将介绍 PFH 的简化加速版本 Fast Point Feature Histogram,在这里简称为 FPFH,中文名译作「快速点特征直方图」。FPFH 能保留 PFH 的大部分特性和获得近似的结果,并能将计算复杂度降为 。
Fast Point Feature Histogram 的介绍
由于 FPFH 由 PFH 延伸变化而来,因此与 PFH 该几何特征共享着大部分的特性和原理,具体 PFH 的特性和细节可参考回博客中的这篇文章。FPFH 的输入也是具有法线信息的点云,输出是能反映每个点周围邻域相关特征的直方图。但与 PFH 不同的是,会采取一些简化和优化措施来加快 FPFH 的计算速度。通过对比点云的 FPFH 结果,同样可以用来寻找点云内部或不同点云之间的关联关系。需要强调的是,点云的法线质量对于 FPFH 该几何特征的质量也有着非常大的影响。
Fast Point Feature Histogram 的原理
下面具体介绍 FPFH 如何通过简化和优化使计算变得更快的。
- 首先是对每个点 ,利用与 PFH 相似的方法计算它与它每个邻域之间的三元组,并统计得到一个 Simplified Point Feature Histogram,即简化的点特征直方图,在这里简称为 SPFH。
- 接下来的一步是重新确定每个点的 邻域,并使用邻近的 SPFH 值来加权计算得到最终 的直方图,也就是所谓的 FPFH。计算 FPFH 的公式如下:
其中权重 依赖于中心点 与某个近邻点 在给定的度量空间中的距离,用以衡量点对 的权重。当然,在这里也可以选用其他的度量方式来设置这个权重。为了理解公式的过程和加权方式,这里将利用下图来作进一步解释,该图表示的是以点 为中心的 邻域影响范围图。
如图所示,给定一个点 ,算法首先通过该点与它的邻域(由红色标注的线段连接)计算出该点的 SPFH,并随后依次对点云中的所有点执行这一步。但此时对比 PFH 会发现,缺少了邻域点之间的联系和影响。因此,需要加权其所有邻域点 的 SPFH 并与 自身的 SPFH 相结合,从而更新计算得到点 最终的 FPFH。由图可知,其实这种加权方式会考虑到邻域的邻域。所有这些被考虑到的点对关系在图中以黑色线表示,若点对被考虑的次数越多,黑线则越粗,即代表着有更高的权重,对中心点 有着更大的影响。
Fast Point Feature Histogram 与 Point Feature Histogram 的对比
FPFH 与 PFH 相比,计算方式大致有以下几个不同的方面:
- FPFH 并没有完全考虑某中心点 邻域内所有的点对关系,所以会丢失一些可能捕获到周围几何特征的信息,从上面的示例图中也能反映出来。
- PFH 的特征模型建立在中心点周围的一个精确半径范围内,而 FPFH 还包括半径 范围以外的一些额外点(但最大的半径范围不超过 )。
- SPFH 的获得基于中心点及其邻域所形成的点对,而 PFH 还需要邻域之间的点对, 因此 FPFH 整体的计算复杂度被大大地降低(),使其能应用于实时的应用当中。
- FPFH 通过引入一种新的加权方式,根据与中心点的空间距离,对中心点的邻域的 SPFH 进行加权,并与中心点自身的 SPFH 相结合,重新捕获到邻域点之间的关联信息和变化。
Fast Point Feature Histogram 的应用
利用 FPFH 除了和 PFH 一样可以进行聚类之外,还能进行点云的配准。最后,下图展示的是利用 FPFH 进行配准的应用结果。
图中左侧是两只配准前的 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
Latest posts by LEEMANCHIU (see all)
- SIGGRAPH Asia 2017 之旅 - 2017-12-10
- SIGGRAPH 2017 之旅 - 2017-12-05
- 深入理解现代 OpenGL - 2016-08-29
博主介绍的特征描述子很详细,学习了,感谢!
点个赞!
博主关于PFH和FPFH两篇文章都写得很好,作为刚入门的萌新,很清楚