#include <itkKLMRegionGrowImageFilter.h>

Inheritance diagram for itk::KLMRegionGrowImageFilter< TInputImage, TOutputImage >:

Collaboration diagram for itk::KLMRegionGrowImageFilter< TInputImage, TOutputImage >:

Public Types
typedef KLMSegmentationBorder	BorderType
typedef SmartPointer< const Self >	ConstPointer
typedef Superclass::GridSizeType	GridSizeType
typedef ImageRegionConstIterator < TInputImage >	InputImageConstIterator
typedef TInputImage::ConstPointer	InputImageConstPointer
typedef TInputImage::IndexType	InputImageIndexType
typedef ImageRegionIterator < TInputImage >	InputImageIterator
typedef TInputImage::PixelType	InputImagePixelType
typedef TInputImage::Pointer	InputImagePointer
typedef TInputImage	InputImageType
typedef TInputImage::PixelType::VectorType	InputImageVectorType
typedef TInputImage::RegionType	InputRegionType
typedef KLMDynamicBorderArray < BorderType >	KLMSegmentationBorderArrayPtr
typedef LabelImageType::IndexType	LabelImageIndexType
typedef ImageRegionIterator < LabelImageType >	LabelImageIterator
typedef LabelImageType::PixelType	LabelImagePixelType
typedef LabelImageType::Pointer	LabelImagePointer
typedef Image< RegionLabelType, itkGetStaticConstMacro(LabelImageDimension) >	LabelImageType
typedef vnl_vector< double >	MeanRegionIntensityType
typedef TOutputImage::IndexType	OutputImageIndexType
typedef ImageRegionIterator < TOutputImage >	OutputImageIterator
typedef TOutputImage::PixelType	OutputImagePixelType
typedef TOutputImage::Pointer	OutputImagePointer
typedef TOutputImage	OutputImageType
typedef TOutputImage::PixelType::VectorType	OutputImageVectorType
typedef SmartPointer< Self >	Pointer
typedef KLMSegmentationRegion::RegionLabelType	RegionLabelType
typedef KLMRegionGrowImageFilter	Self
typedef RegionGrowImageFilter < TInputImage, TOutputImage >	Superclass
Public Types inherited from itk::RegionGrowImageFilter< TInputImage, TOutputImage >
Public Types inherited from itk::ImageToImageFilter< TInputImage, TOutputImage >
typedef InputImageType::RegionType	InputImageRegionType
typedef Superclass::OutputImageRegionType	OutputImageRegionType
Public Types inherited from itk::ImageSource< TOutputImage >
typedef Superclass::DataObjectIdentifierType	DataObjectIdentifierType
typedef DataObject::Pointer	DataObjectPointer
typedef Superclass::DataObjectPointerArraySizeType	DataObjectPointerArraySizeType
Public Types inherited from itk::ProcessObject
typedef std::vector < DataObjectPointer >	DataObjectPointerArray
typedef std::vector < DataObjectIdentifierType >	NameArray
Public Types inherited from itk::Object
Public Types inherited from itk::LightObject

Public Member Functions
virtual ::itk::LightObject::Pointer	CreateAnother (void) const
LabelImagePointer	GetLabelledImage (void)
virtual const char *	GetNameOfClass () const
void	PrintAlgorithmBorderStats (void)
void	PrintAlgorithmRegionStats (void)
	typedef (Concept::HasNumericTraits< typename InputImagePixelType::ValueType >) InputHasNumericTraitsCheck
	typedef (Concept::SameDimension< itkGetStaticConstMacro(InputImageDimension), itkGetStaticConstMacro(OutputImageDimension) >) SameDimension

virtual void	SetMaximumLambda (double _arg)
virtual const double &	GetMaximumLambda ()

