From 37b1a7560cc132abc0cae800a4b042d543248cb9 Mon Sep 17 00:00:00 2001 From: Dmitriy Anisimov Date: Mon, 18 Aug 2014 22:40:31 +0400 Subject: [PATCH] first version of moving KDTree from core to ml --- modules/core/include/opencv2/core.hpp | 87 ----------------------- modules/features2d/CMakeLists.txt | 2 +- modules/features2d/test/test_nearestneighbors.cpp | 5 +- modules/features2d/test/test_precomp.hpp | 1 + modules/ml/include/opencv2/ml.hpp | 84 ++++++++++++++++++++++ modules/{core => ml}/src/kdtree.cpp | 8 ++- 6 files changed, 94 insertions(+), 93 deletions(-) rename modules/{core => ml}/src/kdtree.cpp (99%) diff --git a/modules/core/include/opencv2/core.hpp b/modules/core/include/opencv2/core.hpp index 6d3d025..a258e8c 100644 --- a/modules/core/include/opencv2/core.hpp +++ b/modules/core/include/opencv2/core.hpp @@ -747,93 +747,6 @@ public: int minusStep, plusStep; }; - - -/*! - Fast Nearest Neighbor Search Class. - - The class implements D. Lowe BBF (Best-Bin-First) algorithm for the last - approximate (or accurate) nearest neighbor search in multi-dimensional spaces. - - First, a set of vectors is passed to KDTree::KDTree() constructor - or KDTree::build() method, where it is reordered. - - Then arbitrary vectors can be passed to KDTree::findNearest() methods, which - find the K nearest neighbors among the vectors from the initial set. - The user can balance between the speed and accuracy of the search by varying Emax - parameter, which is the number of leaves that the algorithm checks. - The larger parameter values yield more accurate results at the expense of lower processing speed. - - \code - KDTree T(points, false); - const int K = 3, Emax = INT_MAX; - int idx[K]; - float dist[K]; - T.findNearest(query_vec, K, Emax, idx, 0, dist); - CV_Assert(dist[0] <= dist[1] && dist[1] <= dist[2]); - \endcode -*/ -class CV_EXPORTS_W KDTree -{ -public: - /*! - The node of the search tree. - */ - struct Node - { - Node() : idx(-1), left(-1), right(-1), boundary(0.f) {} - Node(int _idx, int _left, int _right, float _boundary) - : idx(_idx), left(_left), right(_right), boundary(_boundary) {} - - //! split dimension; >=0 for nodes (dim), < 0 for leaves (index of the point) - int idx; - //! node indices of the left and the right branches - int left, right; - //! go to the left if query_vec[node.idx]<=node.boundary, otherwise go to the right - float boundary; - }; - - //! the default constructor - CV_WRAP KDTree(); - //! the full constructor that builds the search tree - CV_WRAP KDTree(InputArray points, bool copyAndReorderPoints = false); - //! the full constructor that builds the search tree - CV_WRAP KDTree(InputArray points, InputArray _labels, - bool copyAndReorderPoints = false); - //! builds the search tree - CV_WRAP void build(InputArray points, bool copyAndReorderPoints = false); - //! builds the search tree - CV_WRAP void build(InputArray points, InputArray labels, - bool copyAndReorderPoints = false); - //! finds the K nearest neighbors of "vec" while looking at Emax (at most) leaves - CV_WRAP int findNearest(InputArray vec, int K, int Emax, - OutputArray neighborsIdx, - OutputArray neighbors = noArray(), - OutputArray dist = noArray(), - OutputArray labels = noArray()) const; - //! finds all the points from the initial set that belong to the specified box - CV_WRAP void findOrthoRange(InputArray minBounds, - InputArray maxBounds, - OutputArray neighborsIdx, - OutputArray neighbors = noArray(), - OutputArray labels = noArray()) const; - //! returns vectors with the specified indices - CV_WRAP void getPoints(InputArray idx, OutputArray pts, - OutputArray labels = noArray()) const; - //! return a vector with the specified index - const float* getPoint(int ptidx, int* label = 0) const; - //! returns the search space dimensionality - CV_WRAP int dims() const; - - std::vector nodes; //!< all the tree nodes - CV_PROP Mat points; //!< all the points. It can be a reordered copy of the input vector set or the original vector set. - CV_PROP std::vector labels; //!< the parallel array of labels. - CV_PROP int maxDepth; //!< maximum depth of the search tree. Do not modify it - CV_PROP_RW int normType; //!< type of the distance (cv::NORM_L1 or cv::NORM_L2) used for search. Initially set to cv::NORM_L2, but you can modify it -}; - - - /*! Random Number Generator diff --git a/modules/features2d/CMakeLists.txt b/modules/features2d/CMakeLists.txt index 0b080cf..ad6df94 100644 --- a/modules/features2d/CMakeLists.txt +++ b/modules/features2d/CMakeLists.txt @@ -1,2 +1,2 @@ set(the_description "2D Features Framework") -ocv_define_module(features2d opencv_imgproc opencv_flann OPTIONAL opencv_highgui) +ocv_define_module(features2d opencv_imgproc opencv_ml opencv_flann OPTIONAL opencv_highgui) diff --git a/modules/features2d/test/test_nearestneighbors.cpp b/modules/features2d/test/test_nearestneighbors.cpp index 0c2c70b..8dd333c 100644 --- a/modules/features2d/test/test_nearestneighbors.cpp +++ b/modules/features2d/test/test_nearestneighbors.cpp @@ -12,6 +12,7 @@ // // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. // Copyright (C) 2009, Willow Garage Inc., all rights reserved. +// Copyright (C) 2014, Itseez Inc, all rights reserved. // Third party copyrights are property of their respective owners. // // Redistribution and use in source and binary forms, with or without modification, @@ -167,13 +168,13 @@ protected: virtual int findNeighbors( Mat& points, Mat& neighbors ); virtual int checkFindBoxed(); virtual void releaseModel(); - KDTree* tr; + ml::KDTree* tr; }; void CV_KDTreeTest_CPP::createModel( const Mat& data ) { - tr = new KDTree( data, false ); + tr = new ml::KDTree( data, false ); } int CV_KDTreeTest_CPP::checkGetPoins( const Mat& data ) diff --git a/modules/features2d/test/test_precomp.hpp b/modules/features2d/test/test_precomp.hpp index bce72f7..893b29b 100644 --- a/modules/features2d/test/test_precomp.hpp +++ b/modules/features2d/test/test_precomp.hpp @@ -13,6 +13,7 @@ #include "opencv2/imgproc.hpp" #include "opencv2/features2d.hpp" #include "opencv2/imgcodecs.hpp" +#include "opencv2/ml.hpp" #include #endif diff --git a/modules/ml/include/opencv2/ml.hpp b/modules/ml/include/opencv2/ml.hpp index a5ce301..696facb 100644 --- a/modules/ml/include/opencv2/ml.hpp +++ b/modules/ml/include/opencv2/ml.hpp @@ -12,6 +12,7 @@ // // Copyright (C) 2000, Intel Corporation, all rights reserved. // Copyright (C) 2013, OpenCV Foundation, all rights reserved. +// Copyright (C) 2014, Itseez Inc, all rights reserved. // Third party copyrights are property of their respective owners. // // Redistribution and use in source and binary forms, with or without modification, @@ -566,6 +567,89 @@ public: static Ptr create(const Params& params=Params()); }; +/*! + Fast Nearest Neighbor Search Class. + + The class implements D. Lowe BBF (Best-Bin-First) algorithm for the last + approximate (or accurate) nearest neighbor search in multi-dimensional spaces. + + First, a set of vectors is passed to KDTree::KDTree() constructor + or KDTree::build() method, where it is reordered. + + Then arbitrary vectors can be passed to KDTree::findNearest() methods, which + find the K nearest neighbors among the vectors from the initial set. + The user can balance between the speed and accuracy of the search by varying Emax + parameter, which is the number of leaves that the algorithm checks. + The larger parameter values yield more accurate results at the expense of lower processing speed. + + \code + KDTree T(points, false); + const int K = 3, Emax = INT_MAX; + int idx[K]; + float dist[K]; + T.findNearest(query_vec, K, Emax, idx, 0, dist); + CV_Assert(dist[0] <= dist[1] && dist[1] <= dist[2]); + \endcode +*/ +class CV_EXPORTS_W KDTree +{ +public: + /*! + The node of the search tree. + */ + struct Node + { + Node() : idx(-1), left(-1), right(-1), boundary(0.f) {} + Node(int _idx, int _left, int _right, float _boundary) + : idx(_idx), left(_left), right(_right), boundary(_boundary) {} + + //! split dimension; >=0 for nodes (dim), < 0 for leaves (index of the point) + int idx; + //! node indices of the left and the right branches + int left, right; + //! go to the left if query_vec[node.idx]<=node.boundary, otherwise go to the right + float boundary; + }; + + //! the default constructor + CV_WRAP KDTree(); + //! the full constructor that builds the search tree + CV_WRAP KDTree(InputArray points, bool copyAndReorderPoints = false); + //! the full constructor that builds the search tree + CV_WRAP KDTree(InputArray points, InputArray _labels, + bool copyAndReorderPoints = false); + //! builds the search tree + CV_WRAP void build(InputArray points, bool copyAndReorderPoints = false); + //! builds the search tree + CV_WRAP void build(InputArray points, InputArray labels, + bool copyAndReorderPoints = false); + //! finds the K nearest neighbors of "vec" while looking at Emax (at most) leaves + CV_WRAP int findNearest(InputArray vec, int K, int Emax, + OutputArray neighborsIdx, + OutputArray neighbors = noArray(), + OutputArray dist = noArray(), + OutputArray labels = noArray()) const; + //! finds all the points from the initial set that belong to the specified box + CV_WRAP void findOrthoRange(InputArray minBounds, + InputArray maxBounds, + OutputArray neighborsIdx, + OutputArray neighbors = noArray(), + OutputArray labels = noArray()) const; + //! returns vectors with the specified indices + CV_WRAP void getPoints(InputArray idx, OutputArray pts, + OutputArray labels = noArray()) const; + //! return a vector with the specified index + const float* getPoint(int ptidx, int* label = 0) const; + //! returns the search space dimensionality + CV_WRAP int dims() const; + + std::vector nodes; //!< all the tree nodes + CV_PROP Mat points; //!< all the points. It can be a reordered copy of the input vector set or the original vector set. + CV_PROP std::vector labels; //!< the parallel array of labels. + CV_PROP int maxDepth; //!< maximum depth of the search tree. Do not modify it + CV_PROP_RW int normType; //!< type of the distance (cv::NORM_L1 or cv::NORM_L2) used for search. Initially set to cv::NORM_L2, but you can modify it +}; + /****************************************************************************************\ * Auxilary functions declarations * \****************************************************************************************/ diff --git a/modules/core/src/kdtree.cpp b/modules/ml/src/kdtree.cpp similarity index 99% rename from modules/core/src/kdtree.cpp rename to modules/ml/src/kdtree.cpp index fc5338d..f37d910 100644 --- a/modules/core/src/kdtree.cpp +++ b/modules/ml/src/kdtree.cpp @@ -13,6 +13,7 @@ // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. // Copyright (C) 2009, Willow Garage Inc., all rights reserved. // Copyright (C) 2013, OpenCV Foundation, all rights reserved. +// Copyright (C) 2014, Itseez Inc, all rights reserved. // Third party copyrights are property of their respective owners. // // Redistribution and use in source and binary forms, with or without modification, @@ -45,10 +46,10 @@ namespace cv { - +namespace ml +{ // This is reimplementation of kd-trees from cvkdtree*.* by Xavier Delacour, cleaned-up and -// adopted to work with the new OpenCV data structures. It's in cxcore to be shared by -// both cv (CvFeatureTree) and ml (kNN). +// adopted to work with the new OpenCV data structures. // The algorithm is taken from: // J.S. Beis and D.G. Lowe. Shape indexing using approximate nearest-neighbor search @@ -529,3 +530,4 @@ int KDTree::dims() const } } +} -- 2.7.4