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



Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at lun oct 28 01:39:17 CET 2019