ITK  4.3.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 
220 private:
221 
222  unsigned int m_PartitionDimension;
227 }; // end of class
228 
244 template<class 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<class 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 0;
389  }
390 
393  {
394  return 0;
395  }
396 
398  const Superclass * Left() const
399  {
400  return 0;
401  }
402 
404  const Superclass * Right() const
405  {
406  return 0;
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<class TSample>
483 class ITK_EXPORT 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();
548  m_Identifiers.resize( k, NumericTraits< IdentifierType >::max() );
549  m_Distances.clear();
550  m_Distances.resize( k, NumericTraits<double>::max() );
551  m_FarthestNeighborIndex = 0;
552  }
554 
556  double GetLargestDistance()
557  {
558  return m_Distances[m_FarthestNeighborIndex];
559  }
560 
563  void ReplaceFarthestNeighbor( InstanceIdentifier id, double distance )
564  {
565  m_Identifiers[m_FarthestNeighborIndex] = id;
566  m_Distances[m_FarthestNeighborIndex] = distance;
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];
574  m_FarthestNeighborIndex = i;
575  }
576  }
577  }
579 
581  const InstanceIdentifierVectorType & GetNeighbors() const
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 
634  KdTreeNodeType * GetEmptyTerminalNode()
635  {
636  return m_EmptyTerminalNode;
637  }
638 
641  void SetRoot(KdTreeNodeType *root)
642  {
643  if ( this->m_Root )
644  {
645  this->DeleteNode( this->m_Root );
646  }
647  this->m_Root = root;
648  }
650 
652  KdTreeNodeType * GetRoot()
653  {
654  return m_Root;
655  }
656 
659  const MeasurementVectorType & GetMeasurementVector( InstanceIdentifier id )
660  const
661  {
662  return m_Sample->GetMeasurementVector( id );
663  }
664 
668  {
669  return m_Sample->GetFrequency( id );
670  }
671 
673  DistanceMetricType * GetDistanceMetric()
674  {
675  return m_DistanceMetric.GetPointer();
676  }
677 
679  void Search( const MeasurementVectorType &, unsigned int,
680  InstanceIdentifierVectorType & ) const;
681 
683  void Search( const MeasurementVectorType &, double,
684  InstanceIdentifierVectorType & ) const;
685 
691  bool BallWithinBounds( const MeasurementVectorType &,
692  MeasurementVectorType &, MeasurementVectorType &, double ) const;
693 
697  bool BoundsOverlapBall( const MeasurementVectorType &,
698  MeasurementVectorType &, MeasurementVectorType &, double) const;
699 
701  void DeleteNode( KdTreeNodeType * );
702 
704  void PrintTree( std::ostream & ) const;
705 
707  void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
708  std::ostream & os = std::cout ) const;
709 
712  void PlotTree( std::ostream & os ) const;
713 
715  void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;
716 
717  typedef typename TSample::Iterator Iterator;
718  typedef typename TSample::ConstIterator ConstIterator;
719 
720 protected:
722  KdTree();
723 
725  virtual ~KdTree();
726 
727  void PrintSelf( std::ostream & os, Indent indent ) const;
728 
730  int NearestNeighborSearchLoop( const KdTreeNodeType *,
733 
735  int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
738 
739 private:
740  KdTree( const Self & ); //purposely not implemented
741  void operator=( const Self & ); //purposely not implemented
742 
744  const TSample *m_Sample;
745 
748 
751 
754 
757 
760 }; // end of class
761 } // end of namespace Statistics
762 } // end of namespace itk
763 
764 #ifndef ITK_MANUAL_INSTANTIATION
765 #include "itkKdTree.hxx"
766 #endif
767 
768 #endif
769