KDTree.H

Go to the documentation of this file.
00001 /*!@file SIFT/KDTree.H k-d tree implementation */
00002 
00003 // //////////////////////////////////////////////////////////////////// //
00004 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2001 by the //
00005 // University of Southern California (USC) and the iLab at USC.         //
00006 // See http://iLab.usc.edu for information about this project.          //
00007 // //////////////////////////////////////////////////////////////////// //
00008 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00009 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00010 // in Visual Environments, and Applications'' by Christof Koch and      //
00011 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00012 // pending; application number 09/912,225 filed July 23, 2001; see      //
00013 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00014 // //////////////////////////////////////////////////////////////////// //
00015 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00016 //                                                                      //
00017 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00018 // redistribute it and/or modify it under the terms of the GNU General  //
00019 // Public License as published by the Free Software Foundation; either  //
00020 // version 2 of the License, or (at your option) any later version.     //
00021 //                                                                      //
00022 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00023 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00024 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00025 // PURPOSE.  See the GNU General Public License for more details.       //
00026 //                                                                      //
00027 // You should have received a copy of the GNU General Public License    //
00028 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00029 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00030 // Boston, MA 02111-1307 USA.                                           //
00031 // //////////////////////////////////////////////////////////////////// //
00032 //
00033 // Primary maintainer for this file: James Bonaiuto <bonaiuto@usc.edu>
00034 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/SIFT/KDTree.H $
00035 // $Id: KDTree.H 9298 2008-02-21 18:11:04Z rjpeters $
00036 //
00037 #ifndef KDTREE_H_DEFINED
00038 #define KDTREE_H_DEFINED
00039 
00040 #include "SIFT/Keypoint.H"
00041 #include <queue>
00042 
00043 // #######################################################################
00044 //! Represents a rectangle in n-dimensional space
00045 /*! The Hyperrectangle has n dimensions which are assumed to each have
00046   byte type, as in the case in Keypoint. */
00047 class HyperRectangle
00048 {
00049 public:
00050   //! Constructor; the HyperRectangle will be uninitialized
00051   inline HyperRectangle(const uint dim);
00052 
00053   //! Constructor with initial min and max values for all dimensions
00054   inline HyperRectangle(const uint dim, const byte mini, const byte maxi);
00055 
00056   //! Copy constructor
00057   inline HyperRectangle(const HyperRectangle& other);
00058 
00059   //! Creates an all-encompassing rectangle in the dimension specified
00060   inline static HyperRectangle createUniverseRectangle(const uint dim);
00061 
00062   //! Splits the rectangle at the specified dimension and value
00063   inline HyperRectangle splitAt(const uint splitDim, const byte splitVal);
00064 
00065   //! Returns true if the target point is within this HR
00066   inline bool isIn(const rutz::shared_ptr<Keypoint>& target) const;
00067 
00068   //! Return true if any part of this HR is reachable from target
00069   /*! Must be reachable by no more than 'sqdist', false otherwise.  */
00070   inline bool isInReach(const rutz::shared_ptr<Keypoint>& target,
00071                         const int sqdist) const;
00072 
00073   //! Return the dist from nearest point within the HR to the target point.
00074   inline int distSq(const rutz::shared_ptr<Keypoint>& target) const;
00075 
00076 private:
00077   std::vector<byte> itsLeftTop;
00078   std::vector<byte> itsRightBottom;
00079 };
00080 
00081 // ######################################################################
00082 //! A simple KD tree implementation
00083 /*! This class recursively constructs a KD tree from a flat list of
00084   exemplars. Then, it allows for efficient finding of the exemplar in
00085   the tree that is nearest a given target point, of of the set of
00086   exemplars in the tree that are within some distance of a given
00087   target point. */
00088 class KDTree
00089 {
00090 public:
00091   //! Constructor from a flat list of Keypoint objects
00092   /*! Note that it is okay to destroy 'keys' as an internal copy will
00093     be kept. You may want to keep it around, however, and to not
00094     modify it, since the nearest neighbor functions in KDTree return
00095     indices in that original array of keys. Optionally, the array
00096     'objindices' may be passed which contains an object number for
00097     each Keypoint; if it is specified, then second-matches will only
00098     be considered which belong the the same object as the best
00099     match. */
00100   KDTree(const std::vector< rutz::shared_ptr<Keypoint> >& keys,
00101          const std::vector<uint>& objindices = std::vector<uint>());
00102 
00103   //! Destructor
00104   ~KDTree();
00105 
00106   //! Return true if we are empty (no pivot, no subtrees)
00107   inline bool isEmpty() const;
00108 
00109   //! Return true if we are a leaf (valid pivot but no subtrees)
00110   inline bool isLeaf() const;
00111 
00112   //! Find the nearest neighbor to hyperspace point 'target' in kd-tree.
00113   /*! The index of the nearest keypoint in the list passed at
00114     construction is returned. After return 'distsq1' contains the
00115     absolute squared distance between the target point and the
00116     returned nearest neighbor point. 'distsq2' contains the squared
00117     distance between the target point and the second best match found
00118     during the search (the second best match is not returned; distsq2
00119     is useful to check the quality of the best match). */
00120   uint nearestNeighbor(const rutz::shared_ptr<Keypoint>& target,
00121                        int& distsq1, int& distsq2) const;
00122 
00123   //! Limited Best-Bin-First k-d-tree nearest neighbour search.
00124   /*! The index of the nearest keypoint in the list passed at
00125     construction is returned. Find the approximate nearest neighbour
00126     to the hyperspace point 'target' within the kd-tree using
00127     'searchSteps' tail recursions at most (each recursion deciding
00128     about one neighbours' fitness). After return 'distsq1' contains
00129     the absolute squared distance between the target point and the
00130     returned nearest neighbor point. 'distsq2' contains the squared
00131     distance between the target point and the second best match found
00132     during the search (the second best match is not returned; distsq2
00133     is useful to check the quality of the best match). */
00134   uint nearestNeighborBBF(const rutz::shared_ptr<Keypoint>& target,
00135                           const int searchSteps, int& distsq1,
00136                           int& distsq2) const;
00137 
00138 private:
00139   rutz::shared_ptr<Keypoint> itsPivot;      // copy of our splitting Keypoint
00140   uint itsSplitDim;                  // the splitting dimension for subtrees
00141   uint itsPivotIndex;                // index of pivot in c'tor list of keys
00142   uint itsObjIndex;                  // index of object our pivot belongs to
00143   rutz::shared_ptr<KDTree> itsLeftSubTree;  // our left subtree
00144   rutz::shared_ptr<KDTree> itsRightSubTree; // our right subtree
00145 
00146   // a small helper struct for the BBF search:
00147   struct BBFdata {
00148     inline BBFdata(const HyperRectangle& h, const rutz::shared_ptr<KDTree>& t,
00149                    const uint px, const uint pox,
00150                    const rutz::shared_ptr<Keypoint>& p, const int d) :
00151       hr(h), tree(t), pividx(px), pivobji(pox), pivot(p), distsq(d) { }
00152 
00153     HyperRectangle hr;
00154     rutz::shared_ptr<KDTree> tree;
00155     uint pividx;
00156     uint pivobji;
00157     rutz::shared_ptr<Keypoint> pivot;
00158     int distsq;
00159 
00160     // CAUTION! "less priority" means "higher distance" hence, to sort
00161     // our BBF priority queue, operator< is weird!
00162     inline bool operator<(const BBFdata& other) const
00163     { return distsq > other.distsq; }
00164   };
00165 
00166   // used internally by our recursive constructor:
00167   KDTree(const std::vector< rutz::shared_ptr<Keypoint> >& keys,
00168          const std::vector<uint>& indices,
00169          const std::vector<uint>& objindices);
00170 
00171   // Internal recursive algorithm for the kd-tree nearest neighbour search
00172   uint nearestNeighborI(const rutz::shared_ptr<Keypoint>& target,
00173                         const HyperRectangle& hr,
00174                         int maxDistSq, int& distsq1, int& distsq2,
00175                         const int maxdsq, uint& objidx) const;
00176 
00177   // Internal recursive algorithm for BBF kd-tree nearest neighbour search
00178   uint nearestNeighborBBFI(const rutz::shared_ptr<Keypoint>& target,
00179                            const HyperRectangle& hr, int& searchSteps,
00180                            int maxDistSq, int& distsq1, int& distsq2,
00181                            const int maxdsq,
00182                            std::priority_queue<BBFdata>& bbfq,
00183                            uint& objidx) const;
00184 
00185   // find a good candidate for splitting, and splitting dimension
00186   uint goodCandidate(const std::vector< rutz::shared_ptr<Keypoint> >& exset,
00187                      uint& splitDim);
00188 };
00189 
00190 
00191 // #######################################################################
00192 // #######################################################################
00193 // ############# HyperRectangle implementation
00194 // #######################################################################
00195 // #######################################################################
00196 
00197 // #######################################################################
00198 inline HyperRectangle::HyperRectangle(const uint dim) :
00199   itsLeftTop(dim), itsRightBottom(dim)
00200 { }
00201 
00202 // #######################################################################
00203 inline HyperRectangle::HyperRectangle(const uint dim, const byte mini,
00204                                       const byte maxi) :
00205   itsLeftTop(dim, mini), itsRightBottom(dim, maxi)
00206 { }
00207 
00208 // ######################################################################
00209 inline HyperRectangle::HyperRectangle(const HyperRectangle& other) :
00210   itsLeftTop(other.itsLeftTop), itsRightBottom(other.itsRightBottom)
00211 { }
00212 
00213 // #######################################################################
00214 inline HyperRectangle
00215 HyperRectangle::createUniverseRectangle(const uint dim)
00216 { return HyperRectangle(dim, 0, 255); }
00217 
00218 // #######################################################################
00219 inline HyperRectangle
00220 HyperRectangle::splitAt(const uint splitDim, const byte splitVal)
00221 {
00222   HyperRectangle r2(*this);
00223   itsRightBottom[splitDim] = splitVal;
00224   r2.itsLeftTop[splitDim] = splitVal;
00225 
00226   return r2;
00227 }
00228 
00229 // #######################################################################
00230 inline bool HyperRectangle::isIn(const rutz::shared_ptr<Keypoint>& target) const
00231 {
00232   const uint dim = itsLeftTop.size();
00233   //ASSERT(target->getFVlength() == dim);
00234 
00235   for (uint n = 0 ; n < dim ; ++n)
00236     {
00237       const int targD = target->getFVelement(n);
00238       if (targD < itsLeftTop[n] || targD >= itsRightBottom[n]) return false;
00239     }
00240 
00241   return true;
00242 }
00243 
00244 // #######################################################################
00245 inline bool HyperRectangle::isInReach(const rutz::shared_ptr<Keypoint>& target,
00246                                       const int distsq) const
00247 { return (distSq(target) < distsq); }
00248 
00249 // #######################################################################
00250 int HyperRectangle::distSq(const rutz::shared_ptr<Keypoint>& target) const
00251 {
00252   const uint dim = itsLeftTop.size();
00253   //ASSERT(target->getFVlength() == dim);
00254   int distsq = 0;
00255 
00256   for (uint n = 0 ; n < dim ; ++n) {
00257     const int tI = target->getFVelement(n);
00258     const int hrMin = itsLeftTop[n];
00259     const int hrMax = itsRightBottom[n];
00260 
00261     if (tI <= hrMin) { distsq += (tI - hrMin) * (tI - hrMin); }
00262     else if (tI >= hrMax) { distsq += (tI - hrMax) * (tI - hrMax); }
00263   }
00264 
00265   return distsq;
00266 }
00267 
00268 // #######################################################################
00269 // #######################################################################
00270 // ############# KDTree implementation
00271 // #######################################################################
00272 // #######################################################################
00273 
00274 inline bool KDTree::isEmpty() const
00275 { return itsPivot.is_invalid(); }
00276 
00277 // ######################################################################
00278 inline bool KDTree::isLeaf() const
00279 {
00280   return itsPivot.is_valid() &&
00281     itsLeftSubTree.is_invalid() &&
00282     itsRightSubTree.is_invalid();
00283 }
00284 
00285 #endif
00286 
00287 // ######################################################################
00288 /* So things look consistent in everyone's emacs... */
00289 /* Local Variables: */
00290 /* indent-tabs-mode: nil */
00291 /* End: */
Generated on Sun May 8 08:42:16 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3