#include <kdtree_index.h>

Inheritance diagram for rtflann::KDTreeIndex< Distance >:

Classes
struct	Node

Public Types
typedef NNIndex< Distance >	BaseClass

typedef Distance::ResultType	DistanceType

typedef Distance::ElementType	ElementType

typedef bool	needs_kdtree_distance

Public Types inherited from rtflann::NNIndex< Distance >
typedef Distance::ResultType	DistanceType

typedef Distance::ElementType	ElementType

Public Member Functions
void	addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
	Incrementally add points to the index. More...

virtual void	buildIndex ()

virtual void	buildIndex (const Matrix< ElementType > &dataset)

BaseClass *	clone () const

void	findNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const

flann_algorithm_t	getType () const

	KDTreeIndex (const IndexParams &params=KDTreeIndexParams(), Distance d=Distance())

	KDTreeIndex (const KDTreeIndex &other)

	KDTreeIndex (const Matrix< ElementType > &dataset, const IndexParams &params=KDTreeIndexParams(), Distance d=Distance())

void	loadIndex (FILE *stream)

KDTreeIndex &	operator= (KDTreeIndex other)

void	saveIndex (FILE *stream)

template<typename Archive >
void	serialize (Archive &ar)

int	usedMemory () const

virtual	~KDTreeIndex ()

Public Member Functions inherited from rtflann::NNIndex< Distance >
virtual void	buildIndex ()

virtual void	buildIndex (const Matrix< ElementType > &dataset)

IndexParams	getParameters () const

virtual ElementType *	getPoint (size_t id)

virtual int	knnSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search. More...

int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const

virtual int	knnSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, size_t knn, const SearchParams &params) const
	Perform k-nearest neighbor search. More...

	NNIndex (const IndexParams &params, Distance d)

	NNIndex (const NNIndex &other)

	NNIndex (Distance d)

int	radiusSearch (const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const

virtual int	radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const
	Perform radius search. More...

int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< int > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const

virtual int	radiusSearch (const Matrix< ElementType > &queries, std::vector< std::vector< size_t > > &indices, std::vector< std::vector< DistanceType > > &dists, float radius, const SearchParams &params) const
	Perform radius search. More...

size_t	removedCount () const

virtual void	removePoint (size_t id)

template<typename Archive >
void	serialize (Archive &ar)

size_t	size () const

size_t	sizeAtBuild () const

size_t	veclen () const

virtual	~NNIndex ()

Public Member Functions inherited from rtflann::IndexBase
virtual	~IndexBase ()

Protected Member Functions
void	buildIndexImpl ()

void	freeIndex ()

Protected Member Functions inherited from rtflann::NNIndex< Distance >
void	cleanRemovedPoints ()

void	extendDataset (const Matrix< ElementType > &new_points)

size_t	id_to_index (size_t id)

void	indices_to_ids (const size_t in, size_t out, size_t size) const

void	setDataset (const Matrix< ElementType > &dataset)

void	swap (NNIndex &other)

Private Types
enum	{ SAMPLE_MEAN = 100, RAND_DIM =5 }

typedef BranchSt *	Branch

typedef BranchStruct< NodePtr, DistanceType >	BranchSt

typedef Node *	NodePtr

Private Member Functions
void	addPointToTree (NodePtr node, int ind)

void	copyTree (NodePtr &dst, const NodePtr &src)

NodePtr	divideTree (int *ind, int count)

template<bool with_removed>
void	getExactNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, float epsError) const

template<bool with_removed>
void	getNeighbors (ResultSet< DistanceType > &result, const ElementType *vec, int maxCheck, float epsError) const

void	meanSplit (int *ind, int count, int &index, int &cutfeat, DistanceType &cutval)

void	planeSplit (int *ind, int count, int cutfeat, DistanceType cutval, int &lim1, int &lim2)

template<bool with_removed>
void	searchLevel (ResultSet< DistanceType > &result_set, const ElementType vec, NodePtr node, DistanceType mindist, int &checkCount, int maxCheck, float epsError, Heap< BranchSt > heap, DynamicBitset &checked) const

template<bool with_removed>
void	searchLevelExact (ResultSet< DistanceType > &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, const float epsError) const

int	selectDivision (DistanceType *v)

void	swap (KDTreeIndex &other)

Private Attributes
DistanceType *	mean_

