OpenCV 2.4.8 components for OpenCVgrabber.
[mmanager-3rdparty.git] / OpenCV2.4.8 / build / include / opencv2 / flann / nn_index.h
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
44 /**
45  * Nearest-neighbour index base class
46  */
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
57     /**
58      * \brief Builds the index
59      */
60     virtual void buildIndex() = 0;
61
62     /**
63      * \brief Perform k-nearest neighbor search
64      * \param[in] queries The query points for which to find the nearest neighbors
65      * \param[out] indices The indices of the nearest neighbors found
66      * \param[out] dists Distances to the nearest neighbors found
67      * \param[in] knn Number of nearest neighbors to return
68      * \param[in] params Search parameters
69      */
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
95     /**
96      * \brief Perform radius search
97      * \param[in] query The query point
98      * \param[out] indices The indinces of the neighbors found within the given radius
99      * \param[out] dists The distances to the nearest neighbors found
100      * \param[in] radius The radius used for search
101      * \param[in] params Search parameters
102      * \returns Number of neighbors found
103      */
104     virtual int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params)
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
133     /**
134      * \brief Saves the index to a stream
135      * \param stream The stream to save the index to
136      */
137     virtual void saveIndex(FILE* stream) = 0;
138
139     /**
140      * \brief Loads the index from a stream
141      * \param stream The stream from which the index is loaded
142      */
143     virtual void loadIndex(FILE* stream) = 0;
144
145     /**
146      * \returns number of features in this index.
147      */
148     virtual size_t size() const = 0;
149
150     /**
151      * \returns The dimensionality of the features in this index.
152      */
153     virtual size_t veclen() const = 0;
154
155     /**
156      * \returns The amount of memory (in bytes) used by the index.
157      */
158     virtual int usedMemory() const = 0;
159
160     /**
161      * \returns The index type (kdtree, kmeans,...)
162      */
163     virtual flann_algorithm_t getType() const = 0;
164
165     /**
166      * \returns The index parameters
167      */
168     virtual IndexParams getParameters() const = 0;
169
170
171     /**
172      * \brief Method that searches for nearest-neighbours
173      */
174     virtual void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) = 0;
175 };
176
177 }
178
179 #endif //OPENCV_FLANN_NNINDEX_H