kdtree.h File Reference

Functions and structures for maintaining a k-d tree database of image features. More...

---

Detailed Description

Functions and structures for maintaining a k-d tree database of image features.

For more information, refer to:

Beis, J. S. and Lowe, D. G. Shape indexing using approximate nearest-neighbor search in high-dimensional spaces. In Conference on Computer Vision and Pattern Recognition (CVPR) (2003), pp. 1000--1006.

Copyright (C) 2006 Rob Hess <hess@eecs.oregonstate.edu>

Version:

1.1.1-20070119

Definition in file kdtree.h.

Go to the source code of this file.

Classes
struct	kd_node
	a node in a k-d tree More...
Functions
struct kd_node *	kdtree_build (struct feature *features, int n)
	A function to build a k-d tree database from keypoints in an array.
int	kdtree_bbf_knn (struct kd_node *kd_root, struct feature *feat, int k, struct feature ***nbrs, int max_nn_chks)
	Finds an image feature's approximate k nearest neighbors in a kd tree using Best Bin First search.
int	kdtree_bbf_spatial_knn (struct kd_node *kd_root, struct feature *feat, int k, struct feature ***nbrs, int max_nn_chks, CvRect rect, int model)
	Finds an image feature's approximate k nearest neighbors within a specified spatial region in a kd tree using Best Bin First search.
void	kdtree_release (struct kd_node *kd_root)
	De-allocates memory held by a kd tree.

---

Function Documentation

int kdtree_bbf_knn	(	struct kd_node *	kd_root,
		struct feature *	feat,
		int	k,
		struct feature ***	nbrs,
		int	max_nn_chks
	)

Finds an image feature's approximate k nearest neighbors in a kd tree using Best Bin First search.

Parameters:

kd_root	root of an image feature kd tree
feat	image feature for whose neighbors to search
k	number of neighbors to find
nbrs	pointer to an array in which to store pointers to neighbors in order of increasing descriptor distance
max_nn_chks	search is cut off after examining this many tree entries

Returns:

Returns the number of neighbors found and stored in nbrs, or -1 on error.

int kdtree_bbf_spatial_knn	(	struct kd_node *	kd_root,
		struct feature *	feat,
		int	k,
		struct feature ***	nbrs,
		int	max_nn_chks,
		CvRect	rect,
		int	model
	)

Finds an image feature's approximate k nearest neighbors within a specified spatial region in a kd tree using Best Bin First search.

Parameters:

kd_root	root of an image feature kd tree
feat	image feature for whose neighbors to search
k	number of neighbors to find
nbrs	pointer to an array in which to store pointers to neighbors in order of increasing descriptor distance
max_nn_chks	search is cut off after examining this many tree entries
rect	rectangular region in which to search for neighbors
model	if true, spatial search is based on kdtree features' model locations; otherwise it is based on their image locations

Returns:

Returns the number of neighbors found and stored in nbrs (in case k neighbors could not be found before examining max_nn_checks keypoint entries).

struct kd_node* kdtree_build	(	struct feature *	features,
		int	n
	)		[read]

A function to build a k-d tree database from keypoints in an array.

Parameters:

features	an array of features
n	the number of features in features

Returns:

Returns the root of a kd tree built from features.

void kdtree_release

(

struct kd_node *

kd_root

)

De-allocates memory held by a kd tree.

Parameters:

kd_root

pointer to the root of a kd tree