57
57
* been changed from Array to FixedArray.
59
59
* \sa KdTreeNonterminalNode, KdTreeWeightedCentroidNonterminalNode,
62
62
template< class TSample >
65
65
/** type alias for itself */
66
typedef KdTreeNode< TSample> Self ;
66
typedef KdTreeNode< TSample> Self;
68
68
/** Measurement type, not the measurement vector type */
69
typedef typename TSample::MeasurementType MeasurementType ;
69
typedef typename TSample::MeasurementType MeasurementType;
71
71
/** Centroid type */
72
72
typedef Array< double > CentroidType;
74
74
/** Instance identifier type (index value type for the measurement
75
75
* vector in a sample */
76
typedef typename TSample::InstanceIdentifier InstanceIdentifier ;
76
typedef typename TSample::InstanceIdentifier InstanceIdentifier;
78
78
/** Returns true if the node is a terminal node, that is a node that
79
79
* doesn't have any child. */
80
virtual bool IsTerminal() const = 0 ;
80
virtual bool IsTerminal() const = 0;
82
82
/** Fills the partitionDimension (the dimension that was chosen to
83
83
* split the measurement vectors belong to this node to the left and the
84
84
* right child among k dimensions) and the partitionValue (the
85
85
* measurement value on the partitionDimension divides the left and the
87
virtual void GetParameters(unsigned int &partitionDimension,
88
MeasurementType &partitionValue) const = 0 ;
87
virtual void GetParameters(unsigned int &partitionDimension,
88
MeasurementType &partitionValue) const = 0;
90
90
/** Returns the pointer to the left child of this node */
91
virtual Self* Left() = 0 ;
92
virtual const Self* Left() const = 0 ;
91
virtual Self* Left() = 0;
92
virtual const Self* Left() const = 0;
94
94
/** Returns the pointer to the right child of this node */
95
virtual Self* Right() = 0 ;
96
virtual const Self* Right() const = 0 ;
95
virtual Self* Right() = 0;
96
virtual const Self* Right() const = 0;
98
98
/** Returs the number of measurement vectors under this node including
100
virtual unsigned int Size() const = 0 ;
100
virtual unsigned int Size() const = 0;
102
102
/** Returns the vector sum of the all measurement vectors under this node */
103
virtual void GetWeightedCentroid(CentroidType ¢roid) = 0 ;
103
virtual void GetWeightedCentroid(CentroidType ¢roid) = 0;
105
105
/** Returns the centroid. weighted centroid divided by the size */
106
virtual void GetCentroid(CentroidType ¢roid) = 0 ;
106
virtual void GetCentroid(CentroidType ¢roid) = 0;
108
108
/** Retuns the instance identifier of the index-th measurement vector */
109
virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0 ;
109
virtual InstanceIdentifier GetInstanceIdentifier(size_t index) const = 0;
111
111
/** Add an instance to this node */
112
virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0 ;
112
virtual void AddInstanceIdentifier(InstanceIdentifier id) = 0;
114
114
/** Destructor */
115
115
virtual ~KdTreeNode() {}; // needed to subclasses will actually be deleted
118
118
/** \class KdTreeNonterminalNode
119
* \brief This is a subclass of the KdTreeNode.
119
* \brief This is a subclass of the KdTreeNode.
121
121
* KdTreeNonterminalNode doesn't store the information related with the
122
122
* centroids. Therefore, the GetWeightedCentroid and the GetCentroid
123
123
* methods are void. This class should have the left and the right
124
124
* children. If we have a sample and want to generate a KdTree without
125
125
* the centroid related information, we can use the KdTreeGenerator.
127
127
* \sa KdTreeNode, KdTreeWeightedCentroidNonterminalNode, KdTreeGenerator
129
129
template< class TSample >
130
130
struct KdTreeNonterminalNode: public KdTreeNode< TSample >
132
typedef KdTreeNode< TSample > Superclass ;
133
typedef typename Superclass::MeasurementType MeasurementType ;
134
typedef typename Superclass::CentroidType CentroidType ;
135
typedef typename Superclass::InstanceIdentifier InstanceIdentifier ;
132
typedef KdTreeNode< TSample > Superclass;
133
typedef typename Superclass::MeasurementType MeasurementType;
134
typedef typename Superclass::CentroidType CentroidType;
135
typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
137
137
KdTreeNonterminalNode(unsigned int partitionDimension,
138
138
MeasurementType partitionValue,
139
139
Superclass* left,
142
142
virtual ~KdTreeNonterminalNode() {}
144
144
virtual bool IsTerminal() const
147
void GetParameters(unsigned int &partitionDimension,
147
void GetParameters(unsigned int &partitionDimension,
148
148
MeasurementType &partitionValue) const;
156
156
const Superclass* Left() const
159
159
const Superclass* Right() const
162
162
unsigned int Size() const
165
void GetWeightedCentroid(CentroidType &)
168
void GetCentroid(CentroidType &)
165
void GetWeightedCentroid( CentroidType & )
168
void GetCentroid( CentroidType & )
171
// Returns the identifier of the only MeasurementVector associated with
172
// this node in the tree. This MeasurementVector will be used later during
173
// the distance computation when querying the tree.
171
174
InstanceIdentifier GetInstanceIdentifier(size_t) const
175
{ return this->m_InstanceIdentifier; }
174
void AddInstanceIdentifier(InstanceIdentifier) {}
177
void AddInstanceIdentifier(InstanceIdentifier valueId)
178
{ this->m_InstanceIdentifier = valueId; }
177
unsigned int m_PartitionDimension ;
178
MeasurementType m_PartitionValue ;
180
Superclass* m_Right ;
181
unsigned int m_PartitionDimension;
182
MeasurementType m_PartitionValue;
183
InstanceIdentifier m_InstanceIdentifier;
183
188
/** \class KdTreeWeightedCentroidNonterminalNode
184
* \brief This is a subclass of the KdTreeNode.
189
* \brief This is a subclass of the KdTreeNode.
186
191
* KdTreeNonterminalNode does have the information related with the
187
192
* centroids. Therefore, the GetWeightedCentroid and the GetCentroid
188
193
* methods returns meaningful values. This class should have the left
223
228
return m_MeasurementVectorSize;
233
238
const Superclass* Left() const
236
241
const Superclass* Right() const
239
244
unsigned int Size() const
242
247
void GetWeightedCentroid(CentroidType ¢roid)
243
{ centroid = m_WeightedCentroid ; }
248
{ centroid = m_WeightedCentroid; }
245
250
void GetCentroid(CentroidType ¢roid)
246
{ centroid = m_Centroid ; }
251
{ centroid = m_Centroid; }
248
253
InstanceIdentifier GetInstanceIdentifier(size_t) const
254
{ return this->m_InstanceIdentifier; }
251
void AddInstanceIdentifier(InstanceIdentifier) {}
256
void AddInstanceIdentifier(InstanceIdentifier valueId)
257
{ this->m_InstanceIdentifier = valueId; }
254
MeasurementVectorSizeType m_MeasurementVectorSize;
255
unsigned int m_PartitionDimension ;
256
MeasurementType m_PartitionValue ;
257
CentroidType m_WeightedCentroid ;
258
CentroidType m_Centroid ;
259
unsigned int m_Size ;
261
Superclass* m_Right ;
265
/** \class KdTreeTerminalNode
260
MeasurementVectorSizeType m_MeasurementVectorSize;
261
unsigned int m_PartitionDimension;
262
MeasurementType m_PartitionValue;
263
CentroidType m_WeightedCentroid;
264
CentroidType m_Centroid;
265
InstanceIdentifier m_InstanceIdentifier;
272
/** \class KdTreeTerminalNode
266
273
* \brief This class is the node that doesn't have any child node. The
267
274
* IsTerminal method returns true for this class. This class stores the
268
275
* instance identifiers belonging to this node, while the nonterminal
269
276
* nodes do not store them. The AddInstanceIdentifier and
270
277
* GetInstanceIdentifier are storing and retrieving the instance
271
278
* identifiers belonging to this node.
273
280
* \sa KdTreeNode, KdTreeNonterminalNode,
274
281
* KdTreeWeightedCentroidNonterminalNode
276
283
template< class TSample >
277
284
struct KdTreeTerminalNode: public KdTreeNode< TSample >
279
typedef KdTreeNode< TSample > Superclass ;
280
typedef typename Superclass::MeasurementType MeasurementType ;
281
typedef typename Superclass::CentroidType CentroidType ;
282
typedef typename Superclass::InstanceIdentifier InstanceIdentifier ;
286
typedef KdTreeNode< TSample > Superclass;
287
typedef typename Superclass::MeasurementType MeasurementType;
288
typedef typename Superclass::CentroidType CentroidType;
289
typedef typename Superclass::InstanceIdentifier InstanceIdentifier;
284
291
KdTreeTerminalNode() {}
286
293
virtual ~KdTreeTerminalNode() {}
288
295
bool IsTerminal() const
291
void GetParameters(unsigned int &,
298
void GetParameters(unsigned int &,
292
299
MeasurementType &) const {}
301
308
const Superclass* Left() const
304
311
const Superclass* Right() const
307
314
unsigned int Size() const
308
315
{ return static_cast<unsigned int>( m_InstanceIdentifiers.size() ); }
310
317
void GetWeightedCentroid(CentroidType &)
313
320
void GetCentroid(CentroidType &)
316
323
InstanceIdentifier GetInstanceIdentifier(size_t index) const
317
{ return m_InstanceIdentifiers[index] ; }
324
{ return m_InstanceIdentifiers[index]; }
319
void AddInstanceIdentifier(InstanceIdentifier id)
320
{ m_InstanceIdentifiers.push_back(id) ;}
326
void AddInstanceIdentifier(InstanceIdentifier id)
327
{ m_InstanceIdentifiers.push_back(id);}
323
std::vector< InstanceIdentifier > m_InstanceIdentifiers ;
330
std::vector< InstanceIdentifier > m_InstanceIdentifiers;
327
334
* \brief This class provides methods for k-nearest neighbor search and
328
* related data structures for a k-d tree.
335
* related data structures for a k-d tree.
330
337
* An object of this class stores instance identifiers in a k-d tree
331
338
* that is a binary tree with childrens split along a dimension among
385
392
itkGetConstMacro( MeasurementVectorSize, MeasurementVectorSizeType );
387
394
/** DistanceMetric type for the distance calculation and comparison */
388
typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType ;
395
typedef EuclideanDistance< MeasurementVectorType > DistanceMetricType;
390
397
/** Node type of the KdTree */
391
typedef KdTreeNode< TSample > KdTreeNodeType ;
398
typedef KdTreeNode< TSample > KdTreeNodeType;
393
400
/** Neighbor type. The first element of the std::pair is the instance
394
401
* identifier and the second one is the distance between the measurement
395
402
* vector identified by the first element and the query point. */
396
typedef std::pair< InstanceIdentifier, double > NeighborType ;
403
typedef std::pair< InstanceIdentifier, double > NeighborType;
398
typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType ;
405
typedef std::vector< InstanceIdentifier > InstanceIdentifierVectorType;
400
407
/** \class NearestNeighbors
401
408
* \brief data structure for storing k-nearest neighbor search result
402
409
* (k number of Neighbors)
404
411
* This class stores the instance identifiers and the distance values
405
412
* of k-nearest neighbors. We can also query the farthest neighbor's
406
413
* distance from the query point using the GetLargestDistance
409
416
class NearestNeighbors
412
419
/** Constructor */
413
420
NearestNeighbors() {}
415
422
/** Destructor */
416
~NearestNeighbors() {}
423
~NearestNeighbors() {}
418
425
/** Initialize the internal instance identifier and distance holders
419
426
* with the size, k */
420
427
void resize(unsigned int k)
422
m_Identifiers.clear() ;
423
m_Identifiers.resize(k, NumericTraits< unsigned long >::max()) ;
424
m_Distances.clear() ;
425
m_Distances.resize(k, NumericTraits< double >::max()) ;
426
m_FarthestNeighborIndex = 0 ;
429
m_Identifiers.clear();
430
m_Identifiers.resize(k, NumericTraits< unsigned long >::max());
432
m_Distances.resize(k, NumericTraits< double >::max());
433
m_FarthestNeighborIndex = 0;
429
436
/** Returns the distance of the farthest neighbor from the query point */
430
double GetLargestDistance()
431
{ return m_Distances[m_FarthestNeighborIndex] ; }
437
double GetLargestDistance()
438
{ return m_Distances[m_FarthestNeighborIndex]; }
433
440
/** Replaces the farthest neighbor's instance identifier and
434
441
* distance value with the id and the distance */
435
void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
442
void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
437
m_Identifiers[m_FarthestNeighborIndex] = id ;
438
m_Distances[m_FarthestNeighborIndex] = distance ;
439
double farthestDistance = NumericTraits< double >::min() ;
444
m_Identifiers[m_FarthestNeighborIndex] = id;
445
m_Distances[m_FarthestNeighborIndex] = distance;
446
double farthestDistance = NumericTraits< double >::min();
440
447
const unsigned int size = static_cast<unsigned int>( m_Distances.size() );
441
for ( unsigned int i = 0 ; i < size; i++ )
448
for ( unsigned int i = 0; i < size; i++ )
443
450
if ( m_Distances[i] > farthestDistance )
445
farthestDistance = m_Distances[i] ;
446
m_FarthestNeighborIndex = i ;
452
farthestDistance = m_Distances[i];
453
m_FarthestNeighborIndex = i;
451
458
/** Returns the vector of k-neighbors' instance identifiers */
452
InstanceIdentifierVectorType GetNeighbors()
453
{ return m_Identifiers ; }
459
const InstanceIdentifierVectorType & GetNeighbors() const
460
{ return m_Identifiers; }
455
462
/** Returns the instance identifier of the index-th neighbor among
457
InstanceIdentifier GetNeighbor(unsigned int index)
458
{ return m_Identifiers[index] ; }
464
InstanceIdentifier GetNeighbor(unsigned int index) const
465
{ return m_Identifiers[index]; }
460
467
/** Returns the vector of k-neighbors' instance identifiers */
461
std::vector< double >& GetDistances()
462
{ return m_Distances ; }
468
const std::vector< double >& GetDistances() const
469
{ return m_Distances; }
465
472
/** The index of the farthest neighbor among k-neighbors */
466
unsigned int m_FarthestNeighborIndex ;
473
unsigned int m_FarthestNeighborIndex;
468
475
/** Storage for the instance identifiers of k-neighbors */
469
InstanceIdentifierVectorType m_Identifiers ;
476
InstanceIdentifierVectorType m_Identifiers;
471
478
/** Storage for the distance values of k-neighbors from the query
473
std::vector< double > m_Distances ;
480
std::vector< double > m_Distances;
476
483
/** Sets the number of measurement vectors that can be stored in a
477
484
* terminal node */
478
void SetBucketSize(unsigned int size) ;
485
void SetBucketSize(unsigned int size);
480
487
/** Sets the input sample that provides the measurement vectors to the k-d
482
void SetSample(const TSample* sample) ;
489
void SetSample(const TSample* sample);
484
491
/** Returns the pointer to the input sample */
485
492
const TSample* GetSample() const
486
{ return m_Sample ; }
488
495
unsigned long Size() const
489
{ return m_Sample->Size() ; }
496
{ return m_Sample->Size(); }
491
498
/** Returns the pointer to the empty terminal node. A KdTree object
492
499
* has a single empty terminal node in memory. when the split process
493
500
* has to create an empty terminal node, the single instance is reused
494
501
* for this case */
495
502
KdTreeNodeType* GetEmptyTerminalNode()
496
{ return m_EmptyTerminalNode ; }
503
{ return m_EmptyTerminalNode; }
498
505
/** Sets the root node of the KdTree that is a result of
499
506
* KdTreeGenerator or WeightedCentroidKdTreeGenerator. */
500
void SetRoot(KdTreeNodeType* root)
507
void SetRoot(KdTreeNodeType* root)
503
510
/** Returns the pointer to the root node. */
504
KdTreeNodeType* GetRoot()
511
KdTreeNodeType* GetRoot()
507
514
/** Returns the measurement vector identified by the instance
508
515
* identifier that is an identifier defiend for the input sample */
509
516
const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
510
{ return m_Sample->GetMeasurementVector(id) ; }
517
{ return m_Sample->GetMeasurementVector(id); }
512
/** Returns the frequency of the measurement vector identified by
519
/** Returns the frequency of the measurement vector identified by
513
520
* the instance identifier */
514
521
FrequencyType GetFrequency(InstanceIdentifier id) const
515
{ return m_Sample->GetFrequency( id ) ; }
522
{ return m_Sample->GetFrequency( id ); }
517
524
/** Get the pointer to the distance metric. */
518
525
DistanceMetricType* GetDistanceMetric()
519
{ return m_DistanceMetric.GetPointer() ; }
526
{ return m_DistanceMetric.GetPointer(); }
521
528
/** Searches the k-nearest neighbors */
522
void Search(MeasurementVectorType &query,
529
void Search(const MeasurementVectorType &query,
530
unsigned int numberOfNeighborsRequested,
524
531
InstanceIdentifierVectorType& result) const;
526
533
/** Searches the neighbors fallen into a hypersphere */
527
void Search(MeasurementVectorType &query,
534
void Search(const MeasurementVectorType &query,
529
536
InstanceIdentifierVectorType& result) const;
531
538
/** Returns the number of measurement vectors that have been visited
532
539
* to find the k-nearest neighbors. */
533
540
int GetNumberOfVisits() const
534
{ return m_NumberOfVisits ; }
541
{ return m_NumberOfVisits; }
536
543
/** Returns true if the intermediate k-nearest neighbors exist within
537
544
* the the bounding box defined by the lowerBound and the
538
545
* upperBound. Otherwise returns false. Returns false if the ball
539
546
* defined by the distance between the query point and the farthest
540
547
* neighbor touch the surface of the bounding box.*/
541
bool BallWithinBounds(MeasurementVectorType &query,
548
bool BallWithinBounds(const MeasurementVectorType &query,
542
549
MeasurementVectorType &lowerBound,
543
550
MeasurementVectorType &upperBound,
544
double radius) const ;
551
double radius) const;
546
553
/** Returns true if the ball defined by the distance between the query
547
554
* point and the farthest neighbor overlaps with the bounding box
548
555
* defined by the lower and the upper bounds.*/
549
bool BoundsOverlapBall(MeasurementVectorType &query,
556
bool BoundsOverlapBall(const MeasurementVectorType &query,
550
557
MeasurementVectorType &lowerBound,
551
558
MeasurementVectorType &upperBound,
552
double radius) const ;
559
double radius) const;
554
561
/** Deletes the node recursively */
555
void DeleteNode(KdTreeNodeType *node) ;
557
/** Prints out the tree information */
558
void PrintTree(KdTreeNodeType *node, int level,
559
unsigned int activeDimension) ;
561
typedef typename TSample::Iterator Iterator ;
562
typedef typename TSample::ConstIterator ConstIterator ;
562
void DeleteNode(KdTreeNodeType *node);
564
/** Prints out the tree information */
565
void PrintTree( std::ostream & os ) const;
567
/** Prints out the tree information */
568
void PrintTree(KdTreeNodeType *node, unsigned int level,
569
unsigned int activeDimension,
570
std::ostream & os = std::cout ) const;
572
/** Draw out the tree information to a ostream using
573
* the format of the Graphviz dot tool. */
574
void PlotTree( std::ostream & os ) const;
576
/** Prints out the tree information */
577
void PlotTree(KdTreeNodeType *node, std::ostream & os = std::cout ) const;
580
typedef typename TSample::Iterator Iterator;
581
typedef typename TSample::ConstIterator ConstIterator;
566
typename TSample::ConstIterator iter = m_Sample->Begin() ;
585
typename TSample::ConstIterator iter = m_Sample->Begin();
572
Iterator iter = m_Sample->End() ;
591
Iterator iter = m_Sample->End();
576
595
ConstIterator Begin() const
578
typename TSample::ConstIterator iter = m_Sample->Begin() ;
597
typename TSample::ConstIterator iter = m_Sample->Begin();
582
601
ConstIterator End() const
584
ConstIterator iter = m_Sample->End() ;
603
ConstIterator iter = m_Sample->End();
590
608
/** Constructor */
593
611
/** Destructor: deletes the root node and the empty terminal node. */
596
void PrintSelf(std::ostream& os, Indent indent) const ;
614
void PrintSelf(std::ostream& os, Indent indent) const;
599
617
int NearestNeighborSearchLoop(const KdTreeNodeType* node,
600
MeasurementVectorType &query,
618
const MeasurementVectorType &query,
601
619
MeasurementVectorType &lowerBound,
602
620
MeasurementVectorType &upperBound) const;
605
int SearchLoop(const KdTreeNodeType* node, MeasurementVectorType &query,
623
int SearchLoop(const KdTreeNodeType* node, const MeasurementVectorType &query,
606
624
MeasurementVectorType &lowerBound,
607
MeasurementVectorType &upperBound) const ;
625
MeasurementVectorType &upperBound) const;
609
KdTree(const Self&) ; //purposely not implemented
610
void operator=(const Self&) ; //purposely not implemented
627
KdTree(const Self&); //purposely not implemented
628
void operator=(const Self&); //purposely not implemented
612
630
/** Pointer to the input sample */
613
const TSample* m_Sample ;
631
const TSample* m_Sample;
615
633
/** Number of measurement vectors can be stored in a terminal node. */
618
636
/** Pointer to the root node */
619
KdTreeNodeType* m_Root ;
637
KdTreeNodeType* m_Root;
621
639
/** Pointer to the empty terminal node */
622
KdTreeNodeType* m_EmptyTerminalNode ;
640
KdTreeNodeType* m_EmptyTerminalNode;
624
642
/** Distance metric smart pointer */
625
typename DistanceMetricType::Pointer m_DistanceMetric ;
627
mutable bool m_IsNearestNeighborSearch ;
629
mutable double m_SearchRadius ;
631
mutable InstanceIdentifierVectorType m_Neighbors ;
643
typename DistanceMetricType::Pointer m_DistanceMetric;
645
mutable bool m_IsNearestNeighborSearch;
647
mutable double m_SearchRadius;
649
mutable InstanceIdentifierVectorType m_Neighbors;
633
651
/** k-nearest neighbors */
634
mutable NearestNeighbors m_NearestNeighbors ;
652
mutable NearestNeighbors m_NearestNeighbors;
636
654
/** Temporary lower bound in the SearchLoop. */
637
mutable MeasurementVectorType m_LowerBound ;
655
mutable MeasurementVectorType m_LowerBound;
639
657
/** Temporary upper bound in the SearchLoop. */
640
mutable MeasurementVectorType m_UpperBound ;
658
mutable MeasurementVectorType m_UpperBound;
642
/** Number of measurment vectors to find k-nearest neighbors. */
643
mutable int m_NumberOfVisits ;
660
/** Number of measurment vectors to find k-nearest neighbors. */
661
mutable int m_NumberOfVisits;
645
663
/** Flag to stop the SearchLoop. */
646
mutable bool m_StopSearch ;
664
mutable bool m_StopSearch;
648
666
/** Temporary neighbor */
649
mutable NeighborType m_TempNeighbor ;
667
mutable NeighborType m_TempNeighbor;
651
669
/** Measurement vector size */
652
670
MeasurementVectorSizeType m_MeasurementVectorSize;
655
673
} // end of namespace Statistics
656
674
} // end of namespace itk
added
removed
Code/Numerics/Statistics/itkKdTree.h
