kdtree.c File Reference

KD-tree - Definition. More...

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

Include dependency graph for kdtree.c:

Go to the source code of this file.

Defines
#define	VL_HEAP_cmp(v, x, y)   (v[x].distanceLowerBound - v[y].distanceLowerBound)
#define	VL_HEAP_cmp(v, x, y)   (v[x].variance - v[y].variance)
#define	VL_HEAP_cmp(v, x, y)   (v[y].distance - v[x].distance)
#define	VL_HEAP_prefix   vl_kdforest_search_heap
#define	VL_HEAP_prefix   vl_kdtree_split_heap
#define	VL_HEAP_prefix   vl_kdforest_neighbor_heap
#define	VL_HEAP_type   VlKDForestSearchState
#define	VL_HEAP_type   VlKDTreeSplitDimension
#define	VL_HEAP_type   VlKDForestNeighbor
Functions
void	vl_kdforest_build (VlKDForest *self, vl_size numData, void const *data)
	Build KDTree from data.
void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object.
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.
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_max_num_comparisons (VlKDForest *self)
	Get the maximum number of comparisons for a search.
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.
VlKDForestSearcher *	vl_kdforest_get_searcher (VlKDForest const *self, vl_uindex pos)
VlKDTreeThresholdingMethod	vl_kdforest_get_thresholding_method (VlKDForest const *self)
	Get the thresholding method.
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.
vl_size	vl_kdforest_query (VlKDForest *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
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)
	Run multiple queries.
void	vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
	Set the maximum number of comparisons for a search.
void	vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
	Set the thresholding method.
void	vl_kdforestsearcher_delete (VlKDForestSearcher *self)
	Delete object.
VlKDForest *	vl_kdforestsearcher_get_forest (VlKDForestSearcher const *self)
	Get the forest linked to the searcher.
vl_size	vl_kdforestsearcher_query (VlKDForestSearcher *self, VlKDForestNeighbor *neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
static void	vl_kdtree_build_recursively (VlKDForest *forest, VlKDTree *tree, vl_uindex nodeIndex, vl_uindex dataBegin, vl_uindex dataEnd, unsigned int depth)
static void	vl_kdtree_calc_bounds_recursively (VlKDTree *tree, vl_uindex nodeIndex, double *searchBounds)
VL_INLINE int	vl_kdtree_compare_index_entries (void const *a, void const *b)
static vl_uindex	vl_kdtree_node_new (VlKDTree *tree, vl_uindex parentIndex)

---

Detailed Description

KD-tree - Definition.

Author:

Andrea Vedaldi, David Novotny

Definition in file kdtree.c.

---

Define Documentation

#define VL_HEAP_cmp	(		v,
			x,
			y
	)		(v[x].distanceLowerBound - v[y].distanceLowerBound)

Definition at line 111 of file kdtree.c.

#define VL_HEAP_cmp	(		v,
			x,
			y
	)		(v[x].variance - v[y].variance)

Definition at line 111 of file kdtree.c.

#define VL_HEAP_cmp	(		v,
			x,
			y
	)		(v[y].distance - v[x].distance)

Definition at line 111 of file kdtree.c.

#define VL_HEAP_prefix   vl_kdforest_search_heap

Definition at line 109 of file kdtree.c.

#define VL_HEAP_prefix   vl_kdtree_split_heap

Definition at line 109 of file kdtree.c.

#define VL_HEAP_prefix   vl_kdforest_neighbor_heap

Definition at line 109 of file kdtree.c.

#define VL_HEAP_type   VlKDForestSearchState

Definition at line 110 of file kdtree.c.

#define VL_HEAP_type   VlKDTreeSplitDimension

Definition at line 110 of file kdtree.c.

#define VL_HEAP_type   VlKDForestNeighbor

Definition at line 110 of file kdtree.c.

---

Function Documentation

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

Build KDTree from 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 make a copy the data, but retains a pointer to it. Therefore the data buffer must be valid and unchanged for the lifespan of the object.

The number of data points numData must not be smaller than one.

Definition at line 530 of file kdtree.c.

void vl_kdforest_delete

(

VlKDForest *

self

)

Delete KDForest object.

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

