00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #ifndef _OPENCV_FLANN_BASE_HPP_
00032 #define _OPENCV_FLANN_BASE_HPP_
00033
00034 #include <vector>
00035 #include <string>
00036 #include <cassert>
00037 #include <cstdio>
00038
00039 #include "opencv2/flann/general.h"
00040 #include "opencv2/flann/matrix.h"
00041 #include "opencv2/flann/result_set.h"
00042 #include "opencv2/flann/index_testing.h"
00043 #include "opencv2/flann/object_factory.h"
00044 #include "opencv2/flann/saving.h"
00045
00046 #include "opencv2/flann/all_indices.h"
00047
00048 namespace cvflann
00049 {
00050
00051
00058 CV_EXPORTS void log_verbosity(int level);
00059
00060
00066 CV_EXPORTS void set_distance_type(flann_distance_t distance_type, int order);
00067
00068
00069 struct CV_EXPORTS SavedIndexParams : public IndexParams {
00070 SavedIndexParams(std::string filename_) : IndexParams(FLANN_INDEX_SAVED), filename(filename_) {}
00071
00072 std::string filename;
00073
00074 void print() const
00075 {
00076 logger().info("Index type: %d\n",(int)algorithm);
00077 logger().info("Filename: %s\n", filename.c_str());
00078 }
00079 };
00080
00081 template<typename T>
00082 class CV_EXPORTS Index {
00083 NNIndex<T>* nnIndex;
00084 bool built;
00085
00086 public:
00087 Index(const Matrix<T>& features, const IndexParams& params);
00088
00089 ~Index();
00090
00091 void buildIndex();
00092
00093 void knnSearch(const Matrix<T>& queries, Matrix<int>& indices, Matrix<float>& dists, int knn, const SearchParams& params);
00094
00095 int radiusSearch(const Matrix<T>& query, Matrix<int>& indices, Matrix<float>& dists, float radius, const SearchParams& params);
00096
00097 void save(std::string filename);
00098
00099 int veclen() const;
00100
00101 int size() const;
00102
00103 NNIndex<T>* getIndex() { return nnIndex; }
00104
00105 const IndexParams* getIndexParameters() { return nnIndex->getParameters(); }
00106 };
00107
00108
00109 template<typename T>
00110 NNIndex<T>* load_saved_index(const Matrix<T>& dataset, const std::string& filename)
00111 {
00112 FILE* fin = fopen(filename.c_str(), "rb");
00113 if (fin==NULL) {
00114 return NULL;
00115 }
00116 IndexHeader header = load_header(fin);
00117 if (header.data_type!=Datatype<T>::type()) {
00118 throw FLANNException("Datatype of saved index is different than of the one to be created.");
00119 }
00120 if (size_t(header.rows)!=dataset.rows || size_t(header.cols)!=dataset.cols) {
00121 throw FLANNException("The index saved belongs to a different dataset");
00122 }
00123
00124 IndexParams* params = ParamsFactory_instance().create(header.index_type);
00125 NNIndex<T>* nnIndex = create_index_by_type(dataset, *params);
00126 nnIndex->loadIndex(fin);
00127 fclose(fin);
00128
00129 return nnIndex;
00130 }
00131
00132
00133 template<typename T>
00134 Index<T>::Index(const Matrix<T>& dataset, const IndexParams& params)
00135 {
00136 flann_algorithm_t index_type = params.getIndexType();
00137 built = false;
00138
00139 if (index_type==FLANN_INDEX_SAVED) {
00140 nnIndex = load_saved_index(dataset, ((const SavedIndexParams&)params).filename);
00141 built = true;
00142 }
00143 else {
00144 nnIndex = create_index_by_type(dataset, params);
00145 }
00146 }
00147
00148 template<typename T>
00149 Index<T>::~Index()
00150 {
00151 delete nnIndex;
00152 }
00153
00154 template<typename T>
00155 void Index<T>::buildIndex()
00156 {
00157 if (!built) {
00158 nnIndex->buildIndex();
00159 built = true;
00160 }
00161 }
00162
00163 template<typename T>
00164 void Index<T>::knnSearch(const Matrix<T>& queries, Matrix<int>& indices, Matrix<float>& dists, int knn, const SearchParams& searchParams)
00165 {
00166 if (!built) {
00167 throw FLANNException("You must build the index before searching.");
00168 }
00169 assert(queries.cols==nnIndex->veclen());
00170 assert(indices.rows>=queries.rows);
00171 assert(dists.rows>=queries.rows);
00172 assert(int(indices.cols)>=knn);
00173 assert(int(dists.cols)>=knn);
00174
00175 KNNResultSet<T> resultSet(knn);
00176
00177 for (size_t i = 0; i < queries.rows; i++) {
00178 T* target = queries[i];
00179 resultSet.init(target, (int)queries.cols);
00180
00181 nnIndex->findNeighbors(resultSet, target, searchParams);
00182
00183 int* neighbors = resultSet.getNeighbors();
00184 float* distances = resultSet.getDistances();
00185 memcpy(indices[i], neighbors, knn*sizeof(int));
00186 memcpy(dists[i], distances, knn*sizeof(float));
00187 }
00188 }
00189
00190 template<typename T>
00191 int Index<T>::radiusSearch(const Matrix<T>& query, Matrix<int>& indices, Matrix<float>& dists, float radius, const SearchParams& searchParams)
00192 {
00193 if (!built) {
00194 throw FLANNException("You must build the index before searching.");
00195 }
00196 if (query.rows!=1) {
00197 fprintf(stderr, "I can only search one feature at a time for range search\n");
00198 return -1;
00199 }
00200 assert(query.cols==nnIndex->veclen());
00201
00202 RadiusResultSet<T> resultSet(radius);
00203 resultSet.init(query.data, (int)query.cols);
00204 nnIndex->findNeighbors(resultSet,query.data,searchParams);
00205
00206
00207 int* neighbors = resultSet.getNeighbors();
00208 float* distances = resultSet.getDistances();
00209 size_t count_nn = std::min(resultSet.size(), indices.cols);
00210
00211 assert (dists.cols>=count_nn);
00212
00213 for (size_t i=0;i<count_nn;++i) {
00214 indices[0][i] = neighbors[i];
00215 dists[0][i] = distances[i];
00216 }
00217
00218 return (int)count_nn;
00219 }
00220
00221
00222 template<typename T>
00223 void Index<T>::save(std::string filename)
00224 {
00225 FILE* fout = fopen(filename.c_str(), "wb");
00226 if (fout==NULL) {
00227 throw FLANNException("Cannot open file");
00228 }
00229 save_header(fout, *nnIndex);
00230 nnIndex->saveIndex(fout);
00231 fclose(fout);
00232 }
00233
00234
00235 template<typename T>
00236 int Index<T>::size() const
00237 {
00238 return nnIndex->size();
00239 }
00240
00241 template<typename T>
00242 int Index<T>::veclen() const
00243 {
00244 return nnIndex->veclen();
00245 }
00246
00247
00248 template <typename ELEM_TYPE, typename DIST_TYPE>
00249 int hierarchicalClustering(const Matrix<ELEM_TYPE>& features, Matrix<DIST_TYPE>& centers, const KMeansIndexParams& params)
00250 {
00251 KMeansIndex<ELEM_TYPE, DIST_TYPE> kmeans(features, params);
00252 kmeans.buildIndex();
00253
00254 int clusterNum = kmeans.getClusterCenters(centers);
00255 return clusterNum;
00256 }
00257
00258 }
00259 #endif