31 #ifndef OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
32 #define OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
56 (*this)[
"leaf_max_size"] = leaf_max_size;
57 (*this)[
"reorder"] = reorder;
69 template <
typename Distance>
85 Distance
d = Distance() ) :
86 dataset_(inputData), index_params_(
params), distance_(
d)
88 size_ = dataset_.
rows;
91 if (dim_param>0) dim_ = dim_param;
97 for (
size_t i = 0; i < size_; i++) {
110 if (reorder_)
delete[] data_.
data;
118 computeBoundingBox(root_bbox_);
119 root_node_ = divideTree(0, (
int)size_, root_bbox_ );
124 for (
size_t i=0; i<size_; ++i) {
125 for (
size_t j=0; j<dim_; ++j) {
126 data_[i][j] = dataset_[vind_[i]][j];
152 save_tree(stream, root_node_);
170 load_tree(stream, root_node_);
173 index_params_[
"algorithm"] =
getType();
174 index_params_[
"leaf_max_size"] = leaf_max_size_;
175 index_params_[
"reorder"] = reorder_;
215 assert(indices.
rows >= queries.
rows);
217 assert(
int(indices.
cols) >= knn);
218 assert(
int(dists.
cols) >= knn);
221 for (
size_t i = 0; i < queries.
rows; i++) {
222 resultSet.
init(indices[i], dists[i]);
229 return index_params_;
243 float epsError = 1+
get_param(searchParams,
"eps",0.0
f);
245 std::vector<DistanceType> dists(dim_,0);
246 DistanceType distsq = computeInitialDistances(vec, dists);
247 searchLevel(result, vec, root_node_, distsq, dists, epsError);
271 Node* child1, * child2;
273 typedef Node* NodePtr;
281 typedef std::vector<Interval> BoundingBox;
283 typedef BranchStruct<NodePtr, DistanceType> BranchSt;
284 typedef BranchSt* Branch;
289 void save_tree(FILE* stream, NodePtr tree)
292 if (tree->child1!=NULL) {
293 save_tree(stream, tree->child1);
295 if (tree->child2!=NULL) {
296 save_tree(stream, tree->child2);
301 void load_tree(FILE* stream, NodePtr& tree)
305 if (tree->child1!=NULL) {
306 load_tree(stream, tree->child1);
308 if (tree->child2!=NULL) {
309 load_tree(stream, tree->child2);
314 void computeBoundingBox(BoundingBox& bbox)
317 for (
size_t i=0; i<dim_; ++i) {
321 for (
size_t k=1;
k<dataset_.
rows; ++
k) {
322 for (
size_t i=0; i<dim_; ++i) {
323 if (dataset_[
k][i]<bbox[i].low) bbox[i].low = (
DistanceType)dataset_[
k][i];
324 if (dataset_[
k][i]>bbox[i].high) bbox[i].high = (
DistanceType)dataset_[
k][i];
339 NodePtr divideTree(
int left,
int right, BoundingBox& bbox)
344 if ( (right-left) <= leaf_max_size_) {
345 node->child1 = node->child2 = NULL;
350 for (
size_t i=0; i<dim_; ++i) {
355 for (
size_t i=0; i<dim_; ++i) {
356 if (bbox[i].low>dataset_[vind_[
k]][i]) bbox[i].low=(
DistanceType)dataset_[vind_[
k]][i];
357 if (bbox[i].high<dataset_[vind_[
k]][i]) bbox[i].high=(
DistanceType)dataset_[vind_[
k]][i];
365 middleSplit_(&vind_[0]+left, right-left, idx, cutfeat, cutval, bbox);
367 node->divfeat = cutfeat;
369 BoundingBox left_bbox(bbox);
370 left_bbox[cutfeat].high = cutval;
371 node->child1 = divideTree(left, left+idx, left_bbox);
373 BoundingBox right_bbox(bbox);
374 right_bbox[cutfeat].low = cutval;
375 node->child2 = divideTree(left+idx, right, right_bbox);
377 node->divlow = left_bbox[cutfeat].high;
378 node->divhigh = right_bbox[cutfeat].low;
380 for (
size_t i=0; i<dim_; ++i) {
381 bbox[i].low =
std::min(left_bbox[i].low, right_bbox[i].low);
382 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
391 min_elem = dataset_[ind[0]][dim];
392 max_elem = dataset_[ind[0]][dim];
393 for (
int i=1; i<
count; ++i) {
395 if (val<min_elem) min_elem = val;
396 if (val>max_elem) max_elem = val;
400 void middleSplit(
int* ind,
int count,
int&
index,
int& cutfeat,
DistanceType& cutval,
const BoundingBox& bbox)
405 cutval = (bbox[0].high+bbox[0].low)/2;
406 for (
size_t i=1; i<dim_; ++i) {
411 cutval = (bbox[i].high+bbox[i].low)/2;
417 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
418 cutval = (min_elem+max_elem)/2;
419 max_span = max_elem - min_elem;
423 for (
size_t i=0; i<dim_; ++i) {
427 computeMinMax(ind, count, i, min_elem, max_elem);
428 span = max_elem - min_elem;
432 cutval = (min_elem+max_elem)/2;
437 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
439 if (lim1>count/2) index = lim1;
440 else if (lim2<count/2) index = lim2;
441 else index = count/2;
445 void middleSplit_(
int* ind,
int count,
int& index,
int& cutfeat,
DistanceType& cutval,
const BoundingBox& bbox)
447 const float EPS=0.00001f;
449 for (
size_t i=1; i<dim_; ++i) {
457 for (
size_t i=0; i<dim_; ++i) {
461 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
463 if (spread>max_spread) {
470 DistanceType split_val = (bbox[cutfeat].low+bbox[cutfeat].high)/2;
472 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
474 if (split_val<min_elem) cutval = (
DistanceType)min_elem;
475 else if (split_val>max_elem) cutval = (
DistanceType)max_elem;
476 else cutval = split_val;
479 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
481 if (lim1>count/2) index = lim1;
482 else if (lim2<count/2) index = lim2;
483 else index = count/2;
496 void planeSplit(
int* ind,
int count,
int cutfeat,
DistanceType cutval,
int& lim1,
int& lim2)
502 while (left<=right && dataset_[ind[left]][cutfeat]<cutval) ++left;
503 while (left<=right && dataset_[ind[right]][cutfeat]>=cutval) --
right;
504 if (left>right)
break;
513 while (left<=right && dataset_[ind[left]][cutfeat]<=cutval) ++left;
514 while (left<=right && dataset_[ind[right]][cutfeat]>cutval) --
right;
515 if (left>right)
break;
525 for (
size_t i = 0; i < dim_; ++i) {
526 if (vec[i] < root_bbox_[i].low) {
527 dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].low, (
int)i);
530 if (vec[i] > root_bbox_[i].high) {
531 dists[i] = distance_.accum_dist(vec[i], root_bbox_[i].high, (
int)i);
542 void searchLevel(ResultSet<DistanceType>& result_set,
const ElementType* vec,
const NodePtr node,
DistanceType mindistsq,
543 std::vector<DistanceType>& dists,
const float epsError)
546 if ((node->child1 == NULL)&&(node->child2 == NULL)) {
548 for (
int i=node->left; i<node->right; ++i) {
549 int index = reorder_ ? i : vind_[i];
551 if (dist<worst_dist) {
552 result_set.addPoint(dist,vind_[i]);
559 int idx = node->divfeat;
567 if ((diff1+diff2)<0) {
568 bestChild = node->child1;
569 otherChild = node->child2;
570 cut_dist = distance_.accum_dist(val, node->divhigh, idx);
573 bestChild = node->child2;
574 otherChild = node->child1;
575 cut_dist = distance_.accum_dist( val, node->divlow, idx);
579 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
582 mindistsq = mindistsq + cut_dist -
dst;
583 dists[
idx] = cut_dist;
584 if (mindistsq*epsError<=result_set.worstDist()) {
585 searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError);
595 const Matrix<ElementType> dataset_;
606 std::vector<int> vind_;
608 Matrix<ElementType> data_;
618 BoundingBox root_bbox_;
627 PooledAllocator pool_;
634 #endif //OPENCV_FLANN_KDTREE_SINGLE_INDEX_H_
flann_algorithm_t
Definition: defines.h:81
IndexParams getParameters() const
Definition: kdtree_single_index.h:227
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
size_t cols
Definition: matrix.h:52
CvSize CvPoint2D32f int count
Definition: calib3d.hpp:221
int wastedMemory
Definition: allocator.h:90
KDTreeSingleIndex & operator=(const KDTreeSingleIndex &)
const int * idx
Definition: core_c.h:323
T * allocate(size_t count=1)
Definition: allocator.h:178
GLuint index
Definition: core_c.h:986
int d
Definition: legacy.hpp:3064
KDTreeSingleIndex(const Matrix< ElementType > &inputData, const IndexParams ¶ms=KDTreeSingleIndexParams(), Distance d=Distance())
Definition: kdtree_single_index.h:84
void init(int *indices_, DistanceType *dists_)
Definition: result_set.h:98
KDTreeSingleIndexParams(int leaf_max_size=10, bool reorder=true, int dim=-1)
Definition: kdtree_single_index.h:53
~KDTreeSingleIndex()
Definition: kdtree_single_index.h:108
Distance::ResultType DistanceType
Definition: kdtree_single_index.h:74
const CvArr const CvArr CvArr * result
Definition: core_c.h:805
Definition: kdtree_single_index.h:70
GLuint GLuint GLsizei GLenum const GLvoid * indices
Definition: legacy.hpp:3084
void findNeighbors(ResultSet< DistanceType > &result, const ElementType *vec, const SearchParams &searchParams)
Definition: kdtree_single_index.h:241
CV_EXPORTS_W void min(InputArray src1, InputArray src2, OutputArray dst)
computes per-element minimum of two arrays (dst = min(src1, src2))
Definition: kdtree_single_index.h:51
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
Definition: result_set.h:66
std::map< std::string, any > IndexParams
Definition: params.h:42
CvMat * dst
Definition: calib3d.hpp:76
void saveIndex(FILE *stream)
Saves the index to a stream.
Definition: kdtree_single_index.h:141
GLenum const GLfloat * params
Definition: compat.hpp:688
T * data
Definition: matrix.h:54
Definition: result_set.h:85
Distance::ElementType ElementType
Definition: kdtree_single_index.h:73
size_t veclen() const
Definition: kdtree_single_index.h:189
void knnSearch(const Matrix< ElementType > &queries, Matrix< int > &indices, Matrix< DistanceType > &dists, int knn, const SearchParams ¶ms)
Perform k-nearest neighbor search.
Definition: kdtree_single_index.h:212
int usedMemory() const
Definition: kdtree_single_index.h:198
Definition: nn_index.h:48
size_t rows
Definition: matrix.h:51
GLuint dst
Definition: calib3d.hpp:134
::max::max int
Definition: functional.hpp:324
GLenum GLenum GLvoid GLvoid GLvoid * span
CV_EXPORTS void swap(Mat &a, Mat &b)
swaps two matrices
size_t size() const
Definition: kdtree_single_index.h:181
const CvArr * right
Definition: calib3d.hpp:353
void save_value(FILE *stream, const T &value, size_t count=1)
Definition: saving.h:126
flann_algorithm_t getType() const
Definition: kdtree_single_index.h:135
void loadIndex(FILE *stream)
Loads the index from a stream.
Definition: kdtree_single_index.h:156
CvPoint3D64f double * dist
Definition: legacy.hpp:556
void buildIndex()
Definition: kdtree_single_index.h:116