N-D Linear Time Exact Signed Euclidean Distance Transform

Please use this identifier to cite or link to this publication: http://hdl.handle.net/1926/171
Fast computation of distance transforms find direct application
in various computer vision problems. Currently there exists
two image filters in the ITK library which can be used to generate
distance maps. Unfortunately, these
filters produce only approximations to the Euclidean Distance
Transform (EDT). We introduce into the ITK library a third EDT
filter which was developed by Maurer {em et al.} cite{Maurer2003}.
In contrast to other algorithms, this algorithm produces the
exact signed squared EDT using integer arithmetic. The complexity,
which is formally verified, is $O(n)$ with a small time constant
where $n$ is the number of image pixels.
minus 2 Files (222Kb)
minus Automatic Testing Results by Insight-Journal Dashboard on Mon Feb 20 15:46:10 2006 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 4.5
yellow This project passed 3 out of 6 tests.
Click here for more details.

Go here to access the main testing dashboard.

minus Excellent by Luis Ibanez on 04-14-2006 for revision #1
starstarstarstarstar expertise: 4 sensitivity: 4.5
This papers describes the implementation of a exact signed distance map as an ITK filter according to the paper by Maurer et al. This implementation is compared against the current Danielsson distance map existing in ITK.

It was claimed that the Maurer algorithm for computing distance maps was more efficient than the method by Danielsson. The ITK toolkit only had an implementation of the Danielsson filter and was lacking the implementation of Maurer's algorithm. By providing now open source implementation of these two very useful methods, it becomes possible to experimentally verify the performance ratio between these two algorithms. It is reasonable to expect that the availability of this comparison will encourage improvements in the open source implementations of each one of them.

The authors ran the existing Danielsson distance map and their new implementation of the Maurer's algorigthm in a set of synthetic binary images, both in 2D and 3D. Computational times for these test are reported in the paper.

Open Science:
The papers is an excellent example of the Open Science methodology. The description of the problem is clear and direct. The authors provide the source code of the implemented filter as well as tests for running the filter in several synthetc images. The input images and output images are provided.

The material provided by the authors was sufficient for reproducing the work. It took only about 30 minutes to download, configure, build and run the code with its tests.

The only minor drawback was that the CMakeLists.txt file provided by the authors assumes that the code is going to be built in-place, and that the images resulting from the tests will be put in the Source directory also. This reviewer used the code in an out-of-source build, and therefore was forced to make a couple of changes in the CMakeLists.txt file. The section changed was the following:

