1 /*********************************************************************** 2 * Software License Agreement (BSD License) 3 * 4 * Copyright 2008-2009 Marius Muja (mariusm (at) cs.ubc.ca). All rights reserved. 5 * Copyright 2008-2009 David G. Lowe (lowe (at) 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_ 195
