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< Node >	nodes
	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< int >	labels
	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

cv::KDTree::KDTree

(

)

the default constructor

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

the full constructor that builds the search tree

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

the full constructor that builds the search tree

Member Function Documentation

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

builds the search tree

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

builds the search tree

int cv::KDTree::dims

(

)

const

returns the search space dimensionality

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

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

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

return a vector with the specified index

void cv::KDTree::getPoints	(	InputArray	idx,
		OutputArray	pts,
		OutputArray	labels = noArray()
	)		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

vector<Node> cv::KDTree::nodes

all the tree nodes

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

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:

• core/core.hpp