Summary:
This paper presents a set of ITK classes for efficient kernel-based filters. The authors provide source-code and results for various mechanisms including: separable filters, histogram-based kernels, and decomposition of morphological structuring elements. The results indicate the newly-implemented methods are faster than the basic approaches currently implemented in ITK (with some constraints, as discussed in the paper).
Hypothesis:
The efficient implementations are faster (with some constraints) than the existing ITK implementations.
Evidence:
Section 7 of the paper displays graphs of different algorithm performance and the Appendix lists the results in tabular format. The code used to generate the graphs and text file output is provided with the article.
Open Science:
The authors provide the input images, source code, and results used in their experiments.
Reproducibility:
I have downloaded, compiled, and run parts of the work. I did not run the performance analysis code, but I have used some of the filters in my own application (mostly the morphological filters) and anecdotal evidence suggest the speed-ups are valid.
I did have some trouble compiling the code: the compiler I used (Microsoft Visual Studio 8.0.50727.762) complained about an ambiguous call to overloaded function 'pow' in itkFlatStructuringElement. This was fixed by casting the base to double, eg.
unsigned int facets = 8 * (int)pow((double)4, iterations);
Use of Open Source Software:
The work extends ITK.
Open Source Contributions:
The full source-code is provided.
Code Quality:
The code quality is good and matches ITK standards. However, some of the documentation needs further work:
- The \brief for itkSeparableImageFilter could be improved, eg. "A filter for performing kernel operations using decomposition" instead of "A separable filter for filter which are using kernel", similar for itkSeparableRadiusImageFilter
- itkAnchorCloseImageFilter and itkAnchorOpenImageFilter classes have no documentation
- The documentation for the static constructors in itkFlatStructuringElement need work before integration into the toolkit, these methods are important and should be well documented for users
- The documentation in itkMovingHistogramDilateImageFilter and itkMovingHistogramErodeImageFilter erronously refers to MorphologicalGradient
On the plus side, the documentation for itkMovingHistogramImageFilter (and others) is excellent!
I dislike the static const int declarations of the algorithm type, mainly because it is declared 4 separate times: itkGrayscaleMorphologicalOpeningImageFilter, itkGrayscaleMorphologicalClosingImageFilter, itkGrayscaleDilateImageFilter, and itkGrayscaleErodeImageFilter. Can the algorithm type be declared once in a header file? Also, ITK seems to favour enum types (see: itkRegularStepGradientDescentBaseOptimizer), should it be an enum?
I also stumbled across a bug / problem with itkSeparableImageFilter.txx: the output is not correctly grafted. The following line needs to be added above the update for the last filter:
m_Filters[TInputImage::ImageDimension - 1]->GraftOutput( this->GetOutput() );
Applicability to other problems:
The work is applicable to a wide of range of image processing problems, not only in the medical domain.
Suggestions for future work:
- Addition of the Annulus operator (see attachment) and Cross operator to itkFlatStructuringElement
- The itkSeparableImageFilter and itkMaskedSeparableImageFilter classes were of particular interest to me, but I was disappointed to find no morphological operations utilising these (at least that I could find) and no comparisons of speeds for Box structuring elements of basic, histogram, anchor, and separable approaches. I have implemented separable dilation and erosion using the basic approach (see attachment). A moving histogram approach could also be implemented. Perhaps these classes can be added in the darcs repository / toolkit?
Overall:
A comprehensive article which discusses a number of very useful filters (many of which I have already started using). Thanks!
Comment by Richard Beare: Histogram performance is data dependent
Hi Dan,
I've also noticed that Anchor suffers a performance penalty with non char types. The anchor method uses histograms. By default we use an array for 8 and 16 bit types and maps for larger types. Using a map for 16 bit data sometimes performs better than the array, but not always. This may be a caching issue, with the 16 bit array being large enough to fill an important high speed cache. Anyway, you can try changing the default type for 16 bit data, if you are curious. I tend to stick with the van Herk approach.
The van Herk filter can be improved a lot by using more efficient methods to access image data along lines. At present this is done using arrays of offsets because I don't want to recompute the line as it sweeps across the image. A significant proportion of the time is spent in bounds checks that should be turned off. Any help improving this is welcome.
Comment by Dan Mueller: Anchor method is slow with non-char types
Richard, Gaetan,
Strike my last suggestion for future work: adding basic separable morphological filters is *not* helpful. Originally I noticed a gain when I compared the anchor opening method with basic separable opening using signed short images (for box SE 10x10x10). However it seems the anchor method does not perform well for non-char image types. Here are some results I found using signed short and unsigned char 3-D images:
SIGNED SHORT
#radius ao vo so (ao = anchor opening, vo = VGHW, so = separable opening)
1 35.1 0.882 0.566
2 23 0.951 0.773
3 17.1 0.98 1.21
4 14.2 1.11 1.46
5 12.2 1.14 1.78
6 11.2 1.18 2.22
7 10.3 1.25 2.83
8 9.76 1.31 3.25
9 9.68 1.92 3.86
10 9.57 1.41 4.77
15 11.4 1.88 8.65
20 12.9 4.37 14
25 13.3 2.71 22.3
30 18 5.37 31.8
UNSIGNED CHAR
#radius ao vo so
1 0.999 0.944 0.589
2 0.974 0.976 0.751
3 0.974 0.996 1.08
4 0.993 1.05 1.4
5 1.04 1.15 1.88
6 1.11 1.2 2.31
7 1.17 1.29 2.81
8 1.28 1.34 3.26
9 1.57 2.08 4.35
10 1.38 1.43 4.56
15 1.64 1.83 9.08
20 2.1 2.6 14
25 2.28 2.46 21.2
30 2.85 3 29.5
In the signed short case, the basic separable approach outperformed the anchor method for radius 1-10&15, however in both cases the van Herk algorithm is fastest.
Seeing that I almost exclusively use signed short images, I will stick to the van Herk algorithm. Thanks again for implementing it in ITK.
Comment by Richard Beare: A few early notes
Hi,
Thanks for this review.
I'd like to extend Gaetan's comments regarding the separable algorithms - If you are interested in box structuring elements then you should find that the VHGW and Anchor operations, which use separabliity to implement boxes, perform much better than the equivalent operation using the BASIC algorithm. The results should be identical. In fact any SE using either VHGW or Anchor uses decomposition of some sort - the box decomposition is exact, but circles are approximations.
The Masked filters are experimental and I haven't implemented morphology operations. There are two courses of action. One is to specify a rank of 1 or zero in the masked rank filter. I haven't tested this, but it ought to work. The other is to simply use masking. The morphological operations are nonlinear. If you are after a dilation in a region defined by a mask, simply set the region outside the mask to the minimum pixel value, apply the dilation and optionally mask the result. This approach is obviously invalid for linear filters or the rank filters, but should be OK for max/min operations.
Thanks for fixing some bugs, and pointing out lacking documentation. We need to do a fair bit of work on the latter.
Comment by Gaetan Lehmann: thanks for the useful review !
About the separable filters: you're right, the separable basic filters are not implemented.However, the separable moving histogram is tested in perf2D, and the performances are reported in the article. I have added the separable basic dilation in perf2D - the results will be added in the next revision of the article. I'm not sure there is a real interest in implementing the separable algorithm in some new classes, because the performances are not good enough.
About the static members: I have chosen to use them instead of an enum to make them available in wrappers. That's not definitive though - it can be changed once the wrappers will support the enums
I think I have made everything else you have suggested. The changes are available in the darcs repository.
5 Files (22Mb)
Automatic Testing Results
by Insight-Journal Dashboard
on Wed Aug 15 03:41:41 2007 for revision #2 
expertise: 3 sensitivity: 4.5 
