cv::KDTree Class Reference

#include <core.hpp>

List of all members.

Classes

struct  Node

Public Member Functions

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

Public Attributes

CV_PROP vector< int > labels
 the parallel array of labels.
CV_PROP int maxDepth
 maximum depth of the search tree. Do not modify it
vector< Nodenodes
 all the tree nodes
CV_PROP_RW int 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
CV_PROP Mat points
 all the points. It can be a reordered copy of the input vector set or the original vector set.

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 ( const Mat _points,
bool  copyAndReorderPoints = false 
)

the full constructor that builds the search tree

CV_WRAP cv::KDTree::KDTree ( const Mat _points,
const Mat _labels,
bool  copyAndReorderPoints = false 
)

the full constructor that builds the search tree


Member Function Documentation

CV_WRAP void cv::KDTree::build ( const Mat _points,
const Mat _labels,
bool  copyAndReorderPoints = false 
)

builds the search tree

CV_WRAP void cv::KDTree::build ( const Mat _points,
bool  copyAndReorderPoints = false 
)

builds the search tree

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

returns the search space dimensionality

CV_WRAP int cv::KDTree::findNearest ( const vector< float > &  vec,
int  K,
int  Emax,
CV_OUT vector< int > *  neighborsIdx,
CV_OUT Mat neighbors = 0,
CV_OUT vector< float > *  dist = 0,
CV_OUT vector< int > *  labels = 0 
) const
int cv::KDTree::findNearest ( const float *  vec,
int  K,
int  Emax,
vector< int > *  neighborsIdx,
Mat neighbors = 0,
vector< float > *  dist = 0,
vector< int > *  labels = 0 
) const

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

int cv::KDTree::findNearest ( const float *  vec,
int  K,
int  Emax,
int *  neighborsIdx,
Mat neighbors = 0,
float *  dist = 0,
int *  labels = 0 
) const

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

CV_WRAP void cv::KDTree::findOrthoRange ( const vector< float > &  minBounds,
const vector< float > &  maxBounds,
CV_OUT vector< int > *  neighborsIdx,
CV_OUT Mat neighbors = 0,
CV_OUT vector< int > *  labels = 0 
) const
void cv::KDTree::findOrthoRange ( const float *  minBounds,
const float *  maxBounds,
vector< int > *  neighborsIdx,
Mat neighbors = 0,
vector< int > *  labels = 0 
) const

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

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

return a vector with the specified index

CV_WRAP void cv::KDTree::getPoints ( const vector< int > &  idxs,
Mat pts,
CV_OUT vector< int > *  labels = 0 
) const

returns vectors with the specified indices

void cv::KDTree::getPoints ( const int *  idx,
size_t  nidx,
Mat pts,
vector< int > *  labels = 0 
) const

returns vectors with the specified indices


Member Data Documentation

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

all the tree nodes

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

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


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Generated on Thu Dec 23 11:40:55 2010 for opencv by  doxygen 1.6.3