Add additional ROI shapes and functionality

[awalter17]

Hello!

This branch includes several changes to the ROI API. The "major" changes are:

• Changes Contains to Mask which is the base for all ROIs
• Adds additional real space ROI shapes
  • Implementations which include points on boundary (closed), excludes points on boundary (open), and undefined behavior
• Adds operations for combining/transforming ROIs
  • Earlier in the branch this is done one way, and then at 37df63b this setup is reworked to be functions
• Adds adapters for going between (Real)RandomAccessibles and Masks
• Adds interfaces for ROIs which know their bounds

Some of the changes on this branch are based on the work done in #25.

All the commits on this branch compile with passing tests. @tpietzsch please let me know your thoughts on these changes or if you have any questions.

Thank you very much,

Alison

P.S.: The demos which previously existed on this branch have been moved to roi-demo. These demos require a circular dependency on bdv-core, they'll probably be moved elsewhere at a later date.

[awalter17]

@tpietzsch Have you had an opportunity to review these changes? If not that's fine, but if you could please give me a rough approximation of when you may have the time to review them I would greatly appreciate it.

[tpietzsch]

@awalter17 I haven't looked at it yet, but @ctrueden gave a quick demo at the learnathon and it looked fine. I'll review and merge (most likely) during the upcoming Konstanz hackathon

[tpietzsch]

@awalter17 I looked into it during the Konstanz hackathon as promised. There were a few rough edges and basically I started pulling on a thread and it all came apart... :-) You had Mask extend java.util.function.Predicate (which I like). Predicate has default and(), or(), and negate() methods and it would be reasonable to assume that these do the right thing in Mask (produce another mask). I tried to bend the current PR into that shape but it didn't really work.

There is a complete parallel re-implementation of the core interfaces and all the operator logic in package net.imglib2.troi in this branch. What is missing is mainly the adaption of all concrete shapes to these interfaces, and transform operations. For getting started, have a look at net.imglib2.troi.Demo which recapitulates the testAnd() method of your Demo. It has a lot of comments of what is changed with respect to the old demo. Also there is some javadoc on the re-implementation.

Some notes:

• A decision that was causing problems in your design was to let apply-transform-to-mask be a binary operator which has a mask and a transform as operands. This should be formulated as a (parametrised) unary operator which only has the mask as an operand. This allows for tighter typing of operations results, composite masks, etc.
• The mask operations (OR, AND, ...) are now cleany separated into operations on the BoundaryType (implemented here), on the Bounds (here and here, more on that below), and on the Predicate function (implemented here). There is of course boilerplate to support it, but the core logic for e.g. AND is implemented only once and applies to integral/real/interval/unbounded masks.
• There is now the distinction between real/integer Mask and RealMask interfaces. Before, the Mask<T> was that applied to Localizable or RealLocalizable and then at MaskInterval/MaskRealInterval the hierarchy separated into real/integer. I think that was the main reason why correct implementation of the Predicate operators wasn't possible with the old design.
• The Bounds class encapsulates reasoning about mask boundaries. There are basically too options: A mask can have an interval (outside of which it always evaluates to false) or be unbounded. In the first case, we need special consideration of empty intervals (that can arise for example by ANDing two disjoint MaskIntervals). Empty intervals are recognised by having max<min in at least one dimension. To make sure that these empty intervals union/intersect correctly with other intervals, we report min=POSITIVE_INFINITY/max=NEGATIVE_INFINITY in all dimensions as soon as an interval becomes empty.
• Also, we need to consider changing intervals on masks. I.e. if you have mask1, mask2 and mask1 AND mask2, then if you shift mask1 around, the interval on mask1 AND mask2 needs to change. The alternative would be having only unmodifiable masks. After discussion with @ctrueden, this is not the way we want to go. So we need intervals that combine constituent intervals and update their min/max/emptiness as these constituents are modified. All this is taken care of by inner classes in the Bounds class.

