Improving performance of morphological reconstruction

Please use this identifier to cite or link to this publication:
Morphological reconstruction may be implemented in a number of
different ways. ITK has an iterative method and a non iterative
method. This article compares the performance of another non iterative
method and finds a significant improvement.
minus 2 Files (2Mb)
minus Automatic Testing Results by Insight-Journal Dashboard on Mon Feb 20 15:03:27 2006 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 5
yellow This project passed all of its tests.
Click here for more details.

Go here to access the main testing dashboard.

minus Appropriate algorithms for appropriate data by Kevin Robinson on 02-26-2007 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 5
The author demonstrates that Vincent's reconstruction by dilation algorithm is more suitable for processing non-integer data than Robinson's (which was the one then implemented in ITK)

Tests of the author's implementation of Vincent's algorithm produce identical results in less time.

Open Science:
Satisfactory information seems to be provided in all respects.

Open Source Contributions:
Drop in replacement routines are provided.

Applicability to other problems:
See comments below.

Additional Comments:
It was interesting to discover that the downhill filter algorithm had been implemented in ITK, even if I only found out after it had been superseded. I would like to pass on a few thoughts on the subject.

I would certainly agree with the author's comment on page 2, that the `pure' implementation may perform better than the one implemented in ITK. At the heart of the original downhill algorithm was an assumption of integer data. I wouldn't hesitate in recommending Vincent's algorithm over my own where non-integer data is to be accommodated. I have never so far found myself working with other than integer data in my career in medical image analysis, hence my own design decisions in this regard. The core of the algorithm is the dynamically allocated `istart' array (see [1], Appendix B, page B-15) which effectively implements an ordered array of lifo lists. This approach cannot be taken with non-integer data. For full details of the algorithm see Chapter 4 of [1], which is an expanded version of the Pattern Recognition Letters paper cited by the author.

It is interesting to note (though not necessarily significant) that the time for processing the `cthead' test image (0.0218) reported in the authors paper is identical to that reported in [1] for the same (Vincent) algorithm applied to another 256x256 test image (Study 2 MIP, see [1], Table 4.2, p110). In this case the downhill algorithm took just 0.0094 seconds to perform the same processing, while the modified ITK version reported in the author's paper took 0.1324. I would conclude (not having examined the ITK code in detail) that the port to a non-integer handling algorithm has, of necessity, neutralised the performance gains of the original downhill filter design.

Finally it may be of interest that a number of other image processing filters can be approached in a similar way, for instance the grassfire distance transform. Again see Chapter 4 and Appendix B of [1], for more details.

[1] Efficient pre-segmentation filtering in mrcp, K Robinson. Ph.D. Thesis, Dublin City University, Ireland, 2005,
minus Efficient reconstruction filters by Gaetan Lehmann on 02-20-2006 for revision #1
starstarstarstarstar expertise: 4 sensitivity: 5
The paper describe a new implementation of the morphological reconstruction filters, and show an important increase of performance.

The author show that the output of the new filter is exactly the same the output of the old one.

Open Science:
The author provides a good description of his filter, the source code, and the input images. The output images are produced by the filters without problem.

I was able to build the project and run the test on linux mandriva 32 and 64 bits without any problem.

Open Source Contributions:
The code can be replace without any problem the old one - I'm already using that code as a replacement of the old filters.

Code Quality:
The code quality is very good and well documented. The usage of functor avoid duplication of code - that was not the case with the old filters.

Applicability to other problems:
Morphological reconstruction is very useful, and is already used in several filters in ITK. It is a base transform for the family of connected filters.

Suggestions for future work:
Continue to implement such efficient filters :-)
Add a new review
Quick Comments

Download All

Statistics more
Global rating: starstarstarstarstar
Review rating: starstarstarstarstar [review]
Code rating: starstarstarstarstar
Paper Quality: plus minus

Information more
Keywords: morphological reconstruction, geodesic erosion, geodesic dilation
Toolkits: ITK (moved into the toolkit)
Export citation:


Linked Publications more
Vessel Enhancing Diffusion Filter Vessel Enhancing Diffusion Filter
by Enquobahrie A., Ibanez L., Bullitt E., Aylward S.
Gaussian Interpolation Gaussian Interpolation
by Yushkevich P., Tustison N., Gee J.

View license
Loading license...

Send a message to the author
Powered by Midas