Parallel algorithms for erosion and dilation of label images.
logo

Please use this identifier to cite or link to this publication: http://hdl.handle.net/10380/3399
It is sometimes useful to be able to apply binary morphological operations, such as erosions and dilations, to labelled images in a fashion that preserves the labels. This article introduces a specialised class implementing parallel methods described in beare et al [2011] that provide very fast dilations by circles and spheres of arbitary size. Comparisons with other implementations using currently available building blocks are also made.
Code
plus Automatic Testing Results by Insight-Journal Dashboard on Thu Feb 14 13:22:44 2013 for revision #1
starstarstarstarstar expertise: 5 sensitivity: 4.5

Reviews
plus Good implementation of an efficient dilation filter for multi-label images by Dženan Zukić on 2013-02-13 06:54:06 for revision #1
starstarstarstarstar expertise: 3 sensitivity: 4.5
Add a new review
Quick Comments
Comment by Richard Beare yellow
Hi
I've included support for axis oriented elliptical structuring elements. The mechanism is basically the same as used to support spherical structuring elements in images with non-isotropic voxels. Some new tests and examples included. See how you go.
Comment by Jerome Avondo yellow
Hi
I agree the documentation needs to make this clear. I think the main ambiguity is where the Set/Get radius in section to mentions ellipsoids.

Do I think support for ellipsoids is important? Well I would have a use case for them and it would make the algorithm more generic. So I would say YES :)

J.
Comment by Richard Beare yellow
Ellipsoid structuring elements won't work at present. I'll think about whether there is a good way of adding the capability.

The algorithm is based on circles/spheres via the distance transform although there is kind of support for ellipsoid structuring elements via the image spacing - i.e. the circle/sphere radius can be specified in mm and you'll get a sensible result even if the image spacing is non isotropic.

The algorithms work by dilating a mask with a parabolic structuring function to produce a kind of inverted distance transform. The first pass sets the mask to a value that defines the size of the dilation - hence only the first element of the radius has any effect.

It is probably feasible to incorporate a weighting via the image spacing term - do you think this is an important capability? Certainly the documentation needs some improvement in this regard :-)
Comment by Richard Beare yellow
Hi
This stuff worked in the original "parabolicMorphology" package but I probably haven't tested it here. I'll check it out
Comment by Jerome Avondo yellow
Hi

I am having issues with ellipsoid structuring elements.

I did a simple test where I create a 128x128x128 image set the voxel at (64 64 64) to 255 and perform a dilate with a 10x1x10 structuring element. But I still end up with a spherical result. In fact the result obtained is identical to using a 10x10x10 structuring element.

Is there any special setup required to support ellipsoid structuring elements?

Also upon further inspection of the code it seems the computation of LabelSetDilateImageFilter::m_Scale is never used.

Thanks
J.

PS: This behavior is present in both ITK3 and ITK4.
Comment by Jerome Avondo yellow
Hi again

Here is my fork with the added ITK3 support.
https://github.com/ut666/LabelErodeDilate

Tested compilation with both ITK3 & ITK4 all works now.
I have a new found respect for the override keyword!! :)

Thank you for your patience and help to resolve this.
J.
Comment by Jerome Avondo yellow
Found it!

It was the function signature of

itkLabelSetMorphBaseImageFilter::SplitRequestedRegion(..)

ITK3 expects it with int
but ITK4 !as you correctly implemented! expects unsigned int

I'll do some testing and commit the modifications to your github.

J.
Comment by Jerome Avondo yellow
Ok getting somewhere:

I found the difference between ITK3 vs ITK4.

Quick recap:

I have that same ITK pipeline compiling in ITK3 & ITK4.
I set the threads to be fixed for both SetGlobalMaximumNumberOfThreads(2).
This makes it easier to debug and ITK4 seems to have some different logic for thread allocation. So forcing to 2 makes it comparable.
I'm focusing only on itkLabelSetDilateImageFilter for now.

ITK4 works as it should. ITK3 I get that clipping artifact shown in the renders in my previous post.

After quite some hunting the difference is the size of the incoming outputRegionForThread in itkLabelSetDilateImageFilter::ThreadedGenerateData. If I verbose the

s = outputRegionForThread.GetSize()[this-m_CurrentDimension];

For ITK4 the image is always split in s=128 (over 6 calls).
For ITK3 the image is split in s=128 (over 4 calls) and s=64 (last 2 calls)

Seems like ITK3 is skipping some parts of the image.
I haven't looked upstream yet to where this could be coming from.

Anyway hints/tips always welcome but I think I'm getting closer.

J.
Comment by Jerome Avondo yellow
I tested with ITK 4.4.2 and multi-threading on (ie: not forced to 1) and it works fine.

Looking around and refreshing my memory as I had done this !sorry! seems like the main difference for ITK 3 is the function signature for ThreadedGenerateData which is changed to use itk::ThreadIdType.

In fact to make it compatible for ITK 3 all I had to do add:

typedef int ThreadIdType;

at the top of the itkLabelSetMorphBaseImageFilter.h

Maybe this is the issue.
I will do a bit more of debugging and see what it yields.

J.
Comment by Richard Beare yellow
The threading interface changed under ITK 4 - from memory it is simply a type change for the thread ID. It should be easy enough to create a branch for ITK 3 or even perhaps some tricky macros to keep the versions consistent.

Are you able to test whether the issue goes away with ITK4 under windows?