• Fortunately, modifying constituent intervals can never make a (potentially empty) interval become unbounded. Therefore, the interval/unbounded decision can be expressed into argument/return types of the Mask.and() etc methods. For example, consider:

  
  interface Mask extends Predicate<Localizable> ... {
  @Override
  default Mask and( Predicate<? super Localizable> other ) { ... }
  
  @Override
  default Mask or( Predicate<? super Localizable> other ) { ... }
  }

interface MaskInterval extends Mask ... { @Override default MaskInterval and( Predicate< ? super Localizable > other ) { ... }

// *NOT* overriding Mask.or(), just specializing for MaskInterval argument.
default MaskInterval or( MaskInterval other ) { ... }

...

}

`MaskInterval.and(anything)` always results in another `MaskInterval`. For `MaskInterval.or(anything)` it depends on whether `anything` is an interval or not. This is very convenient an avoids unnecessary casting (see Demo).
* Playing with `Sphere`/`Box` for the demo, I found the `double[]`-centered-ness a bit annoying. Maybe we could try to be more imglib-consistent there and allow for `Localizable/Positionable` where appropriate. For exampe, if the `Sphere.center()` would simply give me a `RealLocalizable & RealPositionable` that I can use to move/ask for the sphere's position, that would be convenient. (But I haven't thought that through. Just something I noticed.)
* In your code, you use `transformFromSource`. I would prefer `transformToSource`, otherwise we are restricted to invertible transformations. For example, taking a 2D slice out of a 3D mask is not possible with `transformFromSource`.