PooledAllocator	pool_

std::vector< NodePtr >	tree_roots_

int	trees_

DistanceType *	var_

Additional Inherited Members
Protected Attributes inherited from rtflann::NNIndex< Distance >
ElementType *	data_ptr_

Distance	distance_

std::vector< size_t >	ids_

IndexParams	index_params_

size_t	last_id_

std::vector< ElementType * >	points_

bool	removed_

size_t	removed_count_

DynamicBitset	removed_points_

size_t	size_

size_t	size_at_build_

size_t	veclen_

Detailed Description

template<typename Distance>
class rtflann::KDTreeIndex< Distance >

Randomized kd-tree index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

Definition at line 101 of file kdtree_index.h.

Member Typedef Documentation

◆ BaseClass

template<typename Distance >

typedef NNIndex<Distance> rtflann::KDTreeIndex< Distance >::BaseClass

Definition at line 107 of file kdtree_index.h.

◆ Branch

template<typename Distance >

typedef BranchSt* rtflann::KDTreeIndex< Distance >::Branch

private

Definition at line 177 of file kdtree_index.h.

◆ BranchSt

template<typename Distance >

typedef BranchStruct<NodePtr, DistanceType> rtflann::KDTreeIndex< Distance >::BranchSt

private

Definition at line 176 of file kdtree_index.h.

◆ DistanceType

template<typename Distance >

typedef Distance::ResultType rtflann::KDTreeIndex< Distance >::DistanceType

Definition at line 105 of file kdtree_index.h.

◆ ElementType

template<typename Distance >

typedef Distance::ElementType rtflann::KDTreeIndex< Distance >::ElementType

Definition at line 104 of file kdtree_index.h.

◆ needs_kdtree_distance

template<typename Distance >

typedef bool rtflann::KDTreeIndex< Distance >::needs_kdtree_distance

Definition at line 109 of file kdtree_index.h.

◆ NodePtr

template<typename Distance >

typedef Node* rtflann::KDTreeIndex< Distance >::NodePtr

private

Definition at line 175 of file kdtree_index.h.

Member Enumeration Documentation

◆ anonymous enum

template<typename Distance >

anonymous enum

private

Enumerator

SAMPLE_MEAN

To improve efficiency, only SAMPLE_MEAN random values are used to compute the mean and variance at each level when building a tree. A value of 100 seems to perform as well as using all values.

RAND_DIM

Top random dimensions to consider

When creating random trees, the dimension on which to subdivide is selected at random from among the top RAND_DIM dimensions with the highest variance. A value of 5 works well.

Definition at line 1124 of file kdtree_index.h.

Constructor & Destructor Documentation

◆ KDTreeIndex() [1/3]

template<typename Distance >

rtflann::KDTreeIndex< Distance >::KDTreeIndex	(	const IndexParams &	params = `KDTreeIndexParams()`,
		Distance	d = `Distance()`
	)

inline

KDTree constructor

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm

Definition at line 188 of file kdtree_index.h.

◆ KDTreeIndex() [2/3]

template<typename Distance >

rtflann::KDTreeIndex< Distance >::KDTreeIndex	(	const Matrix< ElementType > &	dataset,
		const IndexParams &	params = `KDTreeIndexParams()`,
		Distance	d = `Distance()`
	)

inline

KDTree constructor

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm

Definition at line 202 of file kdtree_index.h.

◆ KDTreeIndex() [3/3]

template<typename Distance >

rtflann::KDTreeIndex< Distance >::KDTreeIndex ( const KDTreeIndex< Distance > & other )

inline

Definition at line 210 of file kdtree_index.h.

◆ ~KDTreeIndex()

template<typename Distance >

virtual rtflann::KDTreeIndex< Distance >::~KDTreeIndex ( )

inlinevirtual

Standard destructor

Definition at line 228 of file kdtree_index.h.

Member Function Documentation

◆ addPoints()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::addPoints	(	const Matrix< ElementType > &	points,
		float	rebuild_threshold = `2`
	)

inlinevirtual

Incrementally add points to the index.

Parameters

points	Matrix with points to be added
rebuild_threshold

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 240 of file kdtree_index.h.

◆ addPointToTree()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::addPointToTree	(	NodePtr	node,
		int	ind
	)

inlineprivate

Definition at line 1067 of file kdtree_index.h.

◆ buildIndex() [1/2]