I should also include a check in the CMake file to cause errors if building with incorrect ITK versions.
Comment by Jerome Avondo yellow
Correct!

This is with ITK3.
And setting the SetGlobalMaximumNumberOfThreads(1) does solve the issue.

Is there a reason for lack of ITK3 thread support? I am happy to contribute if you have any good pointers to get me started.

J.
Comment by Richard Beare yellow
Another thought - just confirm that you are using ITK 4 - there are differences in threading interfaces and the labelDilate code is set up for ITK 4
Comment by Richard Beare yellow
Hi
That is very distinct - I wasn't getting this kind of problem. I suspect a windows threading issue. Can you test while setting the threads to 1?

#include "itkMultiThreader.h"
itk::MultiThreader::SetGlobalMaximumNumberOfThreads(1);
Comment by Jerome Avondo yellow
Hi again.

Thank you for taking the time to check all this.

I understand the structuring element is not identical and this can lead to differences in the final mask. However I am not convinced this could fully explain the observed differences for 3D images.

To further illustrate my point I added VTK visualisation code:
http://pastebin.com/k8JbeLpC

Saved renderings:

itkBinaryDilateImageFilter
http://imagebin.org/300313

itkLabelSetDilateImageFilter
http://imagebin.org/300311

Notice how the labelset approach does not generate a sphere like mask. It really seems to be clipped in one dimension.

I also tested for 1 iteration with a size of 20.0 and get a similar result.

itkLabelSetDilateImageFilter
http://imagebin.org/300315

Thanks
J.
Comment by Richard Beare yellow
Hi
I've had a play with your example. The difference isn't caused by the loop - that bit appears to be working fine. It is just that the binary ball structuring element is different to the structuring element that gets used in the label dilate code. The binary ball is a bresenham circle. The label dilate code uses distance transforms internally. For a specified radius the bresenham circle is a bit bigger - a voxel that has any part less than the radius will get included in the bresenham circle. The version based on distance transforms is looking at the voxel centre - voxel centre needs to be closer than the specified radius. You can see the difference in your example if you set the iterations to 1. Neither of them do a great job of representing small spheres - thats not something that can be avoided - and the label dilate version is a little smaller. The difference grows with loop iterations.

However there isn't any need to use iterative approaches to construct a large sphere with the label code. Just use a large radius and you'll get a good circle/sphere very quickly. The bianry dilate probably won't be as fast. If you aren't really interested in preserving labels then check out the parabolicMorphology package also on github. Note that it assumes images with 0/1 values.
Comment by Jerome Avondo yellow
Hi again

I tested your example with the axial.png and all seems to behave.
However the behavior I noticed was tested with a 3D image.
Maybe it's isolated to 3D images.

Anyway here is a pure ITK example that produces the problem.

http://pastebin.com/WB2BF6PH

I get a size of 40421 (ITK) vs 15196 (LabelSets)
Comment by Richard Beare yellow
Hi
I've added an example to the github version - it is called labelDilateLoopTest. It seems to behave sensibly for me. The tests in the cmake file will run it for you.

A couple of points
1) You don't have a DisconnectPipeline call in the example loop. I think this is essential for reliable use of itk filters in loops. The BinaryDilateFilter may be a mini pipeline filter and thus do the same thing internally.

2) The label filters (and the parabolic filters from which they were derived) shouldn't need to be run iteratively. If you want a large dilation then simply supply a large radius. This approach is much faster and will give the correct result. The problem with the iterative approach is you tend to end up with dilations that are compositions of little rectangles and are thus like a big rectangle. If you really want a dilation by a circle (which is usually the case) then use a large radius. The tests I've added show the difference between the two cases - check out looplabdilate2d.png and looplabdilate2d50.png.

If you still see problems with this test example then it may be a platform difference - I've only tested this code on linux and mac.
Comment by Jerome Avondo yellow
Hi
I tested your github version: https://github.com/richardbeare/LabelErodeDilate
And the issue is still present.
Thanks
J.
Comment by Richard Beare yellow
Thanks for the test - I'll check it out. Note that the github version is the latest and may be different.
Comment by Jerome Avondo yellow
There seems to be an issue with this filter and running it multiple times in say a loop. For example take this code (useless but shows the problem):

for(int i=0; i10; i++)
{
sourceImage-DisconnectPipeline();
dilateFilter-SetInput(sourceImage);
sourceImage = dilateFilter-GetOutput();
dilateFilter-Update();
}

After a while the dilate image will start not expanding in one dimension. It's like the filter does not update the region / image bounds used for calculation in such a scenario?

Note the same logic was tested with the non-threaded itk::BinaryDilateImageFilter and works as expected.

J.
Comment by Richard Beare yellow
Thanks for the test - I'll check it out. Note that the github version is the latest and may be different.


Resources
backyellow
Download All
Download Paper , View Paper
Download Source code
Source code repository

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

Information more
backyellow
Categories: Geometric transforms, Mathematical Morphology, Watersheds
Keywords: labelled images, dilation, erosion, morphology
Toolkits: ITK, CMake
Export citation:

Share
backyellow
Share

Linked Publications more
backyellow
Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy Diffeomorphic Demons Using ITK's Finite Difference Solver Hierarchy
by Vercauteren T., Pennec X., Perchant A., Ayache N.
Importing Contours from DICOM-RT Structure Sets Importing Contours from DICOM-RT Structure Sets
by Dowling J., Malaterre M., Greer P.B., Salvado O.

View license
Loading license...

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