There is a second demo [ModifyDemo.java](https://github.com/imglib/imglib2-roi/blob/aec4ce7928d6b92a3398fa0a1d7ff3b195b8ef85/src/test/java/net/imglib2/troi/ModifyDemo.java) that showcases the composite with modifiable parts...
![screen shot 2017-10-03 at 01 09 05](https://user-images.githubusercontent.com/622070/31103484-70c960f2-a7d7-11e7-9631-193316683c46.png)
Three spheres that you can move around and the composite `RealMaskRealInterval composite = s1.and( s2 ).and( s3 );` mask (bright yellow). The interval of the composite is overlaid as a red box (or the text "composite interval is empty").

So, the next TODOs would be
* adapt concrete geom regions to the new interfaces.
* implement transforms (maybe affine on RealMask is enough for now) for the new stuff. Consider `transformFromSource` vs `transformToSource`!
* throw out the old implementation and move package `net.imglib2.troi` to `net.imglib2.roi`.

After that, it would be nice if somebody else (@axtimwalde?) could also do a review because I'm rather biased towards my solution now ... :)

[awalter17]

Thanks @tpietzsch! I have been looking over your changes, and I think they are a big improvement.

I did have one question regarding retrieving operands and operation type (and, or, xor, etc.) from a MaskPredicate which resulted from an operation on MaskPredicate(s). I posted about this in more detail on the forum. If you could please let me know your thoughts on this, I'd greatly appreciate it.

[tpietzsch]

@awalter17 I replied on the forum

[awalter17]

Playing with Sphere/Box for the demo, I found the double[]-centered-ness a bit annoying. Maybe we could try to be more imglib-consistent there and allow for Localizable/Positionable where appropriate. For exampe, if the Sphere.center() would simply give me a RealLocalizable & RealPositionable that I can use to move/ask for the sphere's position, that would be convenient. (But I haven't thought that through. Just something I noticed.)

Initially, I was very careful to ensure that the underlying double[] was never exposed and couldn’t be mutated without using setCenter(...). I also kept the geom regions from being positionable since there was already PositionableIterableRegion. So my intuition was that the concrete geom regions should not be positionable, and instead if the region needed to be positioned Regions.positionable(...) could be used (though it would need to be Iterable first). That being said, I don’t really have strong feelings about this decision.

If I change the center() methods to return a RealLocalizable & RealPositionable, should I just have the geom regions themselves implement RealPositionable? Since they’d essentially be positionable anyway (i.e. Sphere.center().move(...) would be the same as Sphere.move(...)).

I could make a RealPositionableRegion interface and have the geom regions which implement center() implement that interface. I don’t think every geom region needs to be positionable though (i.e RealPointCollection, transformed MaskPredicate, etc.).

Please let me know your thoughts on this @tpietzsch.

[tpietzsch]

@awalter17 I agree with your initial intuition: I would not make the geom regions themselves RealPositionable/RealLocalizable. Mainly because it is unclear where the position is anchored, saying Sphere.center().setPosition() leaves no doubt while the meaning of Sphere.setPosition() is not so clear.

[awalter17]

Hello!

This branch is once again ready for review! I have completed the TODOs that @tpietzsch requested and made a couple of other changes (detailed below).

• Operators -> added logic for detecting when a result is empty or all
  • Empty -> returns false for every location
  • All -> returns true for every location
  • Empty masks also occur when subtracting and xor-ing Masks which are the same shape in the same location
  • Detecting this requires knowledge of both the bounds and the shape
  • Similarly, negating empty space results in all of space and vice versa
• Empty space can be bounded, all of space cannot
  • Why? -> Intervals.isEmpty(...) defines an empty interval as min>max additionally it works well with the mask operations as and-ing (xor, minus) two bounded masks would result in a bounded mask which could be empty. As for all, there wasn’t any situation that I could think of where an operation on bounded masks resulted in all of space. So it made sense to have all never be an interval.
• MaskPredicates know if they are empty or all
  • Allowed Bounds class to be simplified (slightly)
• Overrode equals(...) for all the shapes, which was needed for determining if two masks are equal when performing xor, minus operations
• Transform (only implemented real space transforms)
  • Added new class RealMaskRealTransformOperator to Operators which takes a RealTransform as a parameter
  • Switched to use transformToSource
  • UnsupportedOperationException for apply(...) and applyInterval(...) since I don’t currently support applying RealTransforms to discrete space Predicates
  • Bounds.transform takes Object since there isn’t a common base interface for Transform and RealTransform
  • Transformed masks are only bounded if the transformation is invertible
• Switched double[] center-ness to (Real)Localizable & (Real)Positionable
  • center() and vertex() methods now return a RealLocalizable & RealPositionable
  • Added new interface UpdateBoundsRealPoint which has a callback method updateBounds such that when the given point is moved it calls back to the shape and updates the bounds
  • Most of the shape implementations have an inner class which implements UpdateBoundsRealPoint

@tpietzsch - If you could please provide feedback on the commits starting with 4658f5c9e985a07a9f12bf00287e87c2c9e5fce9, I would greatly appreciate it.

@ctrueden, @axtimwalde, @StephanPreibisch, @haesleinhuepf, @stelfrich, @dietzc - If you could please review the commits starting with 12fb20d08d79529f37a4f5e08d878108d47a74ea, I would greatly appreciate it. (you are of course welcome to review the earlier commits as well, but they all pre-date tpietzsch’s re-implementation)

I have also updated the roi-demo branch to use the new structure and merged in @tpietzsch’s demos. Additionally, I checked that the new structure satisfies all the requirements for my imagej-omero work and it does (Hooray!).

Cheers,

Alison

[awalter17]

Hello @tpietzsch, @ctrueden, @axtimwalde, @StephanPreibisch, @haesleinhuepf, @stelfrich, and @dietzc!

I will only be at the hackathon for the second week (12/11 - 12/15). So if you all could try to review this PR before I arrive, that would be greatly appreciated. That way when I arrive, I can hit the ground running and make any changes. :smile_cat:

Thank you very much, Alison

[awalter17]

Fix test(...) to ensure points outside interval never return true (d2114a4) - ImgLib2 generally prefers performance over bounds checking. Do you remember why we needed this here? What happens if test can return true outside the bounds? For compositing ROIs related to empty/all? Or something else?

I don't remember exactly why ... That being said, there could be an issue if outside the bounds returns true when it isn't supposed to. For example, if you have a ROI which is true outside its bounds and then negate it (which gets rid of the bounds) now the resulting ROI is incorrect. Similar issues occur when you combine this ROI with boundless ROIs.

Add RealPoint that updates bounds whenever moved (cc2cea2) - Can we think of a better name than UpdateBoundsRealPoint? MovableRealPoint? DynamicRealPoint? SmartRealPoint? Or maybe this does not need to be an interface, but just e.g. AbstractGeomRegion?

No, I am unreasonably attached to the name UpdateBoundsRealPoint. So much so, I might name my first child that! (Just kidding! 😸 ) You are more than welcome to change the name, or remove the interface. Do you have any preference? I'm partial to having it just be an abstract class.

I tried intentionally breaking the Masks.EMPTY_AND predicate, but no unit tests failed in response. How is the test coverage here?

There's several tests for that behavior. It's odd that they weren't breaking for you ...

The Bounds class has constants that aren't in all caps, and methods which are in all caps.

... Oops! I'll fix those, good catch!

The isAll flag is not dynamically evaluated. But in some cases, it might require dynamic recomputation similar to isEmpty.

Makes sense.

Thanks for looking at this @tpietzsch and @ctrueden!

[awalter17]

@tpietzsch I have completed the changes you requested from when we last chatted at the hackathon (commits a9cebea to 9856b19). If you could please review these changes at your earliest convenience, I'd greatly appreciate it. Additionally, please feel free to let me know if you have any questions or if you'd like me to make any additional changes.

[awalter17]

Thanks for catching that @imagejan! The capitalization is now correct :smile_cat:

[awalter17]

@tpietzsch, would you like me to make any additional changes? If not, it would be really helpful if you could merge this so I can shift my focus to imagej-omero.

Please feel free to let me know if you have any questions regarding these commits, or if you’d like me to make any additional changes.

[tpietzsch]

The only thing I'm not sure about is that the geom region interfaces Line, Sphere, Box etc have generic parameters (< T extends RealLocalizable & RealPositionable > for the T center() etc. methods). This seems a bit cumbersome to use (basically everywhere Box<?>).

I tried to put the generic on the method e2682f9d5e0635431dc23227ca46e2cd59d00ef2 (branch geom-generics) which seems nicer to use at first. You can have Box b without generic and do b.center().setPosition(...) etc. You can also RealLocalizable pos = b.center(). If you ever want to have a RealLocalizable & RealPositionable reference to center() thats really difficult. More importantly, I was thinking that in the future we might want to have ReadableBox (or so) that is immutable and have Box extend that. This is not doable with generics on the method, i.e., < T extends RealLocalizable & RealPositionable > T center(); cannot override RealLocalizable center(); So I think in the end this wouldn't be a good solution. @ctrueden @axtimwalde any other ideas? Otherwise, I will just merge it as is.

@awalter17 You could go through the tests and examples and replace Box<RealPoint> etc by Box<?> because otherwise I'm sure people will copy&paste Box<RealPoint> into their code and then it's pointless to have the generic there at all... :-)

