Loading...
Searching...
No Matches
flann_search.h
/*
* Software License Agreement (BSD License)
*
* Point Cloud Library (PCL) - www.pointclouds.org
* Copyright (c) 2010-2011, Willow Garage, Inc.
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
* * Neither the name of the copyright holder(s) nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
* ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* $Id$
*/
#pragma once
#include <pcl/search/search.h>
#include <pcl/common/time.h>
#include <pcl/point_representation.h>
namespace flann
{
template<typename T> class NNIndex;
template<typename T> struct L2;
template<typename T> struct L2_Simple;
template<typename T> class Matrix;
}
namespace pcl
{
namespace search
{
/** \brief @b search::FlannSearch is a generic FLANN wrapper class for the new search interface.
* It is able to wrap any FLANN index type, e.g. the kd tree as well as indices for high-dimensional
* searches and intended as a more powerful and cleaner successor to KdTreeFlann.
*
* By default, this class creates a single kd tree for indexing the input data. However, for high dimensions
* (> 10), it is often better to use the multiple randomized kd tree index provided by FLANN in combination with
* the \ref flann::L2 distance functor. During search in this type of index, the number of checks to perform before
* terminating the search can be controlled. Here is a code example if a high-dimensional 2-NN search:
*
* \code
* // Feature and distance type
* using FeatureT = SHOT352;
* using DistanceT = flann::L2<float>;
*
* // Search and index types
* using SearchT = search::FlannSearch<FeatureT, DistanceT>;
* using CreatorPtrT = typename SearchT::FlannIndexCreatorPtr;
* using IndexT = typename SearchT::KdTreeMultiIndexCreator;
* using RepresentationPtrT = typename SearchT::PointRepresentationPtr;
*
* // Features
* PointCloud<FeatureT>::Ptr query, target;
*
* // Fill query and target with calculated features...
*
* // Instantiate search object with 4 randomized trees and 256 checks
* SearchT search (true, CreatorPtrT (new IndexT (4)));
* search.setPointRepresentation (RepresentationPtrT (new DefaultFeatureRepresentation<FeatureT>));
* search.setChecks (256);
* search.setInputCloud (target);
*
* // Do search
* std::vector<Indices> k_indices;
* std::vector<std::vector<float> > k_sqr_distances;
* search.nearestKSearch (*query, Indices (), 2, k_indices, k_sqr_distances);
* \endcode
*
* \author Andreas Muetzel
* \author Anders Glent Buch (multiple randomized kd tree interface)
* \ingroup search
*/
template<typename PointT, typename FlannDistance=flann::L2_Simple <float> >
class FlannSearch: public Search<PointT>
{
using Search<PointT>::input_;
using Search<PointT>::indices_;
using Search<PointT>::sorted_results_;
public:
using Ptr = shared_ptr<FlannSearch<PointT, FlannDistance> >;
using ConstPtr = shared_ptr<const FlannSearch<PointT, FlannDistance> >;
using PointCloud = typename Search<PointT>::PointCloud;
using PointCloudConstPtr = typename Search<PointT>::PointCloudConstPtr;
using MatrixPtr = shared_ptr<flann::Matrix<float> >;
using MatrixConstPtr = shared_ptr<const flann::Matrix<float> >;
using Index = flann::NNIndex<FlannDistance>;
using IndexPtr = shared_ptr<flann::NNIndex<FlannDistance> >;
using PointRepresentation = pcl::PointRepresentation<PointT>;
using PointRepresentationPtr = typename PointRepresentation::Ptr;
using PointRepresentationConstPtr = typename PointRepresentation::ConstPtr;
/** \brief Helper class that creates a FLANN index from a given FLANN matrix. To
* use a FLANN index type with FlannSearch, implement this interface and
* pass an object of the new type to the FlannSearch constructor.
* See the implementation of KdTreeIndexCreator for an example.
*/
class FlannIndexCreator
{
public:
/** \brief Create a FLANN Index from the input data.
* \param[in] data The FLANN matrix containing the input.
* \return The FLANN index.
*/
virtual IndexPtr createIndex (MatrixConstPtr data)=0;
/** \brief destructor
*/
virtual ~FlannIndexCreator () = default;
};
using FlannIndexCreatorPtr = shared_ptr<FlannIndexCreator>;
/** \brief Creates a FLANN KdTreeSingleIndex from the given input data.
*/
class KdTreeIndexCreator: public FlannIndexCreator
{
public:
/** \param[in] max_leaf_size All FLANN kd trees created by this class will have
* a maximum of max_leaf_size points per leaf node. Higher values make index creation
* cheaper, but search more costly (and the other way around).
*/
KdTreeIndexCreator (unsigned int max_leaf_size=15) : max_leaf_size_ (max_leaf_size){}
/** \brief Empty destructor */
~KdTreeIndexCreator () override = default;
/** \brief Create a FLANN Index from the input data.
* \param[in] data The FLANN matrix containing the input.
* \return The FLANN index.
*/
IndexPtr createIndex (MatrixConstPtr data) override;
private:
unsigned int max_leaf_size_;
};
/** \brief Creates a FLANN KdTreeSingleIndex from the given input data.
*/
class KMeansIndexCreator: public FlannIndexCreator
{
public:
/** \brief All FLANN kd trees created by this class will have
* a maximum of max_leaf_size points per leaf node. Higher values make index creation
* cheaper, but search more costly (and the other way around).
*/
KMeansIndexCreator () = default;
/** \brief Empty destructor */
virtual ~KMeansIndexCreator () = default;
/** \brief Create a FLANN Index from the input data.
* \param[in] data The FLANN matrix containing the input.
* \return The FLANN index.
*/
virtual IndexPtr createIndex (MatrixConstPtr data);
private:
};
/** \brief Creates a FLANN KdTreeIndex of multiple randomized trees from the given input data,
* suitable for feature matching. Note that in this case, it is often more efficient to use the
* \ref flann::L2 distance functor.
*/
class KdTreeMultiIndexCreator: public FlannIndexCreator
{
public:
/** \param[in] trees Number of randomized trees to create.
*/
KdTreeMultiIndexCreator (int trees = 4) : trees_ (trees) {}
/** \brief Empty destructor */
virtual ~KdTreeMultiIndexCreator () = default;
/** \brief Create a FLANN Index from the input data.
* \param[in] data The FLANN matrix containing the input.
* \return The FLANN index.
*/
virtual IndexPtr createIndex (MatrixConstPtr data);
private:
int trees_;
};
FlannSearch (bool sorted = true, FlannIndexCreatorPtr creator = FlannIndexCreatorPtr (new KdTreeIndexCreator ()));
/** \brief Destructor for FlannSearch. */
~FlannSearch () override;
//void
//setInputCloud (const PointCloudConstPtr &cloud, const IndicesConstPtr &indices = IndicesConstPtr ());
/** \brief Set the search epsilon precision (error bound) for nearest neighbors searches.
* \param[in] eps precision (error bound) for nearest neighbors searches
*/
inline void
setEpsilon (double eps)
{
eps_ = eps;
}
/** \brief Get the search epsilon precision (error bound) for nearest neighbors searches. */
inline double
getEpsilon ()
{
return (eps_);
}
/** \brief Set the number of checks to perform during approximate searches in multiple randomized trees.
* \param[in] checks number of checks to perform during approximate searches in multiple randomized trees.
*/
inline void
setChecks (int checks)
{
checks_ = checks;
}
/** \brief Get the number of checks to perform during approximate searches in multiple randomized trees. */
inline int
getChecks ()
{
return (checks_);
}
/** \brief Provide a pointer to the input dataset.
* \param[in] cloud the const boost shared pointer to a PointCloud message
* \param[in] indices the point indices subset that is to be used from \a cloud
*/
bool
setInputCloud (const PointCloudConstPtr& cloud, const IndicesConstPtr& indices = IndicesConstPtr ()) override;
using Search<PointT>::nearestKSearch;
/** \brief Search for the k-nearest neighbors for the given query point.
* \param[in] point the given query point
* \param[in] k the number of neighbors to search for
* \param[out] k_indices the resultant indices of the neighboring points (must be resized to \a k a priori!)
* \param[out] k_sqr_distances the resultant squared distances to the neighboring points (must be resized to \a k
* a priori!)
* \return number of neighbors found
*/
int
nearestKSearch (const PointT &point, int k, Indices &k_indices, std::vector<float> &k_sqr_distances) const override;
/** \brief Search for the k-nearest neighbors for the given query point.
* \param[in] cloud the point cloud data
* \param[in] indices a vector of point cloud indices to query for nearest neighbors
* \param[in] k the number of neighbors to search for
* \param[out] k_indices the resultant indices of the neighboring points, k_indices[i] corresponds to the neighbors of the query point i
* \param[out] k_sqr_distances the resultant squared distances to the neighboring points, k_sqr_distances[i] corresponds to the neighbors of the query point i
*/
void
nearestKSearch (const PointCloud& cloud, const Indices& indices, int k,
std::vector<Indices>& k_indices, std::vector< std::vector<float> >& k_sqr_distances) const override;
/** \brief Search for all the nearest neighbors of the query point in a given radius.
* \param[in] point the given query point
* \param[in] radius the radius of the sphere bounding all of p_q's neighbors
* \param[out] k_indices the resultant indices of the neighboring points
* \param[out] k_sqr_distances the resultant squared distances to the neighboring points
* \param[in] max_nn if given, bounds the maximum returned neighbors to this value. If \a max_nn is set to
* 0 or to a number higher than the number of points in the input cloud, all neighbors in \a radius will be
* returned.
* \return number of neighbors found in radius
*/
int
radiusSearch (const PointT& point, double radius,
Indices &k_indices, std::vector<float> &k_sqr_distances,
unsigned int max_nn = 0) const override;
/** \brief Search for the k-nearest neighbors for the given query point.
* \param[in] cloud the point cloud data
* \param[in] indices a vector of point cloud indices to query for nearest neighbors
* \param[in] radius the radius of the sphere bounding all of p_q's neighbors
* \param[out] k_indices the resultant indices of the neighboring points, k_indices[i] corresponds to the neighbors of the query point i
* \param[out] k_sqr_distances the resultant squared distances to the neighboring points, k_sqr_distances[i] corresponds to the neighbors of the query point i
* \param[in] max_nn if given, bounds the maximum returned neighbors to this value
*/
void
radiusSearch (const PointCloud& cloud, const Indices& indices, double radius, std::vector<Indices>& k_indices,
std::vector< std::vector<float> >& k_sqr_distances, unsigned int max_nn=0) const override;
/** \brief Provide a pointer to the point representation to use to convert points into k-D vectors.
* \param[in] point_representation the const boost shared pointer to a PointRepresentation
*/
inline void
setPointRepresentation (const PointRepresentationConstPtr &point_representation)
{
point_representation_ = point_representation;
dim_ = point_representation->getNumberOfDimensions ();
if (input_) // re-create the tree, since point_representation might change things such as the scaling of the point clouds.
setInputCloud (input_, indices_);
}
/** \brief Get a pointer to the point representation used when converting points into k-D vectors. */
inline PointRepresentationConstPtr const
getPointRepresentation ()
{
return (point_representation_);
}
protected:
/** \brief converts the input data to a format usable by FLANN
*/
void convertInputToFlannMatrix();
/** The FLANN index.
*/
IndexPtr index_;
/** The index creator, used to (re-) create the index when the search data is passed.
*/
FlannIndexCreatorPtr creator_;
/** Input data in FLANN format.
*/
MatrixPtr input_flann_;
/** Epsilon for approximate NN search.
*/
float eps_{0.0f};
/** Number of checks to perform for approximate NN search using the multiple randomized tree index
*/
int checks_{32};
bool input_copied_for_flann_{false};
PointRepresentationConstPtr point_representation_{nullptr};
int dim_{0};
Indices index_mapping_;
bool identity_mapping_{false};
std::size_t total_nr_points_{0};
};
}
}
// There is no cpp file containing template instantiations of FlannSearch
#include <pcl/search/impl/flann_search.hpp>
#define PCL_INSTANTIATE_FlannSearch(T) template class PCL_EXPORTS pcl::search::FlannSearch<T>;
flann::Matrix
Definition flann_search.h:50
flann::NNIndex
Definition flann_search.h:47
pcl::PointCloud
PointCloud represents the base class in PCL for storing collections of 3D points.
Definition point_cloud.h:173
pcl::PointRepresentation
PointRepresentation provides a set of methods for converting a point structs/object into an n-dimensi...
Definition point_representation.h:60
pcl::PointRepresentation::ConstPtr
shared_ptr< const PointRepresentation< PointT > > ConstPtr
Definition point_representation.h:79
pcl::PointRepresentation::Ptr
shared_ptr< PointRepresentation< PointT > > Ptr
Definition point_representation.h:78
pcl::search::FlannSearch::FlannIndexCreator
Helper class that creates a FLANN index from a given FLANN matrix.
Definition flann_search.h:129
pcl::search::FlannSearch::FlannIndexCreator::createIndex
virtual IndexPtr createIndex(MatrixConstPtr data)=0
Create a FLANN Index from the input data.
pcl::search::FlannSearch::FlannIndexCreator::~FlannIndexCreator
virtual ~FlannIndexCreator()=default
destructor
pcl::search::FlannSearch::KMeansIndexCreator
Creates a FLANN KdTreeSingleIndex from the given input data.
Definition flann_search.h:169
pcl::search::FlannSearch::KMeansIndexCreator::KMeansIndexCreator
KMeansIndexCreator()=default
All FLANN kd trees created by this class will have a maximum of max_leaf_size points per leaf node.
pcl::search::FlannSearch::KMeansIndexCreator::createIndex
virtual IndexPtr createIndex(MatrixConstPtr data)
Create a FLANN Index from the input data.
Definition flann_search.hpp:63
pcl::search::FlannSearch::KMeansIndexCreator::~KMeansIndexCreator
virtual ~KMeansIndexCreator()=default
Empty destructor.
pcl::search::FlannSearch::KdTreeIndexCreator
Creates a FLANN KdTreeSingleIndex from the given input data.
Definition flann_search.h:146
pcl::search::FlannSearch::KdTreeIndexCreator::~KdTreeIndexCreator
~KdTreeIndexCreator() override=default
Empty destructor.
pcl::search::FlannSearch::KdTreeIndexCreator::KdTreeIndexCreator
KdTreeIndexCreator(unsigned int max_leaf_size=15)
Definition flann_search.h:152
pcl::search::FlannSearch::KdTreeIndexCreator::createIndex
IndexPtr createIndex(MatrixConstPtr data) override
Create a FLANN Index from the input data.
Definition flann_search.hpp:55
pcl::search::FlannSearch::KdTreeMultiIndexCreator
Creates a FLANN KdTreeIndex of multiple randomized trees from the given input data,...
Definition flann_search.h:193
pcl::search::FlannSearch::KdTreeMultiIndexCreator::createIndex
virtual IndexPtr createIndex(MatrixConstPtr data)
Create a FLANN Index from the input data.
Definition flann_search.hpp:71
pcl::search::FlannSearch::KdTreeMultiIndexCreator::KdTreeMultiIndexCreator
KdTreeMultiIndexCreator(int trees=4)
Definition flann_search.h:197
pcl::search::FlannSearch::KdTreeMultiIndexCreator::~KdTreeMultiIndexCreator
virtual ~KdTreeMultiIndexCreator()=default
Empty destructor.
pcl::search::FlannSearch
search::FlannSearch is a generic FLANN wrapper class for the new search interface.
Definition flann_search.h:101
pcl::search::FlannSearch::setEpsilon
void setEpsilon(double eps)
Set the search epsilon precision (error bound) for nearest neighbors searches.
Definition flann_search.h:225
pcl::search::FlannSearch::convertInputToFlannMatrix
void convertInputToFlannMatrix()
converts the input data to a format usable by FLANN
Definition flann_search.hpp:372
pcl::search::FlannSearch::radiusSearch
int radiusSearch(const PointT &point, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const override
Search for all the nearest neighbors of the query point in a given radius.
Definition flann_search.hpp:240
pcl::search::FlannSearch::total_nr_points_
std::size_t total_nr_points_
Definition flann_search.h:366
pcl::search::FlannSearch::IndexPtr
shared_ptr< flann::NNIndex< FlannDistance > > IndexPtr
Definition flann_search.h:117
pcl::search::FlannSearch::dim_
int dim_
Definition flann_search.h:361
pcl::search::FlannSearch::PointRepresentation
pcl::PointRepresentation< PointT > PointRepresentation
Definition flann_search.h:119
pcl::search::FlannSearch::checks_
int checks_
Number of checks to perform for approximate NN search using the multiple randomized tree index.
Definition flann_search.h:355
pcl::search::FlannSearch::getEpsilon
double getEpsilon()
Get the search epsilon precision (error bound) for nearest neighbors searches.
Definition flann_search.h:232
pcl::search::FlannSearch::MatrixConstPtr
shared_ptr< const flann::Matrix< float > > MatrixConstPtr
Definition flann_search.h:114
pcl::search::FlannSearch::~FlannSearch
~FlannSearch() override
Destructor for FlannSearch.
Definition flann_search.hpp:86
pcl::search::FlannSearch::setChecks
void setChecks(int checks)
Set the number of checks to perform during approximate searches in multiple randomized trees.
Definition flann_search.h:241
pcl::search::FlannSearch::input_flann_
MatrixPtr input_flann_
Input data in FLANN format.
Definition flann_search.h:347
pcl::search::FlannSearch::setInputCloud
bool setInputCloud(const PointCloudConstPtr &cloud, const IndicesConstPtr &indices=IndicesConstPtr()) override
Provide a pointer to the input dataset.
Definition flann_search.hpp:94
pcl::search::FlannSearch::identity_mapping_
bool identity_mapping_
Definition flann_search.h:364
pcl::search::FlannSearch::Ptr
shared_ptr< FlannSearch< PointT, FlannDistance > > Ptr
Definition flann_search.h:107
pcl::search::FlannSearch::point_representation_
PointRepresentationConstPtr point_representation_
Definition flann_search.h:359
pcl::search::FlannSearch::FlannIndexCreatorPtr
shared_ptr< FlannIndexCreator > FlannIndexCreatorPtr
Definition flann_search.h:141
pcl::search::FlannSearch::nearestKSearch
int nearestKSearch(const PointT &point, int k, Indices &k_indices, std::vector< float > &k_sqr_distances) const override
Search for the k-nearest neighbors for the given query point.
Definition flann_search.hpp:106
pcl::search::FlannSearch::PointCloudConstPtr
typename Search< PointT >::PointCloudConstPtr PointCloudConstPtr
Definition flann_search.h:111
pcl::search::FlannSearch::PointCloud
typename Search< PointT >::PointCloud PointCloud
Definition flann_search.h:110
pcl::search::FlannSearch::creator_
FlannIndexCreatorPtr creator_
The index creator, used to (re-) create the index when the search data is passed.
Definition flann_search.h:343
pcl::search::FlannSearch::index_mapping_
Indices index_mapping_
Definition flann_search.h:363
pcl::search::FlannSearch::index_
IndexPtr index_
The FLANN index.
Definition flann_search.h:339
pcl::search::FlannSearch::PointRepresentationConstPtr
typename PointRepresentation::ConstPtr PointRepresentationConstPtr
Definition flann_search.h:121
pcl::search::FlannSearch::getChecks
int getChecks()
Get the number of checks to perform during approximate searches in multiple randomized trees.
Definition flann_search.h:248
pcl::search::FlannSearch::setPointRepresentation
void setPointRepresentation(const PointRepresentationConstPtr &point_representation)
Provide a pointer to the point representation to use to convert points into k-D vectors.
Definition flann_search.h:316
pcl::search::FlannSearch::getPointRepresentation
PointRepresentationConstPtr const getPointRepresentation()
Get a pointer to the point representation used when converting points into k-D vectors.
Definition flann_search.h:326
pcl::search::FlannSearch::PointRepresentationPtr
typename PointRepresentation::Ptr PointRepresentationPtr
Definition flann_search.h:120
pcl::search::FlannSearch::input_copied_for_flann_
bool input_copied_for_flann_
Definition flann_search.h:357
pcl::search::FlannSearch::eps_
float eps_
Epsilon for approximate NN search.
Definition flann_search.h:351
pcl::search::FlannSearch::MatrixPtr
shared_ptr< flann::Matrix< float > > MatrixPtr
Definition flann_search.h:113
pcl::search::FlannSearch::ConstPtr
shared_ptr< const FlannSearch< PointT, FlannDistance > > ConstPtr
Definition flann_search.h:108
pcl::search::Search
Generic search class.
Definition search.h:75
pcl::search::Search::input_
PointCloudConstPtr input_
Definition search.h:402
pcl::search::Search::PointCloudConstPtr
typename PointCloud::ConstPtr PointCloudConstPtr
Definition search.h:79
pcl::search::Search::indices_
IndicesConstPtr indices_
Definition search.h:403
pcl::search::Search::sorted_results_
bool sorted_results_
Definition search.h:404
time.h
Define methods for measuring time spent in code blocks.
flann
Definition kdtree_flann.h:50
pcl
Definition convolution.h:46
pcl::IndicesConstPtr
shared_ptr< const Indices > IndicesConstPtr
Definition pcl_base.h:59
pcl::Indices
IndicesAllocator<> Indices
Type used for indices in PCL.
Definition types.h:133
flann::L2_Simple
Definition kdtree_flann.h:51
flann::L2
Definition flann_search.h:48
pcl::PointXYZRGB
A point structure representing Euclidean xyz coordinates, and the RGB color.
Definition point_types.hpp:594