cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE > Class Template Reference

#include <kdtree_index.h>

Inheritance diagram for cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >:

[legend]

List of all members.

Classes
struct	TreeSt
Public Member Functions
void	buildIndex ()
void	findNeighbors (ResultSet< ELEM_TYPE > &result, const ELEM_TYPE *vec, const SearchParams &searchParams)
const IndexParams *	getParameters () const
flann_algorithm_t	getType () const
	KDTreeIndex (const Matrix< ELEM_TYPE > &inputData, const KDTreeIndexParams &params=KDTreeIndexParams())
void	loadIndex (FILE *stream)
void	saveIndex (FILE *stream)
size_t	size () const
int	usedMemory () const
size_t	veclen () const
	~KDTreeIndex ()
Private Types
enum	{ SAMPLE_MEAN = 100, RAND_DIM = 5 }
typedef BranchSt *	Branch
typedef BranchStruct< Tree >	BranchSt
typedef TreeSt *	Tree
Private Member Functions
void	chooseDivision (Tree node, int first, int last)
Tree	divideTree (int first, int last)
void	getExactNeighbors (ResultSet< ELEM_TYPE > &result, const ELEM_TYPE *vec)
void	getNeighbors (ResultSet< ELEM_TYPE > &result, const ELEM_TYPE *vec, int maxCheck)
void	load_tree (FILE *stream, Tree &tree)
void	save_tree (FILE *stream, Tree tree)
void	searchLevel (ResultSet< ELEM_TYPE > &result, const ELEM_TYPE *vec, Tree node, float mindistsq, int &checkCount, int maxCheck, Heap< BranchSt > *heap, vector< bool > &checked)
void	searchLevelExact (ResultSet< ELEM_TYPE > &result, const ELEM_TYPE *vec, Tree node, float mindistsq)
int	selectDivision (DIST_TYPE *v)
void	subdivide (Tree node, int first, int last)
Private Attributes
const Matrix< ELEM_TYPE >	dataset
const IndexParams &	index_params
DIST_TYPE *	mean
int	numTrees
PooledAllocator	pool
size_t	size_
Tree *	trees
DIST_TYPE *	var
size_t	veclen_
int *	vind

---

Detailed Description

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>
class cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >

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

---

Member Typedef Documentation

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

typedef BranchSt* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::Branch [private]

Definition at line 155 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

typedef BranchStruct<Tree> cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::BranchSt [private]

Definition at line 154 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

typedef TreeSt* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::Tree [private]

Definition at line 148 of file kdtree_index.h.

---

Member Enumeration Documentation

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

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

---

Constructor & Destructor Documentation

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::KDTreeIndex	(	const Matrix< ELEM_TYPE > &	inputData,
		const KDTreeIndexParams &	params = KDTreeIndexParams()
	)			[inline]

KDTree constructor

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

Definition at line 182 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::~KDTreeIndex

(

)

[inline]

Standard destructor

Definition at line 214 of file kdtree_index.h.

---

Member Function Documentation

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::buildIndex

(

)

[inline, virtual]

Builds the index

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 228 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::chooseDivision	(	Tree	node,
		int	first,
		int	last
	)			[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 379 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

Tree cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::divideTree	(	int	first,
		int	last
	)			[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 356 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::findNeighbors	(	ResultSet< ELEM_TYPE > &	result,
		const ELEM_TYPE *	vec,
		const SearchParams &	searchParams
	)			[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 cvflann::NNIndex< ELEM_TYPE >.

Definition at line 303 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::getExactNeighbors	(	ResultSet< ELEM_TYPE > &	result,
		const ELEM_TYPE *	vec
	)			[inline, private]

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

Definition at line 484 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::getNeighbors	(	ResultSet< ELEM_TYPE > &	result,
		const ELEM_TYPE *	vec,
		int	maxCheck
	)			[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 502 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

const IndexParams* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::getParameters

(

)

const [inline, virtual]

Returns the parameters used for the index

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 314 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

flann_algorithm_t cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::getType

(

)

const [inline, virtual]

Algorithm name

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 170 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::load_tree	(	FILE *	stream,
		Tree &	tree
	)			[inline, private]

Definition at line 334 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::loadIndex

(

FILE *

stream

)

[inline, virtual]

Loads the index from a stream

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 253 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::save_tree	(	FILE *	stream,
		Tree	tree
	)			[inline, private]

Definition at line 322 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::saveIndex

(

FILE *

stream

)

[inline, virtual]

Saves the index to a stream

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 243 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::searchLevel	(	ResultSet< ELEM_TYPE > &	result,
		const ELEM_TYPE *	vec,
		Tree	node,
		float	mindistsq,
		int &	checkCount,
		int	maxCheck,
		Heap< BranchSt > *	heap,
		vector< bool > &	checked
	)			[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 532 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::searchLevelExact	(	ResultSet< ELEM_TYPE > &	result,
		const ELEM_TYPE *	vec,
		Tree	node,
		float	mindistsq
	)			[inline, private]

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

Definition at line 584 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

int cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::selectDivision

(

DIST_TYPE *

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

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

size_t cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::size

(

)

const [inline, virtual]

Returns size of index.

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 270 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

void cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::subdivide	(	Tree	node,
		int	first,
		int	last
	)			[inline, private]

Subdivide the list of exemplars using the feature and division value given in this node. Call divideTree recursively on each list.

Definition at line 450 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

int cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::usedMemory

(

)

const [inline, virtual]

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

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 288 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

size_t cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::veclen

(

)

const [inline, virtual]

Returns the length of an index feature.

Implements cvflann::NNIndex< ELEM_TYPE >.

Definition at line 278 of file kdtree_index.h.

---

Member Data Documentation

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

const Matrix<ELEM_TYPE> cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::dataset [private]

The dataset used by this index

Definition at line 112 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

const IndexParams& cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::index_params [private]

Definition at line 114 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

DIST_TYPE* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::mean [private]

Definition at line 120 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

int cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::numTrees [private]

Number of randomized trees that are used

Definition at line 101 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

PooledAllocator cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::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 164 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

size_t cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::size_ [private]

Definition at line 116 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

Tree* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::trees [private]

Array of k-d trees used to find neighbours.

Definition at line 153 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

DIST_TYPE* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::var [private]

Definition at line 121 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

size_t cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::veclen_ [private]

Definition at line 117 of file kdtree_index.h.

template<typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type>

int* cvflann::KDTreeIndex< ELEM_TYPE, DIST_TYPE >::vind [private]

Array of indices to vectors in the dataset.

Definition at line 106 of file kdtree_index.h.

---

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

• kdtree_index.h