[Insight-users] erosion performance for binary images

Mon Jun 8 06:45:57 EDT 2009

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/87288a8c/attachment-0001.htm>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: box.uc.txt
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/87288a8c/attachment-0003.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: box.us.txt
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/87288a8c/attachment-0004.txt>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: erosion2.zip
Type: application/x-zip-compressed
Size: 21237 bytes
Desc: erosion2.zip
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/87288a8c/attachment-0001.bin>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: box.uc.2.txt
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090608/87288a8c/attachment-0005.txt>