KD-tree (KD-trees and forests) More...

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

Data Structures
struct	VlKDForestNeighbor
	Neighbor of a query point. More...

struct	VlKDForest
	KDForest object. More...

struct	VlKDForestSearcher
	VlKDForest searcher object More...

Enumerations
enum	VlKDTreeThresholdingMethod
	Thresholding method.

Functions
Creating, copying and disposing
VlKDForest *	vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees, VlVectorComparisonType normType)
	Create new KDForest object. More...

VlKDForestSearcher *	vl_kdforest_new_searcher (VlKDForest *kdforest)
	Create a KDForest searcher object, used for processing queries. More...

void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object. More...

void	vl_kdforestsearcher_delete (VlKDForestSearcher *searcher)
	Delete object. More...

Building and querying
void	vl_kdforest_build (VlKDForest self, vl_size numData, void const data)
	Build KDTree from data. More...

vl_size	vl_kdforest_query (VlKDForest self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest. More...

vl_size	vl_kdforest_query_with_array (VlKDForest self, vl_uint32 index, vl_size numNeighbors, vl_size numQueries, void distance, void const queries)
	Run multiple queries. More...

vl_size	vl_kdforestsearcher_query (VlKDForestSearcher self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest. More...

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. More...

vl_size	vl_kdforest_get_num_nodes_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the number of nodes of a given tree. More...

vl_size	vl_kdforest_get_num_trees (VlKDForest const *self)
	Get the number of trees in the forest. More...

vl_size	vl_kdforest_get_data_dimension (VlKDForest const *self)
	Get the dimension of the data. More...

vl_type	vl_kdforest_get_data_type (VlKDForest const *self)
	Get the data type. More...

void	vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
	Set the maximum number of comparisons for a search. More...

vl_size	vl_kdforest_get_max_num_comparisons (VlKDForest *self)
	Get the maximum number of comparisons for a search. More...

void	vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
	Set the thresholding method. More...

VlKDTreeThresholdingMethod	vl_kdforest_get_thresholding_method (VlKDForest const *self)
	Get the thresholding method. More...

VlKDForest *	vl_kdforest_searcher_get_forest (VlKDForestSearcher const *self)

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

Detailed Description

Author: Andrea Vedaldi, David Novotny

Function Documentation

◆ vl_kdforest_build()

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

◆ vl_kdforest_delete()

void vl_kdforest_delete ( VlKDForest * self )

Parameters

self	KDForest object to delete

See also: vl_kdforest_new

◆ vl_kdforest_get_data_dimension()

vl_size vl_kdforest_get_data_dimension ( VlKDForest const * self )

Parameters

self	KDForest object.

Returns: dimension of the data.

◆ vl_kdforest_get_data_type()

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_kdforest_get_depth_of_tree()

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_kdforest_get_max_num_comparisons()

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_kdforest_get_num_nodes_of_tree()

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_kdforest_get_num_trees()

vl_size vl_kdforest_get_num_trees ( VlKDForest const * self )

Parameters

self	KDForest object.

Returns: number of trees.

◆ vl_kdforest_get_thresholding_method()

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method ( VlKDForest const * self )

Parameters

self	KDForest object.

Returns: thresholding method.

See also: vl_kdforest_set_thresholding_method

◆ vl_kdforest_new()

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.

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

◆ vl_kdforest_new_searcher()

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_kdforest_query()

vl_size vl_kdforest_query	(	VlKDForest *	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.

◆ vl_kdforest_query_with_array()

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

◆ vl_kdforest_set_max_num_comparisons()

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.

◆ vl_kdforest_set_thresholding_method()

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

◆ vl_kdforestsearcher_delete()

void vl_kdforestsearcher_delete ( VlKDForestSearcher * self )

Parameters

self object.

◆ vl_kdforestsearcher_query()

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.

VLFeat.org

Data Structures

Enumerations

Functions

Detailed Description

Function Documentation

◆ vl_kdforest_build()

◆ vl_kdforest_delete()

◆ vl_kdforest_get_data_dimension()

◆ vl_kdforest_get_data_type()

◆ vl_kdforest_get_depth_of_tree()

◆ vl_kdforest_get_max_num_comparisons()

◆ vl_kdforest_get_num_nodes_of_tree()

◆ vl_kdforest_get_num_trees()

◆ vl_kdforest_get_thresholding_method()

◆ vl_kdforest_new()

◆ vl_kdforest_new_searcher()

◆ vl_kdforest_query()

◆ vl_kdforest_query_with_array()

◆ vl_kdforest_set_max_num_comparisons()

◆ vl_kdforest_set_thresholding_method()

◆ vl_kdforestsearcher_delete()

◆ vl_kdforestsearcher_query()