virtual void	SetNumberOfRegions (unsigned int _arg)
virtual const unsigned int &	GetNumberOfRegions ()
Public Member Functions inherited from itk::RegionGrowImageFilter< TInputImage, TOutputImage >
virtual void	SetGridSize (GridSizeType _arg)
virtual const GridSizeType &	GetGridSize ()
virtual void	SetMaximumNumberOfRegions (unsigned int _arg)
virtual const unsigned int &	GetMaximumNumberOfRegions ()
Public Member Functions inherited from itk::ImageToImageFilter< TInputImage, TOutputImage >
const InputImageType *	GetInput (void) const
const InputImageType *	GetInput (unsigned int idx) const
virtual void	PopBackInput ()
virtual void	PopFrontInput ()
virtual void	PushBackInput (const InputImageType *image)
virtual void	PushFrontInput (const InputImageType *image)
virtual void	SetInput (const InputImageType *image)
virtual void	SetInput (unsigned int, const TInputImage *image)
Public Member Functions inherited from itk::ImageSource< TOutputImage >
OutputImageType *	GetOutput (unsigned int idx)
virtual void	GraftNthOutput (unsigned int idx, DataObject *output)
virtual void	GraftOutput (DataObject *output)
virtual void	GraftOutput (const DataObjectIdentifierType &key, DataObject *output)
OutputImageType *	GetOutput (void)
const OutputImageType *	GetOutput (void) const
virtual ProcessObject::DataObjectPointer	MakeOutput (ProcessObject::DataObjectPointerArraySizeType idx)
Public Member Functions inherited from itk::ProcessObject
virtual void	AbortGenerateDataOff ()
virtual void	AbortGenerateDataOn ()
virtual const bool &	GetAbortGenerateData ()
NameArray	GetInputNames () const
MultiThreader *	GetMultiThreader () const
DataObjectPointerArraySizeType	GetNumberOfIndexedInputs () const
DataObjectPointerArraySizeType	GetNumberOfInputs () const
DataObjectPointerArraySizeType	GetNumberOfOutputs () const
virtual DataObjectPointerArraySizeType	GetNumberOfValidRequiredInputs () const
NameArray	GetOutputNames () const
virtual const float &	GetProgress ()
NameArray	GetRequiredInputNames () const
bool	HasInput (const DataObjectIdentifierType &key) const
bool	HasOutput (const DataObjectIdentifierType &key) const
virtual DataObjectPointer	MakeOutput (const DataObjectIdentifierType &)
virtual void	PrepareOutputs ()
virtual void	PropagateRequestedRegion (DataObject *output)
virtual void	ResetPipeline ()
virtual void	SetAbortGenerateData (bool _arg)
virtual void	SetProgress (float _arg)
virtual void	Update ()
virtual void	UpdateLargestPossibleRegion ()
virtual void	UpdateOutputData (DataObject *output)
virtual void	UpdateOutputInformation ()
void	UpdateProgress (float amount)
DataObjectPointerArray	GetInputs ()
DataObjectPointerArray	GetOutputs ()
DataObjectPointerArray	GetIndexedInputs ()
DataObjectPointerArray	GetIndexedOutputs ()
DataObjectPointerArraySizeType	GetNumberOfIndexedOutputs () const
virtual void	SetReleaseDataFlag (bool flag)
virtual bool	GetReleaseDataFlag () const
void	ReleaseDataFlagOn ()
void	ReleaseDataFlagOff ()
virtual void	SetReleaseDataBeforeUpdateFlag (bool _arg)
virtual const bool &	GetReleaseDataBeforeUpdateFlag ()
virtual void	ReleaseDataBeforeUpdateFlagOn ()
virtual void	ReleaseDataBeforeUpdateFlagOff ()
virtual void	SetNumberOfThreads (ThreadIdType _arg)
virtual const ThreadIdType &	GetNumberOfThreads ()
Public Member Functions inherited from itk::Object
unsigned long	AddObserver (const EventObject &event, Command *)
unsigned long	AddObserver (const EventObject &event, Command *) const
virtual void	DebugOff () const
virtual void	DebugOn () const
Command *	GetCommand (unsigned long tag)
bool	GetDebug () const
MetaDataDictionary &	GetMetaDataDictionary (void)
const MetaDataDictionary &	GetMetaDataDictionary (void) const
virtual unsigned long	GetMTime () const
virtual const TimeStamp &	GetTimeStamp () const
bool	HasObserver (const EventObject &event) const
void	InvokeEvent (const EventObject &)
void	InvokeEvent (const EventObject &) const
virtual void	Modified () const
virtual void	Register () const
void	RemoveAllObservers ()
void	RemoveObserver (unsigned long tag)
void	SetDebug (bool debugFlag) const
void	SetMetaDataDictionary (const MetaDataDictionary &rhs)
virtual void	SetReferenceCount (int)
virtual void	UnRegister () const
Public Member Functions inherited from itk::LightObject
virtual void	Delete ()
virtual int	GetReferenceCount () const
	itkCloneMacro (Self)
void	Print (std::ostream &os, Indent indent=0) const

Static Public Member Functions
static Pointer	New ()

