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

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: 2008-04-26 00:08:19 $
00007   Version:   $Revision: 1.27 $
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 "itkEuclideanDistance.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   { return false; }
00148 
00149   void GetParameters(unsigned int &partitionDimension,
00150                      MeasurementType &partitionValue) const;
00151 
00152   Superclass* Left()
00153   { return m_Left; }
00154 
00155   Superclass* Right()
00156   { return m_Right; }
00157 
00158   const Superclass* Left() const
00159   { return m_Left; }
00160 
00161   const Superclass* Right() const
00162   { return m_Right; }
00163 
00164   unsigned int Size() const
00165   { return 0; }
00166 
00167   void GetWeightedCentroid( CentroidType & )
00168   { /* do nothing */ }
00169 
00170   void GetCentroid( CentroidType & )
00171   { /* do nothing */ }
00172 
00173   // Returns the identifier of the only MeasurementVector associated with 
00174   // this node in the tree. This MeasurementVector will be used later during
00175   // the distance computation when querying the tree.
00176   InstanceIdentifier GetInstanceIdentifier(size_t) const
00177   { return this->m_InstanceIdentifier; }
00178 
00179   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00180   { this->m_InstanceIdentifier = valueId; }
00181 
00182 private:
00183   unsigned int          m_PartitionDimension;
00184   MeasurementType       m_PartitionValue;
00185   InstanceIdentifier    m_InstanceIdentifier;
00186   Superclass* m_Left;
00187   Superclass* m_Right;
00188 }; // end of class
00189 
00204 template< class TSample >
00205 struct KdTreeWeightedCentroidNonterminalNode: public KdTreeNode< TSample >
00206 {
00207   typedef KdTreeNode< TSample > Superclass;
00208   typedef typename Superclass::MeasurementType MeasurementType;
00209   typedef typename Superclass::CentroidType CentroidType;
00210   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00211   typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;
00212 
00213   KdTreeWeightedCentroidNonterminalNode(unsigned int partitionDimension,
00214                                          MeasurementType partitionValue,
00215                                          Superclass* left,
00216                                          Superclass* right,
00217                                          CentroidType &centroid,
00218                                          unsigned int size);
00219   virtual ~KdTreeWeightedCentroidNonterminalNode() {}
00220 
00221   virtual bool IsTerminal() const
00222   { return false; }
00223 
00224   void GetParameters(unsigned int &partitionDimension,
00225                      MeasurementType &partitionValue) const;
00226 
00228   MeasurementVectorSizeType GetMeasurementVectorSize() const
00229     {
00230     return m_MeasurementVectorSize;
00231     }
00232 
00233   Superclass* Left()
00234   { return m_Left; }
00235 
00236   Superclass* Right()
00237   { return m_Right; }
00238 
00239 
00240   const Superclass* Left() const
00241   { return m_Left; }
00242 
00243   const Superclass* Right() const
00244   { return m_Right; }
00245 
00246   unsigned int Size() const
00247   { return m_Size; }
00248 
00249   void GetWeightedCentroid(CentroidType &centroid)
00250   { centroid = m_WeightedCentroid; }
00251 
00252   void GetCentroid(CentroidType &centroid)
00253   { centroid = m_Centroid; }
00254 
00255   InstanceIdentifier GetInstanceIdentifier(size_t) const
00256   { return this->m_InstanceIdentifier; }
00257 
00258   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00259   { this->m_InstanceIdentifier = valueId; }
00260 
00261 private:
00262   MeasurementVectorSizeType   m_MeasurementVectorSize;
00263   unsigned int                m_PartitionDimension;
00264   MeasurementType             m_PartitionValue;
00265   CentroidType                m_WeightedCentroid;
00266   CentroidType                m_Centroid;
00267   InstanceIdentifier          m_InstanceIdentifier;
00268   unsigned int                m_Size;
00269   Superclass*                 m_Left;
00270   Superclass*                 m_Right;
00271 }; // end of class
00272 
00273 
00285 template< class TSample >
00286 struct KdTreeTerminalNode: public KdTreeNode< TSample >
00287 {
00288   typedef KdTreeNode< TSample > Superclass;
00289   typedef typename Superclass::MeasurementType MeasurementType;
00290   typedef typename Superclass::CentroidType CentroidType;
00291   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00292 
00293   KdTreeTerminalNode() {}
00294 
00295   virtual ~KdTreeTerminalNode() {}
00296 
00297   bool IsTerminal() const
00298   { return true; }
00299 
00300   void GetParameters(unsigned int &,
00301                      MeasurementType &) const {}
00302 
00303   Superclass* Left()
00304   { return 0; }
00305 
00306   Superclass* Right()
00307   { return 0; }
00308 
00309 
00310   const Superclass* Left() const
00311   { return 0; }
00312 
00313   const Superclass* Right() const
00314   { return 0; }
00315 
00316   unsigned int Size() const
00317   { return static_cast<unsigned int>( m_InstanceIdentifiers.size() ); }
00318 
00319   void GetWeightedCentroid(CentroidType &)
00320   { /* do nothing */ }
00321 
00322   void GetCentroid(CentroidType &)
00323   { /* do nothing */ }
00324 
00325   InstanceIdentifier GetInstanceIdentifier(size_t index) const
00326   { return m_InstanceIdentifiers[index]; }
00327 
00328   void AddInstanceIdentifier(InstanceIdentifier id)
00329   { m_InstanceIdentifiers.push_back(id);}
00330 
00331 private:
00332   std::vector< InstanceIdentifier > m_InstanceIdentifiers;
00333 }; // end of class
00334 
00367 template < class TSample >
00368 class ITK_EXPORT KdTree : public Object
00369 {
00370 public:
00372   typedef KdTree Self;
00373   typedef Object Superclass;
00374   typedef SmartPointer<Self> Pointer;
00375   typedef SmartPointer<const Self> ConstPointer;
00376 
00378   itkTypeMacro(KdTree, Object);
00379 
00381   itkNewMacro(Self);
00382 
00384   typedef TSample SampleType;
00385   typedef typename TSample::MeasurementVectorType MeasurementVectorType;
00386   typedef typename TSample::MeasurementType MeasurementType;
00387   typedef typename TSample::InstanceIdentifier InstanceIdentifier;
00388   typedef typename TSample::FrequencyType FrequencyType;
00389 
00390   typedef unsigned int                    MeasurementVectorSizeType;
00391 
00394   itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
00395 
00397   typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType;
00398 
00400   typedef KdTreeNode< TSample > KdTreeNodeType;
00401 
00405   typedef std::pair< InstanceIdentifier, double > NeighborType;
00406 
00407   typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
00408 
00418   class NearestNeighbors
00419   {
00420   public:
00422     NearestNeighbors() {}
00423 
00425     ~NearestNeighbors() {}
00426 
00429     void resize(unsigned int k)
00430     {
00431       m_Identifiers.clear();
00432       m_Identifiers.resize(k, NumericTraits< unsigned long >::max());
00433       m_Distances.clear();
00434       m_Distances.resize(k, NumericTraits< double >::max());
00435       m_FarthestNeighborIndex = 0;
00436     }
00438 
00440     double GetLargestDistance()
00441     { return m_Distances[m_FarthestNeighborIndex]; }
00442 
00445     void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
00446     {
00447       m_Identifiers[m_FarthestNeighborIndex] = id;
00448       m_Distances[m_FarthestNeighborIndex] = distance;
00449       double farthestDistance = NumericTraits< double >::min();
00450       const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
00451       for ( unsigned int i = 0; i < size; i++ )
00452         {
00453         if ( m_Distances[i] > farthestDistance )
00454           {
00455           farthestDistance = m_Distances[i];
00456           m_FarthestNeighborIndex = i;
00457           }
00458         }
00459     }
00461 
00463     const InstanceIdentifierVectorType & GetNeighbors() const
00464     { return m_Identifiers; }
00465 
00468     InstanceIdentifier GetNeighbor(unsigned int index) const
00469     { return m_Identifiers[index]; }
00470 
00472     const std::vector< double >& GetDistances() const
00473     { return m_Distances; }
00474 
00475   private:
00477     unsigned int m_FarthestNeighborIndex;
00478 
00480     InstanceIdentifierVectorType m_Identifiers;
00481 
00484     std::vector< double > m_Distances;
00485   };
00486 
00489   void SetBucketSize(unsigned int size);
00490 
00493   void SetSample(const TSample* sample);
00494 
00496   const TSample* GetSample() const
00497   { return m_Sample; }
00498 
00499   unsigned long Size() const
00500   { return m_Sample->Size(); }
00501 
00506   KdTreeNodeType* GetEmptyTerminalNode()
00507   { return m_EmptyTerminalNode; }
00508 
00511   void SetRoot(KdTreeNodeType* root)
00512   { m_Root = root; }
00513 
00515   KdTreeNodeType* GetRoot()
00516   { return m_Root; }
00517 
00520   const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
00521   { return m_Sample->GetMeasurementVector(id); }
00522 
00525   FrequencyType GetFrequency(InstanceIdentifier id) const
00526   { return m_Sample->GetFrequency( id ); }
00527 
00529   DistanceMetricType* GetDistanceMetric()
00530   { return m_DistanceMetric.GetPointer(); }
00531 
00533   void Search(const MeasurementVectorType &query,
00534               unsigned int numberOfNeighborsRequested,
00535               InstanceIdentifierVectorType& result) const;
00536 
00538   void Search(const MeasurementVectorType &query,
00539               double radius,
00540               InstanceIdentifierVectorType& result) const;
00541 
00544   int GetNumberOfVisits() const
00545   { return m_NumberOfVisits; }
00546 
00552   bool BallWithinBounds(const MeasurementVectorType &query,
00553                         MeasurementVectorType &lowerBound,
00554                         MeasurementVectorType &upperBound,
00555                         double radius) const;
00556 
00560   bool BoundsOverlapBall(const MeasurementVectorType &query,
00561                          MeasurementVectorType &lowerBound,
00562                          MeasurementVectorType &upperBound,
00563                          double radius) const;
00564 
00566   void DeleteNode(KdTreeNodeType *node);
00567 
00569   void PrintTree( std::ostream & os ) const;
00570 
00572   void PrintTree(KdTreeNodeType *node, unsigned int level,
00573                  unsigned int activeDimension,
00574                  std::ostream & os = std::cout ) const;
00575 
00578   void PlotTree( std::ostream & os ) const;
00579 
00581   void PlotTree(KdTreeNodeType *node, std::ostream & os = std::cout ) const;
00582 
00583 
00584   typedef typename TSample::Iterator Iterator;
00585   typedef typename TSample::ConstIterator ConstIterator;
00586 
00587   Iterator Begin()
00588   {
00589     typename TSample::ConstIterator iter = m_Sample->Begin();
00590     return iter;
00591   }
00592 
00593   Iterator End()
00594   {
00595     Iterator iter = m_Sample->End();
00596     return iter;
00597   }
00598 
00599   ConstIterator Begin() const
00600   {
00601     typename TSample::ConstIterator iter = m_Sample->Begin();
00602     return iter;
00603   }
00604 
00605   ConstIterator End() const
00606   {
00607     ConstIterator iter = m_Sample->End();
00608     return iter;
00609   }
00610 
00611 protected:
00613   KdTree();
00614 
00616   virtual ~KdTree();
00617 
00618   void PrintSelf(std::ostream& os, Indent indent) const;
00619 
00621   int NearestNeighborSearchLoop(const KdTreeNodeType* node,
00622                                 const MeasurementVectorType &query,
00623                                 MeasurementVectorType &lowerBound,
00624                                 MeasurementVectorType &upperBound) const;
00625 
00627   int SearchLoop(const KdTreeNodeType* node, const MeasurementVectorType &query,
00628                  MeasurementVectorType &lowerBound,
00629                  MeasurementVectorType &upperBound) const;
00630 private:
00631   KdTree(const Self&); //purposely not implemented
00632   void operator=(const Self&); //purposely not implemented
00634 
00636   const TSample* m_Sample;
00637 
00639   int m_BucketSize;
00640 
00642   KdTreeNodeType* m_Root;
00643 
00645   KdTreeNodeType* m_EmptyTerminalNode;
00646 
00648   typename DistanceMetricType::Pointer m_DistanceMetric;
00649 
00650   mutable bool m_IsNearestNeighborSearch;
00651 
00652   mutable double m_SearchRadius;
00653 
00654   mutable InstanceIdentifierVectorType m_Neighbors;
00655 
00657   mutable NearestNeighbors m_NearestNeighbors;
00658 
00660   mutable MeasurementVectorType m_LowerBound;
00661 
00663   mutable MeasurementVectorType m_UpperBound;
00664 
00666   mutable int m_NumberOfVisits;
00667 
00669   mutable bool m_StopSearch;
00670 
00672   mutable NeighborType m_TempNeighbor;
00673 
00675   MeasurementVectorSizeType m_MeasurementVectorSize;
00676 }; // end of class
00677 
00678 } // end of namespace Statistics
00679 } // end of namespace itk
00680 
00681 #ifndef ITK_MANUAL_INSTANTIATION
00682 #include "itkKdTree.txx"
00683 #endif
00684 
00685 #endif
00686 

Generated at Tue Jul 29 21:00:28 2008 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000