[Insight-developers] Re: integrating the new algorithms for existing filters in ITK

[Richard Beare]

Hi everyone,

I've tidied up the code in the base class so that the two options can
be selected using a method rather than setting macros and recompiling.
I haven't extended access to the method outside the base class though.
The code is in Gaetan's darcs repository

darcs get http://voxel.jouy.inra.fr/darcs/contrib-itk/fastReconstruction

The SetMkInternalCopy method uses padded copies of the control and
marker images produced by the ConstantPadImageFilter and crops the
results. If this method isn't called the boundary conditions are
implemented using the neighborhood operators. When copies are used the
neighborhood iterators are set to the body region of the image
computed using the face calculator. The timing measurements are

2D without MkInternalCopy
#F      Vincent
0       0.0276715
1       0.0371164

2D with MkInternalCopy
#F     Vincent
0       0.0209461
1       0.0277335

3D without MkInternalCopy
#F     Vincent
0       4.29707
1      10.2227
3D with MkInternalCopy
#F     Vincent
0       3.19796
1       5.71459

So, as you can see, some gain in performance.

The method I'm using is applicable to a number of the morphological
filters that use a flooding approach - basically setting the border to
a marker value can be used to terminate flooding without boundary
checks being required. The downside is the requirement for making
image copies inside each filter. In this example we have a copy of
each input image.

In a pipeline of several such filters it would be better to pad the
images at the beginning of the pipeline and crop the result at the end
and then tell the filters in the pipeline that they can do whatever
they like with the borders. In some cases this will allow filters to
avoid copies. In cases where copies are still necessary (such as when
the flooding is controlled by the input image) the copy will be
slightly reduced in size. An alternative would be to simply discard
the border and not pad at all - perfectly acceptable for some
applications.

I initially suspected that there were considerable gains to be made by
doing this, but I can't be certain how generally applicable it is or
how much complication will be added. My first thought was that we
should agree on a method name for selecting from the variety of
situations - one thing to support internal copies, one to sacrifice
borders. I guess this can't really hurt. It would be nice if someone
who really knows the system well thought about how to structure
filters with these capabilities - I'm sure the approach I've taken is
a bit messy.

On a related note - could I request that explicit disabling of
boundary checking be enabled for shaped neighborhood iterators as well
as neighborhood iterators? Is there a reason to not allow this?

On 12/12/06, Gaetan Lehmann <gaetan.lehmann at jouy.inra.fr> wrote:
>
> concerning that specific case, the image can be padded without problem:
> that's still a huge improvement concerning memory usage.
> In my implementation - the current ITK one - the indexes are put in a
> std::set. I can say now that it was not a good choice, and some big images
> can't be processed on my 2GB computer, whereas your filter work just nice.
>
> Gaetan
>
> On Tue, 12 Dec 2006 02:02:00 +0100, Richard Beare
> <richard.beare at gmail.com> wrote:
>
> > Hi,
> >
> > I think it will be highly variable with image size, since cache
> > performance tends to be such a major factor.
> >
> > I'll revisit the reconstruction filter to try and produce some numbers.
> >
> > On 12/12/06, Luis Ibanez <luis.ibanez at kitware.com> wrote:
> >>
> >> Hi Richard,
> >>
> >> I recall that Jim have posted comments related to the padding.
> >>
> >> Could you give us an indication of what is the magnitude of
> >> RAM penalty versus the gain in computation time ?
> >>
> >> Depending on that ratio, it may or may not be worth diverging
> >> from the current coding practices.
> >>
> >>
> >>    Thanks for any hint,
> >>
> >>
> >>       Luis
> >>
> >>
> >> ---------------------
> >> Richard Beare wrote:
> >> > Just a note about the reconstruction filter - there is some ugliness
> >> > relating to performance experiments in that class that will need to be
> >> > removed.
> >> >
> >> > Those experiments highlight a general problem about how difficult it
> >> > is to design efficient general pupose boundary conditions. In queue
> >> > based morphological algorithms a common strategy is to pad the images
> >> > with a max or min to provide a border. In itk this can be done
> >> > explicitly or implicitly - explict padding results in a quicker
> >> > filter, but higher ram usage. Optimization using face calculators is
> >> > not an option in many cases. Sacrificing a border pixel is also
> >> > possible to improve performance.
> >> >
> >> > The same strategy can also be used in watershed and regional extrema
> >> > filters.
> >> >
> >> > It would be nice if we could establish a few conventions that support
> >> > these options consistently.
> >> >
> >> >
> >> >
> >> > On 12/11/06, Gaetan Lehmann <gaetan.lehmann at jouy.inra.fr> wrote:
> >> >
> >> >>
> >> >> Hi Luis,
> >> >>
> >> >> The new connected component and morphological reconstruction filters
> >> done
> >> >> by Richard are ready for a long time now, and work very well.
> >> >>
> >> >> The reconstruction filters are a lot faster, and much important, are
> >> a
> >> >> lot
> >> >> more efficient concerning memory usage.
> >> >>
> >> >> The connected component is a lot more efficient, gives consecutive
> >> >> labels,
> >> >> and is able to label an image containing 255 objects with a 8 bit
> >> pixel
> >> >> type - the current filter nearly always fail in that case. This last
> >> >> feature let the user decrease the memory usage, which is quite
> >> important
> >> >> for me currently.
> >> >>
> >> >> I have put those filters in my ITK tree (not in the nightly test
> >> builds
> >> >> this time :-) ) and all the tests are ok. Can I put those new
> >> algorithms
> >> >> in the cvs repository ?
> >> >>
> >> >> Thanks,
> >> >>
> >> >> Gaetan
> >> >>
> >> >>
> >> >> --
> >> >> 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
> >> >>
> >> >
> >>
>
>
>
> --
> 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
>