Documentation>C API
kdtree.h File Reference

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
VlKDForestvl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees, VlVectorComparisonType normType)
 Create new KDForest object. More...
 
VlKDForestSearchervl_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...
 
VlKDForestvl_kdforest_searcher_get_forest (VlKDForestSearcher const *self)
 
VlKDForestSearchervl_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
selfKDTree object
numDatanumber of data points.
datapointer 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
selfKDForest object to delete
See also
vl_kdforest_new

◆ vl_kdforest_get_data_dimension()

vl_size vl_kdforest_get_data_dimension ( VlKDForest const *  self)
Parameters
selfKDForest object.
Returns
dimension of the data.

◆ vl_kdforest_get_data_type()

vl_type vl_kdforest_get_data_type ( VlKDForest const *  self)
Parameters
selfKDForest 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
selfKDForest object.
treeIndexindex of the tree.
Returns
number of trees.

◆ vl_kdforest_get_max_num_comparisons()

vl_size vl_kdforest_get_max_num_comparisons ( VlKDForest self)
Parameters
selfKDForest 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
selfKDForest object.
treeIndexindex of the tree.
Returns
number of trees.

◆ vl_kdforest_get_num_trees()

vl_size vl_kdforest_get_num_trees ( VlKDForest const *  self)
Parameters
selfKDForest object.
Returns
number of trees.

◆ vl_kdforest_get_thresholding_method()

VlKDTreeThresholdingMethod vl_kdforest_get_thresholding_method ( VlKDForest const *  self)
Parameters
selfKDForest 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
dataTypetype of data (VL_TYPE_FLOAT or VL_TYPE_DOUBLE)
dimensiondata dimensionality.
numTreesnumber of trees in the forest.
distancetype 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
kdforesta 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
selfobject.
neighborslist of nearest neighbors found (output).
numNeighborsnumber of nearest neighbors to find.
queryquery 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
selfobject.
indexesassignments of points.
numNeighborsnumber of nearest neighbors to be found for each data point
numQueriesnumber of query points.
distancesdistances of query points.
querieslisf 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
selfKDForest object.
nmaximum 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
selfKDForest object.
methodone of VlKDTreeThresholdingMethod.
See also
vl_kdforest_get_thresholding_method

◆ vl_kdforestsearcher_delete()

void vl_kdforestsearcher_delete ( VlKDForestSearcher self)
Parameters
selfobject.

◆ vl_kdforestsearcher_query()

vl_size vl_kdforestsearcher_query ( VlKDForestSearcher self,
VlKDForestNeighbor neighbors,
vl_size  numNeighbors,
void const *  query 
)
Parameters
selfobject.
neighborslist of nearest neighbors found (output).
numNeighborsnumber of nearest neighbors to find.
queryquery 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.