[Insight-users] An informal comparison between itk::BinaryDilateImageFilter and Matlab's imdilate()

Sat Aug 20 02:26:24 EDT 2011

Yes, this is entirely true. For example, I've tested the binary dilate
in version 3.20 and the van Herk method available under the review
section as well as a version that uses parabolic morphology (that I've
found to be the fastest in the past) on an image of the size you
mentioned with 3.8% of randomly selected pixels turned on. The vanHerk
method is general purpose (works with grayscale images) and both gave
a time of 83 seconds on a first generation macbook air. The binary
filter is not multi-threaded, while the vanHerk is. The parabolic one
performed far worse, although I'm not sure why yet. My timings were
very similar to those reported earlier in the thread, but I think my
test machine is probably much slower. However, as Gaetan said, the
image structure is important for many of these optimized methods. It
shouldn't matter for vanHerk though, and should only matter slightly
for parabolic. In addition, for large images the bottleneck often
becomes memory bandwidth, so a method that might appear bad in terms
of a basic complexity analysis may perform well if the available
memory bandwidth happens to be utilized more effectively.

2011/8/19 Gaëtan Lehmann <gaetan.lehmann at jouy.inra.fr>:
>
> Hi,
>
> The current implementation of the binary dilation/erosion is highly
> dependent on the content of the image, so doing a direct comparison is not
> as simple as expected.
> Also, for small kernels, the current implementation might be less efficient
> than the brute force implementation.
>
> I already have a FFT based binary erosion/dilation ready and I think I'll
> reintroduce the brute force implementation in ITK while reviewing the
> morphology classes for ITK v4. As for grayscale operations, a meta class
> will be in charge of dispatching the processing to one algorithm or the
> other based on a few heuristics.
> That way the user can almost always get the best of the implementation.
>
> Regards,
>
> Gaëtan
>
>
> Le 17 août 11 à 05:26, Richard Beare a écrit :
>
>> Hi,
>>
>> Can you post your desired test image somewhere?
>>
>> There are a few other issues to clarify before you can really nail
>> down the best way to go. Notably, the precise choice of structuring
>> element shape and the range of sizes you are going to be interested
>> in.
>>
>> There are a range of optimized ITK filters for specific shapes that
>> can be orders of magnitude faster than naive implementations,
>> especially for large structuring elements. In some cases you are
>> actually better off using the general purpose operations, rather than
>> the binary, because of these optimizations.
>>
>> imdilate in matlab uses some of these - if, for example, you are
>> interested in a rectangular structuring element you'll see a big
>> speedup over the naive implementation, which may be what you are
>> getting at present.
>>
>> 2011/8/16 Bradley Lowekamp <blowekamp at mail.nih.gov>:
>>>
>>> Hello Casero,
>>>
>>>
>>> Thank you for the interesting study. I have just 2 comments. You didn't
>>> say what compiler you used. Certain optimizing compilers can produce code
>>> that is 10-20% faster then gcc and I have even seem upto 30% when targeted
>>> for your particular CPU. So I think the two versions are relatively close.
>>> Additionally, ITK is open source so if you see room for improvement in ITK's
>>> implementaion you are able to improve the performance ITK, or specialize the
>>> choices or assumptions is makes for your data.
>>>
>>> Brad
>>>
>>> On Aug 15, 2011, at 6:46 AM, Ramón Casero Cañas wrote:
>>>
>>>>
>>>> Hi all,
>>>>
>>>> After writing a program to run filters derived from
>>>> itk::ImageToImageFilter in Matlab [1], I though to make an informal
>>>> comparison between ITK and Matlab's 3D binary dilation.
>>>>
>>>> I run both on a 574x532x1024 uint8 binary image with 3.8% of voxels ==
>>>> 1, a couple of times, on linux 64-bit, with a 3-voxel radius.
>>>>
>>>>
>>>> itk::BinaryDilateImageFilter (from ITK v3.20) took between 87 and 88
>>>> sec.
>>>>
>>>> Matlab's imdilate()  (from Matlab R2010b) took between 76 and 79 sec.
>>>>
>>>>
>>>>
>>>> My program uses itk::ImportImageFilter to run the filter directly on the
>>>> Matlab buffer, and also uses a Matlab buffer for the filter output
>>>> (using mummification).
>>>>
>>>> The Matlab function invokes a MEX file, so in both cases we are running
>>>> C++ compiled code on the same data.
>>>>
>>>>
>>>> So, the conclusion of this informal comparison would be that Matlab's
>>>> implementation of binary dilation seems 12% faster than ITK's.
>>>>
>>>>
>>>>
>>>> [1]
>>>>
>>>> http://code.google.com/p/gerardus/source/browse/tags/release-0.6.0/matlab/ItkToolbox/ItkImFilter.cpp
>>>>
>>>>
>>>>
>>>> Best regards,
>>>>
>>>> Ramon.
>>>>
>>>> --
>>>> Dr. Ramón Casero Cañas
>>>>
>>>> Computational Biology
>>>> Department of Computer Science
>>>> University of Oxford
>>>> Wolfson Building, Parks Rd
>>>> Oxford OX1 3QD
>>>>
>>>> tlf     +44 (0) 1865 610737
>>>> web     http://web.comlab.ox.ac.uk/people/Ramon.CaseroCanas
>>>> photos  http://www.flickr.com/photos/rcasero/
>>>> _____________________________________
>>>> Powered by www.kitware.com
>>>>
>>>> Visit other Kitware open-source projects at
>>>> http://www.kitware.com/opensource/opensource.html
>>>>
>>>> Kitware offers ITK Training Courses, for more information visit:
>>>> http://www.kitware.com/products/protraining.html
>>>>
>>>> Please keep messages on-topic and check the ITK FAQ at:
>>>> http://www.itk.org/Wiki/ITK_FAQ
>>>>
>>>> Follow this link to subscribe/unsubscribe:
>>>> http://www.itk.org/mailman/listinfo/insight-users
>>>
>>> _____________________________________
>>> Powered by www.kitware.com
>>>
>>> Visit other Kitware open-source projects at
>>> http://www.kitware.com/opensource/opensource.html
>>>
>>> Kitware offers ITK Training Courses, for more information visit:
>>> http://www.kitware.com/products/protraining.html
>>>
>>> Please keep messages on-topic and check the ITK FAQ at:
>>> http://www.itk.org/Wiki/ITK_FAQ
>>>
>>> Follow this link to subscribe/unsubscribe:
>>> http://www.itk.org/mailman/listinfo/insight-users
>>>
>> _____________________________________
>> Powered by www.kitware.com
>>
>> Visit other Kitware open-source projects at
>> http://www.kitware.com/opensource/opensource.html
>>
>> Kitware offers ITK Training Courses, for more information visit:
>> http://www.kitware.com/products/protraining.html
>>
>> Please keep messages on-topic and check the ITK FAQ at:
>> http://www.itk.org/Wiki/ITK_FAQ
>>
>> Follow this link to subscribe/unsubscribe:
>> http://www.itk.org/mailman/listinfo/insight-users
>
> --
> 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://mima2.jouy.inra.fr  http://www.itk.org
> http://www.bepo.fr
>
>