#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 Member Functions
void	addPoints (const Matrix< ElementType > &points, float rebuild_threshold=2)
	Incrementally add points to the index.
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 Matrix< ElementType > &dataset, const IndexParams &params=KDTreeIndexParams(), Distance d=Distance())
	KDTreeIndex (const KDTreeIndex &other)
void	loadIndex (FILE *stream)
KDTreeIndex &	operator= (KDTreeIndex other)
void	saveIndex (FILE *stream)
template<typename Archive >
void	serialize (Archive &ar)
int	usedMemory () const
virtual	~KDTreeIndex ()
Protected Member Functions
void	buildIndexImpl ()
void	freeIndex ()
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_

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 72 of file kdtree_index.h.

Member Typedef Documentation

template<typename Distance>

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

Definition at line 78 of file kdtree_index.h.

template<typename Distance>

typedef BranchSt* rtflann::KDTreeIndex< Distance >::Branch [private]

Definition at line 351 of file kdtree_index.h.

template<typename Distance>

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

Definition at line 350 of file kdtree_index.h.

template<typename Distance>

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

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 76 of file kdtree_index.h.

template<typename Distance>

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

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 75 of file kdtree_index.h.

template<typename Distance>

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

Definition at line 80 of file kdtree_index.h.

template<typename Distance>

typedef Node* rtflann::KDTreeIndex< Distance >::NodePtr [private]

Definition at line 349 of file kdtree_index.h.

Member Enumeration Documentation

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 719 of file kdtree_index.h.

Constructor & Destructor Documentation

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 90 of file kdtree_index.h.

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 104 of file kdtree_index.h.

template<typename Distance>

rtflann::KDTreeIndex< Distance >::KDTreeIndex ( const KDTreeIndex< Distance > & other ) [inline]

Definition at line 112 of file kdtree_index.h.

template<typename Distance>

virtual rtflann::KDTreeIndex< Distance >::~KDTreeIndex ( ) [inline, virtual]

Standard destructor

Definition at line 130 of file kdtree_index.h.

Member Function Documentation

template<typename Distance>

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

Incrementally add points to the index.

Parameters:

points	Matrix with points to be added
rebuild_threshold

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 142 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::addPointToTree	(	NodePtr	node,
		int	ind
	)		`[inline, private]`

Definition at line 662 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::buildIndexImpl ( ) [inline, protected, virtual]

Builds the index

Implements rtflann::NNIndex< Distance >.

Definition at line 253 of file kdtree_index.h.

template<typename Distance>

BaseClass* rtflann::KDTreeIndex< Distance >::clone ( ) const [inline, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 135 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::copyTree	(	NodePtr &	dst,
		const NodePtr &	src
	)		`[inline, private]`

Definition at line 354 of file kdtree_index.h.

template<typename Distance>

NodePtr rtflann::KDTreeIndex< Distance >::divideTree	(	int *	ind,
		int	count
	)		`[inline, private]`

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 379 of file kdtree_index.h.

template<typename Distance>

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

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 225 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::freeIndex ( ) [inline, protected, virtual]

Implements rtflann::NNIndex< Distance >.

Definition at line 275 of file kdtree_index.h.

template<typename Distance>

template<bool with_removed>

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

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

Definition at line 525 of file kdtree_index.h.

template<typename Distance>

template<bool with_removed>

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

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 543 of file kdtree_index.h.

template<typename Distance>

flann_algorithm_t rtflann::KDTreeIndex< Distance >::getType ( ) const [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 161 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::loadIndex ( FILE * stream ) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 200 of file kdtree_index.h.

template<typename Distance>

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

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 410 of file kdtree_index.h.

template<typename Distance>

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

Definition at line 121 of file kdtree_index.h.

template<typename Distance>

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

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 498 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::saveIndex ( FILE * stream ) [inline, virtual]

Implements rtflann::IndexBase.

Definition at line 193 of file kdtree_index.h.

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 `[inline, private]`

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 572 of file kdtree_index.h.

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 `[inline, private]`

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

Definition at line 624 of file kdtree_index.h.

template<typename Distance>

int rtflann::KDTreeIndex< Distance >::selectDivision ( DistanceType * v ) [inline, private]

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

Definition at line 460 of file kdtree_index.h.

template<typename Distance>

template<typename Archive >

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

Reimplemented from rtflann::NNIndex< Distance >.

Definition at line 168 of file kdtree_index.h.

template<typename Distance>

void rtflann::KDTreeIndex< Distance >::swap ( KDTreeIndex< Distance > & other ) [inline, private]

Definition at line 709 of file kdtree_index.h.

template<typename Distance>

int rtflann::KDTreeIndex< Distance >::usedMemory ( ) const [inline, virtual]

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

Implements rtflann::IndexBase.

Definition at line 211 of file kdtree_index.h.

Member Data Documentation

template<typename Distance>

DistanceType* rtflann::KDTreeIndex< Distance >::mean_ [private]

Definition at line 743 of file kdtree_index.h.

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 758 of file kdtree_index.h.

template<typename Distance>

std::vector<NodePtr> rtflann::KDTreeIndex< Distance >::tree_roots_ [private]

Array of k-d trees used to find neighbours.

Definition at line 749 of file kdtree_index.h.

template<typename Distance>

int rtflann::KDTreeIndex< Distance >::trees_ [private]

Number of randomized trees that are used

Definition at line 741 of file kdtree_index.h.

template<typename Distance>

DistanceType* rtflann::KDTreeIndex< Distance >::var_ [private]

Definition at line 744 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

Detailed Description

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

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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