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: 2009-05-02 05:43:56 $
00007   Version:   $Revision: 1.1 $
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   bool IsTerminal() const
00334     {
00335     return true;
00336     }
00337 
00338   void GetParameters(unsigned int &,
00339                      MeasurementType &) const {}
00340 
00341   Superclass* Left()
00342     {
00343     return 0;
00344     }
00345 
00346   Superclass* Right()
00347     {
00348     return 0;
00349     }
00350 
00351   const Superclass* Left() const
00352     {
00353     return 0;
00354     }
00355 
00356   const Superclass* Right() const
00357     {
00358     return 0;
00359     }
00360 
00361   unsigned int Size() const
00362     {
00363     return static_cast<unsigned int>( m_InstanceIdentifiers.size() );
00364     }
00365 
00366   void GetWeightedCentroid(CentroidType &)
00367     { 
00368     /* do nothing */ 
00369     }
00370 
00371   void GetCentroid(CentroidType &)
00372     {
00373     /* do nothing */ 
00374     }
00375 
00376   InstanceIdentifier GetInstanceIdentifier(size_t index) const
00377     { 
00378     return m_InstanceIdentifiers[index];
00379     }
00380 
00381   void AddInstanceIdentifier(InstanceIdentifier id)
00382     {
00383     m_InstanceIdentifiers.push_back(id);
00384     }
00385 
00386 private:
00387   std::vector< InstanceIdentifier > m_InstanceIdentifiers;
00388 }; // end of class
00389 
00422 template < class TSample >
00423 class ITK_EXPORT KdTree : public Object
00424 {
00425 public:
00427   typedef KdTree                                    Self;
00428   typedef Object                                    Superclass;
00429   typedef SmartPointer<Self>                        Pointer;
00430   typedef SmartPointer<const Self>                  ConstPointer;
00431 
00433   itkTypeMacro(KdTree, Object);
00434 
00436   itkNewMacro(Self);
00437 
00439   typedef TSample                                     SampleType;
00440   typedef typename TSample::MeasurementVectorType     MeasurementVectorType;
00441   typedef typename TSample::MeasurementType           MeasurementType;
00442   typedef typename TSample::InstanceIdentifier        InstanceIdentifier;
00443   typedef typename TSample::AbsoluteFrequencyType     AbsoluteFrequencyType;
00444 
00445   typedef unsigned int                    MeasurementVectorSizeType;
00446 
00449   itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
00450 
00452   typedef EuclideanDistanceMetric< MeasurementVectorType > DistanceMetricType;
00453 
00455   typedef KdTreeNode< TSample > KdTreeNodeType;
00456 
00460   typedef std::pair< InstanceIdentifier, double > NeighborType;
00461 
00462   typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
00463 
00473   class NearestNeighbors {
00474   public:
00476     NearestNeighbors() {}
00477 
00479     ~NearestNeighbors() {}
00480 
00483     void resize(unsigned int k)
00484       {
00485       m_Identifiers.clear();
00486       m_Identifiers.resize(k, NumericTraits< unsigned long >::max());
00487       m_Distances.clear();
00488       m_Distances.resize(k, NumericTraits< double >::max());
00489       m_FarthestNeighborIndex = 0;
00490       }
00492 
00494     double GetLargestDistance()
00495       {
00496       return m_Distances[m_FarthestNeighborIndex];
00497       }
00498 
00501     void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
00502       {
00503       m_Identifiers[m_FarthestNeighborIndex] = id;
00504       m_Distances[m_FarthestNeighborIndex] = distance;
00505       double farthestDistance = NumericTraits< double >::min();
00506       const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
00507       for ( unsigned int i = 0; i < size; i++ )
00508         {
00509         if ( m_Distances[i] > farthestDistance )
00510           {
00511           farthestDistance = m_Distances[i];
00512           m_FarthestNeighborIndex = i;
00513           }
00514         }
00515       }
00517 
00519     const InstanceIdentifierVectorType & GetNeighbors() const
00520       {
00521       return m_Identifiers;
00522       }
00523 
00526     InstanceIdentifier GetNeighbor(unsigned int index) const
00527       {
00528       return m_Identifiers[index];
00529       }
00530 
00532     const std::vector< double >& GetDistances() const
00533       { 
00534       return m_Distances;
00535       }
00536 
00537   private:
00539     unsigned int m_FarthestNeighborIndex;
00540 
00542     InstanceIdentifierVectorType m_Identifiers;
00543 
00546     std::vector< double > m_Distances;
00547   };
00548 
00551   void SetBucketSize(unsigned int size);
00552 
00555   void SetSample(const TSample* sample);
00556 
00558   const TSample* GetSample() const
00559     {
00560     return m_Sample;
00561     }
00562 
00563   unsigned long Size() const
00564     {
00565     return m_Sample->Size();
00566     }
00567 
00572   KdTreeNodeType* GetEmptyTerminalNode()
00573     {
00574     return m_EmptyTerminalNode;
00575     }
00576 
00579   void SetRoot(KdTreeNodeType* root)
00580     {
00581     m_Root = root;
00582     }
00583 
00585   KdTreeNodeType* GetRoot()
00586     {
00587     return m_Root;
00588     }
00589 
00592   const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
00593     {
00594     return m_Sample->GetMeasurementVector(id); 
00595     }
00596 
00599   AbsoluteFrequencyType GetFrequency(InstanceIdentifier id) const
00600     {
00601     return m_Sample->GetFrequency( id ); 
00602     }
00603 
00605   DistanceMetricType* GetDistanceMetric()
00606     {
00607     return m_DistanceMetric.GetPointer();
00608     }
00609 
00611   void Search(const MeasurementVectorType &query,
00612               unsigned int numberOfNeighborsRequested,
00613               InstanceIdentifierVectorType& result) const;
00614 
00616   void Search(const MeasurementVectorType &query,
00617               double radius,
00618               InstanceIdentifierVectorType& result) const;
00619 
00622   int GetNumberOfVisits() const
00623     {
00624     return m_NumberOfVisits; 
00625     }
00626 
00632   bool BallWithinBounds(const MeasurementVectorType &query,
00633                         MeasurementVectorType &lowerBound,
00634                         MeasurementVectorType &upperBound,
00635                         double radius) const;
00636 
00640   bool BoundsOverlapBall(const MeasurementVectorType &query,
00641                          MeasurementVectorType &lowerBound,
00642                          MeasurementVectorType &upperBound,
00643                          double radius) const;
00644 
00646   void DeleteNode(KdTreeNodeType *node);
00647 
00649   void PrintTree( std::ostream & os ) const;
00650 
00652   void PrintTree(KdTreeNodeType *node, unsigned int level,
00653                  unsigned int activeDimension,
00654                  std::ostream & os = std::cout ) const;
00655 
00658   void PlotTree( std::ostream & os ) const;
00659 
00661   void PlotTree(KdTreeNodeType *node, std::ostream & os = std::cout ) const;
00662 
00663 
00664   typedef typename TSample::Iterator      Iterator;
00665   typedef typename TSample::ConstIterator ConstIterator;
00666 
00667   Iterator Begin()
00668     {
00669     typename TSample::ConstIterator iter = m_Sample->Begin();
00670     return iter;
00671     }
00672 
00673   Iterator End()
00674     {
00675     Iterator iter = m_Sample->End();
00676     return iter;
00677     }
00678 
00679   ConstIterator Begin() const
00680     {
00681     typename TSample::ConstIterator iter = m_Sample->Begin();
00682     return iter;
00683     }
00684 
00685   ConstIterator End() const
00686     {
00687     ConstIterator iter = m_Sample->End();
00688     return iter;
00689     } 
00690 
00691 protected:
00693   KdTree();
00694 
00696   virtual ~KdTree();
00697 
00698   void PrintSelf(std::ostream& os, Indent indent) const;
00699 
00701   int NearestNeighborSearchLoop(const KdTreeNodeType* node,
00702                                 const MeasurementVectorType &query,
00703                                 MeasurementVectorType &lowerBound,
00704                                 MeasurementVectorType &upperBound) const;
00705 
00707   int SearchLoop(const KdTreeNodeType* node, const MeasurementVectorType &query,
00708                  MeasurementVectorType &lowerBound,
00709                  MeasurementVectorType &upperBound) const;
00710 private:
00711   KdTree(const Self&); //purposely not implemented
00712   void operator=(const Self&); //purposely not implemented
00714 
00716   const TSample* m_Sample;
00717 
00719   int m_BucketSize;
00720 
00722   KdTreeNodeType* m_Root;
00723 
00725   KdTreeNodeType* m_EmptyTerminalNode;
00726 
00728   typename DistanceMetricType::Pointer m_DistanceMetric;
00729 
00730   mutable bool m_IsNearestNeighborSearch;
00731 
00732   mutable double m_SearchRadius;
00733 
00734   mutable InstanceIdentifierVectorType m_Neighbors;
00735 
00737   mutable NearestNeighbors m_NearestNeighbors;
00738 
00740   mutable MeasurementVectorType m_LowerBound;
00741 
00743   mutable MeasurementVectorType m_UpperBound;
00744 
00746   mutable int m_NumberOfVisits;
00747 
00749   mutable bool m_StopSearch;
00750 
00752   mutable NeighborType m_TempNeighbor;
00753 
00755   MeasurementVectorSizeType m_MeasurementVectorSize;
00756 }; // end of class
00757 
00758 } // end of namespace Statistics
00759 } // end of namespace itk
00760 
00761 #ifndef ITK_MANUAL_INSTANTIATION
00762 #include "itkKdTree.txx"
00763 #endif
00764 
00765 #endif
00766 

Generated at Tue Sep 15 03:40:51 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000