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
230 {
231 return this->m_InstanceIdentifier;
232 }
233
237 void
239 {
240 this->m_InstanceIdentifier = valueId;
241 }
242
243private:
244 unsigned int m_PartitionDimension{};
245 MeasurementType m_PartitionValue{};
246 InstanceIdentifier m_InstanceIdentifier{};
247 Superclass * m_Left{};
248 Superclass * m_Right{};
249}; // end of class
250
267template <typename TSample>
268struct ITK_TEMPLATE_EXPORT KdTreeWeightedCentroidNonterminalNode : public KdTreeNode<TSample>
269{
271 using typename Superclass::MeasurementType;
272 using typename Superclass::CentroidType;
273 using typename Superclass::InstanceIdentifier;
274 using MeasurementVectorSizeType = typename TSample::MeasurementVectorSizeType;
275
278 Superclass *,
279 Superclass *,
280 CentroidType &,
281 unsigned int);
282
284
286 bool
287 IsTerminal() const override
288 {
289 return false;
290 }
291
293 void
294 GetParameters(unsigned int &, MeasurementType &) const override;
295
299 {
300 return m_MeasurementVectorSize;
301 }
302
304 Superclass *
305 Left() override
306 {
307 return m_Left;
308 }
309
311 Superclass *
312 Right() override
313 {
314 return m_Right;
315 }
316
318 const Superclass *
319 Left() const override
320 {
321 return m_Left;
322 }
323
325 const Superclass *
326 Right() const override
327 {
328 return m_Right;
329 }
330
332 unsigned int
333 Size() const override
334 {
335 return m_Size;
336 }
337
341 void
343 {
344 centroid = m_WeightedCentroid;
345 }
346
350 void
351 GetCentroid(CentroidType & centroid) override
352 {
353 centroid = m_Centroid;
354 }
355
361 InstanceIdentifier
363 {
364 return this->m_InstanceIdentifier;
365 }
366
370 void
372 {
373 this->m_InstanceIdentifier = valueId;
374 }
375
376private:
377 MeasurementVectorSizeType m_MeasurementVectorSize{};
378 unsigned int m_PartitionDimension{};
379 MeasurementType m_PartitionValue{};
380 CentroidType m_WeightedCentroid{};
381 CentroidType m_Centroid{};
382 InstanceIdentifier m_InstanceIdentifier{};
383 unsigned int m_Size{};
384 Superclass * m_Left{};
385 Superclass * m_Right{};
386}; // end of class
387
401template <typename TSample>
402struct ITK_TEMPLATE_EXPORT KdTreeTerminalNode : public KdTreeNode<TSample>
403{
405 using typename Superclass::MeasurementType;
406 using typename Superclass::CentroidType;
407 using typename Superclass::InstanceIdentifier;
408
410
411 ~KdTreeTerminalNode() override { this->m_InstanceIdentifiers.clear(); }
412
414 bool
415 IsTerminal() const override
416 {
417 return true;
418 }
419
421 void
422 GetParameters(unsigned int &, MeasurementType &) const override
423 {}
424
426 Superclass *
427 Left() override
428 {
429 return nullptr;
430 }
431
433 Superclass *
434 Right() override
435 {
436 return nullptr;
437 }
438
440 const Superclass *
441 Left() const override
442 {
443 return nullptr;
444 }
445
447 const Superclass *
448 Right() const override
449 {
450 return nullptr;
451 }
452
454 unsigned int
455 Size() const override
456 {
457 return static_cast<unsigned int>(m_InstanceIdentifiers.size());
458 }
459
464 void
466 {}
467
472 void
474 {}
475
481 InstanceIdentifier
483 {
484 return m_InstanceIdentifiers[index];
485 }
486
490 void
492 {
493 m_InstanceIdentifiers.push_back(id);
494 }
495
496private:
497 std::vector<InstanceIdentifier> m_InstanceIdentifiers{};
498}; // end of class
499
534template <typename TSample>
535class ITK_TEMPLATE_EXPORT KdTree : public Object
536{
537public:
538 ITK_DISALLOW_COPY_AND_MOVE(KdTree);
539
541 using Self = KdTree;
545
547 itkOverrideGetNameOfClassMacro(KdTree);
548
550 itkNewMacro(Self);
551
553 using SampleType = TSample;
554 using MeasurementVectorType = typename TSample::MeasurementVectorType;
555 using MeasurementType = typename TSample::MeasurementType;
556 using InstanceIdentifier = typename TSample::InstanceIdentifier;
557 using AbsoluteFrequencyType = typename TSample::AbsoluteFrequencyType;
558
559 using MeasurementVectorSizeType = unsigned int;
560
563 itkGetConstMacro(MeasurementVectorSize, MeasurementVectorSizeType);
564
567
570
574 using NeighborType = std::pair<InstanceIdentifier, double>;
575
576 using InstanceIdentifierVectorType = std::vector<InstanceIdentifier>;
577
590 {
591 public:
592
594 NearestNeighbors(std::vector<double> & cache_vector)
595 : m_FarthestNeighborIndex(0)
596 , m_Distances(cache_vector)
597 {}
599
601 ~NearestNeighbors() = default;
602
605 void
606 resize(unsigned int k)
607 {
608 m_Identifiers.clear();
609 m_Identifiers.resize(k, NumericTraits<IdentifierType>::max());
610 m_Distances.clear();
611 m_Distances.resize(k, NumericTraits<double>::max());
612 m_FarthestNeighborIndex = 0;
613 }
617 double
619 {
620 return m_Distances[m_FarthestNeighborIndex];
621 }
622
625 void
627 {
628 m_Identifiers[m_FarthestNeighborIndex] = id;
629 m_Distances[m_FarthestNeighborIndex] = distance;
630 double farthestDistance = NumericTraits<double>::min();
631 const auto size = static_cast<unsigned int>(m_Distances.size());
632 for (unsigned int i = 0; i < size; ++i)
633 {
634 if (m_Distances[i] > farthestDistance)
635 {
636 farthestDistance = m_Distances[i];
637 m_FarthestNeighborIndex = i;
638 }
639 }
640 }
646 {
647 return m_Identifiers;
648 }
649
653 GetNeighbor(unsigned int index) const
654 {
655 return m_Identifiers[index];
656 }
657
658 private:
661
664
668 std::vector<double> & m_Distances;
669 };
670
673 void
674 SetBucketSize(unsigned int);
675
678 void
679 SetSample(const TSample *);
680
682 const TSample *
683 GetSample() const
684 {
685 return m_Sample;
686 }
687
689 Size() const
690 {
691 return m_Sample->Size();
692 }
693
698 KdTreeNodeType *
700 {
701 return m_EmptyTerminalNode;
702 }
703
706 void
708 {
709 if (this->m_Root)
710 {
711 this->DeleteNode(this->m_Root);
712 }
713 this->m_Root = root;
714 }
718 KdTreeNodeType *
720 {
721 return m_Root;
722 }
723
726 const MeasurementVectorType &
728 {
729 return m_Sample->GetMeasurementVector(id);
730 }
731
734 AbsoluteFrequencyType
736 {
737 return m_Sample->GetFrequency(id);
738 }
739
741 DistanceMetricType *
743 {
744 return m_DistanceMetric.GetPointer();
745 }
746
748 void
750
754 void
755 Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &, std::vector<double> &) const;
756
758 void
760
766 bool
768
772 bool
774
776 void
778
780 void
781 PrintTree(std::ostream &) const;
782
784 void
785 PrintTree(KdTreeNodeType *, unsigned int, unsigned int, std::ostream & os = std::cout) const;
786
789 void
790 PlotTree(std::ostream & os) const;
791
793 void
794 PlotTree(KdTreeNodeType * node, std::ostream & os = std::cout) const;
795
796 using Iterator = typename TSample::Iterator;
797 using ConstIterator = typename TSample::ConstIterator;
798
799protected:
802
804 ~KdTree() override;
805
806 void
807 PrintSelf(std::ostream & os, Indent indent) const override;
808
810 int
812 const MeasurementVectorType &,
815 NearestNeighbors &) const;
816
818 int
820 const MeasurementVectorType &,
821 double,
825
826private:
828 const TSample * m_Sample{};
829
831 int m_BucketSize{};
832
834 KdTreeNodeType * m_Root{};
835
837 KdTreeNodeType * m_EmptyTerminalNode{};
838
840 typename DistanceMetricType::Pointer m_DistanceMetric{};
841
843 MeasurementVectorSizeType m_MeasurementVectorSize{};
844}; // end of class
845} // end of namespace Statistics
846} // end of namespace itk
847
848#ifndef ITK_MANUAL_INSTANTIATION
849# include "itkKdTree.hxx"
850#endif
851
852#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:590
std::vector< double > & m_Distances
Definition: itkKdTree.h:668
InstanceIdentifier GetNeighbor(unsigned int index) const
Definition: itkKdTree.h:653
InstanceIdentifierVectorType m_Identifiers
Definition: itkKdTree.h:663
NearestNeighbors(std::vector< double > &cache_vector)
Definition: itkKdTree.h:594
const InstanceIdentifierVectorType & GetNeighbors() const
Definition: itkKdTree.h:645
void ReplaceFarthestNeighbor(InstanceIdentifier id, double distance)
Definition: itkKdTree.h:626
This class provides methods for k-nearest neighbor search and related data structures for a k-d tree.
Definition: itkKdTree.h:536
KdTreeNodeType * GetRoot()
Definition: itkKdTree.h:719
void PlotTree(std::ostream &os) const
KdTreeNodeType * GetEmptyTerminalNode()
Definition: itkKdTree.h:699
const TSample * GetSample() const
Definition: itkKdTree.h:683
void SetBucketSize(unsigned int)
void SetRoot(KdTreeNodeType *root)
Definition: itkKdTree.h:707
void Search(const MeasurementVectorType &, unsigned int, InstanceIdentifierVectorType &) const
typename TSample::InstanceIdentifier InstanceIdentifier
Definition: itkKdTree.h:556
SizeValueType Size() const
Definition: itkKdTree.h:689
bool BoundsOverlapBall(const MeasurementVectorType &, MeasurementVectorType &, MeasurementVectorType &, double) const
DistanceMetricType * GetDistanceMetric()
Definition: itkKdTree.h:742
const MeasurementVectorType & GetMeasurementVector(InstanceIdentifier id) const
Definition: itkKdTree.h:727
typename TSample::AbsoluteFrequencyType AbsoluteFrequencyType
Definition: itkKdTree.h:557
std::pair< InstanceIdentifier, double > NeighborType
Definition: itkKdTree.h:574
void PrintTree(KdTreeNodeType *, unsigned int, unsigned int, std::ostream &os=std::cout) const
std::vector< InstanceIdentifier > InstanceIdentifierVectorType
Definition: itkKdTree.h:576
typename TSample::MeasurementType MeasurementType
Definition: itkKdTree.h:555
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:559
typename TSample::Iterator Iterator
Definition: itkKdTree.h:796
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:735
typename TSample::ConstIterator ConstIterator
Definition: itkKdTree.h:797
typename TSample::MeasurementVectorType MeasurementVectorType
Definition: itkKdTree.h:554
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:229
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:238
This class is the node that doesn't have any child node. The IsTerminal method returns true for this ...
Definition: itkKdTree.h:403
void GetParameters(unsigned int &, MeasurementType &) const override
Definition: itkKdTree.h:422
void GetCentroid(CentroidType &) override
Definition: itkKdTree.h:473
bool IsTerminal() const override
Definition: itkKdTree.h:415
void GetWeightedCentroid(CentroidType &) override
Definition: itkKdTree.h:465
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier index) const override
Definition: itkKdTree.h:482
const Superclass * Right() const override
Definition: itkKdTree.h:448
Superclass * Right() override
Definition: itkKdTree.h:434
const Superclass * Left() const override
Definition: itkKdTree.h:441
unsigned int Size() const override
Definition: itkKdTree.h:455
void AddInstanceIdentifier(InstanceIdentifier id) override
Definition: itkKdTree.h:491
Superclass * Left() override
Definition: itkKdTree.h:427
This is a subclass of the KdTreeNode.
Definition: itkKdTree.h:269
KdTreeWeightedCentroidNonterminalNode(unsigned int, MeasurementType, Superclass *, Superclass *, CentroidType &, unsigned int)
void GetWeightedCentroid(CentroidType &centroid) override
Definition: itkKdTree.h:342
void GetCentroid(CentroidType &centroid) override
Definition: itkKdTree.h:351
InstanceIdentifier GetInstanceIdentifier(InstanceIdentifier) const override
Definition: itkKdTree.h:362
MeasurementVectorSizeType GetMeasurementVectorSize() const
Definition: itkKdTree.h:298
const Superclass * Left() const override
Definition: itkKdTree.h:319
typename TSample::MeasurementVectorSizeType MeasurementVectorSizeType
Definition: itkKdTree.h:274
const Superclass * Right() const override
Definition: itkKdTree.h:326
void GetParameters(unsigned int &, MeasurementType &) const override
void AddInstanceIdentifier(InstanceIdentifier valueId) override
Definition: itkKdTree.h:371