approximate nearest neighbor search
|
View:
New views
1 Messages
—
Rating Filter:
Alert me
|
 |
approximate nearest neighbor search
by Xavier Delacour
::
Rate this Message:
The attached change implements kd-trees and approximate nearest
neighbor search, allowing for log-linear-time matching of large sets of high-dimensional feature vectors (such as those generated by SIFT, SURF, etc). This is useful for object recognition and structure/motion recovery. The paper J.S. Beis and D.G. Lowe. Shape indexing using approximate nearest-neighbor search in highdimensional spaces. In Proc. IEEE Conf. Comp. Vision Patt. Recog., pages 1000--1006, 1997. http://citeseer.ist.psu.edu/beis97shape.html describes the approach. Usage is as follows: call cvCreateFeatureTree with a matrix of feature vectors, cvFindFeatures to match new features to those in the tree, and cvReleaseFeatureTree to free the tree. Searching for a particular feature takes at most emax * log2(n) for n features in the original set and a small constant emax (10 to 20 gives good results). There's a test for cvFindFeatures in tests/cv/src. Also another function cvFindFeaturesBoxed does orthogonal range searching. Feedback appreciated. I'd like to check this in after adding some docs. Xavier [patch-051308.diff] diff -r 8426aff6c201 -r f1898f721abe cv/include/cv.h --- a/cv/include/cv.h Mon May 12 21:50:11 2008 -0400 +++ b/cv/include/cv.h Tue May 13 19:19:08 2008 -0400 @@ -1050,6 +1050,24 @@ CVAPI(void) cvFitLine( const CvArr* poi CVAPI(void) cvFitLine( const CvArr* points, int dist_type, double param, double reps, double aeps, float* line ); + +/* Constructs kd-tree from set of feature descriptors */ +CvFeatureTree* cvCreateFeatureTree(CvMat* desc); + +/* Release kd-tree */ +void cvReleaseFeatureTree(CvFeatureTree* tr); + +/* Searches kd-tree for k nearest neighbors of given reference points, + searching at most emax leaves. */ +void cvFindFeatures(CvFeatureTree* tr, CvMat* desc, + CvMat* results, CvMat* dist, int k = 2, int emax = 20); + +/* Search kd-tree for all points that are inlier to given rect region. */ +int cvFindFeaturesBoxed(CvFeatureTree* tr, + CvMat* bounds_min, CvMat* bounds_max, + CvMat* results); + + /****************************************************************************************\ * Haar-like Object Detection functions * \****************************************************************************************/ diff -r 8426aff6c201 -r f1898f721abe cv/include/cvtypes.h --- a/cv/include/cvtypes.h Mon May 12 21:50:11 2008 -0400 +++ b/cv/include/cvtypes.h Tue May 13 19:19:08 2008 -0400 @@ -379,6 +379,8 @@ typedef struct CvAvgComp } CvAvgComp; +class CvFeatureTree; + #endif /*_CVTYPES_H_*/ /* End of file. */ diff -r 8426aff6c201 -r f1898f721abe cv/src/Makefile.am --- a/cv/src/Makefile.am Mon May 12 21:50:11 2008 -0400 +++ b/cv/src/Makefile.am Tue May 13 19:19:08 2008 -0400 @@ -5,7 +5,9 @@ EXTRA_DIST = cv.dsp cv.vcproj cv.rc reso INCLUDES = -I. -I$(top_srcdir)/cv/include -I$(top_srcdir)/cxcore/include -I$(top_srcdir) -noinst_HEADERS = _cv.h _cvgeom.h _cvimgproc.h _cvipp.h _cvlist.h _cvmatrix.h +noinst_HEADERS = _cv.h _cvgeom.h _cvimgproc.h _cvipp.h _cvlist.h _cvmatrix.h \ + _cvkdtree.hpp + noinst_LTLIBRARIES = lib_cv.la lib_LTLIBRARIES = libcv.la @@ -24,7 +26,7 @@ lib_cv_la_SOURCES = \ cvpyrsegmentation.cpp cvrotcalipers.cpp cvsamplers.cpp cvsegmentation.cpp cvshapedescr.cpp \ cvsmooth.cpp cvsnakes.cpp cvsubdivision2d.cpp cvsumpixels.cpp \ cvswitcher.cpp cvtables.cpp cvtemplmatch.cpp cvthresh.cpp \ - cvundistort.cpp cvutils.cpp + cvundistort.cpp cvutils.cpp cvkdtree.cpp lib_cv_la_LDFLAGS = -no-undefined @LDFLAGS@ # real library diff -r 8426aff6c201 -r f1898f721abe cv/src/_cvkdtree.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cv/src/_cvkdtree.hpp Tue May 13 19:19:08 2008 -0400 @@ -0,0 +1,458 @@ +/*M/////////////////////////////////////////////////////////////////////////////////////// +// +// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. +// +// By downloading, copying, installing or using the software you agree to this license. +// If you do not agree to this license, do not download, install, +// copy or use the software. +// +// +// Intel License Agreement +// For Open Source Computer Vision Library +// +// Copyright (C) 2008, Xavier Delacour, all rights reserved. +// Third party copyrights are property of their respective owners. +// +// Redistribution and use in source and binary forms, with or without modification, +// are permitted provided that the following conditions are met: +// +// * Redistribution's of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// +// * Redistribution's in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// * The name of Intel Corporation may not be used to endorse or promote products +// derived from this software without specific prior written permission. +// +// This software is provided by the copyright holders and contributors "as is" and +// any express or implied warranties, including, but not limited to, the implied +// warranties of merchantability and fitness for a particular purpose are disclaimed. +// In no event shall the Intel Corporation or contributors be liable for any direct, +// indirect, incidental, special, exemplary, or consequential damages +// (including, but not limited to, procurement of substitute goods or services; +// loss of use, data, or profits; or business interruption) however caused +// and on any theory of liability, whether in contract, strict liability, +// or tort (including negligence or otherwise) arising in any way out of +// the use of this software, even if advised of the possibility of such damage. +// +//M*/ + +// 2008-05-13, Xavier Delacour <xavier.delacour@...> + +#ifndef __cv_kdtree_h__ +#define __cv_kdtree_h__ + +#include "_cv.h" + +#include <vector> +#include <algorithm> +#include <limits> +#include <iostream> +#include "assert.h" +#include "math.h" + +// J.S. Beis and D.G. Lowe. Shape indexing using approximate nearest-neighbor search in highdimensional spaces. In Proc. IEEE Conf. Comp. Vision Patt. Recog., pages 1000--1006, 1997. http://citeseer.ist.psu.edu/beis97shape.html + +template < class __valuetype, class __deref > +class CvKDTree { +public: + typedef __deref deref_type; + typedef typename __deref::scalar_type scalar_type; + typedef typename __deref::accum_type accum_type; + +private: + struct node { + int dim; // split dimension; >=0 for nodes, -1 for leaves + __valuetype value; // if leaf, value of leaf + int left, right; // node indices of left and right branches + scalar_type boundary; // left if deref(value,dim)<=boundary, otherwise right + }; + typedef std::vector < node > node_array; + + __deref deref; // requires operator() (__valuetype lhs,int dim) + + node_array nodes; // node storage + int point_dim; // dimension of points (the k in kd-tree) + int root_node; // index of root node, -1 if empty tree + + // for given set of point indices, compute dimension of highest variance + template < class __instype, class __valuector > + int dimension_of_highest_variance(__instype * first, __instype * last, + __valuector ctor) { + assert(last - first > 0); + + accum_type maxvar = std::numeric_limits < accum_type >::min(); + int maxj = 0; + for (int j = 0; j < point_dim; ++j) { + accum_type mean = 0; + for (__instype * k = first; k < last; ++k) + mean += deref(ctor(*k), j); + mean /= last - first; + accum_type var = 0; + for (__instype * k = first; k < last; ++k) { + accum_type diff = accum_type(deref(ctor(*k), j)) - mean; + var += diff * diff; + } + var /= last - first; + + if (var >= maxvar) { + maxvar = var; + maxj = j; + } + } + + assert(maxj >=0 && maxj < point_dim); + return maxj; + } + + // given point indices and dimension, find index of median; (almost) modifies [first,last) + // such that points_in[first,median]<=point[median], points_in(median,last)>point[median]. + // implemented as partial quicksort; expected linear perf. + template < class __instype, class __valuector > + __instype * median_partition(__instype * first, __instype * last, + int dim, __valuector ctor) { + assert(last - first > 0); + __instype *k = first + (last - first) / 2; + median_partition(first, last, k, dim, ctor); + return k; + } + + template < class __instype, class __valuector > + struct median_pr { + const __instype & pivot; + int dim; + __deref deref; + __valuector ctor; + median_pr(const __instype & _pivot, int _dim, __deref _deref, __valuector _ctor) + : pivot(_pivot), dim(_dim), deref(_deref), ctor(_ctor) { + } + bool operator() (const __instype & lhs) const { + return deref(ctor(lhs), dim) <= deref(ctor(pivot), dim); + } + }; + + template < class __instype, class __valuector > + void median_partition(__instype * first, __instype * last, + __instype * k, int dim, __valuector ctor) { + int pivot = (last - first) / 2; + + std::swap(first[pivot], last[-1]); + __instype *middle = std::partition(first, last - 1, + median_pr < __instype, __valuector > + (last[-1], dim, deref, ctor)); + std::swap(*middle, last[-1]); + + if (middle < k) + median_partition(middle + 1, last, k, dim, ctor); + else if (middle > k) + median_partition(first, middle, k, dim, ctor); + } + + // insert given points into the tree; return created node + template < class __instype, class __valuector > + int insert(__instype * first, __instype * last, __valuector ctor) { + if (first == last) + return -1; + else { + + int dim = dimension_of_highest_variance(first, last, ctor); + __instype *median = median_partition(first, last, dim, ctor); + + __instype *split = median; + for (; split != last && deref(ctor(*split), dim) == + deref(ctor(*median), dim); ++split); + + if (split == last) { // leaf + int nexti = -1; + for (--split; split >= first; --split) { + int i = nodes.size(); + node & n = *nodes.insert(nodes.end(), node()); + n.dim = -1; + n.value = ctor(*split); + n.left = -1; + n.right = nexti; + nexti = i; + } + + return nexti; + } else { // node + int i = nodes.size(); + // note that recursive insert may invalidate this ref + node & n = *nodes.insert(nodes.end(), node()); + + n.dim = dim; + n.boundary = deref(ctor(*median), dim); + + int left = insert(first, split, ctor); + nodes[i].left = left; + int right = insert(split, last, ctor); + nodes[i].right = right; + + return i; + } + } + } + + // run to leaf; linear search for p; + // if found, remove paths to empty leaves on unwind + bool remove(int *i, const __valuetype & p) { + if (*i == -1) + return false; + node & n = nodes[*i]; + bool r; + + if (n.dim >= 0) { // node + if (deref(p, n.dim) <= n.boundary) // left + r = remove(&n.left, p); + else // right + r = remove(&n.right, p); + + // if terminal, remove this node + if (n.left == -1 && n.right == -1) + *i = -1; + + return r; + } else { // leaf + if (n.value == p) { + *i = n.right; + return true; + } else + return remove(&n.right, p); + } + } + +public: + struct identity_ctor { + const __valuetype & operator() (const __valuetype & rhs) const { + return rhs; + } + }; + + // initialize an empty tree + CvKDTree(__deref _deref = __deref()) + : deref(_deref), root_node(-1) { + } + // given points, initialize a balanced tree + CvKDTree(__valuetype * first, __valuetype * last, int _point_dim, + __deref _deref = __deref()) + : deref(_deref) { + set_data(first, last, _point_dim, identity_ctor()); + } + // given points, initialize a balanced tree + template < class __instype, class __valuector > + CvKDTree(__instype * first, __instype * last, int _point_dim, + __valuector ctor, __deref _deref = __deref()) + : deref(_deref) { + set_data(first, last, _point_dim, ctor); + } + + void set_deref(__deref _deref) { + deref = _deref; + } + + void set_data(__valuetype * first, __valuetype * last, int _point_dim) { + set_data(first, last, _point_dim, identity_ctor()); + } + template < class __instype, class __valuector > + void set_data(__instype * first, __instype * last, int _point_dim, + __valuector ctor) { + point_dim = _point_dim; + nodes.clear(); + nodes.reserve(last - first); + root_node = insert(first, last, ctor); + } + + int dims() const { + return point_dim; + } + + // remove the given point + bool remove(const __valuetype & p) { + return remove(&root_node, p); + } + + void print() const { + print(root_node); + } + void print(int i, int indent = 0) const { + if (i == -1) + return; + for (int j = 0; j < indent; ++j) + std::cout << " "; + const node & n = nodes[i]; + if (n.dim >= 0) { + std::cout << "node " << i << ", left " << nodes[i].left << ", right " << + nodes[i].right << ", dim " << nodes[i].dim << ", boundary " << + nodes[i].boundary << std::endl; + print(n.left, indent + 3); + print(n.right, indent + 3); + } else + std::cout << "leaf " << i << ", value = " << nodes[i].value << std::endl; + } + + //////////////////////////////////////////////////////////////////////////////////////// + // bbf search +public: + struct bbf_nn { // info on found neighbors (approx k nearest) + const __valuetype *p; // nearest neighbor + accum_type dist; // distance from d to query point + bbf_nn(const __valuetype & _p, accum_type _dist) + : p(&_p), dist(_dist) { + } + bool operator<(const bbf_nn & rhs) const { + return dist < rhs.dist; + } + }; + typedef std::vector < bbf_nn > bbf_nn_pqueue; +private: + struct bbf_node { // info on branches not taken + int node; // corresponding node + accum_type dist; // minimum distance from bounds to query point + bbf_node(int _node, accum_type _dist) + : node(_node), dist(_dist) { + } + bool operator<(const bbf_node & rhs) const { + return dist > rhs.dist; + } + }; + typedef std::vector < bbf_node > bbf_pqueue; + mutable bbf_pqueue tmp_pq; + + // called for branches not taken, as bbf walks to leaf; + // construct bbf_node given minimum distance to bounds of alternate branch + void pq_alternate(int alt_n, bbf_pqueue & pq, scalar_type dist) const { + if (alt_n == -1) + return; + + // add bbf_node for alternate branch in priority queue + pq.push_back(bbf_node(alt_n, dist)); + push_heap(pq.begin(), pq.end()); + } + + // called by bbf to walk to leaf; + // takes one step down the tree towards query point d + template < class __desctype > + int bbf_branch(int i, const __desctype * d, bbf_pqueue & pq) const { + const node & n = nodes[i]; + // push bbf_node with bounds of alternate branch, then branch + if (d[n.dim] <= n.boundary) { // left + pq_alternate(n.right, pq, n.boundary - d[n.dim]); + return n.left; + } else { // right + pq_alternate(n.left, pq, d[n.dim] - n.boundary); + return n.right; + } + } + + // compute euclidean distance between two points + template < class __desctype > + accum_type distance(const __desctype * d, const __valuetype & p) const { + accum_type dist = 0; + for (int j = 0; j < point_dim; ++j) { + accum_type diff = accum_type(d[j]) - accum_type(deref(p, j)); + dist += diff * diff; + } return (accum_type) sqrt(dist); + } + + // called per candidate nearest neighbor; constructs new bbf_nn for + // candidate and adds it to priority queue of all candidates; if + // queue len exceeds k, drops the point furthest from query point d. + template < class __desctype > + void bbf_new_nn(bbf_nn_pqueue & nn_pq, int k, + const __desctype * d, const __valuetype & p) const { + bbf_nn nn(p, distance(d, p)); + if ((int) nn_pq.size() < k) { + nn_pq.push_back(nn); + push_heap(nn_pq.begin(), nn_pq.end()); + } else if (nn_pq[0].dist > nn.dist) { + pop_heap(nn_pq.begin(), nn_pq.end()); + nn_pq.end()[-1] = nn; + push_heap(nn_pq.begin(), nn_pq.end()); + } + assert(nn_pq.size() < 2 || nn_pq[0].dist >= nn_pq[1].dist); + } + +public: + // finds (with high probability) the k nearest neighbors of d, + // searching at most emax leaves/bins. + // ret_nn_pq is an array containing the (at most) k nearest neighbors + // (see bbf_nn structure def above). + template < class __desctype > + int find_nn_bbf(const __desctype * d, + int k, int emax, + bbf_nn_pqueue & ret_nn_pq) const { + assert(k > 0); + ret_nn_pq.clear(); + + if (root_node == -1) + return 0; + + // add root_node to bbf_node priority queue; + // iterate while queue non-empty and emax>0 + tmp_pq.clear(); + tmp_pq.push_back(bbf_node(root_node, 0)); + while (tmp_pq.size() && emax > 0) { + + // from node nearest query point d, run to leaf + pop_heap(tmp_pq.begin(), tmp_pq.end()); + bbf_node bbf(tmp_pq.end()[-1]); + tmp_pq.erase(tmp_pq.end() - 1); + + int i; + for (i = bbf.node; + i != -1 && nodes[i].dim >= 0; + i = bbf_branch(i, d, tmp_pq)); + + if (i != -1) { + + // add points in leaf/bin to ret_nn_pq + do { + bbf_new_nn(ret_nn_pq, k, d, nodes[i].value); + } while (-1 != (i = nodes[i].right)); + + --emax; + } + } + + tmp_pq.clear(); + return ret_nn_pq.size(); + } + + //////////////////////////////////////////////////////////////////////////////////////// + // orthogonal range search +private: + void find_ortho_range(int i, scalar_type * bounds_min, + scalar_type * bounds_max, + std::vector < __valuetype > &inbounds) const { + if (i == -1) + return; + const node & n = nodes[i]; + if (n.dim >= 0) { // node + if (bounds_min[n.dim] <= n.boundary) + find_ortho_range(n.left, bounds_min, bounds_max, inbounds); + if (bounds_max[n.dim] > n.boundary) + find_ortho_range(n.right, bounds_min, bounds_max, inbounds); + } else { // leaf + do { + inbounds.push_back(nodes[i].value); + } while (-1 != (i = nodes[i].right)); + } + } +public: + // return all points that lie within the given bounds; inbounds is cleared + int find_ortho_range(scalar_type * bounds_min, + scalar_type * bounds_max, + std::vector < __valuetype > &inbounds) const { + inbounds.clear(); + find_ortho_range(root_node, bounds_min, bounds_max, inbounds); + return inbounds.size(); + } +}; + +#endif // __cv_kdtree_h__ + +// Local Variables: +// mode:C++ +// End: diff -r 8426aff6c201 -r f1898f721abe cv/src/cvkdtree.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cv/src/cvkdtree.cpp Tue May 13 19:19:08 2008 -0400 @@ -0,0 +1,279 @@ +/*M/////////////////////////////////////////////////////////////////////////////////////// +// +// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. +// +// By downloading, copying, installing or using the software you agree to this license. +// If you do not agree to this license, do not download, install, +// copy or use the software. +// +// +// Intel License Agreement +// For Open Source Computer Vision Library +// +// Copyright (C) 2008, Xavier Delacour, all rights reserved. +// Third party copyrights are property of their respective owners. +// +// Redistribution and use in source and binary forms, with or without modification, +// are permitted provided that the following conditions are met: +// +// * Redistribution's of source code must retain the above copyright notice, +// this list of conditions and the following disclaimer. +// +// * Redistribution's in binary form must reproduce the above copyright notice, +// this list of conditions and the following disclaimer in the documentation +// and/or other materials provided with the distribution. +// +// * The name of Intel Corporation may not be used to endorse or promote products +// derived from this software without specific prior written permission. +// +// This software is provided by the copyright holders and contributors "as is" and +// any express or implied warranties, including, but not limited to, the implied +// warranties of merchantability and fitness for a particular purpose are disclaimed. +// In no event shall the Intel Corporation or contributors be liable for any direct, +// indirect, incidental, special, exemplary, or consequential damages +// (including, but not limited to, procurement of substitute goods or services; +// loss of use, data, or profits; or business interruption) however caused +// and on any theory of liability, whether in contract, strict liability, +// or tort (including negligence or otherwise) arising in any way out of +// the use of this software, even if advised of the possibility of such damage. +// +//M*/ + +// 2008-05-13, Xavier Delacour <xavier.delacour@...> + +#include "_cvkdtree.hpp" + +// * write up some docs + +// * removing __valuetype parameter from CvKDTree and using virtuals instead +// * of void* data here could simplify things. + +class CvFeatureTree { + + template <class __scalartype, int __cvtype> + struct deref { + typedef __scalartype scalar_type; + typedef double accum_type; + + CvMat* mat; + deref(CvMat* _mat) : mat(_mat) { + assert(CV_ELEM_SIZE1(__cvtype) == sizeof(__scalartype)); + } + scalar_type operator() (int i, int j) const { + return *((scalar_type*)(mat->data.ptr + i * mat->step) + j); + } + }; + +#define dispatch_cvtype(mat, c) \ + switch (CV_MAT_DEPTH((mat)->type)) { \ + case CV_32F: \ + { typedef CvKDTree<int, deref<float, CV_32F> > tree_type; c; break; } \ + case CV_64F: \ + { typedef CvKDTree<int, deref<double, CV_64F> > tree_type; c; break; } \ + default: assert(0); \ + } + + CvMat* mat; + void* data; + + template <class __treetype> + void find_nn(CvMat* d, int k, int emax, CvMat* results, CvMat* dist) { + __treetype* tr = (__treetype*) data; + uchar* dptr = d->data.ptr; + uchar* resultsptr = results->data.ptr; + uchar* distptr = dist->data.ptr; + typename __treetype::bbf_nn_pqueue nn; + + assert(d->cols == tr->dims()); + assert(results->rows == d->rows); + assert(results->rows == dist->rows); + assert(results->cols == k); + assert(dist->cols == k); + + for (int j = 0; j < d->rows; ++j) { + typename __treetype::scalar_type* dj = (typename __treetype::scalar_type*) dptr; + + int* resultsj = (int*) resultsptr; + double* distj = (double*) distptr; + tr->find_nn_bbf(dj, k, emax, nn); + + assert((int)nn.size() <= k); + for (unsigned int j = 0; j < nn.size(); ++j) { + *resultsj++ = *nn[j].p; + *distj++ = nn[j].dist; + } + std::fill(resultsj, resultsj + k - nn.size(), -1); + std::fill(distj, distj + k - nn.size(), 0); + + dptr += d->step; + resultsptr += results->step; + distptr += dist->step; + } + } + + template <class __treetype> + int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max, + CvMat* results) { + int rn = results->rows * results->cols; + std::vector<int> inbounds; + dispatch_cvtype(mat, ((__treetype*)data)-> + find_ortho_range((typename __treetype::scalar_type*)bounds_min->data.ptr, + (typename __treetype::scalar_type*)bounds_max->data.ptr, + inbounds)); + std::copy(inbounds.begin(), + inbounds.begin() + std::min((int)inbounds.size(), rn), + (int*) results->data.ptr); + return inbounds.size(); + } + + CvFeatureTree(const CvFeatureTree& x); + CvFeatureTree& operator= (const CvFeatureTree& rhs); +public: + CvFeatureTree(CvMat* _mat) : mat(_mat) { + // * a flag parameter should tell us whether + // * (a) user ensures *mat outlives *this and is unchanged, + // * (b) we take reference and user ensures mat is unchanged, + // * (c) we copy data, (d) we own and release data. + + std::vector<int> tmp(mat->rows); + for (unsigned int j = 0; j < tmp.size(); ++j) + tmp[j] = j; + + dispatch_cvtype(mat, data = new tree_type + (&tmp[0], &tmp[tmp.size()], mat->cols, + tree_type::deref_type(mat))); + } + ~CvFeatureTree() { + dispatch_cvtype(mat, delete (tree_type*) data); + } + + int dims() { + int d; + dispatch_cvtype(mat, d = ((tree_type*) data)->dims()); + return d; + } + int type() { + return mat->type; + } + + void find_nn(CvMat* d, int k, int emax, CvMat* results, CvMat* dist) { + assert(CV_MAT_TYPE(d->type) == CV_MAT_TYPE(mat->type)); + assert(CV_MAT_TYPE(dist->type) == CV_64FC1); + assert(CV_MAT_TYPE(results->type) == CV_32SC1); + + dispatch_cvtype(mat, find_nn<tree_type> + (d, k, emax, results, dist)); + } + int find_ortho_range(CvMat* bounds_min, CvMat* bounds_max, + CvMat* results) { + assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(mat->type)); + assert(CV_MAT_TYPE(bounds_min->type) == CV_MAT_TYPE(bounds_max->type)); + assert(bounds_min->rows * bounds_min->cols == dims()); + assert(bounds_max->rows * bounds_max->cols == dims()); + + int count = 0; + dispatch_cvtype(mat, count = find_ortho_range<tree_type> + (bounds_min, bounds_max,results)); + return count; + } +}; + + + +CvFeatureTree* cvCreateFeatureTree(CvMat* desc) { + __BEGIN__; + CV_FUNCNAME("cvCreateFeatureTree"); + + if (CV_MAT_TYPE(desc->type) != CV_32FC1 && + CV_MAT_TYPE(desc->type) != CV_64FC1) + CV_ERROR(CV_StsUnsupportedFormat, "descriptors must be either CV_32FC1 or CV_64FC1"); + + return new CvFeatureTree(desc); + __END__; + + return 0; +} + +void cvReleaseFeatureTree(CvFeatureTree* tr) { + delete tr; +} + +// desc is m x d set of candidate points. +// results is m x k set of row of indices of matching points. +// dist is m x k distance to matching points. +void cvFindFeatures(CvFeatureTree* tr, CvMat* desc, + CvMat* results, CvMat* dist, int k, int emax) { + bool free_desc = false; + int dims = tr->dims(); + int type = tr->type(); + + __BEGIN__; + CV_FUNCNAME("cvFindFeatures"); + + if (desc->cols != dims) + CV_ERROR(CV_StsUnmatchedSizes, "desc columns be equal feature dimensions"); + if (results->rows != desc->rows && results->cols != k) + CV_ERROR(CV_StsUnmatchedSizes, "results and desc must be same height"); + if (dist->rows != desc->rows && dist->cols != k) + CV_ERROR(CV_StsUnmatchedSizes, "dist and desc must be same height"); + if (CV_MAT_TYPE(results->type) != CV_32SC1) + CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1"); + if (CV_MAT_TYPE(dist->type) != CV_64FC1) + CV_ERROR(CV_StsUnsupportedFormat, "dist must be CV_64FC1"); + + if (CV_MAT_TYPE(type) != CV_MAT_TYPE(desc->type)) { + CvMat* old_desc = desc; + desc = cvCreateMat(desc->rows, desc->cols, type); + cvConvert(old_desc, desc); + free_desc = true; + } + + tr->find_nn(desc, k, emax, results, dist); + + __END__; + + if (free_desc) + cvReleaseMat(&desc); +} + +int cvFindFeaturesBoxed(CvFeatureTree* tr, + CvMat* bounds_min, CvMat* bounds_max, + CvMat* results) { + int nr = -1; + bool free_bounds = false; + int dims = tr->dims(); + int type = tr->type(); + + __BEGIN__; + CV_FUNCNAME("cvFindFeaturesBoxed"); + + if (bounds_min->cols * bounds_min->rows != dims || + bounds_max->cols * bounds_max->rows != dims) + CV_ERROR(CV_StsUnmatchedSizes, "bounds_{min,max} must 1 x dims or dims x 1"); + if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(bounds_max->type)) + CV_ERROR(CV_StsUnmatchedFormats, "bounds_{min,max} must have same type"); + if (CV_MAT_TYPE(results->type) != CV_32SC1) + CV_ERROR(CV_StsUnsupportedFormat, "results must be CV_32SC1"); + + if (CV_MAT_TYPE(bounds_min->type) != CV_MAT_TYPE(type)) { + free_bounds = true; + + CvMat* old_bounds_min = bounds_min; + bounds_min = cvCreateMat(bounds_min->rows, bounds_min->cols, type); + cvConvert(old_bounds_min, bounds_min); + + CvMat* old_bounds_max = bounds_max; + bounds_max = cvCreateMat(bounds_max->rows, bounds_max->cols, type); + cvConvert(old_bounds_max, bounds_max); + } + + nr = tr->find_ortho_range(bounds_min, bounds_max, results); + + __END__; + if (free_bounds) { + cvReleaseMat(&bounds_min); + cvReleaseMat(&bounds_max); + } + + return nr; +} diff -r 8426aff6c201 -r f1898f721abe tests/cv/src/Makefile.am --- a/tests/cv/src/Makefile.am Mon May 12 21:50:11 2008 -0400 +++ b/tests/cv/src/Makefile.am Tue May 13 19:19:08 2008 -0400 @@ -30,6 +30,7 @@ cvtest_SOURCES = \ amotiontemplates.cpp amotseg.cpp aoptflowhs.cpp \ aoptflowlk.cpp aoptflowpyrlk.cpp aposit.cpp \ apyrsegmentation.cpp asnakes.cpp asubdivisions.cpp \ + akdtree.cpp \ atemplmatch.cpp athresh.cpp cvtest.cpp tsysa.cpp cvtest_LDADD = \ $(top_builddir)/tests/cxts/libcxts.la \ diff -r 8426aff6c201 -r f1898f721abe tests/cv/src/akdtree.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/cv/src/akdtree.cpp Tue May 13 19:19:08 2008 -0400 @@ -0,0 +1,72 @@ +#include "_cxts.h" +#include "cv.h" + +// * add test for cvFindFeaturesBoxed + +#include <algorithm> +#include <vector> +#include <iostream> + +class CV_FeatureTreeTest : public CvTest { +public: + CV_FeatureTreeTest(); + ~CV_FeatureTreeTest(); +protected: + virtual void run( int start_from ); +}; + +CV_FeatureTreeTest::CV_FeatureTreeTest() +: CvTest( "feature-tree", "cvFindFeatures" ) { +} + +CV_FeatureTreeTest::~CV_FeatureTreeTest() { +} + + +void CV_FeatureTreeTest::run( int start_from ) { + + int dims = 64; + int features = 2000; + int k = 1; // * should also test 2nd nn etc.? + int emax = 20; + double noise = .2; + int points = 1000; + + CvRNG rng = cvRNG(); + CvMat* desc = cvCreateMat(features, dims, CV_64FC1); + cvRandArr( &rng, desc, CV_RAND_UNI, cvRealScalar(0), cvRealScalar(1)); + + CvFeatureTree* tr = cvCreateFeatureTree(desc); + CvMat* results = cvCreateMat(points, k, CV_32SC1); + CvMat* dist = cvCreateMat(points, k, CV_64FC1); + + CvMat* pts = cvCreateMat(points, dims, CV_64FC1); + std::vector<int> fmap(points); + for (int j = 0; j < points; ++j) { + int fi = cvRandInt(&rng) % features; + fmap[j] = fi; + double* f = (double*)cvPtr2D(desc, fi, 0); + double* p = (double*)cvPtr2D(pts, j, 0); + for (int k = 0; k < dims; ++ k) + p[k] = f[k] + cvRandReal(&rng) * noise; + } + + cvFindFeatures(tr, pts, results, dist, k, emax); + + int correct_matches = 0; + for (int j = 0; j < points; ++j) { + int fi = (int)cvGetReal2D(results, j, 0); + if (fmap[j] == fi) + ++correct_matches; + } + + double correct_perc = correct_matches / (double)points; + std::cout<<"correct_perc = " << correct_perc << std::endl; + if (correct_perc < .8) + ts->set_failed_test_info(CvTS::FAIL_INVALID_OUTPUT); + + cvReleaseFeatureTree(tr); +} + + +CV_FeatureTreeTest feature_tree_test; diff -r 8426aff6c201 -r f1898f721abe tests/cxts/cxts.cpp --- a/tests/cxts/cxts.cpp Mon May 12 21:50:11 2008 -0400 +++ b/tests/cxts/cxts.cpp Tue May 13 19:19:08 2008 -0400 @@ -1258,7 +1258,7 @@ int CvTS::run( int argc, char** argv ) fs = cvOpenFileStorage( config_name, 0, CV_STORAGE_WRITE ); if( !fs ) { - printf( LOG, "ERROR: could not open config file %s", config_name ); + printf( LOG, "ERROR: could not open config file %s\n", config_name ); return -1; } cvWriteComment( fs, CV_TS_VERSION " config file", 0 ); ------------------------------------------------------------------------- This SF.net email is sponsored by: Microsoft Defy all challenges. Microsoft(R) Visual Studio 2008. http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ _______________________________________________ Opencvlibrary-devel mailing list Opencvlibrary-devel@... https://lists.sourceforge.net/lists/listinfo/opencvlibrary-devel |
| Free Forum Powered by Nabble | Forum Help |