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< class TKdTree >
class ITK_EXPORT KdTreeBasedKmeansEstimator:
  public Object
{
public:
  typedef KdTreeBasedKmeansEstimator Self;
  typedef Object                     Superclass;
  typedef SmartPointer< Self >       Pointer;
  typedef SmartPointer< const Self > ConstPointer;

  itkNewMacro(Self);

  itkTypeMacro(KdTreeBasedKmeansEstimator, Object);

  typedef typename TKdTree::KdTreeNodeType        KdTreeNodeType;
  typedef typename TKdTree::MeasurementType       MeasurementType;
  typedef typename TKdTree::MeasurementVectorType MeasurementVectorType;
  typedef typename TKdTree::InstanceIdentifier    InstanceIdentifier;
  typedef typename TKdTree::SampleType            SampleType;
  typedef typename KdTreeNodeType::CentroidType   CentroidType;

  typedef unsigned int MeasurementVectorSizeType;

  typedef Array< double >              ParameterType;
  typedef std::vector< ParameterType > InternalParametersType;
  typedef Array< double >              ParametersType;

  typedef DistanceToCentroidMembershipFunction< MeasurementVectorType >
  DistanceToCentroidMembershipFunctionType;

  typedef typename DistanceToCentroidMembershipFunctionType::Pointer
  DistanceToCentroidMembershipFunctionPointer;

  typedef MembershipFunctionBase< MeasurementVectorType > MembershipFunctionType;
  typedef typename MembershipFunctionType::ConstPointer   MembershipFunctionPointer;
  typedef std::vector< MembershipFunctionPointer >        MembershipFunctionVectorType;
  typedef SimpleDataObjectDecorator<
    MembershipFunctionVectorType >                        MembershipFunctionVectorObjectType;
  typedef typename
  MembershipFunctionVectorObjectType::Pointer MembershipFunctionVectorObjectPointer;

  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();

  typedef itksys::hash_map< InstanceIdentifier, unsigned int > ClusterLabelsType;

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

protected:
  KdTreeBasedKmeansEstimator();
  virtual ~KdTreeBasedKmeansEstimator() {}

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

  void FillClusterLabels(KdTreeNodeType *node, int closestIndex);

  class CandidateVector
  {
public:
    CandidateVector() {}

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

    virtual ~CandidateVector() {}

    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;
  };  // 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;

  int m_MaximumIteration;

  double m_CentroidPositionChanges;

  double m_CentroidPositionChangesThreshold;

  typename TKdTree::Pointer m_KdTree;

  typename EuclideanDistanceMetric< ParameterType >::Pointer m_DistanceMetric;

  ParametersType m_Parameters;

  CandidateVector m_CandidateVector;

  ParameterType m_TempVertex;

  bool                                  m_UseClusterLabels;
  bool                                  m_GenerateClusterLabels;
  ClusterLabelsType                     m_ClusterLabels;
  MeasurementVectorSizeType             m_MeasurementVectorSize;
  MembershipFunctionVectorObjectPointer m_MembershipFunctionsObject;
};  // end of class
} // end of namespace Statistics
} // end of namespace itk

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

#endif