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 "general.h"
35 #include "matrix.h"
36 #include "result_set.h"
37 #include "params.h"
38 
39 namespace cvflann
40 {
41 
42 /**
43  * Nearest-neighbour index base class
44  */
45 template <typename Distance>
46 class NNIndex
47 {
48     typedef typename Distance::ElementType ElementType;
49     typedef typename Distance::ResultType DistanceType;
50 
51 public:
52 
~NNIndex()53     virtual ~NNIndex() {}
54 
55     /**
56      * \brief Builds the index
57      */
58     virtual void buildIndex() = 0;
59 
60     /**
61      * \brief Perform k-nearest neighbor search
62      * \param[in] queries The query points for which to find the nearest neighbors
63      * \param[out] indices The indices of the nearest neighbors found
64      * \param[out] dists Distances to the nearest neighbors found
65      * \param[in] knn Number of nearest neighbors to return
66      * \param[in] params Search parameters
67      */
knnSearch(const Matrix<ElementType> & queries,Matrix<int> & indices,Matrix<DistanceType> & dists,int knn,const SearchParams & params)68     virtual void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
69     {
70         assert(queries.cols == veclen());
71         assert(indices.rows >= queries.rows);
72         assert(dists.rows >= queries.rows);
73         assert(int(indices.cols) >= knn);
74         assert(int(dists.cols) >= knn);
75 
76 #if 0
77         KNNResultSet<DistanceType> resultSet(knn);
78         for (size_t i = 0; i < queries.rows; i++) {
79             resultSet.init(indices[i], dists[i]);
80             findNeighbors(resultSet, queries[i], params);
81         }
82 #else
83         KNNUniqueResultSet<DistanceType> resultSet(knn);
84         for (size_t i = 0; i < queries.rows; i++) {
85             resultSet.clear();
86             findNeighbors(resultSet, queries[i], params);
87             if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices[i], dists[i], knn);
88             else resultSet.copy(indices[i], dists[i], knn);
89         }
90 #endif
91     }
92 
93     /**
94      * \brief Perform radius search
95      * \param[in] query The query point
96      * \param[out] indices The indinces of the neighbors found within the given radius
97      * \param[out] dists The distances to the nearest neighbors found
98      * \param[in] radius The radius used for search
99      * \param[in] params Search parameters
100      * \returns Number of neighbors found
101      */
radiusSearch(const Matrix<ElementType> & query,Matrix<int> & indices,Matrix<DistanceType> & dists,float radius,const SearchParams & params)102     virtual int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params)
103     {
104         if (query.rows != 1) {
105             fprintf(stderr, "I can only search one feature at a time for range search\n");
106             return -1;
107         }
108         assert(query.cols == veclen());
109         assert(indices.cols == dists.cols);
110 
111         int n = 0;
112         int* indices_ptr = NULL;
113         DistanceType* dists_ptr = NULL;
114         if (indices.cols > 0) {
115             n = (int)indices.cols;
116             indices_ptr = indices[0];
117             dists_ptr = dists[0];
118         }
119 
120         RadiusUniqueResultSet<DistanceType> resultSet((DistanceType)radius);
121         resultSet.clear();
122         findNeighbors(resultSet, query[0], params);
123         if (n>0) {
124             if (get_param(params,"sorted",true)) resultSet.sortAndCopy(indices_ptr, dists_ptr, n);
125             else resultSet.copy(indices_ptr, dists_ptr, n);
126         }
127 
128         return (int)resultSet.size();
129     }
130 
131     /**
132      * \brief Saves the index to a stream
133      * \param stream The stream to save the index to
134      */
135     virtual void saveIndex(FILE* stream) = 0;
136 
137     /**
138      * \brief Loads the index from a stream
139      * \param stream The stream from which the index is loaded
140      */
141     virtual void loadIndex(FILE* stream) = 0;
142 
143     /**
144      * \returns number of features in this index.
145      */
146     virtual size_t size() const = 0;
147 
148     /**
149      * \returns The dimensionality of the features in this index.
150      */
151     virtual size_t veclen() const = 0;
152 
153     /**
154      * \returns The amount of memory (in bytes) used by the index.
155      */
156     virtual int usedMemory() const = 0;
157 
158     /**
159      * \returns The index type (kdtree, kmeans,...)
160      */
161     virtual flann_algorithm_t getType() const = 0;
162 
163     /**
164      * \returns The index parameters
165      */
166     virtual IndexParams getParameters() const = 0;
167 
168 
169     /**
170      * \brief Method that searches for nearest-neighbours
171      */
172     virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) = 0;
173 };
174 
175 }
176 
177 #endif //OPENCV_FLANN_NNINDEX_H
178