itkKdTreeBasedKmeansEstimator.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright NumFOCUS
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
#ifndef itkKdTreeBasedKmeansEstimator_h
#define itkKdTreeBasedKmeansEstimator_h
 
#include <vector>
#include <unordered_map>
 
#include "itkObject.h"
#include "itkEuclideanDistanceMetric.h"
#include "itkDistanceToCentroidMembershipFunction.h"
#include "itkSimpleDataObjectDecorator.h"
#include "itkNumericTraitsArrayPixel.h"
 
namespace itk::Statistics
{
 
template <typename TKdTree>
class ITK_TEMPLATE_EXPORT KdTreeBasedKmeansEstimator : public Object
{
public:
  using Self = KdTreeBasedKmeansEstimator;
  using Superclass = Object;
  using Pointer = SmartPointer<Self>;
  using ConstPointer = SmartPointer<const Self>;

  itkNewMacro(Self);

  itkOverrideGetNameOfClassMacro(KdTreeBasedKmeansEstimator);

  using KdTreeNodeType = typename TKdTree::KdTreeNodeType;
  using MeasurementType = typename TKdTree::MeasurementType;
  using MeasurementVectorType = typename TKdTree::MeasurementVectorType;
  using InstanceIdentifier = typename TKdTree::InstanceIdentifier;
  using SampleType = typename TKdTree::SampleType;
  using CentroidType = typename KdTreeNodeType::CentroidType;

  using MeasurementVectorSizeType = unsigned int;

  using ParameterType = Array<double>;
  using InternalParametersType = std::vector<ParameterType>;
  using ParametersType = Array<double>;

  using DistanceToCentroidMembershipFunctionType = DistanceToCentroidMembershipFunction<MeasurementVectorType>;
 
  using DistanceToCentroidMembershipFunctionPointer = typename DistanceToCentroidMembershipFunctionType::Pointer;
 
  using MembershipFunctionType = MembershipFunctionBase<MeasurementVectorType>;
  using MembershipFunctionPointer = typename MembershipFunctionType::ConstPointer;
  using MembershipFunctionVectorType = std::vector<MembershipFunctionPointer>;
  using MembershipFunctionVectorObjectType = SimpleDataObjectDecorator<MembershipFunctionVectorType>;
  using MembershipFunctionVectorObjectPointer = typename MembershipFunctionVectorObjectType::Pointer;

  const MembershipFunctionVectorObjectType *
  GetOutput() const;

  itkSetMacro(Parameters, ParametersType);
  itkGetConstMacro(Parameters, ParametersType);

  itkSetMacro(MaximumIteration, int);
  itkGetConstMacro(MaximumIteration, int);

  itkSetMacro(CentroidPositionChangesThreshold, double);
  itkGetConstMacro(CentroidPositionChangesThreshold, double);

  void
  SetKdTree(TKdTree * tree);
 
  const TKdTree *
  GetKdTree() const;

  itkGetConstMacro(MeasurementVectorSize, MeasurementVectorSizeType);
 
  itkGetConstMacro(CurrentIteration, int);
  itkGetConstMacro(CentroidPositionChanges, double);

  void
  StartOptimization();
 
  using ClusterLabelsType = std::unordered_map<InstanceIdentifier, unsigned int>;
 
  itkSetMacro(UseClusterLabels, bool);
  itkGetConstMacro(UseClusterLabels, bool);
  itkBooleanMacro(UseClusterLabels);
 
protected:
  KdTreeBasedKmeansEstimator();
  ~KdTreeBasedKmeansEstimator() override = default;
 
  void
  PrintSelf(std::ostream & os, Indent indent) const override;
 
  void
  FillClusterLabels(KdTreeNodeType * node, int closestIndex);

  class CandidateVector
  {
  public:
    CandidateVector() = default;
 
    struct Candidate
    {
      CentroidType Centroid;
      CentroidType WeightedCentroid;
      int          Size;
    }; // end of struct
 
    virtual ~CandidateVector() = default;

    [[nodiscard]] int
    Size() const
    {
      return static_cast<int>(m_Candidates.size());
    }

    void
    SetCentroids(InternalParametersType & centroids)
    {
      this->m_MeasurementVectorSize = NumericTraits<ParameterType>::GetLength(centroids[0]);
      m_Candidates.resize(centroids.size());
      for (unsigned int i = 0; i < centroids.size(); ++i)
      {
        Candidate candidate;
        candidate.Centroid = centroids[i];
        NumericTraits<CentroidType>::SetLength(candidate.WeightedCentroid, m_MeasurementVectorSize);
        candidate.WeightedCentroid.Fill(0.0);
        candidate.Size = 0;
        m_Candidates[i] = candidate;
      }
    }

    void
    GetCentroids(InternalParametersType & centroids)
    {
      centroids.resize(this->Size());
      for (unsigned int i = 0; i < static_cast<unsigned int>(this->Size()); ++i)
      {
        centroids[i] = m_Candidates[i].Centroid;
      }
    }

    void
    UpdateCentroids()
    {
      for (unsigned int i = 0; i < static_cast<unsigned int>(this->Size()); ++i)
      {
        if (m_Candidates[i].Size > 0)
        {
          for (unsigned int j = 0; j < m_MeasurementVectorSize; ++j)
          {
            m_Candidates[i].Centroid[j] =
              m_Candidates[i].WeightedCentroid[j] / static_cast<double>(m_Candidates[i].Size);
          }
        }
      }
    }

    Candidate &
    operator[](int index)
    {
      return m_Candidates[index];
    }
 
  private:
    std::vector<Candidate> m_Candidates;

    MeasurementVectorSizeType m_MeasurementVectorSize{ 0 };
  }; // end of class

  double
  GetSumOfSquaredPositionChanges(InternalParametersType & previous, InternalParametersType & current);

  int
  GetClosestCandidate(ParameterType & measurements, std::vector<int> & validIndexes);

  bool
  IsFarther(ParameterType &         pointA,
            ParameterType &         pointB,
            MeasurementVectorType & lowerBound,
            MeasurementVectorType & upperBound);

  void
  Filter(KdTreeNodeType *        node,
         std::vector<int>        validIndexes,
         MeasurementVectorType & lowerBound,
         MeasurementVectorType & upperBound);

  void
  CopyParameters(InternalParametersType & source, InternalParametersType & target);

  void
  CopyParameters(ParametersType & source, InternalParametersType & target);

  void
  CopyParameters(InternalParametersType & source, ParametersType & target);

  void
  GetPoint(ParameterType & point, MeasurementVectorType measurements);
 
  void
  PrintPoint(ParameterType & point);
 
private:
  int m_CurrentIteration{ 0 };

  int m_MaximumIteration{ 100 };

  double m_CentroidPositionChanges{ 0.0 };

  double m_CentroidPositionChangesThreshold{ 0.0 };

  typename TKdTree::Pointer m_KdTree{};

  typename EuclideanDistanceMetric<ParameterType>::Pointer m_DistanceMetric{};

  ParametersType m_Parameters{};
 
  CandidateVector m_CandidateVector{};
 
  ParameterType m_TempVertex{};
 
  bool                                  m_UseClusterLabels{ false };
  bool                                  m_GenerateClusterLabels{ false };
  ClusterLabelsType                     m_ClusterLabels{};
  MeasurementVectorSizeType             m_MeasurementVectorSize{ 0 };
  MembershipFunctionVectorObjectPointer m_MembershipFunctionsObject{};
}; // end of class
} // namespace itk::Statistics
 
#ifndef ITK_MANUAL_INSTANTIATION
#  include "itkKdTreeBasedKmeansEstimator.hxx"
#endif
 
#endif