OpenCV  2.4.13.4
Open Source Computer Vision
cv::KDTree Class Reference

#include <core.hpp>

Classes

struct  Node
 

Public Member Functions

 KDTree ()
 the default constructor More...
 
 KDTree (InputArray points, bool copyAndReorderPoints=false)
 the full constructor that builds the search tree More...
 
 KDTree (InputArray points, InputArray _labels, bool copyAndReorderPoints=false)
 the full constructor that builds the search tree More...
 
void build (InputArray points, bool copyAndReorderPoints=false)
 builds the search tree More...
 
void build (InputArray points, InputArray labels, bool copyAndReorderPoints=false)
 builds the search tree More...
 
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...
 
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...
 
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...
 
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. It can be a reordered copy of the input vector set or the original vector set. More...
 
CV_PROP vector< intlabels
 the parallel array of labels. More...
 
CV_PROP int maxDepth
 maximum depth of the search tree. Do not modify it More...
 
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 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

§ KDTree() [1/3]

cv::KDTree::KDTree ( )

the default constructor

§ KDTree() [2/3]

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

the full constructor that builds the search tree

§ KDTree() [3/3]

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

the full constructor that builds the search tree

Member Function Documentation

§ build() [1/2]

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

builds the search tree

§ build() [2/2]

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

builds the search tree

§ dims()

int cv::KDTree::dims ( ) const

returns the search space dimensionality

§ findNearest()

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

§ findOrthoRange()

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

§ getPoint()

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

return a vector with the specified index

§ getPoints()

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

returns vectors with the specified indices

Member Data Documentation

§ labels

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

the parallel array of labels.

§ maxDepth

CV_PROP int cv::KDTree::maxDepth

maximum depth of the search tree. Do not modify it

§ nodes

vector<Node> cv::KDTree::nodes

all the tree nodes

§ normType

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

§ points

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.


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