include/opencv2/flann/flann_base.hpp
Go to the documentation of this file.
00001 /***********************************************************************
00002  * Software License Agreement (BSD License)
00003  *
00004  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
00005  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
00006  *
00007  * THE BSD LICENSE
00008  *
00009  * Redistribution and use in source and binary forms, with or without
00010  * modification, are permitted provided that the following conditions
00011  * are met:
00012  *
00013  * 1. Redistributions of source code must retain the above copyright
00014  *    notice, this list of conditions and the following disclaimer.
00015  * 2. Redistributions in binary form must reproduce the above copyright
00016  *    notice, this list of conditions and the following disclaimer in the
00017  *    documentation and/or other materials provided with the distribution.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
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;       // filename of the stored index
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     // TODO: optimise here
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 } // namespace cvflann
00259 #endif /* _OPENCV_FLANN_BASE_HPP_ */