Nearest neighbor index over a set of features. More...

#include <FlannIndex.h>

Public Types
enum	flann_algorithm_t { FLANN_INDEX_LINEAR = 0 , FLANN_INDEX_KDTREE = 1 , FLANN_INDEX_KDTREE_SINGLE = 4 , FLANN_INDEX_LSH = 6 , NANOFLANN_INDEX_KDTREE_SINGLE = 100 }
	The index structure built by buildIndex() More...

Public Member Functions
void	release ()
	Drop the index and everything it holds, back to the state of a new one.

std::vector< unsigned char >	serializeIndex (bool computeChecksum=true) const
	Serialize the index, to be given back to loadIndex()

size_t	indexedFeatures () const

size_t	memoryUsed () const

void	buildIndex (flann_algorithm_t algorithm, const cv::Mat &features, bool useDistanceL1=false, float rebalancingFactor=2.0f)
	Build the index over the given features, releasing any previous one.

bool	loadIndex (const std::vector< unsigned char > &indexData, flann_algorithm_t algorithm, const cv::Mat &features, bool useDistanceL1=false, float rebalancingFactor=2.0f, std::string *errorMsg=NULL)
	Load an index serialized by serializeIndex(), releasing any previous one.

bool	loadIndex (const unsigned char indexData, size_t indexDataSize, flann_algorithm_t algorithm, const cv::Mat &features, bool useDistanceL1=false, float rebalancingFactor=2.0f, std::string errorMsg=NULL)
	Load an index from a raw buffer, see the overload above.

bool	isBuilt ()

int	featuresType () const

int	featuresDim () const

std::vector< unsigned int >	addPoints (const cv::Mat &features)
	Add features to the index.

void	removePoint (unsigned int index)
	Remove an indexed feature, by the index addPoints() gave for it.

void	knnSearch (const cv::Mat &query, cv::Mat &indices, cv::Mat &dists, int knn, int checks=32, float eps=0.0, bool sorted=true) const
	Search the k nearest neighbors of each query.

void	radiusSearch (const cv::Mat &query, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< float > > &dists, float radius, int maxNeighbors=0, int checks=32, float eps=0.0, bool sorted=true) const
	Search the neighbors of each query within a radius.

Detailed Description

Nearest neighbor index over a set of features.

Wraps the search structures of the vendored rtflann and nanoflann libraries behind one interface, the structure being chosen with flann_algorithm_t at build time. Used for the visual word dictionary (VWDictionary) and for the 2D point searches of visual registration (RegistrationVis).

The features are not copied: the index refers to the matrices it is given and keeps them alive, cv::Mat data being reference counted, so they must not be modified in place while it is in use. Every point it holds is designated by an index, assigned in the order the points were added and stable for the lifetime of the index: removePoint() leaves a hole rather than renumbering the points after it.

Definition at line 55 of file FlannIndex.h.

Member Enumeration Documentation

◆ flann_algorithm_t

enum rtabmap::FlannIndex::flann_algorithm_t

The index structure built by buildIndex()

The values under 8 are forwarded from rtflann's own enum and have to match it (see src/rtflann/defines.h); the nanoflann ones are rtabmap-specific and kept outside its range (0-7, 254, 255). A value is written in the serialized index header and checked back on load, so none of them may be renumbered.

The nanoflann structures take float features only (nanoflann has no Hamming metric) and search exactly, ignoring "checks". That makes them the fastest ones for 2D and 3D points, and the wrong ones for descriptors: an exact search visits more and more of the tree as the dimension grows, down to being as slow as an exhaustive search. Prefer the approximate rtflann kd-trees for those.

Enumerator
FLANN_INDEX_LINEAR	Exhaustive search.
FLANN_INDEX_KDTREE	4 randomized kd-trees, searched approximately
FLANN_INDEX_KDTREE_SINGLE	Single kd-tree, searched exactly.
FLANN_INDEX_LSH	Locality-Sensitive Hashing (binary descriptors)
NANOFLANN_INDEX_KDTREE_SINGLE	nanoflann kd-tree. With a rebalancing factor of 1 it is built once, which is the cheapest to build and to search; over 1 it is the weight-balanced tree accepting addPoints()/removePoint(), which cannot be serialized while some of its points are removed.

Definition at line 75 of file FlannIndex.h.

Member Function Documentation

◆ serializeIndex()

std::vector< unsigned char > rtabmap::FlannIndex::serializeIndex ( bool computeChecksum = true ) const

Serialize the index, to be given back to loadIndex()

Parameters

computeChecksum Add a checksum of the indexed features to the data, which loadIndex() compares against the features it is given

Returns: The serialized index, empty when there is nothing to serialize or when the structure in use cannot be

The format depends on the architecture and on the versions of the vendored libraries: loadIndex() refuses an index it cannot read, leaving it to be rebuilt.

◆ indexedFeatures()

size_t rtabmap::FlannIndex::indexedFeatures ( ) const

Returns: Number of indexed features, the removed ones excluded.

◆ memoryUsed()