Static Public Attributes
static const unsigned int	InputImageDimension = TInputImage::ImageDimension
static const unsigned int	InputImageVectorDimension = InputImagePixelType::Dimension
static const RegionLabelType	LabelImageDimension = InputImageDimension
static const unsigned int	OutputImageDimension = TOutputImage::ImageDimension
static const unsigned int	OutputImageVectorDimension = OutputImagePixelType::Dimension

Protected Member Functions
void	ApplyKLM ()
void	ApplyRegionGrowImageFilter ()
virtual void	EnlargeOutputRequestedRegion (DataObject *)
virtual void	GenerateData ()
virtual void	GenerateInputRequestedRegion ()
LabelImagePointer	GenerateLabelledImage (LabelImageType *labelImagePtr)
virtual void	GenerateOutputImage ()
void	InitializeKLM ()
virtual void	InitializeRegionParameters (InputRegionType region)
virtual void	MergeRegions ()
virtual void	ResolveRegions ()

	KLMRegionGrowImageFilter ()
	~KLMRegionGrowImageFilter ()
void	PrintSelf (std::ostream &os, Indent indent) const
Protected Member Functions inherited from itk::RegionGrowImageFilter< TInputImage, TOutputImage >
	RegionGrowImageFilter ()
	~RegionGrowImageFilter ()
Protected Member Functions inherited from itk::ImageToImageFilter< TInputImage, TOutputImage >
virtual void	CallCopyInputRegionToOutputRegion (OutputImageRegionType &destRegion, const InputImageRegionType &srcRegion)
virtual void	CallCopyOutputRegionToInputRegion (InputImageRegionType &destRegion, const OutputImageRegionType &srcRegion)
	ImageToImageFilter ()
virtual void	VerifyInputInformation ()
	~ImageToImageFilter ()
void	PushBackInput (const DataObject *input)
void	PushFrontInput (const DataObject *input)
Protected Member Functions inherited from itk::ImageSource< TOutputImage >
virtual void	AfterThreadedGenerateData ()
virtual void	AllocateOutputs ()
virtual void	BeforeThreadedGenerateData ()
	ImageSource ()
virtual unsigned int	SplitRequestedRegion (unsigned int i, unsigned int num, OutputImageRegionType &splitRegion)
virtual void	ThreadedGenerateData (const OutputImageRegionType &outputRegionForThread, ThreadIdType threadId)
virtual	~ImageSource ()
Protected Member Functions inherited from itk::ProcessObject
virtual void	AddInput (DataObject *input)
virtual void	AddOutput (DataObject *output)
bool	AddRequiredInputName (const DataObjectIdentifierType &)
virtual void	CacheInputReleaseDataFlags ()
virtual void	GenerateOutputInformation ()
virtual void	GenerateOutputRequestedRegion (DataObject *output)
virtual const DataObjectPointerArraySizeType &	GetNumberOfRequiredInputs ()
virtual const DataObjectPointerArraySizeType &	GetNumberOfRequiredOutputs ()
bool	IsIndexedName (const DataObjectIdentifierType &) const
bool	IsRequiredInputName (const DataObjectIdentifierType &) const
	itkLegacyMacro (virtual void RemoveInput(DataObject *input))
	itkLegacyMacro (virtual void RemoveOutput(DataObject *output))
	itkLegacyMacro (void SetNumberOfInputs(DataObjectPointerArraySizeType num))
	itkLegacyMacro (void SetNumberOfOutputs(DataObjectPointerArraySizeType num))
DataObjectPointerArraySizeType	MakeIndexFromName (const DataObjectIdentifierType &) const
DataObjectIdentifierType	MakeNameFromIndex (DataObjectPointerArraySizeType) const
	ProcessObject ()
virtual void	PropagateResetPipeline ()
virtual void	ReleaseInputs ()
virtual void	RemoveInput (const DataObjectIdentifierType &key)
virtual void	RemoveInput (DataObjectPointerArraySizeType)
virtual void	RemoveOutput (const DataObjectIdentifierType &key)
virtual void	RemoveOutput (DataObjectPointerArraySizeType idx)
bool	RemoveRequiredInputName (const DataObjectIdentifierType &)
virtual void	RestoreInputReleaseDataFlags ()
virtual void	SetInput (const DataObjectIdentifierType &key, DataObject *input)
virtual void	SetNthInput (DataObjectPointerArraySizeType num, DataObject *input)
virtual void	SetNthOutput (DataObjectPointerArraySizeType num, DataObject *output)
void	SetNumberOfIndexedInputs (DataObjectPointerArraySizeType num)
void	SetNumberOfIndexedOutputs (DataObjectPointerArraySizeType num)
virtual void	SetNumberOfRequiredInputs (DataObjectPointerArraySizeType)
virtual void	SetNumberOfRequiredOutputs (DataObjectPointerArraySizeType _arg)
virtual void	SetOutput (const DataObjectIdentifierType &key, DataObject *output)
virtual void	SetPrimaryInput (DataObject *input)
virtual void	SetPrimaryOutput (DataObject *output)
void	SetRequiredInputNames (const NameArray &)
virtual void	VerifyPreconditions ()
	~ProcessObject ()
