388 lines
20 KiB
HTML
388 lines
20 KiB
HTML
|
|
|
|
<!DOCTYPE html>
|
|
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
|
|
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
|
|
<head>
|
|
<meta charset="utf-8">
|
|
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0">
|
|
|
|
<title>Fast Point Feature Histograms (FPFH) descriptors — Point Cloud Library 1.12.0 documentation</title>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<script type="text/javascript" src="_static/js/modernizr.min.js"></script>
|
|
|
|
|
|
<script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
|
|
<script type="text/javascript" src="_static/jquery.js"></script>
|
|
<script type="text/javascript" src="_static/underscore.js"></script>
|
|
<script type="text/javascript" src="_static/doctools.js"></script>
|
|
<script type="text/javascript" src="_static/language_data.js"></script>
|
|
|
|
<script type="text/javascript" src="_static/js/theme.js"></script>
|
|
|
|
|
|
|
|
|
|
<link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
|
|
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
|
|
<link rel="index" title="Index" href="genindex.html" />
|
|
<link rel="search" title="Search" href="search.html" />
|
|
</head>
|
|
|
|
<body class="wy-body-for-nav">
|
|
|
|
|
|
<div class="wy-grid-for-nav">
|
|
|
|
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
|
|
<div class="wy-side-scroll">
|
|
<div class="wy-side-nav-search" >
|
|
|
|
|
|
|
|
<a href="index.html" class="icon icon-home"> Point Cloud Library
|
|
|
|
|
|
|
|
</a>
|
|
|
|
|
|
|
|
|
|
<div class="version">
|
|
1.12.0
|
|
</div>
|
|
|
|
|
|
|
|
|
|
<div role="search">
|
|
<form id="rtd-search-form" class="wy-form" action="search.html" method="get">
|
|
<input type="text" name="q" placeholder="Search docs" />
|
|
<input type="hidden" name="check_keywords" value="yes" />
|
|
<input type="hidden" name="area" value="default" />
|
|
</form>
|
|
</div>
|
|
|
|
|
|
</div>
|
|
|
|
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<!-- Local TOC -->
|
|
<div class="local-toc"><ul>
|
|
<li><a class="reference internal" href="#">Fast Point Feature Histograms (FPFH) descriptors</a></li>
|
|
<li><a class="reference internal" href="#theoretical-primer">Theoretical primer</a></li>
|
|
<li><a class="reference internal" href="#differences-between-pfh-and-fpfh">Differences between PFH and FPFH</a></li>
|
|
<li><a class="reference internal" href="#estimating-fpfh-features">Estimating FPFH features</a></li>
|
|
<li><a class="reference internal" href="#speeding-fpfh-with-openmp">Speeding FPFH with OpenMP</a></li>
|
|
</ul>
|
|
</div>
|
|
|
|
|
|
</div>
|
|
</div>
|
|
</nav>
|
|
|
|
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
|
|
|
|
|
|
<nav class="wy-nav-top" aria-label="top navigation">
|
|
|
|
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
|
|
<a href="index.html">Point Cloud Library</a>
|
|
|
|
</nav>
|
|
|
|
|
|
<div class="wy-nav-content">
|
|
|
|
<div class="rst-content">
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<div role="navigation" aria-label="breadcrumbs navigation">
|
|
|
|
<ul class="wy-breadcrumbs">
|
|
|
|
<li><a href="index.html">Docs</a> »</li>
|
|
|
|
<li>Fast Point Feature Histograms (FPFH) descriptors</li>
|
|
|
|
|
|
<li class="wy-breadcrumbs-aside">
|
|
|
|
|
|
|
|
</li>
|
|
|
|
</ul>
|
|
|
|
|
|
<hr/>
|
|
</div>
|
|
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
|
|
<div itemprop="articleBody">
|
|
|
|
<div class="section" id="fast-point-feature-histograms-fpfh-descriptors">
|
|
<span id="fpfh-estimation"></span><h1>Fast Point Feature Histograms (FPFH) descriptors</h1>
|
|
<p>The theoretical computational complexity of the Point Feature Histogram (see
|
|
<a class="reference internal" href="pfh_estimation.html#pfh-estimation"><span class="std std-ref">Point Feature Histograms (PFH) descriptors</span></a>) for a given point cloud <img class="math" src="_images/math/9dcbbef8e0f76051d388013b90a95bec3069e484.png" alt="P"/> with <img class="math" src="_images/math/e11f2701c4a39c7fe543a6c4150b421d50f1c159.png" alt="n"/> points
|
|
is <img class="math" src="_images/math/866b337d50f1df14d3a0a178ee35ecec4d03b10c.png" alt="O(nk^2)"/>, where <img class="math" src="_images/math/0b7c1e16a3a8a849bb8ffdcdbf86f65fd1f30438.png" alt="k"/> is the number of neighbors for each point
|
|
<img class="math" src="_images/math/27d463da4622be5b3ef1d4176ced7d7a323c6425.png" alt="p"/> in <img class="math" src="_images/math/9dcbbef8e0f76051d388013b90a95bec3069e484.png" alt="P"/>. For real-time or near real-time applications, the
|
|
computation of Point Feature Histograms in dense point neighborhoods can
|
|
represent one of the major bottlenecks.</p>
|
|
<p>This tutorial describes a simplification of the PFH formulation, called Fast
|
|
Point Feature Histograms (FPFH) (see <a class="reference internal" href="how_features_work.html#rusudissertation" id="id1">[RusuDissertation]</a> for more information),
|
|
that reduces the computational complexity of the algorithm to <img class="math" src="_images/math/05183080f866630e768f12d49bc272adfd9bc856.png" alt="O(nk)"/>,
|
|
while still retaining most of the discriminative power of the PFH.</p>
|
|
</div>
|
|
<div class="section" id="theoretical-primer">
|
|
<h1>Theoretical primer</h1>
|
|
<p>To simplify the histogram feature computation, we proceed as follows:</p>
|
|
<blockquote>
|
|
<div><ul class="simple">
|
|
<li>in a first step, for each query point <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/> a set of tuples
|
|
<img class="math" src="_images/math/bed82e2d27ba8ab77f72d246070de39916f43f4e.png" alt="\alpha, \phi, \theta"/> between itself and its neighbors are computed
|
|
as described in <a class="reference internal" href="pfh_estimation.html#pfh-estimation"><span class="std std-ref">Point Feature Histograms (PFH) descriptors</span></a> - this will be called the Simplified
|
|
Point Feature Histogram (SPFH);</li>
|
|
<li>in a second step, for each point its <img class="math" src="_images/math/0b7c1e16a3a8a849bb8ffdcdbf86f65fd1f30438.png" alt="k"/> neighbors are re-determined, and the
|
|
neighboring SPFH values are used to weight the final histogram of <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/>
|
|
(called FPFH) as follows:</li>
|
|
</ul>
|
|
</div></blockquote>
|
|
<div class="math">
|
|
<p><img src="_images/math/a9e532d075ea171726fd625d8cb2d589f3ed8dda.png" alt="FPFH(\boldsymbol{p}_q) = SPFH(\boldsymbol{p}_q) + {1 \over k} \sum_{i=1}^k {{1 \over \omega_i} \cdot SPFH(\boldsymbol{p}_i)}"/></p>
|
|
</div><p>where the weight <img class="math" src="_images/math/359c8be672c286f0451ce49e8c8b7db7f99fad74.png" alt="\omega_i"/> represents a distance between the query point
|
|
<img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/> and a neighbor point <img class="math" src="_images/math/24b68632b58b3294cc8f170cef67b2dd9510e981.png" alt="p_i"/> in some given metric space, thus
|
|
scoring the (<img class="math" src="_images/math/4584f2865f8e16f707dec0c0db3927bfa014bc61.png" alt="p_q, p_i"/>) pair, but could just as well be selected as a
|
|
different measure if necessary. To understand the importance of this weighting
|
|
scheme, the figure below presents the influence region diagram for a
|
|
k-neighborhood set centered at <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/>.</p>
|
|
<img alt="_images/fpfh_diagram.png" class="align-center" src="_images/fpfh_diagram.png" />
|
|
<p>Thus, for a given query point <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/>, the algorithm first estimates its
|
|
SPFH values by creating pairs between itself and its neighbors (illustrated
|
|
using red lines). This is repeated for all the points in the dataset, followed
|
|
by a re-weighting of the SPFH values of <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/> using the SPFH values of its
|
|
<img class="math" src="_images/math/0b7c1e16a3a8a849bb8ffdcdbf86f65fd1f30438.png" alt="k"/> neighbors, thus creating the FPFH for <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/>. The extra FPFH
|
|
connections, resultant due to the additional weighting scheme, are shown with
|
|
black lines. As the diagram shows, some of the value pairs will be counted
|
|
twice (marked with thicker lines in the figure).</p>
|
|
</div>
|
|
<div class="section" id="differences-between-pfh-and-fpfh">
|
|
<h1>Differences between PFH and FPFH</h1>
|
|
<p>The main differences between the PFH and FPFH formulations are summarized below:</p>
|
|
<blockquote>
|
|
<div><ol class="arabic simple">
|
|
<li>the FPFH does not fully interconnect all neighbors of <img class="math" src="_images/math/1557bf30f68d8d9460f124be9bad1e7739a98601.png" alt="p_q"/> as it
|
|
can be seen from the figure, and is thus missing some value pairs which
|
|
might contribute to capture the geometry around the query point;</li>
|
|
<li>the PFH models a precisely determined surface around the query point,
|
|
while the FPFH includes additional point pairs outside the <strong>r</strong> radius
|
|
sphere (though at most <strong>2r</strong> away);</li>
|
|
<li>because of the re-weighting scheme, the FPFH combines SPFH values and
|
|
recaptures some of the point neighboring value pairs;</li>
|
|
<li>the overall complexity of FPFH is greatly reduced, thus making possible to
|
|
use it in real-time applications;</li>
|
|
<li>the resultant histogram is simplified by decorrelating the values, that is
|
|
simply creating <em>d</em> separate feature histograms, one for each feature
|
|
dimension, and concatenate them together (see figure below).</li>
|
|
</ol>
|
|
</div></blockquote>
|
|
<img alt="_images/fpfh_theory.jpg" class="align-center" src="_images/fpfh_theory.jpg" />
|
|
</div>
|
|
<div class="section" id="estimating-fpfh-features">
|
|
<h1>Estimating FPFH features</h1>
|
|
<p>Fast Point Feature Histograms are implemented in PCL as part of the
|
|
<a class="reference external" href="http://docs.pointclouds.org/trunk/a02944.html">pcl_features</a>
|
|
library.</p>
|
|
<p>The default FPFH implementation uses 11 binning subdivisions (e.g., each of the
|
|
four feature values will use this many bins from its value interval), and a
|
|
decorrelated scheme (see above: the feature histograms are computed separately
|
|
and concantenated) which results in a 33-byte array of float values. These are
|
|
stored in a <strong>pcl::FPFHSignature33</strong> point type.</p>
|
|
<p>The following code snippet will estimate a set of FPFH features for all the
|
|
points in the input dataset.</p>
|
|
<div class="highlight-cpp notranslate"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1
|
|
2
|
|
3
|
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
13
|
|
14
|
|
15
|
|
16
|
|
17
|
|
18
|
|
19
|
|
20
|
|
21
|
|
22
|
|
23
|
|
24
|
|
25
|
|
26
|
|
27
|
|
28
|
|
29
|
|
30
|
|
31
|
|
32
|
|
33
|
|
34</pre></div></td><td class="code"><div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><pcl/point_types.h></span><span class="cp"></span>
|
|
<span class="cp">#include</span> <span class="cpf"><pcl/features/fpfh.h></span><span class="cp"></span>
|
|
|
|
<span class="p">{</span>
|
|
<span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">PointXYZ</span><span class="o">>::</span><span class="n">Ptr</span> <span class="n">cloud</span> <span class="p">(</span><span class="k">new</span> <span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">PointXYZ</span><span class="o">></span><span class="p">);</span>
|
|
<span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">Normal</span><span class="o">>::</span><span class="n">Ptr</span> <span class="n">normals</span> <span class="p">(</span><span class="k">new</span> <span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">Normal</span><span class="o">></span> <span class="p">());</span>
|
|
|
|
<span class="p">...</span> <span class="n">read</span><span class="p">,</span> <span class="n">pass</span> <span class="n">in</span> <span class="n">or</span> <span class="n">create</span> <span class="n">a</span> <span class="n">point</span> <span class="n">cloud</span> <span class="n">with</span> <span class="n">normals</span> <span class="p">...</span>
|
|
<span class="p">...</span> <span class="p">(</span><span class="nl">note</span><span class="p">:</span> <span class="n">you</span> <span class="n">can</span> <span class="n">create</span> <span class="n">a</span> <span class="n">single</span> <span class="n">PointCloud</span><span class="o"><</span><span class="n">PointNormal</span><span class="o">></span> <span class="k">if</span> <span class="n">you</span> <span class="n">want</span><span class="p">)</span> <span class="p">...</span>
|
|
|
|
<span class="c1">// Create the FPFH estimation class, and pass the input dataset+normals to it</span>
|
|
<span class="n">pcl</span><span class="o">::</span><span class="n">FPFHEstimation</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">PointXYZ</span><span class="p">,</span> <span class="n">pcl</span><span class="o">::</span><span class="n">Normal</span><span class="p">,</span> <span class="n">pcl</span><span class="o">::</span><span class="n">FPFHSignature33</span><span class="o">></span> <span class="n">fpfh</span><span class="p">;</span>
|
|
<span class="n">fpfh</span><span class="p">.</span><span class="n">setInputCloud</span> <span class="p">(</span><span class="n">cloud</span><span class="p">);</span>
|
|
<span class="n">fpfh</span><span class="p">.</span><span class="n">setInputNormals</span> <span class="p">(</span><span class="n">normals</span><span class="p">);</span>
|
|
<span class="c1">// alternatively, if cloud is of tpe PointNormal, do fpfh.setInputNormals (cloud);</span>
|
|
|
|
<span class="c1">// Create an empty kdtree representation, and pass it to the FPFH estimation object.</span>
|
|
<span class="c1">// Its content will be filled inside the object, based on the given input dataset (as no other search surface is given).</span>
|
|
<span class="n">pcl</span><span class="o">::</span><span class="n">search</span><span class="o">::</span><span class="n">KdTree</span><span class="o"><</span><span class="n">PointXYZ</span><span class="o">>::</span><span class="n">Ptr</span> <span class="n">tree</span> <span class="p">(</span><span class="k">new</span> <span class="n">pcl</span><span class="o">::</span><span class="n">search</span><span class="o">::</span><span class="n">KdTree</span><span class="o"><</span><span class="n">PointXYZ</span><span class="o">></span><span class="p">);</span>
|
|
|
|
<span class="n">fpfh</span><span class="p">.</span><span class="n">setSearchMethod</span> <span class="p">(</span><span class="n">tree</span><span class="p">);</span>
|
|
|
|
<span class="c1">// Output datasets</span>
|
|
<span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">FPFHSignature33</span><span class="o">>::</span><span class="n">Ptr</span> <span class="n">fpfhs</span> <span class="p">(</span><span class="k">new</span> <span class="n">pcl</span><span class="o">::</span><span class="n">PointCloud</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">FPFHSignature33</span><span class="o">></span> <span class="p">());</span>
|
|
|
|
<span class="c1">// Use all neighbors in a sphere of radius 5cm</span>
|
|
<span class="c1">// IMPORTANT: the radius used here has to be larger than the radius used to estimate the surface normals!!!</span>
|
|
<span class="n">fpfh</span><span class="p">.</span><span class="n">setRadiusSearch</span> <span class="p">(</span><span class="mf">0.05</span><span class="p">);</span>
|
|
|
|
<span class="c1">// Compute the features</span>
|
|
<span class="n">fpfh</span><span class="p">.</span><span class="n">compute</span> <span class="p">(</span><span class="o">*</span><span class="n">fpfhs</span><span class="p">);</span>
|
|
|
|
<span class="c1">// fpfhs->size () should have the same size as the input cloud->size ()*</span>
|
|
<span class="p">}</span>
|
|
</pre></div>
|
|
</td></tr></table></div>
|
|
<p>The actual <strong>compute</strong> call from the <strong>FPFHEstimation</strong> class does nothing internally but:</p>
|
|
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>for each point p in cloud P
|
|
|
|
1. pass 1:
|
|
|
|
1. get the nearest neighbors of :math:`p`
|
|
|
|
2. for each pair of :math:`p, p_i` (where :math:`p_i` is a neighbor of :math:`p`, compute the three angular values
|
|
|
|
3. bin all the results in an output SPFH histogram
|
|
|
|
2. pass 2:
|
|
|
|
1. get the nearest neighbors of :math:`p`
|
|
|
|
3. use each SPFH of :math:`p` with a weighting scheme to assemble the FPFH of :math:`p`:
|
|
</pre></div>
|
|
</div>
|
|
<div class="admonition note">
|
|
<p class="first admonition-title">Note</p>
|
|
<p>For efficiency reasons, the <strong>compute</strong> method in <strong>FPFHEstimation</strong> does not check if the normals contains NaN or infinite values.
|
|
Passing such values to <strong>compute()</strong> will result in undefined output.
|
|
It is advisable to check the normals, at least during the design of the processing chain or when setting the parameters.
|
|
This can be done by inserting the following code before the call to <strong>compute()</strong>:</p>
|
|
<div class="highlight-cpp notranslate"><div class="highlight"><pre><span></span><span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">normals</span><span class="o">-></span><span class="n">size</span><span class="p">();</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
|
|
<span class="p">{</span>
|
|
<span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">pcl</span><span class="o">::</span><span class="n">isFinite</span><span class="o"><</span><span class="n">pcl</span><span class="o">::</span><span class="n">Normal</span><span class="o">></span><span class="p">((</span><span class="o">*</span><span class="n">normals</span><span class="p">)[</span><span class="n">i</span><span class="p">]))</span>
|
|
<span class="p">{</span>
|
|
<span class="n">PCL_WARN</span><span class="p">(</span><span class="s">"normals[%d] is not finite</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span> <span class="n">i</span><span class="p">);</span>
|
|
<span class="p">}</span>
|
|
<span class="p">}</span>
|
|
</pre></div>
|
|
</div>
|
|
<p class="last">In production code, preprocessing steps and parameters should be set so that normals are finite or raise an error.</p>
|
|
</div>
|
|
</div>
|
|
<div class="section" id="speeding-fpfh-with-openmp">
|
|
<h1>Speeding FPFH with OpenMP</h1>
|
|
<p>For the speed-savvy users, PCL provides an additional implementation of FPFH
|
|
estimation which uses multi-core/multi-threaded paradigms using OpenMP to speed
|
|
the computation. The name of the class is <strong>pcl::FPFHEstimationOMP</strong>, and its
|
|
API is 100% compatible to the single-threaded <strong>pcl::FPFHEstimation</strong>, which
|
|
makes it suitable as a drop-in replacement. On a system with 8 cores, you
|
|
should get anything between 6-8 times faster computation times.</p>
|
|
</div>
|
|
|
|
|
|
</div>
|
|
|
|
</div>
|
|
<footer>
|
|
|
|
|
|
<hr/>
|
|
|
|
<div role="contentinfo">
|
|
<p>
|
|
© Copyright
|
|
|
|
</p>
|
|
</div>
|
|
Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
|
|
|
|
</footer>
|
|
|
|
</div>
|
|
</div>
|
|
|
|
</section>
|
|
|
|
</div>
|
|
|
|
|
|
|
|
<script type="text/javascript">
|
|
jQuery(function () {
|
|
SphinxRtdTheme.Navigation.enable(true);
|
|
});
|
|
</script>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
</body>
|
|
</html> |