template<typename Distance >

virtual void rtflann::NNIndex< Distance >::buildIndex

inline

Builds the index

Definition at line 153 of file nn_index.h.

◆ buildIndex() [2/2]

template<typename Distance >

virtual void rtflann::NNIndex< Distance >::buildIndex

inline

Builds the index using the specified dataset

Parameters

dataset the dataset to use

Definition at line 169 of file nn_index.h.

◆ buildIndexImpl()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::buildIndexImpl ( )

inlineprotectedvirtual

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 694 of file kdtree_index.h.

◆ clone()

template<typename Distance >

BaseClass* rtflann::KDTreeIndex< Distance >::clone ( ) const

inlinevirtual

Implements rtflann::NNIndex< Distance >.

Definition at line 233 of file kdtree_index.h.

◆ copyTree()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::copyTree	(	NodePtr &	dst,
		const NodePtr &	src
	)

inlineprivate

Definition at line 730 of file kdtree_index.h.

◆ divideTree()

template<typename Distance >

NodePtr rtflann::KDTreeIndex< Distance >::divideTree	(	int *	ind,
		int	count
	)

inlineprivate

Create a tree node that subdivides the list of vecs from vind[first] to vind[last]. The routine is called recursively on each sublist. Place a pointer to this new tree node in the location pTree.

Params: pTree = the new node to create first = index of the first vector last = index of the last vector

Definition at line 755 of file kdtree_index.h.

◆ findNeighbors()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::findNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		const SearchParams &	searchParams
	)		const

inlinevirtual

Find set of nearest neighbors to vec. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors maxCheck = the maximum number of restarts (in a best-bin-first manner)

Implements rtflann::NNIndex< Distance >.

Definition at line 323 of file kdtree_index.h.

◆ freeIndex()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::freeIndex ( )

inlineprotectedvirtual

Implements rtflann::NNIndex< Distance >.

Definition at line 718 of file kdtree_index.h.

◆ getExactNeighbors()

template<typename Distance >

template<bool with_removed>

void rtflann::KDTreeIndex< Distance >::getExactNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		float	epsError
	)		const

inlineprivate

Performs an exact nearest neighbor search. The exact search performs a full traversal of the tree.

Definition at line 901 of file kdtree_index.h.

◆ getNeighbors()

template<typename Distance >

template<bool with_removed>

void rtflann::KDTreeIndex< Distance >::getNeighbors	(	ResultSet< DistanceType > &	result,
		const ElementType *	vec,
		int	maxCheck,
		float	epsError
	)		const

inlineprivate

Performs the approximate nearest-neighbor search. The search is approximate because the tree traversal is abandoned after a given number of descends in the tree.

Definition at line 919 of file kdtree_index.h.

◆ getType()

template<typename Distance >

flann_algorithm_t rtflann::KDTreeIndex< Distance >::getType ( ) const

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 259 of file kdtree_index.h.

◆ loadIndex()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::loadIndex ( FILE * stream )

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 298 of file kdtree_index.h.

◆ meanSplit()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::meanSplit	(	int *	ind,
		int	count,
		int &	index,
		int &	cutfeat,
		DistanceType &	cutval
	)

inlineprivate

Choose which feature to use in order to subdivide this set of vectors. Make a random choice among those with the highest variance, and use its variance as the threshold value.

Definition at line 786 of file kdtree_index.h.

◆ operator=()

template<typename Distance >

KDTreeIndex& rtflann::KDTreeIndex< Distance >::operator= ( KDTreeIndex< Distance > other )

inline

Definition at line 219 of file kdtree_index.h.

◆ planeSplit()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::planeSplit	(	int *	ind,
		int	count,
		int	cutfeat,
		DistanceType	cutval,
		int &	lim1,
		int &	lim2
	)

inlineprivate

Subdivide the list of points by a plane perpendicular on axe corresponding to the 'cutfeat' dimension at 'cutval' position.

On return: dataset[ind[0..lim1-1]][cutfeat]<cutval dataset[ind[lim1..lim2-1]][cutfeat]==cutval dataset[ind[lim2..count]][cutfeat]>cutval

Definition at line 874 of file kdtree_index.h.

◆ saveIndex()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::saveIndex ( FILE * stream )

inlinevirtual

Implements rtflann::IndexBase.

Definition at line 291 of file kdtree_index.h.

