[Insight-users] itkBinaryDilateImageFilter speed 4D data

[Richard Beare]

I have a couple of filters for binary morphology that are quite fast - they
are separable and based on morphology using parabolic structuring
functions. There are two repositories - one for general parabolic
operations and one for specialised operations on label images. The general
one contains classes for binary operations and distance transforms.

The limitations and/or restrictions of the classes used on binary images
are 1) Spherical structuring elements (SE) or ellipses aligned with axes -
no other shapes possible 2) the binary image has to be 1/0 valued, not
255/0, for example.

Repositories are:

https://github.com/richardbeare/parabolicMorphology.git

https://github.com/richardbeare/LabelErodeDilate.git

and the insight journal article about the second one is

*http://hdl.handle.net/10380/3399* <http://hdl.handle.net/10380/3399>

Also note that the greyscale morphology operations in ITK are
multithreaded, and there is a range of tradeoffs with speed vs structuring
element type. They all work on binary images too, without the 1/0
restriction.

For general flat structuring elements there is the option of this "HIST"
algorithm, which uses a sliding window and will give you complexity of
about O(m^(n-1)), where m is the radius of the SE and n is the image
dimension. This is faster than the naive approach for all but the tiniest
SE.

Then there are the Box and Poly structuring elements. These use operations
along lines, probably similar to the approach Brad mentioned, and construct
different shaped SEs by repeated application. The Box does
rectangles/cubes, which are exact. The Poly approximates circles in 2D and
attempts to approximate spheres in 3D, but it isn't great at that.

So in summary, if you are definitely interested in the binary case, and are
after spheres or ellipses, go with the parabolic stuff. If you need a
specific shape that isn't a sphere or rectangle, try the grayscale
morphology histogram methods. In principle these can be made more efficient
for the binary case if you really need the speed.

On Wed, Sep 4, 2013 at 12:15 AM, Bradley Lowekamp <blowekamp at mail.nih.gov>wrote:

> Hello,
>
> Here are some things you can try.
>
> 1) Use the current filter but separate it by decomposing the structuring
> element. run it 3-times with 1-D lines in each direction.
> 2) If your image is just 0s and 1s you can try the grayscale algorithms.
>
> Plug: exploring the performance difference between your current method and
> the two above is something that SimpleITK in python would be very quick at
> doing.
>
> 3) A while ago I prototyped a parallel and more optimized algorithm for
> dilation and closing of 1-D lines. So it only works with Flat structuring
> elements. I haven't had a chance to get back to it to polish it up. So I am
> not sure what the state is, but I was able to use it on my data set and get
> something like 100X speed up between the parallelization and the different
> algorithm.
>
> Here is my ITK external module where I did the work:
> https://github.com/blowekamp/itkBinaryMorphologyPerformance
> I'd write a test a verify the results before I used it.
>
> Good luck and let us know what works for you,
> Brad
>
> On Sep 3, 2013, at 9:59 AM, Jose Ignacio Prieto <
> joseignacio.prieto at gmail.com> wrote:
>
> > Hi, I need your advice for a dilate filter I am using. I have cine 3d
> images (3d+time) loaded as a 4d matrix on itk. They are 25 phases of heart
> MRI images. So my matrix dimensions are 128,128,65,25. Following the
> "connected threshold" example, I apply a CurvatureFlowImageFilter for
> smoothing and then ConnectedThreshold for segmenting the heart and aorta.
> Then I use Binary dilate over the mask to close the holes (for example
> between the vessels).
> > The question is that the dilate operation takes too much time (around 6
> min) and I have noticed that is single-threaded. As the structuring
> elemente I was using binary ball and now I changed to a
> FlatStructuringElement(box) to speed up (as I could read in a forum), but
> it takes the same time. Given that kind of image, what variation could I
> make to have a fast dilation? What about gpu based methods? I have noticed
> that the radius 8 ball is the problematic, when I try 4 or 2 pixel radius
> it works much faster.
> > Thank you very much.
> >
> > --
> > José Ignacio Prieto
> > celular(nuevo): 94348182
> > _____________________________________
> > 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.php
> >
> > 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.php
>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130904/155969ae/attachment-0001.htm>