Orfeo Toolbox  4.0
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 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<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  }
553 
556  {
558  }
559 
562  void ReplaceFarthestNeighbor( InstanceIdentifier id, double distance )
563  {
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];
574  }
575  }
576  }
577 
580  {
581  return m_Identifiers;
582  }
583 
586  InstanceIdentifier GetNeighbor(unsigned int index) const
587  {
588  return m_Identifiers[index];
589  }
590 
592  const std::vector<double> & GetDistances() const
593  {
594  return m_Distances;
595  }
596 
597  private:
600 
603 
606  std::vector<double> m_Distances;
607  };
608 
611  void SetBucketSize( unsigned int );
612 
615  void SetSample( const TSample * );
616 
618  const TSample * GetSample() const
619  {
620  return m_Sample;
621  }
622 
624  {
625  return m_Sample->Size();
626  }
627 
633  {
634  return m_EmptyTerminalNode;
635  }
636 
640  {
641  if ( this->m_Root )
642  {
643  this->DeleteNode( this->m_Root );
644  }
645  this->m_Root = root;
646  }
647 
650  {
651  return m_Root;
652  }
653 
657  const
658  {
659  return m_Sample->GetMeasurementVector( id );
660  }
661 
665  {
666  return m_Sample->GetFrequency( id );
667  }
668 
671  {
672  return m_DistanceMetric.GetPointer();
673  }
674 
676  void Search( const MeasurementVectorType &, unsigned int,
678 
680  void Search( const MeasurementVectorType &, double,
682 
689  MeasurementVectorType &, MeasurementVectorType &, double ) const;
690 
695  MeasurementVectorType &, MeasurementVectorType &, double) const;
696 
698  void DeleteNode( KdTreeNodeType * );
699 
701  void PrintTree( std::ostream & ) const;
702 
704  void PrintTree( KdTreeNodeType *, unsigned int, unsigned int,
705  std::ostream & os = std::cout ) const;
706 
709  void PlotTree( std::ostream & os ) const;
710 
712  void PlotTree( KdTreeNodeType *node, std::ostream & os = std::cout ) const;
713 
714  typedef typename TSample::Iterator Iterator;
715  typedef typename TSample::ConstIterator ConstIterator;
716 
717 protected:
719  KdTree();
720 
722  virtual ~KdTree();
723 
724  void PrintSelf( std::ostream & os, Indent indent ) const;
725 
730 
732  int SearchLoop( const KdTreeNodeType *, const MeasurementVectorType &,
735 
736 private:
737  KdTree( const Self & ); //purposely not implemented
738  void operator=( const Self & ); //purposely not implemented
739 
741  const TSample *m_Sample;
742 
745 
748 
751 
754 
757 }; // end of class
758 } // end of namespace Statistics
759 } // end of namespace itk
760 
761 #ifndef ITK_MANUAL_INSTANTIATION
762 #include "itkKdTree.hxx"
763 #endif
764 
765 #endif

Generated at Sat Mar 8 2014 15:00:26 for Orfeo Toolbox with doxygen 1.8.3.1