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: 2003/09/10 14:29:46 $ 00007 Version: $Revision: 1.20 $ 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 00056 template< class TSample > 00057 struct KdTreeNode 00058 { 00060 typedef KdTreeNode< TSample> Self ; 00061 00063 typedef typename TSample::MeasurementType MeasurementType ; 00064 00066 itkStaticConstMacro(MeasurementVectorSize, unsigned int, 00067 TSample::MeasurementVectorSize) ; 00068 00070 typedef FixedArray< double, 00071 itkGetStaticConstMacro(MeasurementVectorSize) > CentroidType ; 00072 00075 typedef typename TSample::InstanceIdentifier InstanceIdentifier ; 00076 00079 virtual bool IsTerminal() = 0 ; 00080 00086 virtual void GetParameters(unsigned int &partitionDimension, 00087 MeasurementType &partitionValue) = 0 ; 00088 00090 virtual Self* Left() = 0 ; 00091 00093 virtual Self* Right() = 0 ; 00094 00097 virtual unsigned int Size() = 0 ; 00098 00100 virtual void GetWeightedCentroid(CentroidType &centroid) = 0 ; 00101 00103 virtual void GetCentroid(CentroidType &centroid) = 0 ; 00104 00106 virtual InstanceIdentifier GetInstanceIdentifier(size_t index) = 0 ; 00107 00109 virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0 ; 00110 00112 virtual ~KdTreeNode() {}; // needed to subclasses will actually be deleted 00113 } ; // end of class 00114 00126 template< class TSample > 00127 struct KdTreeNonterminalNode: public KdTreeNode< TSample > 00128 { 00129 typedef KdTreeNode< TSample > Superclass ; 00130 typedef typename Superclass::MeasurementType MeasurementType ; 00131 typedef typename Superclass::CentroidType CentroidType ; 00132 typedef typename Superclass::InstanceIdentifier InstanceIdentifier ; 00133 00134 KdTreeNonterminalNode(unsigned int partitionDimension, 00135 MeasurementType partitionValue, 00136 Superclass* left, 00137 Superclass* right) ; 00138 00139 virtual ~KdTreeNonterminalNode() {} 00140 00141 virtual bool IsTerminal() 00142 { return false ; } 00143 00144 void GetParameters(unsigned int &partitionDimension, 00145 MeasurementType &partitionValue) ; 00146 00147 Superclass* Left() 00148 { return m_Left ; } 00149 00150 Superclass* Right() 00151 { return m_Right ; } 00152 00153 unsigned int Size() 00154 { return 0 ; } 00155 00156 void GetWeightedCentroid(CentroidType &) 00157 { /* do nothing */ } 00158 00159 void GetCentroid(CentroidType &) 00160 { /* do nothing */ } 00161 00162 InstanceIdentifier GetInstanceIdentifier(size_t) 00163 { return 0 ; } 00164 00165 void AddInstanceIdentifier(InstanceIdentifier) {} 00166 00167 private: 00168 unsigned int m_PartitionDimension ; 00169 MeasurementType m_PartitionValue ; 00170 Superclass* m_Left ; 00171 Superclass* m_Right ; 00172 } ; // end of class 00173 00188 template< class TSample > 00189 struct KdTreeWeightedCentroidNonterminalNode: public KdTreeNode< TSample > 00190 { 00191 typedef KdTreeNode< TSample > Superclass ; 00192 typedef typename Superclass::MeasurementType MeasurementType ; 00193 typedef typename Superclass::CentroidType CentroidType ; 00194 typedef typename Superclass::InstanceIdentifier InstanceIdentifier ; 00195 00196 KdTreeWeightedCentroidNonterminalNode(unsigned int partitionDimension, 00197 MeasurementType partitionValue, 00198 Superclass* left, 00199 Superclass* right, 00200 CentroidType &centroid, 00201 unsigned int size) ; 00202 virtual ~KdTreeWeightedCentroidNonterminalNode() {} 00203 00204 virtual bool IsTerminal() 00205 { return false ; } 00206 00207 void GetParameters(unsigned int &partitionDimension, 00208 MeasurementType &partitionValue) ; 00209 00210 Superclass* Left() 00211 { return m_Left ; } 00212 00213 Superclass* Right() 00214 { return m_Right ; } 00215 00216 unsigned int Size() 00217 { return m_Size ; } 00218 00219 void GetWeightedCentroid(CentroidType &centroid) 00220 { centroid = m_WeightedCentroid ; } 00221 00222 void GetCentroid(CentroidType &centroid) 00223 { centroid = m_Centroid ; } 00224 00225 InstanceIdentifier GetInstanceIdentifier(size_t) 00226 { return 0 ; } 00227 00228 void AddInstanceIdentifier(InstanceIdentifier) {} 00229 00230 private: 00231 unsigned int m_PartitionDimension ; 00232 MeasurementType m_PartitionValue ; 00233 CentroidType m_WeightedCentroid ; 00234 CentroidType m_Centroid ; 00235 unsigned int m_Size ; 00236 Superclass* m_Left ; 00237 Superclass* m_Right ; 00238 } ; // end of class 00239 00240 00252 template< class TSample > 00253 struct KdTreeTerminalNode: public KdTreeNode< TSample > 00254 { 00255 typedef KdTreeNode< TSample > Superclass ; 00256 typedef typename Superclass::MeasurementType MeasurementType ; 00257 typedef typename Superclass::CentroidType CentroidType ; 00258 typedef typename Superclass::InstanceIdentifier InstanceIdentifier ; 00259 00260 KdTreeTerminalNode() {} 00261 00262 virtual ~KdTreeTerminalNode() {} 00263 00264 bool IsTerminal() 00265 { return true ; } 00266 00267 void GetParameters(unsigned int &, 00268 MeasurementType &) {} 00269 00270 Superclass* Left() 00271 { return 0 ; } 00272 00273 Superclass* Right() 00274 { return 0 ; } 00275 00276 unsigned int Size() 00277 { return static_cast<unsigned int>( m_InstanceIdentifiers.size() ); } 00278 00279 void GetWeightedCentroid(CentroidType &) 00280 { /* do nothing */ } 00281 00282 void GetCentroid(CentroidType &) 00283 { /* do nothing */ } 00284 00285 InstanceIdentifier GetInstanceIdentifier(size_t index) 00286 { return m_InstanceIdentifiers[index] ; } 00287 00288 void AddInstanceIdentifier(InstanceIdentifier id) 00289 { m_InstanceIdentifiers.push_back(id) ;} 00290 00291 private: 00292 std::vector< InstanceIdentifier > m_InstanceIdentifiers ; 00293 } ; // end of class 00294 00321 template < class TSample > 00322 class ITK_EXPORT KdTree : public Object 00323 { 00324 public: 00326 typedef KdTree Self ; 00327 typedef Object Superclass ; 00328 typedef SmartPointer<Self> Pointer; 00329 00331 itkTypeMacro(KdTree, Object); 00332 00334 itkNewMacro(Self) ; 00335 00337 typedef TSample SampleType ; 00338 typedef typename TSample::MeasurementVectorType MeasurementVectorType ; 00339 typedef typename TSample::MeasurementType MeasurementType ; 00340 typedef typename TSample::InstanceIdentifier InstanceIdentifier ; 00341 typedef typename TSample::FrequencyType FrequencyType ; 00342 00344 itkStaticConstMacro(MeasurementVectorSize, unsigned int, 00345 TSample::MeasurementVectorSize) ; 00346 00348 typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType ; 00349 00351 typedef KdTreeNode< TSample > KdTreeNodeType ; 00352 00356 typedef std::pair< InstanceIdentifier, double > NeighborType ; 00357 00358 typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType ; 00359 00369 class NearestNeighbors 00370 { 00371 public: 00373 NearestNeighbors() {} 00374 00376 ~NearestNeighbors() {} 00377 00380 void resize(unsigned int k) 00381 { 00382 m_Identifiers.clear() ; 00383 m_Identifiers.resize(k, NumericTraits< unsigned long >::max()) ; 00384 m_Distances.clear() ; 00385 m_Distances.resize(k, NumericTraits< double >::max()) ; 00386 m_FarthestNeighborIndex = 0 ; 00387 } 00388 00390 double GetLargestDistance() 00391 { return m_Distances[m_FarthestNeighborIndex] ; } 00392 00395 void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance) 00396 { 00397 m_Identifiers[m_FarthestNeighborIndex] = id ; 00398 m_Distances[m_FarthestNeighborIndex] = distance ; 00399 double farthestDistance = NumericTraits< double >::min() ; 00400 const unsigned int size = static_cast<unsigned int>( m_Distances.size() ); 00401 for ( unsigned int i = 0 ; i < size; i++ ) 00402 { 00403 if ( m_Distances[i] > farthestDistance ) 00404 { 00405 farthestDistance = m_Distances[i] ; 00406 m_FarthestNeighborIndex = i ; 00407 } 00408 } 00409 } 00410 00412 InstanceIdentifierVectorType GetNeighbors() 00413 { return m_Identifiers ; } 00414 00417 InstanceIdentifier GetNeighbor(unsigned int index) 00418 { return m_Identifiers[index] ; } 00419 00421 std::vector< double >& GetDistances() 00422 { return m_Distances ; } 00423 00424 private: 00426 unsigned int m_FarthestNeighborIndex ; 00427 00429 InstanceIdentifierVectorType m_Identifiers ; 00430 00433 std::vector< double > m_Distances ; 00434 } ; 00435 00438 void SetBucketSize(unsigned int size) ; 00439 00442 void SetSample(TSample* sample) ; 00443 00445 TSample* GetSample() 00446 { return m_Sample ; } 00447 00448 unsigned long Size() 00449 { return m_Sample->Size() ; } 00450 00455 KdTreeNodeType* GetEmptyTerminalNode() 00456 { return m_EmptyTerminalNode ; } 00457 00460 void SetRoot(KdTreeNodeType* root) 00461 { m_Root = root ; } 00462 00464 KdTreeNodeType* GetRoot() 00465 { return m_Root ; } 00466 00469 MeasurementVectorType GetMeasurementVector(InstanceIdentifier id) 00470 { return m_Sample->GetMeasurementVector(id) ; } 00471 00474 FrequencyType GetFrequency(InstanceIdentifier id) 00475 { return m_Sample->GetFrequency( id ) ; } 00476 00478 DistanceMetricType* GetDistanceMetric() 00479 { return m_DistanceMetric.GetPointer() ; } 00480 00482 void Search(MeasurementVectorType &query, 00483 unsigned int k, 00484 InstanceIdentifierVectorType& result) ; 00485 00487 void Search(MeasurementVectorType &query, 00488 double radius, 00489 InstanceIdentifierVectorType& result) ; 00490 00493 int GetNumberOfVisits() 00494 { return m_NumberOfVisits ; } 00495 00501 bool BallWithinBounds(MeasurementVectorType &query, 00502 MeasurementVectorType &lowerBound, 00503 MeasurementVectorType &upperBound, 00504 double radius) ; 00505 00509 bool BoundsOverlapBall(MeasurementVectorType &query, 00510 MeasurementVectorType &lowerBound, 00511 MeasurementVectorType &upperBound, 00512 double radius) ; 00513 00515 void DeleteNode(KdTreeNodeType *node) ; 00516 00518 void PrintTree(KdTreeNodeType *node, int level, 00519 unsigned int activeDimension) ; 00520 00521 typedef typename TSample::Iterator Iterator ; 00522 00523 Iterator Begin() 00524 { 00525 typename TSample::Iterator iter = m_Sample->Begin() ; 00526 return iter; 00527 } 00528 00529 Iterator End() 00530 { 00531 Iterator iter = m_Sample->End() ; 00532 return iter; 00533 } 00534 00535 protected: 00537 KdTree() ; 00538 00540 virtual ~KdTree() ; 00541 00542 void PrintSelf(std::ostream& os, Indent indent) const ; 00543 00545 int NearestNeighborSearchLoop(KdTreeNodeType* node, 00546 MeasurementVectorType &query, 00547 MeasurementVectorType &lowerBound, 00548 MeasurementVectorType &upperBound) ; 00549 00551 int SearchLoop(KdTreeNodeType* node, MeasurementVectorType &query, 00552 MeasurementVectorType &lowerBound, 00553 MeasurementVectorType &upperBound) ; 00554 private: 00555 KdTree(const Self&) ; //purposely not implemented 00556 void operator=(const Self&) ; //purposely not implemented 00557 00559 TSample* m_Sample ; 00560 00562 int m_BucketSize ; 00563 00565 KdTreeNodeType* m_Root ; 00566 00568 KdTreeNodeType* m_EmptyTerminalNode ; 00569 00571 typename DistanceMetricType::Pointer m_DistanceMetric ; 00572 00573 bool m_IsNearestNeighborSearch ; 00574 00575 double m_SearchRadius ; 00576 00577 InstanceIdentifierVectorType m_Neighbors ; 00578 00580 NearestNeighbors m_NearestNeighbors ; 00581 00583 MeasurementVectorType m_LowerBound ; 00584 00586 MeasurementVectorType m_UpperBound ; 00587 00589 int m_NumberOfVisits ; 00590 00592 bool m_StopSearch ; 00593 00595 NeighborType m_TempNeighbor ; 00596 } ; // end of class 00597 00598 } // end of namespace Statistics 00599 } // end of namespace itk 00600 00601 #ifndef ITK_MANUAL_INSTANTIATION 00602 #include "itkKdTree.txx" 00603 #endif 00604 00605 #endif 00606 00607 00608

Generated at Sat Mar 31 02:23:23 2007 for ITK by doxygen 1.3.8 written by Dimitri van Heesch, © 1997-2000