[awalter17]

I agree the generic is a bit annoying. I don't know if we could get rid of the generic on Box, but perhaps we could make additional interfaces. So Box still has a generic and then is extended by MutableBox, ImmutableBox, etc. So the interfaces would look something like the below. It would also be useful to have a marker interface which extends RealLocalizable and RealPositionable.

public interface Foo extends RealLocalizable, RealPositionable
{
    // NB: marker interface
}

public interface Box< T > extends RealMaskRealInterval
{
    T center();
    double sideLength( int d );
}

public interface MutableBox extends Box< Foo >
{
    void setSideLength( int d, double length )
}

public interface Immutable Box extends Box< RealLocalizable >
{
    // NB: marker interface, for now    
}

And then all my implementations extend the mutable interfaces. The downside to this is that now there’s all these extra interfaces. Also sorry about the names, I couldn’t think of any good names …

Not sure if this is the best option, but it’s an option.

Thoughts @tpietzsch, @ctrueden, @axtimwalde?

[axtimwalde]

What is the reason for not always returning and consuming RealLocalizable?

[tpietzsch]

It allows to mutate the region. sphere.center().setPosition(...) should work.

[tpietzsch]

@awalter17 We always shied away from the "interface which extends RealLocalizable and RealPositionable" because something can implement RealLocalizable and RealPositionable and still is not automatically be usable as Foo. We want to encourage people to write code that takes RealLocalizable & RealPositionable arguments so that it will be most broadly applicable. This works well for method arguments, but not so much for return values. So yes, maybe that Foo interface is the right thing to do here.

