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 FLANN_COMPOSITE_INDEX_H_ 32 #define FLANN_COMPOSITE_INDEX_H_ 33 34 #include "flann/general.h" 35 #include "flann/algorithms/nn_index.h" 36 #include "flann/algorithms/kdtree_index.h" 37 #include "flann/algorithms/kmeans_index.h" 38 39 namespace flann 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 typedef NNIndex<Distance> BaseClass; 78 79 typedef bool needs_kdtree_distance; 80 81 /** 82 * Index constructor 83 * @param inputData dataset containing the points to index 84 * @param params Index parameters 85 * @param d Distance functor 86 * @return 87 */ 88 CompositeIndex(const IndexParams& params = CompositeIndexParams(), Distance d = Distance()) : BaseClass(params,d)89 BaseClass(params, d) 90 { 91 kdtree_index_ = new KDTreeIndex<Distance>(params, d); 92 kmeans_index_ = new KMeansIndex<Distance>(params, d); 93 94 } 95 96 CompositeIndex(const Matrix<ElementType>& inputData, const IndexParams& params = CompositeIndexParams(), BaseClass(params,d)97 Distance d = Distance()) : BaseClass(params, d) 98 { 99 kdtree_index_ = new KDTreeIndex<Distance>(inputData, params, d); 100 kmeans_index_ = new KMeansIndex<Distance>(inputData, params, d); 101 } 102 CompositeIndex(const CompositeIndex & other)103 CompositeIndex(const CompositeIndex& other) : BaseClass(other), 104 kmeans_index_(other.kmeans_index_), kdtree_index_(other.kdtree_index_) 105 { 106 } 107 108 CompositeIndex& operator=(CompositeIndex other) 109 { 110 this->swap(other); 111 return *this; 112 } 113 ~CompositeIndex()114 virtual ~CompositeIndex() 115 { 116 delete kdtree_index_; 117 delete kmeans_index_; 118 } 119 clone()120 BaseClass* clone() const 121 { 122 return new CompositeIndex(*this); 123 } 124 125 /** 126 * @return The index type 127 */ getType()128 flann_algorithm_t getType() const 129 { 130 return FLANN_INDEX_COMPOSITE; 131 } 132 133 /** 134 * @return Size of the index 135 */ size()136 size_t size() const 137 { 138 return kdtree_index_->size(); 139 } 140 141 /** 142 * \returns The dimensionality of the features in this index. 143 */ veclen()144 size_t veclen() const 145 { 146 return kdtree_index_->veclen(); 147 } 148 149 /** 150 * \returns The amount of memory (in bytes) used by the index. 151 */ usedMemory()152 int usedMemory() const 153 { 154 return kmeans_index_->usedMemory() + kdtree_index_->usedMemory(); 155 } 156 157 using NNIndex<Distance>::buildIndex; 158 /** 159 * \brief Builds the index 160 */ buildIndex()161 void buildIndex() 162 { 163 Logger::info("Building kmeans tree...\n"); 164 kmeans_index_->buildIndex(); 165 Logger::info("Building kdtree tree...\n"); 166 kdtree_index_->buildIndex(); 167 } 168 169 void addPoints(const Matrix<ElementType>& points, float rebuild_threshold = 2) 170 { 171 kmeans_index_->addPoints(points, rebuild_threshold); 172 kdtree_index_->addPoints(points, rebuild_threshold); 173 } 174 removePoint(size_t index)175 void removePoint(size_t index) 176 { 177 kmeans_index_->removePoint(index); 178 kdtree_index_->removePoint(index); 179 } 180 181 182 /** 183 * \brief Saves the index to a stream 184 * \param stream The stream to save the index to 185 */ saveIndex(FILE * stream)186 void saveIndex(FILE* stream) 187 { 188 kmeans_index_->saveIndex(stream); 189 kdtree_index_->saveIndex(stream); 190 } 191 192 /** 193 * \brief Loads the index from a stream 194 * \param stream The stream from which the index is loaded 195 */ loadIndex(FILE * stream)196 void loadIndex(FILE* stream) 197 { 198 kmeans_index_->loadIndex(stream); 199 kdtree_index_->loadIndex(stream); 200 } 201 202 /** 203 * \brief Method that searches for nearest-neighbours 204 */ findNeighbors(ResultSet<DistanceType> & result,const ElementType * vec,const SearchParams & searchParams)205 void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) const 206 { 207 kmeans_index_->findNeighbors(result, vec, searchParams); 208 kdtree_index_->findNeighbors(result, vec, searchParams); 209 } 210 211 protected: swap(CompositeIndex & other)212 void swap(CompositeIndex& other) 213 { 214 std::swap(kmeans_index_, other.kmeans_index_); 215 std::swap(kdtree_index_, other.kdtree_index_); 216 } 217 buildIndexImpl()218 void buildIndexImpl() 219 { 220 /* nothing to do here */ 221 } 222 freeIndex()223 void freeIndex() 224 { 225 /* nothing to do here */ 226 } 227 228 229 private: 230 /** The k-means index */ 231 KMeansIndex<Distance>* kmeans_index_; 232 233 /** The kd-tree index */ 234 KDTreeIndex<Distance>* kdtree_index_; 235 }; 236 237 } 238 239 #endif //FLANN_COMPOSITE_INDEX_H_ 240