ITK  4.1.0
Insight Segmentation and Registration Toolkit
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Private Types | Private Member Functions | Private Attributes
itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction > Class Template Reference

#include <itkImageKmeansModelEstimator.h>

+ Inheritance diagram for itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >:
+ Collaboration diagram for itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >:

List of all members.

Public Types

typedef vnl_matrix< double > CodebookMatrixOfDoubleType
typedef vnl_matrix< int > CodebookMatrixOfIntegerType
typedef SmartPointer< const SelfConstPointer
typedef
ImageRegionConstIterator
< TInputImage > 
InputImageConstIterator
typedef TInputImage::ConstPointer InputImageConstPointer
typedef ImageRegionIterator
< TInputImage > 
InputImageIterator
typedef TInputImage::PixelType InputImagePixelType
typedef TInputImage::Pointer InputImagePointer
typedef TInputImage InputImageType
typedef
TInputImage::PixelType::VectorType 
InputImageVectorType
typedef
TMembershipFunction::Pointer 
MembershipFunctionPointer
typedef SmartPointer< SelfPointer
typedef ImageKmeansModelEstimator Self
typedef
ImageModelEstimatorBase
< TInputImage,
TMembershipFunction > 
Superclass

Public Member Functions

virtual ::itk::LightObject::Pointer CreateAnother (void) const
virtual CodebookMatrixOfDoubleType GetCodebook () const
virtual int GetMaxSplitAttempts () const
virtual const char * GetNameOfClass () const
virtual double GetOffsetAdd () const
virtual double GetOffsetMultiply () const
CodebookMatrixOfDoubleType GetOutCodebook ()
virtual double GetThreshold () const
void SetCodebook (CodebookMatrixOfDoubleType InCodebook)
virtual void SetMaxSplitAttempts (int _arg)
virtual void SetOffsetAdd (double _arg)
virtual void SetOffsetMultiply (double _arg)
virtual void SetThreshold (double _arg)

Static Public Member Functions

static Pointer New ()

Protected Member Functions

void Allocate ()
void GenerateData ()
void PrintKmeansAlgorithmResults ()

Private Types

typedef TInputImage::SizeType ImageSizeType
typedef
TInputImage::PixelType::VectorType 
InputPixelVectorType

Private Member Functions

void EstimateKmeansModelParameters ()
virtual void EstimateModels ()
 ImageKmeansModelEstimator (const Self &)
void NearestNeighborSearchBasic (double *distortion)
void operator= (const Self &)
void Perturb (double *oldCodeword, int scale, double *newCodeword)
void Reallocate (int oldSize, int newSize)
void SplitCodewords (int currentSize, int numDesired, int scale)
int WithCodebookUseGLA ()
int WithoutCodebookUseLBG ()

Private Attributes

CodebookMatrixOfDoubleType m_Centroid
CodebookMatrixOfDoubleType m_Codebook
CodebookMatrixOfDoubleType m_CodewordDistortion
CodebookMatrixOfIntegerType m_CodewordHistogram
SizeValueType m_CurrentNumberOfCodewords
double m_DoubleMaximum
int m_MaxSplitAttempts
SizeValueType m_NumberOfCodewords
double m_OffsetAdd
double m_OffsetMultiply
double m_OutputDistortion
int m_OutputNumberOfEmptyCells
double m_Threshold
bool m_ValidInCodebook
SizeValueType m_VectorDimension
CodebookMatrixOfDoubleType GetKmeansResults (void)
 ImageKmeansModelEstimator ()
 ~ImageKmeansModelEstimator ()
virtual void PrintSelf (std::ostream &os, Indent indent) const

Detailed Description

template<class TInputImage, class TMembershipFunction>
class itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >

Base class for ImageKmeansModelEstimator object.

itkImageKmeansModelEstimator generates the kmeans model (cluster centers). This object performs clustering of data sets into different clusters, either using user-provided seed points as an initial guess or generating the clusters using a recursive approach when the user provides the number of desired clusters. Each cluster is represented by its cluster center. The two algorithms used are the generalized Lloyd algorithm (GLA) and the Linde-Buzo-Gray algorithm. The cluster centers are also referred to as codewords and a table of cluster centers is referred as a codebook.

As required by the GLA algorithm, the initial seed cluster should contain approximate centers of clusters. The GLA algorithm genrates updated cluster centers that result in a lower distortion than the input seed cluster when the input vectors are mapped/classified/labelled using the given codebooks.