DataObject *	GetInput (const DataObjectIdentifierType &key)
const DataObject *	GetInput (const DataObjectIdentifierType &key) const
DataObject *	GetInput (DataObjectPointerArraySizeType)
const DataObject *	GetInput (DataObjectPointerArraySizeType idx) const
DataObject *	GetPrimaryInput ()
const DataObject *	GetPrimaryInput () const
DataObject *	GetOutput (const DataObjectIdentifierType &key)
const DataObject *	GetOutput (const DataObjectIdentifierType &key) const
DataObject *	GetOutput (DataObjectPointerArraySizeType idx)
const DataObject *	GetOutput (DataObjectPointerArraySizeType idx) const
DataObject *	GetPrimaryOutput ()
const DataObject *	GetPrimaryOutput () const
Protected Member Functions inherited from itk::Object
	Object ()
bool	PrintObservers (std::ostream &os, Indent indent) const
virtual void	SetTimeStamp (const TimeStamp &time)
virtual	~Object ()
Protected Member Functions inherited from itk::LightObject
virtual LightObject::Pointer	InternalClone () const
	LightObject ()
virtual void	PrintHeader (std::ostream &os, Indent indent) const
virtual void	PrintTrailer (std::ostream &os, Indent indent) const
virtual	~LightObject ()

Private Types
typedef TInputImage::SizeType	InputImageSizeType
typedef KLMSegmentationBorder::Pointer	KLMSegmentationBorderPtr
typedef KLMSegmentationRegion::Pointer	KLMSegmentationRegionPtr

Private Member Functions
	KLMRegionGrowImageFilter (const Self &)
void	operator= (const Self &)

Private Attributes
KLMSegmentationBorderArrayPtr *	m_BorderCandidate
std::vector < KLMSegmentationBorderArrayPtr >	m_BordersDynamicPointer
std::vector < KLMSegmentationBorderPtr >	m_BordersPointer
unsigned int	m_InitialNumberOfRegions
double	m_InitialRegionArea
MeanRegionIntensityType	m_InitialRegionMean
double	m_InternalLambda
double	m_MaximumLambda
unsigned int	m_NumberOfRegions
std::vector < KLMSegmentationRegionPtr >	m_RegionsPointer
double	m_TotalBorderLength

Detailed Description

template<class TInputImage, class TOutputImage>
class itk::KLMRegionGrowImageFilter< TInputImage, TOutputImage >

Base class for a region growing object that performs energy-based region growing for multiband images.

itkKLMRegionGrowImageFilter is the base class for the KLMRegionGrowImageFilter objects. This object performs energy-based region growing for multiband images. Since this is based on G. Koepfler,C. Lopez and J. M. Morel's work described below, the acronym KLM is added at the end of the object name.

The ApplyRegionGrowImageFilter() function implements the segmentation algorithm that partitions the input image into non-overlapping regions by minimizing an energy functional which trades off the similarity of regions against the length of their shared boundary. The heart of the process relies on the MergeRegion() method that calls a private function to perform the merging of region based on the piecewise constant KLM algorithm for region merging. For extensibility purposes, the MergeRegion() function is made virtual. Extensions can be made possible using function overloading or overriding the virtual function in a derived class. It starts by breaking the image into many small regions and fitting the regions to a polynomial model. The algorithm iteratively merges into one region the two adjoining regions which are most alike in terms of the specified polynomial model given the length of the border between the two regions. Internally, the energy functional is evaluated using a Lagrangian parameter called lambda which is also called the scale parameter as it controls the coarseness of the segmentation where a small value of lambda corresponds to a finer segmentation with more regions and a large value corresponds to a coarse segmentation with fewer regions. Since the algorithm grows regions by merging like regions, the internal value of lambda increases as the number of regions decreases.

