Joe Verbout / Mbed 2 deprecated main

opencv on mbed

Dependencies:   mbed

opencv2/flann/kdtree_single_index.h@0:ea44dc9ed014, 2016-03-31 (annotated)

Committer:
joeverbout
Date:
Thu Mar 31 21:16:38 2016 +0000
Revision:
0:ea44dc9ed014
OpenCV on mbed attempt

Who changed what in which revision?

UserRevisionLine numberNew contents of line
joeverbout 0:ea44dc9ed014 1 /***********************************************************************
joeverbout 0:ea44dc9ed014 2 * Software License Agreement (BSD License)
joeverbout 0:ea44dc9ed014 3 *
joeverbout 0:ea44dc9ed014 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 6 *
joeverbout 0:ea44dc9ed014 7 * THE BSD LICENSE
joeverbout 0:ea44dc9ed014 8 *
joeverbout 0:ea44dc9ed014 9 * Redistribution and use in source and binary forms, with or without
joeverbout 0:ea44dc9ed014 10 * modification, are permitted provided that the following conditions
joeverbout 0:ea44dc9ed014 11 * are met:
joeverbout 0:ea44dc9ed014 12 *
joeverbout 0:ea44dc9ed014 13 * 1. Redistributions of source code must retain the above copyright
joeverbout 0:ea44dc9ed014 14 * notice, this list of conditions and the following disclaimer.
joeverbout 0:ea44dc9ed014 15 * 2. Redistributions in binary form must reproduce the above copyright
joeverbout 0:ea44dc9ed014 16 * notice, this list of conditions and the following disclaimer in the
joeverbout 0:ea44dc9ed014 17 * documentation and/or other materials provided with the distribution.
joeverbout 0:ea44dc9ed014 18 *
joeverbout 0:ea44dc9ed014 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
joeverbout 0:ea44dc9ed014 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
joeverbout 0:ea44dc9ed014 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
joeverbout 0:ea44dc9ed014 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
joeverbout 0:ea44dc9ed014 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
joeverbout 0:ea44dc9ed014 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
joeverbout 0:ea44dc9ed014 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
joeverbout 0:ea44dc9ed014 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
joeverbout 0:ea44dc9ed014 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
joeverbout 0:ea44dc9ed014 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
joeverbout 0:ea44dc9ed014 29 *************************************************************************/
joeverbout 0:ea44dc9ed014 30
joeverbout 0:ea44dc9ed014 31 #ifndef OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
joeverbout 0:ea44dc9ed014 32 #define OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
joeverbout 0:ea44dc9ed014 33
joeverbout 0:ea44dc9ed014 34 #include <algorithm>
joeverbout 0:ea44dc9ed014 35 #include <map>
joeverbout 0:ea44dc9ed014 36 #include <cassert>
joeverbout 0:ea44dc9ed014 37 #include <cstring>
joeverbout 0:ea44dc9ed014 38
joeverbout 0:ea44dc9ed014 39 #include "general.h"
joeverbout 0:ea44dc9ed014 40 #include "nn_index.h"
joeverbout 0:ea44dc9ed014 41 #include "matrix.h"
joeverbout 0:ea44dc9ed014 42 #include "result_set.h"
joeverbout 0:ea44dc9ed014 43 #include "heap.h"
joeverbout 0:ea44dc9ed014 44 #include "allocator.h"
joeverbout 0:ea44dc9ed014 45 #include "random.h"
joeverbout 0:ea44dc9ed014 46 #include "saving.h"
joeverbout 0:ea44dc9ed014 47
joeverbout 0:ea44dc9ed014 48 namespace cvflann
joeverbout 0:ea44dc9ed014 49 {
joeverbout 0:ea44dc9ed014 50
joeverbout 0:ea44dc9ed014 51 struct KDTreeSingleIndexParams : public IndexParams
joeverbout 0:ea44dc9ed014 52 {
joeverbout 0:ea44dc9ed014 53 KDTreeSingleIndexParams(int leaf_max_size = 10, bool reorder = true, int dim = -1)
joeverbout 0:ea44dc9ed014 54 {
joeverbout 0:ea44dc9ed014 55 (*this)["algorithm"] = FLANN_INDEX_KDTREE_SINGLE;
joeverbout 0:ea44dc9ed014 56 (*this)["leaf_max_size"] = leaf_max_size;
joeverbout 0:ea44dc9ed014 57 (*this)["reorder"] = reorder;
joeverbout 0:ea44dc9ed014 58 (*this)["dim"] = dim;
joeverbout 0:ea44dc9ed014 59 }
joeverbout 0:ea44dc9ed014 60 };
joeverbout 0:ea44dc9ed014 61
joeverbout 0:ea44dc9ed014 62
joeverbout 0:ea44dc9ed014 63 /**
joeverbout 0:ea44dc9ed014 64 * Randomized kd-tree index
joeverbout 0:ea44dc9ed014 65 *
joeverbout 0:ea44dc9ed014 66 * Contains the k-d trees and other information for indexing a set of points
joeverbout 0:ea44dc9ed014 67 * for nearest-neighbor matching.
joeverbout 0:ea44dc9ed014 68 */
joeverbout 0:ea44dc9ed014 69 template <typename Distance>
joeverbout 0:ea44dc9ed014 70 class KDTreeSingleIndex : public NNIndex<Distance>
joeverbout 0:ea44dc9ed014 71 {
joeverbout 0:ea44dc9ed014 72 public:
joeverbout 0:ea44dc9ed014 73 typedef typename Distance::ElementType ElementType;
joeverbout 0:ea44dc9ed014 74 typedef typename Distance::ResultType DistanceType;
joeverbout 0:ea44dc9ed014 75
joeverbout 0:ea44dc9ed014 76
joeverbout 0:ea44dc9ed014 77 /**
joeverbout 0:ea44dc9ed014 78 * KDTree constructor
joeverbout 0:ea44dc9ed014 79 *
joeverbout 0:ea44dc9ed014 80 * Params:
joeverbout 0:ea44dc9ed014 81 * inputData = dataset with the input features
joeverbout 0:ea44dc9ed014 82 * params = parameters passed to the kdtree algorithm
joeverbout 0:ea44dc9ed014 83 */
joeverbout 0:ea44dc9ed014 84 KDTreeSingleIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KDTreeSingleIndexParams(),
joeverbout 0:ea44dc9ed014 85 Distance d = Distance() ) :
joeverbout 0:ea44dc9ed014 86 dataset_(inputData), index_params_(params), distance_(d)
joeverbout 0:ea44dc9ed014 87 {
joeverbout 0:ea44dc9ed014 88 size_ = dataset_.rows;
joeverbout 0:ea44dc9ed014 89 dim_ = dataset_.cols;
joeverbout 0:ea44dc9ed014 90 int dim_param = get_param(params,"dim",-1);
joeverbout 0:ea44dc9ed014 91 if (dim_param>0) dim_ = dim_param;
joeverbout 0:ea44dc9ed014 92 leaf_max_size_ = get_param(params,"leaf_max_size",10);
joeverbout 0:ea44dc9ed014 93 reorder_ = get_param(params,"reorder",true);
joeverbout 0:ea44dc9ed014 94
joeverbout 0:ea44dc9ed014 95 // Create a permutable array of indices to the input vectors.
joeverbout 0:ea44dc9ed014 96 vind_.resize(size_);
joeverbout 0:ea44dc9ed014 97 for (size_t i = 0; i < size_; i++) {
joeverbout 0:ea44dc9ed014 98 vind_[i] = (int)i;
joeverbout 0:ea44dc9ed014 99 }
joeverbout 0:ea44dc9ed014 100 }
joeverbout 0:ea44dc9ed014 101
joeverbout 0:ea44dc9ed014 102 KDTreeSingleIndex(const KDTreeSingleIndex&);
joeverbout 0:ea44dc9ed014 103 KDTreeSingleIndex& operator=(const KDTreeSingleIndex&);
joeverbout 0:ea44dc9ed014 104
joeverbout 0:ea44dc9ed014 105 /**
joeverbout 0:ea44dc9ed014 106 * Standard destructor
joeverbout 0:ea44dc9ed014 107 */
joeverbout 0:ea44dc9ed014 108 ~KDTreeSingleIndex()
joeverbout 0:ea44dc9ed014 109 {
joeverbout 0:ea44dc9ed014 110 if (reorder_) delete[] data_.data;
joeverbout 0:ea44dc9ed014 111 }
joeverbout 0:ea44dc9ed014 112
joeverbout 0:ea44dc9ed014 113 /**
joeverbout 0:ea44dc9ed014 114 * Builds the index
joeverbout 0:ea44dc9ed014 115 */
joeverbout 0:ea44dc9ed014 116 void buildIndex()
joeverbout 0:ea44dc9ed014 117 {
joeverbout 0:ea44dc9ed014 118 computeBoundingBox(root_bbox_);
joeverbout 0:ea44dc9ed014 119 root_node_ = divideTree(0, (int)size_, root_bbox_ ); // construct the tree
joeverbout 0:ea44dc9ed014 120
joeverbout 0:ea44dc9ed014 121 if (reorder_) {
joeverbout 0:ea44dc9ed014 122 delete[] data_.data;
joeverbout 0:ea44dc9ed014 123 data_ = cvflann::Matrix<ElementType>(new ElementType[size_*dim_], size_, dim_);
joeverbout 0:ea44dc9ed014 124 for (size_t i=0; i<size_; ++i) {
joeverbout 0:ea44dc9ed014 125 for (size_t j=0; j<dim_; ++j) {
joeverbout 0:ea44dc9ed014 126 data_[i][j] = dataset_[vind_[i]][j];
joeverbout 0:ea44dc9ed014 127 }
joeverbout 0:ea44dc9ed014 128 }
joeverbout 0:ea44dc9ed014 129 }
joeverbout 0:ea44dc9ed014 130 else {
joeverbout 0:ea44dc9ed014 131 data_ = dataset_;
joeverbout 0:ea44dc9ed014 132 }
joeverbout 0:ea44dc9ed014 133 }
joeverbout 0:ea44dc9ed014 134
joeverbout 0:ea44dc9ed014 135 flann_algorithm_t getType() const
joeverbout 0:ea44dc9ed014 136 {
joeverbout 0:ea44dc9ed014 137 return FLANN_INDEX_KDTREE_SINGLE;
joeverbout 0:ea44dc9ed014 138 }
joeverbout 0:ea44dc9ed014 139
joeverbout 0:ea44dc9ed014 140
joeverbout 0:ea44dc9ed014 141 void saveIndex(FILE* stream)
joeverbout 0:ea44dc9ed014 142 {
joeverbout 0:ea44dc9ed014 143 save_value(stream, size_);
joeverbout 0:ea44dc9ed014 144 save_value(stream, dim_);
joeverbout 0:ea44dc9ed014 145 save_value(stream, root_bbox_);
joeverbout 0:ea44dc9ed014 146 save_value(stream, reorder_);
joeverbout 0:ea44dc9ed014 147 save_value(stream, leaf_max_size_);
joeverbout 0:ea44dc9ed014 148 save_value(stream, vind_);
joeverbout 0:ea44dc9ed014 149 if (reorder_) {
joeverbout 0:ea44dc9ed014 150 save_value(stream, data_);
joeverbout 0:ea44dc9ed014 151 }
joeverbout 0:ea44dc9ed014 152 save_tree(stream, root_node_);
joeverbout 0:ea44dc9ed014 153 }
joeverbout 0:ea44dc9ed014 154
joeverbout 0:ea44dc9ed014 155
joeverbout 0:ea44dc9ed014 156 void loadIndex(FILE* stream)
joeverbout 0:ea44dc9ed014 157 {
joeverbout 0:ea44dc9ed014 158 load_value(stream, size_);
joeverbout 0:ea44dc9ed014 159 load_value(stream, dim_);
joeverbout 0:ea44dc9ed014 160 load_value(stream, root_bbox_);
joeverbout 0:ea44dc9ed014 161 load_value(stream, reorder_);
joeverbout 0:ea44dc9ed014 162 load_value(stream, leaf_max_size_);
joeverbout 0:ea44dc9ed014 163 load_value(stream, vind_);
joeverbout 0:ea44dc9ed014 164 if (reorder_) {
joeverbout 0:ea44dc9ed014 165 load_value(stream, data_);
joeverbout 0:ea44dc9ed014 166 }
joeverbout 0:ea44dc9ed014 167 else {
joeverbout 0:ea44dc9ed014 168 data_ = dataset_;
joeverbout 0:ea44dc9ed014 169 }
joeverbout 0:ea44dc9ed014 170 load_tree(stream, root_node_);
joeverbout 0:ea44dc9ed014 171
joeverbout 0:ea44dc9ed014 172
joeverbout 0:ea44dc9ed014 173 index_params_["algorithm"] = getType();
joeverbout 0:ea44dc9ed014 174 index_params_["leaf_max_size"] = leaf_max_size_;
joeverbout 0:ea44dc9ed014 175 index_params_["reorder"] = reorder_;
joeverbout 0:ea44dc9ed014 176 }
joeverbout 0:ea44dc9ed014 177
joeverbout 0:ea44dc9ed014 178 /**
joeverbout 0:ea44dc9ed014 179 * Returns size of index.
joeverbout 0:ea44dc9ed014 180 */
joeverbout 0:ea44dc9ed014 181 size_t size() const
joeverbout 0:ea44dc9ed014 182 {
joeverbout 0:ea44dc9ed014 183 return size_;
joeverbout 0:ea44dc9ed014 184 }
joeverbout 0:ea44dc9ed014 185
joeverbout 0:ea44dc9ed014 186 /**
joeverbout 0:ea44dc9ed014 187 * Returns the length of an index feature.
joeverbout 0:ea44dc9ed014 188 */
joeverbout 0:ea44dc9ed014 189 size_t veclen() const
joeverbout 0:ea44dc9ed014 190 {
joeverbout 0:ea44dc9ed014 191 return dim_;
joeverbout 0:ea44dc9ed014 192 }
joeverbout 0:ea44dc9ed014 193
joeverbout 0:ea44dc9ed014 194 /**
joeverbout 0:ea44dc9ed014 195 * Computes the inde memory usage
joeverbout 0:ea44dc9ed014 196 * Returns: memory used by the index
joeverbout 0:ea44dc9ed014 197 */
joeverbout 0:ea44dc9ed014 198 int usedMemory() const
joeverbout 0:ea44dc9ed014 199 {
joeverbout 0:ea44dc9ed014 200 return (int)(pool_.usedMemory+pool_.wastedMemory+dataset_.rows*sizeof(int)); // pool memory and vind array memory
joeverbout 0:ea44dc9ed014 201 }
joeverbout 0:ea44dc9ed014 202
joeverbout 0:ea44dc9ed014 203
joeverbout 0:ea44dc9ed014 204 /**
joeverbout 0:ea44dc9ed014 205 * \brief Perform k-nearest neighbor search
joeverbout 0:ea44dc9ed014 206 * \param[in] queries The query points for which to find the nearest neighbors
joeverbout 0:ea44dc9ed014 207 * \param[out] indices The indices of the nearest neighbors found
joeverbout 0:ea44dc9ed014 208 * \param[out] dists Distances to the nearest neighbors found
joeverbout 0:ea44dc9ed014 209 * \param[in] knn Number of nearest neighbors to return
joeverbout 0:ea44dc9ed014 210 * \param[in] params Search parameters
joeverbout 0:ea44dc9ed014 211 */
joeverbout 0:ea44dc9ed014 212 void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
joeverbout 0:ea44dc9ed014 213 {
joeverbout 0:ea44dc9ed014 214 assert(queries.cols == veclen());
joeverbout 0:ea44dc9ed014 215 assert(indices.rows >= queries.rows);
joeverbout 0:ea44dc9ed014 216 assert(dists.rows >= queries.rows);
joeverbout 0:ea44dc9ed014 217 assert(int(indices.cols) >= knn);
joeverbout 0:ea44dc9ed014 218 assert(int(dists.cols) >= knn);
joeverbout 0:ea44dc9ed014 219
joeverbout 0:ea44dc9ed014 220 KNNSimpleResultSet<DistanceType> resultSet(knn);
joeverbout 0:ea44dc9ed014 221 for (size_t i = 0; i < queries.rows; i++) {
joeverbout 0:ea44dc9ed014 222 resultSet.init(indices[i], dists[i]);
joeverbout 0:ea44dc9ed014 223 findNeighbors(resultSet, queries[i], params);
joeverbout 0:ea44dc9ed014 224 }
joeverbout 0:ea44dc9ed014 225 }
joeverbout 0:ea44dc9ed014 226
joeverbout 0:ea44dc9ed014 227 IndexParams getParameters() const
joeverbout 0:ea44dc9ed014 228 {
joeverbout 0:ea44dc9ed014 229 return index_params_;
joeverbout 0:ea44dc9ed014 230 }
joeverbout 0:ea44dc9ed014 231
joeverbout 0:ea44dc9ed014 232 /**
joeverbout 0:ea44dc9ed014 233 * Find set of nearest neighbors to vec. Their indices are stored inside
joeverbout 0:ea44dc9ed014 234 * the result object.
joeverbout 0:ea44dc9ed014 235 *
joeverbout 0:ea44dc9ed014 236 * Params:
joeverbout 0:ea44dc9ed014 237 * result = the result object in which the indices of the nearest-neighbors are stored
joeverbout 0:ea44dc9ed014 238 * vec = the vector for which to search the nearest neighbors
joeverbout 0:ea44dc9ed014 239 * maxCheck = the maximum number of restarts (in a best-bin-first manner)
joeverbout 0:ea44dc9ed014 240 */
joeverbout 0:ea44dc9ed014 241 void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
joeverbout 0:ea44dc9ed014 242 {
joeverbout 0:ea44dc9ed014 243 float epsError = 1+get_param(searchParams,"eps",0.0f);
joeverbout 0:ea44dc9ed014 244
joeverbout 0:ea44dc9ed014 245 std::vector<DistanceType> dists(dim_,0);
joeverbout 0:ea44dc9ed014 246 DistanceType distsq = computeInitialDistances(vec, dists);
joeverbout 0:ea44dc9ed014 247 searchLevel(result, vec, root_node_, distsq, dists, epsError);
joeverbout 0:ea44dc9ed014 248 }
joeverbout 0:ea44dc9ed014 249
joeverbout 0:ea44dc9ed014 250 private:
joeverbout 0:ea44dc9ed014 251
joeverbout 0:ea44dc9ed014 252
joeverbout 0:ea44dc9ed014 253 /*--------------------- Internal Data Structures --------------------------*/
joeverbout 0:ea44dc9ed014 254 struct Node
joeverbout 0:ea44dc9ed014 255 {
joeverbout 0:ea44dc9ed014 256 /**
joeverbout 0:ea44dc9ed014 257 * Indices of points in leaf node
joeverbout 0:ea44dc9ed014 258 */
joeverbout 0:ea44dc9ed014 259 int left, right;
joeverbout 0:ea44dc9ed014 260 /**
joeverbout 0:ea44dc9ed014 261 * Dimension used for subdivision.
joeverbout 0:ea44dc9ed014 262 */
joeverbout 0:ea44dc9ed014 263 int divfeat;
joeverbout 0:ea44dc9ed014 264 /**
joeverbout 0:ea44dc9ed014 265 * The values used for subdivision.
joeverbout 0:ea44dc9ed014 266 */
joeverbout 0:ea44dc9ed014 267 DistanceType divlow, divhigh;
joeverbout 0:ea44dc9ed014 268 /**
joeverbout 0:ea44dc9ed014 269 * The child nodes.
joeverbout 0:ea44dc9ed014 270 */
joeverbout 0:ea44dc9ed014 271 Node* child1, * child2;
joeverbout 0:ea44dc9ed014 272 };
joeverbout 0:ea44dc9ed014 273 typedef Node* NodePtr;
joeverbout 0:ea44dc9ed014 274
joeverbout 0:ea44dc9ed014 275
joeverbout 0:ea44dc9ed014 276 struct Interval
joeverbout 0:ea44dc9ed014 277 {
joeverbout 0:ea44dc9ed014 278 DistanceType low, high;
joeverbout 0:ea44dc9ed014 279 };
joeverbout 0:ea44dc9ed014 280
joeverbout 0:ea44dc9ed014 281 typedef std::vector<Interval> BoundingBox;
joeverbout 0:ea44dc9ed014 282
joeverbout 0:ea44dc9ed014 283 typedef BranchStruct<NodePtr, DistanceType> BranchSt;
joeverbout 0:ea44dc9ed014 284 typedef BranchSt* Branch;
joeverbout 0:ea44dc9ed014 285
joeverbout 0:ea44dc9ed014 286
joeverbout 0:ea44dc9ed014 287
joeverbout 0:ea44dc9ed014 288
joeverbout 0:ea44dc9ed014 289 void save_tree(FILE* stream, NodePtr tree)
joeverbout 0:ea44dc9ed014 290 {
joeverbout 0:ea44dc9ed014 291 save_value(stream, *tree);
joeverbout 0:ea44dc9ed014 292 if (tree->child1!=NULL) {
joeverbout 0:ea44dc9ed014 293 save_tree(stream, tree->child1);
joeverbout 0:ea44dc9ed014 294 }
joeverbout 0:ea44dc9ed014 295 if (tree->child2!=NULL) {
joeverbout 0:ea44dc9ed014 296 save_tree(stream, tree->child2);
joeverbout 0:ea44dc9ed014 297 }
joeverbout 0:ea44dc9ed014 298 }
joeverbout 0:ea44dc9ed014 299
joeverbout 0:ea44dc9ed014 300
joeverbout 0:ea44dc9ed014 301 void load_tree(FILE* stream, NodePtr& tree)
joeverbout 0:ea44dc9ed014 302 {
joeverbout 0:ea44dc9ed014 303 tree = pool_.allocate<Node>();
joeverbout 0:ea44dc9ed014 304 load_value(stream, *tree);
joeverbout 0:ea44dc9ed014 305 if (tree->child1!=NULL) {
joeverbout 0:ea44dc9ed014 306 load_tree(stream, tree->child1);
joeverbout 0:ea44dc9ed014 307 }
joeverbout 0:ea44dc9ed014 308 if (tree->child2!=NULL) {
joeverbout 0:ea44dc9ed014 309 load_tree(stream, tree->child2);
joeverbout 0:ea44dc9ed014 310 }
joeverbout 0:ea44dc9ed014 311 }
joeverbout 0:ea44dc9ed014 312
joeverbout 0:ea44dc9ed014 313
joeverbout 0:ea44dc9ed014 314 void computeBoundingBox(BoundingBox& bbox)
joeverbout 0:ea44dc9ed014 315 {
joeverbout 0:ea44dc9ed014 316 bbox.resize(dim_);
joeverbout 0:ea44dc9ed014 317 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 318 bbox[i].low = (DistanceType)dataset_[0][i];
joeverbout 0:ea44dc9ed014 319 bbox[i].high = (DistanceType)dataset_[0][i];
joeverbout 0:ea44dc9ed014 320 }
joeverbout 0:ea44dc9ed014 321 for (size_t k=1; k<dataset_.rows; ++k) {
joeverbout 0:ea44dc9ed014 322 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 323 if (dataset_[k][i]<bbox[i].low) bbox[i].low = (DistanceType)dataset_[k][i];
joeverbout 0:ea44dc9ed014 324 if (dataset_[k][i]>bbox[i].high) bbox[i].high = (DistanceType)dataset_[k][i];
joeverbout 0:ea44dc9ed014 325 }
joeverbout 0:ea44dc9ed014 326 }
joeverbout 0:ea44dc9ed014 327 }
joeverbout 0:ea44dc9ed014 328
joeverbout 0:ea44dc9ed014 329
joeverbout 0:ea44dc9ed014 330 /**
joeverbout 0:ea44dc9ed014 331 * Create a tree node that subdivides the list of vecs from vind[first]
joeverbout 0:ea44dc9ed014 332 * to vind[last]. The routine is called recursively on each sublist.
joeverbout 0:ea44dc9ed014 333 * Place a pointer to this new tree node in the location pTree.
joeverbout 0:ea44dc9ed014 334 *
joeverbout 0:ea44dc9ed014 335 * Params: pTree = the new node to create
joeverbout 0:ea44dc9ed014 336 * first = index of the first vector
joeverbout 0:ea44dc9ed014 337 * last = index of the last vector
joeverbout 0:ea44dc9ed014 338 */
joeverbout 0:ea44dc9ed014 339 NodePtr divideTree(int left, int right, BoundingBox& bbox)
joeverbout 0:ea44dc9ed014 340 {
joeverbout 0:ea44dc9ed014 341 NodePtr node = pool_.allocate<Node>(); // allocate memory
joeverbout 0:ea44dc9ed014 342
joeverbout 0:ea44dc9ed014 343 /* If too few exemplars remain, then make this a leaf node. */
joeverbout 0:ea44dc9ed014 344 if ( (right-left) <= leaf_max_size_) {
joeverbout 0:ea44dc9ed014 345 node->child1 = node->child2 = NULL; /* Mark as leaf node. */
joeverbout 0:ea44dc9ed014 346 node->left = left;
joeverbout 0:ea44dc9ed014 347 node->right = right;
joeverbout 0:ea44dc9ed014 348
joeverbout 0:ea44dc9ed014 349 // compute bounding-box of leaf points
joeverbout 0:ea44dc9ed014 350 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 351 bbox[i].low = (DistanceType)dataset_[vind_[left]][i];
joeverbout 0:ea44dc9ed014 352 bbox[i].high = (DistanceType)dataset_[vind_[left]][i];
joeverbout 0:ea44dc9ed014 353 }
joeverbout 0:ea44dc9ed014 354 for (int k=left+1; k<right; ++k) {
joeverbout 0:ea44dc9ed014 355 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 356 if (bbox[i].low>dataset_[vind_[k]][i]) bbox[i].low=(DistanceType)dataset_[vind_[k]][i];
joeverbout 0:ea44dc9ed014 357 if (bbox[i].high<dataset_[vind_[k]][i]) bbox[i].high=(DistanceType)dataset_[vind_[k]][i];
joeverbout 0:ea44dc9ed014 358 }
joeverbout 0:ea44dc9ed014 359 }
joeverbout 0:ea44dc9ed014 360 }
joeverbout 0:ea44dc9ed014 361 else {
joeverbout 0:ea44dc9ed014 362 int idx;
joeverbout 0:ea44dc9ed014 363 int cutfeat;
joeverbout 0:ea44dc9ed014 364 DistanceType cutval;
joeverbout 0:ea44dc9ed014 365 middleSplit_(&vind_[0]+left, right-left, idx, cutfeat, cutval, bbox);
joeverbout 0:ea44dc9ed014 366
joeverbout 0:ea44dc9ed014 367 node->divfeat = cutfeat;
joeverbout 0:ea44dc9ed014 368
joeverbout 0:ea44dc9ed014 369 BoundingBox left_bbox(bbox);
joeverbout 0:ea44dc9ed014 370 left_bbox[cutfeat].high = cutval;
joeverbout 0:ea44dc9ed014 371 node->child1 = divideTree(left, left+idx, left_bbox);
joeverbout 0:ea44dc9ed014 372
joeverbout 0:ea44dc9ed014 373 BoundingBox right_bbox(bbox);
joeverbout 0:ea44dc9ed014 374 right_bbox[cutfeat].low = cutval;
joeverbout 0:ea44dc9ed014 375 node->child2 = divideTree(left+idx, right, right_bbox);
joeverbout 0:ea44dc9ed014 376
joeverbout 0:ea44dc9ed014 377 node->divlow = left_bbox[cutfeat].high;
joeverbout 0:ea44dc9ed014 378 node->divhigh = right_bbox[cutfeat].low;
joeverbout 0:ea44dc9ed014 379
joeverbout 0:ea44dc9ed014 380 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 381 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
joeverbout 0:ea44dc9ed014 382 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
joeverbout 0:ea44dc9ed014 383 }
joeverbout 0:ea44dc9ed014 384 }
joeverbout 0:ea44dc9ed014 385
joeverbout 0:ea44dc9ed014 386 return node;
joeverbout 0:ea44dc9ed014 387 }
joeverbout 0:ea44dc9ed014 388
joeverbout 0:ea44dc9ed014 389 void computeMinMax(int* ind, int count, int dim, ElementType& min_elem, ElementType& max_elem)
joeverbout 0:ea44dc9ed014 390 {
joeverbout 0:ea44dc9ed014 391 min_elem = dataset_[ind[0]][dim];
joeverbout 0:ea44dc9ed014 392 max_elem = dataset_[ind[0]][dim];
joeverbout 0:ea44dc9ed014 393 for (int i=1; i<count; ++i) {
joeverbout 0:ea44dc9ed014 394 ElementType val = dataset_[ind[i]][dim];
joeverbout 0:ea44dc9ed014 395 if (val<min_elem) min_elem = val;
joeverbout 0:ea44dc9ed014 396 if (val>max_elem) max_elem = val;
joeverbout 0:ea44dc9ed014 397 }
joeverbout 0:ea44dc9ed014 398 }
joeverbout 0:ea44dc9ed014 399
joeverbout 0:ea44dc9ed014 400 void middleSplit(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
joeverbout 0:ea44dc9ed014 401 {
joeverbout 0:ea44dc9ed014 402 // find the largest span from the approximate bounding box
joeverbout 0:ea44dc9ed014 403 ElementType max_span = bbox[0].high-bbox[0].low;
joeverbout 0:ea44dc9ed014 404 cutfeat = 0;
joeverbout 0:ea44dc9ed014 405 cutval = (bbox[0].high+bbox[0].low)/2;
joeverbout 0:ea44dc9ed014 406 for (size_t i=1; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 407 ElementType span = bbox[i].high-bbox[i].low;
joeverbout 0:ea44dc9ed014 408 if (span>max_span) {
joeverbout 0:ea44dc9ed014 409 max_span = span;
joeverbout 0:ea44dc9ed014 410 cutfeat = i;
joeverbout 0:ea44dc9ed014 411 cutval = (bbox[i].high+bbox[i].low)/2;
joeverbout 0:ea44dc9ed014 412 }
joeverbout 0:ea44dc9ed014 413 }
joeverbout 0:ea44dc9ed014 414
joeverbout 0:ea44dc9ed014 415 // compute exact span on the found dimension
joeverbout 0:ea44dc9ed014 416 ElementType min_elem, max_elem;
joeverbout 0:ea44dc9ed014 417 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
joeverbout 0:ea44dc9ed014 418 cutval = (min_elem+max_elem)/2;
joeverbout 0:ea44dc9ed014 419 max_span = max_elem - min_elem;
joeverbout 0:ea44dc9ed014 420
joeverbout 0:ea44dc9ed014 421 // check if a dimension of a largest span exists
joeverbout 0:ea44dc9ed014 422 size_t k = cutfeat;
joeverbout 0:ea44dc9ed014 423 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 424 if (i==k) continue;
joeverbout 0:ea44dc9ed014 425 ElementType span = bbox[i].high-bbox[i].low;
joeverbout 0:ea44dc9ed014 426 if (span>max_span) {
joeverbout 0:ea44dc9ed014 427 computeMinMax(ind, count, i, min_elem, max_elem);
joeverbout 0:ea44dc9ed014 428 span = max_elem - min_elem;
joeverbout 0:ea44dc9ed014 429 if (span>max_span) {
joeverbout 0:ea44dc9ed014 430 max_span = span;
joeverbout 0:ea44dc9ed014 431 cutfeat = i;
joeverbout 0:ea44dc9ed014 432 cutval = (min_elem+max_elem)/2;
joeverbout 0:ea44dc9ed014 433 }
joeverbout 0:ea44dc9ed014 434 }
joeverbout 0:ea44dc9ed014 435 }
joeverbout 0:ea44dc9ed014 436 int lim1, lim2;
joeverbout 0:ea44dc9ed014 437 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
joeverbout 0:ea44dc9ed014 438
joeverbout 0:ea44dc9ed014 439 if (lim1>count/2) index = lim1;
joeverbout 0:ea44dc9ed014 440 else if (lim2<count/2) index = lim2;
joeverbout 0:ea44dc9ed014 441 else index = count/2;
joeverbout 0:ea44dc9ed014 442 }
joeverbout 0:ea44dc9ed014 443
joeverbout 0:ea44dc9ed014 444
joeverbout 0:ea44dc9ed014 445 void middleSplit_(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
joeverbout 0:ea44dc9ed014 446 {
joeverbout 0:ea44dc9ed014 447 const float EPS=0.00001f;
joeverbout 0:ea44dc9ed014 448 DistanceType max_span = bbox[0].high-bbox[0].low;
joeverbout 0:ea44dc9ed014 449 for (size_t i=1; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 450 DistanceType span = bbox[i].high-bbox[i].low;
joeverbout 0:ea44dc9ed014 451 if (span>max_span) {
joeverbout 0:ea44dc9ed014 452 max_span = span;
joeverbout 0:ea44dc9ed014 453 }
joeverbout 0:ea44dc9ed014 454 }
joeverbout 0:ea44dc9ed014 455 DistanceType max_spread = -1;
joeverbout 0:ea44dc9ed014 456 cutfeat = 0;
joeverbout 0:ea44dc9ed014 457 for (size_t i=0; i<dim_; ++i) {
joeverbout 0:ea44dc9ed014 458 DistanceType span = bbox[i].high-bbox[i].low;
joeverbout 0:ea44dc9ed014 459 if (span>(DistanceType)((1-EPS)*max_span)) {
joeverbout 0:ea44dc9ed014 460 ElementType min_elem, max_elem;
joeverbout 0:ea44dc9ed014 461 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
joeverbout 0:ea44dc9ed014 462 DistanceType spread = (DistanceType)(max_elem-min_elem);
joeverbout 0:ea44dc9ed014 463 if (spread>max_spread) {
joeverbout 0:ea44dc9ed014 464 cutfeat = (int)i;
joeverbout 0:ea44dc9ed014 465 max_spread = spread;
joeverbout 0:ea44dc9ed014 466 }
joeverbout 0:ea44dc9ed014 467 }
joeverbout 0:ea44dc9ed014 468 }
joeverbout 0:ea44dc9ed014 469 // split in the middle
joeverbout 0:ea44dc9ed014 470 DistanceType split_val = (bbox[cutfeat].low+bbox[cutfeat].high)/2;
joeverbout 0:ea44dc9ed014 471 ElementType min_elem, max_elem;
joeverbout 0:ea44dc9ed014 472 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
joeverbout 0:ea44dc9ed014 473
joeverbout 0:ea44dc9ed014 474 if (split_val<min_elem) cutval = (DistanceType)min_elem;
joeverbout 0:ea44dc9ed014 475 else if (split_val>max_elem) cutval = (DistanceType)max_elem;
joeverbout 0:ea44dc9ed014 476 else cutval = split_val;
joeverbout 0:ea44dc9ed014 477
joeverbout 0:ea44dc9ed014 478 int lim1, lim2;
joeverbout 0:ea44dc9ed014 479 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
joeverbout 0:ea44dc9ed014 480
joeverbout 0:ea44dc9ed014 481 if (lim1>count/2) index = lim1;
joeverbout 0:ea44dc9ed014 482 else if (lim2<count/2) index = lim2;
joeverbout 0:ea44dc9ed014 483 else index = count/2;
joeverbout 0:ea44dc9ed014 484 }
joeverbout 0:ea44dc9ed014 485
joeverbout 0:ea44dc9ed014 486
joeverbout 0:ea44dc9ed014 487 /**
joeverbout 0:ea44dc9ed014 488 * Subdivide the list of points by a plane perpendicular on axe corresponding
joeverbout 0:ea44dc9ed014 489 * to the 'cutfeat' dimension at 'cutval' position.
joeverbout 0:ea44dc9ed014 490 *
joeverbout 0:ea44dc9ed014 491 * On return:
joeverbout 0:ea44dc9ed014 492 * dataset[ind[0..lim1-1]][cutfeat]<cutval
joeverbout 0:ea44dc9ed014 493 * dataset[ind[lim1..lim2-1]][cutfeat]==cutval
joeverbout 0:ea44dc9ed014 494 * dataset[ind[lim2..count]][cutfeat]>cutval
joeverbout 0:ea44dc9ed014 495 */
joeverbout 0:ea44dc9ed014 496 void planeSplit(int* ind, int count, int cutfeat, DistanceType cutval, int& lim1, int& lim2)
joeverbout 0:ea44dc9ed014 497 {
joeverbout 0:ea44dc9ed014 498 /* Move vector indices for left subtree to front of list. */
joeverbout 0:ea44dc9ed014 499 int left = 0;
joeverbout 0:ea44dc9ed014 500 int right = count-1;
joeverbout 0:ea44dc9ed014 501 for (;; ) {
joeverbout 0:ea44dc9ed014 502 while (left<=right && dataset_[ind[left]][cutfeat]<cutval) ++left;
joeverbout 0:ea44dc9ed014 503 while (left<=right && dataset_[ind[right]][cutfeat]>=cutval) --right;
joeverbout 0:ea44dc9ed014 504 if (left>right) break;
joeverbout 0:ea44dc9ed014 505 std::swap(ind[left], ind[right]); ++left; --right;
joeverbout 0:ea44dc9ed014 506 }
joeverbout 0:ea44dc9ed014 507 /* If either list is empty, it means that all remaining features
joeverbout 0:ea44dc9ed014 508 * are identical. Split in the middle to maintain a balanced tree.
joeverbout 0:ea44dc9ed014 509 */
joeverbout 0:ea44dc9ed014 510 lim1 = left;
joeverbout 0:ea44dc9ed014 511 right = count-1;
joeverbout 0:ea44dc9ed014 512 for (;; ) {
joeverbout 0:ea44dc9ed014 513 while (left<=right && dataset_[ind[left]][cutfeat]<=cutval) ++left;
joeverbout 0:ea44dc9ed014 514 while (left<=right && dataset_[ind[right]][cutfeat]>cutval) --right;
joeverbout 0:ea44dc9ed014 515 if (left>right) break;
joeverbout 0:ea44dc9ed014 516 std::swap(ind[left], ind[right]); ++left; --right;
joeverbout 0:ea44dc9ed014 517 }
joeverbout 0:ea44dc9ed014 518 lim2 = left;
joeverbout 0:ea44dc9ed014 519 }
joeverbout 0:ea44dc9ed014 520
joeverbout 0:ea44dc9ed014 521 DistanceType computeInitialDistances(const ElementType* vec, std::vector<DistanceType>& dists)
joeverbout 0:ea44dc9ed014 522 {
joeverbout 0:ea44dc9ed014 523 DistanceType distsq = 0.0;
joeverbout 0:ea44dc9ed014 524
joeverbout 0:ea44dc9ed014 525 for (size_t i = 0; i < dim_; ++i) {
joeverbout 0:ea44dc9ed014 526 if (vec[i] < root_bbox_[i].low) {
joeverbout 0:ea44dc9ed014 527 dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].low, (int)i);
joeverbout 0:ea44dc9ed014 528 distsq += dists[i];
joeverbout 0:ea44dc9ed014 529 }
joeverbout 0:ea44dc9ed014 530 if (vec[i] > root_bbox_[i].high) {
joeverbout 0:ea44dc9ed014 531 dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].high, (int)i);
joeverbout 0:ea44dc9ed014 532 distsq += dists[i];
joeverbout 0:ea44dc9ed014 533 }
joeverbout 0:ea44dc9ed014 534 }
joeverbout 0:ea44dc9ed014 535
joeverbout 0:ea44dc9ed014 536 return distsq;
joeverbout 0:ea44dc9ed014 537 }
joeverbout 0:ea44dc9ed014 538
joeverbout 0:ea44dc9ed014 539 /**
joeverbout 0:ea44dc9ed014 540 * Performs an exact search in the tree starting from a node.
joeverbout 0:ea44dc9ed014 541 */
joeverbout 0:ea44dc9ed014 542 void searchLevel(ResultSet<DistanceType>& result_set, const ElementType* vec, const NodePtr node, DistanceType mindistsq,
joeverbout 0:ea44dc9ed014 543 std::vector<DistanceType>& dists, const float epsError)
joeverbout 0:ea44dc9ed014 544 {
joeverbout 0:ea44dc9ed014 545 /* If this is a leaf node, then do check and return. */
joeverbout 0:ea44dc9ed014 546 if ((node->child1 == NULL)&&(node->child2 == NULL)) {
joeverbout 0:ea44dc9ed014 547 DistanceType worst_dist = result_set.worstDist();
joeverbout 0:ea44dc9ed014 548 for (int i=node->left; i<node->right; ++i) {
joeverbout 0:ea44dc9ed014 549 int index = reorder_ ? i : vind_[i];
joeverbout 0:ea44dc9ed014 550 DistanceType dist = distance_(vec, data_[index], dim_, worst_dist);
joeverbout 0:ea44dc9ed014 551 if (dist<worst_dist) {
joeverbout 0:ea44dc9ed014 552 result_set.addPoint(dist,vind_[i]);
joeverbout 0:ea44dc9ed014 553 }
joeverbout 0:ea44dc9ed014 554 }
joeverbout 0:ea44dc9ed014 555 return;
joeverbout 0:ea44dc9ed014 556 }
joeverbout 0:ea44dc9ed014 557
joeverbout 0:ea44dc9ed014 558 /* Which child branch should be taken first? */
joeverbout 0:ea44dc9ed014 559 int idx = node->divfeat;
joeverbout 0:ea44dc9ed014 560 ElementType val = vec[idx];
joeverbout 0:ea44dc9ed014 561 DistanceType diff1 = val - node->divlow;
joeverbout 0:ea44dc9ed014 562 DistanceType diff2 = val - node->divhigh;
joeverbout 0:ea44dc9ed014 563
joeverbout 0:ea44dc9ed014 564 NodePtr bestChild;
joeverbout 0:ea44dc9ed014 565 NodePtr otherChild;
joeverbout 0:ea44dc9ed014 566 DistanceType cut_dist;
joeverbout 0:ea44dc9ed014 567 if ((diff1+diff2)<0) {
joeverbout 0:ea44dc9ed014 568 bestChild = node->child1;
joeverbout 0:ea44dc9ed014 569 otherChild = node->child2;
joeverbout 0:ea44dc9ed014 570 cut_dist = distance_.accum_dist(val, node->divhigh, idx);
joeverbout 0:ea44dc9ed014 571 }
joeverbout 0:ea44dc9ed014 572 else {
joeverbout 0:ea44dc9ed014 573 bestChild = node->child2;
joeverbout 0:ea44dc9ed014 574 otherChild = node->child1;
joeverbout 0:ea44dc9ed014 575 cut_dist = distance_.accum_dist( val, node->divlow, idx);
joeverbout 0:ea44dc9ed014 576 }
joeverbout 0:ea44dc9ed014 577
joeverbout 0:ea44dc9ed014 578 /* Call recursively to search next level down. */
joeverbout 0:ea44dc9ed014 579 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
joeverbout 0:ea44dc9ed014 580
joeverbout 0:ea44dc9ed014 581 DistanceType dst = dists[idx];
joeverbout 0:ea44dc9ed014 582 mindistsq = mindistsq + cut_dist - dst;
joeverbout 0:ea44dc9ed014 583 dists[idx] = cut_dist;
joeverbout 0:ea44dc9ed014 584 if (mindistsq*epsError<=result_set.worstDist()) {
joeverbout 0:ea44dc9ed014 585 searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError);
joeverbout 0:ea44dc9ed014 586 }
joeverbout 0:ea44dc9ed014 587 dists[idx] = dst;
joeverbout 0:ea44dc9ed014 588 }
joeverbout 0:ea44dc9ed014 589
joeverbout 0:ea44dc9ed014 590 private:
joeverbout 0:ea44dc9ed014 591
joeverbout 0:ea44dc9ed014 592 /**
joeverbout 0:ea44dc9ed014 593 * The dataset used by this index
joeverbout 0:ea44dc9ed014 594 */
joeverbout 0:ea44dc9ed014 595 const Matrix<ElementType> dataset_;
joeverbout 0:ea44dc9ed014 596
joeverbout 0:ea44dc9ed014 597 IndexParams index_params_;
joeverbout 0:ea44dc9ed014 598
joeverbout 0:ea44dc9ed014 599 int leaf_max_size_;
joeverbout 0:ea44dc9ed014 600 bool reorder_;
joeverbout 0:ea44dc9ed014 601
joeverbout 0:ea44dc9ed014 602
joeverbout 0:ea44dc9ed014 603 /**
joeverbout 0:ea44dc9ed014 604 * Array of indices to vectors in the dataset.
joeverbout 0:ea44dc9ed014 605 */
joeverbout 0:ea44dc9ed014 606 std::vector<int> vind_;
joeverbout 0:ea44dc9ed014 607
joeverbout 0:ea44dc9ed014 608 Matrix<ElementType> data_;
joeverbout 0:ea44dc9ed014 609
joeverbout 0:ea44dc9ed014 610 size_t size_;
joeverbout 0:ea44dc9ed014 611 size_t dim_;
joeverbout 0:ea44dc9ed014 612
joeverbout 0:ea44dc9ed014 613 /**
joeverbout 0:ea44dc9ed014 614 * Array of k-d trees used to find neighbours.
joeverbout 0:ea44dc9ed014 615 */
joeverbout 0:ea44dc9ed014 616 NodePtr root_node_;
joeverbout 0:ea44dc9ed014 617
joeverbout 0:ea44dc9ed014 618 BoundingBox root_bbox_;
joeverbout 0:ea44dc9ed014 619
joeverbout 0:ea44dc9ed014 620 /**
joeverbout 0:ea44dc9ed014 621 * Pooled memory allocator.
joeverbout 0:ea44dc9ed014 622 *
joeverbout 0:ea44dc9ed014 623 * Using a pooled memory allocator is more efficient
joeverbout 0:ea44dc9ed014 624 * than allocating memory directly when there is a large
joeverbout 0:ea44dc9ed014 625 * number small of memory allocations.
joeverbout 0:ea44dc9ed014 626 */
joeverbout 0:ea44dc9ed014 627 PooledAllocator pool_;
joeverbout 0:ea44dc9ed014 628
joeverbout 0:ea44dc9ed014 629 Distance distance_;
joeverbout 0:ea44dc9ed014 630 }; // class KDTree
joeverbout 0:ea44dc9ed014 631
joeverbout 0:ea44dc9ed014 632 }
joeverbout 0:ea44dc9ed014 633
joeverbout 0:ea44dc9ed014 634 #endif //OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
joeverbout 0:ea44dc9ed014 635