If no codebook is provided, the Linde-Buzo-Gray algorithm is used. This algorithm uses the GLA algorithm at its core to generate the centroids of the input vectors (data). However, since there is no initial codebook, LBG first creates a one word codebook (or centroid of one cluster comprising of all the input training vectors). The LBG uses codeword or centroid splitting to create an increasing number of clusters. Each new set of clusters are optimized using the GLA algorithm. The number of clusters increases as $2^{n}$ n= 0, 1, ... The codebook is expected to be in the form of a vnl matrix, where there are N rows, each row representing the cluster mean of a given cluster. The number of columns in the codebook should be equal to the input image vector dimension.

The threshold parameter controls the ''optimality'' of the returned codebook, where optimality is related to the least possible mean-squared error distortion that can be found by the algorithm. For larger thresholds, the result will be less optimal. For smaller thresholds, the result will be more optimal. If a more optimal result is desired, then the algorithm will take longer to complete. A reasonable threshold value is 0.01.

If, during the operation of the algorithm, there are any unused clusters or cells, the m_OffsetAdd and m_OffsetMultiply parameters are used to split the cells with the highest distortion. This function will attempt to fill empty cells up to 10 times (unless the overall distortion is zero). Using 0.01 is a reasonable default values for the m_OffsetAdd and m_OffsetMultiply parameters.

If the GLA is unable to resolve the data into the desired number of clusters or cells, only the codewords which were used will be returned.

In terms of clustering, codewords are cluster centers, and a codebook is a table containing all cluster centers. The GLA produces results that are equivalent to the K-means clustering algorithm.

For more information about the algorithms, see A. Gersho and R. M. Gray, {Vector Quantization and Signal Compression}, Kluwer Academic Publishers, Boston, MA, 1992.

This object supports data handling of multiband images. The object accepts the input image in vector format only, where each pixel is a vector and each element of the vector corresponds to an entry from 1 particular band of a multiband dataset. A single band image is treated as a vector image with a single element for every vector.

This function is templated over the type of input image. In addition, a second parameter for the MembershipFunction needs to be specified. In this case a Membership function that store cluster centroids models needs to be specified.

The Update() function enables the calculation of the various models, creates the membership function objects and populates them.

Note: There is a second implementation of k-means algorithm in ITK under the itk::statistics namespace. While this algorithm (GLA/LBG based algorithm) is memory efficient, the other algorithm is time efficient.

See also:
KdTreeBasedKmeansEstimator, WeightedCentroidKdTreeGenerator, KdTree
ScalarImageKmeansImageFilter
Wiki Examples:

Definition at line 131 of file itkImageKmeansModelEstimator.h.


Member Typedef Documentation

template<class TInputImage , class TMembershipFunction >
typedef vnl_matrix< double > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::CodebookMatrixOfDoubleType

Type definition for a double matrix.

Definition at line 170 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef vnl_matrix< int > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::CodebookMatrixOfIntegerType

Type definition for an integer vector.

Definition at line 173 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef SmartPointer< const Self > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::ConstPointer
template<class TInputImage , class TMembershipFunction >
typedef TInputImage::SizeType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::ImageSizeType [private]

Definition at line 239 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef ImageRegionConstIterator< TInputImage > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImageConstIterator

Definition at line 164 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TInputImage::ConstPointer itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImageConstPointer

Definition at line 152 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef ImageRegionIterator< TInputImage > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImageIterator

Type definition for the input image iterator type.

Definition at line 162 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TInputImage::PixelType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImagePixelType

Type definition for the input image pixel type.

Definition at line 159 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TInputImage::Pointer itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImagePointer
template<class TInputImage , class TMembershipFunction >
typedef TInputImage itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImageType

Type definition for the input image.

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

Definition at line 147 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TInputImage::PixelType::VectorType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputImageVectorType

Type definition for the vector associated with input image pixel type.

Definition at line 156 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TInputImage::PixelType::VectorType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::InputPixelVectorType [private]

Set up the vector to store the image data.

Definition at line 242 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef TMembershipFunction::Pointer itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::MembershipFunctionPointer

Type definitions for the membership function .

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

Definition at line 167 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef SmartPointer< Self > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Pointer
template<class TInputImage , class TMembershipFunction >
typedef ImageKmeansModelEstimator itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Self

Standard class typedefs.

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

Definition at line 136 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
typedef ImageModelEstimatorBase< TInputImage, TMembershipFunction > itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Superclass

Constructor & Destructor Documentation

template<class TInputImage , class TMembershipFunction >
itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::ImageKmeansModelEstimator ( ) [protected]

Return the codebook/cluster centers.

template<class TInputImage , class TMembershipFunction >
itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::~ImageKmeansModelEstimator ( ) [protected]

Return the codebook/cluster centers.

template<class TInputImage , class TMembershipFunction >
itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::ImageKmeansModelEstimator ( const Self ) [private]

Member Function Documentation

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Allocate ( ) [protected]

Allocate memory for the output model.

