Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

include/opencv2/flann/kdtree_index.h@0:0e0631af0305, 2021-01-29 (annotated)

Committer:
RyoheiHagimoto
Date:
Fri Jan 29 04:53:38 2021 +0000
Revision:
0:0e0631af0305
copied from https://github.com/d-kato/opencv-lib.

Who changed what in which revision?

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