modules/flann/include/opencv2/flann/composite_index.h

   1 /***********************************************************************
   2  * Software License Agreement (BSD License)
   3  *
   4  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
   5  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
   6  *
   7  * THE BSD LICENSE
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *************************************************************************/
  30
  31 #ifndef OPENCV_FLANN_COMPOSITE_INDEX_H_
  32 #define OPENCV_FLANN_COMPOSITE_INDEX_H_
  33
  34 #include "general.h"
  35 #include "nn_index.h"
  36 #include "kdtree_index.h"
  37 #include "kmeans_index.h"
  38
  39 namespace cvflann
  40 {
  41
  42 /**
  43  * Index parameters for the CompositeIndex.
  44  */
  45 struct CompositeIndexParams : public IndexParams
  46 {
  47     CompositeIndexParams(int trees = 4, int branching = 32, int iterations = 11,
  48                          flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM, float cb_index = 0.2 )
  49     {
  50         (*this)["algorithm"] = FLANN_INDEX_KMEANS;
  51         // number of randomized trees to use (for kdtree)
  52         (*this)["trees"] = trees;
  53         // branching factor
  54         (*this)["branching"] = branching;
  55         // max iterations to perform in one kmeans clustering (kmeans tree)
  56         (*this)["iterations"] = iterations;
  57         // algorithm used for picking the initial cluster centers for kmeans tree
  58         (*this)["centers_init"] = centers_init;
  59         // cluster boundary index. Used when searching the kmeans tree
  60         (*this)["cb_index"] = cb_index;
  61     }
  62 };
  63
  64
  65 /**
  66  * This index builds a kd-tree index and a k-means index and performs nearest
  67  * neighbour search both indexes. This gives a slight boost in search performance
  68  * as some of the neighbours that are missed by one index are found by the other.
  69  */
  70 template <typename Distance>
  71 class CompositeIndex : public NNIndex<Distance>
  72 {
  73 public:
  74     typedef typename Distance::ElementType ElementType;
  75     typedef typename Distance::ResultType DistanceType;
  76
  77     /**
  78      * Index constructor
  79      * @param inputData dataset containing the points to index
  80      * @param params Index parameters
  81      * @param d Distance functor
  82      * @return
  83      */
  84     CompositeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = CompositeIndexParams(),
  85                    Distance d = Distance()) : index_params_(params)
  86     {
  87         kdtree_index_ = new KDTreeIndex<Distance>(inputData, params, d);
  88         kmeans_index_ = new KMeansIndex<Distance>(inputData, params, d);
  89
  90     }
  91
  92     CompositeIndex(const CompositeIndex&);
  93     CompositeIndex& operator=(const CompositeIndex&);
  94
  95     virtual ~CompositeIndex()
  96     {
  97         delete kdtree_index_;
  98         delete kmeans_index_;
  99     }
 100
 101     /**
 102      * @return The index type
 103      */
 104     flann_algorithm_t getType() const
 105     {
 106         return FLANN_INDEX_COMPOSITE;
 107     }
 108
 109     /**
 110      * @return Size of the index
 111      */
 112     size_t size() const
 113     {
 114         return kdtree_index_->size();
 115     }
 116
 117     /**
 118      * \returns The dimensionality of the features in this index.
 119      */
 120     size_t veclen() const
 121     {
 122         return kdtree_index_->veclen();
 123     }
 124
 125     /**
 126      * \returns The amount of memory (in bytes) used by the index.
 127      */
 128     int usedMemory() const
 129     {
 130         return kmeans_index_->usedMemory() + kdtree_index_->usedMemory();
 131     }
 132
 133     /**
 134      * \brief Builds the index
 135      */
 136     void buildIndex()
 137     {
 138         Logger::info("Building kmeans tree...\n");
 139         kmeans_index_->buildIndex();
 140         Logger::info("Building kdtree tree...\n");
 141         kdtree_index_->buildIndex();
 142     }
 143
 144     /**
 145      * \brief Saves the index to a stream
 146      * \param stream The stream to save the index to
 147      */
 148     void saveIndex(FILE* stream)
 149     {
 150         kmeans_index_->saveIndex(stream);
 151         kdtree_index_->saveIndex(stream);
 152     }
 153
 154     /**
 155      * \brief Loads the index from a stream
 156      * \param stream The stream from which the index is loaded
 157      */
 158     void loadIndex(FILE* stream)
 159     {
 160         kmeans_index_->loadIndex(stream);
 161         kdtree_index_->loadIndex(stream);
 162     }
 163
 164     /**
 165      * \returns The index parameters
 166      */
 167     IndexParams getParameters() const
 168     {
 169         return index_params_;
 170     }
 171
 172     /**
 173      * \brief Method that searches for nearest-neighbours
 174      */
 175     void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams)
 176     {
 177         kmeans_index_->findNeighbors(result, vec, searchParams);
 178         kdtree_index_->findNeighbors(result, vec, searchParams);
 179     }
 180
 181 private:
 182     /** The k-means index */
 183     KMeansIndex<Distance>* kmeans_index_;
 184
 185     /** The kd-tree index */
 186     KDTreeIndex<Distance>* kdtree_index_;
 187
 188     /** The index parameters */
 189     const IndexParams index_params_;
 190 };
 191
 192 }
 193
 194 #endif //OPENCV_FLANN_COMPOSITE_INDEX_H_