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

vector<Node> cv::KDTree::nodes

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

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:

• /home/grier/opencv/opencv/modules/core/include/opencv2/core/core.hpp