Review/Statistics/itkKdTreeBasedKmeansEstimator.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkKdTreeBasedKmeansEstimator.h,v $
  Language:  C++
  Date:      $Date: 2009-06-15 12:40:37 $
  Version:   $Revision: 1.2 $

  Copyright (c) Insight Software Consortium. All rights reserved.
  See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even 
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/
#ifndef __itkKdTreeBasedKmeansEstimator_h
#define __itkKdTreeBasedKmeansEstimator_h

#include <vector>
#include "itk_hash_map.h"

#include "itkObject.h"
#include "itkMeasurementVectorTraits.h"
#include "itkEuclideanDistanceMetric.h"
#include "itkDistanceToCentroidMembershipFunction.h"
#include "itkSimpleDataObjectDecorator.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 itk::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 = MeasurementVectorTraits::GetLength( centroids[0] );
      m_Candidates.resize(centroids.size());
      for (unsigned int i = 0; i < centroids.size(); i++)
        {
          Candidate candidate;
          candidate.Centroid = centroids[i];
          MeasurementVectorTraits::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.txx"
#endif

#endif