Digital Topology

Please use this identifier to cite or link to this publication:
This documents describes a set of classes to integrate digital topology in the
Insight Toolkit, with an application to homotopic thinning. The skeletonization
filter implemented using our set of classes is twice as fast as BinaryThinningImageFilter
and can be used on images of any dimension.
minus 2 Files (184Kb)
minus Automatic Testing Results by Insight-Journal Dashboard on Mon Aug 28 13:50:22 2006 for revision #3
starstarstarstarstar expertise: 5 sensitivity: 4.6
yellow This project passed 0 out of 1 tests.
Click here for more details.

Go here to access the main testing dashboard.
plus Automatic Testing Results by Insight-Journal Dashboard on Thu Aug 24 10:56:26 2006 for revision #2
starstarstarstarstar expertise: 5 sensitivity: 4.3
plus Automatic Testing Results by Insight-Journal Dashboard on Wed Aug 23 17:45:43 2006 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 5

minus With some work, a great addition to ITK by Dan Mueller on 07-23-2007 for revision #3
starstarstarstarstar expertise: 3 sensitivity: 4.6

This paper presents an ITK filter for skeletonization using homotopic thinning.

The author claims the presented filter is faster than the existing ITK method, and works for both 2-D and 3-D images.

A table of results in given on page 3 of the paper supporting the claim.

Open Science:
The source code, input data, and baseline result is supplied with the article.

I downloaded, compiled, and ran the work (there were some compilation issues, see below). I have also used the filter in other applications on a variety of 2-D and 3-D images.

Use of Open Source Software:
Extends ITK.

Open Source Contributions:
The full source code is provided, as well as a test executable. I would suggest using the CMake ADD_TEST functionality and ImageCompare for validating the output matches the baseline image.

Code Quality:
Most of the code is good. However I did encounter some issues compiling the code using Microsoft Visual Studio 8.0.50727.762:

  • itkChamferDistanceTransformImageFilter.txx(180) : Error C2780: 'const _Ty &std::min(const _Ty &,const _Ty &,_Pr)' : expects 3 arguments - 2 provided
  • itkUnitCubeCCCounter.txx(34) : Warning C4996: 'std::copy': Function call with parameters that may be unsafe - this call relies on the caller to check that the passed values are correct. To disable this warning, use -D_SCL_SECURE_NO_WARNINGS. See documentation on how to use Visual C++ 'Checked Iterators'

I fixed the errors by specifying the template argument for std::min: minimum = std::min(minimum, it.GetPixel(i) + mask[i]);

There are a number of style considerations I would also suggest:

  • Is there a good reason for the itkSkeletonizeImageFilter to be an InPlaceImageFilter? I have found that this causes issues when writing the output of the skeletonize filter to disk: the output must be disconnected before being plugged into a writer object. I think making the filter an ImageToImageFilter would fix this.
  • I agree with Gaëtan's comment regarding the ForegroundConnectivity template: it should be removed (to help with wrapping).
  • I agree with Gaëtan's comment regarding automated border padding: at the moment if the input image (accidentally) touches the edges a segfault is caused (perhaps this is the problem that Ruben described in this review?).
  • I like Ivan's idea to add a template for the itkSkeletonizeImageFilter ordering image: except I would make the default the input image type for sake of ease.
  • The txx file include in itkSkeletonizeImageFilter.h should be wrapped with the normal ITK_MANUAL_INSTANTIATION.
  • The commenting in the header files does not seem to conform to the standard ITK style.
  • The mechanism for setting the weights in itkChamferDistanceTransformImageFilter is not the typical ITK style (in fact it took me quite some time to work out how to set the values). To bring it more in line with the ITK standard, I suggest using a FixedArray typedef similar to that used by the BilateralImageFilter to specify the DomainSigma parameters, or the itkCannyEdgeDetectionImageFilter Variance parameter, etc.

Applicability to other problems:
The work is useful for a range of applications, including vessel centerline detection.

A useful filter, with some further work it will make a great addition to ITK.

minus fails for modifications of the test image and crashes for own images, that meet described criteria by Ruben Schilling on 06-24-2007 for revision #3
starstarstarstarstar expertise: 2 sensitivity: 3.4
The authors addressed the lack of a 3D skeletonization filter in ITK. They implemented a homotopic thinning algorithm based on chamfer distance ordered topologically correct pixel removal.

The authors assume the image to be binary and not connected to the image's border. Their goal is a 1D line of good medial position reflecting the topology of the image.

The authors support their claims by a test input image and the expected resulting image of their algorithm.

Open Science:
The authors provide enough data, code and information to conduct the experiment.

I reproduced the authors work by downloading, compiling and running their code on the provided image. The image was indeed as reported by the authors.

Open Source Contributions:
The authors provide their source code. Except for a missing file (IJMacros.txt) everything was in place. After obtaining the missing file from a different place on the internet compilation was fine.

