ITK
4.1.0
Insight Segmentation and Registration Toolkit
|
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