size_t rtabmap::FlannIndex::memoryUsed ( ) const

Returns: Bytes used by the index, the features themselves excluded as they are only referred to.

◆ buildIndex()

void rtabmap::FlannIndex::buildIndex	(	flann_algorithm_t	algorithm,
		const cv::Mat &	features,
		bool	useDistanceL1 = `false`,
		float	rebalancingFactor = `2.0f`
	)

Build the index over the given features, releasing any previous one.

Parameters

algorithm	The structure to build
features	One feature per row, CV_32FC1 or, for the rtflann structures only, CV_8UC1 for binary descriptors (Hamming distance)
useDistanceL1	Search with the L1 distance instead of L2, ignored by LSH and by the binary descriptors
rebalancingFactor	Fraction (factor-1)/factor of the index that can be left removed before it is rebuilt, e.g. half of it for 2. Set to 1 to never rebuild it.

◆ loadIndex()

bool rtabmap::FlannIndex::loadIndex	(	const std::vector< unsigned char > &	indexData,
		flann_algorithm_t	algorithm,
		const cv::Mat &	features,
		bool	useDistanceL1 = `false`,
		float	rebalancingFactor = `2.0f`,
		std::string *	errorMsg = `NULL`
	)

Load an index serialized by serializeIndex(), releasing any previous one.

Parameters

indexData	The serialized index
algorithm	The structure it was built with
features	The very same features it was built with, in the same order: the index refers to them by their row
useDistanceL1	The distance it was built with
rebalancingFactor	See buildIndex(). The serialized data carries the one the index was built with, which is deprecated and ignored: this one is used instead.
errorMsg	Filled with what didn't match when the index is refused

Returns: False if the data doesn't correspond to the given features and parameters, in which case the index is left released

◆ isBuilt()

bool rtabmap::FlannIndex::isBuilt ( )

Returns: Whether an index has been built or loaded.

◆ featuresType()

int rtabmap::FlannIndex::featuresType ( ) const

inline

Returns: Type of the indexed features (CV_32FC1 or CV_8UC1).

Definition at line 169 of file FlannIndex.h.

◆ featuresDim()

int rtabmap::FlannIndex::featuresDim ( ) const

inline

Returns: Dimension of the indexed features.

Definition at line 171 of file FlannIndex.h.

◆ addPoints()

std::vector< unsigned int > rtabmap::FlannIndex::addPoints ( const cv::Mat & features )

Add features to the index.

Parameters

features One feature per row, of the type and dimension the index was built with

Returns: The index assigned to each of them, empty when the structure doesn't accept points after it is built

◆ removePoint()

void rtabmap::FlannIndex::removePoint ( unsigned int index )

Remove an indexed feature, by the index addPoints() gave for it.

The feature is only marked as removed: it is skipped by the searches, but keeps taking memory until the index is rebuilt (see the rebalancing factor of buildIndex()). Not supported by every structure.

◆ knnSearch()

void rtabmap::FlannIndex::knnSearch	(	const cv::Mat &	query,
		cv::Mat &	indices,
		cv::Mat &	dists,
		int	knn,
		int	checks = `32`,
		float	eps = `0.0`,
		bool	sorted = `true`
	)		const

Search the k nearest neighbors of each query.

Parameters

query	One feature per row, of the type and dimension the index was built with
indices	Neighbors found, one query per row, CV_32SC1. The neighbors that couldn't be found are set to -1.
dists	Their squared distances, CV_32FC1, or CV_32SC1 for the Hamming distances of binary descriptors
knn	Number of neighbors to search for
checks	Number of leaves an approximate search visits, the exact structures ignoring it
eps	Search for eps-approximate neighbors
sorted	Give the neighbors back by increasing distance

◆ radiusSearch()

void rtabmap::FlannIndex::radiusSearch	(	const cv::Mat &	query,
		std::vector< std::vector< size_t > > &	indices,
		std::vector< std::vector< float > > &	dists,
		float	radius,
		int	maxNeighbors = `0`,
		int	checks = `32`,
		float	eps = `0.0`,
		bool	sorted = `true`
	)		const

Search the neighbors of each query within a radius.

Parameters

query	One feature per row, of the type and dimension the index was built with
indices	Neighbors found, one vector per query
dists	Their squared distances, one vector per query
radius	Search radius, squared internally: it is a distance, not a squared one
maxNeighbors	Maximum number of neighbors per query, the nearest ones being kept. 0 for all of them.
checks	Number of leaves an approximate search visits, the exact structures ignoring it
eps	Search for eps-approximate neighbors
sorted	Give the neighbors back by increasing distance

The documentation for this class was generated from the following file:

corelib/include/rtabmap/core/FlannIndex.h

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ flann_algorithm_t

Member Function Documentation

◆ serializeIndex()

◆ indexedFeatures()

◆ memoryUsed()

◆ buildIndex()

◆ loadIndex()

◆ isBuilt()

◆ featuresType()

◆ featuresDim()

◆ addPoints()

◆ removePoint()

◆ knnSearch()

◆ radiusSearch()