- Main Page
- Data Structures
- Files

- File List
- Globals

# kdtree.h File Reference

## 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-2007 Rob Hess <hess@eecs.oregonstate.edu>

Version:
  1.1.1-20070913

`#include "cxcore.h"`

## Data Structures
struct | kd_node
| a node in a k-d tree More...
## Functions
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

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.

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

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