31 #ifndef OPENCV_FLANN_HIERARCHICAL_CLUSTERING_INDEX_H_
32 #define OPENCV_FLANN_HIERARCHICAL_CLUSTERING_INDEX_H_
59 int trees = 4,
int leaf_size = 100)
63 (*this)[
"branching"] = branching;
65 (*this)[
"centers_init"] = centers_init;
67 (*this)[
"trees"] = trees;
69 (*this)[
"leaf_size"] = leaf_size;
80 template <
typename Distance>
95 centersAlgFunction chooseCenters;
109 void chooseCentersRandom(
int k,
int* dsindices,
int indices_length,
int* centers,
int& centers_length)
114 for (index=0; index<
k; ++
index) {
115 bool duplicate =
true;
121 centers_length =
index;
125 centers[
index] = dsindices[rnd];
127 for (
int j=0; j<
index; ++j) {
128 DistanceType sq = distance(dataset[centers[index]], dataset[centers[j]], dataset.
cols);
136 centers_length =
index;
150 void chooseCentersGonzales(
int k,
int* dsindices,
int indices_length,
int* centers,
int& centers_length)
152 int n = indices_length;
155 assert(rnd >=0 && rnd < n);
157 centers[0] = dsindices[rnd];
160 for (index=1; index<
k; ++
index) {
164 for (
int j=0; j<
n; ++j) {
166 for (
int i=1; i<
index; ++i) {
167 DistanceType tmp_dist = distance(dataset[centers[i]],dataset[dsindices[j]],dataset.
cols);
177 if (best_index!=-1) {
178 centers[
index] = dsindices[best_index];
184 centers_length =
index;
201 void chooseCentersKMeanspp(
int k,
int* dsindices,
int indices_length,
int* centers,
int& centers_length)
203 int n = indices_length;
205 double currentPot = 0;
210 assert(index >=0 && index < n);
211 centers[0] = dsindices[
index];
213 for (
int i = 0; i <
n; i++) {
214 closestDistSq[i] = distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.
cols);
215 currentPot += closestDistSq[i];
219 const int numLocalTries = 1;
223 for (centerCount = 1; centerCount <
k; centerCount++) {
226 double bestNewPot = -1;
227 int bestNewIndex = 0;
228 for (
int localTrial = 0; localTrial < numLocalTries; localTrial++) {
233 for (index = 0; index < n-1; index++) {
234 if (randVal <= closestDistSq[index])
break;
235 else randVal -= closestDistSq[
index];
240 for (
int i = 0; i <
n; i++) newPot +=
std::min( distance(dataset[dsindices[i]], dataset[dsindices[index]], dataset.
cols), closestDistSq[i] );
243 if ((bestNewPot < 0)||(newPot < bestNewPot)) {
245 bestNewIndex =
index;
250 centers[centerCount] = dsindices[bestNewIndex];
251 currentPot = bestNewPot;
252 for (
int i = 0; i <
n; i++) closestDistSq[i] =
std::min( distance(dataset[dsindices[i]], dataset[dsindices[bestNewIndex]], dataset.
cols), closestDistSq[i] );
255 centers_length = centerCount;
257 delete[] closestDistSq;
272 Distance
d = Distance())
273 : dataset(inputData),
params(index_params), root(NULL),
indices(NULL), distance(
d)
277 size_ = dataset.
rows;
278 veclen_ = dataset.
cols;
286 chooseCenters = &HierarchicalClusteringIndex::chooseCentersRandom;
289 chooseCenters = &HierarchicalClusteringIndex::chooseCentersGonzales;
292 chooseCenters = &HierarchicalClusteringIndex::chooseCentersKMeanspp;
295 throw FLANNException(
"Unknown algorithm for choosing initial centers.");
299 root =
new NodePtr[trees_];
302 for (
int i=0; i<trees_; ++i) {
336 for(
int i=0; i<trees_; ++i) {
383 for (
int i=0; i<trees_; ++i) {
385 for (
size_t j=0; j<size_; ++j) {
389 computeClustering(root[i],
indices[i], (
int)size_, branching_,0);
407 for (
int i=0; i<trees_; ++i) {
409 save_tree(stream, root[i], i);
434 root =
new NodePtr[trees_];
435 for (
int i=0; i<trees_; ++i) {
438 load_tree(stream, root[i], i);
442 params[
"branching"] = branching_;
444 params[
"centers_init"] = centers_init_;
445 params[
"leaf_size"] = leaf_size_;
461 int maxChecks =
get_param(searchParams,
"checks",32);
466 std::vector<bool> checked(size_,
false);
468 for (
int i=0; i<trees_; ++i) {
469 findNN(root[i], result, vec, checks, maxChecks, heap, checked);
473 while (heap->
popMin(branch) && (checks<maxChecks || !result.
full())) {
475 findNN(node, result, vec, checks, maxChecks, heap, checked);
477 assert(result.
full());
517 typedef Node* NodePtr;
524 typedef BranchStruct<NodePtr, DistanceType> BranchSt;
528 void save_tree(FILE* stream, NodePtr
node,
int num)
531 if (node->childs==NULL) {
532 int indices_offset = (
int)(node->indices -
indices[num]);
536 for(
int i=0; i<branching_; ++i) {
537 save_tree(stream, node->childs[i], num);
543 void load_tree(FILE* stream, NodePtr& node,
int num)
547 if (node->childs==NULL) {
550 node->indices =
indices[num] + indices_offset;
553 node->childs = pool.
allocate<NodePtr>(branching_);
554 for(
int i=0; i<branching_; ++i) {
555 load_tree(stream, node->childs[i], num);
563 void computeLabels(
int* dsindices,
int indices_length,
int* centers,
int centers_length,
int*
labels,
DistanceType&
cost)
566 for (
int i=0; i<indices_length; ++i) {
568 DistanceType dist = distance(point, dataset[centers[0]], veclen_);
570 for (
int j=1; j<centers_length; ++j) {
571 DistanceType new_dist = distance(point, dataset[centers[j]], veclen_);
592 void computeClustering(NodePtr node,
int* dsindices,
int indices_length,
int branching,
int level)
594 node->size = indices_length;
597 if (indices_length < leaf_size_) {
598 node->indices = dsindices;
599 std::sort(node->indices,node->indices+indices_length);
604 std::vector<int> centers(branching);
605 std::vector<int>
labels(indices_length);
608 (this->*chooseCenters)(branching, dsindices, indices_length, ¢ers[0], centers_length);
610 if (centers_length<branching) {
611 node->indices = dsindices;
612 std::sort(node->indices,node->indices+indices_length);
620 computeLabels(dsindices, indices_length, ¢ers[0], centers_length, &labels[0], cost);
622 node->childs = pool.
allocate<NodePtr>(branching);
625 for (
int i=0; i<branching; ++i) {
626 for (
int j=0; j<indices_length; ++j) {
634 node->childs[i] = pool.
allocate<Node>();
635 node->childs[i]->pivot = centers[i];
636 node->childs[i]->indices = NULL;
637 computeClustering(node->childs[i],dsindices+start, end-start, branching, level+1);
657 void findNN(NodePtr node, ResultSet<DistanceType>&
result,
const ElementType* vec,
int& checks,
int maxChecks,
658 Heap<BranchSt>* heap, std::vector<bool>& checked)
660 if (node->childs==NULL) {
661 if (checks>=maxChecks) {
662 if (result.full())
return;
664 for (
int i=0; i<node->size; ++i) {
665 int index = node->indices[i];
666 if (!checked[index]) {
667 DistanceType dist = distance(dataset[index], vec, veclen_);
668 result.addPoint(dist, index);
669 checked[
index] =
true;
677 domain_distances[best_index] = distance(vec, dataset[node->childs[best_index]->pivot], veclen_);
678 for (
int i=1; i<branching_; ++i) {
679 domain_distances[i] = distance(vec, dataset[node->childs[i]->pivot], veclen_);
680 if (domain_distances[i]<domain_distances[best_index]) {
684 for (
int i=0; i<branching_; ++i) {
686 heap->insert(BranchSt(node->childs[i],domain_distances[i]));
689 delete[] domain_distances;
690 findNN(node->childs[best_index],result,vec, checks, maxChecks, heap, checked);
700 const Matrix<ElementType> dataset;
741 PooledAllocator pool;
Definition: hierarchical_clustering_index.h:81
flann_algorithm_t
Definition: defines.h:81
CvFileNode * node
Definition: core_c.h:1638
T get_param(const IndexParams ¶ms, std::string name, const T &default_value)
Definition: params.h:59
int usedMemory
Definition: allocator.h:89
GLint level
Definition: tracking.hpp:88
virtual ~HierarchicalClusteringIndex()
Definition: hierarchical_clustering_index.h:316
HierarchicalClusteringIndexParams(int branching=32, flann_centers_init_t centers_init=FLANN_CENTERS_RANDOM, int trees=4, int leaf_size=100)
Definition: hierarchical_clustering_index.h:57
int usedMemory() const
Definition: hierarchical_clustering_index.h:367
size_t cols
Definition: matrix.h:52
void loadIndex(FILE *stream)
Loads the index from a stream.
Definition: hierarchical_clustering_index.h:415
CV_EXPORTS_W void sort(InputArray src, OutputArray dst, int flags)
sorts independently each matrix row or each matrix column
Definition: defines.h:108
void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams)
Definition: hierarchical_clustering_index.h:458
int wastedMemory
Definition: allocator.h:90
double rand_double(double high=1.0, double low=0)
Definition: random.h:61
virtual bool full() const =0
T * allocate(size_t count=1)
Definition: allocator.h:178
Distance::ResultType DistanceType
Definition: hierarchical_clustering_index.h:85
int d
Definition: legacy.hpp:3064
CvRect r
Definition: core_c.h:1282
size_t size() const
Definition: hierarchical_clustering_index.h:349
void saveIndex(FILE *stream)
Saves the index to a stream.
Definition: hierarchical_clustering_index.h:400
IndexParams getParameters() const
Definition: hierarchical_clustering_index.h:483
T node
Definition: result_set.h:52
double CvStereoLineCoeff CvPoint3D64f * point
Definition: legacy.hpp:558
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
typedef void(CV_CDECL *CvMouseCallback)(int event
Distance::ElementType ElementType
Definition: hierarchical_clustering_index.h:84
double start
Definition: core_c.h:774
IplImage CvMemStorage CvSeq int level
Definition: legacy.hpp:2917
GLuint GLuint GLsizei GLenum const GLvoid * indices
Definition: legacy.hpp:3084
CV_EXPORTS_W void min(InputArray src1, InputArray src2, OutputArray dst)
computes per-element minimum of two arrays (dst = min(src1, src2))
int index
Definition: core_c.h:309
const CvMat CvMat CvMat int k
Definition: legacy.hpp:3052
void load_value(FILE *stream, T &value, size_t count=1)
Definition: saving.h:147
size_t veclen() const
Definition: hierarchical_clustering_index.h:357
flann_centers_init_t
Definition: defines.h:105
HierarchicalClusteringIndex & operator=(const HierarchicalClusteringIndex &)
Definition: result_set.h:66
flann_algorithm_t getType() const
Definition: hierarchical_clustering_index.h:394
std::map< std::string, any > IndexParams
Definition: params.h:42
int next()
Definition: random.h:120
GLenum const GLfloat * params
Definition: compat.hpp:688
HierarchicalClusteringIndex(const Matrix< ElementType > &inputData, const IndexParams &index_params=HierarchicalClusteringIndexParams(), Distance d=Distance())
Definition: hierarchical_clustering_index.h:271
Definition: hierarchical_clustering_index.h:55
void free_elements()
Definition: hierarchical_clustering_index.h:333
Definition: nn_index.h:48
int n
Definition: legacy.hpp:3070
size_t rows
Definition: matrix.h:51
::max::max int
Definition: functional.hpp:324
void buildIndex()
Definition: hierarchical_clustering_index.h:375
double double end
Definition: core_c.h:774
CV_EXPORTS void swap(Mat &a, Mat &b)
swaps two matrices
const CvArr * cost
Definition: calib3d.hpp:359
Definition: defines.h:107
void save_value(FILE *stream, const T &value, size_t count=1)
Definition: saving.h:126
bool popMin(T &value)
Definition: heap.h:147
int rand_int(int high=RAND_MAX, int low=0)
Definition: random.h:72
Definition: defines.h:109
CvPoint3D64f double * dist
Definition: legacy.hpp:556
Definition: result_set.h:50
CvMemStorage CvSeq ** labels
Definition: core_c.h:1083