Renesas / opencv-lib

openCV library for Renesas RZ/A

Dependents:   RZ_A2M_Mbed_samples

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