Parameters:

self	KDForest object to delete

See also:

vl_kdforest_new

Definition at line 461 of file kdtree.c.

vl_size vl_kdforest_get_data_dimension

(

VlKDForest const *

self

)

Get the dimension of the data.

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

Parameters:

self	KDForest object.

Returns:

dimension of the data.

Definition at line 1055 of file kdtree.c.

vl_type vl_kdforest_get_data_type

(

VlKDForest const *

self

)

Get the data type.

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

Parameters:

self	KDForest object.

Returns:

data type (one of VL_TYPE_FLOAT, VL_TYPE_DOUBLE).

Definition at line 1067 of file kdtree.c.

vl_size vl_kdforest_get_depth_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)

Get the detph of a given tree.

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

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:

number of trees.

Definition at line 966 of file kdtree.c.

vl_size vl_kdforest_get_max_num_comparisons

(

VlKDForest *

self

)

Get the maximum number of comparisons for a search.

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

Parameters:

self	KDForest object.

Returns:

maximum number of leaves.

See also:

vl_kdforest_set_max_num_comparisons.

Definition at line 1013 of file kdtree.c.

vl_size vl_kdforest_get_num_nodes_of_tree	(	VlKDForest const *	self,
		vl_uindex	treeIndex
	)

Get the number of nodes of a given tree.

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

Parameters:

self	KDForest object.
treeIndex	index of the tree.

Returns:

number of trees.

Definition at line 952 of file kdtree.c.

vl_size vl_kdforest_get_num_trees

(

VlKDForest const *

self

)

Get the number of trees in the forest.

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

Parameters:

self	KDForest object.

Returns:

number of trees.

Definition at line 980 of file kdtree.c.

VlKDForestSearcher* vl_kdforest_get_searcher	(	VlKDForest const *	self,
		vl_uindex	pos
	)

Definition at line 443 of file kdtree.c.

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method

(

VlKDForest const *

self

)

Get the thresholding method.

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

Parameters:

self	KDForest object.

Returns:

thresholding method.

See also:

vl_kdforest_set_thresholding_method

Definition at line 1043 of file kdtree.c.

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

Create new KDForest object.

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

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.

The data dimension dimension and the number of trees numTrees must not be smaller than one.

Definition at line 332 of file kdtree.c.

VlKDForestSearcher* vl_kdforest_new_searcher

(

VlKDForest *

kdforest

)

Create a KDForest searcher object, used for processing queries.

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

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.

Definition at line 388 of file kdtree.c.

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

Query the forest.

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

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.

Definition at line 744 of file kdtree.c.

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
	)

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

Definition at line 585 of file kdtree.c.

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.

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

Parameters:

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

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.

Definition at line 870 of file kdtree.c.

void vl_kdforest_set_max_num_comparisons	(	VlKDForest *	self,
		vl_size	n
	)

Set the maximum number of comparisons for a search.

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

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 998 of file kdtree.c.

void vl_kdforest_set_thresholding_method	(	VlKDForest *	self,
		VlKDTreeThresholdingMethod	method
	)

Set the thresholding method.

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

Parameters:

self	KDForest object.
method	one of VlKDTreeThresholdingMethod.

See also:

vl_kdforest_get_thresholding_method

Definition at line 1027 of file kdtree.c.

void vl_kdforestsearcher_delete

(

VlKDForestSearcher *

self

)

Delete object.

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

Parameters:

self

object.

Definition at line 423 of file kdtree.c.

VlKDForest* vl_kdforestsearcher_get_forest

(

VlKDForestSearcher const *

self

)

Get the forest linked to the searcher.

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

Parameters:

self

object.

Returns:

correspoinding KD-Forest.

Definition at line 1079 of file kdtree.c.

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

Query the forest.

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

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.

Definition at line 774 of file kdtree.c.

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

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

Definition at line 167 of file kdtree.c.

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

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

Definition at line 491 of file kdtree.c.

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

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

Definition at line 143 of file kdtree.c.

static vl_uindex vl_kdtree_node_new	(	VlKDTree *	tree,
		vl_uindex	parentIndex
	)		[static]

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

Definition at line 120 of file kdtree.c.