KD-tree - Definition. More...

#include "kdtree.h"
#include "generic.h"
#include "random.h"
#include "mathop.h"
#include <stdlib.h>
#include "heap-def.h"

Functions
static vl_uindex	vl_kdtree_node_new (VlKDTree *tree, vl_uindex parentIndex)
	Allocate a new node from the tree pool.
int	vl_kdtree_compare_index_entries (void const a, void const b)
	Compare KDTree index entries for sorting.
static void	vl_kdtree_build_recursively (VlKDForest forest, VlKDTree tree, vl_uindex nodeIndex, vl_uindex dataBegin, vl_uindex dataEnd, unsigned int depth)
	Build KDTree recursively.
VlKDForest *	vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees, VlVectorComparisonType distance)
	Create new KDForest object.
VlKDForestSearcher *	vl_kdforest_new_searcher (VlKDForest *kdforest)
	Create a KDForest searcher object, used for processing queries.
void	vl_kdforestsearcher_delete (VlKDForestSearcher *self)
	Delete object.
void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object.
static void	vl_kdtree_calc_bounds_recursively (VlKDTree tree, vl_uindex nodeIndex, double searchBounds)
	Compute tree bounds recursively.
void	vl_kdforest_build (VlKDForest self, vl_size numData, void const data)
	Build KDTree from data.
vl_uindex	vl_kdforest_query_recursively (VlKDForestSearcher searcher, VlKDTree tree, vl_uindex nodeIndex, VlKDForestNeighbor neighbors, vl_size numNeighbors, vl_size numAddedNeighbors, double dist, void const *query)
vl_size	vl_kdforest_query (VlKDForest self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
vl_size	vl_kdforestsearcher_query (VlKDForestSearcher self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
vl_size	vl_kdforest_query_with_array (VlKDForest self, vl_uint32 indexes, vl_size numNeighbors, vl_size numQueries, void distances, void const queries)
	Run multiple queries.
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_depth_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the detph of a given tree.
vl_size	vl_kdforest_get_num_trees (VlKDForest const *self)
	Get the number of trees in the forest.
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.
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.
VlKDForest *	vl_kdforestsearcher_get_forest (VlKDForestSearcher const *self)
	Get the forest linked to the searcher.

Detailed Description

Author:: Andrea Vedaldi, David Novotny

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.

void vl_kdforest_delete ( VlKDForest * self )

Parameters:

self	KDForest object to delete

See also:: vl_kdforest_new

vl_size vl_kdforest_get_data_dimension ( VlKDForest const * self )

Parameters:

self	KDForest object.

Returns:: dimension of the data.

vl_type vl_kdforest_get_data_type ( VlKDForest const * self )

Parameters:

self	KDForest object.

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

vl_size vl_kdforest_get_depth_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:: number of trees.

vl_size vl_kdforest_get_max_num_comparisons ( VlKDForest * self )

Parameters:

self	KDForest object.

Returns:: maximum number of leaves.

See also:: vl_kdforest_set_max_num_comparisons.

vl_size vl_kdforest_get_num_nodes_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:: number of trees.

vl_size vl_kdforest_get_num_trees ( VlKDForest const * self )

Parameters:

self	KDForest object.

Returns:: number of trees.

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method ( VlKDForest const * self )

Parameters:

self	KDForest object.

Returns:: thresholding method.

See also:: vl_kdforest_set_thresholding_method

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

Parameters:

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

Returns:: new KDForest.

VlKDForestSearcher* vl_kdforest_new_searcher ( VlKDForest * kdforest )

Parameters:

kdforest a forest to which the queries should be pointing.

Returns:: KDForest searcher object.

A searcher is an object attached to the forest which must be created before running the queries. Each query has to be invoked with the searcher as its argument.

When using a multi-threaded approach a user should at first instantiate a correct number of searchers - each used in one thread. Then in each thread a query to the given searcher could be run.

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

Parameters:

selft	object.
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.

vl_uindex vl_kdforest_query_recursively	(	VlKDForestSearcher *	searcher,
		VlKDTree *	tree,
		vl_uindex	nodeIndex,
		VlKDForestNeighbor *	neighbors,
		vl_size	numNeighbors,
		vl_size *	numAddedNeighbors,
		double	dist,
		void const *	query
	)

vl_size vl_kdforest_query_with_array	(	VlKDForest *	self,
		vl_uint32 *	indexes,
		vl_size	numNeighbors,
		vl_size	numQueries,
		void *	distances,
		void const *	queries
	)

Parameters:

self	object.
indexes	assignments of points.
distances	distances of query points.
numQueries	number of query points.
numNeighbors	number of nearest neighbors to be found for each data point

indexes and distances are numNeighbors by numQueries matrices containing the indexes and distances of the nearest neighbours for each of the numQueries queries queries.

This function is similar to vl_kdforest_query. The main difference is that the function can use multiple cores to query large amounts of data.

See also:: vl_kdforest_query.

void vl_kdforest_set_max_num_comparisons	(	VlKDForest *	self,
		vl_size	n
	)

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.

void vl_kdforest_set_thresholding_method	(	VlKDForest *	self,
		VlKDTreeThresholdingMethod	method
	)

Parameters:

self	KDForest object.
method	one of VlKDTreeThresholdingMethod.

See also:: vl_kdforest_get_thresholding_method

void vl_kdforestsearcher_delete ( VlKDForestSearcher * self )

Parameters:

self object.

VlKDForest* vl_kdforestsearcher_get_forest ( VlKDForestSearcher const * self )

Parameters:

self object.

Returns:: correspoinding KD-Forest.

vl_size vl_kdforestsearcher_query	(	VlKDForestSearcher *	self,
		VlKDForestNeighbor *	neighbors,
		vl_size	numNeighbors,
		void const *	query
	)

Parameters:

self	object.
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.

static void vl_kdtree_build_recursively	(	VlKDForest *	forest,
		VlKDTree *	tree,
		vl_uindex	nodeIndex,
		vl_uindex	dataBegin,
		vl_uindex	dataEnd,
		unsigned int	depth
	)

static

Parameters:

forest	forest to which the tree belongs.
tree	tree being built.
nodeIndex	node to process.
dataBegin	begin of data for this node.
dataEnd	end of data for this node.
depth	depth of this node.

static void vl_kdtree_calc_bounds_recursively	(	VlKDTree *	tree,
		vl_uindex	nodeIndex,
		double *	searchBounds
	)

static

Parameters:

tree	KDTree object instance.
nodeIndex	node index to start from.
searchBounds	2 x numDimension array of bounds.

int vl_kdtree_compare_index_entries	(	void const *	a,
		void const *	b
	)

inline

static vl_uindex vl_kdtree_node_new	(	VlKDTree *	tree,
		vl_uindex	parentIndex
	)

static

VLFeat.org

Functions

Detailed Description

Function Documentation