[awalter17]

Alternatively, we could bring back setCenter(...). So the base Box interface would only have getters and no generic. And then there could be a separate mutable/writable Box interface, which also has no generics and the setters. This way we wouldn't need the Foo interface.

Personally though, I like box.center().setPosition(...) more than box.setCenter(...).

[tpietzsch]

Personally though, I like box.center().setPosition(...) more than box.setCenter(...).

Me too.

Let's go with your suggestion:

• Make a RealLocalizableRealPositionable combination interface, and have the center() etc return that.
• Make a convenience wrapper, where you can put it a RealLocalizable & RealPositionable and it is wrapped as a RealLocalizableRealPositionable. We will not use this now, but it is helpful if somebody else wants to implement e.g. a Box and only has RealPoint for example.

Put both the interface and the wrapper in net.imglib2.roi.util. I would later add discrete versions. Which would be useful for example here: https://github.com/imglib/imglib2-roi/blob/43e26c3b36d4dd5798ce3cad55b2839c5c9008b1/src/main/java/net/imglib2/roi/labeling/LabelRegion.java#L134

[awalter17]

Make a RealLocalizableRealPositionable combination interface, and have the center() etc return that.

I created the RealLocalizableRealPositionable interface, is that an alright name for it? I'm not sure what else to call it.

Make a convenience wrapper, where you can put it a RealLocalizable & RealPositionable and it is wrapped as a RealLocalizableRealPositionable.

I've created the wrapper as well, is this what you had in mind?

Currently, I've switched the concrete implementations (ClosedBox, etc.) to use the new interface, but I still have the interfaces (Box, etc.) with <T extends RealLocalizable & RealPositionable>. Do we want these interfaces to have just <T> or should it be something like <T extends RealLocalizable>? It seems odd to have acenter() that isn't at least RealLocalizable, but there could be use cases I'm not thinking of.

Additionally, do we want the additional interfaces I suggested? So Box<T> and MutableBox which would have any setters. If so should it be named, MutableBox, WritableBox, or something else? And should my concrete implementations then contain mutable/writable i.e. ClosedMutableBox?

Thoughts @tpietzsch?

[awalter17]

@tpietzsch I made the remaining changes. I left RealLocalizableRealPositionable with the same name, since I couldn't think of a better one. And then for all the mutable/writable classes/interfaces I used "Writable".

This writable structure is a little odd for WritableRealPointCollection and WritablePointMask. WritableRealPointCollection still has a generic to define what is in the collection, but since its intended to be mutable I have the objects in the collection as RealLocalizable & RealPositionable. I'm not sure if this is necessary. The writable layer is nice though, since technically KDTreeRealPointCollection has never been writable so now its just a RealPointCollection while the others are WritableRealPointCollections.

For WritablePointMask, PointMask never had generics. So for it to be writable, I just have the interface extend RealPositionable directly.

If you'd prefer not to have this whole "writable" layer, we can just get rid of all commits after 382365f.

Please feel free to let me know if you'd like any changes, or if you have any questions.

[awalter17]

@tpietzsch Have you had the opportunity to review these changes? If not, do you think you’ll be able to review them in the next couple of weeks?

Please feel free to let me know if there’s anything I can do to help.

[tpietzsch]

