ITK  4.6.0
Insight Segmentation and Registration Toolkit
itkKdTree.h
Go to the documentation of this file.
1 /*=========================================================================
2  *
3  * Copyright Insight Software Consortium
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef __itkKdTree_h
19 #define __itkKdTree_h
20 
21 #include <queue>
22 #include <vector>
23 
24 #include "itkPoint.h"
25 #include "itkSize.h"
26 #include "itkObject.h"
27 #include "itkArray.h"
28 
29 #include "itkSubsample.h"
30 
32 
33 namespace itk
34 {
35 namespace Statistics
36 {
62 template<typename TSample>
63 
64 struct KdTreeNode
65  {
68 
70  typedef typename TSample::MeasurementType MeasurementType;
71 
74 
77  typedef typename TSample::InstanceIdentifier InstanceIdentifier;
78 
81  virtual bool IsTerminal() const = 0;
82 
88  virtual void GetParameters( unsigned int &, MeasurementType & ) const = 0;
89 
91  virtual Self * Left() = 0;
92 
94  virtual const Self * Left() const = 0;
95 
97  virtual Self * Right() = 0;
98 
100  virtual const Self * Right() const = 0;
101 
106  virtual unsigned int Size() const = 0;
107 
109  virtual void GetWeightedCentroid( CentroidType & ) = 0;
110 
112  virtual void GetCentroid( CentroidType & ) = 0;
113 
116 
118  virtual void AddInstanceIdentifier( InstanceIdentifier ) = 0;
119 
121  virtual ~KdTreeNode() {} // needed to subclasses will actually be deleted
122 }; // end of class
123 
136 template<typename TSample>
137 
138 struct KdTreeNonterminalNode:public KdTreeNode<TSample>
139  {
144 
146  Superclass * );
147 
149 
150  virtual bool IsTerminal() const
151  {
152  return false;
153  }
154 
155  void GetParameters( unsigned int &, MeasurementType & ) const;
156 
159  {
160  return m_Left;
161  }
162 
165  {
166  return m_Right;
167  }
168 
170  const Superclass * Left() const
171  {
172  return m_Left;
173  }
174 
176  const Superclass * Right() const
177  {
178  return m_Right;
179  }
180 
185  unsigned int Size() const
186  {
187  return 0;
188  }
189 
195 
201 
208  {
209  return this->m_InstanceIdentifier;
210  }
211 
216  {
217  this->m_InstanceIdentifier = valueId;
218  }
219 
220 private:
221 
222  unsigned int m_PartitionDimension;
227 }; // end of class
228 
244 template<typename TSample>
246  {
251  typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;
252 
254  Superclass *, Superclass *, CentroidType &, unsigned int );
255 
257 
259  virtual bool IsTerminal() const
260  {
261  return false;
262  }
263 
265  void GetParameters( unsigned int &, MeasurementType & ) const;
266 
269  {
271  }
272 
275  {
276  return m_Left;
277  }
278 
281  {
282  return m_Right;
283  }
284 
286  const Superclass * Left() const
287  {
288  return m_Left;
289  }
290 
292  const Superclass * Right() const
293  {
294  return m_Right;
295  }
296 
298  unsigned int Size() const
299  {
300  return m_Size;
301  }
302 
307  {
308  centroid = m_WeightedCentroid;
309  }
310 
314  void GetCentroid(CentroidType & centroid)
315  {
316  centroid = m_Centroid;
317  }
318 
325  {
326  return this->m_InstanceIdentifier;
327  }
328 
333  {
334  this->m_InstanceIdentifier = valueId;
335  }
336 
337 private:
339  unsigned int m_PartitionDimension;
344  unsigned int m_Size;
347 }; // end of class
348 
361 template<typename TSample>
362 struct KdTreeTerminalNode:public KdTreeNode<TSample>
363  {
368 
370 
372  {
373  this->m_InstanceIdentifiers.clear();
374  }
375 
377  bool IsTerminal() const
378  {
379  return true;
380  }
381 
383  void GetParameters( unsigned int &, MeasurementType & ) const {}
384 
387  {
388  return ITK_NULLPTR;
389  }
390 
393  {
394  return ITK_NULLPTR;
395  }
396 
398  const Superclass * Left() const
399  {
400  return ITK_NULLPTR;
401  }
402 
404  const Superclass * Right() const
405  {
406  return ITK_NULLPTR;
407  }
408 
410  unsigned int Size() const
411  {
412  return static_cast< unsigned int >( m_InstanceIdentifiers.size() );
413  }
414 
420 
426 
433  {
434  return m_InstanceIdentifiers[index];
435  }
436 
441  {
442  m_InstanceIdentifiers.push_back( id );
443  }
444 
445 private:
446  std::vector< InstanceIdentifier > m_InstanceIdentifiers;
447 }; // end of class
448 
482 template<typename TSample>
483 class KdTree:public Object
484 {
485 public:
487  typedef KdTree Self;
491 
493  itkTypeMacro(KdTree, Object);
494 
496  itkNewMacro(Self);
497 
499  typedef TSample SampleType;
500  typedef typename TSample::MeasurementVectorType MeasurementVectorType;
501  typedef typename TSample::MeasurementType MeasurementType;
502  typedef typename TSample::InstanceIdentifier InstanceIdentifier;
503  typedef typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType;
504 
505  typedef unsigned int MeasurementVectorSizeType;
506 
509  itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
510 
513 
516 
520  typedef std::pair< InstanceIdentifier, double > NeighborType;
521 
522  typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
523 
535  {
536  public:
539 
542 
545  void resize( unsigned int k )
546  {
547  m_Identifiers.clear();
549  m_Distances.clear();
552  }
554 
557  {
559  }
560 
563  void ReplaceFarthestNeighbor( InstanceIdentifier id, double distance )
564  {
567  double farthestDistance = NumericTraits<double>::min();
568  const unsigned int size = static_cast< unsigned int >( m_Distances.size() );
569  for ( unsigned int i = 0; i < size; i++ )
570  {
571  if ( m_Distances[i] > farthestDistance )
572  {
573  farthestDistance = m_Distances[i];
575  }
576  }
577  }
579 
582  {
583  return m_Identifiers;
584  }
585 
588  InstanceIdentifier GetNeighbor(unsigned int index) const
589  {
590  return m_Identifiers[index];
591  }
592 
594  const std::vector<double> & GetDistances() const
595  {
596  return m_Distances;
597  }
598 
599  private:
602 
605 
608  std::vector<double> m_Distances;
609  };
610 
613  void SetBucketSize( unsigned int );
614 
617  void SetSample( const TSample * );
618 
620  const TSample * GetSample() const
621  {
622  return m_Sample;
623  }
624 
626  {
627  return m_Sample->Size();
628  }
629 
635  {
636  return m_EmptyTerminalNode;
637  }
638 
642  {
643  if ( this->m_Root )
644  {
645  this->DeleteNode( this->m_Root );
646  }
647  this->m_Root = root;
648  }
650 
653  {
654  return m_Root;
655  }
656 
660  const
661  {
662  return m_Sample->GetMeasurementVector( id );
663  }
664 
668  {
669  return m_Sample->GetFrequency( id );
670  }
671 
674  {
675  return m_DistanceMetric.GetPointer();
676  }
677 
679  void Search( const MeasurementVectorType &, unsigned int,
681 
685  void Search( const MeasurementVectorType &, unsigned int,
686  InstanceIdentifierVectorType &, std::vector<double> & ) const;
687 
689  void Search( const MeasurementVectorType &, double,
691 
698  MeasurementVectorType &, MeasurementVectorType &, double ) const;
699 
704  MeasurementVectorType &, MeasurementVectorType &, double) const;
705 
707  void DeleteNode( KdTreeNodeType * );
708 
710  void PrintTree( std::ostream & ) const;
711 
713  void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
714  std::ostream & os = std::cout ) const;
715 
718  void PlotTree( std::ostream & os ) const;
719 
721  void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;
722 
723  typedef typename TSample::Iterator Iterator;
724  typedef typename TSample::ConstIterator ConstIterator;
725 
726 protected:
728  KdTree();
729 
731  virtual ~KdTree();
732 
733  virtual void PrintSelf( std::ostream & os, Indent indent ) const ITK_OVERRIDE;
734 
739 
741  int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
744 
745 private:
746  KdTree( const Self & ); //purposely not implemented
747  void operator=( const Self & ); //purposely not implemented
748 
750  const TSample *m_Sample;
751 
754 
757 
760 
763 
766 }; // end of class
767 } // end of namespace Statistics
768 } // end of namespace itk
769 
770 #ifndef ITK_MANUAL_INSTANTIATION
771 #include "itkKdTree.hxx"
772 #endif
773 
774 #endif
void GetWeightedCentroid(CentroidType &)
Definition: itkKdTree.h:419
const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
Definition: itkKdTree.h:659
void GetCentroid(CentroidType &)
Definition: itkKdTree.h:425
KdTreeNode< TSample > Self
Definition: itkKdTree.h:67
void DeleteNode(KdTreeNodeType *)
TSample::ConstIterator ConstIterator
Definition: itkKdTree.h:724
Light weight base class for most itk classes.
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier index) const
Definition: itkKdTree.h:432
KdTreeNodeType * GetEmptyTerminalNode()
Definition: itkKdTree.h:634
KdTreeNodeType * m_Root
Definition: itkKdTree.h:756
Superclass::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:250
KdTreeNodeType * GetRoot()
Definition: itkKdTree.h:652
This class defines the interface of its derived classes.
Definition: itkKdTree.h:64
This is a subclass of the KdTreeNode.
Definition: itkKdTree.h:138
const Superclass * Left() const
Definition: itkKdTree.h:170
void AddInstanceIdentifier(InstanceIdentifier valueId)
Definition: itkKdTree.h:215
const Superclass * Right() const
Definition: itkKdTree.h:176
TSample::MeasurementVectorType MeasurementVectorType
Definition: itkKdTree.h:500
void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
Definition: itkKdTree.h:563
TSample::AbsoluteFrequencyType AbsoluteFrequencyType
Definition: itkKdTree.h:503
virtual void GetWeightedCentroid(CentroidType &)=0
virtual InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const =0
void GetWeightedCentroid(CentroidType &)
Definition: itkKdTree.h:194
TSample::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:77
void GetWeightedCentroid(CentroidType &centroid)
Definition: itkKdTree.h:306
void operator=(const Self &)
KdTreeWeightedCentroidNonterminalNode(unsigned int, MeasurementType, Superclass *, Superclass *, CentroidType &, unsigned int)
TSample::MeasurementType MeasurementType
Definition: itkKdTree.h:501
SizeValueType Size() const
Definition: itkKdTree.h:625
EuclideanDistanceMetric< MeasurementVectorType > DistanceMetricType
Definition: itkKdTree.h:509
void GetParameters(unsigned int &, MeasurementType &) const
ObjectType * GetPointer() const
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const
Definition: itkKdTree.h:324
bool BallWithinBounds(const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, double) const
unsigned long SizeValueType
Definition: itkIntTypes.h:143
const Superclass * Left() const
Definition: itkKdTree.h:398
Superclass::CentroidType CentroidType
Definition: itkKdTree.h:142
void PrintTree(std::ostream &) const
static T min(const T &)
KdTreeNode< TSample > KdTreeNodeType
Definition: itkKdTree.h:515
void GetCentroid(CentroidType &)
Definition: itkKdTree.h:200
InstanceIdentifier m_InstanceIdentifier
Definition: itkKdTree.h:224
virtual bool IsTerminal() const
Definition: itkKdTree.h:150
data structure for storing k-nearest neighbor search result (k number of Neighbors) ...
Definition: itkKdTree.h:534
This class is the node that doesn&#39;t have any child node. The IsTerminal method returns true for this ...
Definition: itkKdTree.h:362
TSample::Iterator Iterator
Definition: itkKdTree.h:723
unsigned int Size() const
Definition: itkKdTree.h:410
const InstanceIdentifierVectorType & GetNeighbors() const
Definition: itkKdTree.h:581
const TSample * m_Sample
Definition: itkKdTree.h:750
int NearestNeighborSearchLoop(const KdTreeNodeType *, const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, NearestNeighbors &) const
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const
Definition: itkKdTree.h:207
DistanceMetricType * GetDistanceMetric()
Definition: itkKdTree.h:673
void GetParameters(unsigned int &, MeasurementType &) const
void Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &) const
void SetRoot(KdTreeNodeType *root)
Definition: itkKdTree.h:641
void AddInstanceIdentifier(InstanceIdentifier id)
Definition: itkKdTree.h:440
virtual unsigned int Size() const =0
This is a subclass of the KdTreeNode.
Definition: itkKdTree.h:245
void PlotTree(std::ostream &os) const
Superclass::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:367
KdTreeNodeType * m_EmptyTerminalNode
Definition: itkKdTree.h:759
MeasurementVectorSizeType GetMeasurementVectorSize() const
Definition: itkKdTree.h:268
AbsoluteFrequencyType GetFrequency(InstanceIdentifier id) const
Definition: itkKdTree.h:667
virtual void GetCentroid(CentroidType &)=0
virtual void GetParameters(unsigned int &, MeasurementType &) const =0
DistanceMetricType::Pointer m_DistanceMetric
Definition: itkKdTree.h:762
TSample::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:502
const Superclass * Right() const
Definition: itkKdTree.h:404
Array< double > CentroidType
Definition: itkKdTree.h:73
std::pair< InstanceIdentifier, double > NeighborType
Definition: itkKdTree.h:520
std::vector< InstanceIdentifier > InstanceIdentifierVectorType
Definition: itkKdTree.h:522
KdTreeNonterminalNode(unsigned int, MeasurementType, Superclass *, Superclass *)
Superclass::MeasurementType MeasurementType
Definition: itkKdTree.h:365
virtual void PrintSelf(std::ostream &os, Indent indent) const ITK_OVERRIDE
InstanceIdentifier GetNeighbor(unsigned int index) const
Definition: itkKdTree.h:588
Superclass::CentroidType CentroidType
Definition: itkKdTree.h:366
unsigned int MeasurementVectorSizeType
Definition: itkKdTree.h:505
std::vector< InstanceIdentifier > m_InstanceIdentifiers
Definition: itkKdTree.h:446
void SetSample(const TSample *)
KdTreeNode< TSample > Superclass
Definition: itkKdTree.h:364
TSample::MeasurementVectorSizeType MeasurementVectorSizeType
Definition: itkKdTree.h:251
virtual Self * Left()=0
void GetParameters(unsigned int &, MeasurementType &) const
Definition: itkKdTree.h:383
Control indentation during Print() invocation.
Definition: itkIndent.h:49
KdTreeNode< TSample > Superclass
Definition: itkKdTree.h:140
InstanceIdentifierVectorType m_Identifiers
Definition: itkKdTree.h:604
Define additional traits for native types such as int or float.
virtual void AddInstanceIdentifier(InstanceIdentifier)=0
void AddInstanceIdentifier(InstanceIdentifier valueId)
Definition: itkKdTree.h:332
MeasurementVectorSizeType m_MeasurementVectorSize
Definition: itkKdTree.h:765
virtual Self * Right()=0
const TSample * GetSample() const
Definition: itkKdTree.h:620
Base class for most ITK classes.
Definition: itkObject.h:57
SmartPointer< Self > Pointer
Definition: itkKdTree.h:489
const std::vector< double > & GetDistances() const
Definition: itkKdTree.h:594
int SearchLoop(const KdTreeNodeType *, const MeasurementVectorType &, double, MeasurementVectorType &, MeasurementVectorType &, InstanceIdentifierVectorType &) const
virtual bool IsTerminal() const =0
Superclass::MeasurementType MeasurementType
Definition: itkKdTree.h:141
bool BoundsOverlapBall(const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, double) const
This class provides methods for k-nearest neighbor search and related data structures for a k-d tree...
Definition: itkKdTree.h:483
Superclass::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:143
SmartPointer< const Self > ConstPointer
Definition: itkKdTree.h:490
TSample::MeasurementType MeasurementType
Definition: itkKdTree.h:70
void SetBucketSize(unsigned int)