include/opencv2/flann/composite_index.h
Go to the documentation of this file.
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_