[Insight-users] Fast binary morphology dilation

[Miller, James V (Research)]

Jerome, 

Thanks for the contribution.

The binary dilate code in ITK was designed to:

1) Work with any structuring element
2) Work in a multithreaded environment

There are a filter called DilateObjectMorphologyImageFilter that is operates
on the border on the object.  This is faster.  However, I do not the 
ObjectMorphology approach is thread safe.  I think it also requires that the

"center pixel" of the structuring element is on.

For your point on the exotic structuring elements, from the shifted sums, I 
agree that ITK is not doing the right thing.

What I would like to do is replace the BinaryDilateImageFilter and the
BinaryErodeImageFilter with versions of this fast approach.  We'll need
to the address the threading issue.  I am also not sure about the boundary 
condition.  I think the requested region needs to be padded in case someone
requests the dilation of a subregion of an image.  This is important in 
supporting streaming.  For instance, if a request comes in for the kxk
section
in the middle of an NxN image, you would need have used the (k+2r)x(k+2r)
input
region in order to produce an output that would be consistent with the
output
of a request for a mxm section in the middle of the NxN image (m > k).

I'll take a look at the code and see if this is easily changed. 

Thanks.
Jim


-----Original Message-----
From: jerome schmid [mailto:jerome.schmid at ircad.u-strasbg.fr]
Sent: Monday, September 13, 2004 12:21 PM
To: insight-users at itk.org
Subject: [Insight-users] Fast binary morphology dilation


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.