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
_______________________________________________
ImageJ-devel mailing list
[email protected]
http://imagej.net/mailman/listinfo/imagej-devel
