kdtree.h File Reference

#include "generic.h"
#include "mathop.h"

Data Structures
struct	_VlKDForestNeighbor
	Neighbor of a query point. More...
struct	_VlKDForest
	KDForest object. More...
Typedefs
typedef enum _VlKDTreeThresholdingMethod	VlKDTreeThresholdingMethod
	Thresholding method.
typedef struct _VlKDForestNeighbor	VlKDForestNeighbor
	Neighbor of a query point.
typedef struct _VlKDForest	VlKDForest
	KDForest object.
Enumerations
enum	_VlKDTreeThresholdingMethod
	Thresholding method.
Functions
Creatind and disposing

VlKDForest *	vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees)
	Create new KDForest object.
void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object.
Building and querying

void	vl_kdforest_build (VlKDForest self, vl_size numData, void const data)
	Build KDTree from data.
vl_size	vl_kdforest_query (VlKDForest self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query operation.
Retrieving and setting parameters

vl_size	vl_kdforest_get_depth_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the detph of a given tree.
vl_size	vl_kdforest_get_num_nodes_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the number of nodes of a given tree.
vl_size	vl_kdforest_get_num_trees (VlKDForest const *self)
	Get the number of trees in the forest.
vl_size	vl_kdforest_get_data_dimension (VlKDForest const *self)
	Get the dimension of the data.
vl_type	vl_kdforest_get_data_type (VlKDForest const *self)
	Get the data type.
void	vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
	Set the maximum number of comparisons for a search.
vl_size	vl_kdforest_get_max_num_comparisons (VlKDForest *self)
	Get the maximum number of comparisons for a search.
void	vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
	Set the thresholding method.
VlKDTreeThresholdingMethod	vl_kdforest_get_thresholding_method (VlKDForest const *self)
	Get the thresholding method.

Detailed Description

VlKDTree implements a KD-tree object data structure useful to index moderately dimensional vector spaces. It can be used to quickly match two groups of feature descriptors.

Overview

To create a VlKDForest object use vl_kdforest_new specifying the dimensionality of the data and the number of trees in the forest. With one tree only, the algorithm is analogous to [1] (best-bin KDTree). Multiple trees correspond to the randomized KDTree forest as in [2,3].

To let the KD-tree index some data use vl_kdforest_build. Note that for efficiency KD-tree does not copy the data but retains a pointer to it. Therefore the data must exist (and not change) until the KD-tree is deleted. To delete the KD-tree object, use vl_kdforest_delete.

To find the N nearest neighbors to a query point use vl_kdforest_query. To set a maximum number of comparisons per query and calculate approximate nearest neighbors use vl_kdforest_set_max_num_comparisons.

Technical details

See also:: References

VlKDTree implements the best-bin-first kd-tree of [1].

Construction. Given a set of points $x_1,\dots,x_n \in \mathbb{R}^d$ , the algorithm recursively partitions the d dimensional Euclidean space $\mathbb{R}^d$ into (hyper-) rectangles.

Partitions are organized into a binary tree with the root corresponding to the whole space $\mathbb{R}^d$ . The algorithm refines each partition by dividing it into two halves by thresholding along a given dimension. Both the splitting dimension and the threshold are determined as a statistic of the data points contained in the partition. The splitting dimension is the one which has largest sample variance and the splitting threshold is either the sample mean or the median. Leaves are atomic partitions and they contain a list of zero or more data points (typically one).

Querying. Querying amounts to finding the N data points closer to a given query point $x_q \in \mathbb{R}^d$ . This is done by branch-and-bound. A search state is an active partition (initially the root) and it is weighed by the lower bound on the distance of any point in the partition and the query point. Such a lower bound is trivial to compute because partitions are hyper-rectangles.

References

[1] J. S. Beis and D. G. Lowe. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Proc. CVPR, 1997.

[2] C. Silpa-Anan and R. Hartley. Optimised KD-trees for fast image descriptor matching. In Proc. CVPR, 2008.

[3] M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithmic configuration. In Proc. VISAPP, 2009.

Author:
Andrea Vedaldi

Definition in file kdtree.h.

Function Documentation

void vl_kdforest_build	(	VlKDForest *	self,
		vl_size	numData,
		void const *	data
	)

------------------------------------------------------------------

Parameters:

	self	KDTree object
	numData	number of data points.
	data	pointer to the data.

The function builds the KDTree by processing the data data. For efficiency, KDTree does not copy the data, but retains a pointer to it. Therefore the data must survive (and not change) until the KDTree is deleted.

Definition at line 372 of file kdtree.c.

References vl_kdtree_build_recursively(), vl_kdtree_node_new(), and vl_malloc().

void vl_kdforest_delete ( VlKDForest * self )

------------------------------------------------------------------

Parameters:

self

KDForest object to delete

See also:: vl_kdforest_new

Definition at line 343 of file kdtree.c.

References vl_free().

vl_size vl_kdforest_get_data_dimension ( VlKDForest const * self ) [inline]

------------------------------------------------------------------

Parameters:

self

KDForest object.

Returns:: dimension of the data.

Definition at line 257 of file kdtree.h.

vl_type vl_kdforest_get_data_type ( VlKDForest const * self ) [inline]

------------------------------------------------------------------

Parameters:

self

KDForest object.

Returns:: data type (one of VL_TYPE_FLOAT, VL_TYPE_DOUBLE).

Definition at line 269 of file kdtree.h.

vl_size vl_kdforest_get_depth_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)			`[inline]`

