Numerics/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-03-04 15:23:51 $
  Version:   $Revision: 1.19 $

  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"

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, Obeject);

  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;

  void SetParameters(ParametersType& params)
    { m_Parameters = params; }

  ParametersType& GetParameters() 
    { return m_Parameters; }

  itkSetMacro( MaximumIteration, int );
  itkGetConstReferenceMacro( MaximumIteration, int ); 

  itkSetMacro( CentroidPositionChangesThreshold, double );   
  itkGetConstReferenceMacro( CentroidPositionChangesThreshold, double );   

  void SetKdTree(TKdTree* tree) 
    { 
    m_KdTree = tree; 
    m_MeasurementVectorSize = tree->GetMeasurementVectorSize();
    m_DistanceMetric->SetMeasurementVectorSize( m_MeasurementVectorSize );
    MeasurementVectorTraits::SetLength( m_TempVertex, m_MeasurementVectorSize );
    }

  TKdTree* GetKdTree() 
    { return m_KdTree.GetPointer(); }

  itkGetConstReferenceMacro( MeasurementVectorSize, MeasurementVectorSizeType );

  itkGetConstReferenceMacro( CurrentIteration, int);
  itkGetConstReferenceMacro( CentroidPositionChanges, double);

  void StartOptimization();

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

  void SetUseClusterLabels(bool flag)
    { m_UseClusterLabels = flag; }

  ClusterLabelsType* GetClusterLabels() 
    { return &m_ClusterLabels; }

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)
    {
    for (unsigned int i = 0; i < m_MeasurementVectorSize; i++)
      {
      point[i] = measurements[i];
      }
    }

  void PrintPoint(ParameterType &point)
    {
    std::cout << "[ ";
    for (unsigned int i = 0; i < m_MeasurementVectorSize; i++)
      {
      std::cout << point[i] << " ";
      }
    std::cout << "]";
    }

private:
  int m_CurrentIteration;

  int m_MaximumIteration;

  double m_CentroidPositionChanges;

  double m_CentroidPositionChangesThreshold;

  typename TKdTree::Pointer m_KdTree;

  typename EuclideanDistance< 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;
}; // end of class

} // end of namespace Statistics
} // end of namespace itk

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


#endif