Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
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 ¢roid) = 0;
00106
00108 virtual void GetCentroid(CentroidType ¢roid) = 0;
00109
00111 virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0;
00112
00114 virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0;
00115
00117 virtual ~KdTreeNode() {};
00118 };
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
00182 }
00183
00184 void GetCentroid( CentroidType & )
00185 {
00186
00187 }
00188
00189
00190
00191
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 };
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 ¢roid,
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 ¢roid)
00278 {
00279 centroid = m_WeightedCentroid;
00280 }
00281
00282 void GetCentroid(CentroidType ¢roid)
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 };
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
00372 }
00373
00374 void GetCentroid(CentroidType &)
00375 {
00376
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 };
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&);
00720 void operator=(const Self&);
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 };
00765
00766 }
00767 }
00768
00769 #ifndef ITK_MANUAL_INSTANTIATION
00770 #include "itkKdTree.txx"
00771 #endif
00772
00773 #endif
00774