forked from InsightSoftwareConsortium/ITK
-
Notifications
You must be signed in to change notification settings - Fork 0
/
itkKLMRegionGrowImageFilter.h
390 lines (323 loc) · 16.9 KB
/
itkKLMRegionGrowImageFilter.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
/*=========================================================================
Program: Insight Segmentation & Registration Toolkit
Module: itkKLMRegionGrowImageFilter.h
Language: C++
Date: $Date$
Version: $Revision$
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 _itkKLMRegionGrowImageFilter_h
#define _itkKLMRegionGrowImageFilter_h
#include "itkImage.h"
#include "itkObject.h"
#include "itkImageToImageFilter.h"
#include "itkRegionGrowImageFilter.h"
#include "itkKLMSegmentationRegion.h"
#include "itkKLMSegmentationBorder.h"
#include "itkImageRegionIterator.h"
#include "itkImageRegionConstIterator.h"
#include "itkConceptChecking.h"
#include <algorithm>
#include <functional>
namespace itk
{
/** \class KLMRegionGrowImageFilter
* \brief 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,'' {\em 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 \f$ O_i, i=1,2,\ldots,N \f$, where
* \f$ N \f$ is the
* total number of region, by minimizing the following energy functional
* (also known as the simplified Mumford and Shah functional):
* \f$
* E(u,K)=\int_{\Omega-K}||u(r,c)-g(r,c)||^2{d{\Omega}}+\lambda\cdot{L(K)}
* \f$,
* where \f$ \Omega \f$ denotes the domain of an image, \f$ g(r,c) \f$
* is the input image, and \f$ u(r,c) \f$ is an approximation of
* \f$ g(r,c) \f$. Furthermore, \f$ u(r,c) \f$ is defined to be
* piecewise constant in regions \f$ O_i \f$. If
* \f$ \partial O_i \f$ represents the boundary of the region,
* \f$ K=\bigcup_{i=1}^N\partial{O_i} \f$ denotes the set of all region
* boundaries and \f$ L(K) \f$ is the total length of the boundaries. The
* parameter \f$ \lambda \f$ controls the coarseness of the segmentation
* (i.e. a larger \f$ \lambda \f$ will result in fewer boundaries).
*
* Starting with small, piecewise-constant initial regions the algorithm
* iteratively merges the two adjacent regions \f$ O_i \f$ and
* \f$ O_j \f$ which most
* decrease the energy functional. In other words, the merging criterion
* is based on the difference between the current energy
* \f$ E(u,K) \f$ and the
* energy that would result after a merge,
* \f$ E(\hat{u},K-\partial(O_i,O_j)) \f$,
* where \f$ \hat{u} \f$ is the piecewise constant approximation of the
* input image \f$ g \f$, and \f$ \partial(O_i,O_j) \f$ is the common boundary
* between region \f$ O_i \f$ and \f$ O_j \f$. It can be shown that
* \f$ E(u,K)-E(\hat{u},K-\partial(O_i,O_j))=
* \lambda\cdot{L(\partial(O_i,O_j))}-
* {(|O_i| \cdot |O_j|)\over (|O_i|+|O_j|)} ||c_i-c_j||^2 \f$.
*
* Once two regions are merged the following update equations are used
* to calculated the constant approximation of the new region:
*
* \f$ c_{i,j} = (c_i |O_i| + c_j |O_j|) \over (|O_i| + |O_j|) \f$.
*
* 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 \f$ \lambda \f$) 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.
*
* \ingroup RegionGrowingSegmentation
*/
template <class TInputImage, class TOutputImage>
class ITK_EXPORT KLMRegionGrowImageFilter : public RegionGrowImageFilter<TInputImage,TOutputImage>
{
public:
/** Standard class typedefs. */
typedef KLMRegionGrowImageFilter Self;
typedef RegionGrowImageFilter< TInputImage, TOutputImage > Superclass;
typedef SmartPointer< Self > Pointer;
typedef SmartPointer< const Self > ConstPointer;
/** Method for creation through the object factory. */
itkNewMacro(Self);
/** Run-time type information (and related methods). */
itkTypeMacro(KLMRegionGrowImageFilter, RegionGrowImageFilter);
/** Type definition for the input image. */
typedef TInputImage InputImageType;
typedef typename TInputImage::Pointer InputImagePointer;
typedef typename TInputImage::ConstPointer InputImageConstPointer;
/** Type definition for the input image pixel type. */
typedef typename TInputImage::PixelType InputImagePixelType;
/** Type definition for the input image pixel vector type. */
typedef typename TInputImage::PixelType::VectorType InputImageVectorType;
/** InputImageVectorDimension enumeration. */
itkStaticConstMacro(InputImageVectorDimension, unsigned int,
InputImagePixelType::Dimension);
/** Type definition for the input image index type. */
typedef typename TInputImage::IndexType InputImageIndexType;
/** Type definition for the image iterators to be used. */
typedef ImageRegionIterator< TInputImage > InputImageIterator;
typedef ImageRegionConstIterator< TInputImage > InputImageConstIterator;
/** Type definition for the image region type. */
typedef typename TInputImage::RegionType InputRegionType;
/** Type definition for the input grid size type used to create
* initial atomic regions. */
typedef typename Superclass::GridSizeType GridSizeType;
/** Type definition for the output image. */
typedef TOutputImage OutputImageType;
typedef typename TOutputImage::Pointer OutputImagePointer;
/** InputImageDimension enumeration. */
itkStaticConstMacro(InputImageDimension, unsigned int,
TInputImage::ImageDimension);
/** OutputImageDimension enumeration. */
itkStaticConstMacro(OutputImageDimension, unsigned int,
TOutputImage::ImageDimension);
/** Type definition for the output image pixel type. */
typedef typename TOutputImage::PixelType OutputImagePixelType;
/** Type definition for the output image pixel vector type. */
typedef typename TOutputImage::PixelType::VectorType OutputImageVectorType;
/** OutputImageVectorDimension enumeration. */
itkStaticConstMacro(OutputImageVectorDimension, unsigned int,
OutputImagePixelType::Dimension);
/** Type definition for the output image index type. */
typedef typename TOutputImage::IndexType OutputImageIndexType;
/** Type definition for the output image iterators. */
typedef ImageRegionIterator< TOutputImage > OutputImageIterator;
/** The dimensions of the input image must equal those of the
output image. */
itkConceptMacro(SameDimension,
(Concept::SameDimension<itkGetStaticConstMacro(InputImageDimension),itkGetStaticConstMacro(OutputImageDimension)>));
#if THIS_CONCEPT_FAILS_ON_GCC
/** The input pixel type must be the same as that of the output
image. */
itkConceptMacro(SameVectorDimension,
(Concept::SameDimension<itkGetStaticConstMacro(InputImageVectorDimension),itkGetStaticConstMacro(OutputImageVectorDimension)>));
#endif
/** type definition for the region label type. */
typedef typename KLMSegmentationRegion::RegionLabelType RegionLabelType;
/** The dimension of the labelled image. */
itkStaticConstMacro(LabelImageDimension, RegionLabelType,
InputImageDimension);
/** Type definition for the labelled image pixel type. */
typedef Image< RegionLabelType, itkGetStaticConstMacro(LabelImageDimension) > LabelImageType;
/** Type definition for the labelled image pointer. */
typedef typename LabelImageType::Pointer LabelImagePointer;
/** Type definition for the labelled image pixel type. */
typedef typename LabelImageType::PixelType LabelImagePixelType;
/** Type definition for the labelled image index type. */
typedef typename LabelImageType::IndexType LabelImageIndexType;
/** Type definition for the labelled image iterators. */
typedef ImageRegionIterator< LabelImageType > LabelImageIterator;
/** Storage type for the mean region intensity. */
typedef vnl_vector< double > MeanRegionIntensityType;
/** Type definition for the smart border type. */
typedef KLMSegmentationBorder BorderType;
/** Type definition for the smart border pointers object. */
typedef KLMDynamicBorderArray< BorderType > KLMSegmentationBorderArrayPtr;
/** Set/Get the desired threshold parameter for lambda. See
* itkSegmentationBorder documentation for details regarding this
* parameter. */
itkSetMacro(MaximumLambda, double);
itkGetConstReferenceMacro(MaximumLambda, double);
/** Set/Get the desired number of regions. */
itkSetMacro(NumberOfRegions, unsigned int);
itkGetConstReferenceMacro(NumberOfRegions, unsigned int);
/** Generate labelled image. */
LabelImagePointer GetLabelledImage(void);
/** Function that prints all the region information. */
void PrintAlgorithmRegionStats(void);
/** Function that prints all the border information. */
void PrintAlgorithmBorderStats(void);
protected:
KLMRegionGrowImageFilter();
~KLMRegionGrowImageFilter();
void PrintSelf(std::ostream& os, Indent indent) const;
/**
* Standard pipeline method.
*/
virtual void GenerateData();
/** KLMRegionGrowImageFilter needs the entire input. Therefore
* it must provide an implementation GenerateInputRequestedRegion().
* \sa ProcessObject::GenerateInputRequestedRegion(). */
virtual void GenerateInputRequestedRegion();
/** KLMRegionGrowImageFilter will produce all of the output.
* Therefore it must provide an implementation of
* EnlargeOutputRequestedRegion().
* \sa ProcessObject::EnlargeOutputRequestedRegion() */
virtual void EnlargeOutputRequestedRegion( DataObject * );
/** This is the interface function that calls the specific algorithm
* implementation of region growing. */
void ApplyRegionGrowImageFilter();
/** Function to merge two regions.
* The smaller label is always assigned to the new region. This is
* consistent with the connected components algorithm. */
virtual void MergeRegions();
/** Generate output approximated image. */
virtual void GenerateOutputImage();
/** Function that calls the KLM region growing algorithm. */
void ApplyKLM();
/** Initialize the RegionGrowImageFilter algorithm. */
void InitializeKLM();
/** Generate the labelled image. */
LabelImagePointer GenerateLabelledImage( LabelImageType *labelImagePtr );
/** Calculate the statistics representing the region. In this
* case we compute the mean region intensity and the area of the
* initial N-dimensional rectangular area. This is the function that
* can be overriden in order to enable a different statistical
* representation for region initialization. */
virtual void InitializeRegionParameters( InputRegionType region );
/** Function to resolve the region labels to be consecutively ordered.
* Each initial atomic region is given a new label and the aggregrate
* region area and mean intensity. */
virtual void ResolveRegions();
private:
KLMRegionGrowImageFilter(const Self&); // purposely not implemented
void operator=(const Self&); // purposely not implemented
typedef typename TInputImage::SizeType InputImageSizeType;
typedef typename KLMSegmentationRegion::Pointer KLMSegmentationRegionPtr;
typedef typename KLMSegmentationBorder::Pointer KLMSegmentationBorderPtr;
double m_MaximumLambda;
unsigned int m_NumberOfRegions;
/** Local variables. */
double m_InternalLambda;
unsigned int m_InitialNumberOfRegions;
double m_TotalBorderLength;
std::vector< KLMSegmentationRegionPtr > m_RegionsPointer;
std::vector< KLMSegmentationBorderPtr > m_BordersPointer;
std::vector< KLMSegmentationBorderArrayPtr > m_BordersDynamicPointer;
KLMSegmentationBorderArrayPtr *m_BorderCandidate;
MeanRegionIntensityType m_InitialRegionMean;
double m_InitialRegionArea;
}; // class KLMRegionGrowImageFilter
} // namespace itk
#ifndef ITK_MANUAL_INSTANTIATION
#include "itkKLMRegionGrowImageFilter.txx"
#endif
#endif