flann.hpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                           License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
00014 // Copyright (C) 2009, Willow Garage Inc., all rights reserved.
00015 // Third party copyrights are property of their respective owners.
00016 //
00017 // Redistribution and use in source and binary forms, with or without modification,
00018 // are permitted provided that the following conditions are met:
00019 //
00020 //   * Redistribution's of source code must retain the above copyright notice,
00021 //     this list of conditions and the following disclaimer.
00022 //
00023 //   * Redistribution's in binary form must reproduce the above copyright notice,
00024 //     this list of conditions and the following disclaimer in the documentation
00025 //     and/or other materials provided with the distribution.
00026 //
00027 //   * The name of the copyright holders may not be used to endorse or promote products
00028 //     derived from this software without specific prior written permission.
00029 //
00030 // This software is provided by the copyright holders and contributors "as is" and
00031 // any express or implied warranties, including, but not limited to, the implied
00032 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00033 // In no event shall the Intel Corporation or contributors be liable for any direct,
00034 // indirect, incidental, special, exemplary, or consequential damages
00035 // (including, but not limited to, procurement of substitute goods or services;
00036 // loss of use, data, or profits; or business interruption) however caused
00037 // and on any theory of liability, whether in contract, strict liability,
00038 // or tort (including negligence or otherwise) arising in any way out of
00039 // the use of this software, even if advised of the possibility of such damage.
00040 //
00041 //M*/
00042 
00043 #ifndef _OPENCV_FLANN_HPP_
00044 #define _OPENCV_FLANN_HPP_
00045 
00046 #include "opencv2/core.hpp"
00047 #include "opencv2/flann/miniflann.hpp"
00048 #include "opencv2/flann/flann_base.hpp"
00049 
00050 /**
00051 @defgroup flann Clustering and Search in Multi-Dimensional Spaces
00052 
00053 This section documents OpenCV's interface to the FLANN library. FLANN (Fast Library for Approximate
00054 Nearest Neighbors) is a library that contains a collection of algorithms optimized for fast nearest
00055 neighbor search in large datasets and for high dimensional features. More information about FLANN
00056 can be found in @cite Muja2009 .
00057 */
00058 
00059 namespace cvflann
00060 {
00061     CV_EXPORTS flann_distance_t flann_distance_type();
00062     FLANN_DEPRECATED CV_EXPORTS void set_distance_type(flann_distance_t distance_type, int order);
00063 }
00064 
00065 
00066 namespace cv
00067 {
00068 namespace flann
00069 {
00070 
00071 
00072 //! @addtogroup flann
00073 //! @{
00074 
00075 template <typename T> struct CvType {};
00076 template <> struct CvType<unsigned char> { static int type() { return CV_8U; } };
00077 template <> struct CvType<char> { static int type() { return CV_8S; } };
00078 template <> struct CvType<unsigned short> { static int type() { return CV_16U; } };
00079 template <> struct CvType<short> { static int type() { return CV_16S; } };
00080 template <> struct CvType<int> { static int type() { return CV_32S; } };
00081 template <> struct CvType<float> { static int type() { return CV_32F; } };
00082 template <> struct CvType<double> { static int type() { return CV_64F; } };
00083 
00084 
00085 // bring the flann parameters into this namespace
00086 using ::cvflann::get_param;
00087 using ::cvflann::print_params;
00088 
00089 // bring the flann distances into this namespace
00090 using ::cvflann::L2_Simple;
00091 using ::cvflann::L2;
00092 using ::cvflann::L1;
00093 using ::cvflann::MinkowskiDistance;
00094 using ::cvflann::MaxDistance;
00095 using ::cvflann::HammingLUT;
00096 using ::cvflann::Hamming;
00097 using ::cvflann::Hamming2;
00098 using ::cvflann::HistIntersectionDistance;
00099 using ::cvflann::HellingerDistance;
00100 using ::cvflann::ChiSquareDistance;
00101 using ::cvflann::KL_Divergence;
00102 
00103 
00104 /** @brief The FLANN nearest neighbor index class. This class is templated with the type of elements for which
00105 the index is built.
00106  */
00107 template <typename Distance>
00108 class GenericIndex
00109 {
00110 public:
00111         typedef typename Distance::ElementType ElementType;
00112         typedef typename Distance::ResultType DistanceType;
00113 
00114         /** @brief Constructs a nearest neighbor search index for a given dataset.
00115 
00116         @param features Matrix of containing the features(points) to index. The size of the matrix is
00117         num_features x feature_dimensionality and the data type of the elements in the matrix must
00118         coincide with the type of the index.
00119         @param params Structure containing the index parameters. The type of index that will be
00120         constructed depends on the type of this parameter. See the description.
00121         @param distance
00122 
00123         The method constructs a fast search structure from a set of features using the specified algorithm
00124         with specified parameters, as defined by params. params is a reference to one of the following class
00125         IndexParams descendants:
00126 
00127         - **LinearIndexParams** When passing an object of this type, the index will perform a linear,
00128         brute-force search. :
00129         @code
00130         struct LinearIndexParams : public IndexParams
00131         {
00132         };
00133         @endcode
00134         - **KDTreeIndexParams** When passing an object of this type the index constructed will consist of
00135         a set of randomized kd-trees which will be searched in parallel. :
00136         @code
00137         struct KDTreeIndexParams : public IndexParams
00138         {
00139             KDTreeIndexParams( int trees = 4 );
00140         };
00141         @endcode
00142         - **KMeansIndexParams** When passing an object of this type the index constructed will be a
00143         hierarchical k-means tree. :
00144         @code
00145         struct KMeansIndexParams : public IndexParams
00146         {
00147             KMeansIndexParams(
00148                 int branching = 32,
00149                 int iterations = 11,
00150                 flann_centers_init_t centers_init = CENTERS_RANDOM,
00151                 float cb_index = 0.2 );
00152         };
00153         @endcode
00154         - **CompositeIndexParams** When using a parameters object of this type the index created
00155         combines the randomized kd-trees and the hierarchical k-means tree. :
00156         @code
00157         struct CompositeIndexParams : public IndexParams
00158         {
00159             CompositeIndexParams(
00160                 int trees = 4,
00161                 int branching = 32,
00162                 int iterations = 11,
00163                 flann_centers_init_t centers_init = CENTERS_RANDOM,
00164                 float cb_index = 0.2 );
00165         };
00166         @endcode
00167         - **LshIndexParams** When using a parameters object of this type the index created uses
00168         multi-probe LSH (by Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search
00169         by Qin Lv, William Josephson, Zhe Wang, Moses Charikar, Kai Li., Proceedings of the 33rd
00170         International Conference on Very Large Data Bases (VLDB). Vienna, Austria. September 2007) :
00171         @code
00172         struct LshIndexParams : public IndexParams
00173         {
00174             LshIndexParams(
00175                 unsigned int table_number,
00176                 unsigned int key_size,
00177                 unsigned int multi_probe_level );
00178         };
00179         @endcode
00180         - **AutotunedIndexParams** When passing an object of this type the index created is
00181         automatically tuned to offer the best performance, by choosing the optimal index type
00182         (randomized kd-trees, hierarchical kmeans, linear) and parameters for the dataset provided. :
00183         @code
00184         struct AutotunedIndexParams : public IndexParams
00185         {
00186             AutotunedIndexParams(
00187                 float target_precision = 0.9,
00188                 float build_weight = 0.01,
00189                 float memory_weight = 0,
00190                 float sample_fraction = 0.1 );
00191         };
00192         @endcode
00193         - **SavedIndexParams** This object type is used for loading a previously saved index from the
00194         disk. :
00195         @code
00196         struct SavedIndexParams : public IndexParams
00197         {
00198             SavedIndexParams( String filename );
00199         };
00200         @endcode
00201          */
00202         GenericIndex(const Mat& features, const ::cvflann::IndexParams& params, Distance distance = Distance());
00203 
00204         ~GenericIndex();
00205 
00206         /** @brief Performs a K-nearest neighbor search for a given query point using the index.
00207 
00208         @param query The query point
00209         @param indices Vector that will contain the indices of the K-nearest neighbors found. It must have
00210         at least knn size.
00211         @param dists Vector that will contain the distances to the K-nearest neighbors found. It must have
00212         at least knn size.
00213         @param knn Number of nearest neighbors to search for.
00214         @param params SearchParams
00215          */
00216         void knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices,
00217                        std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& params);
00218         void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& params);
00219 
00220         int radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices,
00221                          std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& params);
00222         int radiusSearch(const Mat& query, Mat& indices, Mat& dists,
00223                          DistanceType radius, const ::cvflann::SearchParams& params);
00224 
00225         void save(String filename) { nnIndex->save(filename); }
00226 
00227         int veclen() const { return nnIndex->veclen(); }
00228 
00229         int size() const { return nnIndex->size(); }
00230 
00231         ::cvflann::IndexParams getParameters() { return nnIndex->getParameters(); }
00232 
00233         FLANN_DEPRECATED const ::cvflann::IndexParams* getIndexParameters() { return nnIndex->getIndexParameters(); }
00234 
00235 private:
00236         ::cvflann::Index<Distance>* nnIndex;
00237 };
00238 
00239 //! @cond IGNORED
00240 
00241 #define FLANN_DISTANCE_CHECK \
00242     if ( ::cvflann::flann_distance_type() != cvflann::FLANN_DIST_L2) { \
00243         printf("[WARNING] You are using cv::flann::Index (or cv::flann::GenericIndex) and have also changed "\
00244         "the distance using cvflann::set_distance_type. This is no longer working as expected "\
00245         "(cv::flann::Index always uses L2). You should create the index templated on the distance, "\
00246         "for example for L1 distance use: GenericIndex< L1<float> > \n"); \
00247     }
00248 
00249 
00250 template <typename Distance>
00251 GenericIndex<Distance>::GenericIndex(const Mat& dataset, const ::cvflann::IndexParams& params, Distance distance)
00252 {
00253     CV_Assert(dataset.type() == CvType<ElementType>::type());
00254     CV_Assert(dataset.isContinuous()); 
00255     ::cvflann::Matrix<ElementType>  m_dataset((ElementType*)dataset.ptr<ElementType>(0), dataset.rows, dataset.cols);
00256 
00257     nnIndex = new ::cvflann::Index<Distance>(m_dataset, params, distance);
00258 
00259     FLANN_DISTANCE_CHECK
00260 
00261     nnIndex->buildIndex();
00262 }
00263 
00264 template <typename Distance>
00265 GenericIndex<Distance>::~GenericIndex()
00266 {
00267     delete nnIndex;
00268 }
00269 
00270 template <typename Distance>
00271 void GenericIndex<Distance>::knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
00272 { 
00273     ::cvflann::Matrix<ElementType>  m_query((ElementType*)&query[0], 1, query.size()); 
00274     ::cvflann::Matrix<int>  m_indices(&indices[0], 1, indices.size());
00275     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
00276 
00277     FLANN_DISTANCE_CHECK
00278 
00279     nnIndex->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
00280 }
00281 
00282 
00283 template <typename Distance>
00284 void GenericIndex<Distance>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
00285 {
00286     CV_Assert(queries.type() == CvType<ElementType>::type());
00287     CV_Assert(queries.isContinuous()); 
00288     ::cvflann::Matrix<ElementType>  m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
00289 
00290     CV_Assert(indices.type() == CV_32S);
00291     CV_Assert(indices.isContinuous()); 
00292     ::cvflann::Matrix<int>  m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
00293 
00294     CV_Assert(dists.type() == CvType<DistanceType>::type());
00295     CV_Assert(dists.isContinuous());
00296     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
00297 
00298     FLANN_DISTANCE_CHECK
00299 
00300     nnIndex->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
00301 }
00302 
00303 template <typename Distance>
00304 int GenericIndex<Distance>::radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
00305 { 
00306     ::cvflann::Matrix<ElementType>  m_query((ElementType*)&query[0], 1, query.size()); 
00307     ::cvflann::Matrix<int>  m_indices(&indices[0], 1, indices.size());
00308     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
00309 
00310     FLANN_DISTANCE_CHECK
00311 
00312     return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00313 }
00314 
00315 template <typename Distance>
00316 int GenericIndex<Distance>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
00317 {
00318     CV_Assert(query.type() == CvType<ElementType>::type());
00319     CV_Assert(query.isContinuous()); 
00320     ::cvflann::Matrix<ElementType>  m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
00321 
00322     CV_Assert(indices.type() == CV_32S);
00323     CV_Assert(indices.isContinuous()); 
00324     ::cvflann::Matrix<int>  m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
00325 
00326     CV_Assert(dists.type() == CvType<DistanceType>::type());
00327     CV_Assert(dists.isContinuous());
00328     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
00329 
00330     FLANN_DISTANCE_CHECK
00331 
00332     return nnIndex->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00333 }
00334 
00335 //! @endcond
00336 
00337 /**
00338  * @deprecated Use GenericIndex class instead
00339  */
00340 template <typename T>
00341 class
00342 #ifndef _MSC_VER
00343  FLANN_DEPRECATED
00344 #endif
00345  Index_  {
00346 public:
00347         typedef typename L2<T>::ElementType ElementType;
00348         typedef typename L2<T>::ResultType DistanceType;
00349 
00350     Index_ (const Mat& features, const ::cvflann::IndexParams& params);
00351 
00352     ~Index_ ();
00353 
00354     void knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& params);
00355     void knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& params);
00356 
00357     int radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& params);
00358     int radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& params);
00359 
00360     void save(String filename)
00361         {
00362             if (nnIndex_L1) nnIndex_L1->save(filename);
00363             if (nnIndex_L2) nnIndex_L2->save(filename);
00364         }
00365 
00366     int veclen() const
00367     {
00368             if (nnIndex_L1) return nnIndex_L1->veclen();
00369             if (nnIndex_L2) return nnIndex_L2->veclen();
00370         }
00371 
00372     int size() const
00373     {
00374             if (nnIndex_L1) return nnIndex_L1->size();
00375             if (nnIndex_L2) return nnIndex_L2->size();
00376         }
00377 
00378         ::cvflann::IndexParams getParameters()
00379         {
00380             if (nnIndex_L1) return nnIndex_L1->getParameters();
00381             if (nnIndex_L2) return nnIndex_L2->getParameters();
00382 
00383         }
00384 
00385         FLANN_DEPRECATED const ::cvflann::IndexParams* getIndexParameters()
00386         {
00387             if (nnIndex_L1) return nnIndex_L1->getIndexParameters();
00388             if (nnIndex_L2) return nnIndex_L2->getIndexParameters();
00389         }
00390 
00391 private:
00392         // providing backwards compatibility for L2 and L1 distances (most common)
00393         ::cvflann::Index< L2<ElementType> >* nnIndex_L2;
00394         ::cvflann::Index< L1<ElementType> >* nnIndex_L1;
00395 };
00396 
00397 #ifdef _MSC_VER
00398 template <typename T>
00399 class FLANN_DEPRECATED Index_ ;
00400 #endif
00401 
00402 //! @cond IGNORED
00403 
00404 template <typename T>
00405 Index_<T>::Index_ (const Mat& dataset, const ::cvflann::IndexParams& params)
00406 {
00407     printf("[WARNING] The cv::flann::Index_<T> class is deperecated, use cv::flann::GenericIndex<Distance> instead\n");
00408 
00409     CV_Assert(dataset.type() == CvType<ElementType>::type());
00410     CV_Assert(dataset.isContinuous()); 
00411     ::cvflann::Matrix<ElementType>  m_dataset((ElementType*)dataset.ptr<ElementType>(0), dataset.rows, dataset.cols);
00412 
00413     if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
00414         nnIndex_L1 = NULL;
00415         nnIndex_L2 = new ::cvflann::Index< L2<ElementType> >(m_dataset, params);
00416     }
00417     else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
00418         nnIndex_L1 = new ::cvflann::Index< L1<ElementType> >(m_dataset, params);
00419         nnIndex_L2 = NULL;
00420     }
00421     else {
00422         printf("[ERROR] cv::flann::Index_<T> only provides backwards compatibility for the L1 and L2 distances. "
00423         "For other distance types you must use cv::flann::GenericIndex<Distance>\n");
00424         CV_Assert(0);
00425     }
00426     if (nnIndex_L1) nnIndex_L1->buildIndex();
00427     if (nnIndex_L2) nnIndex_L2->buildIndex();
00428 }
00429 
00430 template <typename T>
00431 Index_<T>::~Index_()
00432 {
00433     if (nnIndex_L1) delete nnIndex_L1;
00434     if (nnIndex_L2) delete nnIndex_L2;
00435 }
00436 
00437 template <typename T>
00438 void Index_<T>::knnSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, int knn, const ::cvflann::SearchParams& searchParams)
00439 { 
00440     ::cvflann::Matrix<ElementType>  m_query((ElementType*)&query[0], 1, query.size()); 
00441     ::cvflann::Matrix<int>  m_indices(&indices[0], 1, indices.size());
00442     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
00443 
00444     if (nnIndex_L1) nnIndex_L1->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
00445     if (nnIndex_L2) nnIndex_L2->knnSearch(m_query,m_indices,m_dists,knn,searchParams);
00446 }
00447 
00448 
00449 template <typename T>
00450 void Index_<T>::knnSearch(const Mat& queries, Mat& indices, Mat& dists, int knn, const ::cvflann::SearchParams& searchParams)
00451 {
00452     CV_Assert(queries.type() == CvType<ElementType>::type());
00453     CV_Assert(queries.isContinuous()); 
00454     ::cvflann::Matrix<ElementType>  m_queries((ElementType*)queries.ptr<ElementType>(0), queries.rows, queries.cols);
00455 
00456     CV_Assert(indices.type() == CV_32S);
00457     CV_Assert(indices.isContinuous()); 
00458     ::cvflann::Matrix<int>  m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
00459 
00460     CV_Assert(dists.type() == CvType<DistanceType>::type());
00461     CV_Assert(dists.isContinuous());
00462     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
00463 
00464     if (nnIndex_L1) nnIndex_L1->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
00465     if (nnIndex_L2) nnIndex_L2->knnSearch(m_queries,m_indices,m_dists,knn, searchParams);
00466 }
00467 
00468 template <typename T>
00469 int Index_<T>::radiusSearch(const std::vector<ElementType>& query, std::vector<int>& indices, std::vector<DistanceType>& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
00470 { 
00471     ::cvflann::Matrix<ElementType>  m_query((ElementType*)&query[0], 1, query.size()); 
00472     ::cvflann::Matrix<int>  m_indices(&indices[0], 1, indices.size());
00473     ::cvflann::Matrix<DistanceType> m_dists(&dists[0], 1, dists.size());
00474 
00475     if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00476     if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00477 }
00478 
00479 template <typename T>
00480 int Index_<T>::radiusSearch(const Mat& query, Mat& indices, Mat& dists, DistanceType radius, const ::cvflann::SearchParams& searchParams)
00481 {
00482     CV_Assert(query.type() == CvType<ElementType>::type());
00483     CV_Assert(query.isContinuous()); 
00484     ::cvflann::Matrix<ElementType>  m_query((ElementType*)query.ptr<ElementType>(0), query.rows, query.cols);
00485 
00486     CV_Assert(indices.type() == CV_32S);
00487     CV_Assert(indices.isContinuous()); 
00488     ::cvflann::Matrix<int>  m_indices((int*)indices.ptr<int>(0), indices.rows, indices.cols);
00489 
00490     CV_Assert(dists.type() == CvType<DistanceType>::type());
00491     CV_Assert(dists.isContinuous());
00492     ::cvflann::Matrix<DistanceType> m_dists((DistanceType*)dists.ptr<DistanceType>(0), dists.rows, dists.cols);
00493 
00494     if (nnIndex_L1) return nnIndex_L1->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00495     if (nnIndex_L2) return nnIndex_L2->radiusSearch(m_query,m_indices,m_dists,radius,searchParams);
00496 }
00497 
00498 //! @endcond
00499 
00500 /** @brief Clusters features using hierarchical k-means algorithm.
00501 
00502 @param features The points to be clustered. The matrix must have elements of type
00503 Distance::ElementType.
00504 @param centers The centers of the clusters obtained. The matrix must have type
00505 Distance::ResultType. The number of rows in this matrix represents the number of clusters desired,
00506 however, because of the way the cut in the hierarchical tree is chosen, the number of clusters
00507 computed will be the highest number of the form (branching-1)\*k+1 that's lower than the number of
00508 clusters desired, where branching is the tree's branching factor (see description of the
00509 KMeansIndexParams).
00510 @param params Parameters used in the construction of the hierarchical k-means tree.
00511 @param d Distance to be used for clustering.
00512 
00513 The method clusters the given feature vectors by constructing a hierarchical k-means tree and
00514 choosing a cut in the tree that minimizes the cluster's variance. It returns the number of clusters
00515 found.
00516  */
00517 template <typename Distance>
00518 int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params,
00519                            Distance d = Distance())
00520 {
00521     typedef typename Distance::ElementType ElementType;
00522     typedef typename Distance::ResultType DistanceType;
00523 
00524     CV_Assert(features.type() == CvType<ElementType>::type());
00525     CV_Assert(features.isContinuous()); 
00526     ::cvflann::Matrix<ElementType>  m_features((ElementType*)features.ptr<ElementType>(0), features.rows, features.cols);
00527 
00528     CV_Assert(centers.type() == CvType<DistanceType>::type());
00529     CV_Assert(centers.isContinuous());
00530     ::cvflann::Matrix<DistanceType> m_centers((DistanceType*)centers.ptr<DistanceType>(0), centers.rows, centers.cols);
00531 
00532     return ::cvflann::hierarchicalClustering<Distance>(m_features, m_centers, params, d);
00533 }
00534 
00535 /** @deprecated
00536 */
00537 template <typename ELEM_TYPE, typename DIST_TYPE>
00538 FLANN_DEPRECATED int hierarchicalClustering(const Mat& features, Mat& centers, const ::cvflann::KMeansIndexParams& params)
00539 {
00540     printf("[WARNING] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> is deprecated, use "
00541         "cv::flann::hierarchicalClustering<Distance> instead\n");
00542 
00543     if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L2 ) {
00544         return hierarchicalClustering< L2<ELEM_TYPE> >(features, centers, params);
00545     }
00546     else if ( ::cvflann::flann_distance_type() == cvflann::FLANN_DIST_L1 ) {
00547         return hierarchicalClustering< L1<ELEM_TYPE> >(features, centers, params);
00548     }
00549     else {
00550         printf("[ERROR] cv::flann::hierarchicalClustering<ELEM_TYPE,DIST_TYPE> only provides backwards "
00551         "compatibility for the L1 and L2 distances. "
00552         "For other distance types you must use cv::flann::hierarchicalClustering<Distance>\n");
00553         CV_Assert(0);
00554     }
00555 }
00556 
00557 //! @} flann
00558 
00559 } } // namespace cv::flann
00560 
00561 #endif
00562