A Generalized Squared Euclidean Distance Transform with Voronoi Maps
Abstract
This document describes the implementation of an algorithm that computes a generalization of the distance transform with the squared euclidean metric. The generalization allows for interesting image operators, e.g. a morphologic dilation with euclidean ball structure elements that can vary in size across the image. Voronoi maps and the standard distance transform can be computed as well. The algorithm is provided as an image processing filter for ITK. Several example programs demonstrate its applications.
Keywords
Source Code and Data
No source code files available for this publication.
Reviews
Hauke Heibel
Saturday 17 November 2007
Summary:
The authors are providing very well documented code and classes to compute a generalized euclidean distance transform.
Open Science:
The given publication offers an efficient way to compute euclidean distance transforms in 2D as well as 3D being integrated as an ImageToImageFilter into the ITK framework. For the computation of non-squared distances as well as signed distance maps, the authors utilize existing ITK algorithms on top of their own so they are following the paradigm of reusing as much existing code as possible.
Reproducibility:
I did not ran the author's tests but tested the algorithm (extensively) in my own framework. The integration was done within minutes due to well written examples which are present within the publication.
Open Source Contributions:
The algorithm implements the distance transform based on "Distance Transforms of Sampled Functions." by Pedro F. Felzenszwalb and Daniel P. Huttenlocher which is new in the ITK framework.
Code Quality:
All code is very well documented as well as very well structured and designed. A few abbreviations are used but they are already marked as to be replaced by the according long versions.
Applicability to other problems:
Euclidean distance transforms are used in many applications/algorithms (registration, skeletonizing, etc.) and thus they are an important part within the ITK framework.
The work of the authors is probably of special interest to those who are computing distance transforms on "large" volumes, since it does not only have reasonable performance (~31s on 512x512x488, UseSpacing = true) but also a low memory print as opposed to the parallel maurer version introduced recently.
Suggestions for future work:
Force the 'pow' calls in the itkLowerEnvelopeOfParabolas.txx to float/double precision to prevent compile errors.
E.g. change
::minimalSpacing = static_cast<SpacingType>(pow(10, -MinimalSpacingPrecision));
to
::minimalSpacing = static_cast<SpacingType>(pow(10.0, -1.0*MinimalSpacingPrecision));
Requests for additional information from authors:
I've stumbled over a small problem when I was reading binary unsigned short images from HD and wanted to perform a distance transform on them. I was wondering why the assert
assert(std::numeric_limits::is_signed);
was failing (itkLowerEnvelopeOfParabolas.txx l. 321). My input image was as said before unsigned short and my output image was float. After looking at the publication into section 3.1 at the description of the template parameters I found that you state that normally the TApexHeightType "is the type of voxels in the distance image", i.e. TDistanceImage::PixelType.
This is now confusing me, since within the itk::GeneralizedDistanceTransformImageFilter the parameter is typedef'ed to TFunctionImage::PixelType.
What is the correct version? I personally just did a quick-hack-test and interchanged TFunctionImage with TDistanceImage within the LEOP typedef but since I am not sure about the side effects I am not really happy with it, even though now I am getting correct distance transforms when enabling pixel spacing.
Additional Comments:
Great work and I am still giving full credit even in presence of the small issue mentioned above since the rest of the publication is so well done.
Gaetan Lehmann
Thursday 6 July 2006
Summary: The authors are providing code and detailed paper for a new distance transform for ITK, and examples of applications
Reproducibility: The articl lack of a test infrastructure. CMake let the developer define very easily some test (see modified code)
Open Source Contributions: All the sources are there, and the test program are documented. Configuring and building the code was done in a few minutes [Do the authorâs provide their source code? Is it in a form that is usable? Do they describe clearly how to use of the code? How long did it take you to use that code?]
Code Quality: The code is very clean
Applicability to other problems: distance transform is very important in image analysis, so this code will be useful in many cases
Suggestions for future work:
- use cmake\\\'s tests
- avoid using too much template parameters (they are difficult to wrap), and static attributes (they are not supported by the wrappers)
- use concept checking rather than assert when possible, so we get the error at compile time, and we get it even if compiled in release mode
Requests for additional information from authors: One thing I\'m not sure, is the usage of maxApexHeight. It has the type of the distance map pixel, but is used with the function pixel type in your examples. Does it mean that we must use the same type for distance map and function ?
Additional Comments: I have modified your contribution to:
- run tests with cmake
- drop some template parameter - the parameter can now be chosen at run time
- add progress report
- set a GetMaximumApexHeight() static method, so it can be used with wrappers
- wrap the classes and run a python test
- fix a warning when function and distance type are different
very nice article