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

Include dependency graph for vl/kdtree.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	_VlKDForest
	KDForest object. More...
struct	_VlKDForestNeighbor
	Neighbor of a query point. More...
struct	_VlKDForestSearcher
	VlKDForest searcher object More...
struct	_VlKDForestSearchState
struct	_VlKDTree
struct	_VlKDTreeDataIndexEntry
struct	_VlKDTreeNode
struct	_VlKDTreeSplitDimension
Defines
#define	VL_KDTREE_SPLIT_HEAP_SIZE 5
#define	VL_KDTREE_VARIANCE_EST_NUM_SAMPLES 1024
Typedefs
typedef struct _VlKDForest	VlKDForest
	KDForest object.
typedef struct _VlKDForestNeighbor	VlKDForestNeighbor
	Neighbor of a query point.
typedef struct _VlKDForestSearcher	VlKDForestSearcher
	VlKDForest searcher object
typedef struct _VlKDForestSearchState	VlKDForestSearchState
typedef struct _VlKDTree	VlKDTree
typedef struct _VlKDTreeDataIndexEntry	VlKDTreeDataIndexEntry
typedef struct _VlKDTreeNode	VlKDTreeNode
typedef struct _VlKDTreeSplitDimension	VlKDTreeSplitDimension
typedef enum _VlKDTreeThresholdingMethod	VlKDTreeThresholdingMethod
	Thresholding method.
Enumerations
enum	_VlKDTreeThresholdingMethod { VL_KDTREE_MEDIAN, VL_KDTREE_MEAN }
	Thresholding method. More...
Functions
Creating, copying and disposing
VL_EXPORT VlKDForest *	vl_kdforest_new (vl_type dataType, vl_size dimension, vl_size numTrees, VlVectorComparisonType normType)
	Create new KDForest object.
VL_EXPORT VlKDForestSearcher *	vl_kdforest_new_searcher (VlKDForest *kdforest)
	Create a KDForest searcher object, used for processing queries.
VL_EXPORT void	vl_kdforest_delete (VlKDForest *self)
	Delete KDForest object.
VL_EXPORT void	vl_kdforestsearcher_delete (VlKDForestSearcher *searcher)
	Delete object.
Building and querying
VL_EXPORT void	vl_kdforest_build (VlKDForest self, vl_size numData, void const data)
	Build KDTree from data.
VL_EXPORT vl_size	vl_kdforest_query (VlKDForest self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
VL_EXPORT 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.
VL_EXPORT vl_size	vl_kdforestsearcher_query (VlKDForestSearcher self, VlKDForestNeighbor neighbors, vl_size numNeighbors, void const *query)
	Query the forest.
Retrieving and setting parameters
VL_EXPORT vl_size	vl_kdforest_get_depth_of_tree (VlKDForest const *self, vl_uindex treeIndex)
	Get the detph of a given tree.
VL_EXPORT 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_EXPORT vl_size	vl_kdforest_get_num_trees (VlKDForest const *self)
	Get the number of trees in the forest.
VL_EXPORT vl_size	vl_kdforest_get_data_dimension (VlKDForest const *self)
	Get the dimension of the data.
VL_EXPORT vl_type	vl_kdforest_get_data_type (VlKDForest const *self)
	Get the data type.
VL_EXPORT void	vl_kdforest_set_max_num_comparisons (VlKDForest *self, vl_size n)
	Set the maximum number of comparisons for a search.
VL_EXPORT vl_size	vl_kdforest_get_max_num_comparisons (VlKDForest *self)
	Get the maximum number of comparisons for a search.
VL_EXPORT void	vl_kdforest_set_thresholding_method (VlKDForest *self, VlKDTreeThresholdingMethod method)
	Set the thresholding method.
VL_EXPORT VlKDTreeThresholdingMethod	vl_kdforest_get_thresholding_method (VlKDForest const *self)
	Get the thresholding method.
VL_EXPORT VlKDForest *	vl_kdforest_searcher_get_forest (VlKDForestSearcher const *self)
VL_EXPORT VlKDForestSearcher *	vl_kdforest_get_searcher (VlKDForest const *self, vl_uindex pos)

Define Documentation

#define VL_KDTREE_SPLIT_HEAP_SIZE 5

Definition at line 20 of file vl/kdtree.h.

#define VL_KDTREE_VARIANCE_EST_NUM_SAMPLES 1024

Definition at line 21 of file vl/kdtree.h.

Typedef Documentation

typedef struct _VlKDForest VlKDForest

KDForest object.

typedef struct _VlKDForestNeighbor VlKDForestNeighbor

Neighbor of a query point.

typedef struct _VlKDForestSearcher VlKDForestSearcher

VlKDForest searcher object

typedef struct _VlKDForestSearchState VlKDForestSearchState

Definition at line 26 of file vl/kdtree.h.

typedef struct _VlKDTree VlKDTree

typedef struct _VlKDTreeDataIndexEntry VlKDTreeDataIndexEntry

Definition at line 25 of file vl/kdtree.h.

typedef struct _VlKDTreeNode VlKDTreeNode

Definition at line 23 of file vl/kdtree.h.

typedef struct _VlKDTreeSplitDimension VlKDTreeSplitDimension

Definition at line 24 of file vl/kdtree.h.

typedef enum _VlKDTreeThresholdingMethod VlKDTreeThresholdingMethod

Thresholding method.

Enumeration Type Documentation

enum _VlKDTreeThresholdingMethod

Thresholding method.

Enumerator:

VL_KDTREE_MEDIAN
VL_KDTREE_MEAN

Definition at line 53 of file vl/kdtree.h.

Function Documentation

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

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

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

Definition at line 443 of file kdtree.c.

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

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

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

VL_EXPORT VlKDForest* vl_kdforest_searcher_get_forest ( VlKDForestSearcher const * self )

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

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

VL_EXPORT void vl_kdforestsearcher_delete ( VlKDForestSearcher * self )

Delete object.

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

Parameters:

self object.

Definition at line 423 of file kdtree.c.

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

Classes

Defines

Typedefs

Enumerations

Functions

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation