ITK  6.0.0
Insight Toolkit
itkKdTreeBasedKmeansEstimator.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 itkKdTreeBasedKmeansEstimator_h
19 #define itkKdTreeBasedKmeansEstimator_h
20 
21 #include <vector>
22 #include <unordered_map>
23 
24 #include "itkObject.h"
29 
30 namespace itk
31 {
32 namespace Statistics
33 {
73 template <typename TKdTree>
74 class ITK_TEMPLATE_EXPORT KdTreeBasedKmeansEstimator : public Object
75 {
76 public:
79  using Superclass = Object;
82 
84  itkNewMacro(Self);
85 
87  itkOverrideGetNameOfClassMacro(KdTreeBasedKmeansEstimator);
88 
90  using KdTreeNodeType = typename TKdTree::KdTreeNodeType;
91  using MeasurementType = typename TKdTree::MeasurementType;
92  using MeasurementVectorType = typename TKdTree::MeasurementVectorType;
93  using InstanceIdentifier = typename TKdTree::InstanceIdentifier;
94  using SampleType = typename TKdTree::SampleType;
95  using CentroidType = typename KdTreeNodeType::CentroidType;
96 
98  using MeasurementVectorSizeType = unsigned int;
99 
103  using InternalParametersType = std::vector<ParameterType>;
105 
109 
111 
114  using MembershipFunctionVectorType = std::vector<MembershipFunctionPointer>;
117 
121  GetOutput() const;
122 
124  itkSetMacro(Parameters, ParametersType);
125  itkGetConstMacro(Parameters, ParametersType);
129  itkSetMacro(MaximumIteration, int);
130  itkGetConstMacro(MaximumIteration, int);
135  itkSetMacro(CentroidPositionChangesThreshold, double);
136  itkGetConstMacro(CentroidPositionChangesThreshold, double);
137 
139  void
140  SetKdTree(TKdTree * tree);
141 
142  const TKdTree *
143  GetKdTree() const;
144 
146  itkGetConstMacro(MeasurementVectorSize, MeasurementVectorSizeType);
147 
148  itkGetConstMacro(CurrentIteration, int);
149  itkGetConstMacro(CentroidPositionChanges, double);
150 
155  void
156  StartOptimization();
157 
158  using ClusterLabelsType = std::unordered_map<InstanceIdentifier, unsigned int>;
159 
160  itkSetMacro(UseClusterLabels, bool);
161  itkGetConstMacro(UseClusterLabels, bool);
162  itkBooleanMacro(UseClusterLabels);
163 
164 protected:
166  ~KdTreeBasedKmeansEstimator() override = default;
167 
168  void
169  PrintSelf(std::ostream & os, Indent indent) const override;
170 
171  void
172  FillClusterLabels(KdTreeNodeType * node, int closestIndex);
173 
180  {
181  public:
182  CandidateVector() = default;
183 
184  struct Candidate
185  {
188  int Size;
189  }; // end of struct
190 
191  virtual ~CandidateVector() = default;
192 
194  int
195  Size() const
196  {
197  return static_cast<int>(m_Candidates.size());
198  }
199 
202  void
204  {
205  this->m_MeasurementVectorSize = NumericTraits<ParameterType>::GetLength(centroids[0]);
206  m_Candidates.resize(centroids.size());
207  for (unsigned int i = 0; i < centroids.size(); ++i)
208  {
209  Candidate candidate;
210  candidate.Centroid = centroids[i];
211  NumericTraits<CentroidType>::SetLength(candidate.WeightedCentroid, m_MeasurementVectorSize);
212  candidate.WeightedCentroid.Fill(0.0);
213  candidate.Size = 0;
214  m_Candidates[i] = candidate;
215  }
216  }
220  void
222  {
223  centroids.resize(this->Size());
224  for (unsigned int i = 0; i < static_cast<unsigned int>(this->Size()); ++i)
225  {
226  centroids[i] = m_Candidates[i].Centroid;
227  }
228  }
233  void
235  {
236  for (unsigned int i = 0; i < static_cast<unsigned int>(this->Size()); ++i)
237  {
238  if (m_Candidates[i].Size > 0)
239  {
240  for (unsigned int j = 0; j < m_MeasurementVectorSize; ++j)
241  {
242  m_Candidates[i].Centroid[j] =
243  m_Candidates[i].WeightedCentroid[j] / static_cast<double>(m_Candidates[i].Size);
244  }
245  }
246  }
247  }
251  Candidate &
252  operator[](int index)
253  {
254  return m_Candidates[index];
255  }
256 
257  private:
259  std::vector<Candidate> m_Candidates;
260 
262  MeasurementVectorSizeType m_MeasurementVectorSize{ 0 };
263  }; // end of class
264 
270  double
271  GetSumOfSquaredPositionChanges(InternalParametersType & previous, InternalParametersType & current);
272 
275  int
276  GetClosestCandidate(ParameterType & measurements, std::vector<int> & validIndexes);
277 
279  bool
280  IsFarther(ParameterType & pointA,
281  ParameterType & pointB,
282  MeasurementVectorType & lowerBound,
283  MeasurementVectorType & upperBound);
284 
287  void
288  Filter(KdTreeNodeType * node,
289  std::vector<int> validIndexes,
290  MeasurementVectorType & lowerBound,
291  MeasurementVectorType & upperBound);
292 
294  void
295  CopyParameters(InternalParametersType & source, InternalParametersType & target);
296 
298  void
299  CopyParameters(ParametersType & source, InternalParametersType & target);
300 
302  void
303  CopyParameters(InternalParametersType & source, ParametersType & target);
304 
306  void
307  GetPoint(ParameterType & point, MeasurementVectorType measurements);
308 
309  void
310  PrintPoint(ParameterType & point);
311 
312 private:
314  int m_CurrentIteration{ 0 };
315 
317  int m_MaximumIteration{ 100 };
318 
320  double m_CentroidPositionChanges{ 0.0 };
321 
324  double m_CentroidPositionChangesThreshold{ 0.0 };
325 
327  typename TKdTree::Pointer m_KdTree{};
328 
331 
333  ParametersType m_Parameters{};
334 
335  CandidateVector m_CandidateVector{};
336 
337  ParameterType m_TempVertex{};
338 
339  bool m_UseClusterLabels{ false };
340  bool m_GenerateClusterLabels{ false };
341  ClusterLabelsType m_ClusterLabels{};
342  MeasurementVectorSizeType m_MeasurementVectorSize{ 0 };
343  MembershipFunctionVectorObjectPointer m_MembershipFunctionsObject{};
344 }; // end of class
345 } // end of namespace Statistics
346 } // end of namespace itk
347 
348 #ifndef ITK_MANUAL_INSTANTIATION
349 # include "itkKdTreeBasedKmeansEstimator.hxx"
350 #endif
351 
352 #endif
itk::Statistics::DistanceToCentroidMembershipFunction
DistanceToCentroidMembershipFunction models class membership using a distance metric.
Definition: itkDistanceToCentroidMembershipFunction.h:45
Pointer
SmartPointer< Self > Pointer
Definition: itkAddImageFilter.h:93
itk::SimpleDataObjectDecorator
Decorates any "simple" data type (data types without smart pointers) with a DataObject API.
Definition: itkSimpleDataObjectDecorator.h:66
ConstPointer
SmartPointer< const Self > ConstPointer
Definition: itkAddImageFilter.h:94
itk::Statistics::KdTreeBasedKmeansEstimator::DistanceToCentroidMembershipFunctionPointer
typename DistanceToCentroidMembershipFunctionType::Pointer DistanceToCentroidMembershipFunctionPointer
Definition: itkKdTreeBasedKmeansEstimator.h:110
itk::Statistics::KdTreeBasedKmeansEstimator::MembershipFunctionVectorObjectPointer
typename MembershipFunctionVectorObjectType::Pointer MembershipFunctionVectorObjectPointer
Definition: itkKdTreeBasedKmeansEstimator.h:116
itk::Size
Represent a n-dimensional size (bounds) of a n-dimensional image.
Definition: itkSize.h:69
itk::Statistics::KdTreeBasedKmeansEstimator::MeasurementVectorSizeType
unsigned int MeasurementVectorSizeType
Definition: itkKdTreeBasedKmeansEstimator.h:98
itkDistanceToCentroidMembershipFunction.h
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate::Centroid
CentroidType Centroid
Definition: itkKdTreeBasedKmeansEstimator.h:186
itk::NumericTraits::SetLength
static void SetLength(T &m, const unsigned int s)
Definition: itkNumericTraits.h:187
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::GetCentroids
void GetCentroids(InternalParametersType &centroids)
Definition: itkKdTreeBasedKmeansEstimator.h:221
itk::Statistics::KdTreeBasedKmeansEstimator::SampleType
typename TKdTree::SampleType SampleType
Definition: itkKdTreeBasedKmeansEstimator.h:94
itk::Statistics::MembershipFunctionBase
MembershipFunctionBase defines common interfaces for membership functions.
Definition: itkMembershipFunctionBase.h:58
itk::SmartPointer< Self >
itk::Indent
Control indentation during Print() invocation.
Definition: itkIndent.h:49
itk::Statistics::KdTreeBasedKmeansEstimator::KdTreeNodeType
typename TKdTree::KdTreeNodeType KdTreeNodeType
Definition: itkKdTreeBasedKmeansEstimator.h:90
itk::Statistics::KdTreeBasedKmeansEstimator::CentroidType
typename KdTreeNodeType::CentroidType CentroidType
Definition: itkKdTreeBasedKmeansEstimator.h:95
itk::Statistics::KdTreeBasedKmeansEstimator::InstanceIdentifier
typename TKdTree::InstanceIdentifier InstanceIdentifier
Definition: itkKdTreeBasedKmeansEstimator.h:93
itk::Statistics::KdTreeBasedKmeansEstimator::ClusterLabelsType
std::unordered_map< InstanceIdentifier, unsigned int > ClusterLabelsType
Definition: itkKdTreeBasedKmeansEstimator.h:158
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate
Definition: itkKdTreeBasedKmeansEstimator.h:184
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:55
itk::point
*par Constraints *The filter requires an image with at least two dimensions and a vector *length of at least The theory supports extension to scalar but *the implementation of the itk vector classes do not **The template parameter TRealType must be floating point(float or double) or *a user-defined "real" numerical type with arithmetic operations defined *sufficient to compute derivatives. **\par Performance *This filter will automatically multithread if run with *SetUsePrincipleComponents
itk::Statistics::KdTreeBasedKmeansEstimator
fast k-means algorithm implementation using k-d tree structure
Definition: itkKdTreeBasedKmeansEstimator.h:74
itkNumericTraitsArrayPixel.h
itk::Statistics::KdTreeBasedKmeansEstimator::MeasurementType
typename TKdTree::MeasurementType MeasurementType
Definition: itkKdTreeBasedKmeansEstimator.h:91
itkObject.h
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Size
int Size() const
Definition: itkKdTreeBasedKmeansEstimator.h:195
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnatomicalOrientation.h:29
itk::NumericTraits::GetLength
static unsigned int GetLength()
Definition: itkNumericTraits.h:210
itk::Statistics::KdTreeBasedKmeansEstimator::MembershipFunctionPointer
typename MembershipFunctionType::ConstPointer MembershipFunctionPointer
Definition: itkKdTreeBasedKmeansEstimator.h:113
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector
Candidate Vector.
Definition: itkKdTreeBasedKmeansEstimator.h:179
itk::Array< double >
itk::Object
Base class for most ITK classes.
Definition: itkObject.h:61
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::SetCentroids
void SetCentroids(InternalParametersType &centroids)
Definition: itkKdTreeBasedKmeansEstimator.h:203
itkSimpleDataObjectDecorator.h
itk::Statistics::KdTreeBasedKmeansEstimator::MeasurementVectorType
typename TKdTree::MeasurementVectorType MeasurementVectorType
Definition: itkKdTreeBasedKmeansEstimator.h:92
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate::WeightedCentroid
CentroidType WeightedCentroid
Definition: itkKdTreeBasedKmeansEstimator.h:187
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate::Size
int Size
Definition: itkKdTreeBasedKmeansEstimator.h:188
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::operator[]
Candidate & operator[](int index)
Definition: itkKdTreeBasedKmeansEstimator.h:252
itkEuclideanDistanceMetric.h
itk::Statistics::KdTreeBasedKmeansEstimator::InternalParametersType
std::vector< ParameterType > InternalParametersType
Definition: itkKdTreeBasedKmeansEstimator.h:103
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::UpdateCentroids
void UpdateCentroids()
Definition: itkKdTreeBasedKmeansEstimator.h:234
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::m_Candidates
std::vector< Candidate > m_Candidates
Definition: itkKdTreeBasedKmeansEstimator.h:259
itk::Statistics::KdTreeBasedKmeansEstimator::MembershipFunctionVectorType
std::vector< MembershipFunctionPointer > MembershipFunctionVectorType
Definition: itkKdTreeBasedKmeansEstimator.h:114