[Insight-users] erosion performance for binary images
M.Staring at lumc.nl
M.Staring at lumc.nl
Mon Jun 8 09:29:55 EDT 2009
Hi Richard,
I just found your multi-threaded version of the parabolic morphology package (the IJ version was not your latest version):
Box radius: 1
Elapsed time parabolic (multi-threaded): 1.469s.
Box radius: 2
Elapsed time parabolic (multi-threaded): 1.313s.
Box radius: 4
Elapsed time parabolic (multi-threaded): 1.328s.
Box radius: 8
Elapsed time parabolic (multi-threaded): 1.375s.
Box radius: 16
Elapsed time parabolic (multi-threaded): 1.375s.
Box radius: 32
Elapsed time parabolic (multi-threaded): 1.515s.
on my quad-core machine.
I guess I can stop looking around for the fastest binary erosion filter :-)
Great work,
Marius
________________________________
From: insight-users-bounces at itk.org [mailto:insight-users-bounces at itk.org] On Behalf Of M.Staring at lumc.nl
Sent: Monday, June 08, 2009 12:46 PM
To: gaetan.lehmann at jouy.inra.fr
Cc: insight-users at itk.org
Subject: Re: [Insight-users] erosion performance for binary images
Hi Gaetan and Richard,
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).
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:
Box radius: 1
Elapsed time erosion VHGW (multi-threaded): 14.719s.
Elapsed time contour iterative (multi-threaded): 0.688s.
Elapsed time parabolic (single-threaded): 5.094s.
Box radius: 2
Elapsed time erosion VHGW (multi-threaded): 19.235s.
Elapsed time contour iterative (multi-threaded): 1.297s.
Elapsed time parabolic (single-threaded): 5.094s.
Box radius: 4
Elapsed time erosion VHGW (multi-threaded): 14.968s.
Elapsed time contour iterative (multi-threaded): 2.61s.
Elapsed time parabolic (single-threaded): 5.141s.
Box radius: 8
Elapsed time erosion VHGW (multi-threaded): 36.89s.
Elapsed time contour iterative (multi-threaded): 5.125s.
Elapsed time parabolic (single-threaded): 5.188s.
Box radius: 16
Elapsed time erosion VHGW (multi-threaded): 20.328s.
Elapsed time contour iterative (multi-threaded): 10.188s.
Elapsed time parabolic (single-threaded): 5.312s.
Box radius: 32
Elapsed time erosion VHGW (multi-threaded): 30.391s.
Elapsed time contour iterative (multi-threaded): 19.953s.
Elapsed time parabolic (single-threaded): 5.765s.
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!
Richard, for the parabolic morphology algorithm I had to set:
parabolic->SetScale( radii[ i ]*radii[ i ]/2 + 1 );
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?
Thanks again for all your feedback and sharing of this code!
Regards,
Marius
________________________________
From: Gaëtan Lehmann [mailto:gaetan.lehmann at jouy.inra.fr]
Sent: Sunday, June 07, 2009 8:50 PM
To: Staring, M. (LKEB)
Cc: insight-users at itk.org
Subject: Re: [Insight-users] erosion performance for binary images
Hi Marius,
I was a bit surprised by the bad results with the anchor morphology -
it seems to be caused by the pixel type used. Using unsigned char
instead of unsigned short give those results for me:
[glehmann at gbook src]$ ./test ../post_zoom_mask.mhd
Box radius: 1
Elapsed time erosion_binary: 8.67705s.
Elapsed time erosion VHGW: 17.9855s.
Elapsed time erosion Anchor: 26.9067s.
Box radius: 2
Elapsed time erosion_binary: 9.60058s.
Elapsed time erosion VHGW: 19.3998s.
Elapsed time erosion Anchor: 27.9886s.
Box radius: 4
Elapsed time erosion_binary: 12.2166s.
Elapsed time erosion VHGW: 20.6566s.
Elapsed time erosion Anchor: 28.6419s.
Box radius: 8
Elapsed time erosion_binary: 20.2531s.
Elapsed time erosion VHGW: 20.6925s.
Elapsed time erosion Anchor: 30.2072s.
Box radius: 16
Elapsed time erosion_binary: 50.8547s.
Elapsed time erosion VHGW: 22.6839s.
Elapsed time erosion Anchor: 31.6612s.
Box radius: 32
Elapsed time erosion_binary: 156.725s.
Elapsed time erosion VHGW: 27.783s.
Elapsed time erosion Anchor: 36.0459s.
I guess we have to investigate what can do that...
I've also implemented an erosion based on BinaryContourImageFilter.
The contour filter is applied several times to get the same results as
above. You can get the code at
http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/iterative.cxx
http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.h
http://voxel.jouy.inra.fr/darcs/contrib-itk/fof/itkIterativeImageFilter.txx
Here are the execution times for the same box sizes as above:
0.988033
1.69216
3.10681
6.00902
12.9424
27.6227
That implementation is faster than all the other filters, up to a
radius of 32 :-)
It is much limited also, because it works only with binary images, and
the same size on all the dimensions of the radius.
All the measures where made on a macbook air with a core 2 duo at 1.8
GHz, gcc 4.0.1, ITK 3.14, and built in Release mode.
More input to come with separable implementations :-)
Thanks for your feedbacks!
Gaëtan
Le 5 juin 09 à 18:46, <M.Staring at lumc.nl> <M.Staring at lumc.nl> a écrit :
> Hi Dan and Gaetan,
>
> First of all: thanks for your feedback.
>
> I forgot about the importance of the specific choice of the kernel.
> That makes sense of course. In my test code I used the line
>
> erosionFilter->SetRadius( radii[ i ] );
>
> and assumed it would be give a ball. Now I use:
>
> erosionFilter-
> >SetKernel( itk::FlatStructuringElement<Dimension>::Box( radius ) );
> or
> erosionFilter-
> >SetKernel( itk::FlatStructuringElement<Dimension>::Ball( radius ) );
>
> Then the VHGW filter indeed did not run for the Ball, because it is
> not decomposable.
>
> The new performance results for ball and box are in the attachments.
> For the box the binary erode still seems to be faster up till a
> radius of 8, after which the VHGW takes over. The latter is not
> constant for increasing radius though.
>
> I added the source code in the zip, so you can reproduce the
> results. You can also find the binary image on which I did the test
> in the zip.
>
> From: Gaëtan Lehmann [mailto:gaetan.lehmann at jouy.inra.fr]
> The algorithm used in BinaryErodeImageFilter can't be easily
> constrained to a zone, and so it is difficult to multithread it.
> If you want to perform an erosion with a radius of 1 (on all the
> dimension), BinaryContourImageFilter followed by a SubtractImageFilter
> would be a lot faster (really) especially on a multicore system, as
> they are both multithreaded. Some timings are available in section 3
> of http://insight-journal.com/download/viewpdf/217/2
>
> I just assumed it would be, since there were multi-threaded versions
> for grayscale images. But it's an entirely different algorithm I
> guess.
> Regards,
> Marius
> <erosion.zip><ball.txt><box.txt>
--
Gaëtan Lehmann
Biologie du Développement et de la Reproduction
INRA de Jouy-en-Josas (France)
tel: +33 1 34 65 29 66 fax: 01 34 65 29 09
http://voxel.jouy.inra.fr http://www.itk.org
http://www.mandriva.org http://www.bepo.fr
No virus found in this incoming message.
Checked by AVG - www.avg.com
Version: 8.5.339 / Virus Database: 270.12.56/2161 - Release Date: 06/08/09 06:01:00
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/7f029392/attachment-0001.htm>
More information about the Insight-users
mailing list