@awalter17 I'll do it tomorrow. Promised!

[tpietzsch]

@awalter17 I pushed some changes to branch shape-roi-fixes.

Please remove generic parameters from the remaining non-writable interfaces. I did it for Box here: https://github.com/imglib/imglib2-roi/commit/2773f4d205f2f0ce0d207513341503c0360e0e2a

Alternatives to the name Writable would be Mutable or Modifiable. I'm fine with writable, but maybe somebody else has preferences? (@axtimwalde @ctrueden @maarzt @hanslovsky @StephanPreibisch)

[awalter17]

Thanks @tpietzsch! I added your commits from shape-roi-fixes to shape-rois and removed the generic parameters on the remaining non-writable interfaces except RealPointCollection.

Switching RealPointCollection to use just RealLocalizable felt a bit too constraining. One change I did make to WritableRealPointCollection was to just make the points in the collection have to be RealLocalizable not RealLocalizable & RealPositionable. Looking back, it just seemed weird to demand they be RealPositionable.

As for the naming (writable, etc.), I have no strong feelings. I am happy to change it to something else, if need be!

[ctrueden]

Writable is OK by me also. The precedent is limited and mixed already:

Writable

fiji/Video_Editing/src/main/java/video2/WritableVirtualStack.java
imglib/imglib2-algorithm/src/main/java/net/imglib2/algorithm/gauss/WritableLineIterator.java
scifio/scifio-jai-imageio/src/main/java/io/scif/media/imageioimpl/plugins/gif/GIFWritableImageMetadata.java
scifio/scifio-jai-imageio/src/main/java/io/scif/media/imageioimpl/plugins/gif/GIFWritableStreamMetadata.java

Mutable

scijava/scijava-common/src/main/java/org/scijava/module/DefaultMutableModuleInfo.java
scijava/scijava-common/src/main/java/org/scijava/module/DefaultMutableModule.java
scijava/scijava-common/src/main/java/org/scijava/module/MutableModuleItem.java
scijava/scijava-common/src/main/java/org/scijava/module/DefaultMutableModuleItem.java
scijava/scijava-common/src/main/java/org/scijava/module/MutableModule.java
scijava/scijava-common/src/main/java/org/scijava/module/MutableModuleInfo.java
imagej/imagej-ops/src/main/java/net/imagej/ops/special/OutputMutable.java

[hanslovsky]

I do not have a very strong opinion on this as I did not have time to go through the PR in detail (I read, and I think understood, most of the discussion, though), but I have a suggestion for a different identifier for mutable/writable shapes: If I understand correctly, we do have an immutable implementation (e.g. Box) and one that we can move (by setting the center, e.g. WritableBox) for each ROI shape. If that is true, I think that Positionable as a prefix would be more expressive than Writable or Mutable, e.g. PositionableBox.

[awalter17]

If I understand correctly, we do have an immutable implementation (e.g. Box) and one that we can move (by setting the center, e.g. WritableBox) for each ROI shape. If that is true, I think that Positionable as a prefix would be more expressive than Writable or Mutable, e.g. PositionableBox.

@hanslovsky It is true that WritableBox is positionable by setting the center. However, it also allows the user to mutate the side lengths. So, I think Positionable would be too specific of a prefix.

[ctrueden]

I think Positionable would be too specific of a prefix.

I second that—the PositionableBox would not actually implement Positionable so I think that name would be misleading. (ExtendedRandomAccessibleInterval I'm looking at you! 👁)

[hanslovsky]

Thank you for the clarification @awalter17 and @ctrueden I am fine with picking any of the suggested prefixes, then.

[imagejan]

I'd slightly prefer Mutable as it is in line with MutableModule etc. in SciJava, and it's shorter by one letter :-)

Otherwise, is this PR now ready to be merged?

[tpietzsch]

yep, it's finally merged... Thanks @awalter17 and everyone who contributed/reviewed

[tpietzsch]

... and released (imglib2-roi 0.5.0)