[Insight-users] erosion performance for binary images

Fri Jun 5 11:09:23 EDT 2009

Le 5 juin 09 à 16:03, <M.Staring at lumc.nl> <M.Staring at lumc.nl> a écrit :

> Hi all (Gaetan),
>

Hi Marius,

> I am wondering what is the fastest performing filter for the erosion  
> of 3D binary data.
>
> I have tried the BinaryErodeImageFilter and the several flavours of  
> erosion filters from the review directory  
> (OptGrayscaleErodeImageFilter: BASIC, HISTO, VHGW, ANCHOR),  
> contributed by Gaetan

Richard Beare has also written a lot of code in that contrib

> , on a large (512x512x142) binary 3D dataset. These new filters,  
> which I expected to be much faster, appeared to be slower. I think  
> that is because these filters are all suitable for grayscale images,  
> so they are "too general" for my problem. Do you think that  
> assumption is correct?

I don't think so. They should work well also in that case.

>
> Here are some performance numbers:

van Herk / Gil Werman and Anchor algorithm are not usable with a ball  
structuring element. They can only work with structuring elements  
which provide some lines - for example, a structuring element created  
with

   itk::FlatStructuringElement::Box()

Also, the binary execution time with erode filter is *very* dependent  
of the content of the image - that's not the case for the others. With  
an image with lot of pixels on the contour of the object, you may have  
a lot longer execution time.

>
> Ball radius: 1
>   Elapsed time erosion_binary: 5.422s.
>   Elapsed time erosion basic: 1.875s.
>   Elapsed time erosion HISTO: 11.86s.
>   Elapsed time erosion VHGW: 17.734s.
>   Elapsed time erosion Anchor: 33.891s.
> Ball radius: 2
>   Elapsed time erosion_binary: 5.704s.
>   Elapsed time erosion basic: 9.312s.
>   Elapsed time erosion HISTO: 26.954s.
>   Elapsed time erosion VHGW: 13.031s.
>   Elapsed time erosion Anchor: 33.484s.
> Ball radius: 4
>   Elapsed time erosion_binary: 6.453s.
>   Elapsed time erosion basic: 67.047s.
>   Elapsed time erosion HISTO: 82.063s.
>   Elapsed time erosion VHGW: 43.719s.
>   Elapsed time erosion Anchor: 44.75s.
> Ball radius: 8
>   Elapsed time erosion_binary: 9.547s.
>   Elapsed time erosion basic: 603.593s.
>   Elapsed time erosion HISTO: 299.89s.
>   Elapsed time erosion VHGW: 13.062s.
>   Elapsed time erosion Anchor: 37.094s.
> Ball radius: 16
>   Elapsed time erosion_binary: 21.625s.
>   Elapsed time erosion basic: too slow
>   Elapsed time erosion HISTO: too slow
>   Elapsed time erosion VHGW: 17.922s.
>   Elapsed time erosion Anchor: 37.5s.
> Ball radius: 32
>   Elapsed time erosion_binary: 70.391s.
>   Elapsed time erosion VHGW: 44.375s.
>   Elapsed time erosion Anchor: 57.875s.
> where the BinaryErodeImageFilter is single-threaded and the other  
> ones multi-threaded ( I used 4 cores on my pc).

I'm quite surprised by the execution time you get, especially if you  
have use a ball structuring element.
Can you share your test program and your input data, so I can try to  
reproduce?

>
> So, as I currently understand the BinaryErodeImageFilter is the  
> fastest one for this task up till a radius of 8-16, even though it  
> is single-threaded. After that the VanHerkGilWerman method takes  
> over, probably due to it's multi-threadedness. Does anyone know of  
> an erosion filter potentially faster than the  
> BinaryErodeImageFilter, that I missed? Does anyone have a multi- 
> threaded version of the BinaryErodeImageFilter lying around?

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

>
> When I set ITK_USE_CONSOLIDATED_MORPHOLOGY to true, the base class  
> of BinaryErodeImageFilter, namely BinaryMorphologyImageFilter is  
> replaced by an optimized version. However, this does not seem to  
> change anything, since the GenerateData() of BinaryErodeImageFilter  
> is not overridden. Was it supposed to change?

It change the base class of BinaryMorphologyImageFilter for  
KernelImageFilter, which contain some code shared by all the filters  
which are working with kernels, and give some facility method, like  
SetRadius() to set a bok kernel of given radius, like in all the  
filter which are working on neighborhoods (median, mean, ... filters).

>
> Thanks for you advise/comments,
>

You're welcome !

Gaëtan

-- 
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/20090605/3029bc42/attachment.pgp>