Classes | Public Member Functions | Public Attributes | List of all members
cv::KDTree Class Reference

Fast Nearest Neighbor Search Class. More...

#include <core.hpp>

Classes

struct  Node
 The node of the search tree. More...
 

Public Member Functions

CV_WRAP KDTree ()
 the default constructor More...
 
CV_WRAP KDTree (InputArray points, bool copyAndReorderPoints=false)
 the full constructor that builds the search tree More...
 
CV_WRAP KDTree (InputArray points, InputArray _labels, bool copyAndReorderPoints=false)
 the full constructor that builds the search tree More...
 
CV_WRAP void build (InputArray points, bool copyAndReorderPoints=false)
 builds the search tree More...
 
CV_WRAP void build (InputArray points, InputArray labels, bool copyAndReorderPoints=false)
 builds the search tree More...
 
CV_WRAP int findNearest (InputArray vec, int K, int Emax, OutputArray neighborsIdx, OutputArray neighbors=noArray(), OutputArray dist=noArray(), OutputArray labels=noArray()) const
 finds the K nearest neighbors of "vec" while looking at Emax (at most) leaves More...
 
CV_WRAP void findOrthoRange (InputArray minBounds, InputArray maxBounds, OutputArray neighborsIdx, OutputArray neighbors=noArray(), OutputArray labels=noArray()) const
 finds all the points from the initial set that belong to the specified box More...
 
CV_WRAP void getPoints (InputArray idx, OutputArray pts, OutputArray labels=noArray()) const
 returns vectors with the specified indices More...
 
const float * getPoint (int ptidx, int *label=0) const
 return a vector with the specified index More...
 
CV_WRAP int dims () const
 returns the search space dimensionality More...
 

Public Attributes

vector< Nodenodes
 all the tree nodes More...
 
CV_PROP Mat points
 all the points. More...
 
CV_PROP vector< intlabels
 the parallel array of labels. More...
 
CV_PROP int maxDepth
 maximum depth of the search tree. More...
 
CV_PROP_RW int normType
 type of the distance (cv::NORM_L1 or cv::NORM_L2) used for search. More...
 

Detailed Description

Fast Nearest Neighbor Search Class.

The class implements D. Lowe BBF (Best-Bin-First) algorithm for the last approximate (or accurate) nearest neighbor search in multi-dimensional spaces.

First, a set of vectors is passed to KDTree::KDTree() constructor or KDTree::build() method, where it is reordered.

Then arbitrary vectors can be passed to KDTree::findNearest() methods, which find the K nearest neighbors among the vectors from the initial set. The user can balance between the speed and accuracy of the search by varying Emax parameter, which is the number of leaves that the algorithm checks. The larger parameter values yield more accurate results at the expense of lower processing speed.

KDTree T(points, false);
const int K = 3, Emax = INT_MAX;
int idx[K];
float dist[K];
T.findNearest(query_vec, K, Emax, idx, 0, dist);
CV_Assert(dist[0] <= dist[1] && dist[1] <= dist[2]);

Constructor & Destructor Documentation

CV_WRAP cv::KDTree::KDTree ( )

the default constructor

CV_WRAP cv::KDTree::KDTree ( InputArray  points,
bool  copyAndReorderPoints = false 
)

the full constructor that builds the search tree

CV_WRAP cv::KDTree::KDTree ( InputArray  points,
InputArray  _labels,
bool  copyAndReorderPoints = false 
)

the full constructor that builds the search tree

Member Function Documentation

CV_WRAP void cv::KDTree::build ( InputArray  points,
bool  copyAndReorderPoints = false 
)

builds the search tree

CV_WRAP void cv::KDTree::build ( InputArray  points,
InputArray  labels,
bool  copyAndReorderPoints = false 
)

builds the search tree

CV_WRAP int cv::KDTree::findNearest ( InputArray  vec,
int  K,
int  Emax,
OutputArray  neighborsIdx,
OutputArray  neighbors = noArray(),
OutputArray  dist = noArray(),
OutputArray  labels = noArray() 
) const

finds the K nearest neighbors of "vec" while looking at Emax (at most) leaves

CV_WRAP void cv::KDTree::findOrthoRange ( InputArray  minBounds,
InputArray  maxBounds,
OutputArray  neighborsIdx,
OutputArray  neighbors = noArray(),
OutputArray  labels = noArray() 
) const

finds all the points from the initial set that belong to the specified box

CV_WRAP void cv::KDTree::getPoints ( InputArray  idx,
OutputArray  pts,
OutputArray  labels = noArray() 
) const

returns vectors with the specified indices

const float* cv::KDTree::getPoint ( int  ptidx,
int label = 0 
) const

return a vector with the specified index

CV_WRAP int cv::KDTree::dims ( ) const

returns the search space dimensionality

Member Data Documentation

vector<Node> cv::KDTree::nodes

all the tree nodes

CV_PROP Mat cv::KDTree::points

all the points.

It can be a reordered copy of the input vector set or the original vector set.

CV_PROP vector<int> cv::KDTree::labels

the parallel array of labels.

CV_PROP int cv::KDTree::maxDepth

maximum depth of the search tree.

Do not modify it

CV_PROP_RW int cv::KDTree::normType

type of the distance (cv::NORM_L1 or cv::NORM_L2) used for search.

Initially set to cv::NORM_L2, but you can modify it


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