[ImageJ-devel] Local Neighborhood stuff
Stephan Saalfeld
saalfeld at mpi-cbg.de
Mon Aug 20 05:56:11 CDT 2012
Hi Tobias and all,
great---thanks for spending time on that.
The most important design question in my opinion is what Tobias has now
called the `Safe' vs. `UnSafe' concept. As far as I remember from
previous discussions we do not have a final answer yet to that problem
and I sucked in posting the discussion to the Wiki. So I suggest to
discuss it here now it becomes relevant.
The problem:
Both, accessors (e.g. Cursor) and proxy types (e.g. NativeType) are
stateful. How should they be used in concurrent (e.g. multi-threaded)
code? So far, the contract in ImgLib2 is: one accessor should not be
used concurrently, concurrent threads should each acquire a unique
accessor which, if required, provides a unique proxy type. The inverse
contract is that if you have an accessible (e.g. IterableInterval), then
you can write concurrent code by requesting a unique accessor for each
thread. This becomes problematic when accessibles are `nested', i.e.
the proxy type is an accessible. The contract holds at all nested
levels when using what Tobias has implemented as the `Safe' solution.
It holds only at the top nesting level when using the `UnSafe' solution
where the `inner' accessible uses one single accessor instance. Why
then doing it? Because it is faster. Iterating a 4-neighborhood for
each pixel in a 2d image would be slower when creating a new accessor at
each pixel-location. Why is it problematic? Because methods working
with an accessible as input can be applied to the inner accessibles,
may be implemented concurrently (e.g. apply convolution to a
neighborhood), and do not know at which `nesting' level they are called
(it also sucks to require thinking about that).
Nesting accessibles is clearly a good thing and basically the reason why
ImgLib2 is designed as it is. For `small' accessibles, it is necessary
to break the current contract that an accessible generates independent
accessors, because they would be slow otherwise. So that contract is
broken.
My current idea to solve this issue at compile time is by introducing
the empty interface ConcurrencySafe and require each accessible that
generates independent accessors to implement this interface. Methods
that depend on that must then require their input to implement this
interface, e.g.
<A extends RandomAccessible<T> & ConcurrencySafe>
void convolve(A a, A b){ ... }
Since it doesn't interfere with existing code, it would enable to slowly
add this `security' constraint slowly over time while keeping things
running.
It also means that the safe and unsafe factories would return a generic
interface combination and it can become a bit convoluted to keep that
information for passing such an object into another method using the
buggy Oracle compiler...
An Oracle-friendly option would be to embed that interface into the
interface hierarchy and create the full bunch of concurrency safe
extensions of existing interfaces:
ConcurrencySafeRandomAccessible extends RandomAccessible
ConcurrencySafeIterableInterval extends IterableInterval ...
Obviously, the JDK is not doing this and instead throws Exceptions for
an enormous synchronization and testing overhead at runtime (compare
Vector and ArrayList).
What do you think?
Best,
Stephan
On Fri, 2012-08-17 at 16:24 +0200, Tobias Pietzsch wrote:
> 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
> ImageJ-devel at imagej.net
> http://imagej.net/mailman/listinfo/imagej-devel
More information about the ImageJ-devel
mailing list