itkKdTreeBasedKmeansEstimator.h

Go to the documentation of this file.

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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkKdTreeBasedKmeansEstimator.h,v $
  Language:  C++
  Date:      $Date: 2005/07/26 15:54:59 $
  Version:   $Revision: 1.18 $

  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

---