◆ searchLevel()

template<typename Distance >

template<bool with_removed>

void rtflann::KDTreeIndex< Distance >::searchLevel	(	ResultSet< DistanceType > &	result_set,
		const ElementType *	vec,
		NodePtr	node,
		DistanceType	mindist,
		int &	checkCount,
		int	maxCheck,
		float	epsError,
		Heap< BranchSt > *	heap,
		DynamicBitset &	checked
	)		const

inlineprivate

Search starting from a given node of the tree. Based on any mismatches at higher levels, all exemplars below this level must have a distance of at least "mindistsq".

Definition at line 977 of file kdtree_index.h.

◆ searchLevelExact()

template<typename Distance >

template<bool with_removed>

void rtflann::KDTreeIndex< Distance >::searchLevelExact	(	ResultSet< DistanceType > &	result_set,
		const ElementType *	vec,
		const NodePtr	node,
		DistanceType	mindist,
		const float	epsError
	)		const

inlineprivate

Performs an exact search in the tree starting from a node.

Definition at line 1029 of file kdtree_index.h.

◆ selectDivision()

template<typename Distance >

int rtflann::KDTreeIndex< Distance >::selectDivision ( DistanceType * v )

inlineprivate

Select the top RAND_DIM largest values from v and return the index of one of these selected at random.

Definition at line 836 of file kdtree_index.h.

◆ serialize()

template<typename Distance >

template<typename Archive >

void rtflann::KDTreeIndex< Distance >::serialize ( Archive & ar )

inline

Definition at line 266 of file kdtree_index.h.

◆ swap()

template<typename Distance >

void rtflann::KDTreeIndex< Distance >::swap ( KDTreeIndex< Distance > & other )

inlineprivate

Definition at line 1114 of file kdtree_index.h.

◆ usedMemory()

template<typename Distance >

int rtflann::KDTreeIndex< Distance >::usedMemory ( ) const

inlinevirtual

Computes the inde memory usage Returns: memory used by the index

Implements rtflann::IndexBase.

Definition at line 309 of file kdtree_index.h.

Member Data Documentation

◆ mean_

template<typename Distance >

DistanceType* rtflann::KDTreeIndex< Distance >::mean_

private

Definition at line 1148 of file kdtree_index.h.

◆ pool_

template<typename Distance >

PooledAllocator rtflann::KDTreeIndex< Distance >::pool_

private

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

Definition at line 1163 of file kdtree_index.h.

◆ tree_roots_

template<typename Distance >

std::vector<NodePtr> rtflann::KDTreeIndex< Distance >::tree_roots_

private

Array of k-d trees used to find neighbours.

Definition at line 1154 of file kdtree_index.h.

◆ trees_

template<typename Distance >

int rtflann::KDTreeIndex< Distance >::trees_

private

Number of randomized trees that are used

Definition at line 1146 of file kdtree_index.h.

◆ var_

template<typename Distance >

DistanceType* rtflann::KDTreeIndex< Distance >::var_

private

Definition at line 1149 of file kdtree_index.h.

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

kdtree_index.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<typename Distance> class rtflann::KDTreeIndex< Distance >

Member Typedef Documentation

◆ BaseClass

◆ Branch

◆ BranchSt

◆ DistanceType

◆ ElementType

◆ needs_kdtree_distance

◆ NodePtr

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ KDTreeIndex() [1/3]

◆ KDTreeIndex() [2/3]

◆ KDTreeIndex() [3/3]

◆ ~KDTreeIndex()

Member Function Documentation

◆ addPoints()

◆ addPointToTree()

◆ buildIndex() [1/2]

◆ buildIndex() [2/2]

◆ buildIndexImpl()

◆ clone()

◆ copyTree()

◆ divideTree()

◆ findNeighbors()

◆ freeIndex()

◆ getExactNeighbors()

◆ getNeighbors()

◆ getType()

◆ loadIndex()

◆ meanSplit()

◆ operator=()

◆ planeSplit()

◆ saveIndex()

◆ searchLevel()

◆ searchLevelExact()

◆ selectDivision()

◆ serialize()

◆ swap()

◆ usedMemory()

Member Data Documentation

◆ mean_

◆ pool_

◆ tree_roots_

◆ trees_

◆ var_

template<typename Distance>
class rtflann::KDTreeIndex< Distance >