ITK  6.0.0
Insight Toolkit
itkKdTree.h
Go to the documentation of this file.
1/*=========================================================================
2 *
3 * Copyright NumFOCUS
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 * https://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
33namespace itk
34{
35namespace Statistics
36{
63template <typename TSample>
64
65struct ITK_TEMPLATE_EXPORT KdTreeNode
66{
69
71 using MeasurementType = typename TSample::MeasurementType;
72
75
78 using InstanceIdentifier = typename TSample::InstanceIdentifier;
79
82 virtual bool
83 IsTerminal() const = 0;
84
90 virtual void
91 GetParameters(unsigned int &, MeasurementType &) const = 0;
92
94 virtual Self *
95 Left() = 0;
96
98 virtual const Self *
99 Left() const = 0;
100
102 virtual Self *
103 Right() = 0;
104
106 virtual const Self *
107 Right() const = 0;
108
113 virtual unsigned int
114 Size() const = 0;
115
117 virtual void
119
121 virtual void
123
126
129
131 virtual ~KdTreeNode() = default; // needed to subclasses will actually be deleted
132}; // end of class
133
147template <typename TSample>
148
149struct ITK_TEMPLATE_EXPORT KdTreeNonterminalNode : public KdTreeNode<TSample>
150{
152 using typename Superclass::MeasurementType;
153 using typename Superclass::CentroidType;
154 using typename Superclass::InstanceIdentifier;
155
157
158 ~KdTreeNonterminalNode() override = default;
159
160 bool
161 IsTerminal() const override
162 {
163 return false;
164 }
165
166 void
167 GetParameters(unsigned int &, MeasurementType &) const override;
168
170 Superclass *
171 Left() override
172 {
173 return m_Left;
174 }
175
177 Superclass *
178 Right() override
179 {
180 return m_Right;
181 }
182
184 const Superclass *
185 Left() const override
186 {
187 return m_Left;
188 }
189
191 const Superclass *
192 Right() const override
193 {
194 return m_Right;
195 }
196
201 unsigned int
202 Size() const override
203 {
204 return 0;
205 }
206
211 void
213 {}
214
219 void
221 {}
222
228 InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const override { return this->m_InstanceIdentifier; }
229
233 void
235 {
236 this->m_InstanceIdentifier = valueId;
237 }
238
239private:
240 unsigned int m_PartitionDimension{};
241 MeasurementType m_PartitionValue{};
242 InstanceIdentifier m_InstanceIdentifier{};
243 Superclass * m_Left{};
244 Superclass * m_Right{};
245}; // end of class
246
263template <typename TSample>
264struct ITK_TEMPLATE_EXPORT KdTreeWeightedCentroidNonterminalNode : public KdTreeNode<TSample>
265{
267 using typename Superclass::MeasurementType;
268 using typename Superclass::CentroidType;
269 using typename Superclass::InstanceIdentifier;
270 using MeasurementVectorSizeType = typename TSample::MeasurementVectorSizeType;
271
274 Superclass *,
275 Superclass *,
276 CentroidType &,
277 unsigned int);
278
280
282 bool
283 IsTerminal() const override
284 {
285 return false;
286 }
287
289 void
290 GetParameters(unsigned int &, MeasurementType &) const override;
291
295 {
296 return m_MeasurementVectorSize;
297 }
298
300 Superclass *
301 Left() override
302 {
303 return m_Left;
304 }
305
307 Superclass *
308 Right() override
309 {
310 return m_Right;
311 }
312
314 const Superclass *
315 Left() const override
316 {
317 return m_Left;
318 }
319
321 const Superclass *
322 Right() const override
323 {
324 return m_Right;
325 }
326
328 unsigned int
329 Size() const override
330 {
331 return m_Size;
332 }
333
337 void
339 {
340 centroid = m_WeightedCentroid;
341 }
342
346 void
347 GetCentroid(CentroidType & centroid) override
348 {
349 centroid = m_Centroid;
350 }
351
357 InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const override { return this->m_InstanceIdentifier; }
358
362 void
364 {
365 this->m_InstanceIdentifier = valueId;
366 }
367
368private:
369 MeasurementVectorSizeType m_MeasurementVectorSize{};
370 unsigned int m_PartitionDimension{};
371 MeasurementType m_PartitionValue{};
372 CentroidType m_WeightedCentroid{};
373 CentroidType m_Centroid{};
374 InstanceIdentifier m_InstanceIdentifier{};
375 unsigned int m_Size{};
376 Superclass * m_Left{};
377 Superclass * m_Right{};
378}; // end of class
379
393template <typename TSample>
394struct ITK_TEMPLATE_EXPORT KdTreeTerminalNode : public KdTreeNode<TSample>
395{
397 using typename Superclass::MeasurementType;
398 using typename Superclass::CentroidType;
399 using typename Superclass::InstanceIdentifier;
400
402
403 ~KdTreeTerminalNode() override { this->m_InstanceIdentifiers.clear(); }
404
406 bool
407 IsTerminal() const override
408 {
409 return true;
410 }
411
413 void
414 GetParameters(unsigned int &, MeasurementType &) const override
415 {}
416
418 Superclass *
419 Left() override
420 {
421 return nullptr;
422 }
423
425 Superclass *
426 Right() override
427 {
428 return nullptr;
429 }
430
432 const Superclass *
433 Left() const override
434 {
435 return nullptr;
436 }
437
439 const Superclass *
440 Right() const override
441 {
442 return nullptr;
443 }
444
446 unsigned int
447 Size() const override
448 {
449 return static_cast<unsigned int>(m_InstanceIdentifiers.size());
450 }
451
456 void
458 {}
459
464 void
466 {}
467
473 InstanceIdentifier
475 {
476 return m_InstanceIdentifiers[index];
477 }
478
482 void
484 {
485 m_InstanceIdentifiers.push_back(id);
486 }
487
488private:
489 std::vector<InstanceIdentifier> m_InstanceIdentifiers{};
490}; // end of class
491
526template <typename TSample>
527class ITK_TEMPLATE_EXPORT KdTree : public Object
528{
529public:
530 ITK_DISALLOW_COPY_AND_MOVE(KdTree);
531
533 using Self = KdTree;
537
539 itkOverrideGetNameOfClassMacro(KdTree);
540
542 itkNewMacro(Self);
543
545 using SampleType = TSample;
546 using MeasurementVectorType = typename TSample::MeasurementVectorType;
547 using MeasurementType = typename TSample::MeasurementType;
548 using InstanceIdentifier = typename TSample::InstanceIdentifier;
549 using AbsoluteFrequencyType = typename TSample::AbsoluteFrequencyType;
550
551 using MeasurementVectorSizeType = unsigned int;
552
555 itkGetConstMacro(MeasurementVectorSize, MeasurementVectorSizeType);
556
559
562
566 using NeighborType = std::pair<InstanceIdentifier, double>;
567
568 using InstanceIdentifierVectorType = std::vector<InstanceIdentifier>;
569
582 {
583 public:
584
586 NearestNeighbors(std::vector<double> & cache_vector)
587 : m_FarthestNeighborIndex(0)
588 , m_Distances(cache_vector)
589 {}
591
593 ~NearestNeighbors() = default;
594
597 void
598 resize(unsigned int k)
599 {
600 m_Identifiers.clear();
601 m_Identifiers.resize(k, NumericTraits<IdentifierType>::max());
602 m_Distances.clear();
603 m_Distances.resize(k, NumericTraits<double>::max());
604 m_FarthestNeighborIndex = 0;
605 }
609 double
611 {
612 return m_Distances[m_FarthestNeighborIndex];
613 }
614
617 void
619 {
620 m_Identifiers[m_FarthestNeighborIndex] = id;
621 m_Distances[m_FarthestNeighborIndex] = distance;
622 double farthestDistance = NumericTraits<double>::min();
623 const auto size = static_cast<unsigned int>(m_Distances.size());
624 for (unsigned int i = 0; i < size; ++i)
625 {
626 if (m_Distances[i] > farthestDistance)
627 {
628 farthestDistance = m_Distances[i];
629 m_FarthestNeighborIndex = i;
630 }
631 }
632 }
638 {
639 return m_Identifiers;
640 }
641
645 GetNeighbor(unsigned int index) const
646 {
647 return m_Identifiers[index];
648 }
649
650 private:
653
656
660 std::vector<double> & m_Distances;
661 };
662
665 void
666 SetBucketSize(unsigned int);
667
670 void
671 SetSample(const TSample *);
672
674 const TSample *
675 GetSample() const
676 {
677 return m_Sample;
678 }
679
681 Size() const
682 {
683 return m_Sample->Size();
684 }
685
690 KdTreeNodeType *
692 {
693 return m_EmptyTerminalNode;
694 }
695
698 void
700 {
701 if (this->m_Root)
702 {
703 this->DeleteNode(this->m_Root);
704 }
705 this->m_Root = root;
706 }
710 KdTreeNodeType *
712 {
713 return m_Root;
714 }
715
718 const MeasurementVectorType &
720 {
721 return m_Sample->GetMeasurementVector(id);
722 }
723
726 AbsoluteFrequencyType
728 {
729 return m_Sample->GetFrequency(id);
730 }
731
733 DistanceMetricType *
735 {
736 return m_DistanceMetric.GetPointer();
737 }
738
740 void
742
746 void
747 Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &, std::vector<double> &) const;
748
750 void
752
758 bool
760
764 bool
766
768 void
770
772 void
773 PrintTree(std::ostream &) const;
774
776 void
777 PrintTree(KdTreeNodeType *, unsigned int, unsigned int, std::ostream & os = std::cout) const;
778
781 void
782 PlotTree(std::ostream & os) const;
783
785 void
786 PlotTree(KdTreeNodeType * node, std::ostream & os = std::cout) const;
787
788 using Iterator = typename TSample::Iterator;
789 using ConstIterator = typename TSample::ConstIterator;
790
791protected:
794
796 ~KdTree() override;
797
798 void
799 PrintSelf(std::ostream & os, Indent indent) const override;
800
802 int
804 const MeasurementVectorType &,
807 NearestNeighbors &) const;
808
810 int
812 const MeasurementVectorType &,
813 double,
817
818private:
820 const TSample * m_Sample{};
821
823 int m_BucketSize{};
824
826 KdTreeNodeType * m_Root{};
827
829 KdTreeNodeType * m_EmptyTerminalNode{};
830
832 typename DistanceMetricType::Pointer m_DistanceMetric{};
833
835 MeasurementVectorSizeType m_MeasurementVectorSize{};
836}; // end of class
837} // end of namespace Statistics
838} // end of namespace itk
839
840#ifndef ITK_MANUAL_INSTANTIATION
841# include "itkKdTree.hxx"
842#endif
843
844#endif
Control indentation during Print() invocation.
Definition: itkIndent.h:50
Light weight base class for most itk classes.
Define additional traits for native types such as int or float.
static constexpr T min(const T &)
Base class for most ITK classes.
Definition: itkObject.h:62
data structure for storing k-nearest neighbor search result (k number of Neighbors)
Definition: itkKdTree.h:582
std::vector< double > & m_Distances
Definition: itkKdTree.h:660
InstanceIdentifier GetNeighbor(unsigned int index) const
Definition: itkKdTree.h:645
InstanceIdentifierVectorType m_Identifiers
Definition: itkKdTree.h:655
NearestNeighbors(std::vector< double > &cache_vector)
Definition: itkKdTree.h:586
const InstanceIdentifierVectorType & GetNeighbors() const
Definition: itkKdTree.h:637
void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
Definition: itkKdTree.h:618
This class provides methods for k-nearest neighbor search and related data structures for a k-d tree.
Definition: itkKdTree.h:528
KdTreeNodeType * GetRoot()
Definition: itkKdTree.h:711
void PlotTree(std::ostream &os) const
KdTreeNodeType * GetEmptyTerminalNode()
Definition: itkKdTree.h:691
const TSample * GetSample() const
Definition: itkKdTree.h:675
void SetBucketSize(unsigned int)
void SetRoot(KdTreeNodeType *root)
Definition: itkKdTree.h:699
void Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &) const
typename TSample::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:548
SizeValueType Size() const
Definition: itkKdTree.h:681
bool BoundsOverlapBall(const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, double) const
DistanceMetricType * GetDistanceMetric()
Definition: itkKdTree.h:734
const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
Definition: itkKdTree.h:719
typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType
Definition: itkKdTree.h:549
std::pair< InstanceIdentifier, double > NeighborType
Definition: itkKdTree.h:566
void PrintTree(KdTreeNodeType *, unsigned int, unsigned int, std::ostream &os=std::cout) const
std::vector< InstanceIdentifier > InstanceIdentifierVectorType
Definition: itkKdTree.h:568
typename TSample::MeasurementType MeasurementType
Definition: itkKdTree.h:547
void Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &, std::vector< double > &) const
void PrintSelf(std::ostream &os, Indent indent) const override
int SearchLoop(const KdTreeNodeType *, const MeasurementVectorType &, double, MeasurementVectorType &, MeasurementVectorType &, InstanceIdentifierVectorType &) const
unsigned int MeasurementVectorSizeType
Definition: itkKdTree.h:551
typename TSample::Iterator Iterator
Definition: itkKdTree.h:788
int NearestNeighborSearchLoop(const KdTreeNodeType *, const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, NearestNeighbors &) const
bool BallWithinBounds(const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, double) const
void SetSample(const TSample *)
void PlotTree(KdTreeNodeType *node, std::ostream &os=std::cout) const
AbsoluteFrequencyType GetFrequency(InstanceIdentifier id) const
Definition: itkKdTree.h:727
typename TSample::ConstIterator ConstIterator
Definition: itkKdTree.h:789
typename TSample::MeasurementVectorType MeasurementVectorType
Definition: itkKdTree.h:546
void Search(const MeasurementVectorType &, double, InstanceIdentifierVectorType &) const
void PrintTree(std::ostream &) const
void DeleteNode(KdTreeNodeType *)
BinaryGeneratorImageFilter< TInputImage1, TInputImage2, TOutputImage > Superclass
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
unsigned long SizeValueType
Definition: itkIntTypes.h:86
This class defines the interface of its derived classes.
Definition: itkKdTree.h:66
typename TSample::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:78
virtual void GetParameters(unsigned int &, MeasurementType &) const =0
virtual InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const =0
virtual bool IsTerminal() const =0
virtual Self * Right()=0
virtual void GetCentroid(CentroidType &)=0
typename TSample::MeasurementType MeasurementType
Definition: itkKdTree.h:71
virtual void AddInstanceIdentifier(InstanceIdentifier)=0
virtual void GetWeightedCentroid(CentroidType &)=0
virtual unsigned int Size() const =0
virtual const Self * Left() const =0
virtual ~KdTreeNode()=default
virtual const Self * Right() const =0
virtual Self * Left()=0
This is a subclass of the KdTreeNode.
Definition: itkKdTree.h:150
bool IsTerminal() const override
Definition: itkKdTree.h:161
const Superclass * Right() const override
Definition: itkKdTree.h:192
unsigned int Size() const override
Definition: itkKdTree.h:202
const Superclass * Left() const override
Definition: itkKdTree.h:185
void GetWeightedCentroid(CentroidType &) override
Definition: itkKdTree.h:212
Superclass * Right() override
Definition: itkKdTree.h:178
void GetParameters(unsigned int &, MeasurementType &) const override
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const override
Definition: itkKdTree.h:228
void GetCentroid(CentroidType &) override
Definition: itkKdTree.h:220
KdTreeNonterminalNode(unsigned int, MeasurementType, Superclass *, Superclass *)
Superclass * Left() override
Definition: itkKdTree.h:171
void AddInstanceIdentifier(InstanceIdentifier valueId) override
Definition: itkKdTree.h:234
This class is the node that doesn't have any child node. The IsTerminal method returns true for this ...
Definition: itkKdTree.h:395
void GetParameters(unsigned int &, MeasurementType &) const override
Definition: itkKdTree.h:414
void GetCentroid(CentroidType &) override
Definition: itkKdTree.h:465
bool IsTerminal() const override
Definition: itkKdTree.h:407
void GetWeightedCentroid(CentroidType &) override
Definition: itkKdTree.h:457
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier index) const override
Definition: itkKdTree.h:474
const Superclass * Right() const override
Definition: itkKdTree.h:440
Superclass * Right() override
Definition: itkKdTree.h:426
const Superclass * Left() const override
Definition: itkKdTree.h:433
unsigned int Size() const override
Definition: itkKdTree.h:447
void AddInstanceIdentifier(InstanceIdentifier id) override
Definition: itkKdTree.h:483
Superclass * Left() override
Definition: itkKdTree.h:419
This is a subclass of the KdTreeNode.
Definition: itkKdTree.h:265
KdTreeWeightedCentroidNonterminalNode(unsigned int, MeasurementType, Superclass *, Superclass *, CentroidType &, unsigned int)
void GetWeightedCentroid(CentroidType &centroid) override
Definition: itkKdTree.h:338
void GetCentroid(CentroidType &centroid) override
Definition: itkKdTree.h:347
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const override
Definition: itkKdTree.h:357
MeasurementVectorSizeType GetMeasurementVectorSize() const
Definition: itkKdTree.h:294
const Superclass * Left() const override
Definition: itkKdTree.h:315
typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType
Definition: itkKdTree.h:270
const Superclass * Right() const override
Definition: itkKdTree.h:322
void GetParameters(unsigned int &, MeasurementType &) const override
void AddInstanceIdentifier(InstanceIdentifier valueId) override
Definition: itkKdTree.h:363