[Insight-users] Anisotropic diffusion

[Joshua Cates]

Hi Luca,

Thanks for the feedback on the anisotropic diffusion code.  Hope I can
answer some of your concerns.

I am a little surprised at the magnitude of the slow-down you are seeing,
but a significant slow-down is to be expected when adding a dimension.

There are many factors at work:

A non-linear decrease in speed is consistent with the complexity of the
anisotropic diffusion algorithm, which is not separable, like, for
example, Gaussian blurring. (Also note that a single 3D diffusion of
stacked slices will *not* produce the same result as 2D diffusions on
those slices individually.)

Algorithmic complexity aside, you are incurring additional penalties from
two other sources:

(1) The most significant penalty comes from resolving boundary conditions.
By using two slices, you place every pixel on a data-set boundary because
the algorithm needs a 3x3 neighborhood of pixels for its calculations.
The anisotropic diffusion algorithms are optimized to process non-boundary
pixels and boundary pixels using different methods.  As you might expect,
processing a boundary pixel is *much* slower because missing data must be
identified and then generated.

So when you go from 2 to 3 dimensions, you have gone from 512x4 boundary
pixels to 512x512x2 boundary pixels.  If you were to increase the number
of slices to N, you would have 512x512x2 + 512x4x(N-2) boundary pixels.
Thus, this boundary condition overhead is most noticeable when using just
2 slices.

(2) There is some additional overhead due to the way the ND diffusion code
(which is used for 3D volumes) is implemented.  This I can do something
about, but it involves a bit of redesign work, so may take some time to
get into the toolkit.  I expect these improvements will make a noticible
difference, but only be really significant for volumes of 4+ dimensions.


Some suggestions for improving execution times:

The code is designed to automatically multi-thread if multiple processors
are available.  We have seen near linear speed-ups in execution time using
multiple processors.

Padding your 2D volume with appropriate boundary values and then
processing only pixels you are interested in will eliminate the
algorithm's need to calculate boundary conditions.  This will speed up
execution times.


Regarding instabilities in your solutions:

The instabilities you are seeing may be a result of the time-step value
you are using.  Try decreasing the time-step value (less than 0.125 should
be stable for calculations in 3D).  The number of slices should not have
any effect on the stability of the solution.


Hope this helps.  If you continue to see instabilities in your solutions
please let me know.

Thanks,

Josh.

______________________________
 Josh Cates
 School of Computer Science
 University of Utah
 Email: cates@sci.utah.edu
 Phone: (801) 587-7697
 URL:   www.cs.utk.edu/~cates


On Thu, 18 Apr 2002, Luca Antiga wrote:

> Dear users,
> I noticed that anisotropic diffusion filters experience a great decrease in
> performance when switching from 2D to 3D (two 2D 512x512 images take tens of
> seconds, while the same images in a 512x512x2 volume take minutes).
> Furthermore, increasing the number of slices in input to
> itk::CurvatureAnisotropicDiffusionImageFilter is likely to produce
> instabilities in the output. Are these problems going to be solved in the
> future?
> Thank you all for your great work. You rule!
>
> Luca
>
> _________________________________________________________________
> Chat with friends online, try MSN Messenger: http://messenger.msn.com
>
> _______________________________________________
> Insight-users mailing list
> Insight-users@public.kitware.com
> http://public.kitware.com/mailman/listinfo/insight-users
>