MRPT  1.9.9
kdtree.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | http://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2018, Individual contributors, see AUTHORS file |
6  | See: http://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See details in http://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 
10 #ifndef KDTREE_H
11 #define KDTREE_H
12 
13 //#include "cxcore.h"
14 // Universal include for all versions of OpenCV
15 #include <mrpt/otherlibs/do_opencv_includes.h>
16 
17 /********************************* Structures ********************************/
18 
19 struct feature;
20 
21 /** a node in a k-d tree */
22 struct kd_node
23 {
24  int ki; /**< partition key index */
25  double kv; /**< partition key value */
26  int leaf; /**< 1 if node is a leaf, 0 otherwise */
27  struct feature* features; /**< features at this node */
28  int n; /**< number of features */
29  struct kd_node* kd_left; /**< left child */
30  struct kd_node* kd_right; /**< right child */
31 };
32 
33 /*************************** Function Prototypes *****************************/
34 
35 /**
36 A function to build a k-d tree database from keypoints in an array.
37 
38 @param features an array of features
39 @param n the number of features in \a features
40 
41 @return Returns the root of a kd tree built from \a features.
42 */
43 extern struct kd_node* kdtree_build(struct feature* features, int n);
44 
45 /**
46 Finds an image feature's approximate k nearest neighbors in a kd tree using
47 Best Bin First search.
48 
49 @param kd_root root of an image feature kd tree
50 @param feat image feature for whose neighbors to search
51 @param k number of neighbors to find
52 @param nbrs pointer to an array in which to store pointers to neighbors
53  in order of increasing descriptor distance
54 @param max_nn_chks search is cut off after examining this many tree entries
55 
56 @return Returns the number of neighbors found and stored in \a nbrs, or
57  -1 on error.
58 */
59 extern int kdtree_bbf_knn(
60  struct kd_node* kd_root, struct feature* feat, int k,
61  struct feature*** nbrs, int max_nn_chks);
62 
63 /**
64 Finds an image feature's approximate k nearest neighbors within a specified
65 spatial region in a kd tree using Best Bin First search.
66 
67 @param kd_root root of an image feature kd tree
68 @param feat image feature for whose neighbors to search
69 @param k number of neighbors to find
70 @param nbrs pointer to an array in which to store pointers to neighbors
71  in order of increasing descriptor distance
72 @param max_nn_chks search is cut off after examining this many tree entries
73 @param rect rectangular region in which to search for neighbors
74 @param model if true, spatial search is based on kdtree features' model
75  locations; otherwise it is based on their image locations
76 
77 @return Returns the number of neighbors found and stored in \a nbrs
78  (in case \a k neighbors could not be found before examining
79  \a max_nn_checks keypoint entries).
80 */
81 extern int kdtree_bbf_spatial_knn(
82  struct kd_node* kd_root, struct feature* feat, int k,
83  struct feature*** nbrs, int max_nn_chks, CvRect rect, int model);
84 
85 /**
86 De-allocates memory held by a kd tree
87 
88 @param kd_root pointer to the root of a kd tree
89 */
90 extern void kdtree_release(struct kd_node* kd_root);
91 
92 #endif
struct kd_node * kd_left
left child
Definition: kdtree.h:29
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&#39;s approximate k nearest neighbors 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
int leaf
1 if node is a leaf, 0 otherwise
Definition: kdtree.h:26
GLenum GLsizei n
Definition: glext.h:5074
struct kd_node * kd_right
right child
Definition: kdtree.h:30
double kv
partition key value
Definition: kdtree.h:25
int n
number of features
Definition: kdtree.h:28
struct kd_node * kdtree_build(struct feature *features, int n)
A function to build a k-d tree database from keypoints in an array.
struct feature * features
features at this node
Definition: kdtree.h:27
_u8 model
Definition: rplidar_cmd.h:19
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&#39;s approximate k nearest neighbors within a specified spatial region in a kd t...
a node in a k-d tree
Definition: kdtree.h:22
Structure to represent an affine invariant image feature.
Definition: imgfeatures.h:49
int ki
partition key index
Definition: kdtree.h:24



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 7d5e6d718 Fri Aug 24 01:51:28 2018 +0200 at lun nov 2 08:35:50 CET 2020