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_COMPOSITETREE_H_ 00032 #define _OPENCV_COMPOSITETREE_H_ 00033 00034 #include "opencv2/flann/general.h" 00035 #include "opencv2/flann/nn_index.h" 00036 00037 namespace cvflann 00038 { 00039 00040 00041 struct CompositeIndexParams : public IndexParams { 00042 CompositeIndexParams(int trees_ = 4, int branching_ = 32, int iterations_ = 11, 00043 flann_centers_init_t centers_init_ = FLANN_CENTERS_RANDOM, float cb_index_ = 0.2 ) : 00044 IndexParams(FLANN_INDEX_COMPOSITE), 00045 trees(trees_), 00046 branching(branching_), 00047 iterations(iterations_), 00048 centers_init(centers_init_), 00049 cb_index(cb_index_) {}; 00050 00051 int trees; // number of randomized trees to use (for kdtree) 00052 int branching; // branching factor (for kmeans tree) 00053 int iterations; // max iterations to perform in one kmeans clustering (kmeans tree) 00054 flann_centers_init_t centers_init; // algorithm used for picking the initial cluster centers for kmeans tree 00055 float cb_index; // cluster boundary index. Used when searching the kmeans tree 00056 00057 void print() const 00058 { 00059 logger().info("Index type: %d\n",(int)algorithm); 00060 logger().info("Trees: %d\n", trees); 00061 logger().info("Branching: %d\n", branching); 00062 logger().info("Iterations: %d\n", iterations); 00063 logger().info("Centres initialisation: %d\n", centers_init); 00064 logger().info("Cluster boundary weight: %g\n", cb_index); 00065 } 00066 }; 00067 00068 00069 00070 template <typename ELEM_TYPE, typename DIST_TYPE = typename DistType<ELEM_TYPE>::type > 00071 class CompositeIndex : public NNIndex<ELEM_TYPE> 00072 { 00073 KMeansIndex<ELEM_TYPE, DIST_TYPE>* kmeans; 00074 KDTreeIndex<ELEM_TYPE, DIST_TYPE>* kdtree; 00075 00076 const Matrix<ELEM_TYPE> dataset; 00077 00078 const IndexParams& index_params; 00079 00080 CompositeIndex& operator=(const CompositeIndex&); 00081 CompositeIndex(const CompositeIndex&); 00082 public: 00083 00084 CompositeIndex(const Matrix<ELEM_TYPE>& inputData, const CompositeIndexParams& params = CompositeIndexParams() ) : 00085 dataset(inputData), index_params(params) 00086 { 00087 KDTreeIndexParams kdtree_params(params.trees); 00088 KMeansIndexParams kmeans_params(params.branching, params.iterations, params.centers_init, params.cb_index); 00089 00090 kdtree = new KDTreeIndex<ELEM_TYPE, DIST_TYPE>(inputData,kdtree_params); 00091 kmeans = new KMeansIndex<ELEM_TYPE, DIST_TYPE>(inputData,kmeans_params); 00092 00093 } 00094 00095 virtual ~CompositeIndex() 00096 { 00097 delete kdtree; 00098 delete kmeans; 00099 } 00100 00101 00102 flann_algorithm_t getType() const 00103 { 00104 return FLANN_INDEX_COMPOSITE; 00105 } 00106 00107 00108 size_t size() const 00109 { 00110 return dataset.rows; 00111 } 00112 00113 size_t veclen() const 00114 { 00115 return dataset.cols; 00116 } 00117 00118 00119 int usedMemory() const 00120 { 00121 return kmeans->usedMemory()+kdtree->usedMemory(); 00122 } 00123 00124 void buildIndex() 00125 { 00126 logger().info("Building kmeans tree...\n"); 00127 kmeans->buildIndex(); 00128 logger().info("Building kdtree tree...\n"); 00129 kdtree->buildIndex(); 00130 } 00131 00132 00133 void saveIndex(FILE* stream) 00134 { 00135 kmeans->saveIndex(stream); 00136 kdtree->saveIndex(stream); 00137 } 00138 00139 00140 void loadIndex(FILE* stream) 00141 { 00142 kmeans->loadIndex(stream); 00143 kdtree->loadIndex(stream); 00144 } 00145 00146 void findNeighbors(ResultSet<ELEM_TYPE>& result, const ELEM_TYPE* vec, const SearchParams& searchParams) 00147 { 00148 kmeans->findNeighbors(result,vec,searchParams); 00149 kdtree->findNeighbors(result,vec,searchParams); 00150 } 00151 00152 const IndexParams* getParameters() const 00153 { 00154 return &index_params; 00155 } 00156 00157 00158 }; 00159 00160 } // namespace cvflann 00161 00162 #endif //_OPENCV_COMPOSITETREE_H_