Code Quality:
The code runs fine on my Mac OS X box and was nicely readable and structured.

Applicability to other problems:
I didn't get the authors code to work on any other image except the one provided. Changing file format of the provided file from .hdr/.img to .tif stopped the algorithm from producing output. Adding a second object to the image (just another foreground blob, not connected to the bunny and flat circular 10 pixels radius, not touching the border) stopped also the algorithm from producing output. Using my own binary data (not touching border of the image) let the algorithm crash with a segmentation fault, even for very small image sizes, where memory isn't an issue. Converting the provided test images to tif and back to hdr resulted in silghtly different output.

Suggestions for future work:
I would suggest, that the code should be made more reliable regarding the described issues.

Requests for additional information from authors:
I found, that the paper was missing enough information about tuning parameters of the algorithm and an instructive description of the algorithm's parameters. It would be helpful to add those to the paper and/or code comments.

Additional Comments:

minus Very useful for tasks such as 3D skeletonization. Incorporates some features missing in ITK. by Ivan Macia on 02-21-2007 for revision #3
starstarstarstarstar expertise: 3 sensitivity: 4.6

This paper describes an implementation in ITK of some concepts taken from digital topology. It implements a connectivity framework allowing to calculate the topological numbers of a point in a neighborhood and to discriminate simple points. The authors implement a useful algorithm for skeletonization using binary thinning based on these concepts. In my opinion it is a very useful contribution for the toolkit and one I was particularly interested in.

Open Science:
Source code as well as an example with data is provided that allows reproducibility.

I was able to compile and reproduce the mentioned results. Latest fixes solve most of the initial compilation problems.

Use of Open Source Software:
The implementation is based on ITK and is itself an extension of the libraries for some features that are not already implemented.

Open Source Contributions:
The provided source code is readily usable as it is, maybe requiring some minor changes/fixes. Main contributions are a framework for connectivity and an implementation of a skeletonization image filter based on binary thinning. More work could be derived by extending/using these concepts.

Code Quality:
The implementation is good and well structured, separating the different concepts involved into components.
I miss some more documentation/comments in some parts on the code that makes it easier to read.
Sometimes it does not follow the ITK coding style.

Additionally I made some fixes/improvements in the code :
- The ordering image type should be a template parameter. I have already been in the need of using an image type different from itk::Image
- There where some variables/members/methods that were using char/int where they should use unsigned char/unsigned int, for example the neighborhood image buffer and neighborhood sizes.
- I had linking problems with the global method factorial() when integrating it into an application. Changed this to a static method. Also reimplemented Factorial() to avoid recursive function calls.

My proposed changes are included as an attachment

Applicability to other problems:
More imaging algorithms based on concepts of digital topology could be implemented using this work. The skeletonization algorithm is very useful for vessel centerline extraction.

Suggestions for future work:
I miss some more introductory information in the paper. For example, the definition of simple points which is not obvious for non-experts.

minus Efficient Connectivity based framework, close to ITK ready? by Martin Styner on 09-21-2006 for revision #3
starstarstarstarstar expertise: 4 sensitivity: 4.6

The paper presents the implementation of efficient connectivity framework based on ITK. By including all the recommendations suggested in Gaetan Lehmann’s earlier review, this makes a formidable example for an inclusion into ITK.

Open Science:
The full source code, a testing program as well as the test data is provided.

I have not compiled or reproduced the results.

Use of Open Source Software:
The work is based on ITK and represents an extension of it.

Open Source Contributions:
The author provide a flexible and efficient basic framework for connectivity operators as open source.

Code Quality:
The code looks good, well structured and documented.

Applicability to other problems:
The framework seems easily adapted and applicable to other connectivity problems.
plus Got 16 errors and 5 warnings by Bipul Das on 09-27-2006 for revision #2
starstarstarstarstar expertise: 2 sensitivity: 4.7
plus a good contribution, even if it require some enhancement. It also open the discussion on connectivity in the toolkit by Gaetan Lehmann on 11-06-2006 for revision #2
starstarstarstarstar expertise: 3 sensitivity: 4.7
Add a new review
Quick Comments
Comment by Pablo Hernandez cerdan yellow
Digital Topology would be a great addition to the Insight Toolkit.

The author published an illustrative article with an extended introduction to Digital Topology here:

Download All

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

Information more
Categories: Data Representation, Programming
Keywords: Digital topology
Toolkits: ITK, CMake
Export citation:


Linked Publications more
N4ITK:  Nick's N3 ITK Implementation For MRI Bias Field Correction N4ITK: Nick's N3 ITK Implementation For MRI Bias Field Correction
by Tustison N., Gee J.
Large Image Streaming using ITKv4 Large Image Streaming using ITKv4
by Zuluaga M.A., Ibáñez L., Peyrin F.

View license
Loading license...

Send a message to the author
Powered by Midas