flann_base.hpp

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 <cassert>
00036 #include <cstdio>
00037 
00038 #include "general.h"
00039 #include "matrix.h"
00040 #include "params.h"
00041 #include "saving.h"
00042 
00043 #include "all_indices.h"
00044 
00045 namespace cvflann
00046 {
00047 
00048 /**
00049  * Sets the log level used for all flann functions
00050  * @param level Verbosity level
00051  */
00052 inline void log_verbosity(int level)
00053 {
00054     if (level >= 0) {
00055         Logger::setLevel(level);
00056     }
00057 }
00058 
00059 /**
00060  * (Deprecated) Index parameters for creating a saved index.
00061  */
00062 struct SavedIndexParams : public IndexParams
00063 {
00064     SavedIndexParams(cv::String filename)
00065     {
00066         (* this)["algorithm"] = FLANN_INDEX_SAVED;
00067         (*this)["filename"] = filename;
00068     }
00069 };
00070 
00071 
00072 template<typename Distance>
00073 NNIndex<Distance>* load_saved_index(const Matrix<typename Distance::ElementType>& dataset, const cv::String& filename, Distance distance)
00074 {
00075     typedef typename Distance::ElementType ElementType;
00076 
00077     FILE* fin = fopen(filename.c_str(), "rb");
00078     if (fin == NULL) {
00079         return NULL;
00080     }
00081     IndexHeader header = load_header(fin);
00082     if (header.data_type != Datatype<ElementType>::type()) {
00083         throw FLANNException("Datatype of saved index is different than of the one to be created.");
00084     }
00085     if ((size_t(header.rows) != dataset.rows)||(size_t(header.cols) != dataset.cols)) {
00086         throw FLANNException("The index saved belongs to a different dataset");
00087     }
00088 
00089     IndexParams params;
00090     params["algorithm"] = header.index_type;
00091     NNIndex<Distance>* nnIndex = create_index_by_type<Distance>(dataset, params, distance);
00092     nnIndex->loadIndex(fin);
00093     fclose(fin);
00094 
00095     return nnIndex;
00096 }
00097 
00098 
00099 template<typename Distance>
00100 class Index : public NNIndex<Distance>
00101 {
00102 public:
00103     typedef typename Distance::ElementType ElementType;
00104     typedef typename Distance::ResultType DistanceType;
00105 
00106     Index(const Matrix<ElementType>& features, const IndexParams& params, Distance distance = Distance() )
00107         : index_params_(params)
00108     {
00109         flann_algorithm_t index_type = get_param<flann_algorithm_t>(params,"algorithm");
00110         loaded_ = false;
00111 
00112         if (index_type == FLANN_INDEX_SAVED) {
00113             nnIndex_ = load_saved_index<Distance>(features, get_param<cv::String>(params,"filename"), distance);
00114             loaded_ = true;
00115         }
00116         else {
00117             nnIndex_ = create_index_by_type<Distance>(features, params, distance);
00118         }
00119     }
00120 
00121     ~Index()
00122     {
00123         delete nnIndex_;
00124     }
00125 
00126     /**
00127      * Builds the index.
00128      */
00129     void buildIndex()
00130     {
00131         if (!loaded_) {
00132             nnIndex_->buildIndex();
00133         }
00134     }
00135 
00136     void save(cv::String filename)
00137     {
00138         FILE* fout = fopen(filename.c_str(), "wb");
00139         if (fout == NULL) {
00140             throw FLANNException("Cannot open file");
00141         }
00142         save_header(fout, *nnIndex_);
00143         saveIndex(fout);
00144         fclose(fout);
00145     }
00146 
00147     /**
00148      * \brief Saves the index to a stream
00149      * \param stream The stream to save the index to
00150      */
00151     virtual void saveIndex(FILE* stream)
00152     {
00153         nnIndex_->saveIndex(stream);
00154     }
00155 
00156     /**
00157      * \brief Loads the index from a stream
00158      * \param stream The stream from which the index is loaded
00159      */
00160     virtual void loadIndex(FILE* stream)
00161     {
00162         nnIndex_->loadIndex(stream);
00163     }
00164 
00165     /**
00166      * \returns number of features in this index.
00167      */
00168     size_t veclen() const
00169     {
00170         return nnIndex_->veclen();
00171     }
00172 
00173     /**
00174      * \returns The dimensionality of the features in this index.
00175      */
00176     size_t size() const
00177     {
00178         return nnIndex_->size();
00179     }
00180 
00181     /**
00182      * \returns The index type (kdtree, kmeans,...)
00183      */
00184     flann_algorithm_t getType() const
00185     {
00186         return nnIndex_->getType();
00187     }
00188 
00189     /**
00190      * \returns The amount of memory (in bytes) used by the index.
00191      */
00192     virtual int usedMemory() const
00193     {
00194         return nnIndex_->usedMemory();
00195     }
00196 
00197 
00198     /**
00199      * \returns The index parameters
00200      */
00201     IndexParams getParameters() const
00202     {
00203         return nnIndex_->getParameters();
00204     }
00205 
00206     /**
00207      * \brief Perform k-nearest neighbor search
00208      * \param[in] queries The query points for which to find the nearest neighbors
00209      * \param[out] indices The indices of the nearest neighbors found
00210      * \param[out] dists Distances to the nearest neighbors found
00211      * \param[in] knn Number of nearest neighbors to return
00212      * \param[in] params Search parameters
00213      */
00214     void knnSearch(const Matrix<ElementType>& queries, Matrix<int>& indices, Matrix<DistanceType>& dists, int knn, const SearchParams& params)
00215     {
00216         nnIndex_->knnSearch(queries, indices, dists, knn, params);
00217     }
00218 
00219     /**
00220      * \brief Perform radius search
00221      * \param[in] query The query point
00222      * \param[out] indices The indinces of the neighbors found within the given radius
00223      * \param[out] dists The distances to the nearest neighbors found
00224      * \param[in] radius The radius used for search
00225      * \param[in] params Search parameters
00226      * \returns Number of neighbors found
00227      */
00228     int radiusSearch(const Matrix<ElementType>& query, Matrix<int>& indices, Matrix<DistanceType>& dists, float radius, const SearchParams& params)
00229     {
00230         return nnIndex_->radiusSearch(query, indices, dists, radius, params);
00231     }
00232 
00233     /**
00234      * \brief Method that searches for nearest-neighbours
00235      */
00236     void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
00237     {
00238         nnIndex_->findNeighbors(result, vec, searchParams);
00239     }
00240 
00241     /**
00242      * \brief Returns actual index
00243      */
00244     FLANN_DEPRECATED NNIndex<Distance>* getIndex()
00245     {
00246         return nnIndex_;
00247     }
00248 
00249     /**
00250      * \brief Returns index parameters.
00251      * \deprecated use getParameters() instead.
00252      */
00253     FLANN_DEPRECATED  const IndexParams* getIndexParameters()
00254     {
00255         return &index_params_;
00256     }
00257 
00258 private:
00259     /** Pointer to actual index class */
00260     NNIndex<Distance>* nnIndex_;
00261     /** Indices if the index was loaded from a file */
00262     bool loaded_;
00263     /** Parameters passed to the index */
00264     IndexParams index_params_;
00265 };
00266 
00267 /**
00268  * Performs a hierarchical clustering of the points passed as argument and then takes a cut in the
00269  * the clustering tree to return a flat clustering.
00270  * @param[in] points Points to be clustered
00271  * @param centers The computed cluster centres. Matrix should be preallocated and centers.rows is the
00272  *  number of clusters requested.
00273  * @param params Clustering parameters (The same as for cvflann::KMeansIndex)
00274  * @param d Distance to be used for clustering (eg: cvflann::L2)
00275  * @return number of clusters computed (can be different than clusters.rows and is the highest number
00276  * of the form (branching-1)*K+1 smaller than clusters.rows).
00277  */
00278 template <typename Distance>
00279 int hierarchicalClustering(const Matrix<typename Distance::ElementType>& points, Matrix<typename Distance::ResultType>& centers,
00280                            const KMeansIndexParams& params, Distance d = Distance())
00281 {
00282     KMeansIndex<Distance> kmeans(points, params, d);
00283     kmeans.buildIndex();
00284 
00285     int clusterNum = kmeans.getClusterCenters(centers);
00286     return clusterNum;
00287 }
00288 
00289 }
00290 #endif /* OPENCV_FLANN_BASE_HPP_ */
00291