ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkKdTree.h
Go to the documentation of this file.
00001 /*=========================================================================
00002  *
00003  *  Copyright Insight Software Consortium
00004  *
00005  *  Licensed under the Apache License, Version 2.0 (the "License");
00006  *  you may not use this file except in compliance with the License.
00007  *  You may obtain a copy of the License at
00008  *
00009  *         http://www.apache.org/licenses/LICENSE-2.0.txt
00010  *
00011  *  Unless required by applicable law or agreed to in writing, software
00012  *  distributed under the License is distributed on an "AS IS" BASIS,
00013  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  *  See the License for the specific language governing permissions and
00015  *  limitations under the License.
00016  *
00017  *=========================================================================*/
00018 #ifndef __itkKdTree_h
00019 #define __itkKdTree_h
00020 
00021 #include <queue>
00022 #include <vector>
00023 
00024 #include "itkPoint.h"
00025 #include "itkSize.h"
00026 #include "itkObject.h"
00027 #include "itkArray.h"
00028 
00029 #include "itkSubsample.h"
00030 
00031 #include "itkEuclideanDistanceMetric.h"
00032 
00033 namespace itk
00034 {
00035 namespace Statistics
00036 {
00062 template<class TSample>
00063 
00064 struct KdTreeNode
00065   {
00067   typedef KdTreeNode<TSample> Self;
00068 
00070   typedef typename TSample::MeasurementType MeasurementType;
00071 
00073   typedef Array<double> CentroidType;
00074 
00077   typedef typename TSample::InstanceIdentifier InstanceIdentifier;
00078 
00081   virtual bool IsTerminal() const = 0;
00082 
00088   virtual void GetParameters( unsigned int &, MeasurementType & ) const = 0;
00089 
00091   virtual Self * Left() = 0;
00092 
00094   virtual const Self * Left() const = 0;
00095 
00097   virtual Self * Right() = 0;
00098 
00100   virtual const Self * Right() const = 0;
00101 
00106   virtual unsigned int Size() const = 0;
00107 
00109   virtual void GetWeightedCentroid( CentroidType & ) = 0;
00110 
00112   virtual void GetCentroid( CentroidType & ) = 0;
00113 
00115   virtual InstanceIdentifier GetInstanceIdentifier( InstanceIdentifier ) const = 0;
00116 
00118   virtual void AddInstanceIdentifier( InstanceIdentifier ) = 0;
00119 
00121   virtual ~KdTreeNode() {}  // needed to subclasses will actually be deleted
00122 }; // end of class
00123 
00136 template<class TSample>
00137 
00138 struct KdTreeNonterminalNode:public KdTreeNode<TSample>
00139   {
00140   typedef KdTreeNode<TSample>                     Superclass;
00141   typedef typename Superclass::MeasurementType    MeasurementType;
00142   typedef typename Superclass::CentroidType       CentroidType;
00143   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00144 
00145   KdTreeNonterminalNode( unsigned int, MeasurementType, Superclass *,
00146     Superclass * );
00147 
00148   virtual ~KdTreeNonterminalNode() {}
00149 
00150   virtual bool IsTerminal() const
00151   {
00152     return false;
00153   }
00154 
00155   void GetParameters( unsigned int &, MeasurementType & ) const;
00156 
00158   Superclass * Left()
00159   {
00160     return m_Left;
00161   }
00162 
00164   Superclass * Right()
00165   {
00166     return m_Right;
00167   }
00168 
00170   const Superclass * Left() const
00171   {
00172     return m_Left;
00173   }
00174 
00176   const Superclass * Right() const
00177   {
00178     return m_Right;
00179   }
00180 
00185   unsigned int Size() const
00186   {
00187     return 0;
00188   }
00189 
00194   void GetWeightedCentroid( CentroidType & ) {}
00195 
00200   void GetCentroid( CentroidType & ) {}
00201 
00207   InstanceIdentifier GetInstanceIdentifier( InstanceIdentifier ) const
00208   {
00209     return this->m_InstanceIdentifier;
00210   }
00211 
00215   void AddInstanceIdentifier( InstanceIdentifier valueId )
00216   {
00217     this->m_InstanceIdentifier = valueId;
00218   }
00219 private:
00220 
00221   unsigned int           m_PartitionDimension;
00222   MeasurementType        m_PartitionValue;
00223   InstanceIdentifier     m_InstanceIdentifier;
00224   Superclass            *m_Left;
00225   Superclass            *m_Right;
00226 };  // end of class
00227 
00243 template<class TSample>
00244 struct KdTreeWeightedCentroidNonterminalNode:public KdTreeNode<TSample>
00245   {
00246   typedef KdTreeNode<TSample>                         Superclass;
00247   typedef typename Superclass::MeasurementType        MeasurementType;
00248   typedef typename Superclass::CentroidType           CentroidType;
00249   typedef typename Superclass::InstanceIdentifier     InstanceIdentifier;
00250   typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;
00251 
00252   KdTreeWeightedCentroidNonterminalNode( unsigned int, MeasurementType,
00253     Superclass *, Superclass *, CentroidType &, unsigned int );
00254 
00255   virtual ~KdTreeWeightedCentroidNonterminalNode() {}
00256 
00258   virtual bool IsTerminal() const
00259   {
00260     return false;
00261   }
00262 
00264   void GetParameters( unsigned int &, MeasurementType & ) const;
00265 
00267   MeasurementVectorSizeType GetMeasurementVectorSize() const
00268   {
00269     return m_MeasurementVectorSize;
00270   }
00271 
00273   Superclass * Left()
00274   {
00275     return m_Left;
00276   }
00277 
00279   Superclass * Right()
00280   {
00281     return m_Right;
00282   }
00283 
00285   const Superclass * Left() const
00286   {
00287     return m_Left;
00288   }
00289 
00291   const Superclass * Right() const
00292   {
00293     return m_Right;
00294   }
00295 
00297   unsigned int Size() const
00298   {
00299     return m_Size;
00300   }
00301 
00305   void GetWeightedCentroid(CentroidType & centroid)
00306   {
00307     centroid = m_WeightedCentroid;
00308   }
00309 
00313   void GetCentroid(CentroidType & centroid)
00314   {
00315     centroid = m_Centroid;
00316   }
00317 
00323   InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const
00324   {
00325     return this->m_InstanceIdentifier;
00326   }
00327 
00331   void AddInstanceIdentifier(InstanceIdentifier valueId)
00332   {
00333     this->m_InstanceIdentifier = valueId;
00334   }
00335 
00336 private:
00337   MeasurementVectorSizeType     m_MeasurementVectorSize;
00338   unsigned int                  m_PartitionDimension;
00339   MeasurementType               m_PartitionValue;
00340   CentroidType                  m_WeightedCentroid;
00341   CentroidType                  m_Centroid;
00342   InstanceIdentifier            m_InstanceIdentifier;
00343   unsigned int                  m_Size;
00344   Superclass                   *m_Left;
00345   Superclass                   *m_Right;
00346 };  // end of class
00347 
00360 template<class TSample>
00361 struct KdTreeTerminalNode:public KdTreeNode<TSample>
00362   {
00363   typedef KdTreeNode<TSample>                     Superclass;
00364   typedef typename Superclass::MeasurementType    MeasurementType;
00365   typedef typename Superclass::CentroidType       CentroidType;
00366   typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
00367 
00368   KdTreeTerminalNode() {}
00369 
00370   virtual ~KdTreeTerminalNode()
00371   {
00372     this->m_InstanceIdentifiers.clear();
00373   }
00374 
00376   bool IsTerminal() const
00377   {
00378     return true;
00379   }
00380 
00382   void GetParameters( unsigned int &, MeasurementType & ) const {}
00383 
00385   Superclass * Left()
00386   {
00387     return 0;
00388   }
00389 
00391   Superclass * Right()
00392   {
00393     return 0;
00394   }
00395 
00397   const Superclass * Left() const
00398   {
00399     return 0;
00400   }
00401 
00403   const Superclass * Right() const
00404   {
00405     return 0;
00406   }
00407 
00409   unsigned int Size() const
00410   {
00411     return static_cast< unsigned int >( m_InstanceIdentifiers.size() );
00412   }
00413 
00418   void GetWeightedCentroid( CentroidType & ) {}
00419 
00424   void GetCentroid( CentroidType & ) {}
00425 
00431   InstanceIdentifier GetInstanceIdentifier( InstanceIdentifier index ) const
00432   {
00433     return m_InstanceIdentifiers[index];
00434   }
00435 
00439   void AddInstanceIdentifier( InstanceIdentifier id )
00440   {
00441     m_InstanceIdentifiers.push_back( id );
00442   }
00443 
00444 private:
00445   std::vector< InstanceIdentifier > m_InstanceIdentifiers;
00446 };  // end of class
00447 
00481 template<class TSample>
00482 class ITK_EXPORT KdTree:public Object
00483 {
00484 public:
00486   typedef KdTree                     Self;
00487   typedef Object                     Superclass;
00488   typedef SmartPointer< Self >       Pointer;
00489   typedef SmartPointer< const Self > ConstPointer;
00490 
00492   itkTypeMacro(KdTree, Object);
00493 
00495   itkNewMacro(Self);
00496 
00498   typedef TSample                                 SampleType;
00499   typedef typename TSample::MeasurementVectorType MeasurementVectorType;
00500   typedef typename TSample::MeasurementType       MeasurementType;
00501   typedef typename TSample::InstanceIdentifier    InstanceIdentifier;
00502   typedef typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType;
00503 
00504   typedef unsigned int MeasurementVectorSizeType;
00505 
00508   itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
00509 
00511   typedef EuclideanDistanceMetric< MeasurementVectorType > DistanceMetricType;
00512 
00514   typedef KdTreeNode<TSample> KdTreeNodeType;
00515 
00519   typedef std::pair< InstanceIdentifier, double > NeighborType;
00520 
00521   typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
00522 
00533   class NearestNeighbors
00534   {
00535   public:
00537     NearestNeighbors() {}
00538 
00540     ~NearestNeighbors() {}
00541 
00544     void resize( unsigned int k )
00545     {
00546       m_Identifiers.clear();
00547       m_Identifiers.resize( k, NumericTraits< IdentifierType >::max() );
00548       m_Distances.clear();
00549       m_Distances.resize( k, NumericTraits<double>::max() );
00550       m_FarthestNeighborIndex = 0;
00551     }
00553 
00555     double GetLargestDistance()
00556     {
00557       return m_Distances[m_FarthestNeighborIndex];
00558     }
00559 
00562     void ReplaceFarthestNeighbor( InstanceIdentifier id, double distance )
00563     {
00564       m_Identifiers[m_FarthestNeighborIndex] = id;
00565       m_Distances[m_FarthestNeighborIndex] = distance;
00566       double farthestDistance = NumericTraits<double>::min();
00567       const unsigned int size = static_cast< unsigned int >( m_Distances.size() );
00568       for ( unsigned int i = 0; i < size; i++ )
00569         {
00570         if ( m_Distances[i] > farthestDistance )
00571           {
00572           farthestDistance = m_Distances[i];
00573           m_FarthestNeighborIndex = i;
00574           }
00575         }
00576     }
00578 
00580     const InstanceIdentifierVectorType & GetNeighbors() const
00581     {
00582       return m_Identifiers;
00583     }
00584 
00587     InstanceIdentifier GetNeighbor(unsigned int index) const
00588     {
00589       return m_Identifiers[index];
00590     }
00591 
00593     const std::vector<double> & GetDistances() const
00594     {
00595       return m_Distances;
00596     }
00597 
00598   private:
00600     unsigned int m_FarthestNeighborIndex;
00601 
00603     InstanceIdentifierVectorType m_Identifiers;
00604 
00607     std::vector<double> m_Distances;
00608   };
00609 
00612   void SetBucketSize( unsigned int );
00613 
00616   void SetSample( const TSample * );
00617 
00619   const TSample * GetSample() const
00620   {
00621     return m_Sample;
00622   }
00623 
00624   SizeValueType Size() const
00625   {
00626     return m_Sample->Size();
00627   }
00628 
00633   KdTreeNodeType * GetEmptyTerminalNode()
00634   {
00635     return m_EmptyTerminalNode;
00636   }
00637 
00640   void SetRoot(KdTreeNodeType *root)
00641   {
00642     if ( this->m_Root )
00643       {
00644       this->DeleteNode( this->m_Root );
00645       }
00646     this->m_Root = root;
00647   }
00649 
00651   KdTreeNodeType * GetRoot()
00652   {
00653     return m_Root;
00654   }
00655 
00658   const MeasurementVectorType & GetMeasurementVector( InstanceIdentifier id )
00659     const
00660   {
00661     return m_Sample->GetMeasurementVector( id );
00662   }
00663 
00666   AbsoluteFrequencyType GetFrequency(InstanceIdentifier id ) const
00667   {
00668     return m_Sample->GetFrequency( id );
00669   }
00670 
00672   DistanceMetricType * GetDistanceMetric()
00673   {
00674     return m_DistanceMetric.GetPointer();
00675   }
00676 
00678   void Search( const MeasurementVectorType &, unsigned int,
00679     InstanceIdentifierVectorType & ) const;
00680 
00682   void Search( const MeasurementVectorType &, double,
00683     InstanceIdentifierVectorType & ) const;
00684 
00690   bool BallWithinBounds( const MeasurementVectorType &,
00691     MeasurementVectorType &, MeasurementVectorType &, double ) const;
00692 
00696   bool BoundsOverlapBall( const MeasurementVectorType &,
00697     MeasurementVectorType &, MeasurementVectorType &, double) const;
00698 
00700   void DeleteNode( KdTreeNodeType * );
00701 
00703   void PrintTree( std::ostream & ) const;
00704 
00706   void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
00707     std::ostream & os = std::cout ) const;
00708 
00711   void PlotTree( std::ostream & os ) const;
00712 
00714   void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;
00715 
00716   typedef typename TSample::Iterator      Iterator;
00717   typedef typename TSample::ConstIterator ConstIterator;
00718 
00719 protected:
00721   KdTree();
00722 
00724   virtual ~KdTree();
00725 
00726   void PrintSelf( std::ostream & os, Indent indent ) const;
00727 
00729   int NearestNeighborSearchLoop( const KdTreeNodeType *,
00730     const MeasurementVectorType &, MeasurementVectorType &,
00731     MeasurementVectorType &, NearestNeighbors & ) const;
00732 
00734   int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
00735     double, MeasurementVectorType &, MeasurementVectorType &,
00736     InstanceIdentifierVectorType & ) const;
00737 
00738 private:
00739   KdTree( const Self & );         //purposely not implemented
00740   void operator=( const Self & ); //purposely not implemented
00741 
00743   const TSample *m_Sample;
00744 
00746   int m_BucketSize;
00747 
00749   KdTreeNodeType *m_Root;
00750 
00752   KdTreeNodeType *m_EmptyTerminalNode;
00753 
00755   typename DistanceMetricType::Pointer m_DistanceMetric;
00756 
00758   MeasurementVectorSizeType m_MeasurementVectorSize;
00759 };  // end of class
00760 } // end of namespace Statistics
00761 } // end of namespace itk
00762 
00763 #ifndef ITK_MANUAL_INSTANTIATION
00764 #include "itkKdTree.hxx"
00765 #endif
00766 
00767 #endif
00768