kmeans_index.h 68 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821
  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. #ifndef OPENCV_FLANN_KMEANS_INDEX_H_
  31. #define OPENCV_FLANN_KMEANS_INDEX_H_
  32. //! @cond IGNORED
  33. #include <algorithm>
  34. #include <map>
  35. #include <limits>
  36. #include <cmath>
  37. #include "general.h"
  38. #include "nn_index.h"
  39. #include "dist.h"
  40. #include "matrix.h"
  41. #include "result_set.h"
  42. #include "heap.h"
  43. #include "allocator.h"
  44. #include "random.h"
  45. #include "saving.h"
  46. #include "logger.h"
  47. #define BITS_PER_CHAR 8
  48. #define BITS_PER_BASE 2 // for DNA/RNA sequences
  49. #define BASE_PER_CHAR (BITS_PER_CHAR/BITS_PER_BASE)
  50. #define HISTOS_PER_BASE (1<<BITS_PER_BASE)
  51. namespace cvflann
  52. {
  53. struct KMeansIndexParams : public IndexParams
  54. {
  55. KMeansIndexParams(int branching = 32, int iterations = 11,
  56. flann_centers_init_t centers_init = FLANN_CENTERS_RANDOM,
  57. float cb_index = 0.2, int trees = 1 )
  58. {
  59. (*this)["algorithm"] = FLANN_INDEX_KMEANS;
  60. // branching factor
  61. (*this)["branching"] = branching;
  62. // max iterations to perform in one kmeans clustering (kmeans tree)
  63. (*this)["iterations"] = iterations;
  64. // algorithm used for picking the initial cluster centers for kmeans tree
  65. (*this)["centers_init"] = centers_init;
  66. // cluster boundary index. Used when searching the kmeans tree
  67. (*this)["cb_index"] = cb_index;
  68. // number of kmeans trees to search in
  69. (*this)["trees"] = trees;
  70. }
  71. };
  72. /**
  73. * Hierarchical kmeans index
  74. *
  75. * Contains a tree constructed through a hierarchical kmeans clustering
  76. * and other information for indexing a set of points for nearest-neighbour matching.
  77. */
  78. template <typename Distance>
  79. class KMeansIndex : public NNIndex<Distance>
  80. {
  81. public:
  82. typedef typename Distance::ElementType ElementType;
  83. typedef typename Distance::ResultType DistanceType;
  84. typedef typename Distance::CentersType CentersType;
  85. typedef typename Distance::is_kdtree_distance is_kdtree_distance;
  86. typedef typename Distance::is_vector_space_distance is_vector_space_distance;
  87. typedef void (KMeansIndex::* centersAlgFunction)(int, int*, int, int*, int&);
  88. /**
  89. * The function used for choosing the cluster centers.
  90. */
  91. centersAlgFunction chooseCenters;
  92. /**
  93. * Chooses the initial centers in the k-means clustering in a random manner.
  94. *
  95. * Params:
  96. * k = number of centers
  97. * vecs = the dataset of points
  98. * indices = indices in the dataset
  99. * indices_length = length of indices vector
  100. *
  101. */
  102. void chooseCentersRandom(int k, int* indices, int indices_length, int* centers, int& centers_length)
  103. {
  104. UniqueRandom r(indices_length);
  105. int index;
  106. for (index=0; index<k; ++index) {
  107. bool duplicate = true;
  108. int rnd;
  109. while (duplicate) {
  110. duplicate = false;
  111. rnd = r.next();
  112. if (rnd<0) {
  113. centers_length = index;
  114. return;
  115. }
  116. centers[index] = indices[rnd];
  117. for (int j=0; j<index; ++j) {
  118. DistanceType sq = distance_(dataset_[centers[index]], dataset_[centers[j]], dataset_.cols);
  119. if (sq<1e-16) {
  120. duplicate = true;
  121. }
  122. }
  123. }
  124. }
  125. centers_length = index;
  126. }
  127. /**
  128. * Chooses the initial centers in the k-means using Gonzales' algorithm
  129. * so that the centers are spaced apart from each other.
  130. *
  131. * Params:
  132. * k = number of centers
  133. * vecs = the dataset of points
  134. * indices = indices in the dataset
  135. * Returns:
  136. */
  137. void chooseCentersGonzales(int k, int* indices, int indices_length, int* centers, int& centers_length)
  138. {
  139. int n = indices_length;
  140. int rnd = rand_int(n);
  141. CV_DbgAssert(rnd >=0 && rnd < n);
  142. centers[0] = indices[rnd];
  143. int index;
  144. for (index=1; index<k; ++index) {
  145. int best_index = -1;
  146. DistanceType best_val = 0;
  147. for (int j=0; j<n; ++j) {
  148. DistanceType dist = distance_(dataset_[centers[0]],dataset_[indices[j]],dataset_.cols);
  149. for (int i=1; i<index; ++i) {
  150. DistanceType tmp_dist = distance_(dataset_[centers[i]],dataset_[indices[j]],dataset_.cols);
  151. if (tmp_dist<dist) {
  152. dist = tmp_dist;
  153. }
  154. }
  155. if (dist>best_val) {
  156. best_val = dist;
  157. best_index = j;
  158. }
  159. }
  160. if (best_index!=-1) {
  161. centers[index] = indices[best_index];
  162. }
  163. else {
  164. break;
  165. }
  166. }
  167. centers_length = index;
  168. }
  169. /**
  170. * Chooses the initial centers in the k-means using the algorithm
  171. * proposed in the KMeans++ paper:
  172. * Arthur, David; Vassilvitskii, Sergei - k-means++: The Advantages of Careful Seeding
  173. *
  174. * Implementation of this function was converted from the one provided in Arthur's code.
  175. *
  176. * Params:
  177. * k = number of centers
  178. * vecs = the dataset of points
  179. * indices = indices in the dataset
  180. * Returns:
  181. */
  182. void chooseCentersKMeanspp(int k, int* indices, int indices_length, int* centers, int& centers_length)
  183. {
  184. int n = indices_length;
  185. double currentPot = 0;
  186. DistanceType* closestDistSq = new DistanceType[n];
  187. // Choose one random center and set the closestDistSq values
  188. int index = rand_int(n);
  189. CV_DbgAssert(index >=0 && index < n);
  190. centers[0] = indices[index];
  191. for (int i = 0; i < n; i++) {
  192. closestDistSq[i] = distance_(dataset_[indices[i]], dataset_[indices[index]], dataset_.cols);
  193. closestDistSq[i] = ensureSquareDistance<Distance>( closestDistSq[i] );
  194. currentPot += closestDistSq[i];
  195. }
  196. const int numLocalTries = 1;
  197. // Choose each center
  198. int centerCount;
  199. for (centerCount = 1; centerCount < k; centerCount++) {
  200. // Repeat several trials
  201. double bestNewPot = -1;
  202. int bestNewIndex = -1;
  203. for (int localTrial = 0; localTrial < numLocalTries; localTrial++) {
  204. // Choose our center - have to be slightly careful to return a valid answer even accounting
  205. // for possible rounding errors
  206. double randVal = rand_double(currentPot);
  207. for (index = 0; index < n-1; index++) {
  208. if (randVal <= closestDistSq[index]) break;
  209. else randVal -= closestDistSq[index];
  210. }
  211. // Compute the new potential
  212. double newPot = 0;
  213. for (int i = 0; i < n; i++) {
  214. DistanceType dist = distance_(dataset_[indices[i]], dataset_[indices[index]], dataset_.cols);
  215. newPot += std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] );
  216. }
  217. // Store the best result
  218. if ((bestNewPot < 0)||(newPot < bestNewPot)) {
  219. bestNewPot = newPot;
  220. bestNewIndex = index;
  221. }
  222. }
  223. // Add the appropriate center
  224. centers[centerCount] = indices[bestNewIndex];
  225. currentPot = bestNewPot;
  226. for (int i = 0; i < n; i++) {
  227. DistanceType dist = distance_(dataset_[indices[i]], dataset_[indices[bestNewIndex]], dataset_.cols);
  228. closestDistSq[i] = std::min( ensureSquareDistance<Distance>(dist), closestDistSq[i] );
  229. }
  230. }
  231. centers_length = centerCount;
  232. delete[] closestDistSq;
  233. }
  234. public:
  235. flann_algorithm_t getType() const CV_OVERRIDE
  236. {
  237. return FLANN_INDEX_KMEANS;
  238. }
  239. template<class CentersContainerType>
  240. class KMeansDistanceComputer : public cv::ParallelLoopBody
  241. {
  242. public:
  243. KMeansDistanceComputer(Distance _distance, const Matrix<ElementType>& _dataset,
  244. const int _branching, const int* _indices, const CentersContainerType& _dcenters,
  245. const size_t _veclen, std::vector<int> &_new_centroids,
  246. std::vector<DistanceType> &_sq_dists)
  247. : distance(_distance)
  248. , dataset(_dataset)
  249. , branching(_branching)
  250. , indices(_indices)
  251. , dcenters(_dcenters)
  252. , veclen(_veclen)
  253. , new_centroids(_new_centroids)
  254. , sq_dists(_sq_dists)
  255. {
  256. }
  257. void operator()(const cv::Range& range) const CV_OVERRIDE
  258. {
  259. const int begin = range.start;
  260. const int end = range.end;
  261. for( int i = begin; i<end; ++i)
  262. {
  263. DistanceType sq_dist(distance(dataset[indices[i]], dcenters[0], veclen));
  264. int new_centroid(0);
  265. for (int j=1; j<branching; ++j) {
  266. DistanceType new_sq_dist = distance(dataset[indices[i]], dcenters[j], veclen);
  267. if (sq_dist>new_sq_dist) {
  268. new_centroid = j;
  269. sq_dist = new_sq_dist;
  270. }
  271. }
  272. sq_dists[i] = sq_dist;
  273. new_centroids[i] = new_centroid;
  274. }
  275. }
  276. private:
  277. Distance distance;
  278. const Matrix<ElementType>& dataset;
  279. const int branching;
  280. const int* indices;
  281. const CentersContainerType& dcenters;
  282. const size_t veclen;
  283. std::vector<int> &new_centroids;
  284. std::vector<DistanceType> &sq_dists;
  285. KMeansDistanceComputer& operator=( const KMeansDistanceComputer & ) { return *this; }
  286. };
  287. /**
  288. * Index constructor
  289. *
  290. * Params:
  291. * inputData = dataset with the input features
  292. * params = parameters passed to the hierarchical k-means algorithm
  293. */
  294. KMeansIndex(const Matrix<ElementType>& inputData, const IndexParams& params = KMeansIndexParams(),
  295. Distance d = Distance())
  296. : dataset_(inputData), index_params_(params), root_(NULL), indices_(NULL), distance_(d)
  297. {
  298. memoryCounter_ = 0;
  299. size_ = dataset_.rows;
  300. veclen_ = dataset_.cols;
  301. branching_ = get_param(params,"branching",32);
  302. trees_ = get_param(params,"trees",1);
  303. iterations_ = get_param(params,"iterations",11);
  304. if (iterations_<0) {
  305. iterations_ = (std::numeric_limits<int>::max)();
  306. }
  307. centers_init_ = get_param(params,"centers_init",FLANN_CENTERS_RANDOM);
  308. if (centers_init_==FLANN_CENTERS_RANDOM) {
  309. chooseCenters = &KMeansIndex::chooseCentersRandom;
  310. }
  311. else if (centers_init_==FLANN_CENTERS_GONZALES) {
  312. chooseCenters = &KMeansIndex::chooseCentersGonzales;
  313. }
  314. else if (centers_init_==FLANN_CENTERS_KMEANSPP) {
  315. chooseCenters = &KMeansIndex::chooseCentersKMeanspp;
  316. }
  317. else {
  318. FLANN_THROW(cv::Error::StsBadArg, "Unknown algorithm for choosing initial centers.");
  319. }
  320. cb_index_ = 0.4f;
  321. root_ = new KMeansNodePtr[trees_];
  322. indices_ = new int*[trees_];
  323. for (int i=0; i<trees_; ++i) {
  324. root_[i] = NULL;
  325. indices_[i] = NULL;
  326. }
  327. }
  328. KMeansIndex(const KMeansIndex&);
  329. KMeansIndex& operator=(const KMeansIndex&);
  330. /**
  331. * Index destructor.
  332. *
  333. * Release the memory used by the index.
  334. */
  335. virtual ~KMeansIndex()
  336. {
  337. if (root_ != NULL) {
  338. free_centers();
  339. delete[] root_;
  340. }
  341. if (indices_!=NULL) {
  342. free_indices();
  343. delete[] indices_;
  344. }
  345. }
  346. /**
  347. * Returns size of index.
  348. */
  349. size_t size() const CV_OVERRIDE
  350. {
  351. return size_;
  352. }
  353. /**
  354. * Returns the length of an index feature.
  355. */
  356. size_t veclen() const CV_OVERRIDE
  357. {
  358. return veclen_;
  359. }
  360. void set_cb_index( float index)
  361. {
  362. cb_index_ = index;
  363. }
  364. /**
  365. * Computes the inde memory usage
  366. * Returns: memory used by the index
  367. */
  368. int usedMemory() const CV_OVERRIDE
  369. {
  370. return pool_.usedMemory+pool_.wastedMemory+memoryCounter_;
  371. }
  372. /**
  373. * Builds the index
  374. */
  375. void buildIndex() CV_OVERRIDE
  376. {
  377. if (branching_<2) {
  378. FLANN_THROW(cv::Error::StsError, "Branching factor must be at least 2");
  379. }
  380. free_indices();
  381. for (int i=0; i<trees_; ++i) {
  382. indices_[i] = new int[size_];
  383. for (size_t j=0; j<size_; ++j) {
  384. indices_[i][j] = int(j);
  385. }
  386. root_[i] = pool_.allocate<KMeansNode>();
  387. std::memset(root_[i], 0, sizeof(KMeansNode));
  388. Distance* dummy = NULL;
  389. computeNodeStatistics(root_[i], indices_[i], (unsigned int)size_, dummy);
  390. computeClustering(root_[i], indices_[i], (int)size_, branching_,0);
  391. }
  392. }
  393. void saveIndex(FILE* stream) CV_OVERRIDE
  394. {
  395. save_value(stream, branching_);
  396. save_value(stream, iterations_);
  397. save_value(stream, memoryCounter_);
  398. save_value(stream, cb_index_);
  399. save_value(stream, trees_);
  400. for (int i=0; i<trees_; ++i) {
  401. save_value(stream, *indices_[i], (int)size_);
  402. save_tree(stream, root_[i], i);
  403. }
  404. }
  405. void loadIndex(FILE* stream) CV_OVERRIDE
  406. {
  407. if (indices_!=NULL) {
  408. free_indices();
  409. delete[] indices_;
  410. }
  411. if (root_!=NULL) {
  412. free_centers();
  413. }
  414. load_value(stream, branching_);
  415. load_value(stream, iterations_);
  416. load_value(stream, memoryCounter_);
  417. load_value(stream, cb_index_);
  418. load_value(stream, trees_);
  419. indices_ = new int*[trees_];
  420. for (int i=0; i<trees_; ++i) {
  421. indices_[i] = new int[size_];
  422. load_value(stream, *indices_[i], size_);
  423. load_tree(stream, root_[i], i);
  424. }
  425. index_params_["algorithm"] = getType();
  426. index_params_["branching"] = branching_;
  427. index_params_["trees"] = trees_;
  428. index_params_["iterations"] = iterations_;
  429. index_params_["centers_init"] = centers_init_;
  430. index_params_["cb_index"] = cb_index_;
  431. }
  432. /**
  433. * Find set of nearest neighbors to vec. Their indices are stored inside
  434. * the result object.
  435. *
  436. * Params:
  437. * result = the result object in which the indices of the nearest-neighbors are stored
  438. * vec = the vector for which to search the nearest neighbors
  439. * searchParams = parameters that influence the search algorithm (checks, cb_index)
  440. */
  441. void findNeighbors(ResultSet<DistanceType>& result, const ElementType* vec, const SearchParams& searchParams) CV_OVERRIDE
  442. {
  443. const int maxChecks = get_param(searchParams,"checks",32);
  444. if (maxChecks==FLANN_CHECKS_UNLIMITED) {
  445. findExactNN(root_[0], result, vec);
  446. }
  447. else {
  448. // Priority queue storing intermediate branches in the best-bin-first search
  449. Heap<BranchSt>* heap = new Heap<BranchSt>((int)size_);
  450. int checks = 0;
  451. for (int i=0; i<trees_; ++i) {
  452. findNN(root_[i], result, vec, checks, maxChecks, heap);
  453. if ((checks >= maxChecks) && result.full())
  454. break;
  455. }
  456. BranchSt branch;
  457. while (heap->popMin(branch) && (checks<maxChecks || !result.full())) {
  458. KMeansNodePtr node = branch.node;
  459. findNN(node, result, vec, checks, maxChecks, heap);
  460. }
  461. delete heap;
  462. CV_Assert(result.full());
  463. }
  464. }
  465. /**
  466. * Clustering function that takes a cut in the hierarchical k-means
  467. * tree and return the clusters centers of that clustering.
  468. * Params:
  469. * numClusters = number of clusters to have in the clustering computed
  470. * Returns: number of cluster centers
  471. */
  472. int getClusterCenters(Matrix<CentersType>& centers)
  473. {
  474. int numClusters = centers.rows;
  475. if (numClusters<1) {
  476. FLANN_THROW(cv::Error::StsBadArg, "Number of clusters must be at least 1");
  477. }
  478. DistanceType variance;
  479. KMeansNodePtr* clusters = new KMeansNodePtr[numClusters];
  480. int clusterCount = getMinVarianceClusters(root_[0], clusters, numClusters, variance);
  481. Logger::info("Clusters requested: %d, returning %d\n",numClusters, clusterCount);
  482. for (int i=0; i<clusterCount; ++i) {
  483. CentersType* center = clusters[i]->pivot;
  484. for (size_t j=0; j<veclen_; ++j) {
  485. centers[i][j] = center[j];
  486. }
  487. }
  488. delete[] clusters;
  489. return clusterCount;
  490. }
  491. IndexParams getParameters() const CV_OVERRIDE
  492. {
  493. return index_params_;
  494. }
  495. private:
  496. /**
  497. * Structure representing a node in the hierarchical k-means tree.
  498. */
  499. struct KMeansNode
  500. {
  501. /**
  502. * The cluster center.
  503. */
  504. CentersType* pivot;
  505. /**
  506. * The cluster radius.
  507. */
  508. DistanceType radius;
  509. /**
  510. * The cluster mean radius.
  511. */
  512. DistanceType mean_radius;
  513. /**
  514. * The cluster variance.
  515. */
  516. DistanceType variance;
  517. /**
  518. * The cluster size (number of points in the cluster)
  519. */
  520. int size;
  521. /**
  522. * Child nodes (only for non-terminal nodes)
  523. */
  524. KMeansNode** childs;
  525. /**
  526. * Node points (only for terminal nodes)
  527. */
  528. int* indices;
  529. /**
  530. * Level
  531. */
  532. int level;
  533. };
  534. typedef KMeansNode* KMeansNodePtr;
  535. /**
  536. * Alias definition for a nicer syntax.
  537. */
  538. typedef BranchStruct<KMeansNodePtr, DistanceType> BranchSt;
  539. void save_tree(FILE* stream, KMeansNodePtr node, int num)
  540. {
  541. save_value(stream, *node);
  542. save_value(stream, *(node->pivot), (int)veclen_);
  543. if (node->childs==NULL) {
  544. int indices_offset = (int)(node->indices - indices_[num]);
  545. save_value(stream, indices_offset);
  546. }
  547. else {
  548. for(int i=0; i<branching_; ++i) {
  549. save_tree(stream, node->childs[i], num);
  550. }
  551. }
  552. }
  553. void load_tree(FILE* stream, KMeansNodePtr& node, int num)
  554. {
  555. node = pool_.allocate<KMeansNode>();
  556. load_value(stream, *node);
  557. node->pivot = new CentersType[veclen_];
  558. load_value(stream, *(node->pivot), (int)veclen_);
  559. if (node->childs==NULL) {
  560. int indices_offset;
  561. load_value(stream, indices_offset);
  562. node->indices = indices_[num] + indices_offset;
  563. }
  564. else {
  565. node->childs = pool_.allocate<KMeansNodePtr>(branching_);
  566. for(int i=0; i<branching_; ++i) {
  567. load_tree(stream, node->childs[i], num);
  568. }
  569. }
  570. }
  571. /**
  572. * Helper function
  573. */
  574. void free_centers(KMeansNodePtr node)
  575. {
  576. delete[] node->pivot;
  577. if (node->childs!=NULL) {
  578. for (int k=0; k<branching_; ++k) {
  579. free_centers(node->childs[k]);
  580. }
  581. }
  582. }
  583. void free_centers()
  584. {
  585. if (root_ != NULL) {
  586. for(int i=0; i<trees_; ++i) {
  587. if (root_[i] != NULL) {
  588. free_centers(root_[i]);
  589. }
  590. }
  591. }
  592. }
  593. /**
  594. * Release the inner elements of indices[]
  595. */
  596. void free_indices()
  597. {
  598. if (indices_!=NULL) {
  599. for(int i=0; i<trees_; ++i) {
  600. if (indices_[i]!=NULL) {
  601. delete[] indices_[i];
  602. indices_[i] = NULL;
  603. }
  604. }
  605. }
  606. }
  607. /**
  608. * Computes the statistics of a node (mean, radius, variance).
  609. *
  610. * Params:
  611. * node = the node to use
  612. * indices = array of indices of the points belonging to the node
  613. * indices_length = number of indices in the array
  614. */
  615. void computeNodeStatistics(KMeansNodePtr node, int* indices, unsigned int indices_length)
  616. {
  617. DistanceType variance = 0;
  618. CentersType* mean = new CentersType[veclen_];
  619. memoryCounter_ += int(veclen_*sizeof(CentersType));
  620. memset(mean,0,veclen_*sizeof(CentersType));
  621. for (unsigned int i=0; i<indices_length; ++i) {
  622. ElementType* vec = dataset_[indices[i]];
  623. for (size_t j=0; j<veclen_; ++j) {
  624. mean[j] += vec[j];
  625. }
  626. variance += distance_(vec, ZeroIterator<ElementType>(), veclen_);
  627. }
  628. float length = static_cast<float>(indices_length);
  629. for (size_t j=0; j<veclen_; ++j) {
  630. mean[j] = cvflann::round<CentersType>( mean[j] / static_cast<double>(indices_length) );
  631. }
  632. variance /= static_cast<DistanceType>( length );
  633. variance -= distance_(mean, ZeroIterator<ElementType>(), veclen_);
  634. DistanceType radius = 0;
  635. for (unsigned int i=0; i<indices_length; ++i) {
  636. DistanceType tmp = distance_(mean, dataset_[indices[i]], veclen_);
  637. if (tmp>radius) {
  638. radius = tmp;
  639. }
  640. }
  641. node->variance = variance;
  642. node->radius = radius;
  643. node->pivot = mean;
  644. }
  645. void computeBitfieldNodeStatistics(KMeansNodePtr node, int* indices,
  646. unsigned int indices_length)
  647. {
  648. const unsigned int accumulator_veclen = static_cast<unsigned int>(
  649. veclen_*sizeof(CentersType)*BITS_PER_CHAR);
  650. unsigned long long variance = 0ull;
  651. CentersType* mean = new CentersType[veclen_];
  652. memoryCounter_ += int(veclen_*sizeof(CentersType));
  653. unsigned int* mean_accumulator = new unsigned int[accumulator_veclen];
  654. memset(mean_accumulator, 0, sizeof(unsigned int)*accumulator_veclen);
  655. for (unsigned int i=0; i<indices_length; ++i) {
  656. variance += static_cast<unsigned long long>( ensureSquareDistance<Distance>(
  657. distance_(dataset_[indices[i]], ZeroIterator<ElementType>(), veclen_)));
  658. unsigned char* vec = (unsigned char*)dataset_[indices[i]];
  659. for (size_t k=0, l=0; k<accumulator_veclen; k+=BITS_PER_CHAR, ++l) {
  660. mean_accumulator[k] += (vec[l]) & 0x01;
  661. mean_accumulator[k+1] += (vec[l]>>1) & 0x01;
  662. mean_accumulator[k+2] += (vec[l]>>2) & 0x01;
  663. mean_accumulator[k+3] += (vec[l]>>3) & 0x01;
  664. mean_accumulator[k+4] += (vec[l]>>4) & 0x01;
  665. mean_accumulator[k+5] += (vec[l]>>5) & 0x01;
  666. mean_accumulator[k+6] += (vec[l]>>6) & 0x01;
  667. mean_accumulator[k+7] += (vec[l]>>7) & 0x01;
  668. }
  669. }
  670. double cnt = static_cast<double>(indices_length);
  671. unsigned char* char_mean = (unsigned char*)mean;
  672. for (size_t k=0, l=0; k<accumulator_veclen; k+=BITS_PER_CHAR, ++l) {
  673. char_mean[l] = static_cast<unsigned char>(
  674. (((int)(0.5 + (double)(mean_accumulator[k]) / cnt)))
  675. | (((int)(0.5 + (double)(mean_accumulator[k+1]) / cnt))<<1)
  676. | (((int)(0.5 + (double)(mean_accumulator[k+2]) / cnt))<<2)
  677. | (((int)(0.5 + (double)(mean_accumulator[k+3]) / cnt))<<3)
  678. | (((int)(0.5 + (double)(mean_accumulator[k+4]) / cnt))<<4)
  679. | (((int)(0.5 + (double)(mean_accumulator[k+5]) / cnt))<<5)
  680. | (((int)(0.5 + (double)(mean_accumulator[k+6]) / cnt))<<6)
  681. | (((int)(0.5 + (double)(mean_accumulator[k+7]) / cnt))<<7));
  682. }
  683. variance = static_cast<unsigned long long>(
  684. 0.5 + static_cast<double>(variance) / static_cast<double>(indices_length));
  685. variance -= static_cast<unsigned long long>(
  686. ensureSquareDistance<Distance>(
  687. distance_(mean, ZeroIterator<ElementType>(), veclen_)));
  688. DistanceType radius = 0;
  689. for (unsigned int i=0; i<indices_length; ++i) {
  690. DistanceType tmp = distance_(mean, dataset_[indices[i]], veclen_);
  691. if (tmp>radius) {
  692. radius = tmp;
  693. }
  694. }
  695. node->variance = static_cast<DistanceType>(variance);
  696. node->radius = radius;
  697. node->pivot = mean;
  698. delete[] mean_accumulator;
  699. }
  700. void computeDnaNodeStatistics(KMeansNodePtr node, int* indices,
  701. unsigned int indices_length)
  702. {
  703. const unsigned int histos_veclen = static_cast<unsigned int>(
  704. veclen_*sizeof(CentersType)*(HISTOS_PER_BASE*BASE_PER_CHAR));
  705. unsigned long long variance = 0ull;
  706. unsigned int* histograms = new unsigned int[histos_veclen];
  707. memset(histograms, 0, sizeof(unsigned int)*histos_veclen);
  708. for (unsigned int i=0; i<indices_length; ++i) {
  709. variance += static_cast<unsigned long long>( ensureSquareDistance<Distance>(
  710. distance_(dataset_[indices[i]], ZeroIterator<ElementType>(), veclen_)));
  711. unsigned char* vec = (unsigned char*)dataset_[indices[i]];
  712. for (size_t k=0, l=0; k<histos_veclen; k+=HISTOS_PER_BASE*BASE_PER_CHAR, ++l) {
  713. histograms[k + ((vec[l]) & 0x03)]++;
  714. histograms[k + 4 + ((vec[l]>>2) & 0x03)]++;
  715. histograms[k + 8 + ((vec[l]>>4) & 0x03)]++;
  716. histograms[k +12 + ((vec[l]>>6) & 0x03)]++;
  717. }
  718. }
  719. CentersType* mean = new CentersType[veclen_];
  720. memoryCounter_ += int(veclen_*sizeof(CentersType));
  721. unsigned char* char_mean = (unsigned char*)mean;
  722. unsigned int* h = histograms;
  723. for (size_t k=0, l=0; k<histos_veclen; k+=HISTOS_PER_BASE*BASE_PER_CHAR, ++l) {
  724. char_mean[l] = (h[k] > h[k+1] ? h[k+2] > h[k+3] ? h[k] > h[k+2] ? 0x00 : 0x10
  725. : h[k] > h[k+3] ? 0x00 : 0x11
  726. : h[k+2] > h[k+3] ? h[k+1] > h[k+2] ? 0x01 : 0x10
  727. : h[k+1] > h[k+3] ? 0x01 : 0x11)
  728. | (h[k+4]>h[k+5] ? h[k+6] > h[k+7] ? h[k+4] > h[k+6] ? 0x00 : 0x1000
  729. : h[k+4] > h[k+7] ? 0x00 : 0x1100
  730. : h[k+6] > h[k+7] ? h[k+5] > h[k+6] ? 0x0100 : 0x1000
  731. : h[k+5] > h[k+7] ? 0x0100 : 0x1100)
  732. | (h[k+8]>h[k+9] ? h[k+10]>h[k+11] ? h[k+8] >h[k+10] ? 0x00 : 0x100000
  733. : h[k+8] >h[k+11] ? 0x00 : 0x110000
  734. : h[k+10]>h[k+11] ? h[k+9] >h[k+10] ? 0x010000 : 0x100000
  735. : h[k+9] >h[k+11] ? 0x010000 : 0x110000)
  736. | (h[k+12]>h[k+13] ? h[k+14]>h[k+15] ? h[k+12] >h[k+14] ? 0x00 : 0x10000000
  737. : h[k+12] >h[k+15] ? 0x00 : 0x11000000
  738. : h[k+14]>h[k+15] ? h[k+13] >h[k+14] ? 0x01000000 : 0x10000000
  739. : h[k+13] >h[k+15] ? 0x01000000 : 0x11000000);
  740. }
  741. variance = static_cast<unsigned long long>(
  742. 0.5 + static_cast<double>(variance) / static_cast<double>(indices_length));
  743. variance -= static_cast<unsigned long long>(
  744. ensureSquareDistance<Distance>(
  745. distance_(mean, ZeroIterator<ElementType>(), veclen_)));
  746. DistanceType radius = 0;
  747. for (unsigned int i=0; i<indices_length; ++i) {
  748. DistanceType tmp = distance_(mean, dataset_[indices[i]], veclen_);
  749. if (tmp>radius) {
  750. radius = tmp;
  751. }
  752. }
  753. node->variance = static_cast<DistanceType>(variance);
  754. node->radius = radius;
  755. node->pivot = mean;
  756. delete[] histograms;
  757. }
  758. template<typename DistType>
  759. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  760. unsigned int indices_length,
  761. const DistType* identifier)
  762. {
  763. (void)identifier;
  764. computeNodeStatistics(node, indices, indices_length);
  765. }
  766. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  767. unsigned int indices_length,
  768. const cvflann::HammingLUT* identifier)
  769. {
  770. (void)identifier;
  771. computeBitfieldNodeStatistics(node, indices, indices_length);
  772. }
  773. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  774. unsigned int indices_length,
  775. const cvflann::Hamming<unsigned char>* identifier)
  776. {
  777. (void)identifier;
  778. computeBitfieldNodeStatistics(node, indices, indices_length);
  779. }
  780. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  781. unsigned int indices_length,
  782. const cvflann::Hamming2<unsigned char>* identifier)
  783. {
  784. (void)identifier;
  785. computeBitfieldNodeStatistics(node, indices, indices_length);
  786. }
  787. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  788. unsigned int indices_length,
  789. const cvflann::DNAmmingLUT* identifier)
  790. {
  791. (void)identifier;
  792. computeDnaNodeStatistics(node, indices, indices_length);
  793. }
  794. void computeNodeStatistics(KMeansNodePtr node, int* indices,
  795. unsigned int indices_length,
  796. const cvflann::DNAmming2<unsigned char>* identifier)
  797. {
  798. (void)identifier;
  799. computeDnaNodeStatistics(node, indices, indices_length);
  800. }
  801. void refineClustering(int* indices, int indices_length, int branching, CentersType** centers,
  802. std::vector<DistanceType>& radiuses, int* belongs_to, int* count)
  803. {
  804. cv::AutoBuffer<double> dcenters_buf(branching*veclen_);
  805. Matrix<double> dcenters(dcenters_buf.data(), branching, veclen_);
  806. bool converged = false;
  807. int iteration = 0;
  808. while (!converged && iteration<iterations_) {
  809. converged = true;
  810. iteration++;
  811. // compute the new cluster centers
  812. for (int i=0; i<branching; ++i) {
  813. memset(dcenters[i],0,sizeof(double)*veclen_);
  814. radiuses[i] = 0;
  815. }
  816. for (int i=0; i<indices_length; ++i) {
  817. ElementType* vec = dataset_[indices[i]];
  818. double* center = dcenters[belongs_to[i]];
  819. for (size_t k=0; k<veclen_; ++k) {
  820. center[k] += vec[k];
  821. }
  822. }
  823. for (int i=0; i<branching; ++i) {
  824. int cnt = count[i];
  825. for (size_t k=0; k<veclen_; ++k) {
  826. dcenters[i][k] /= cnt;
  827. }
  828. }
  829. std::vector<int> new_centroids(indices_length);
  830. std::vector<DistanceType> sq_dists(indices_length);
  831. // reassign points to clusters
  832. KMeansDistanceComputer<Matrix<double> > invoker(
  833. distance_, dataset_, branching, indices, dcenters, veclen_, new_centroids, sq_dists);
  834. parallel_for_(cv::Range(0, (int)indices_length), invoker);
  835. for (int i=0; i < (int)indices_length; ++i) {
  836. DistanceType sq_dist(sq_dists[i]);
  837. int new_centroid(new_centroids[i]);
  838. if (sq_dist > radiuses[new_centroid]) {
  839. radiuses[new_centroid] = sq_dist;
  840. }
  841. if (new_centroid != belongs_to[i]) {
  842. count[belongs_to[i]]--;
  843. count[new_centroid]++;
  844. belongs_to[i] = new_centroid;
  845. converged = false;
  846. }
  847. }
  848. for (int i=0; i<branching; ++i) {
  849. // if one cluster converges to an empty cluster,
  850. // move an element into that cluster
  851. if (count[i]==0) {
  852. int j = (i+1)%branching;
  853. while (count[j]<=1) {
  854. j = (j+1)%branching;
  855. }
  856. for (int k=0; k<indices_length; ++k) {
  857. if (belongs_to[k]==j) {
  858. // for cluster j, we move the furthest element from the center to the empty cluster i
  859. if ( distance_(dataset_[indices[k]], dcenters[j], veclen_) == radiuses[j] ) {
  860. belongs_to[k] = i;
  861. count[j]--;
  862. count[i]++;
  863. break;
  864. }
  865. }
  866. }
  867. converged = false;
  868. }
  869. }
  870. }
  871. for (int i=0; i<branching; ++i) {
  872. centers[i] = new CentersType[veclen_];
  873. memoryCounter_ += (int)(veclen_*sizeof(CentersType));
  874. for (size_t k=0; k<veclen_; ++k) {
  875. centers[i][k] = (CentersType)dcenters[i][k];
  876. }
  877. }
  878. }
  879. void refineBitfieldClustering(int* indices, int indices_length, int branching, CentersType** centers,
  880. std::vector<DistanceType>& radiuses, int* belongs_to, int* count)
  881. {
  882. for (int i=0; i<branching; ++i) {
  883. centers[i] = new CentersType[veclen_];
  884. memoryCounter_ += (int)(veclen_*sizeof(CentersType));
  885. }
  886. const unsigned int accumulator_veclen = static_cast<unsigned int>(
  887. veclen_*sizeof(ElementType)*BITS_PER_CHAR);
  888. cv::AutoBuffer<unsigned int> dcenters_buf(branching*accumulator_veclen);
  889. Matrix<unsigned int> dcenters(dcenters_buf.data(), branching, accumulator_veclen);
  890. bool converged = false;
  891. int iteration = 0;
  892. while (!converged && iteration<iterations_) {
  893. converged = true;
  894. iteration++;
  895. // compute the new cluster centers
  896. for (int i=0; i<branching; ++i) {
  897. memset(dcenters[i],0,sizeof(unsigned int)*accumulator_veclen);
  898. radiuses[i] = 0;
  899. }
  900. for (int i=0; i<indices_length; ++i) {
  901. unsigned char* vec = (unsigned char*)dataset_[indices[i]];
  902. unsigned int* dcenter = dcenters[belongs_to[i]];
  903. for (size_t k=0, l=0; k<accumulator_veclen; k+=BITS_PER_CHAR, ++l) {
  904. dcenter[k] += (vec[l]) & 0x01;
  905. dcenter[k+1] += (vec[l]>>1) & 0x01;
  906. dcenter[k+2] += (vec[l]>>2) & 0x01;
  907. dcenter[k+3] += (vec[l]>>3) & 0x01;
  908. dcenter[k+4] += (vec[l]>>4) & 0x01;
  909. dcenter[k+5] += (vec[l]>>5) & 0x01;
  910. dcenter[k+6] += (vec[l]>>6) & 0x01;
  911. dcenter[k+7] += (vec[l]>>7) & 0x01;
  912. }
  913. }
  914. for (int i=0; i<branching; ++i) {
  915. double cnt = static_cast<double>(count[i]);
  916. unsigned int* dcenter = dcenters[i];
  917. unsigned char* charCenter = (unsigned char*)centers[i];
  918. for (size_t k=0, l=0; k<accumulator_veclen; k+=BITS_PER_CHAR, ++l) {
  919. charCenter[l] = static_cast<unsigned char>(
  920. (((int)(0.5 + (double)(dcenter[k]) / cnt)))
  921. | (((int)(0.5 + (double)(dcenter[k+1]) / cnt))<<1)
  922. | (((int)(0.5 + (double)(dcenter[k+2]) / cnt))<<2)
  923. | (((int)(0.5 + (double)(dcenter[k+3]) / cnt))<<3)
  924. | (((int)(0.5 + (double)(dcenter[k+4]) / cnt))<<4)
  925. | (((int)(0.5 + (double)(dcenter[k+5]) / cnt))<<5)
  926. | (((int)(0.5 + (double)(dcenter[k+6]) / cnt))<<6)
  927. | (((int)(0.5 + (double)(dcenter[k+7]) / cnt))<<7));
  928. }
  929. }
  930. std::vector<int> new_centroids(indices_length);
  931. std::vector<DistanceType> dists(indices_length);
  932. // reassign points to clusters
  933. KMeansDistanceComputer<ElementType**> invoker(
  934. distance_, dataset_, branching, indices, centers, veclen_, new_centroids, dists);
  935. parallel_for_(cv::Range(0, (int)indices_length), invoker);
  936. for (int i=0; i < indices_length; ++i) {
  937. DistanceType dist(dists[i]);
  938. int new_centroid(new_centroids[i]);
  939. if (dist > radiuses[new_centroid]) {
  940. radiuses[new_centroid] = dist;
  941. }
  942. if (new_centroid != belongs_to[i]) {
  943. count[belongs_to[i]]--;
  944. count[new_centroid]++;
  945. belongs_to[i] = new_centroid;
  946. converged = false;
  947. }
  948. }
  949. for (int i=0; i<branching; ++i) {
  950. // if one cluster converges to an empty cluster,
  951. // move an element into that cluster
  952. if (count[i]==0) {
  953. int j = (i+1)%branching;
  954. while (count[j]<=1) {
  955. j = (j+1)%branching;
  956. }
  957. for (int k=0; k<indices_length; ++k) {
  958. if (belongs_to[k]==j) {
  959. // for cluster j, we move the furthest element from the center to the empty cluster i
  960. if ( distance_(dataset_[indices[k]], centers[j], veclen_) == radiuses[j] ) {
  961. belongs_to[k] = i;
  962. count[j]--;
  963. count[i]++;
  964. break;
  965. }
  966. }
  967. }
  968. converged = false;
  969. }
  970. }
  971. }
  972. }
  973. void refineDnaClustering(int* indices, int indices_length, int branching, CentersType** centers,
  974. std::vector<DistanceType>& radiuses, int* belongs_to, int* count)
  975. {
  976. for (int i=0; i<branching; ++i) {
  977. centers[i] = new CentersType[veclen_];
  978. memoryCounter_ += (int)(veclen_*sizeof(CentersType));
  979. }
  980. const unsigned int histos_veclen = static_cast<unsigned int>(
  981. veclen_*sizeof(CentersType)*(HISTOS_PER_BASE*BASE_PER_CHAR));
  982. cv::AutoBuffer<unsigned int> histos_buf(branching*histos_veclen);
  983. Matrix<unsigned int> histos(histos_buf.data(), branching, histos_veclen);
  984. bool converged = false;
  985. int iteration = 0;
  986. while (!converged && iteration<iterations_) {
  987. converged = true;
  988. iteration++;
  989. // compute the new cluster centers
  990. for (int i=0; i<branching; ++i) {
  991. memset(histos[i],0,sizeof(unsigned int)*histos_veclen);
  992. radiuses[i] = 0;
  993. }
  994. for (int i=0; i<indices_length; ++i) {
  995. unsigned char* vec = (unsigned char*)dataset_[indices[i]];
  996. unsigned int* h = histos[belongs_to[i]];
  997. for (size_t k=0, l=0; k<histos_veclen; k+=HISTOS_PER_BASE*BASE_PER_CHAR, ++l) {
  998. h[k + ((vec[l]) & 0x03)]++;
  999. h[k + 4 + ((vec[l]>>2) & 0x03)]++;
  1000. h[k + 8 + ((vec[l]>>4) & 0x03)]++;
  1001. h[k +12 + ((vec[l]>>6) & 0x03)]++;
  1002. }
  1003. }
  1004. for (int i=0; i<branching; ++i) {
  1005. unsigned int* h = histos[i];
  1006. unsigned char* charCenter = (unsigned char*)centers[i];
  1007. for (size_t k=0, l=0; k<histos_veclen; k+=HISTOS_PER_BASE*BASE_PER_CHAR, ++l) {
  1008. charCenter[l]= (h[k] > h[k+1] ? h[k+2] > h[k+3] ? h[k] > h[k+2] ? 0x00 : 0x10
  1009. : h[k] > h[k+3] ? 0x00 : 0x11
  1010. : h[k+2] > h[k+3] ? h[k+1] > h[k+2] ? 0x01 : 0x10
  1011. : h[k+1] > h[k+3] ? 0x01 : 0x11)
  1012. | (h[k+4]>h[k+5] ? h[k+6] > h[k+7] ? h[k+4] > h[k+6] ? 0x00 : 0x1000
  1013. : h[k+4] > h[k+7] ? 0x00 : 0x1100
  1014. : h[k+6] > h[k+7] ? h[k+5] > h[k+6] ? 0x0100 : 0x1000
  1015. : h[k+5] > h[k+7] ? 0x0100 : 0x1100)
  1016. | (h[k+8]>h[k+9] ? h[k+10]>h[k+11] ? h[k+8] >h[k+10] ? 0x00 : 0x100000
  1017. : h[k+8] >h[k+11] ? 0x00 : 0x110000
  1018. : h[k+10]>h[k+11] ? h[k+9] >h[k+10] ? 0x010000 : 0x100000
  1019. : h[k+9] >h[k+11] ? 0x010000 : 0x110000)
  1020. | (h[k+12]>h[k+13] ? h[k+14]>h[k+15] ? h[k+12] >h[k+14] ? 0x00 : 0x10000000
  1021. : h[k+12] >h[k+15] ? 0x00 : 0x11000000
  1022. : h[k+14]>h[k+15] ? h[k+13] >h[k+14] ? 0x01000000 : 0x10000000
  1023. : h[k+13] >h[k+15] ? 0x01000000 : 0x11000000);
  1024. }
  1025. }
  1026. std::vector<int> new_centroids(indices_length);
  1027. std::vector<DistanceType> dists(indices_length);
  1028. // reassign points to clusters
  1029. KMeansDistanceComputer<ElementType**> invoker(
  1030. distance_, dataset_, branching, indices, centers, veclen_, new_centroids, dists);
  1031. parallel_for_(cv::Range(0, (int)indices_length), invoker);
  1032. for (int i=0; i < indices_length; ++i) {
  1033. DistanceType dist(dists[i]);
  1034. int new_centroid(new_centroids[i]);
  1035. if (dist > radiuses[new_centroid]) {
  1036. radiuses[new_centroid] = dist;
  1037. }
  1038. if (new_centroid != belongs_to[i]) {
  1039. count[belongs_to[i]]--;
  1040. count[new_centroid]++;
  1041. belongs_to[i] = new_centroid;
  1042. converged = false;
  1043. }
  1044. }
  1045. for (int i=0; i<branching; ++i) {
  1046. // if one cluster converges to an empty cluster,
  1047. // move an element into that cluster
  1048. if (count[i]==0) {
  1049. int j = (i+1)%branching;
  1050. while (count[j]<=1) {
  1051. j = (j+1)%branching;
  1052. }
  1053. for (int k=0; k<indices_length; ++k) {
  1054. if (belongs_to[k]==j) {
  1055. // for cluster j, we move the furthest element from the center to the empty cluster i
  1056. if ( distance_(dataset_[indices[k]], centers[j], veclen_) == radiuses[j] ) {
  1057. belongs_to[k] = i;
  1058. count[j]--;
  1059. count[i]++;
  1060. break;
  1061. }
  1062. }
  1063. }
  1064. converged = false;
  1065. }
  1066. }
  1067. }
  1068. }
  1069. void computeSubClustering(KMeansNodePtr node, int* indices, int indices_length,
  1070. int branching, int level, CentersType** centers,
  1071. std::vector<DistanceType>& radiuses, int* belongs_to, int* count)
  1072. {
  1073. // compute kmeans clustering for each of the resulting clusters
  1074. node->childs = pool_.allocate<KMeansNodePtr>(branching);
  1075. int start = 0;
  1076. int end = start;
  1077. for (int c=0; c<branching; ++c) {
  1078. int s = count[c];
  1079. DistanceType variance = 0;
  1080. DistanceType mean_radius =0;
  1081. for (int i=0; i<indices_length; ++i) {
  1082. if (belongs_to[i]==c) {
  1083. DistanceType d = distance_(dataset_[indices[i]], ZeroIterator<ElementType>(), veclen_);
  1084. variance += d;
  1085. mean_radius += static_cast<DistanceType>( sqrt(d) );
  1086. std::swap(indices[i],indices[end]);
  1087. std::swap(belongs_to[i],belongs_to[end]);
  1088. end++;
  1089. }
  1090. }
  1091. variance /= s;
  1092. mean_radius /= s;
  1093. variance -= distance_(centers[c], ZeroIterator<ElementType>(), veclen_);
  1094. node->childs[c] = pool_.allocate<KMeansNode>();
  1095. std::memset(node->childs[c], 0, sizeof(KMeansNode));
  1096. node->childs[c]->radius = radiuses[c];
  1097. node->childs[c]->pivot = centers[c];
  1098. node->childs[c]->variance = variance;
  1099. node->childs[c]->mean_radius = mean_radius;
  1100. computeClustering(node->childs[c],indices+start, end-start, branching, level+1);
  1101. start=end;
  1102. }
  1103. }
  1104. void computeAnyBitfieldSubClustering(KMeansNodePtr node, int* indices, int indices_length,
  1105. int branching, int level, CentersType** centers,
  1106. std::vector<DistanceType>& radiuses, int* belongs_to, int* count)
  1107. {
  1108. // compute kmeans clustering for each of the resulting clusters
  1109. node->childs = pool_.allocate<KMeansNodePtr>(branching);
  1110. int start = 0;
  1111. int end = start;
  1112. for (int c=0; c<branching; ++c) {
  1113. int s = count[c];
  1114. unsigned long long variance = 0ull;
  1115. DistanceType mean_radius =0;
  1116. for (int i=0; i<indices_length; ++i) {
  1117. if (belongs_to[i]==c) {
  1118. DistanceType d = distance_(dataset_[indices[i]], ZeroIterator<ElementType>(), veclen_);
  1119. variance += static_cast<unsigned long long>( ensureSquareDistance<Distance>(d) );
  1120. mean_radius += ensureSimpleDistance<Distance>(d);
  1121. std::swap(indices[i],indices[end]);
  1122. std::swap(belongs_to[i],belongs_to[end]);
  1123. end++;
  1124. }
  1125. }
  1126. mean_radius = static_cast<DistanceType>(
  1127. 0.5f + static_cast<float>(mean_radius) / static_cast<float>(s));
  1128. variance = static_cast<unsigned long long>(
  1129. 0.5 + static_cast<double>(variance) / static_cast<double>(s));
  1130. variance -= static_cast<unsigned long long>(
  1131. ensureSquareDistance<Distance>(
  1132. distance_(centers[c], ZeroIterator<ElementType>(), veclen_)));
  1133. node->childs[c] = pool_.allocate<KMeansNode>();
  1134. std::memset(node->childs[c], 0, sizeof(KMeansNode));
  1135. node->childs[c]->radius = radiuses[c];
  1136. node->childs[c]->pivot = centers[c];
  1137. node->childs[c]->variance = static_cast<DistanceType>(variance);
  1138. node->childs[c]->mean_radius = mean_radius;
  1139. computeClustering(node->childs[c],indices+start, end-start, branching, level+1);
  1140. start=end;
  1141. }
  1142. }
  1143. template<typename DistType>
  1144. void refineAndSplitClustering(
  1145. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1146. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1147. int* belongs_to, int* count, const DistType* identifier)
  1148. {
  1149. (void)identifier;
  1150. refineClustering(indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1151. computeSubClustering(node, indices, indices_length, branching,
  1152. level, centers, radiuses, belongs_to, count);
  1153. }
  1154. /**
  1155. * The methods responsible with doing the recursive hierarchical clustering on
  1156. * binary vectors.
  1157. * As some might have heard that KMeans on binary data doesn't make sense,
  1158. * it's worth a little explanation why it actually fairly works. As
  1159. * with the Hierarchical Clustering algortihm, we seed several centers for the
  1160. * current node by picking some of its points. Then in a first pass each point
  1161. * of the node is then related to its closest center. Now let's have a look at
  1162. * the 5 central dimensions of the 9 following points:
  1163. *
  1164. * xxxxxx11100xxxxx (1)
  1165. * xxxxxx11010xxxxx (2)
  1166. * xxxxxx11001xxxxx (3)
  1167. * xxxxxx10110xxxxx (4)
  1168. * xxxxxx10101xxxxx (5)
  1169. * xxxxxx10011xxxxx (6)
  1170. * xxxxxx01110xxxxx (7)
  1171. * xxxxxx01101xxxxx (8)
  1172. * xxxxxx01011xxxxx (9)
  1173. * sum _____
  1174. * of 1: 66555
  1175. *
  1176. * Even if the barycenter notion doesn't apply, we can set a center
  1177. * xxxxxx11111xxxxx that will better fit the five dimensions we are focusing
  1178. * on for these points.
  1179. *
  1180. * Note that convergence isn't ensured anymore. In practice, using Gonzales
  1181. * as seeding algorithm should be fine for getting convergence ("iterations"
  1182. * value can be set to -1). But with KMeans++ seeding you should definitely
  1183. * set a maximum number of iterations (but make it higher than the "iterations"
  1184. * default value of 11).
  1185. *
  1186. * Params:
  1187. * node = the node to cluster
  1188. * indices = indices of the points belonging to the current node
  1189. * indices_length = number of points in the current node
  1190. * branching = the branching factor to use in the clustering
  1191. * level = 0 for the root node, it increases with the subdivision levels
  1192. * centers = clusters centers to compute
  1193. * radiuses = radiuses of clusters
  1194. * belongs_to = LookUp Table returning, for a given indice id, the center id it belongs to
  1195. * count = array storing the number of indices for a given center id
  1196. * identifier = dummy pointer on an instance of Distance (use to branch correctly among templates)
  1197. */
  1198. void refineAndSplitClustering(
  1199. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1200. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1201. int* belongs_to, int* count, const cvflann::HammingLUT* identifier)
  1202. {
  1203. (void)identifier;
  1204. refineBitfieldClustering(
  1205. indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1206. computeAnyBitfieldSubClustering(node, indices, indices_length, branching,
  1207. level, centers, radiuses, belongs_to, count);
  1208. }
  1209. void refineAndSplitClustering(
  1210. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1211. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1212. int* belongs_to, int* count, const cvflann::Hamming<unsigned char>* identifier)
  1213. {
  1214. (void)identifier;
  1215. refineBitfieldClustering(
  1216. indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1217. computeAnyBitfieldSubClustering(node, indices, indices_length, branching,
  1218. level, centers, radiuses, belongs_to, count);
  1219. }
  1220. void refineAndSplitClustering(
  1221. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1222. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1223. int* belongs_to, int* count, const cvflann::Hamming2<unsigned char>* identifier)
  1224. {
  1225. (void)identifier;
  1226. refineBitfieldClustering(
  1227. indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1228. computeAnyBitfieldSubClustering(node, indices, indices_length, branching,
  1229. level, centers, radiuses, belongs_to, count);
  1230. }
  1231. void refineAndSplitClustering(
  1232. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1233. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1234. int* belongs_to, int* count, const cvflann::DNAmmingLUT* identifier)
  1235. {
  1236. (void)identifier;
  1237. refineDnaClustering(
  1238. indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1239. computeAnyBitfieldSubClustering(node, indices, indices_length, branching,
  1240. level, centers, radiuses, belongs_to, count);
  1241. }
  1242. void refineAndSplitClustering(
  1243. KMeansNodePtr node, int* indices, int indices_length, int branching,
  1244. int level, CentersType** centers, std::vector<DistanceType>& radiuses,
  1245. int* belongs_to, int* count, const cvflann::DNAmming2<unsigned char>* identifier)
  1246. {
  1247. (void)identifier;
  1248. refineDnaClustering(
  1249. indices, indices_length, branching, centers, radiuses, belongs_to, count);
  1250. computeAnyBitfieldSubClustering(node, indices, indices_length, branching,
  1251. level, centers, radiuses, belongs_to, count);
  1252. }
  1253. /**
  1254. * The method responsible with actually doing the recursive hierarchical
  1255. * clustering
  1256. *
  1257. * Params:
  1258. * node = the node to cluster
  1259. * indices = indices of the points belonging to the current node
  1260. * branching = the branching factor to use in the clustering
  1261. *
  1262. * TODO: for 1-sized clusters don't store a cluster center (it's the same as the single cluster point)
  1263. */
  1264. void computeClustering(KMeansNodePtr node, int* indices, int indices_length, int branching, int level)
  1265. {
  1266. node->size = indices_length;
  1267. node->level = level;
  1268. if (indices_length < branching) {
  1269. node->indices = indices;
  1270. std::sort(node->indices,node->indices+indices_length);
  1271. node->childs = NULL;
  1272. return;
  1273. }
  1274. cv::AutoBuffer<int> centers_idx_buf(branching);
  1275. int* centers_idx = centers_idx_buf.data();
  1276. int centers_length;
  1277. (this->*chooseCenters)(branching, indices, indices_length, centers_idx, centers_length);
  1278. if (centers_length<branching) {
  1279. node->indices = indices;
  1280. std::sort(node->indices,node->indices+indices_length);
  1281. node->childs = NULL;
  1282. return;
  1283. }
  1284. std::vector<DistanceType> radiuses(branching);
  1285. cv::AutoBuffer<int> count_buf(branching);
  1286. int* count = count_buf.data();
  1287. for (int i=0; i<branching; ++i) {
  1288. radiuses[i] = 0;
  1289. count[i] = 0;
  1290. }
  1291. // assign points to clusters
  1292. cv::AutoBuffer<int> belongs_to_buf(indices_length);
  1293. int* belongs_to = belongs_to_buf.data();
  1294. for (int i=0; i<indices_length; ++i) {
  1295. DistanceType sq_dist = distance_(dataset_[indices[i]], dataset_[centers_idx[0]], veclen_);
  1296. belongs_to[i] = 0;
  1297. for (int j=1; j<branching; ++j) {
  1298. DistanceType new_sq_dist = distance_(dataset_[indices[i]], dataset_[centers_idx[j]], veclen_);
  1299. if (sq_dist>new_sq_dist) {
  1300. belongs_to[i] = j;
  1301. sq_dist = new_sq_dist;
  1302. }
  1303. }
  1304. if (sq_dist>radiuses[belongs_to[i]]) {
  1305. radiuses[belongs_to[i]] = sq_dist;
  1306. }
  1307. count[belongs_to[i]]++;
  1308. }
  1309. CentersType** centers = new CentersType*[branching];
  1310. Distance* dummy = NULL;
  1311. refineAndSplitClustering(node, indices, indices_length, branching, level,
  1312. centers, radiuses, belongs_to, count, dummy);
  1313. delete[] centers;
  1314. }
  1315. /**
  1316. * Performs one descent in the hierarchical k-means tree. The branches not
  1317. * visited are stored in a priority queue.
  1318. *
  1319. * Params:
  1320. * node = node to explore
  1321. * result = container for the k-nearest neighbors found
  1322. * vec = query points
  1323. * checks = how many points in the dataset have been checked so far
  1324. * maxChecks = maximum dataset points to checks
  1325. */
  1326. void findNN(KMeansNodePtr node, ResultSet<DistanceType>& result, const ElementType* vec, int& checks, int maxChecks,
  1327. Heap<BranchSt>* heap)
  1328. {
  1329. // Ignore those clusters that are too far away
  1330. {
  1331. DistanceType bsq = distance_(vec, node->pivot, veclen_);
  1332. DistanceType rsq = node->radius;
  1333. DistanceType wsq = result.worstDist();
  1334. if (isSquareDistance<Distance>())
  1335. {
  1336. DistanceType val = bsq-rsq-wsq;
  1337. if ((val>0) && (val*val > 4*rsq*wsq))
  1338. return;
  1339. }
  1340. else
  1341. {
  1342. if (bsq-rsq > wsq)
  1343. return;
  1344. }
  1345. }
  1346. if (node->childs==NULL) {
  1347. if ((checks>=maxChecks) && result.full()) {
  1348. return;
  1349. }
  1350. checks += node->size;
  1351. for (int i=0; i<node->size; ++i) {
  1352. int index = node->indices[i];
  1353. DistanceType dist = distance_(dataset_[index], vec, veclen_);
  1354. result.addPoint(dist, index);
  1355. }
  1356. }
  1357. else {
  1358. DistanceType* domain_distances = new DistanceType[branching_];
  1359. int closest_center = exploreNodeBranches(node, vec, domain_distances, heap);
  1360. delete[] domain_distances;
  1361. findNN(node->childs[closest_center],result,vec, checks, maxChecks, heap);
  1362. }
  1363. }
  1364. /**
  1365. * Helper function that computes the nearest childs of a node to a given query point.
  1366. * Params:
  1367. * node = the node
  1368. * q = the query point
  1369. * distances = array with the distances to each child node.
  1370. * Returns:
  1371. */
  1372. int exploreNodeBranches(KMeansNodePtr node, const ElementType* q, DistanceType* domain_distances, Heap<BranchSt>* heap)
  1373. {
  1374. int best_index = 0;
  1375. domain_distances[best_index] = distance_(q, node->childs[best_index]->pivot, veclen_);
  1376. for (int i=1; i<branching_; ++i) {
  1377. domain_distances[i] = distance_(q, node->childs[i]->pivot, veclen_);
  1378. if (domain_distances[i]<domain_distances[best_index]) {
  1379. best_index = i;
  1380. }
  1381. }
  1382. // float* best_center = node->childs[best_index]->pivot;
  1383. for (int i=0; i<branching_; ++i) {
  1384. if (i != best_index) {
  1385. domain_distances[i] -= cvflann::round<DistanceType>(
  1386. cb_index_*node->childs[i]->variance );
  1387. // float dist_to_border = getDistanceToBorder(node.childs[i].pivot,best_center,q);
  1388. // if (domain_distances[i]<dist_to_border) {
  1389. // domain_distances[i] = dist_to_border;
  1390. // }
  1391. heap->insert(BranchSt(node->childs[i],domain_distances[i]));
  1392. }
  1393. }
  1394. return best_index;
  1395. }
  1396. /**
  1397. * Function the performs exact nearest neighbor search by traversing the entire tree.
  1398. */
  1399. void findExactNN(KMeansNodePtr node, ResultSet<DistanceType>& result, const ElementType* vec)
  1400. {
  1401. // Ignore those clusters that are too far away
  1402. {
  1403. DistanceType bsq = distance_(vec, node->pivot, veclen_);
  1404. DistanceType rsq = node->radius;
  1405. DistanceType wsq = result.worstDist();
  1406. if (isSquareDistance<Distance>())
  1407. {
  1408. DistanceType val = bsq-rsq-wsq;
  1409. if ((val>0) && (val*val > 4*rsq*wsq))
  1410. return;
  1411. }
  1412. else
  1413. {
  1414. if (bsq-rsq > wsq)
  1415. return;
  1416. }
  1417. }
  1418. if (node->childs==NULL) {
  1419. for (int i=0; i<node->size; ++i) {
  1420. int index = node->indices[i];
  1421. DistanceType dist = distance_(dataset_[index], vec, veclen_);
  1422. result.addPoint(dist, index);
  1423. }
  1424. }
  1425. else {
  1426. int* sort_indices = new int[branching_];
  1427. getCenterOrdering(node, vec, sort_indices);
  1428. for (int i=0; i<branching_; ++i) {
  1429. findExactNN(node->childs[sort_indices[i]],result,vec);
  1430. }
  1431. delete[] sort_indices;
  1432. }
  1433. }
  1434. /**
  1435. * Helper function.
  1436. *
  1437. * I computes the order in which to traverse the child nodes of a particular node.
  1438. */
  1439. void getCenterOrdering(KMeansNodePtr node, const ElementType* q, int* sort_indices)
  1440. {
  1441. DistanceType* domain_distances = new DistanceType[branching_];
  1442. for (int i=0; i<branching_; ++i) {
  1443. DistanceType dist = distance_(q, node->childs[i]->pivot, veclen_);
  1444. int j=0;
  1445. while (domain_distances[j]<dist && j<i)
  1446. j++;
  1447. for (int k=i; k>j; --k) {
  1448. domain_distances[k] = domain_distances[k-1];
  1449. sort_indices[k] = sort_indices[k-1];
  1450. }
  1451. domain_distances[j] = dist;
  1452. sort_indices[j] = i;
  1453. }
  1454. delete[] domain_distances;
  1455. }
  1456. /**
  1457. * Method that computes the squared distance from the query point q
  1458. * from inside region with center c to the border between this
  1459. * region and the region with center p
  1460. */
  1461. DistanceType getDistanceToBorder(DistanceType* p, DistanceType* c, DistanceType* q)
  1462. {
  1463. DistanceType sum = 0;
  1464. DistanceType sum2 = 0;
  1465. for (int i=0; i<veclen_; ++i) {
  1466. DistanceType t = c[i]-p[i];
  1467. sum += t*(q[i]-(c[i]+p[i])/2);
  1468. sum2 += t*t;
  1469. }
  1470. return sum*sum/sum2;
  1471. }
  1472. /**
  1473. * Helper function the descends in the hierarchical k-means tree by splitting those clusters that minimize
  1474. * the overall variance of the clustering.
  1475. * Params:
  1476. * root = root node
  1477. * clusters = array with clusters centers (return value)
  1478. * varianceValue = variance of the clustering (return value)
  1479. * Returns:
  1480. */
  1481. int getMinVarianceClusters(KMeansNodePtr root, KMeansNodePtr* clusters, int clusters_length, DistanceType& varianceValue)
  1482. {
  1483. int clusterCount = 1;
  1484. clusters[0] = root;
  1485. DistanceType meanVariance = root->variance*root->size;
  1486. while (clusterCount<clusters_length) {
  1487. DistanceType minVariance = (std::numeric_limits<DistanceType>::max)();
  1488. int splitIndex = -1;
  1489. for (int i=0; i<clusterCount; ++i) {
  1490. if (clusters[i]->childs != NULL) {
  1491. DistanceType variance = meanVariance - clusters[i]->variance*clusters[i]->size;
  1492. for (int j=0; j<branching_; ++j) {
  1493. variance += clusters[i]->childs[j]->variance*clusters[i]->childs[j]->size;
  1494. }
  1495. if (variance<minVariance) {
  1496. minVariance = variance;
  1497. splitIndex = i;
  1498. }
  1499. }
  1500. }
  1501. if (splitIndex==-1) break;
  1502. if ( (branching_+clusterCount-1) > clusters_length) break;
  1503. meanVariance = minVariance;
  1504. // split node
  1505. KMeansNodePtr toSplit = clusters[splitIndex];
  1506. clusters[splitIndex] = toSplit->childs[0];
  1507. for (int i=1; i<branching_; ++i) {
  1508. clusters[clusterCount++] = toSplit->childs[i];
  1509. }
  1510. }
  1511. varianceValue = meanVariance/root->size;
  1512. return clusterCount;
  1513. }
  1514. private:
  1515. /** The branching factor used in the hierarchical k-means clustering */
  1516. int branching_;
  1517. /** Number of kmeans trees (default is one) */
  1518. int trees_;
  1519. /** Maximum number of iterations to use when performing k-means clustering */
  1520. int iterations_;
  1521. /** Algorithm for choosing the cluster centers */
  1522. flann_centers_init_t centers_init_;
  1523. /**
  1524. * Cluster border index. This is used in the tree search phase when determining
  1525. * the closest cluster to explore next. A zero value takes into account only
  1526. * the cluster centres, a value greater then zero also take into account the size
  1527. * of the cluster.
  1528. */
  1529. float cb_index_;
  1530. /**
  1531. * The dataset used by this index
  1532. */
  1533. const Matrix<ElementType> dataset_;
  1534. /** Index parameters */
  1535. IndexParams index_params_;
  1536. /**
  1537. * Number of features in the dataset.
  1538. */
  1539. size_t size_;
  1540. /**
  1541. * Length of each feature.
  1542. */
  1543. size_t veclen_;
  1544. /**
  1545. * The root node in the tree.
  1546. */
  1547. KMeansNodePtr* root_;
  1548. /**
  1549. * Array of indices to vectors in the dataset.
  1550. */
  1551. int** indices_;
  1552. /**
  1553. * The distance
  1554. */
  1555. Distance distance_;
  1556. /**
  1557. * Pooled memory allocator.
  1558. */
  1559. PooledAllocator pool_;
  1560. /**
  1561. * Memory occupied by the index.
  1562. */
  1563. int memoryCounter_;
  1564. };
  1565. }
  1566. //! @endcond
  1567. #endif //OPENCV_FLANN_KMEANS_INDEX_H_