composite_index.h

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_COMPOSITE_INDEX_H_
00032 #define OPENCV_FLANN_COMPOSITE_INDEX_H_
00033 
00034 #include "general.h"
00035 #include "nn_index.h"
00036 #include "kdtree_index.h"
00037 #include "kmeans_index.h"
00038 
00039 namespace cvflann
00040 {
00041 
00042 /**
00043  * Index parameters for the CompositeIndex.
00044  */
00045 struct CompositeIndexParams : public IndexParams
00046 {
00047     CompositeIndexParams(int trees = 4, int branching = 32, int iterations = 11,
00048                          flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, float cb_index = 0.2 )
00049     {
00050         (*this)["algorithm"] = FLANN_INDEX_KMEANS;
00051         // number of randomized trees to use (for kdtree)
00052         (*this)["trees"] = trees;
00053         // branching factor
00054         (*this)["branching"] = branching;
00055         // max iterations to perform in one kmeans clustering (kmeans tree)
00056         (*this)["iterations"] = iterations;
00057         // algorithm used for picking the initial cluster centers for kmeans tree
00058         (*this)["centers_init"] = centers_init;
00059         // cluster boundary index. Used when searching the kmeans tree
00060         (*this)["cb_index"] = cb_index;
00061     }
00062 };
00063 
00064 
00065 /**
00066  * This index builds a kd-tree index and a k-means index and performs nearest
00067  * neighbour search both indexes. This gives a slight boost in search performance
00068  * as some of the neighbours that are missed by one index are found by the other.
00069  */
00070 template <typename Distance>
00071 class CompositeIndex : public NNIndex<Distance>
00072 {
00073 public:
00074     typedef typename Distance::ElementType ElementType;
00075     typedef typename Distance::ResultType DistanceType;
00076 
00077     /**
00078      * Index constructor
00079      * @param inputData dataset containing the points to index
00080      * @param params Index parameters
00081      * @param d Distance functor
00082      * @return
00083      */
00084     CompositeIndex(const Matrix<ElementType> & inputData, const IndexParams& params = CompositeIndexParams(),
00085                    Distance d = Distance()) : index_params_(params)
00086     {
00087         kdtree_index_ = new KDTreeIndex<Distance>(inputData, params, d);
00088         kmeans_index_ = new KMeansIndex<Distance>(inputData, params, d);
00089 
00090     }
00091 
00092     CompositeIndex(const CompositeIndex&);
00093     CompositeIndex& operator=(const CompositeIndex&);
00094 
00095     virtual ~CompositeIndex()
00096     {
00097         delete kdtree_index_;
00098         delete kmeans_index_;
00099     }
00100 
00101     /**
00102      * @return The index type
00103      */
00104     flann_algorithm_t getType () const
00105     {
00106         return FLANN_INDEX_COMPOSITE;
00107     }
00108 
00109     /**
00110      * @return Size of the index
00111      */
00112     size_t size () const
00113     {
00114         return kdtree_index_->size();
00115     }
00116 
00117     /**
00118      * \returns The dimensionality of the features in this index.
00119      */
00120     size_t veclen () const
00121     {
00122         return kdtree_index_->veclen();
00123     }
00124 
00125     /**
00126      * \returns The amount of memory (in bytes) used by the index.
00127      */
00128     int usedMemory () const
00129     {
00130         return kmeans_index_->usedMemory() + kdtree_index_->usedMemory();
00131     }
00132 
00133     /**
00134      * \brief Builds the index
00135      */
00136     void buildIndex()
00137     {
00138         Logger::info("Building kmeans tree...\n");
00139         kmeans_index_->buildIndex();
00140         Logger::info("Building kdtree tree...\n");
00141         kdtree_index_->buildIndex();
00142     }
00143 
00144     /**
00145      * \brief Saves the index to a stream
00146      * \param stream The stream to save the index to
00147      */
00148     void saveIndex(FILE* stream)
00149     {
00150         kmeans_index_->saveIndex(stream);
00151         kdtree_index_->saveIndex(stream);
00152     }
00153 
00154     /**
00155      * \brief Loads the index from a stream
00156      * \param stream The stream from which the index is loaded
00157      */
00158     void loadIndex(FILE* stream)
00159     {
00160         kmeans_index_->loadIndex(stream);
00161         kdtree_index_->loadIndex(stream);
00162     }
00163 
00164     /**
00165      * \returns The index parameters
00166      */
00167     IndexParams getParameters () const
00168     {
00169         return index_params_;
00170     }
00171 
00172     /**
00173      * \brief Method that searches for nearest-neighbours
00174      */
00175     void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
00176     {
00177         kmeans_index_->findNeighbors(result, vec, searchParams);
00178         kdtree_index_->findNeighbors(result, vec, searchParams);
00179     }
00180 
00181 private:
00182     /** The k-means index */
00183     KMeansIndex<Distance>* kmeans_index_;
00184 
00185     /** The kd-tree index */
00186     KDTreeIndex<Distance>* kdtree_index_;
00187 
00188     /** The index parameters */
00189     const IndexParams index_params_;
00190 };
00191 
00192 }
00193 
00194 #endif //OPENCV_FLANN_COMPOSITE_INDEX_H_
00195