kdtree_index.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  *
7  * THE BSD LICENSE
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  *************************************************************************/
30 
31 #ifndef RTABMAP_FLANN_KDTREE_INDEX_H_
32 #define RTABMAP_FLANN_KDTREE_INDEX_H_
33 
34 #include <algorithm>
35 #include <map>
36 #include <cassert>
37 #include <cstring>
38 #include <stdarg.h>
39 #include <cmath>
40 #include <random>
41 
42 #include "rtflann/general.h"
45 #include "rtflann/util/matrix.h"
47 #include "rtflann/util/heap.h"
48 #include "rtflann/util/allocator.h"
49 #include "rtflann/util/random.h"
50 #include "rtflann/util/saving.h"
51 
52 
53 namespace rtflann
54 {
55 
56 struct KDTreeIndexParams : public IndexParams
57 {
58  KDTreeIndexParams(int trees = 4)
59  {
60  (*this)["algorithm"] = FLANN_INDEX_KDTREE;
61  (*this)["trees"] = trees;
62  }
63 };
64 
65 
72 template <typename Distance>
73 class KDTreeIndex : public NNIndex<Distance>
74 {
75 public:
76  typedef typename Distance::ElementType ElementType;
77  typedef typename Distance::ResultType DistanceType;
78 
79  typedef NNIndex<Distance> BaseClass;
80 
81  typedef bool needs_kdtree_distance;
82 
83 private:
84  /*--------------------- Internal Data Structures --------------------------*/
85  struct Node
86  {
90  int divfeat;
102  Node* child1, *child2;
103  Node(){
106  }
107  ~Node() {
108  if (child1 != NULL) { child1->~Node(); child1 = NULL; }
109 
110  if (child2 != NULL) { child2->~Node(); child2 = NULL; }
111  }
112 
113  private:
114  template<typename Archive>
115  void serialize(Archive& ar)
116  {
118  Index* obj = static_cast<Index*>(ar.getObject());
119 
120  ar & divfeat;
121  ar & divval;
122 
123  bool leaf_node = false;
124  if (Archive::is_saving::value) {
125  leaf_node = ((child1==NULL) && (child2==NULL));
126  }
127  ar & leaf_node;
128 
129  if (leaf_node) {
130  if (Archive::is_loading::value) {
131  point = obj->points_[divfeat];
132  }
133  }
134 
135  if (!leaf_node) {
136  if (Archive::is_loading::value) {
137  child1 = new(obj->pool_) Node();
138  child2 = new(obj->pool_) Node();
139  }
140  ar & *child1;
141  ar & *child2;
142  }
143  }
144  friend struct serialization::access;
145  };
146 
147  typedef Node* NodePtr;
149  typedef BranchSt* Branch;
150 
151 public:
152 
160  KDTreeIndex(const IndexParams& params = KDTreeIndexParams(), Distance d = Distance() ) :
162  {
163  trees_ = get_param(index_params_,"trees",4);
164  }
165 
166 
174  KDTreeIndex(const Matrix<ElementType>& dataset, const IndexParams& params = KDTreeIndexParams(),
175  Distance d = Distance() ) : BaseClass(params,d ), mean_(NULL), var_(NULL)
176  {
178 
179  setDataset(dataset);
180  }
181 
182  KDTreeIndex(const KDTreeIndex& other) : BaseClass(other),
184  {
185  tree_roots_.resize(other.tree_roots_.size());
186  for (size_t i=0;i<tree_roots_.size();++i) {
187  copyTree(tree_roots_[i], other.tree_roots_[i]);
188  }
189  }
190 
192  {
193  this->swap(other);
194  return *this;
195  }
196 
200  virtual ~KDTreeIndex()
201  {
203  }
204 
205  BaseClass* clone() const
206  {
207  return new KDTreeIndex(*this);
208  }
209 
211 
212  void addPoints(const Matrix<ElementType>& points, float rebuild_threshold = 2)
213  {
214  assert(points.cols==veclen_);
215 
216  size_t old_size = size_;
217  extendDataset(points);
218 
219  if (rebuild_threshold>1 && size_at_build_*rebuild_threshold<size_) {
220  buildIndex();
221  }
222  else {
223  for (size_t i=old_size;i<size_;++i) {
224  for (int j = 0; j < trees_; j++) {
226  }
227  }
228  }
229  }
230 
231  flann_algorithm_t getType() const
232  {
234  }
235 
236 
237  template<typename Archive>
238  void serialize(Archive& ar)
239  {
240  ar.setObject(this);
241 
242  ar & *static_cast<NNIndex<Distance>*>(this);
243 
244  ar & trees_;
245 
246  if (Archive::is_loading::value) {
247  tree_roots_.resize(trees_);
248  }
249  for (size_t i=0;i<tree_roots_.size();++i) {
250  if (Archive::is_loading::value) {
251  tree_roots_[i] = new(pool_) Node();
252  }
253  ar & *tree_roots_[i];
254  }
255 
256  if (Archive::is_loading::value) {
257  index_params_["algorithm"] = getType();
258  index_params_["trees"] = trees_;
259  }
260  }
261 
262 
263  void saveIndex(FILE* stream)
264  {
265  serialization::SaveArchive sa(stream);
266  sa & *this;
267  }
268 
269 
270  void loadIndex(FILE* stream)
271  {
272  freeIndex();
274  la & *this;
275  }
276 
281  int usedMemory() const
282  {
283  return int(pool_.usedMemory+pool_.wastedMemory+size_*sizeof(int)); // pool memory and vind array memory
284  }
285 
295  void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) const
296  {
297  int maxChecks = searchParams.checks;
298  float epsError = 1+searchParams.eps;
299 
300  if (maxChecks==FLANN_CHECKS_UNLIMITED) {
301  if (removed_) {
302  getExactNeighbors<true>(result, vec, epsError);
303  }
304  else {
305  getExactNeighbors<false>(result, vec, epsError);
306  }
307  }
308  else {
309  if (removed_) {
310  getNeighbors<true>(result, vec, maxChecks, epsError);
311  }
312  else {
313  getNeighbors<false>(result, vec, maxChecks, epsError);
314  }
315  }
316  }
317 
318 #ifdef FLANN_KDTREE_MEM_OPT
319 
329  void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams, Heap<BranchSt>* heap) const
330  {
331  int maxChecks = searchParams.checks;
332  float epsError = 1+searchParams.eps;
333 
334  if (maxChecks==FLANN_CHECKS_UNLIMITED) {
335  if (removed_) {
336  getExactNeighbors<true>(result, vec, epsError);
337  }
338  else {
339  getExactNeighbors<false>(result, vec, epsError);
340  }
341  }
342  else {
343  if (removed_) {
344  getNeighbors<true>(result, vec, maxChecks, epsError, heap);
345  }
346  else {
347  getNeighbors<false>(result, vec, maxChecks, epsError, heap);
348  }
349  }
350  }
351 
360  virtual int knnSearch(const Matrix<ElementType>& queries,
361  Matrix<size_t>& indices,
362  Matrix<DistanceType>& dists,
363  size_t knn,
364  const SearchParams& params) const
365  {
366  assert(queries.cols == veclen_);
367  assert(indices.rows >= queries.rows);
368  assert(dists.rows >= queries.rows);
369  assert(indices.cols >= knn);
370  assert(dists.cols >= knn);
371  bool use_heap;
372 
373  if (params.use_heap==FLANN_Undefined) {
374  use_heap = (knn>KNN_HEAP_THRESHOLD)?true:false;
375  }
376  else {
377  use_heap = (params.use_heap==FLANN_True)?true:false;
378  }
379  int count = 0;
380 
381  Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
382 
383  if (use_heap) {
384  //#pragma omp parallel num_threads(params.cores)
385  {
386  KNNResultSet2<DistanceType> resultSet(knn);
387  //#pragma omp for schedule(static) reduction(+:count)
388  for (int i = 0; i < (int)queries.rows; i++) {
389  resultSet.clear();
390  findNeighbors(resultSet, queries[i], params, heap);
391  size_t n = std::min(resultSet.size(), knn);
392  resultSet.copy(indices[i], dists[i], n, params.sorted);
393  indices_to_ids(indices[i], indices[i], n);
394  count += n;
395  }
396  }
397  }
398  else {
399  std::vector<double> times(queries.rows);
400  //#pragma omp parallel num_threads(params.cores)
401  {
402  KNNSimpleResultSet<DistanceType> resultSet(knn);
403  //#pragma omp for schedule(static) reduction(+:count)
404  for (int i = 0; i < (int)queries.rows; i++) {
405  resultSet.clear();
406  findNeighbors(resultSet, queries[i], params, heap);
407  size_t n = std::min(resultSet.size(), knn);
408  resultSet.copy(indices[i], dists[i], n, params.sorted);
409  indices_to_ids(indices[i], indices[i], n);
410  count += n;
411  }
412  }
413  std::sort(times.begin(), times.end());
414  }
415  delete heap;
416  return count;
417  }
418 
419 
428  virtual int knnSearch(const Matrix<ElementType>& queries,
429  std::vector< std::vector<size_t> >& indices,
430  std::vector<std::vector<DistanceType> >& dists,
431  size_t knn,
432  const SearchParams& params) const
433  {
434  assert(queries.cols == veclen_);
435  bool use_heap;
436  if (params.use_heap==FLANN_Undefined) {
437  use_heap = (knn>KNN_HEAP_THRESHOLD)?true:false;
438  }
439  else {
440  use_heap = (params.use_heap==FLANN_True)?true:false;
441  }
442 
443  if (indices.size() < queries.rows ) indices.resize(queries.rows);
444  if (dists.size() < queries.rows ) dists.resize(queries.rows);
445 
446  Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
447 
448  int count = 0;
449  if (use_heap) {
450  //#pragma omp parallel num_threads(params.cores)
451  {
452  KNNResultSet2<DistanceType> resultSet(knn);
453  //#pragma omp for schedule(static) reduction(+:count)
454  for (int i = 0; i < (int)queries.rows; i++) {
455  resultSet.clear();
456  findNeighbors(resultSet, queries[i], params, heap);
457  size_t n = std::min(resultSet.size(), knn);
458  indices[i].resize(n);
459  dists[i].resize(n);
460  if (n>0) {
461  resultSet.copy(&indices[i][0], &dists[i][0], n, params.sorted);
462  indices_to_ids(&indices[i][0], &indices[i][0], n);
463  }
464  count += n;
465  }
466  }
467  }
468  else {
469  //#pragma omp parallel num_threads(params.cores)
470  {
471  KNNSimpleResultSet<DistanceType> resultSet(knn);
472  //#pragma omp for schedule(static) reduction(+:count)
473  for (int i = 0; i < (int)queries.rows; i++) {
474  resultSet.clear();
475  findNeighbors(resultSet, queries[i], params, heap);
476  size_t n = std::min(resultSet.size(), knn);
477  indices[i].resize(n);
478  dists[i].resize(n);
479  if (n>0) {
480  resultSet.copy(&indices[i][0], &dists[i][0], n, params.sorted);
481  indices_to_ids(&indices[i][0], &indices[i][0], n);
482  }
483  count += n;
484  }
485  }
486  }
487  delete heap;
488 
489  return count;
490  }
491 
501  virtual int radiusSearch(const Matrix<ElementType>& queries,
502  Matrix<size_t>& indices,
503  Matrix<DistanceType>& dists,
504  float radius,
505  const SearchParams& params) const
506  {
507  assert(queries.cols == veclen);
508  int count = 0;
509  size_t num_neighbors = std::min(indices.cols, dists.cols);
510  int max_neighbors = params.max_neighbors;
511  if (max_neighbors<0) max_neighbors = num_neighbors;
512  else max_neighbors = std::min(max_neighbors,(int)num_neighbors);
513 
514  Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
515 
516  if (max_neighbors==0) {
517  //#pragma omp parallel num_threads(params.cores)
518  {
519  CountRadiusResultSet<DistanceType> resultSet(radius);
520  //#pragma omp for schedule(static) reduction(+:count)
521  for (int i = 0; i < (int)queries.rows; i++) {
522  resultSet.clear();
523  findNeighbors(resultSet, queries[i], params, heap);
524  count += resultSet.size();
525  }
526  }
527  }
528  else {
529  // explicitly indicated to use unbounded radius result set
530  // and we know there'll be enough room for resulting indices and dists
531  if (params.max_neighbors<0 && (num_neighbors>=this->size())) {
532  //#pragma omp parallel num_threads(params.cores)
533  {
534  RadiusResultSet<DistanceType> resultSet(radius);
535  //#pragma omp for schedule(static) reduction(+:count)
536  for (int i = 0; i < (int)queries.rows; i++) {
537  resultSet.clear();
538  findNeighbors(resultSet, queries[i], params, heap);
539  size_t n = resultSet.size();
540  count += n;
541  if (n>num_neighbors) n = num_neighbors;
542  resultSet.copy(indices[i], dists[i], n, params.sorted);
543 
544  // mark the next element in the output buffers as unused
545  if (n<indices.cols) indices[i][n] = size_t(-1);
546  if (n<dists.cols) dists[i][n] = std::numeric_limits<DistanceType>::infinity();
547  indices_to_ids(indices[i], indices[i], n);
548  }
549  }
550  }
551  else {
552  // number of neighbors limited to max_neighbors
553  //#pragma omp parallel num_threads(params.cores)
554  {
555  KNNRadiusResultSet<DistanceType> resultSet(radius, max_neighbors);
556  //#pragma omp for schedule(static) reduction(+:count)
557  for (int i = 0; i < (int)queries.rows; i++) {
558  resultSet.clear();
559  findNeighbors(resultSet, queries[i], params, heap);
560  size_t n = resultSet.size();
561  count += n;
562  if ((int)n>max_neighbors) n = max_neighbors;
563  resultSet.copy(indices[i], dists[i], n, params.sorted);
564 
565  // mark the next element in the output buffers as unused
566  if (n<indices.cols) indices[i][n] = size_t(-1);
567  if (n<dists.cols) dists[i][n] = std::numeric_limits<DistanceType>::infinity();
568  indices_to_ids(indices[i], indices[i], n);
569  }
570  }
571  }
572  }
573  delete heap;
574  return count;
575  }
576 
586  virtual int radiusSearch(const Matrix<ElementType>& queries,
587  std::vector< std::vector<size_t> >& indices,
588  std::vector<std::vector<DistanceType> >& dists,
589  float radius,
590  const SearchParams& params) const
591  {
592  assert(queries.cols == veclen_);
593  int count = 0;
594 
595  Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
596 
597  // just count neighbors
598  if (params.max_neighbors==0) {
599  //#pragma omp parallel num_threads(params.cores)
600  {
601  CountRadiusResultSet<DistanceType> resultSet(radius);
602  //#pragma omp for schedule(static) reduction(+:count)
603  for (int i = 0; i < (int)queries.rows; i++) {
604  resultSet.clear();
605  findNeighbors(resultSet, queries[i], params, heap);
606  count += resultSet.size();
607  }
608  }
609  }
610  else {
611  if (indices.size() < queries.rows ) indices.resize(queries.rows);
612  if (dists.size() < queries.rows ) dists.resize(queries.rows);
613 
614  if (params.max_neighbors<0) {
615  // search for all neighbors
616  //#pragma omp parallel num_threads(params.cores)
617  {
618  RadiusResultSet<DistanceType> resultSet(radius);
619  //#pragma omp for schedule(static) reduction(+:count)
620  for (int i = 0; i < (int)queries.rows; i++) {
621  resultSet.clear();
622  findNeighbors(resultSet, queries[i], params, heap);
623  size_t n = resultSet.size();
624  count += n;
625  indices[i].resize(n);
626  dists[i].resize(n);
627  if (n > 0) {
628  resultSet.copy(&indices[i][0], &dists[i][0], n, params.sorted);
629  indices_to_ids(&indices[i][0], &indices[i][0], n);
630  }
631  }
632  }
633  }
634  else {
635  // number of neighbors limited to max_neighbors
636  //#pragma omp parallel num_threads(params.cores)
637  {
638  KNNRadiusResultSet<DistanceType> resultSet(radius, params.max_neighbors);
639  //#pragma omp for schedule(static) reduction(+:count)
640  for (int i = 0; i < (int)queries.rows; i++) {
641  resultSet.clear();
642  findNeighbors(resultSet, queries[i], params, heap);
643  size_t n = resultSet.size();
644  count += n;
645  if ((int)n>params.max_neighbors) n = params.max_neighbors;
646  indices[i].resize(n);
647  dists[i].resize(n);
648  if (n > 0) {
649  resultSet.copy(&indices[i][0], &dists[i][0], n, params.sorted);
650  indices_to_ids(&indices[i][0], &indices[i][0], n);
651  }
652  }
653  }
654  }
655  }
656  delete heap;
657  return count;
658  }
659 #endif
660 
661 protected:
662 
666  void buildIndexImpl()
667  {
668  // Create a permutable array of indices to the input vectors.
669  std::vector<int> ind(size_);
670  for (size_t i = 0; i < size_; ++i) {
671  ind[i] = int(i);
672  }
673 
674  mean_ = new DistanceType[veclen_];
675  var_ = new DistanceType[veclen_];
676 
677  tree_roots_.resize(trees_);
678  /* Construct the randomized trees. */
679  for (int i = 0; i < trees_; i++) {
680  /* Randomize the order of vectors to allow for unbiased sampling. */
681  std::random_device rd;
682  std::mt19937 g(rd());
683  std::shuffle(ind.begin(), ind.end(), g);
684  tree_roots_[i] = divideTree(&ind[0], int(size_) );
685  }
686  delete[] mean_;
687  delete[] var_;
688  }
689 
690  void freeIndex()
691  {
692  for (size_t i=0;i<tree_roots_.size();++i) {
693  // using placement new, so call destructor explicitly
694  if (tree_roots_[i]!=NULL) tree_roots_[i]->~Node();
695  }
696  pool_.free();
697  }
698 
699 
700 private:
701 
702  void copyTree(NodePtr& dst, const NodePtr& src)
703  {
704  dst = new(pool_) Node();
705  dst->divfeat = src->divfeat;
706  dst->divval = src->divval;
707  if (src->child1==NULL && src->child2==NULL) {
708  dst->point = points_[dst->divfeat];
709  dst->child1 = NULL;
710  dst->child2 = NULL;
711  }
712  else {
713  copyTree(dst->child1, src->child1);
714  copyTree(dst->child2, src->child2);
715  }
716  }
717 
727  NodePtr divideTree(int* ind, int count)
728  {
729  NodePtr node = new(pool_) Node(); // allocate memory
730 
731  /* If too few exemplars remain, then make this a leaf node. */
732  if (count == 1) {
733  node->child1 = node->child2 = NULL; /* Mark as leaf node. */
734  node->divfeat = *ind; /* Store index of this vec. */
735  node->point = points_[*ind];
736  }
737  else {
738  int idx;
739  int cutfeat;
740  DistanceType cutval;
741  meanSplit(ind, count, idx, cutfeat, cutval);
742 
743  node->divfeat = cutfeat;
744  node->divval = cutval;
745  node->child1 = divideTree(ind, idx);
746  node->child2 = divideTree(ind+idx, count-idx);
747  }
748 
749  return node;
750  }
751 
752 
758  void meanSplit(int* ind, int count, int& index, int& cutfeat, DistanceType& cutval)
759  {
760  memset(mean_,0,veclen_*sizeof(DistanceType));
761  memset(var_,0,veclen_*sizeof(DistanceType));
762 
763  /* Compute mean values. Only the first SAMPLE_MEAN values need to be
764  sampled to get a good estimate.
765  */
766  int cnt = std::min((int)SAMPLE_MEAN+1, count);
767  for (int j = 0; j < cnt; ++j) {
768  ElementType* v = points_[ind[j]];
769  for (size_t k=0; k<veclen_; ++k) {
770  mean_[k] += v[k];
771  }
772  }
773  DistanceType div_factor = DistanceType(1)/cnt;
774  for (size_t k=0; k<veclen_; ++k) {
775  mean_[k] *= div_factor;
776  }
777 
778  /* Compute variances (no need to divide by count). */
779  for (int j = 0; j < cnt; ++j) {
780  ElementType* v = points_[ind[j]];
781  for (size_t k=0; k<veclen_; ++k) {
782  DistanceType dist = v[k] - mean_[k];
783  var_[k] += dist * dist;
784  }
785  }
786  /* Select one of the highest variance indices at random. */
787  cutfeat = selectDivision(var_);
788  cutval = mean_[cutfeat];
789 
790  int lim1, lim2;
791  planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
792 
793  if (lim1>count/2) index = lim1;
794  else if (lim2<count/2) index = lim2;
795  else index = count/2;
796 
797  /* If either list is empty, it means that all remaining features
798  * are identical. Split in the middle to maintain a balanced tree.
799  */
800  if ((lim1==count)||(lim2==0)) index = count/2;
801  }
802 
803 
809  {
810  int num = 0;
811  size_t topind[RAND_DIM];
812 
813  /* Create a list of the indices of the top RAND_DIM values. */
814  for (size_t i = 0; i < veclen_; ++i) {
815  if ((num < RAND_DIM)||(v[i] > v[topind[num-1]])) {
816  /* Put this element at end of topind. */
817  if (num < RAND_DIM) {
818  topind[num++] = i; /* Add to list. */
819  }
820  else {
821  topind[num-1] = i; /* Replace last element. */
822  }
823  /* Bubble end value down to right location by repeated swapping. */
824  int j = num - 1;
825  while (j > 0 && v[topind[j]] > v[topind[j-1]]) {
826  std::swap(topind[j], topind[j-1]);
827  --j;
828  }
829  }
830  }
831  /* Select a random integer in range [0,num-1], and return that index. */
832  int rnd = rand_int(num);
833  return (int)topind[rnd];
834  }
835 
836 
846  void planeSplit(int* ind, int count, int cutfeat, DistanceType cutval, int& lim1, int& lim2)
847  {
848  /* Move vector indices for left subtree to front of list. */
849  int left = 0;
850  int right = count-1;
851  for (;; ) {
852  while (left<=right && points_[ind[left]][cutfeat]<cutval) ++left;
853  while (left<=right && points_[ind[right]][cutfeat]>=cutval) --right;
854  if (left>right) break;
855  std::swap(ind[left], ind[right]); ++left; --right;
856  }
857  lim1 = left;
858  right = count-1;
859  for (;; ) {
860  while (left<=right && points_[ind[left]][cutfeat]<=cutval) ++left;
861  while (left<=right && points_[ind[right]][cutfeat]>cutval) --right;
862  if (left>right) break;
863  std::swap(ind[left], ind[right]); ++left; --right;
864  }
865  lim2 = left;
866  }
867 
872  template<bool with_removed>
873  void getExactNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, float epsError) const
874  {
875  // checkID -= 1; /* Set a different unique ID for each search. */
876 
877  if (trees_ > 1) {
878  fprintf(stderr,"It doesn't make any sense to use more than one tree for exact search");
879  }
880  if (trees_>0) {
881  searchLevelExact<with_removed>(result, vec, tree_roots_[0], 0.0, epsError);
882  }
883  }
884 
890  template<bool with_removed>
891  void getNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, int maxCheck, float epsError) const
892  {
893  int i;
894  BranchSt branch;
895 
896  int checkCount = 0;
897  Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
898  DynamicBitset checked(size_);
899 
900  /* Search once through each tree down to root. */
901  for (i = 0; i < trees_; ++i) {
902  searchLevel<with_removed>(result, vec, tree_roots_[i], 0, checkCount, maxCheck, epsError, heap, checked);
903  }
904 
905  /* Keep searching other branches from heap until finished. */
906  while ( heap->popMin(branch) && (checkCount < maxCheck || !result.full() )) {
907  searchLevel<with_removed>(result, vec, branch.node, branch.mindist, checkCount, maxCheck, epsError, heap, checked);
908  }
909 
910  delete heap;
911 
912  }
913 
914 #ifdef FLANN_KDTREE_MEM_OPT
915 
920  template<bool with_removed>
921  void getNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, int maxCheck, float epsError, Heap<BranchSt>* heap) const
922  {
923  int i;
924  BranchSt branch;
925 
926  int checkCount = 0;
927  DynamicBitset checked(size_);
928  heap->clear();
929 
930  /* Search once through each tree down to root. */
931  for (i = 0; i < trees_; ++i) {
932  searchLevel<with_removed>(result, vec, tree_roots_[i], 0, checkCount, maxCheck, epsError, heap, checked);
933  }
934 
935  /* Keep searching other branches from heap until finished. */
936  while ( heap->popMin(branch) && (checkCount < maxCheck || !result.full() )) {
937  searchLevel<with_removed>(result, vec, branch.node, branch.mindist, checkCount, maxCheck, epsError, heap, checked);
938  }
939  }
940 #endif
941 
942 
948  template<bool with_removed>
949  void searchLevel(ResultSet<DistanceType>& result_set, const ElementType* vec, NodePtr node, DistanceType mindist, int& checkCount, int maxCheck,
950  float epsError, Heap<BranchSt>* heap, DynamicBitset& checked) const
951  {
952  if (result_set.worstDist()<mindist) {
953  // printf("Ignoring branch, too far\n");
954  return;
955  }
956 
957  /* If this is a leaf node, then do check and return. */
958  if ((node->child1 == NULL)&&(node->child2 == NULL)) {
959  int index = node->divfeat;
960  if (with_removed) {
961  if (removed_points_.test(index)) return;
962  }
963  /* Do not check same node more than once when searching multiple trees. */
964  if ( checked.test(index) || ((checkCount>=maxCheck)&& result_set.full()) ) return;
965  checked.set(index);
966  checkCount++;
967 
968  DistanceType dist = distance_(node->point, vec, veclen_);
969  result_set.addPoint(dist,index);
970  return;
971  }
972 
973  /* Which child branch should be taken first? */
974  ElementType val = vec[node->divfeat];
975  DistanceType diff = val - node->divval;
976  NodePtr bestChild = (diff < 0) ? node->child1 : node->child2;
977  NodePtr otherChild = (diff < 0) ? node->child2 : node->child1;
978 
979  /* Create a branch record for the branch not taken. Add distance
980  of this feature boundary (we don't attempt to correct for any
981  use of this feature in a parent node, which is unlikely to
982  happen and would have only a small effect). Don't bother
983  adding more branches to heap after halfway point, as cost of
984  adding exceeds their value.
985  */
986 
987  DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat);
988  // if (2 * checkCount < maxCheck || !result.full()) {
989  if ((new_distsq*epsError < result_set.worstDist())|| !result_set.full()) {
990  heap->insert( BranchSt(otherChild, new_distsq) );
991  }
992 
993  /* Call recursively to search next level down. */
994  searchLevel<with_removed>(result_set, vec, bestChild, mindist, checkCount, maxCheck, epsError, heap, checked);
995  }
996 
1000  template<bool with_removed>
1001  void searchLevelExact(ResultSet<DistanceType>& result_set, const ElementType* vec, const NodePtr node, DistanceType mindist, const float epsError) const
1002  {
1003  /* If this is a leaf node, then do check and return. */
1004  if ((node->child1 == NULL)&&(node->child2 == NULL)) {
1005  int index = node->divfeat;
1006  if (with_removed) {
1007  if (removed_points_.test(index)) return; // ignore removed points
1008  }
1009  DistanceType dist = distance_(node->point, vec, veclen_);
1010  result_set.addPoint(dist,index);
1011 
1012  return;
1013  }
1014 
1015  /* Which child branch should be taken first? */
1016  ElementType val = vec[node->divfeat];
1017  DistanceType diff = val - node->divval;
1018  NodePtr bestChild = (diff < 0) ? node->child1 : node->child2;
1019  NodePtr otherChild = (diff < 0) ? node->child2 : node->child1;
1020 
1021  /* Create a branch record for the branch not taken. Add distance
1022  of this feature boundary (we don't attempt to correct for any
1023  use of this feature in a parent node, which is unlikely to
1024  happen and would have only a small effect). Don't bother
1025  adding more branches to heap after halfway point, as cost of
1026  adding exceeds their value.
1027  */
1028 
1029  DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat);
1030 
1031  /* Call recursively to search next level down. */
1032  searchLevelExact<with_removed>(result_set, vec, bestChild, mindist, epsError);
1033 
1034  if (mindist*epsError<=result_set.worstDist()) {
1035  searchLevelExact<with_removed>(result_set, vec, otherChild, new_distsq, epsError);
1036  }
1037  }
1038 
1039  void addPointToTree(NodePtr node, int ind)
1040  {
1042 
1043  if ((node->child1==NULL) && (node->child2==NULL)) {
1044  ElementType* leaf_point = node->point;
1045  ElementType max_span = 0;
1046  size_t div_feat = 0;
1047  for (size_t i=0;i<veclen_;++i) {
1048  ElementType span = std::abs(point[i]-leaf_point[i]);
1049  if (span > max_span) {
1050  max_span = span;
1051  div_feat = i;
1052  }
1053  }
1054  NodePtr left = new(pool_) Node();
1055  left->child1 = left->child2 = NULL;
1056  NodePtr right = new(pool_) Node();
1057  right->child1 = right->child2 = NULL;
1058 
1059  if (point[div_feat]<leaf_point[div_feat]) {
1060  left->divfeat = ind;
1061  left->point = point;
1062  right->divfeat = node->divfeat;
1063  right->point = node->point;
1064  }
1065  else {
1066  left->divfeat = node->divfeat;
1067  left->point = node->point;
1068  right->divfeat = ind;
1069  right->point = point;
1070  }
1071  node->divfeat = div_feat;
1072  node->divval = (point[div_feat]+leaf_point[div_feat])/2;
1073  node->child1 = left;
1074  node->child2 = right;
1075  }
1076  else {
1077  if (point[node->divfeat]<node->divval) {
1078  addPointToTree(node->child1,ind);
1079  }
1080  else {
1081  addPointToTree(node->child2,ind);
1082  }
1083  }
1084  }
1085 private:
1086  void swap(KDTreeIndex& other)
1087  {
1088  BaseClass::swap(other);
1089  std::swap(trees_, other.trees_);
1090  std::swap(tree_roots_, other.tree_roots_);
1091  std::swap(pool_, other.pool_);
1092  }
1093 
1094 private:
1095 
1096  enum
1097  {
1103  SAMPLE_MEAN = 100,
1111  RAND_DIM=5
1112  };
1113 
1118  int trees_;
1119 
1121  DistanceType* var_;
1122 
1126  std::vector<NodePtr> tree_roots_;
1127 
1136 
1138 }; // class KDTreeIndex
1140 }
1141 
1142 #endif //FLANN_KDTREE_INDEX_H_
rtflann::KDTreeIndex::needs_kdtree_distance
bool needs_kdtree_distance
Definition: kdtree_index.h:109
ind
std::vector< int > ind
glm::min
GLM_FUNC_DECL genType min(genType const &x, genType const &y)
int
int
rtflann::KDTreeIndex::Node::child2
Node * child2
Definition: kdtree_index.h:130
rtflann::KDTreeIndexParams
Definition: kdtree_index.h:84
rtflann::FLANN_CHECKS_UNLIMITED
@ FLANN_CHECKS_UNLIMITED
Definition: defines.h:147
stderr
stderr
general.h
rtflann::ResultSet
Definition: result_set.h:110
rtflann::NNIndex
Definition: nn_index.h:101
rtflann::FLANN_True
@ FLANN_True
Definition: params.h:82
rtflann::KDTreeIndex::searchLevelExact
void searchLevelExact(ResultSet< DistanceType > &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, const float epsError) const
Definition: kdtree_index.h:1029
rtflann::KDTreeIndex::Node::serialize
void serialize(Archive &ar)
Definition: kdtree_index.h:143
rtflann::KDTreeIndex::selectDivision
int selectDivision(DistanceType *v)
Definition: kdtree_index.h:836
knn
int knn
rtflann::PooledAllocator::free
void free()
Definition: allocator.h:142
stream
stream
rtflann::Matrix_::cols
size_t cols
Definition: matrix.h:101
rtflann::get_param
T get_param(const IndexParams &params, std::string name, const T &default_value)
Definition: params.h:121
rtflann::KDTreeIndex::planeSplit
void planeSplit(int *ind, int count, int cutfeat, DistanceType cutval, int &lim1, int &lim2)
Definition: kdtree_index.h:874
rtflann::FLANN_Undefined
@ FLANN_Undefined
Definition: params.h:83
this
this
rtflann::Heap
Definition: heap.h:77
rtflann::FLANN_INDEX_KDTREE
@ FLANN_INDEX_KDTREE
Definition: defines.h:82
rtflann::KDTreeIndexParams::KDTreeIndexParams
KDTreeIndexParams(int trees=4)
Definition: kdtree_index.h:114
count
Index count
rtflann::Heap::popMin
bool popMin(T &value)
Definition: heap.h:217
rtflann::NNIndex::veclen
size_t veclen() const
Definition: nn_index.h:247
nn_index.h
rtflann::KDTreeIndex::serialize
void serialize(Archive &ar)
Definition: kdtree_index.h:266
rtflann::NNIndex::points_
std::vector< ElementType * > points_
Definition: nn_index.h:914
rtflann::PooledAllocator::wastedMemory
int wastedMemory
Definition: allocator.h:119
rtflann::KDTreeIndex::addPointToTree
void addPointToTree(NodePtr node, int ind)
Definition: kdtree_index.h:1067
rtflann::KDTreeIndex::DistanceType
Distance::ResultType DistanceType
Definition: kdtree_index.h:105
rtflann::NNIndex::radiusSearch
virtual int radiusSearch(const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params) const
Perform radius search.
Definition: nn_index.h:529
rtflann::KDTreeIndex::Node::divfeat
int divfeat
Definition: kdtree_index.h:118
rtflann::KDTreeIndex::Node::divval
DistanceType divval
Definition: kdtree_index.h:122
Eigen::PlainObjectBase::resize
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE void resize(Index rows, Index cols)
rtflann::NNIndex::knnSearch
virtual int knnSearch(const Matrix< ElementType > &queries, Matrix< size_t > &indices, Matrix< DistanceType > &dists, size_t knn, const SearchParams &params) const
Perform k-nearest neighbor search.
Definition: nn_index.h:343
dynamic_bitset.h
rtflann::KDTreeIndex::divideTree
NodePtr divideTree(int *ind, int count)
Definition: kdtree_index.h:755
rtflann::serialization::access
Definition: serialization.h:29
rtflann::PooledAllocator::usedMemory
int usedMemory
Definition: allocator.h:118
rtflann::KDTreeIndex::meanSplit
void meanSplit(int *ind, int count, int &index, int &cutfeat, DistanceType &cutval)
Definition: kdtree_index.h:786
rtflann::KDTreeIndex::KDTreeIndex
KDTreeIndex(const IndexParams &params=KDTreeIndexParams(), Distance d=Distance())
Definition: kdtree_index.h:188
indices
indices
rtflann::KDTreeIndex::freeIndex
void freeIndex()
Definition: kdtree_index.h:718
rtflann::KDTreeIndex::SAMPLE_MEAN
@ SAMPLE_MEAN
Definition: kdtree_index.h:1131
rtflann::DynamicBitset::test
bool test(size_t index) const
Definition: dynamic_bitset.h:199
rtflann::DynamicBitset
Definition: dynamic_bitset.h:82
n
int n
point
point
rtflann::rand_int
int rand_int(int high=RAND_MAX, int low=0)
Definition: random.h:102
random.h
matrix.h
rtflann::KDTreeIndex::saveIndex
void saveIndex(FILE *stream)
Definition: kdtree_index.h:291
rtflann::NNIndex::indices_to_ids
void indices_to_ids(const size_t *in, size_t *out, size_t size) const
Definition: nn_index.h:775
rtflann::KDTreeIndex::ElementType
Distance::ElementType ElementType
Definition: kdtree_index.h:104
rtflann::NNIndex::size_
size_t size_
Definition: nn_index.h:874
g
float g
j
std::ptrdiff_t j
rtflann::KDTreeIndex::addPoints
void addPoints(const Matrix< ElementType > &points, float rebuild_threshold=2)
Incrementally add points to the index.
Definition: kdtree_index.h:240
rtflann::serialization::LoadArchive
Definition: serialization.h:550
Eigen::PlainObjectBase::rows
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE EIGEN_CONSTEXPR Index rows() const EIGEN_NOEXCEPT
rtflann::NNIndex::veclen_
size_t veclen_
Definition: nn_index.h:884
rtflann::NNIndex::removed_points_
DynamicBitset removed_points_
Definition: nn_index.h:899
rtflann::KDTreeIndex::trees_
int trees_
Definition: kdtree_index.h:1146
std::swap
void swap(GeographicLib::NearestNeighbor< dist_t, pos_t, distfun_t > &a, GeographicLib::NearestNeighbor< dist_t, pos_t, distfun_t > &b)
rtflann::KDTreeIndex::loadIndex
void loadIndex(FILE *stream)
Definition: kdtree_index.h:298
rtflann::KDTreeIndex::Node::child1
Node * child1
Definition: kdtree_index.h:130
rtflann::NNIndex::setDataset
void setDataset(const Matrix< ElementType > &dataset)
Definition: nn_index.h:784
d
d
saving.h
result_set.h
params
SmartProjectionParams params(gtsam::HESSIAN, gtsam::ZERO_ON_DEGENERACY)
rtflann::BranchStruct
Definition: result_set.h:78
rtflann::KDTreeIndex
Definition: kdtree_index.h:101
rtflann::NNIndex::distance_
Distance distance_
Definition: nn_index.h:861
rtflann::KDTreeIndex::pool_
PooledAllocator pool_
Definition: kdtree_index.h:1163
rtflann::NNIndex::removed_
bool removed_
Definition: nn_index.h:894
size_t
std::size_t size_t
rtflann::KDTreeIndex::clone
BaseClass * clone() const
Definition: kdtree_index.h:233
rtflann::KDTreeIndex::mean_
DistanceType * mean_
Definition: kdtree_index.h:1148
rtflann::KDTreeIndex::getNeighbors
void getNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, int maxCheck, float epsError) const
Definition: kdtree_index.h:919
rtflann::PooledAllocator
Definition: allocator.h:103
rtflann::KDTreeIndex::Node::~Node
~Node()
Definition: kdtree_index.h:135
rtflann::flann_algorithm_t
flann_algorithm_t
Definition: defines.h:79
rtflann::KDTreeIndex::BaseClass
NNIndex< Distance > BaseClass
Definition: kdtree_index.h:107
KNN_HEAP_THRESHOLD
#define KNN_HEAP_THRESHOLD
Definition: nn_index.h:74
rtflann::NNIndex::swap
void swap(NNIndex &other)
Definition: nn_index.h:840
rtflann::KDTreeIndex::usedMemory
int usedMemory() const
Definition: kdtree_index.h:309
allocator.h
rtflann::KDTreeIndex::Node
Definition: kdtree_index.h:113
Eigen::PlainObjectBase::cols
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE EIGEN_CONSTEXPR Index cols() const EIGEN_NOEXCEPT
rtflann::KDTreeIndex::findNeighbors
void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: kdtree_index.h:323
rtflann::KDTreeIndex::~KDTreeIndex
virtual ~KDTreeIndex()
Definition: kdtree_index.h:228
glm::abs
GLM_FUNC_DECL genType abs(genType const &x)
rtflann::KDTreeIndex::operator=
KDTreeIndex & operator=(KDTreeIndex other)
Definition: kdtree_index.h:219
rtflann::KDTreeIndex::var_
DistanceType * var_
Definition: kdtree_index.h:1149
Index
struct Index Index
Definition: sqlite3.c:8577
rtflann::KDTreeIndex::swap
void swap(KDTreeIndex &other)
Definition: kdtree_index.h:1114
rtflann::NNIndex::size_at_build_
size_t size_at_build_
Definition: nn_index.h:879
diff
diff
rtflann::KDTreeIndex::Node::point
ElementType * point
Definition: kdtree_index.h:126
span
Index span
v
Array< int, Dynamic, 1 > v
rtflann::KDTreeIndex::tree_roots_
std::vector< NodePtr > tree_roots_
Definition: kdtree_index.h:1154
Eigen.Matrix< double, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor >
rtflann::KDTreeIndex::getType
flann_algorithm_t getType() const
Definition: kdtree_index.h:259
rtflann::IndexParams
std::map< std::string, any > IndexParams
Definition: params.h:77
rtflann::NNIndex::buildIndex
virtual void buildIndex()
Definition: nn_index.h:153
NULL
#define NULL
rtflann::KDTreeIndex::Branch
BranchSt * Branch
Definition: kdtree_index.h:177
rtflann::KDTreeIndex::NodePtr
Node * NodePtr
Definition: kdtree_index.h:175
rtflann::KDTreeIndex::buildIndexImpl
void buildIndexImpl()
Definition: kdtree_index.h:694
dist
dist
USING_BASECLASS_SYMBOLS
#define USING_BASECLASS_SYMBOLS
Definition: nn_index.h:925
dst
char * dst
Definition: lz4.h:354
rtflann::KDTreeIndex::RAND_DIM
@ RAND_DIM
Definition: kdtree_index.h:1139
rtflann::NNIndex::extendDataset
void extendDataset(const Matrix< ElementType > &new_points)
Definition: nn_index.h:801
rtflann::KDTreeIndex::BranchSt
BranchStruct< NodePtr, DistanceType > BranchSt
Definition: kdtree_index.h:176
rtflann::KDTreeIndex::copyTree
void copyTree(NodePtr &dst, const NodePtr &src)
Definition: kdtree_index.h:730
rtflann
Definition: all_indices.h:49
i
int i
other
other
result
RESULT & result
heap.h
rtflann::KDTreeIndex::Node::Node
Node()
Definition: kdtree_index.h:131
rtflann::NNIndex::index_params_
IndexParams index_params_
Definition: nn_index.h:889
rtflann::Matrix< ElementType >
rtflann::KDTreeIndex::getExactNeighbors
void getExactNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, float epsError) const
Definition: kdtree_index.h:901
rtflann::KDTreeIndex::searchLevel
void searchLevel(ResultSet< DistanceType > &result_set, const ElementType *vec, NodePtr node, DistanceType mindist, int &checkCount, int maxCheck, float epsError, Heap< BranchSt > *heap, DynamicBitset &checked) const
Definition: kdtree_index.h:977
rtflann::Index
Definition: flann.hpp:104


rtabmap
Author(s): Mathieu Labbe
autogenerated on Thu Jul 25 2024 02:50:11