31 #ifndef OPENCV_FLANN_KDTREE_INDEX_H_
32 #define OPENCV_FLANN_KDTREE_INDEX_H_
58 (*this)[
"trees"] = trees;
69 template <
typename Distance>
85 Distance
d = Distance() ) :
86 dataset_(inputData), index_params_(
params), distance_(
d)
88 size_ = dataset_.
rows;
89 veclen_ = dataset_.
cols;
91 trees_ =
get_param(index_params_,
"trees",4);
92 tree_roots_ =
new NodePtr[trees_];
96 for (
size_t i = 0; i < size_; ++i) {
113 if (tree_roots_!=NULL) {
114 delete[] tree_roots_;
126 for (
int i = 0; i < trees_; i++) {
128 std::random_shuffle(vind_.begin(), vind_.end());
129 tree_roots_[i] = divideTree(&vind_[0],
int(size_) );
143 for (
int i=0; i<trees_; ++i) {
144 save_tree(stream, tree_roots_[i]);
153 if (tree_roots_!=NULL) {
154 delete[] tree_roots_;
156 tree_roots_ =
new NodePtr[trees_];
157 for (
int i=0; i<trees_; ++i) {
158 load_tree(stream,tree_roots_[i]);
161 index_params_[
"algorithm"] =
getType();
162 index_params_[
"trees"] = tree_roots_;
201 int maxChecks =
get_param(searchParams,
"checks", 32);
202 float epsError = 1+
get_param(searchParams,
"eps",0.0
f);
205 getExactNeighbors(result, vec, epsError);
208 getNeighbors(result, vec, maxChecks, epsError);
214 return index_params_;
234 Node* child1, * child2;
236 typedef Node* NodePtr;
237 typedef BranchStruct<NodePtr, DistanceType> BranchSt;
238 typedef BranchSt* Branch;
242 void save_tree(FILE* stream, NodePtr tree)
245 if (tree->child1!=NULL) {
246 save_tree(stream, tree->child1);
248 if (tree->child2!=NULL) {
249 save_tree(stream, tree->child2);
254 void load_tree(FILE* stream, NodePtr& tree)
258 if (tree->child1!=NULL) {
259 load_tree(stream, tree->child1);
261 if (tree->child2!=NULL) {
262 load_tree(stream, tree->child2);
276 NodePtr divideTree(
int* ind,
int count)
282 node->child1 = node->child2 = NULL;
283 node->divfeat = *ind;
289 meanSplit(ind, count, idx, cutfeat, cutval);
291 node->divfeat = cutfeat;
292 node->divval = cutval;
293 node->child1 = divideTree(ind, idx);
294 node->child2 = divideTree(ind+idx, count-idx);
306 void meanSplit(
int* ind,
int count,
int&
index,
int& cutfeat,
DistanceType& cutval)
314 int cnt =
std::min((
int)SAMPLE_MEAN+1, count);
315 for (
int j = 0; j < cnt; ++j) {
317 for (
size_t k=0;
k<veclen_; ++
k) {
321 for (
size_t k=0;
k<veclen_; ++
k) {
326 for (
int j = 0; j < cnt; ++j) {
328 for (
size_t k=0;
k<veclen_; ++
k) {
330 var_[
k] += dist *
dist;
334 cutfeat = selectDivision(var_);
335 cutval = mean_[cutfeat];
338 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
340 if (lim1>count/2) index = lim1;
341 else if (lim2<count/2) index = lim2;
342 else index = count/2;
347 if ((lim1==count)||(lim2==0)) index = count/2;
358 size_t topind[RAND_DIM];
361 for (
size_t i = 0; i < veclen_; ++i) {
362 if ((num < RAND_DIM)||(v[i] > v[topind[num-1]])) {
364 if (num < RAND_DIM) {
372 while (j > 0 && v[topind[j]] > v[topind[j-1]]) {
380 return (
int)topind[rnd];
393 void planeSplit(
int* ind,
int count,
int cutfeat,
DistanceType cutval,
int& lim1,
int& lim2)
399 while (left<=right && dataset_[ind[left]][cutfeat]<cutval) ++left;
400 while (left<=right && dataset_[ind[right]][cutfeat]>=cutval) --
right;
401 if (left>right)
break;
407 while (left<=right && dataset_[ind[left]][cutfeat]<=cutval) ++left;
408 while (left<=right && dataset_[ind[right]][cutfeat]>cutval) --
right;
409 if (left>right)
break;
419 void getExactNeighbors(ResultSet<DistanceType>&
result,
const ElementType* vec,
float epsError)
424 fprintf(stderr,
"It doesn't make any sense to use more than one tree for exact search");
427 searchLevelExact(result, vec, tree_roots_[0], 0.0, epsError);
429 assert(result.full());
437 void getNeighbors(ResultSet<DistanceType>& result,
const ElementType* vec,
int maxCheck,
float epsError)
443 Heap<BranchSt>* heap =
new Heap<BranchSt>((
int)size_);
447 for (i = 0; i < trees_; ++i) {
448 searchLevel(result, vec, tree_roots_[i], 0, checkCount, maxCheck, epsError, heap, checked);
452 while ( heap->popMin(branch) && (checkCount < maxCheck || !result.full() )) {
453 searchLevel(result, vec, branch.node, branch.mindist, checkCount, maxCheck, epsError, heap, checked);
458 assert(result.full());
467 void searchLevel(ResultSet<DistanceType>& result_set,
const ElementType* vec, NodePtr node,
DistanceType mindist,
int& checkCount,
int maxCheck,
468 float epsError, Heap<BranchSt>* heap,
DynamicBitset& checked)
470 if (result_set.worstDist()<mindist) {
476 if ((node->child1 == NULL)&&(node->child2 == NULL)) {
481 int index = node->divfeat;
482 if ( checked.test(index) || ((checkCount>=maxCheck)&& result_set.full()) )
return;
487 result_set.addPoint(dist,index);
495 NodePtr bestChild = (diff < 0) ? node->child1 : node->child2;
496 NodePtr otherChild = (diff < 0) ? node->child2 : node->child1;
506 DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat);
508 if ((new_distsq*epsError < result_set.worstDist())|| !result_set.full()) {
509 heap->insert( BranchSt(otherChild, new_distsq) );
513 searchLevel(result_set, vec, bestChild, mindist, checkCount, maxCheck, epsError, heap, checked);
519 void searchLevelExact(ResultSet<DistanceType>& result_set,
const ElementType* vec,
const NodePtr node,
DistanceType mindist,
const float epsError)
522 if ((node->child1 == NULL)&&(node->child2 == NULL)) {
523 int index = node->divfeat;
524 DistanceType dist = distance_(dataset_[index], vec, veclen_);
525 result_set.addPoint(dist,index);
532 NodePtr bestChild = (diff < 0) ? node->child1 : node->child2;
533 NodePtr otherChild = (diff < 0) ? node->child2 : node->child1;
543 DistanceType new_distsq = mindist + distance_.accum_dist(val, node->divval, node->divfeat);
546 searchLevelExact(result_set, vec, bestChild, mindist, epsError);
548 if (new_distsq*epsError<=result_set.worstDist()) {
549 searchLevelExact(result_set, vec, otherChild, new_distsq, epsError);
583 std::vector<int> vind_;
588 const Matrix<ElementType> dataset_;
603 NodePtr* tree_roots_;
612 PooledAllocator pool_;
621 #endif //OPENCV_FLANN_KDTREE_INDEX_H_
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
Distance::ResultType DistanceType
Definition: kdtree_index.h:74
void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams)
Definition: kdtree_index.h:199
size_t cols
Definition: matrix.h:52
KDTreeIndex & operator=(const KDTreeIndex &)
int wastedMemory
Definition: allocator.h:90
const int * idx
Definition: core_c.h:323
T * allocate(size_t count=1)
Definition: allocator.h:178
int usedMemory() const
Definition: kdtree_index.h:185
GLuint index
Definition: core_c.h:986
int d
Definition: legacy.hpp:3064
KDTreeIndex(const Matrix< ElementType > &inputData, const IndexParams ¶ms=KDTreeIndexParams(), Distance d=Distance())
Definition: kdtree_index.h:84
size_t size() const
Definition: kdtree_index.h:168
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
KDTreeIndexParams(int trees=4)
Definition: kdtree_index.h:55
boost::dynamic_bitset DynamicBitset
Definition: dynamic_bitset.h:44
void buildIndex()
Definition: kdtree_index.h:123
size_t veclen() const
Definition: kdtree_index.h:176
CV_EXPORTS_W void min(InputArray src1, InputArray src2, OutputArray dst)
computes per-element minimum of two arrays (dst = min(src1, src2))
const CvMat CvMat CvMat int k
Definition: legacy.hpp:3052
GLuint GLuint GLsizei count
Definition: core_c.h:973
void load_value(FILE *stream, T &value, size_t count=1)
Definition: saving.h:147
flann_algorithm_t getType() const
Definition: kdtree_index.h:134
Definition: result_set.h:66
std::map< std::string, any > IndexParams
Definition: params.h:42
~KDTreeIndex()
Definition: kdtree_index.h:111
void loadIndex(FILE *stream)
Loads the index from a stream.
Definition: kdtree_index.h:150
GLenum const GLfloat * params
Definition: compat.hpp:688
Distance::ElementType ElementType
Definition: kdtree_index.h:73
IndexParams getParameters() const
Definition: kdtree_index.h:212
Definition: defines.h:170
Definition: kdtree_index.h:70
Definition: nn_index.h:48
size_t rows
Definition: matrix.h:51
void saveIndex(FILE *stream)
Saves the index to a stream.
Definition: kdtree_index.h:140
::max::max int
Definition: functional.hpp:324
Definition: kdtree_index.h:53
CV_EXPORTS void swap(Mat &a, Mat &b)
swaps two matrices
const CvArr * right
Definition: calib3d.hpp:353
void save_value(FILE *stream, const T &value, size_t count=1)
Definition: saving.h:126
int rand_int(int high=RAND_MAX, int low=0)
Definition: random.h:72
CvPoint3D64f double * dist
Definition: legacy.hpp:556