template<class TInputImage , class TMembershipFunction >
virtual::itk::LightObject::Pointer itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::CreateAnother ( void  ) const [virtual]

Create an object from an instance, potentially deferring to a factory. This method allows you to create an instance of an object that is exactly the same type as the referring object. This is useful in cases where an object has been cast back to a base class.

Reimplemented from itk::LightProcessObject.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::EstimateKmeansModelParameters ( ) [private]
template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::EstimateModels ( ) [private, virtual]

A function that generates the cluster centers (model) corresponding to the estimates of the cluster centers (in the initial codebook). If no codebook is provided, then use the number of classes to determine the cluster centers or the Kmeans model. This is the the base function to call the K-means classifier.

Implements itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GenerateData ( ) [protected, virtual]

Starts the image modelling process

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

template<class TInputImage , class TMembershipFunction >
virtual CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetCodebook ( ) const [virtual]

Get the cluster centers.

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetKmeansResults ( void  ) [inline]

Return the codebook/cluster centers.

Definition at line 209 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
virtual int itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetMaxSplitAttempts ( ) const [virtual]

Get the manimum number of attempts to split a codeword.

template<class TInputImage , class TMembershipFunction >
virtual const char* itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetNameOfClass ( ) const [virtual]

Run-time type information (and related methods).

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

template<class TInputImage , class TMembershipFunction >
virtual double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetOffsetAdd ( ) const [virtual]

Get the offset add parameter.

template<class TInputImage , class TMembershipFunction >
virtual double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetOffsetMultiply ( ) const [virtual]

Get the offset multiplication parameter.

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetOutCodebook ( ) [inline]

Get the optimized codebook or the centroids of the clusters.

Definition at line 182 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
virtual double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::GetThreshold ( ) const [virtual]

Get the threshold parameter.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::NearestNeighborSearchBasic ( double *  distortion) [private]
template<class TInputImage , class TMembershipFunction >
static Pointer itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::New ( ) [static]

Method for creation through the object factory.

Reimplemented from itk::LightProcessObject.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::operator= ( const Self ) [private]

This method causes the filter to generate its output.

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Perturb ( double *  oldCodeword,
int  scale,
double *  newCodeword 
) [private]
template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::PrintKmeansAlgorithmResults ( ) [protected]

Print out the results on the screen for visual feedback.

template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::PrintSelf ( std::ostream &  os,
Indent  indent 
) const [protected, virtual]

Return the codebook/cluster centers.

Reimplemented from itk::ImageModelEstimatorBase< TInputImage, TMembershipFunction >.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::Reallocate ( int  oldSize,
int  newSize 
) [private]
template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SetCodebook ( CodebookMatrixOfDoubleType  InCodebook)

Set the cluster centers.

template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SetMaxSplitAttempts ( int  _arg) [virtual]

Set the maximum number of attempts to split a codeword.

template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SetOffsetAdd ( double  _arg) [virtual]

Set the offset add parameter.

template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SetOffsetMultiply ( double  _arg) [virtual]

Set the offset multiplication parameter.

template<class TInputImage , class TMembershipFunction >
virtual void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SetThreshold ( double  _arg) [virtual]

Set the threshold parameter.

template<class TInputImage , class TMembershipFunction >
void itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::SplitCodewords ( int  currentSize,
int  numDesired,
int  scale 
) [private]
template<class TInputImage , class TMembershipFunction >
int itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::WithCodebookUseGLA ( ) [private]
template<class TInputImage , class TMembershipFunction >
int itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::WithoutCodebookUseLBG ( ) [private]

Member Data Documentation

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_Centroid [private]

Definition at line 264 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_Codebook [private]

Definition at line 261 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfDoubleType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_CodewordDistortion [private]

Definition at line 282 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
CodebookMatrixOfIntegerType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_CodewordHistogram [private]

Definition at line 281 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
SizeValueType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_CurrentNumberOfCodewords [private]

Definition at line 279 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_DoubleMaximum [private]

Definition at line 273 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
int itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_MaxSplitAttempts [private]

Definition at line 269 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
SizeValueType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_NumberOfCodewords [private]

Definition at line 278 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_OffsetAdd [private]

Definition at line 267 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_OffsetMultiply [private]

Definition at line 268 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_OutputDistortion [private]

Definition at line 274 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
int itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_OutputNumberOfEmptyCells [private]

Definition at line 275 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
double itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_Threshold [private]

Definition at line 266 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
bool itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_ValidInCodebook [private]

Definition at line 272 of file itkImageKmeansModelEstimator.h.

template<class TInputImage , class TMembershipFunction >
SizeValueType itk::ImageKmeansModelEstimator< TInputImage, TMembershipFunction >::m_VectorDimension [private]

Definition at line 277 of file itkImageKmeansModelEstimator.h.


The documentation for this class was generated from the following file: