ITK  4.2.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<class 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<class 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 private:
220 
221  unsigned int m_PartitionDimension;
226 }; // end of class
227 
243 template<class TSample>
245  {
250  typedef typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType;
251 
253  Superclass *, Superclass *, CentroidType &, unsigned int );
254 
256 
258  virtual bool IsTerminal() const
259  {
260  return false;
261  }
262 
264  void GetParameters( unsigned int &, MeasurementType & ) const;
265 
268  {
270  }
271 
274  {
275  return m_Left;
276  }
277 
280  {
281  return m_Right;
282  }
283 
285  const Superclass * Left() const
286  {
287  return m_Left;
288  }
289 
291  const Superclass * Right() const
292  {
293  return m_Right;
294  }
295 
297  unsigned int Size() const
298  {
299  return m_Size;
300  }
301 
306  {
307  centroid = m_WeightedCentroid;
308  }
309 
313  void GetCentroid(CentroidType & centroid)
314  {
315  centroid = m_Centroid;
316  }
317 
324  {
325  return this->m_InstanceIdentifier;
326  }
327 
332  {
333  this->m_InstanceIdentifier = valueId;
334  }
335 
336 private:
338  unsigned int m_PartitionDimension;
343  unsigned int m_Size;
346 }; // end of class
347 
360 template<class TSample>
361 struct KdTreeTerminalNode:public KdTreeNode<TSample>
362  {
367 
369 
371  {
372  this->m_InstanceIdentifiers.clear();
373  }
374 
376  bool IsTerminal() const
377  {
378  return true;
379  }
380 
382  void GetParameters( unsigned int &, MeasurementType & ) const {}
383 
386  {
387  return 0;
388  }
389 
392  {
393  return 0;
394  }
395 
397  const Superclass * Left() const
398  {
399  return 0;
400  }
401 
403  const Superclass * Right() const
404  {
405  return 0;
406  }
407 
409  unsigned int Size() const
410  {
411  return static_cast< unsigned int >( m_InstanceIdentifiers.size() );
412  }
413 
419 
425 
432  {
433  return m_InstanceIdentifiers[index];
434  }
435 
440  {
441  m_InstanceIdentifiers.push_back( id );
442  }
443 
444 private:
445  std::vector< InstanceIdentifier > m_InstanceIdentifiers;
446 }; // end of class
447 
481 template<class TSample>
482 class ITK_EXPORT KdTree:public Object
483 {
484 public:
486  typedef KdTree Self;
490 
492  itkTypeMacro(KdTree, Object);
493 
495  itkNewMacro(Self);
496 
498  typedef TSample SampleType;
499  typedef typename TSample::MeasurementVectorType MeasurementVectorType;
500  typedef typename TSample::MeasurementType MeasurementType;
501  typedef typename TSample::InstanceIdentifier InstanceIdentifier;
502  typedef typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType;
503 
504  typedef unsigned int MeasurementVectorSizeType;
505 
508  itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
509 
512 
515 
519  typedef std::pair< InstanceIdentifier, double > NeighborType;
520 
521  typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
522 
534  {
535  public:
538 
541 
544  void resize( unsigned int k )
545  {
546  m_Identifiers.clear();
547  m_Identifiers.resize( k, NumericTraits< IdentifierType >::max() );
548  m_Distances.clear();
549  m_Distances.resize( k, NumericTraits<double>::max() );
550  m_FarthestNeighborIndex = 0;
551  }
553 
555  double GetLargestDistance()
556  {
557  return m_Distances[m_FarthestNeighborIndex];
558  }
559 
562  void ReplaceFarthestNeighbor( InstanceIdentifier id, double distance )
563  {
564  m_Identifiers[m_FarthestNeighborIndex] = id;
565  m_Distances[m_FarthestNeighborIndex] = distance;
566  double farthestDistance = NumericTraits<double>::min();
567  const unsigned int size = static_cast< unsigned int >( m_Distances.size() );
568  for ( unsigned int i = 0; i < size; i++ )
569  {
570  if ( m_Distances[i] > farthestDistance )
571  {
572  farthestDistance = m_Distances[i];
573  m_FarthestNeighborIndex = i;
574  }
575  }
576  }
578 
580  const InstanceIdentifierVectorType & GetNeighbors() const
581  {
582  return m_Identifiers;
583  }
584 
587  InstanceIdentifier GetNeighbor(unsigned int index) const
588  {
589  return m_Identifiers[index];
590  }
591 
593  const std::vector<double> & GetDistances() const
594  {
595  return m_Distances;
596  }
597 
598  private:
601 
604 
607  std::vector<double> m_Distances;
608  };
609 
612  void SetBucketSize( unsigned int );
613 
616  void SetSample( const TSample * );
617 
619  const TSample * GetSample() const
620  {
621  return m_Sample;
622  }
623 
625  {
626  return m_Sample->Size();
627  }
628 
633  KdTreeNodeType * GetEmptyTerminalNode()
634  {
635  return m_EmptyTerminalNode;
636  }
637 
640  void SetRoot(KdTreeNodeType *root)
641  {
642  if ( this->m_Root )
643  {
644  this->DeleteNode( this->m_Root );
645  }
646  this->m_Root = root;
647  }
649 
651  KdTreeNodeType * GetRoot()
652  {
653  return m_Root;
654  }
655 
658  const MeasurementVectorType & GetMeasurementVector( InstanceIdentifier id )
659  const
660  {
661  return m_Sample->GetMeasurementVector( id );
662  }
663 
667  {
668  return m_Sample->GetFrequency( id );
669  }
670 
672  DistanceMetricType * GetDistanceMetric()
673  {
674  return m_DistanceMetric.GetPointer();
675  }
676 
678  void Search( const MeasurementVectorType &, unsigned int,
679  InstanceIdentifierVectorType & ) const;
680 
682  void Search( const MeasurementVectorType &, double,
683  InstanceIdentifierVectorType & ) const;
684 
690  bool BallWithinBounds( const MeasurementVectorType &,
691  MeasurementVectorType &, MeasurementVectorType &, double ) const;
692 
696  bool BoundsOverlapBall( const MeasurementVectorType &,
697  MeasurementVectorType &, MeasurementVectorType &, double) const;
698 
700  void DeleteNode( KdTreeNodeType * );
701 
703  void PrintTree( std::ostream & ) const;
704 
706  void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
707  std::ostream & os = std::cout ) const;
708 
711  void PlotTree( std::ostream & os ) const;
712 
714  void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;
715 
716  typedef typename TSample::Iterator Iterator;
717  typedef typename TSample::ConstIterator ConstIterator;
718 
719 protected:
721  KdTree();
722 
724  virtual ~KdTree();
725 
726  void PrintSelf( std::ostream & os, Indent indent ) const;
727 
729  int NearestNeighborSearchLoop( const KdTreeNodeType *,
732 
734  int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
737 
738 private:
739  KdTree( const Self & ); //purposely not implemented
740  void operator=( const Self & ); //purposely not implemented
741 
743  const TSample *m_Sample;
744 
747 
750 
753 
756 
759 }; // end of class
760 } // end of namespace Statistics
761 } // end of namespace itk
762 
763 #ifndef ITK_MANUAL_INSTANTIATION
764 #include "itkKdTree.hxx"
765 #endif
766 
767 #endif
768