itkKdTreeBasedKmeansEstimator.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright Insight Software Consortium
 *
 *  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
 *
 *         http://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 "itksys/hash_map.hxx"

#include "itkObject.h"
#include "itkEuclideanDistanceMetric.h"
#include "itkDistanceToCentroidMembershipFunction.h"
#include "itkSimpleDataObjectDecorator.h"
#include "itkNumericTraitsArrayPixel.h"

namespace itk
{
namespace 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);

  itkTypeMacro(KdTreeBasedKmeansEstimator, Object);

  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 = itksys::hash_map< InstanceIdentifier, unsigned int >;

  itkSetMacro(UseClusterLabels, bool);
  itkGetConstMacro(UseClusterLabels, bool);

protected:
  KdTreeBasedKmeansEstimator();
  ~KdTreeBasedKmeansEstimator() override = default;

  void PrintSelf(std::ostream & os, Indent indent) const override;

  void FillClusterLabels(KdTreeNodeType *node, int closestIndex);

  class CandidateVector
  {
public:
    CandidateVector()  {}

    struct Candidate {
      CentroidType Centroid;
      CentroidType WeightedCentroid;
      int Size;
    };   // end of struct

    virtual ~CandidateVector() = default;

    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)
    {
      unsigned int i;

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

    void UpdateCentroids()
    {
      unsigned int i, j;

      for ( i = 0; i < (unsigned int)this->Size(); i++ )
        {
        if ( m_Candidates[i].Size > 0 )
          {
          for ( j = 0; j < m_MeasurementVectorSize; j++ )
            {
            m_Candidates[i].Centroid[j] =
              m_Candidates[i].WeightedCentroid[j]
              / 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
} // end of namespace Statistics
} // end of namespace itk

#ifndef ITK_MANUAL_INSTANTIATION
#include "itkKdTreeBasedKmeansEstimator.hxx"
#endif

#endif