[Insight-users] erosion performance for binary images

[Gaëtan Lehmann]

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 --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 203 bytes
Desc: Ceci est une signature ?lectronique PGP
URL: <http://www.itk.org/pipermail/insight-users/attachments/20090607/28dbc428/attachment.pgp>