[ImageJ-devel] Local Neighborhood stuff

[Tobias Pietzsch]

Hi,

the last two days, I finally took some time to take a deeper look at
the Local Neighborhoods. About a year ago, I discussed with Stephan
Saalfeld the idea that Neighborhood systems could just be nested
Accessibles. I did a lot of exploratory implementation and it all lead
naturally back to this idea. It just feels very "Imglib-like". I think
it's the way to go.

I made a proof-of-concept implementation which I just pushed to branch
"tobias-neighborhood-experiments".  After playing around a lot, I have
basically come up with the following design:


Neighborhood<T>
===============
The interface Neighborhood<T> extends Localizable, IterableInterval<T>.
It is _not_ Positionable. It is simply at a fixed location.


Cursor/RandomAccess< Neighborhood<T> >
========================================
To move a neighborhood around, we use standard accessor interfaces.
Assume you have a RandomAccess<Neighborhood<T>> a.
Using a.setPosition() you can position the center of the neighborhood.
Using a.get() you obtain a Neighborhood<T> (which you can then iterate).

In many ways, the Neighborhood is like a NativeType. It is just a
reference into an underlying structure. If you have a Cursor<T> of
a NativeType, then the result T t = cursor.get() will be invalidated
when you advance the cursor. The same holds for Cursor<Neighborhood<T>>.
When you move the cursor, the neighborhood Neighborhood<T> n =
cursor.get() will be invalidated when you advance the cursor.


IterableInterval/RandomAccessible< Neighborhood<T> >
====================================================
Of course, once you have the Accessors, it's easy to put the into
Accessibles and benefit from all the goodies that are in ImgLib already.
For example, if you have implemented a RandomAccess<Neighborhood<T>>
it is straightforward to wrap it into a RandomAccessible and use
Views.iterable() to get a Cursor over Neighborhood<T>.

This results is pure syntactic sugar and lets you write sexy code like
this:
   for ( Neighborhood<T> n : neighborhoods )
       for ( T t : n )
           ...

Shape
=====
At the top level is the interface "Shape". This is basically a factory
for Accessibles on Neighborhoods. Every type of neighborhood should 
provide such a factory. There are four methods. The first is

   public <T> IterableInterval<Neighborhood<T>>
       neighborhoods( final RandomAccessibleInterval<T> source );

This will give you an IteratableInterval over all neighborhoods in the 
source image. Augmenting the above example, in actual code it is used
like this:
   Img<FloatType> img;
   long radius;
   HyperSphereShape shape = new HyperSphereShape( radius );
   for ( Neighborhood<FloatType> n : shape.neighborhoods( img ) )
       for ( FloatType t : n )
           ...

The second method is

   public <T> RandomAccessibleInterval<Neighborhood<T>>
       neighborhoodsRandomAccessible(
           final RandomAccessibleInterval<T> source );

which gives you a RandomAccessibleInterval over all neighborhoods.
Then there are "safe" variants of these two methods, which I will 
discuss later because it goes a bit deeper into the details...

Examples
========
I have fully implemented RectangleShape which supports
(hyper-)rectangular neighborhoods. This is rather involved, because
it supports both neighborhoods that skip the center pixel and such
that don't; it has both an implementation of Cursor<Neighborhood<T>>
and RandomAccess<Neighborhood<T>> for optimal speed; and so on...

There is an incomplete implementation of HyperSphereShape, which
despite being incomplete should be a better example to look at first.
Basically I just copied and pasted from HyperSphereCursor.
In this case, there is only a RandomAccess<Neighborhood<T>>. The
Cursor is simply build using Views.iterable().

Unfortunately, the code is still largely undocumented. I put effort
into documenting the Shape interface, but that's it basically :(

As an example for how to use Neighborhoods, please see
net.imglib2.algorithm.region.localneighborhood.MinFilterExample
in the imglib2-tests sub-project.
Actually, just let me paste a fragement here. This implements a
minimum filter using arbitrary neighborhood Shape:

public static <T extends Type<T> & Comparable<T> > void
     minFilter( final RandomAccessibleInterval<T> input,
                final RandomAccessibleInterval<T> output,
                final Shape shape )
{
   final RandomAccess< T > out = output.randomAccess();
   for (final Neighborhood<T> neighborhood : shape.neighborhoods(input))
   {
     out.setPosition( neighborhood );
     final T o = out.get();
     o.set( neighborhood.firstElement() );
     for ( final T i : neighborhood )
       if ( i.compareTo( o ) < 0 )
         o.set( i );
   }
}

Beautiful, isn't it?

Safe vs Unsafe Neighborhoods
============================
About the "safe" variants of the methods in Shape. The above "unsafe"
variants behave as follows: A Neighborhood<T> that you obtained from the
returned accessible will re-use a single Cursor instance. That is:
   Neighborhood<T> n = shape.neighborhoods( img ).firstElement();
   Cursor<T> c1 = n.cursor();
   Cursor<T> c2 = n.cursor();
Here, c1 and c2 will be the same object! This is necessary to make
the nested loops shown above really fast. Otherwise here,
   for ( Neighborhood<T> n : neighborhoods )
       for ( T t : n )
in every iteration of the outer loop, a new Cursor would be created for
the inner loop.
I decided to make the "unsafe" option the default, i.e., the methods are
called Shape.neighborhoods() and Shape.neighborhoodsSafe() instead of
Shape.neighborhoodsUnsafe() and Shape.neighborhoods(). I'm open to 
change that, though.

If you require a different behaviour, you can use the
Shape.neighborhoodsSafe and neighborhoodsRandomAccessibleSafe methods.
There are also other options which are described in the javadoc of the 
Shape interface. Please have a look!

Performance
===========
It can be made quite fast, actually. I have implemented a find-local-
maxima benchmark (see LocalMaximaBenchmark) that compares several
implementations of (3x3x...x3) Neighborhood.

To count local maxima in a 200x200x200 float image, I get
683 ms using RectangleShape vs
877 ms using the old LocalNeighborhoodCursor



As you might have noticed, I have completely neclected the copyOn() and
updateSource() methods we discussed before.  I don't really see the need
for them in the above design.

Ok, I hope you will have a look at the code
(branch "tobias-neighborhood-experiments") and tell me what you think.

best regards,
Tobias


On 07/27/2012 05:35 PM, Jean-Yves Tinevez wrote:
>
> Hi all
>
> I pushed some changes to the test branch: I removed the realpositionable
> stuff, and tried to draft the mother interface from our discussions.
>
> But I got stuck at the copyOn method. If I try to make it as generic as
> I can (copy on a different RandomAccessible type and on a different
> type), concrete implementations that are more specific (like the
> buffered rectangle) fail on bad type bounds. I could use some help there.
>
> Best
> jy
>
>