ITK  5.2.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  * 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 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  itkTypeMacro(KdTreeBasedKmeansEstimator, Object);
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);
127 
129  itkSetMacro(MaximumIteration, int);
130  itkGetConstMacro(MaximumIteration, int);
132 
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 
163 protected:
165  ~KdTreeBasedKmeansEstimator() override = default;
166 
167  void
168  PrintSelf(std::ostream & os, Indent indent) const override;
169 
170  void
171  FillClusterLabels(KdTreeNodeType * node, int closestIndex);
172 
179  {
180  public:
181  CandidateVector() = default;
182 
183  struct Candidate
184  {
187  int Size;
188  }; // end of struct
189 
190  virtual ~CandidateVector() = default;
191 
193  int
194  Size() const
195  {
196  return static_cast<int>(m_Candidates.size());
197  }
198 
201  void
203  {
204  this->m_MeasurementVectorSize = NumericTraits<ParameterType>::GetLength(centroids[0]);
205  m_Candidates.resize(centroids.size());
206  for (unsigned int i = 0; i < centroids.size(); i++)
207  {
208  Candidate candidate;
209  candidate.Centroid = centroids[i];
210  NumericTraits<CentroidType>::SetLength(candidate.WeightedCentroid, m_MeasurementVectorSize);
211  candidate.WeightedCentroid.Fill(0.0);
212  candidate.Size = 0;
213  m_Candidates[i] = candidate;
214  }
215  }
217 
219  void
221  {
222  unsigned int i;
223 
224  centroids.resize(this->Size());
225  for (i = 0; i < (unsigned int)this->Size(); i++)
226  {
227  centroids[i] = m_Candidates[i].Centroid;
228  }
229  }
230 
233  void
235  {
236  unsigned int i, j;
237 
238  for (i = 0; i < (unsigned int)this->Size(); i++)
239  {
240  if (m_Candidates[i].Size > 0)
241  {
242  for (j = 0; j < m_MeasurementVectorSize; j++)
243  {
244  m_Candidates[i].Centroid[j] = m_Candidates[i].WeightedCentroid[j] / double(m_Candidates[i].Size);
245  }
246  }
247  }
248  }
249 
251  Candidate & operator[](int index) { return m_Candidates[index]; }
252 
253  private:
255  std::vector<Candidate> m_Candidates;
256 
258  MeasurementVectorSizeType m_MeasurementVectorSize{ 0 };
259  }; // end of class
260 
266  double
267  GetSumOfSquaredPositionChanges(InternalParametersType & previous, InternalParametersType & current);
268 
271  int
272  GetClosestCandidate(ParameterType & measurements, std::vector<int> & validIndexes);
273 
275  bool
276  IsFarther(ParameterType & pointA,
277  ParameterType & pointB,
278  MeasurementVectorType & lowerBound,
279  MeasurementVectorType & upperBound);
280 
283  void
284  Filter(KdTreeNodeType * node,
285  std::vector<int> validIndexes,
286  MeasurementVectorType & lowerBound,
287  MeasurementVectorType & upperBound);
288 
290  void
291  CopyParameters(InternalParametersType & source, InternalParametersType & target);
292 
294  void
295  CopyParameters(ParametersType & source, InternalParametersType & target);
296 
298  void
299  CopyParameters(InternalParametersType & source, ParametersType & target);
300 
302  void
303  GetPoint(ParameterType & point, MeasurementVectorType measurements);
304 
305  void
306  PrintPoint(ParameterType & point);
307 
308 private:
310  int m_CurrentIteration{ 0 };
311 
313  int m_MaximumIteration{ 100 };
314 
316  double m_CentroidPositionChanges{ 0.0 };
317 
320  double m_CentroidPositionChangesThreshold{ 0.0 };
321 
323  typename TKdTree::Pointer m_KdTree;
324 
327 
330 
332 
334 
335  bool m_UseClusterLabels{ false };
336  bool m_GenerateClusterLabels{ false };
338  MeasurementVectorSizeType m_MeasurementVectorSize{ 0 };
340 }; // end of class
341 } // end of namespace Statistics
342 } // end of namespace itk
343 
344 #ifndef ITK_MANUAL_INSTANTIATION
345 # include "itkKdTreeBasedKmeansEstimator.hxx"
346 #endif
347 
348 #endif
itk::Statistics::DistanceToCentroidMembershipFunction
DistanceToCentroidMembershipFunction models class membership using a distance metric.
Definition: itkDistanceToCentroidMembershipFunction.h:45
itk::SimpleDataObjectDecorator
Decorates any "simple" data type (data types without smart pointers) with a DataObject API.
Definition: itkSimpleDataObjectDecorator.h:66
itk::Statistics::KdTreeBasedKmeansEstimator::DistanceToCentroidMembershipFunctionPointer
typename DistanceToCentroidMembershipFunctionType::Pointer DistanceToCentroidMembershipFunctionPointer
Definition: itkKdTreeBasedKmeansEstimator.h:110
itk::Statistics::KdTreeBasedKmeansEstimator::m_TempVertex
ParameterType m_TempVertex
Definition: itkKdTreeBasedKmeansEstimator.h:333
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:185
itk::NumericTraits::SetLength
static void SetLength(T &m, const unsigned int s)
Definition: itkNumericTraits.h:185
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::GetCentroids
void GetCentroids(InternalParametersType &centroids)
Definition: itkKdTreeBasedKmeansEstimator.h:220
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::Statistics::KdTreeBasedKmeansEstimator::m_Parameters
ParametersType m_Parameters
Definition: itkKdTreeBasedKmeansEstimator.h:329
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::m_KdTree
TKdTree::Pointer m_KdTree
Definition: itkKdTreeBasedKmeansEstimator.h:323
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:183
itk::LightObject
Light weight base class for most itk classes.
Definition: itkLightObject.h:59
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:194
itk
The "itk" namespace contains all Insight Segmentation and Registration Toolkit (ITK) classes....
Definition: itkAnnulusOperator.h:24
itk::NumericTraits::GetLength
static unsigned int GetLength()
Definition: itkNumericTraits.h:208
itk::Statistics::KdTreeBasedKmeansEstimator::MembershipFunctionPointer
typename MembershipFunctionType::ConstPointer MembershipFunctionPointer
Definition: itkKdTreeBasedKmeansEstimator.h:113
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector
Candidate Vector.
Definition: itkKdTreeBasedKmeansEstimator.h:178
itk::Array< double >
itk::Object
Base class for most ITK classes.
Definition: itkObject.h:60
itk::Statistics::KdTreeBasedKmeansEstimator::m_MembershipFunctionsObject
MembershipFunctionVectorObjectPointer m_MembershipFunctionsObject
Definition: itkKdTreeBasedKmeansEstimator.h:339
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::SetCentroids
void SetCentroids(InternalParametersType &centroids)
Definition: itkKdTreeBasedKmeansEstimator.h:202
itk::Statistics::KdTreeBasedKmeansEstimator::m_CandidateVector
CandidateVector m_CandidateVector
Definition: itkKdTreeBasedKmeansEstimator.h:331
itkSimpleDataObjectDecorator.h
itk::Statistics::KdTreeBasedKmeansEstimator::MeasurementVectorType
typename TKdTree::MeasurementVectorType MeasurementVectorType
Definition: itkKdTreeBasedKmeansEstimator.h:92
itk::Statistics::KdTreeBasedKmeansEstimator::m_ClusterLabels
ClusterLabelsType m_ClusterLabels
Definition: itkKdTreeBasedKmeansEstimator.h:337
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate::WeightedCentroid
CentroidType WeightedCentroid
Definition: itkKdTreeBasedKmeansEstimator.h:186
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::Candidate::Size
int Size
Definition: itkKdTreeBasedKmeansEstimator.h:187
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::operator[]
Candidate & operator[](int index)
Definition: itkKdTreeBasedKmeansEstimator.h:251
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::m_DistanceMetric
EuclideanDistanceMetric< ParameterType >::Pointer m_DistanceMetric
Definition: itkKdTreeBasedKmeansEstimator.h:326
itk::Statistics::KdTreeBasedKmeansEstimator::CandidateVector::m_Candidates
std::vector< Candidate > m_Candidates
Definition: itkKdTreeBasedKmeansEstimator.h:255
itk::Statistics::KdTreeBasedKmeansEstimator::MembershipFunctionVectorType
std::vector< MembershipFunctionPointer > MembershipFunctionVectorType
Definition: itkKdTreeBasedKmeansEstimator.h:114