<!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=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>Hi Richard,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>I just found your multi-threaded version of the parabolic
morphology package (the IJ version was not your latest
version):</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>Box radius: 1<BR> Elapsed time parabolic
(multi-threaded): 1.469s.<BR>Box radius: 2<BR> Elapsed time parabolic
(multi-threaded): 1.313s.<BR>Box radius: 4<BR> Elapsed time parabolic
(multi-threaded): 1.328s.<BR>Box radius: 8<BR> Elapsed time parabolic
(multi-threaded): 1.375s.<BR>Box radius: 16<BR> Elapsed time parabolic
(multi-threaded): 1.375s.<BR>Box radius: 32<BR> Elapsed time parabolic
(multi-threaded): 1.515s.<BR></FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>on my quad-core machine.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>I guess I can stop looking around for the fastest binary
erosion filter :-)</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>Great work,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=593272713-08062009><FONT color=#0000ff
size=2 face=Arial>Marius</DIV></FONT></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> insight-users-bounces@itk.org
[mailto:insight-users-bounces@itk.org] <B>On Behalf Of
</B>M.Staring@lumc.nl<BR><B>Sent:</B> Monday, June 08, 2009 12:46
PM<BR><B>To:</B> gaetan.lehmann@jouy.inra.fr<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>
<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>
<P><FONT size=2 face=Arial>No virus found in this incoming message.<BR>Checked
by AVG - www.avg.com<BR>Version: 8.5.339 / Virus Database: 270.12.56/2161 -
Release Date: 06/08/09 06:01:00<BR></FONT></P>
<P><FONT size=2 face=Arial></FONT></P></BLOCKQUOTE></BODY></HTML>