<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>Re: [Insight-users] erosion performance for binary images</TITLE>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 8.00.6001.18702"></HEAD>
<BODY>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial>Hi Gaetan and Richard,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial>I can confirm the performance dependence on pixel type
(compare box.us.txt with box.uc.txt for unsigned short and char). For my problem
it's ok to use unsigned char (and also to use a box structure
element).</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial>Thank you guys for sharing your implementations of the binary
contour + iterative filter and the parabolic morphology code. I added both
of them to my little test program, see erosion2.zip. On my pc (WinXP, SP3, 32
bit, Intel Core 2 Quad Q6600 @ 2.4 GHz, 4 GB RAM) I get the following
numbers:</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=078163410-08062009><FONT color=#0000ff
size=2 face=Arial>Box radius: 1<BR> Elapsed time erosion VHGW
(multi-threaded): 14.719s.<BR> Elapsed time contour iterative
(multi-threaded): 0.688s.<BR> Elapsed time parabolic (single-threaded):
5.094s.<BR>Box radius: 2<BR> Elapsed time erosion VHGW (multi-threaded):
19.235s.<BR> Elapsed time contour iterative (multi-threaded):
1.297s.<BR> Elapsed time parabolic (single-threaded): 5.094s.<BR>Box
radius: 4<BR> Elapsed time erosion VHGW (multi-threaded):
14.968s.<BR> Elapsed time contour iterative (multi-threaded):
2.61s.<BR> Elapsed time parabolic (single-threaded): 5.141s.<BR>Box
radius: 8<BR> Elapsed time erosion VHGW (multi-threaded):
36.89s.<BR> Elapsed time contour iterative (multi-threaded):
5.125s.<BR> Elapsed time parabolic (single-threaded): 5.188s.<BR>Box
radius: 16<BR> Elapsed time erosion VHGW (multi-threaded):
20.328s.<BR> Elapsed time contour iterative (multi-threaded):
10.188s.<BR> Elapsed time parabolic (single-threaded): 5.312s.<BR>Box
radius: 32<BR> Elapsed time erosion VHGW (multi-threaded):
30.391s.<BR> Elapsed time contour iterative (multi-threaded):
19.953s.<BR> Elapsed time parabolic (single-threaded):
5.765s.</FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2 face=Arial>So,
erosion based on the binary contours is very fast and the fastest up till a
radius of 8. After that the parabolic morphology algorithm takes over with a
very constant run time of about 5s!</FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT face=Arial><FONT color=#0000ff
size=2>Richard, for the parabolic morphology algorithm I had to
set:</FONT></FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009></SPAN><SPAN class=078163410-08062009><FONT
face=Arial><FONT size=2><FONT color=#0000ff><SPAN
class=078163410-08062009> p</SPAN>arabolic->SetScale(
radii[ i ]*radii[ i ]/2 + 1 );</FONT></FONT></FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2 face=Arial>to
get identical results compared with my baseline algorithm (BinaryErode),
instead of simply setting parabolic->SetScale( radii[ i ] ), like with the
other filters. Does this make sense to you?</FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2 face=Arial>Thanks
again for all your feedback and sharing of this code!</FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial>Regards,</FONT></SPAN></DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial></FONT></SPAN> </DIV>
<DIV><SPAN class=078163410-08062009><FONT color=#0000ff size=2
face=Arial>Marius</FONT></DIV>
<DIV dir=ltr align=left><FONT face=Arial><BR><FONT color=#0000ff
size=2></FONT></FONT></DIV></SPAN><BR>
<BLOCKQUOTE
style="BORDER-LEFT: #0000ff 2px solid; PADDING-LEFT: 5px; MARGIN-LEFT: 5px; MARGIN-RIGHT: 0px"
dir=ltr>
<DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left>
<HR tabIndex=-1>
<FONT size=2 face=Tahoma><B>From:</B> Gaëtan Lehmann
[mailto:gaetan.lehmann@jouy.inra.fr] <BR><B>Sent:</B> Sunday, June 07, 2009
8:50 PM<BR><B>To:</B> Staring, M. (LKEB)<BR><B>Cc:</B>
insight-users@itk.org<BR><B>Subject:</B> Re: [Insight-users] erosion
performance for binary images<BR></FONT><BR></DIV>
<DIV></DIV><!-- Converted from text/plain format --><BR>
<P><FONT size=2>Hi Marius,<BR><BR>I was a bit surprised by the bad results
with the anchor morphology - <BR>it seems to be caused by the pixel type
used. Using unsigned char <BR>instead of unsigned short give those
results for me:<BR><BR>[glehmann@gbook src]$ ./test
../post_zoom_mask.mhd<BR>Box radius: 1<BR> Elapsed time
erosion_binary: 8.67705s.<BR> Elapsed time erosion VHGW:
17.9855s.<BR> Elapsed time erosion Anchor: 26.9067s.<BR>Box
radius: 2<BR> Elapsed time erosion_binary:
9.60058s.<BR> Elapsed time erosion VHGW: 19.3998s.<BR>
Elapsed time erosion Anchor: 27.9886s.<BR>Box radius: 4<BR>
Elapsed time erosion_binary: 12.2166s.<BR> Elapsed time erosion
VHGW: 20.6566s.<BR> Elapsed time erosion Anchor: 28.6419s.<BR>Box
radius: 8<BR> Elapsed time erosion_binary:
20.2531s.<BR> Elapsed time erosion VHGW: 20.6925s.<BR>
Elapsed time erosion Anchor: 30.2072s.<BR>Box radius: 16<BR>
Elapsed time erosion_binary: 50.8547s.<BR> Elapsed time erosion
VHGW: 22.6839s.<BR> Elapsed time erosion Anchor: 31.6612s.<BR>Box
radius: 32<BR> Elapsed time erosion_binary:
156.725s.<BR> Elapsed time erosion VHGW: 27.783s.<BR>
Elapsed time erosion Anchor: 36.0459s.<BR><BR>I guess we have to investigate
what can do that…<BR><BR>I've also implemented an erosion based on
BinaryContourImageFilter. <BR>The contour filter is applied several times
to get the same results as <BR>above. You can get the code at<BR><BR><A
href="http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/iterative.cxx">http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/iterative.cxx</A><BR><A
href="http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.h">http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.h</A><BR><A
href="http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.txx">http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.txx</A><BR><BR>Here
are the execution times for the same box sizes as
above:<BR><BR>0.988033<BR>1.69216<BR>3.10681<BR>6.00902<BR>12.9424<BR>27.6227<BR><BR>That
implementation is faster than all the other filters, up to a <BR>radius
of 32 :-)<BR>It is much limited also, because it works only with binary
images, and <BR>the same size on all the dimensions of the
radius.<BR><BR>All the measures where made on a macbook air with a core 2 duo
at 1.8 <BR>GHz, gcc 4.0.1, ITK 3.14, and built in Release
mode.<BR><BR>More input to come with separable implementations
:-)<BR><BR>Thanks for your feedbacks!<BR><BR>Gaëtan<BR><BR><BR><BR><BR><BR>Le
5 juin 09 à 18:46, <M.Staring@lumc.nl> <M.Staring@lumc.nl> a écrit
:<BR><BR>> Hi Dan and Gaetan,<BR>><BR>> First of all: thanks for your
feedback.<BR>><BR>> I forgot about the importance of the specific choice
of the kernel. <BR>> That makes sense of course. In my test code I
used the line<BR>><BR>>
erosionFilter->SetRadius( radii[ i ] );<BR>><BR>> and assumed it
would be give a ball. Now I use:<BR>><BR>>
erosionFilter-<BR>> >SetKernel(
itk::FlatStructuringElement<Dimension>::Box( radius ) );<BR>>
or<BR>> erosionFilter-<BR>> >SetKernel(
itk::FlatStructuringElement<Dimension>::Ball( radius )
);<BR>><BR>> Then the VHGW filter indeed did not run for the Ball,
because it is <BR>> not decomposable.<BR>><BR>> The new
performance results for ball and box are in the attachments. <BR>> For
the box the binary erode still seems to be faster up till a <BR>>
radius of 8, after which the VHGW takes over. The latter is not <BR>>
constant for increasing radius though.<BR>><BR>> I added the source code
in the zip, so you can reproduce the <BR>> results. You can also find
the binary image on which I did the test <BR>> in the
zip.<BR>><BR>> From: Gaëtan Lehmann [<A
href="mailto:gaetan.lehmann@jouy.inra.fr">mailto:gaetan.lehmann@jouy.inra.fr</A>]<BR>>
The algorithm used in BinaryErodeImageFilter can't be easily<BR>>
constrained to a zone, and so it is difficult to multithread it.<BR>> If
you want to perform an erosion with a radius of 1 (on all the<BR>>
dimension), BinaryContourImageFilter followed by a SubtractImageFilter<BR>>
would be a lot faster (really) especially on a multicore system, as<BR>>
they are both multithreaded. Some timings are available in section 3<BR>>
of <A
href="http://insight-journal.com/download/viewpdf/217/2">http://insight-journal.com/download/viewpdf/217/2</A><BR>><BR>>
I just assumed it would be, since there were multi-threaded
versions <BR>> for grayscale images. But it's an entirely different
algorithm I <BR>> guess.<BR>> Regards,<BR>> Marius<BR>>
<erosion.zip><ball.txt><box.txt><BR><BR>--<BR>Gaëtan
Lehmann<BR>Biologie du Développement et de la Reproduction<BR>INRA de
Jouy-en-Josas (France)<BR>tel: +33 1 34 65 29 66 fax: 01 34
65 29 09<BR><A
href="http://voxel.jouy.inra.fr">http://voxel.jouy.inra.fr</A> <A
href="http://www.itk.org">http://www.itk.org</A><BR><A
href="http://www.mandriva.org">http://www.mandriva.org</A> <A
href="http://www.bepo.fr">http://www.bepo.fr</A><BR><BR></FONT></P></BLOCKQUOTE></BODY></HTML>