#include <kdtree_index.h>
Classes | |
struct | Node |
Public Types | |
typedef NNIndex< Distance > | BaseClass |
typedef Distance::ResultType | DistanceType |
typedef Distance::ElementType | ElementType |
typedef bool | needs_kdtree_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 ¶ms=KDTreeIndexParams(), Distance d=Distance()) | |
KDTreeIndex (const KDTreeIndex &other) | |
KDTreeIndex (const Matrix< ElementType > &dataset, const IndexParams ¶ms=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 () |
![]() | |
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 ¶ms) 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 ¶ms) 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 ¶ms) const |
Perform k-nearest neighbor search. More... | |
NNIndex (const IndexParams ¶ms, 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 ¶ms) const |
virtual int | radiusSearch (const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams ¶ms) 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 ¶ms) 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 ¶ms) 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 () |
![]() | |
virtual | ~IndexBase () |
Protected Member Functions | |
void | buildIndexImpl () |
void | freeIndex () |
![]() | |
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 | |
![]() | |
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_ |
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.
typedef NNIndex<Distance> rtflann::KDTreeIndex< Distance >::BaseClass |
Definition at line 107 of file kdtree_index.h.
|
private |
Definition at line 177 of file kdtree_index.h.
|
private |
Definition at line 176 of file kdtree_index.h.
typedef Distance::ResultType rtflann::KDTreeIndex< Distance >::DistanceType |
Definition at line 105 of file kdtree_index.h.
typedef Distance::ElementType rtflann::KDTreeIndex< Distance >::ElementType |
Definition at line 104 of file kdtree_index.h.
typedef bool rtflann::KDTreeIndex< Distance >::needs_kdtree_distance |
Definition at line 109 of file kdtree_index.h.
|
private |
Definition at line 175 of file kdtree_index.h.
|
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.
|
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.
|
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.
|
inline |
Definition at line 210 of file kdtree_index.h.
|
inlinevirtual |
Standard destructor
Definition at line 228 of file kdtree_index.h.
|
inlinevirtual |
Incrementally add points to the index.
points | Matrix with points to be added |
rebuild_threshold |
Reimplemented from rtflann::NNIndex< Distance >.
Definition at line 240 of file kdtree_index.h.
|
inlineprivate |
Definition at line 1067 of file kdtree_index.h.
|
inline |
Builds the index
Definition at line 153 of file nn_index.h.
|
inline |
Builds the index using the specified dataset
dataset | the dataset to use |
Definition at line 169 of file nn_index.h.
|
inlineprotectedvirtual |
Builds the index
Implements rtflann::NNIndex< Distance >.
Definition at line 694 of file kdtree_index.h.
|
inlinevirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 233 of file kdtree_index.h.
|
inlineprivate |
Definition at line 730 of file kdtree_index.h.
|
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.
|
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.
|
inlineprotectedvirtual |
Implements rtflann::NNIndex< Distance >.
Definition at line 718 of file kdtree_index.h.
|
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.
|
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.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 259 of file kdtree_index.h.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 298 of file kdtree_index.h.
|
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.
|
inline |
Definition at line 219 of file kdtree_index.h.
|
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.
|
inlinevirtual |
Implements rtflann::IndexBase.
Definition at line 291 of file kdtree_index.h.
|
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.
|
inlineprivate |
Performs an exact search in the tree starting from a node.
Definition at line 1029 of file kdtree_index.h.
|
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.
|
inline |
Definition at line 266 of file kdtree_index.h.
|
inlineprivate |
Definition at line 1114 of file kdtree_index.h.
|
inlinevirtual |
Computes the inde memory usage Returns: memory used by the index
Implements rtflann::IndexBase.
Definition at line 309 of file kdtree_index.h.
|
private |
Definition at line 1148 of file kdtree_index.h.
|
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.
|
private |
Array of k-d trees used to find neighbours.
Definition at line 1154 of file kdtree_index.h.
|
private |
Number of randomized trees that are used
Definition at line 1146 of file kdtree_index.h.
|
private |
Definition at line 1149 of file kdtree_index.h.