1 #ifndef KDTREE_H
2 #define KDTREE_H
3 
4 #include "precomp.hpp"
5 
6 namespace cv
7 {
8 namespace ml
9 {
10 
11 /*!
12  Fast Nearest Neighbor Search Class.
13 
14  The class implements D. Lowe BBF (Best-Bin-First) algorithm for the last
15  approximate (or accurate) nearest neighbor search in multi-dimensional spaces.
16 
17  First, a set of vectors is passed to KDTree::KDTree() constructor
18  or KDTree::build() method, where it is reordered.
19 
20  Then arbitrary vectors can be passed to KDTree::findNearest() methods, which
21  find the K nearest neighbors among the vectors from the initial set.
22  The user can balance between the speed and accuracy of the search by varying Emax
23  parameter, which is the number of leaves that the algorithm checks.
24  The larger parameter values yield more accurate results at the expense of lower processing speed.
25 
26  \code
27  KDTree T(points, false);
28  const int K = 3, Emax = INT_MAX;
29  int idx[K];
30  float dist[K];
31  T.findNearest(query_vec, K, Emax, idx, 0, dist);
32  CV_Assert(dist[0] <= dist[1] && dist[1] <= dist[2]);
33  \endcode
34 */
35 class CV_EXPORTS_W KDTree
36 {
37 public:
38     /*!
39         The node of the search tree.
40     */
41     struct Node
42     {
Nodecv::ml::KDTree::Node43         Node() : idx(-1), left(-1), right(-1), boundary(0.f) {}
Nodecv::ml::KDTree::Node44         Node(int _idx, int _left, int _right, float _boundary)
45             : idx(_idx), left(_left), right(_right), boundary(_boundary) {}
46 
47         //! split dimension; >=0 for nodes (dim), < 0 for leaves (index of the point)
48         int idx;
49         //! node indices of the left and the right branches
50         int left, right;
51         //! go to the left if query_vec[node.idx]<=node.boundary, otherwise go to the right
52         float boundary;
53     };
54 
55     //! the default constructor
56     CV_WRAP KDTree();
57     //! the full constructor that builds the search tree
58     CV_WRAP KDTree(InputArray points, bool copyAndReorderPoints = false);
59     //! the full constructor that builds the search tree
60     CV_WRAP KDTree(InputArray points, InputArray _labels,
61                    bool copyAndReorderPoints = false);
62     //! builds the search tree
63     CV_WRAP void build(InputArray points, bool copyAndReorderPoints = false);
64     //! builds the search tree
65     CV_WRAP void build(InputArray points, InputArray labels,
66                        bool copyAndReorderPoints = false);
67     //! finds the K nearest neighbors of "vec" while looking at Emax (at most) leaves
68     CV_WRAP int findNearest(InputArray vec, int K, int Emax,
69                             OutputArray neighborsIdx,
70                             OutputArray neighbors = noArray(),
71                             OutputArray dist = noArray(),
72                             OutputArray labels = noArray()) const;
73     //! finds all the points from the initial set that belong to the specified box
74     CV_WRAP void findOrthoRange(InputArray minBounds,
75                                 InputArray maxBounds,
76                                 OutputArray neighborsIdx,
77                                 OutputArray neighbors = noArray(),
78                                 OutputArray labels = noArray()) const;
79     //! returns vectors with the specified indices
80     CV_WRAP void getPoints(InputArray idx, OutputArray pts,
81                            OutputArray labels = noArray()) const;
82     //! return a vector with the specified index
83     const float* getPoint(int ptidx, int* label = 0) const;
84     //! returns the search space dimensionality
85     CV_WRAP int dims() const;
86 
87     std::vector<Node> nodes; //!< all the tree nodes
88     CV_PROP Mat points; //!< all the points. It can be a reordered copy of the input vector set or the original vector set.
89     CV_PROP std::vector<int> labels; //!< the parallel array of labels.
90     CV_PROP int maxDepth; //!< maximum depth of the search tree. Do not modify it
91     CV_PROP_RW int normType; //!< type of the distance (cv::NORM_L1 or cv::NORM_L2) used for search. Initially set to cv::NORM_L2, but you can modify it
92 };
93 
94 }
95 }
96 
97 #endif
98