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_ */