[Insight-users] Fast binary morphology dilation

[jerome schmid]

Hi itk users,

I have been using itk binary dilation for a project and I found that
sometimes the  binary dilation, especially for big images and big
structuring element, can be very very long. It is normal because the
standard itk implementation is not optimised as it is very generic.


I have hence coded a new one which is based on incremental binary dilation.
If you are interested in the technique and usage please read what follows.
If someone has already some code with binary dilation, he can make some
benchmarks and especially detect some bugs...!

Regards,

Jerome.


Fast binary dilation
********************

Principle
**********
This implementation is based on the following papers:

L.Vincent "Morphological transformations of binary images with arbitrary
structuring elements"
and
N.Nikopoulos et al. "An efficient algorithm for 3d binary morphological
transformations with 3d structuring elements for arbitrary size and shape"

The idea is quite simple.

The method is based on the following property:
Let's consider the set of the ON elements of the input image as X.
Let's consider the structuring element as B = {B0, B1, ..., Bn}, where Bi
denotes a connected component of B.
Let's consider bi, i in [0,n], an arbitrary point of Bi.

We use hence the next property in order to compute minkoswki addition (
which will be written (+) ):
X (+) B = ( Xb0 UNION Xb1 UNION ... Xbn ) UNION ( BORDER(X) (+) B ),
where Xbi is the set X translated with respect to vector bi : Xbi = { x +
bi, x belongs to X }
where BORDER(X) is the extracted border of X ( 8 connectivity in 2D, 26 in
3D )

This property is valid in 2D and 3D, I don't know if it is valid for higher
dimensions ( I think but I am not sure ). If it is the case, as itk is
generic in dimensions the proposed code should work for higher dimensions.

The itk binary dilation is defined as:
DILATION(X)_B = {x belongs to X | Bx INTERSECTION X is not empty}
Then with minkowski addition you have:

X (+) SYM(B) = DILATION(X)_B
Where DILATION(X)_B is the dilation of set with structuring element B
Where SYM(B) is the symmetric of the structuring element relatively to its
center

Advantages
**********

*Speed*
If you have a look at the property you see that we only "paint" the
structuring element (SE) on the border --> faster
When we paint the SE on a pixel a position x and a SE at a pixel at position
x+1, we only paint the SE and the difference between the SE at position x
and the SE at position x+1 . This is the incremental aspect of the
method --> faster

*Exotic SE*
The proposed implementation works with any kind of SE even if the center
pixel of SE is not ON. In fact, itk doesn't handle correctly this kind of SE
( it also written in the doc. Currently I haven't upgraded to 1.8 maybe
there are some changes? ). For instance let's consider in the attached 2D
images the white dot. If you use a SE like this:

 *
* *
 *

i.e a centered cross without the center pixel on, you should retrieve after
dilation ( if you respect the dilation definition ) the result in image
fastDilation.png ( I use OpenCV to check that my implementation was valid!
Maybe mine presented some mistakes....^_^ ). If you look the classic itk
one, you see that the center pixel is ON. I actually don't know why itk
chooses to return what they call the most appopriate "background" value for
center pixel, but I think there are some valid reasons.

If you use "standard" SE like balls or cross, the results are the same
between classic and proposed implementation.

*Usage*
It is like binaryDilateImageFilter, you define a kernel for dilation.
For the input image it can be not a binary image but the filter will
binarize it in the following way:

Any pixel which intensity is m_InputForegroundValue ( set by
SetInputForegroundValue() ) is considered as a foreground> pixel.
Any pixel which intensity is m_InputBackgroundValue ( set by
SetInputBackgroundValue() ) is considered as a background> pixel.
Any other pixel is considered as background pixel.

The foreground and background values of output are set by
SetOutputForegroundValue() and SetOutputForegroundValue() functions.

*Results*

I have made few tests on 2D and 3D images. You save a lot of time when the
SE size increases and when the image has a lot of big connected components
( size of border is hence << size of connected component )

Some results just to have an idea ( of course results depend on image and
SE!!)
2D image 256x256


			2x2	10x10	15x17	30x30	<< SE Ball radius
itk classic		0.031	0.58	1.78	9.16	<< seconds
itk "fast"		0.031	0.031	0.032	0.063
openCV		0.031	0.31	0.73	2.41


*Technical details*

In classic itk binary dilation, the input requested region is padded with
the connectivity neighborhood. We do not do this in our implementation but
internally we create a temp image in which we take care to this boundary
part of image.

*Remarks*

This filter can be used for erosion, just use complementary property.
This version is NOT threaded but can be modified in order to accept
ThreadedGenerateDaat() feature. However I haven't had the energy to do
it...!
This filter seems to work but some bugs could be present, any feedback would
be appreciated.
Some coding can be optimised, I am not an itk expert.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dot2D.png
Type: application/octet-stream
Size: 113 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20040913/1b23c493/dot2D-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fastDilate.png
Type: application/octet-stream
Size: 128 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20040913/1b23c493/fastDilate-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: classicDilate.png
Type: application/octet-stream
Size: 132 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20040913/1b23c493/classicDilate-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: itkFastIncrementalBinaryDilateImageFilter.h
Type: application/octet-stream
Size: 8181 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20040913/1b23c493/itkFastIncrementalBinaryDilateImageFilter-0002.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: itkFastIncrementalBinaryDilateImageFilter.txx
Type: application/octet-stream
Size: 25857 bytes
Desc: not available
Url : http://public.kitware.com/pipermail/insight-users/attachments/20040913/1b23c493/itkFastIncrementalBinaryDilateImageFilter-0003.obj