nn_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 OPENCV_FLANN_NNINDEX_H
32 #define OPENCV_FLANN_NNINDEX_H
33 
34 #include <string>
35 
36 #include "general.h"
37 #include "matrix.h"
38 #include "result_set.h"
39 #include "params.h"
40 
41 namespace cvflann
42 {
43 
47 template <typename Distance>
48 class NNIndex
49 {
50  typedef typename Distance::ElementType ElementType;
51  typedef typename Distance::ResultType DistanceType;
52 
53 public:
54 
55  virtual ~NNIndex() {}
56 
60  virtual void buildIndex() = 0;
61 
70  virtual void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
71  {
72  assert(queries.cols == veclen());
73  assert(indices.rows >= queries.rows);
74  assert(dists.rows >= queries.rows);
75  assert(int(indices.cols) >= knn);
76  assert(int(dists.cols) >= knn);
77 
78 #if 0
79  KNNResultSet<DistanceType> resultSet(knn);
80  for (size_t i = 0; i < queries.rows; i++) {
81  resultSet.init(indices[i], dists[i]);
82  findNeighbors(resultSet, queries[i], params);
83  }
84 #else
85  KNNUniqueResultSet<DistanceType> resultSet(knn);
86  for (size_t i = 0; i < queries.rows; i++) {
87  resultSet.clear();
88  findNeighbors(resultSet, queries[i], params);
89  if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices[i], dists[i], knn);
90  else resultSet.copy(indices[i], dists[i], knn);
91  }
92 #endif
93  }
94 
105  {
106  if (query.rows != 1) {
107  fprintf(stderr, "I can only search one feature at a time for range search\n");
108  return -1;
109  }
110  assert(query.cols == veclen());
111  assert(indices.cols == dists.cols);
112 
113  int n = 0;
114  int* indices_ptr = NULL;
115  DistanceType* dists_ptr = NULL;
116  if (indices.cols > 0) {
117  n = (int)indices.cols;
118  indices_ptr = indices[0];
119  dists_ptr = dists[0];
120  }
121 
122  RadiusUniqueResultSet<DistanceType> resultSet((DistanceType)radius);
123  resultSet.clear();
124  findNeighbors(resultSet, query[0], params);
125  if (n>0) {
126  if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices_ptr, dists_ptr, n);
127  else resultSet.copy(indices_ptr, dists_ptr, n);
128  }
129 
130  return (int)resultSet.size();
131  }
132 
137  virtual void saveIndex(FILE* stream) = 0;
138 
143  virtual void loadIndex(FILE* stream) = 0;
144 
148  virtual size_t size() const = 0;
149 
153  virtual size_t veclen() const = 0;
154 
158  virtual int usedMemory() const = 0;
159 
163  virtual flann_algorithm_t getType() const = 0;
164 
168  virtual IndexParams getParameters() const = 0;
169 
170 
174  virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) = 0;
175 };
176 
177 }
178 
179 #endif //OPENCV_FLANN_NNINDEX_H
flann_algorithm_t
Definition: defines.h:81
virtual flann_algorithm_t getType() const =0
T get_param(const IndexParams &params, std::string name, const T &default_value)
Definition: params.h:59
size_t cols
Definition: matrix.h:52
virtual size_t size() const =0
virtual void saveIndex(FILE *stream)=0
Saves the index to a stream.
virtual void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams)=0
Method that searches for nearest-neighbours.
virtual void knnSearch(const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, int knn, const SearchParams &params)
Perform k-nearest neighbor search.
Definition: nn_index.h:70
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
void init(int *indices_, DistanceType *dists_)
Definition: result_set.h:165
Definition: params.h:44
void clear()
Definition: result_set.h:471
virtual void sortAndCopy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:351
GLuint GLuint GLsizei GLenum const GLvoid * indices
Definition: legacy.hpp:3084
virtual IndexParams getParameters() const =0
size_t size() const
Definition: result_set.h:359
Definition: result_set.h:152
virtual void buildIndex()=0
Builds the index.
GLenum GLsizei n
void clear()
Definition: result_set.h:425
Definition: result_set.h:389
virtual void copy(int *indices, DistanceType *dist, int n_neighbors=-1) const
Definition: result_set.h:327
Definition: result_set.h:66
std::map< std::string, any > IndexParams
Definition: params.h:42
virtual void loadIndex(FILE *stream)=0
Loads the index from a stream.
Definition: result_set.h:448
GLenum const GLfloat * params
Definition: compat.hpp:688
virtual int radiusSearch(const Matrix< ElementType > &query, Matrix< int > &indices, Matrix< DistanceType > &dists, float radius, const SearchParams &params)
Perform radius search.
Definition: nn_index.h:104
Definition: nn_index.h:48
size_t rows
Definition: matrix.h:51
virtual int usedMemory() const =0
::max::max int
Definition: functional.hpp:324
virtual ~NNIndex()
Definition: nn_index.h:55
virtual size_t veclen() const =0
CvPoint int radius
Definition: core_c.h:1290