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

Numerics/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:09:18 $
00007   Version:   $Revision: 1.30 $
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 
00065 template< class TSample >
00066 struct KdTreeNode
00067 {
00069   typedef KdTreeNode< TSample> Self;
00070 
00072   typedef typename TSample::MeasurementType MeasurementType;
00073 
00075   typedef Array< double > CentroidType;
00076 
00079   typedef typename TSample::InstanceIdentifier InstanceIdentifier;
00080 
00083   virtual bool IsTerminal() const = 0;
00084 
00090   virtual void GetParameters(unsigned int &partitionDimension,
00091                              MeasurementType &partitionValue) const = 0;
00092 
00094   virtual       Self* Left()       = 0;
00095   virtual const Self* Left() const = 0;
00097 
00099   virtual       Self* Right()       = 0;
00100   virtual const Self* Right() const = 0;
00102 
00105   virtual unsigned int Size() const = 0;
00106 
00108   virtual void GetWeightedCentroid(CentroidType &centroid) = 0;
00109 
00111   virtual void GetCentroid(CentroidType &centroid) = 0;
00112 
00114   virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0;
00115 
00117   virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0;
00118 
00120   virtual ~KdTreeNode() {}; // needed to subclasses will actually be deleted
00121 }; // end of class
00122 
00134 template< class TSample >
00135 struct KdTreeNonterminalNode: public KdTreeNode< TSample >
00136 {
00137   typedef KdTreeNode< TSample >                   Superclass;
00138   typedef typename Superclass::MeasurementType    MeasurementType;
00139   typedef typename Superclass::CentroidType       CentroidType;
00140   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00141 
00142   KdTreeNonterminalNode(unsigned int partitionDimension,
00143                         MeasurementType partitionValue,
00144                         Superclass* left,
00145                         Superclass* right);
00146 
00147   virtual ~KdTreeNonterminalNode() {}
00148 
00149   virtual bool IsTerminal() const
00150     { return false; }
00151 
00152   void GetParameters(unsigned int &partitionDimension,
00153                      MeasurementType &partitionValue) const;
00154 
00155   Superclass* Left()
00156     { return m_Left; }
00157 
00158   Superclass* Right()
00159     { return m_Right; }
00160 
00161   const Superclass* Left() const
00162     { return m_Left; }
00163 
00164   const Superclass* Right() const
00165     { return m_Right; }
00166 
00167   unsigned int Size() const
00168     { return 0; }
00169 
00170   void GetWeightedCentroid( CentroidType & )
00171     {}
00172 
00173   void GetCentroid( CentroidType & )
00174     {}
00175 
00176   // Returns the identifier of the only MeasurementVector associated with 
00177   // this node in the tree. This MeasurementVector will be used later during
00178   // the distance computation when querying the tree.
00179   InstanceIdentifier GetInstanceIdentifier(size_t) const
00180     { return this->m_InstanceIdentifier; }
00181 
00182   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00183     { this->m_InstanceIdentifier = valueId; }
00184 
00185 private:
00186   unsigned int          m_PartitionDimension;
00187   MeasurementType       m_PartitionValue;
00188   InstanceIdentifier    m_InstanceIdentifier;
00189   Superclass* m_Left;
00190   Superclass* m_Right;
00191 }; // end of class
00192 
00207 template< class TSample >
00208 struct KdTreeWeightedCentroidNonterminalNode: public KdTreeNode< TSample >
00209 {
00210   typedef KdTreeNode< TSample >                       Superclass;
00211   typedef typename Superclass::MeasurementType        MeasurementType;
00212   typedef typename Superclass::CentroidType           CentroidType;
00213   typedef typename Superclass::InstanceIdentifier     InstanceIdentifier;
00214   typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;
00215 
00216   KdTreeWeightedCentroidNonterminalNode(unsigned int partitionDimension,
00217                                          MeasurementType partitionValue,
00218                                          Superclass* left,
00219                                          Superclass* right,
00220                                          CentroidType &centroid,
00221                                          unsigned int size);
00222   virtual ~KdTreeWeightedCentroidNonterminalNode()
00223     {
00224     }
00225 
00226 
00227   virtual bool IsTerminal() const
00228     { return false; }
00229 
00230   void GetParameters(unsigned int &partitionDimension,
00231                      MeasurementType &partitionValue) const;
00232 
00234   MeasurementVectorSizeType GetMeasurementVectorSize() const
00235     {
00236     return m_MeasurementVectorSize;
00237     }
00238 
00239   Superclass* Left()
00240     { return m_Left; }
00241 
00242   Superclass* Right()
00243     { return m_Right; }
00244 
00245   const Superclass* Left() const
00246     { return m_Left; }
00247 
00248   const Superclass* Right() const
00249     { return m_Right; }
00250 
00251   unsigned int Size() const
00252     { return m_Size; }
00253 
00254   void GetWeightedCentroid(CentroidType &centroid)
00255   { centroid = m_WeightedCentroid; }
00256 
00257   void GetCentroid(CentroidType &centroid)
00258     { centroid = m_Centroid; }
00259 
00260   InstanceIdentifier GetInstanceIdentifier(size_t) const
00261   { return this->m_InstanceIdentifier; }
00262 
00263   void AddInstanceIdentifier(InstanceIdentifier valueId) 
00264   { this->m_InstanceIdentifier = valueId; }
00265 
00266 private:
00267   MeasurementVectorSizeType   m_MeasurementVectorSize;
00268   unsigned int                m_PartitionDimension;
00269   MeasurementType             m_PartitionValue;
00270   CentroidType                m_WeightedCentroid;
00271   CentroidType                m_Centroid;
00272   InstanceIdentifier          m_InstanceIdentifier;
00273   unsigned int                m_Size;
00274   Superclass*                 m_Left;
00275   Superclass*                 m_Right;
00276 }; // end of class
00277 
00278 
00290 template< class TSample >
00291 struct KdTreeTerminalNode: public KdTreeNode< TSample >
00292 {
00293   typedef KdTreeNode< TSample >                   Superclass;
00294   typedef typename Superclass::MeasurementType    MeasurementType;
00295   typedef typename Superclass::CentroidType       CentroidType;
00296   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00297 
00298   KdTreeTerminalNode() {}
00299 
00300   virtual ~KdTreeTerminalNode()
00301     { 
00302     this->m_InstanceIdentifiers.clear();
00303     }
00304 
00305   bool IsTerminal() const
00306     { return true; }
00307 
00308   void GetParameters(unsigned int &,
00309                      MeasurementType &) const {}
00310 
00311   Superclass* Left()
00312     { return 0; }
00313 
00314   Superclass* Right()
00315     { return 0; }
00316 
00317   const Superclass* Left() const
00318     { return 0; }
00319 
00320   const Superclass* Right() const
00321     { return 0; }
00322 
00323   unsigned int Size() const
00324     { return static_cast<unsigned int>( m_InstanceIdentifiers.size() ); }
00325 
00326   void GetWeightedCentroid(CentroidType &)
00327     {}
00328 
00329   void GetCentroid(CentroidType &)
00330     {}
00331 
00332   InstanceIdentifier GetInstanceIdentifier(size_t index) const
00333     { return m_InstanceIdentifiers[index]; }
00334 
00335   void AddInstanceIdentifier(InstanceIdentifier id)
00336     { m_InstanceIdentifiers.push_back(id);}
00337 
00338 private:
00339   std::vector< InstanceIdentifier > m_InstanceIdentifiers;
00340 }; // end of class
00341 
00374 template < class TSample >
00375 class ITK_EXPORT KdTree : public Object
00376 {
00377 public:
00379   typedef KdTree                   Self;
00380   typedef Object                   Superclass;
00381   typedef SmartPointer<Self>       Pointer;
00382   typedef SmartPointer<const Self> ConstPointer;
00383 
00385   itkTypeMacro(KdTree, Object);
00386 
00388   itkNewMacro(Self);
00389 
00391   typedef TSample                                 SampleType;
00392   typedef typename TSample::MeasurementVectorType MeasurementVectorType;
00393   typedef typename TSample::MeasurementType       MeasurementType;
00394   typedef typename TSample::InstanceIdentifier    InstanceIdentifier;
00395   typedef typename TSample::FrequencyType         FrequencyType;
00396 
00397   typedef unsigned int                    MeasurementVectorSizeType;
00398 
00401   itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
00402 
00404   typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType;
00405 
00407   typedef KdTreeNode< TSample > KdTreeNodeType;
00408 
00412   typedef std::pair< InstanceIdentifier, double > NeighborType;
00413 
00414   typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
00415 
00425   class NearestNeighbors
00426     {
00427     public:
00429     NearestNeighbors() {}
00430 
00432     ~NearestNeighbors() {}
00433 
00436     void resize(unsigned int k)
00437       {
00438       m_Identifiers.clear();
00439       m_Identifiers.resize(k, NumericTraits< unsigned long >::max());
00440       m_Distances.clear();
00441       m_Distances.resize(k, NumericTraits< double >::max());
00442       m_FarthestNeighborIndex = 0;
00443       }
00445 
00447     double GetLargestDistance()
00448       { return m_Distances[m_FarthestNeighborIndex]; }
00449 
00452     void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
00453       {
00454       m_Identifiers[m_FarthestNeighborIndex] = id;
00455       m_Distances[m_FarthestNeighborIndex] = distance;
00456       double farthestDistance = NumericTraits< double >::min();
00457       const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
00458       for ( unsigned int i = 0; i < size; i++ )
00459         {
00460         if ( m_Distances[i] > farthestDistance )
00461           {
00462           farthestDistance = m_Distances[i];
00463           m_FarthestNeighborIndex = i;
00464           }
00465         }
00466       }
00468 
00470     const InstanceIdentifierVectorType & GetNeighbors() const
00471       { return m_Identifiers; }
00472 
00475     InstanceIdentifier GetNeighbor(unsigned int index) const
00476       { return m_Identifiers[index]; }
00477 
00479     const std::vector< double >& GetDistances() const
00480       { return m_Distances; }
00481 
00482     private:
00484       unsigned int m_FarthestNeighborIndex;
00485 
00487       InstanceIdentifierVectorType m_Identifiers;
00488 
00491       std::vector< double > m_Distances;
00492   };
00493 
00496   void SetBucketSize(unsigned int size);
00497 
00500   void SetSample(const TSample* sample);
00501 
00503   const TSample* GetSample() const
00504     { return m_Sample; }
00505 
00506   unsigned long Size() const
00507     { return m_Sample->Size(); }
00508 
00513   KdTreeNodeType* GetEmptyTerminalNode()
00514     { return m_EmptyTerminalNode; }
00515 
00518   void SetRoot(KdTreeNodeType* root)
00519     { 
00520     if( this->m_Root )
00521       {
00522       this->DeleteNode( this->m_Root );
00523       }
00524     this->m_Root = root;
00525     }
00527 
00529   KdTreeNodeType* GetRoot()
00530     { return m_Root; }
00531 
00534   const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
00535     { return m_Sample->GetMeasurementVector(id); }
00536 
00539   FrequencyType GetFrequency(InstanceIdentifier id) const
00540     { return m_Sample->GetFrequency( id ); }
00541 
00543   DistanceMetricType* GetDistanceMetric()
00544     { return m_DistanceMetric.GetPointer(); }
00545 
00547   void Search(const MeasurementVectorType &query,
00548               unsigned int numberOfNeighborsRequested,
00549               InstanceIdentifierVectorType& result) const;
00550 
00552   void Search(const MeasurementVectorType &query,
00553               double radius,
00554               InstanceIdentifierVectorType& result) const;
00555 
00558   int GetNumberOfVisits() const
00559     { return m_NumberOfVisits; }
00560 
00566   bool BallWithinBounds(const MeasurementVectorType &query,
00567                         MeasurementVectorType &lowerBound,
00568                         MeasurementVectorType &upperBound,
00569                         double radius) const;
00570 
00574   bool BoundsOverlapBall(const MeasurementVectorType &query,
00575                          MeasurementVectorType &lowerBound,
00576                          MeasurementVectorType &upperBound,
00577                          double radius) const;
00578 
00580   void DeleteNode(KdTreeNodeType *node);
00581 
00583   void PrintTree( std::ostream & os ) const;
00584 
00586   void PrintTree(KdTreeNodeType *node, unsigned int level,
00587                  unsigned int activeDimension,
00588                  std::ostream & os = std::cout ) const;
00589 
00592   void PlotTree( std::ostream & os ) const;
00593 
00595   void PlotTree(KdTreeNodeType *node, std::ostream & os = std::cout ) const;
00596 
00597 
00598   typedef typename TSample::Iterator      Iterator;
00599   typedef typename TSample::ConstIterator ConstIterator;
00600 
00601   Iterator Begin()
00602     {
00603     typename TSample::ConstIterator iter = m_Sample->Begin();
00604     return iter;
00605     }
00606 
00607   Iterator End()
00608     {
00609     Iterator iter = m_Sample->End();
00610     return iter;
00611     }
00612 
00613   ConstIterator Begin() const
00614     {
00615     typename TSample::ConstIterator iter = m_Sample->Begin();
00616     return iter;
00617     }
00618 
00619   ConstIterator End() const
00620     {
00621     ConstIterator iter = m_Sample->End();
00622     return iter;
00623     }
00624 
00625 protected:
00627   KdTree();
00628 
00630   virtual ~KdTree();
00631 
00632   void PrintSelf(std::ostream& os, Indent indent) const;
00633 
00635   int NearestNeighborSearchLoop(const KdTreeNodeType* node,
00636                                 const MeasurementVectorType &query,
00637                                 MeasurementVectorType &lowerBound,
00638                                 MeasurementVectorType &upperBound) const;
00639 
00641   int SearchLoop(const KdTreeNodeType* node, const MeasurementVectorType &query,
00642                  MeasurementVectorType &lowerBound,
00643                  MeasurementVectorType &upperBound) const;
00644 private:
00645   KdTree(const Self&); //purposely not implemented
00646   void operator=(const Self&); //purposely not implemented
00648 
00650   const TSample* m_Sample;
00651 
00653   int m_BucketSize;
00654 
00656   KdTreeNodeType* m_Root;
00657 
00659   KdTreeNodeType* m_EmptyTerminalNode;
00660 
00662   typename DistanceMetricType::Pointer m_DistanceMetric;
00663 
00664   mutable bool m_IsNearestNeighborSearch;
00665 
00666   mutable double m_SearchRadius;
00667 
00668   mutable InstanceIdentifierVectorType m_Neighbors;
00669 
00671   mutable NearestNeighbors m_NearestNeighbors;
00672 
00674   mutable MeasurementVectorType m_LowerBound;
00675 
00677   mutable MeasurementVectorType m_UpperBound;
00678 
00680   mutable int m_NumberOfVisits;
00681 
00683   mutable bool m_StopSearch;
00684 
00686   mutable NeighborType m_TempNeighbor;
00687 
00689   MeasurementVectorSizeType m_MeasurementVectorSize;
00690 }; // end of class
00691 
00692 } // end of namespace Statistics
00693 } // end of namespace itk
00694 
00695 #ifndef ITK_MANUAL_INSTANTIATION
00696 #include "itkKdTree.txx"
00697 #endif
00698 
00699 #endif
00700 

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