Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

Review/Statistics/itkKdTree.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkKdTree.h,v $
00005   Language:  C++
00006   Date:      $Date: 2010-02-04 20:21:48 $
00007   Version:   $Revision: 1.2 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00017 #ifndef __itkKdTree_h
00018 #define __itkKdTree_h
00019 
00020 #include <queue>
00021 #include <vector>
00022 
00023 #include "itkMacro.h"
00024 #include "itkPoint.h"
00025 #include "itkSize.h"
00026 #include "itkObject.h"
00027 #include "itkNumericTraits.h"
00028 #include "itkArray.h"
00029 
00030 #include "itkSample.h"
00031 #include "itkSubsample.h"
00032 
00033 #include "itkEuclideanDistanceMetric.h"
00034 
00035 namespace itk {
00036 namespace Statistics  {
00037 
00062 template< class TSample >
00063 struct KdTreeNode
00064 {
00066   typedef KdTreeNode< TSample> Self;
00067 
00069   typedef typename TSample::MeasurementType MeasurementType;
00070 
00072   typedef Array< double > CentroidType;
00073 
00076   typedef typename TSample::InstanceIdentifier InstanceIdentifier;
00077 
00080   virtual bool IsTerminal() const = 0;
00081 
00087   virtual void GetParameters(unsigned int &partitionDimension,
00088                              MeasurementType &partitionValue) const = 0;
00089 
00091   virtual       Self* Left()       = 0;
00092   virtual const Self* Left() const = 0;
00094 
00096   virtual       Self* Right()       = 0;
00097   virtual const Self* Right() const = 0;
00099 
00102   virtual unsigned int Size() const = 0;
00103 
00105   virtual void GetWeightedCentroid(CentroidType &centroid) = 0;
00106 
00108   virtual void GetCentroid(CentroidType &centroid) = 0;
00109 
00111   virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0;
00112 
00114   virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0;
00115 
00117   virtual ~KdTreeNode() {}; // needed to subclasses will actually be deleted
00118 }; // end of class
00119 
00131 template< class TSample >
00132 struct KdTreeNonterminalNode: public KdTreeNode< TSample >
00133 {
00134   typedef KdTreeNode< TSample >                       Superclass;
00135   typedef typename Superclass::MeasurementType        MeasurementType;
00136   typedef typename Superclass::CentroidType           CentroidType;
00137   typedef typename Superclass::InstanceIdentifier     InstanceIdentifier;
00138 
00139   KdTreeNonterminalNode(unsigned int partitionDimension,
00140                         MeasurementType partitionValue,
00141                         Superclass* left,
00142                         Superclass* right);
00143 
00144   virtual ~KdTreeNonterminalNode() {}
00145 
00146   virtual bool IsTerminal() const
00147     { 
00148     return false;
00149     }
00150 
00151   void GetParameters(unsigned int &partitionDimension,
00152                      MeasurementType &partitionValue) const;
00153 
00154   Superclass* Left()
00155     { 
00156     return m_Left;
00157     }
00158 
00159   Superclass* Right()
00160     {
00161     return m_Right;
00162     }
00163 
00164   const Superclass* Left() const
00165     {
00166     return m_Left;
00167     }
00168 
00169   const Superclass* Right() const
00170     {
00171     return m_Right; 
00172     }
00173 
00174   unsigned int Size() const
00175     { 
00176     return 0;
00177     }
00178 
00179   void GetWeightedCentroid( CentroidType & ) 
00180     { 
00181     /* do nothing */
00182     }
00183 
00184   void GetCentroid( CentroidType & ) 
00185     { 
00186     /* do nothing */
00187     }
00188 
00189   // Returns the identifier of the only MeasurementVector associated with 
00190   // this node in the tree. This MeasurementVector will be used later during
00191   // the distance computation when querying the tree.
00192   InstanceIdentifier GetInstanceIdentifier(size_t) const
00193   { return this->m_InstanceIdentifier; }
00194 
00195   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00196   { this->m_InstanceIdentifier = valueId; }
00197 
00198 private:
00199   unsigned int          m_PartitionDimension;
00200   MeasurementType       m_PartitionValue;
00201   InstanceIdentifier    m_InstanceIdentifier;
00202   Superclass* m_Left;
00203   Superclass* m_Right;
00204 }; // end of class
00205 
00220 template< class TSample >
00221 struct KdTreeWeightedCentroidNonterminalNode: public KdTreeNode< TSample >
00222 {
00223   typedef KdTreeNode< TSample >                           Superclass;
00224   typedef typename Superclass::MeasurementType            MeasurementType;
00225   typedef typename Superclass::CentroidType               CentroidType;
00226   typedef typename Superclass::InstanceIdentifier         InstanceIdentifier;
00227   typedef typename TSample::MeasurementVectorSizeType     MeasurementVectorSizeType;
00228 
00229   KdTreeWeightedCentroidNonterminalNode(unsigned int partitionDimension,
00230                                          MeasurementType partitionValue,
00231                                          Superclass* left,
00232                                          Superclass* right,
00233                                          CentroidType &centroid,
00234                                          unsigned int size);
00235   virtual ~KdTreeWeightedCentroidNonterminalNode() {}
00236 
00237   virtual bool IsTerminal() const
00238     {
00239     return false;
00240     }
00241 
00242   void GetParameters(unsigned int &partitionDimension,
00243                      MeasurementType &partitionValue) const;
00244 
00246   MeasurementVectorSizeType GetMeasurementVectorSize() const
00247     {
00248     return m_MeasurementVectorSize;
00249     }
00250 
00251   Superclass* Left()
00252     {
00253     return m_Left;
00254     }
00255 
00256   Superclass* Right()
00257     {
00258     return m_Right;
00259     }
00260 
00261 
00262   const Superclass* Left() const
00263     {
00264     return m_Left;
00265     }
00266 
00267   const Superclass* Right() const
00268     {
00269     return m_Right;
00270     }
00271 
00272   unsigned int Size() const
00273     {
00274     return m_Size;
00275     }
00276 
00277   void GetWeightedCentroid(CentroidType &centroid)
00278     {
00279     centroid = m_WeightedCentroid;
00280     }
00281 
00282   void GetCentroid(CentroidType &centroid)
00283     {
00284     centroid = m_Centroid;
00285     }
00286 
00287   InstanceIdentifier GetInstanceIdentifier(size_t) const
00288     {
00289     return this->m_InstanceIdentifier;
00290     }
00291 
00292   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00293     {
00294     this->m_InstanceIdentifier = valueId;
00295     }
00296 
00297 private:
00298   MeasurementVectorSizeType   m_MeasurementVectorSize;
00299   unsigned int                m_PartitionDimension;
00300   MeasurementType             m_PartitionValue;
00301   CentroidType                m_WeightedCentroid;
00302   CentroidType                m_Centroid;
00303   InstanceIdentifier          m_InstanceIdentifier;
00304   unsigned int                m_Size;
00305   Superclass*                 m_Left;
00306   Superclass*                 m_Right;
00307 }; // end of class
00308 
00309 
00321 template< class TSample >
00322 struct KdTreeTerminalNode: public KdTreeNode< TSample >
00323 {
00324   typedef KdTreeNode< TSample >                   Superclass;
00325   typedef typename Superclass::MeasurementType    MeasurementType;
00326   typedef typename Superclass::CentroidType       CentroidType;
00327   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00328 
00329   KdTreeTerminalNode() {}
00330 
00331   virtual ~KdTreeTerminalNode()
00332     { 
00333     this->m_InstanceIdentifiers.clear();
00334     }
00335 
00336   bool IsTerminal() const
00337     {
00338     return true;
00339     }
00340 
00341   void GetParameters(unsigned int &,
00342                      MeasurementType &) const {}
00343 
00344   Superclass* Left()
00345     {
00346     return 0;
00347     }
00348 
00349   Superclass* Right()
00350     {
00351     return 0;
00352     }
00353 
00354   const Superclass* Left() const
00355     {
00356     return 0;
00357     }
00358 
00359   const Superclass* Right() const
00360     {
00361     return 0;
00362     }
00363 
00364   unsigned int Size() const
00365     {
00366     return static_cast<unsigned int>( m_InstanceIdentifiers.size() );
00367     }
00368 
00369   void GetWeightedCentroid(CentroidType &)
00370     { 
00371     /* do nothing */ 
00372     }
00373 
00374   void GetCentroid(CentroidType &)
00375     {
00376     /* do nothing */ 
00377     }
00378 
00379   InstanceIdentifier GetInstanceIdentifier(size_t index) const
00380     { 
00381     return m_InstanceIdentifiers[index];
00382     }
00383 
00384   void AddInstanceIdentifier(InstanceIdentifier id)
00385     {
00386     m_InstanceIdentifiers.push_back(id);
00387     }
00388 
00389 private:
00390   std::vector< InstanceIdentifier > m_InstanceIdentifiers;
00391 }; // end of class
00392 
00425 template < class TSample >
00426 class ITK_EXPORT KdTree : public Object
00427 {
00428 public:
00430   typedef KdTree                                    Self;
00431   typedef Object                                    Superclass;
00432   typedef SmartPointer<Self>                        Pointer;
00433   typedef SmartPointer<const Self>                  ConstPointer;
00434 
00436   itkTypeMacro(KdTree, Object);
00437 
00439   itkNewMacro(Self);
00440 
00442   typedef TSample                                     SampleType;
00443   typedef typename TSample::MeasurementVectorType     MeasurementVectorType;
00444   typedef typename TSample::MeasurementType           MeasurementType;
00445   typedef typename TSample::InstanceIdentifier        InstanceIdentifier;
00446   typedef typename TSample::AbsoluteFrequencyType     AbsoluteFrequencyType;
00447 
00448   typedef unsigned int                    MeasurementVectorSizeType;
00449 
00452   itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
00453 
00455   typedef EuclideanDistanceMetric< MeasurementVectorType > DistanceMetricType;
00456 
00458   typedef KdTreeNode< TSample > KdTreeNodeType;
00459 
00463   typedef std::pair< InstanceIdentifier, double > NeighborType;
00464 
00465   typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
00466 
00476   class NearestNeighbors {
00477   public:
00479     NearestNeighbors() {}
00480 
00482     ~NearestNeighbors() {}
00483 
00486     void resize(unsigned int k)
00487       {
00488       m_Identifiers.clear();
00489       m_Identifiers.resize(k, NumericTraits< unsigned long >::max());
00490       m_Distances.clear();
00491       m_Distances.resize(k, NumericTraits< double >::max());
00492       m_FarthestNeighborIndex = 0;
00493       }
00495 
00497     double GetLargestDistance()
00498       {
00499       return m_Distances[m_FarthestNeighborIndex];
00500       }
00501 
00504     void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
00505       {
00506       m_Identifiers[m_FarthestNeighborIndex] = id;
00507       m_Distances[m_FarthestNeighborIndex] = distance;
00508       double farthestDistance = NumericTraits< double >::min();
00509       const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
00510       for ( unsigned int i = 0; i < size; i++ )
00511         {
00512         if ( m_Distances[i] > farthestDistance )
00513           {
00514           farthestDistance = m_Distances[i];
00515           m_FarthestNeighborIndex = i;
00516           }
00517         }
00518       }
00520 
00522     const InstanceIdentifierVectorType & GetNeighbors() const
00523       {
00524       return m_Identifiers;
00525       }
00526 
00529     InstanceIdentifier GetNeighbor(unsigned int index) const
00530       {
00531       return m_Identifiers[index];
00532       }
00533 
00535     const std::vector< double >& GetDistances() const
00536       { 
00537       return m_Distances;
00538       }
00539 
00540   private:
00542     unsigned int m_FarthestNeighborIndex;
00543 
00545     InstanceIdentifierVectorType m_Identifiers;
00546 
00549     std::vector< double > m_Distances;
00550   };
00551 
00554   void SetBucketSize(unsigned int size);
00555 
00558   void SetSample(const TSample* sample);
00559 
00561   const TSample* GetSample() const
00562     {
00563     return m_Sample;
00564     }
00565 
00566   unsigned long Size() const
00567     {
00568     return m_Sample->Size();
00569     }
00570 
00575   KdTreeNodeType* GetEmptyTerminalNode()
00576     {
00577     return m_EmptyTerminalNode;
00578     }
00579 
00582   void SetRoot(KdTreeNodeType* root)
00583     {
00584     if( this->m_Root )
00585       {
00586       this->DeleteNode( this->m_Root );
00587       }
00588     this->m_Root = root;
00589     }
00591 
00593   KdTreeNodeType* GetRoot()
00594     {
00595     return m_Root;
00596     }
00597 
00600   const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
00601     {
00602     return m_Sample->GetMeasurementVector(id); 
00603     }
00604 
00607   AbsoluteFrequencyType GetFrequency(InstanceIdentifier id) const
00608     {
00609     return m_Sample->GetFrequency( id ); 
00610     }
00611 
00613   DistanceMetricType* GetDistanceMetric()
00614     {
00615     return m_DistanceMetric.GetPointer();
00616     }
00617 
00619   void Search(const MeasurementVectorType &query,
00620               unsigned int numberOfNeighborsRequested,
00621               InstanceIdentifierVectorType& result) const;
00622 
00624   void Search(const MeasurementVectorType &query,
00625               double radius,
00626               InstanceIdentifierVectorType& result) const;
00627 
00630   int GetNumberOfVisits() const
00631     {
00632     return m_NumberOfVisits; 
00633     }
00634 
00640   bool BallWithinBounds(const MeasurementVectorType &query,
00641                         MeasurementVectorType &lowerBound,
00642                         MeasurementVectorType &upperBound,
00643                         double radius) const;
00644 
00648   bool BoundsOverlapBall(const MeasurementVectorType &query,
00649                          MeasurementVectorType &lowerBound,
00650                          MeasurementVectorType &upperBound,
00651                          double radius) const;
00652 
00654   void DeleteNode(KdTreeNodeType *node);
00655 
00657   void PrintTree( std::ostream & os ) const;
00658 
00660   void PrintTree(KdTreeNodeType *node, unsigned int level,
00661                  unsigned int activeDimension,
00662                  std::ostream & os = std::cout ) const;
00663 
00666   void PlotTree( std::ostream & os ) const;
00667 
00669   void PlotTree(KdTreeNodeType *node, std::ostream & os = std::cout ) const;
00670 
00671 
00672   typedef typename TSample::Iterator      Iterator;
00673   typedef typename TSample::ConstIterator ConstIterator;
00674 
00675   Iterator Begin()
00676     {
00677     typename TSample::ConstIterator iter = m_Sample->Begin();
00678     return iter;
00679     }
00680 
00681   Iterator End()
00682     {
00683     Iterator iter = m_Sample->End();
00684     return iter;
00685     }
00686 
00687   ConstIterator Begin() const
00688     {
00689     typename TSample::ConstIterator iter = m_Sample->Begin();
00690     return iter;
00691     }
00692 
00693   ConstIterator End() const
00694     {
00695     ConstIterator iter = m_Sample->End();
00696     return iter;
00697     }
00698 
00699 protected:
00701   KdTree();
00702 
00704   virtual ~KdTree();
00705 
00706   void PrintSelf(std::ostream& os, Indent indent) const;
00707 
00709   int NearestNeighborSearchLoop(const KdTreeNodeType* node,
00710                                 const MeasurementVectorType &query,
00711                                 MeasurementVectorType &lowerBound,
00712                                 MeasurementVectorType &upperBound) const;
00713 
00715   int SearchLoop(const KdTreeNodeType* node, const MeasurementVectorType &query,
00716                  MeasurementVectorType &lowerBound,
00717                  MeasurementVectorType &upperBound) const;
00718 private:
00719   KdTree(const Self&); //purposely not implemented
00720   void operator=(const Self&); //purposely not implemented
00722 
00724   const TSample* m_Sample;
00725 
00727   int m_BucketSize;
00728 
00730   KdTreeNodeType* m_Root;
00731 
00733   KdTreeNodeType* m_EmptyTerminalNode;
00734 
00736   typename DistanceMetricType::Pointer m_DistanceMetric;
00737 
00738   mutable bool m_IsNearestNeighborSearch;
00739 
00740   mutable double m_SearchRadius;
00741 
00742   mutable InstanceIdentifierVectorType m_Neighbors;
00743 
00745   mutable NearestNeighbors m_NearestNeighbors;
00746 
00748   mutable MeasurementVectorType m_LowerBound;
00749 
00751   mutable MeasurementVectorType m_UpperBound;
00752 
00754   mutable int m_NumberOfVisits;
00755 
00757   mutable bool m_StopSearch;
00758 
00760   mutable NeighborType m_TempNeighbor;
00761 
00763   MeasurementVectorSizeType m_MeasurementVectorSize;
00764 }; // end of class
00765 
00766 } // end of namespace Statistics
00767 } // end of namespace itk
00768 
00769 #ifndef ITK_MANUAL_INSTANTIATION
00770 #include "itkKdTree.txx"
00771 #endif
00772 
00773 #endif
00774 

Generated at Mon Jul 12 2010 18:54:40 for ITK by doxygen 1.7.1 written by Dimitri van Heesch, © 1997-2000