The user can stop the merging of regions using the SetMaximumNumberOfRegions() and SetMaximumLambda() functions. The SetMaximumNumberOfRegions() function is publicly inherited from its base class and internally sets the m_MaximumNumberOfRegions parameter. The SetMaximumLambda() function sets the m_MaximumLambda parameter. If the number of regions in the image is equal to m_MaximumNumberOfRegions or if the internal energy functional becomes greater than m_MaximumLambda, then the merging iterations will stop. Note that a larger energy function value for m_MaximumLambda will result in fewer boundaries and fewer regions, while a smaller value for m_MaximumLambda will result in more boundaries and more regions. To have m_MaximumNumberOfRegions control exactly the number of output regions, m_MaximumLamda should be set to a very large number. To have m_MaximumLambda control exactly the number of output regions, m_MaximumNumberOfRegions should be set to 2. As a default value, m_MaximumLambda is set to 1000 and m_MaximumNumberOfRegions is set to 2.

Currently implementation puts equal weight to the multichannel values. In future improvements we plan to allow the user to control the weights associated with each individual channels.

It is templated over the type of input and output image. This object supports data handling of multiband images. The object accepts images in vector format, where each pixel is a vector and each element of the vector corresponds to an entry from 1 particular band of a multiband dataset. We expect the user to provide the input to the routine in vector format. A single band image is treated as a vector image with a single element for every vector.

This algorithm implementation takes a multiband image stored in vector format as input and produces two outputs. Using the ImageToImageFilter, the piecewise constant approximation image is the output calculated using the process update mechanism. The second output, i.e., the image with the region labels (segmentation image) is returned at users request by calling GetLabelledImage() function. This function returns a reference to the labelled image determined using the KLM algorithm. The algorithm supports 2D and 3D data sets only. The input image dimensions must be exact multiples of the user specified gridsizes. Appropriate padding must be performed by the user if any image which are not multiples of the gridsizes are used.

For more information about the algorithm, see G. Koepfler, C. Lopez and J. M. Morel, ``A Multiscale Algorithm for Image Segmentation by Variational Method,'' {SIAM Journal of Numerical Analysis}, vol. 31, pp. 282-299, 1994.

Algorithm details:

This function segments a two-dimensional input image into non-overlapping atomic regions $O_i, i=1,2,\ldots,N$ , where $ N $ is the total number of region, by minimizing the following energy functional (also known as the simplified Mumford and Shah functional): $E(u,K)=\int_{\Omega-K}||u(r,c)-g(r,c)||^2{d{\Omega}}+\lambda\cdot{L(K)}$ , where $\Omega$ denotes the domain of an image, $ g(r,c) $ is the input image, and $ u(r,c) $ is an approximation of . Furthermore, is defined to be piecewise constant in regions $ O_i $ . If $\partial O_i$ represents the boundary of the region, $K=\bigcup_{i=1}^N\partial{O_i}$ denotes the set of all region boundaries and $ L(K) $ is the total length of the boundaries. The parameter $\lambda$ controls the coarseness of the segmentation (i.e. a larger $\lambda$ will result in fewer boundaries).

Starting with small, piecewise-constant initial regions the algorithm iteratively merges the two adjacent regions $ O_i $ and $ O_j $ which most decrease the energy functional. In other words, the merging criterion is based on the difference between the current energy $ E(u,K) $ and the energy that would result after a merge, $E(\hat{u},K-\partial(O_i,O_j))$ , where $\hat{u}$ is the piecewise constant approximation of the input image $ g $ , and $\partial(O_i,O_j)$ is the common boundary between region $ O_i $ and $ O_j $ . It can be shown that $E(u,K)-E(\hat{u},K-\partial(O_i,O_j))= \lambda\cdot{L(\partial(O_i,O_j))}- {\frac{(|O_i| \cdot |O_j|)}{(|O_i|+|O_j|)}} \|c_i-c_j\|^2$ .

Once two regions are merged the following update equations are used to calculated the constant approximation of the new region:

$c_{i,j} = \frac{(c_i |O_i| + c_j |O_j|)}{(|O_i| + |O_j|)}$ .

Again, the merging of regions continues until the desired number of regions has been reached or until the desired coarseness (specified by the scale parameter $\lambda$ ) has been reached.

The two outputs are possible to derive from the object: (1) u, the piecewise constant approximation (mean of the regions) to the input image set; This is currently generated by the process object pipeline and the (2) the labelled regions in the input image set is generated by the GetLabelledImage() function.

Definition at line 165 of file itkKLMRegionGrowImageFilter.h.