------------------------------------------------------------------

Parameters:

	self	KDForest object.
	treeIndex	index of the tree.

Returns:: number of trees.

Definition at line 168 of file kdtree.h.

vl_size vl_kdforest_get_max_num_comparisons ( VlKDForest * self ) [inline]

------------------------------------------------------------------

Parameters:

self

KDForest object.

Returns:: maximum number of leaves.

See also:: vl_kdforest_set_max_num_comparisons.

Definition at line 215 of file kdtree.h.

vl_size vl_kdforest_get_num_nodes_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)			`[inline]`

------------------------------------------------------------------

Parameters:

	self	KDForest object.
	treeIndex	index of the tree.

Returns:: number of trees.

Definition at line 154 of file kdtree.h.

vl_size vl_kdforest_get_num_trees ( VlKDForest const * self ) [inline]

------------------------------------------------------------------

Parameters:

self

KDForest object.

Returns:: number of trees.

Definition at line 182 of file kdtree.h.

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method ( VlKDForest const * self ) [inline]

------------------------------------------------------------------

Parameters:

self

KDForest object.

Returns:: thresholding method.

See also:: vl_kdforest_set_thresholding_method

Definition at line 245 of file kdtree.h.

VlKDForest* vl_kdforest_new	(	vl_type	dataType,
		vl_size	dimension,
		vl_size	numTrees
	)

------------------------------------------------------------------

Parameters:

	dataType	type of data (VL_TYPE_FLOAT or VL_TYPE_DOUBLE)
	dimension	data dimensionality.
	numTrees	number of trees in the forest.

Returns:: new KDForest.

Definition at line 293 of file kdtree.c.

References vl_get_rand(), vl_get_vector_comparison_function_d(), vl_get_vector_comparison_function_f(), vl_malloc(), VL_TYPE_DOUBLE, VL_TYPE_FLOAT, and VlDistanceL2.

vl_size vl_kdforest_query	(	VlKDForest *	self,
		VlKDForestNeighbor *	neighbors,
		vl_size	numNeighbors,
		void const *	query
	)

------------------------------------------------------------------

Parameters:

	self	KDTree object instance.
	neighbors	list of nearest neighbors found (output).
	numNeighbors	number of nearest neighbors to find.
	query	query point.

Returns:: number of tree leaves visited.

A neighbor is represented by an instance of the structure VlKDForestNeighbor. Each entry contains the index of the neighbor (this is an index into the KDTree data) and its distance to the query point. Neighbors are sorted by increasing distance.

Definition at line 589 of file kdtree.c.

References _VlKDForestNeighbor::distance, _VlKDForestNeighbor::index, vl_calloc(), vl_free(), VL_INFINITY_F, vl_kdforest_query_recursively(), vl_kdtree_calc_bounds_recursively(), vl_malloc(), and VL_NAN_F.

void vl_kdforest_set_max_num_comparisons	(	VlKDForest *	self,
		vl_size	n
	)			`[inline]`

------------------------------------------------------------------

Parameters:

	self	KDForest object.
	n	maximum number of leaves.

This function sets the maximum number of comparisons for a nearest neighbor search. Setting it to 0 means unbounded comparisons.

See also:: vl_kdforest_query, vl_kdforest_get_max_num_comparisons.

Definition at line 200 of file kdtree.h.

void vl_kdforest_set_thresholding_method	(	VlKDForest *	self,
		VlKDTreeThresholdingMethod	method
	)			`[inline]`

------------------------------------------------------------------

Parameters:

	self	KDForest object.
	method	one of VlKDTreeThresholdingMethod.

See also:: vl_kdforest_get_thresholding_method

Definition at line 229 of file kdtree.h.

VLFeat.org

kdtree.h File Reference

Data Structures

Typedefs

Enumerations

Functions

Detailed Description

Overview

Technical details

References

Function Documentation