ADD_TEST(Run1 ${SignedMaurerDistanceMapImageFilterTest}
${CMAKE_SOURCE_DIR}/binaryPhantom.hdr ${CMAKE_BINARY_DIR}/out1.hdr)
ADD_TEST(CompareImage1 ImageCompare ${CMAKE_BINARY_DIR}/out1.hdr

ADD_TEST(Run2 ${SignedMaurerDistanceMapImageFilterTest}
${CMAKE_SOURCE_DIR}/SquareBinary201.hdr ${CMAKE_BINARY_DIR}/out2.hdr)
ADD_TEST(CompareImage2 ImageCompare ${CMAKE_BINARY_DIR}/out2.hdr

ADD_TEST(Run3 ${SignedMaurerDistanceMapImageFilterTest}
${CMAKE_SOURCE_DIR}/peep0_seg01.hdr ${CMAKE_BINARY_DIR}/out3.hdr)
ADD_TEST(CompareImage3 ImageCompare ${CMAKE_BINARY_DIR}/out3.hdr

Where the "${CMAKE_BINARY_DIR}" was added before "out.hdr"

It will also be desirable to use names out1.hdr, out2.hdr, and out3.hdr for each one of the test,
in that way the three images will still be availble at the end of the test. There is not need to reuse
the filename, since these images are pretty small anyways.

The reviewer used this code in Cygwing wth gcc 3.4, in a laptop Dell D810 with Pentium 4 at 1.86Ghz.

Use of Open Source Software:
The authors made the optimal combination of open source use. Their work is based on open source tools (ITK), and their contribution is also sent back as an open source filter .

Open Source Contributions:
The source code is in very good shape. It was possible to use it without any modifications. The distance map filter contributed by the authors is already in the form of an ITK filter, and could be included in the ITK toolkit with minimal modifications, mostly related to coding style.

Code Quality:
The provided has good quality and already follows most of the ITK coding practices. The authors also included in their implementation a very similar API to the one of the Danielsson distance. It is therefore very easy to replace one with the other in the places where a distance map filter is needed.

Applicability to other problems:
The Distance Map filter is an extremely useful tool in medical image processing. The superior performance of the Maurer's algorithm with respect to the Danielsson algorithms seems to indicate that this new implementation should replace the Danielsson distance in some places in the Toolkit. For example in the CannyLevelSet segmentation filter.

Suggestions for future work:
The RemoveEDT() method could probably be speed up by using an inlined implementation.
The use of acronyms such as EDT is dicouraged in ITK. It will be more convenient to use the full spelling : ExactDistanceTransform.

Requests for additional information from authors:
The authors mention in the paper, evaluations of the method in 3D images. It would have been nice to include those 3D images along with the 2D ones. The infrastructure of the Insight Journal would have supported those images easily, and will have provided a convincing evidence to readers that the filter is effective in 3D.

The comparision of the output between the Maurer's and Danielsson's filter should have included a subtraction of the two output images. The paper presents the two images, which at naked eye look identical. It is interesting however to compute the difference and illustrates the kind of patterns that the difference image will have. This will be useful for those who need to make a decision regarding which one of these two filters to use. The filter SquaredDifferencesImageFilter could provided this comparison easily.


This reviewer was able to verify the good behavior of the filter in a 3D image, by just chaning the dimension of the image in the test provided by the authors.

Additional Comments:
This is an excellent contribution to the medical image processing community, and a success story for the approach of Open Science and electronic publishing. The posting of this paper made possible in a single day to improve performance in method used by other groups in the country. Despite the fact that this algorithm has been published for about 3 years, this new open source implementation raises its impact by making it inmediately available to readers. We anticipate that this filter will make it soon to a future release of the ITK toolkit.
minus Efficient distance transform by Gaetan Lehmann on 02-19-2006 for revision #1
starstarstarstarstar expertise: 3 sensitivity: 4.5
The paper describe a new filter to compute the distance map of a binary image. The author provides a more efficient filter than the current filter available in ITK

The author provides source code and input and output images so it's easy to validate the behavior of the filter.

Open Science:
The author provides a good description of is filter, the source code, and the input and output image. It can be even better by also providing the source code of the timing test.

I was able to reproduce the work, with some small problems: I'm used to build the code in a "build" directory. The build succeed, but the test failed when run out of the source directory.
I compile and run the code on a mandriva linux 2006.0 with a pentium 4 and 2GB of RAM.
As said above, it would have been easier with the source code of the timing test.

Open Source Contributions:
The code is easily usable - it is really closed itk's danielsson filter.

Code Quality:
The code quality is quite good, but the core of the implementation is not documented - it should be done before inclusion in ITK to make modification of the code easier.
Indentation doesn't follow the ITK convention.

Applicability to other problems:
Distance transform is the base of lots of algorithms - This efficient version will be useful in lots of cases.

Suggestions for future work:
In the title, it's said that the filter perform the computation in linear time. It would be great to see a graph which show that in the paper - "time = f( number of pixels)" instead of "time = f( number of pixels per dimension )".
The filter should report its progress - it currently doesn't report it.
The ability to select the background color is interesting, but unless the common usage of this filter is for labeled images, I think it would be better to be able to select the foreground value, like it's done in other filters which manipulate binary images.
Finally, I would suggest to implement the squared option in a separate filter. The progress report would be easier to implement this way, and it would be possible to implement concept check for pixel types.

Additional Comments:
Note that a template for IJ contribution is available at http://voxel.jouy.inra.fr/darcs/contrib-itk/template/, and should avoid the problems of build directory, for example.
Thanks for that filter !
minus Distance Transform by Vamsi Jammalamadaka on 02-19-2006 for revision #1
starstarstarstarstar expertise: 2 sensitivity: 4.5
ITK filter to perform signed distance transform.

I was able to download, compile, and run the work.

Use of Open Source Software:
This is clearly Open Source code. It is written completely in itk

Open Source Contributions:
The authors provide the full source code and documentation. It took me about 10 minutes to download and run the code.

Code Quality:
The code quality is very good. It is easy to understand. The author provide documentation along with the code.

Additional Comments:
This is a very useful filter to perform fast distance transforms.
Our team is implementing a warping algorithm for which we use the signed distance transform on 3d images. Generating the signed distance transform is the most time consuming part of our algorithm. Due to this filter there is a 10 fold improvement in speed of our algorithm .
Thanks for this addition to ITK.
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: Euclidean Distance Transform
Toolkits: ITK (moved into the toolkit)
Export citation:


Linked Publications more
Cardiac Interventional Guidance using Multimodal Data Processing and Visualisation: medInria as an... Cardiac Interventional Guidance using Multimodal Data Processing and Visualisation: medInria as an...
by Vichot F., Cochet H., Bleuzé B., Toussaint N., Jaïs P., Sermesant M.
GeoInterp: Contour Interpolation with Geodesic Snakes
Geodesic Snakes GeoInterp: Contour Interpolation with Geodesic Snakes Geodesic Snakes
by Saboo R., Julian R., Stephen P.

View license
Loading license...

Send a message to the author
ISSN 2327-770X
Powered by Midas