Implementation plan for Imglib2-rois 2D

Nice! I wish I had the discipline to keep such a priority list!

I actually wrote it down today in response to your question. Now I hope I will be disciplined enough to keep it up-to-date. Shouldn’t be too hard, since most of those projects are substantial.

Hello,

Thanks for your feedback @haesleinhuepf and @tpietzsch!

Below are some additional clarifications/questions:

True a RAI has boundaries to locate it in space. When I was creating this list I wasn’t taking into consideration what was already implemented. So the intention of this was just that we should not implement new ROIs without having some method of locating them in space. Since we’re basing the various regions off of RAIs this isn’t an issue, but kind of still a requirement for ROIs in general. (Maybe?)

True, but there’s also a possible issue with Boundary.

List<RealLocalizable> vertices = new ArrayList<RealLocalizable>();
vertices.add(new RealPoint(1d, 1d));
vertices.add(new RealPoint(5d, 1d));
vertices.add(new RealPoint(5d, 5d));
vertices.add(new RealPoint(1d, 5d));

Polygon shape = new Polygon(vertices);
IterableRandomAccessibleRegion<BoolType> rs = shape.rasterize();
Boundary<BoolType> b = new Boundary<BoolType>(rs);

So the size of rs is 16, which makes sense because it is a 4x4 square but the size of b is 12 when it should also be 16. This occurs because when you define a rectangle using Polygon points along the top and right boundary are not included in the region. And it needs to be that way, otherwise the size of rs would be off.

Still this is kind of confusing (at least to me) because if I get a RandomAccess from b and then set it to (5, 5) it evaluates to false. My intuition would be that points used to define my shape should be included in the boundary.

Though I suppose if you really wanted the points along this boundary you could use RasterizedPolygonalChain. And if you wanted points along the chain and inside the region or only points in the region that aren’t part of the chain, etc., you could just use one of the composite methods (e.g. or, subtract, etc.). Thoughts?

If we decide to leave this functionality as is, then we should ensure all region types exhibit the same behavior for consistency. :wink:

True, but then why have classes like RasterizedPolygon if there’s a Regions.rasterize()? Presumably Regions.rasterize() would do something similar to the constructor which takes a Polygon for RasterizedPolygon.

My intention with that point was more to continue the structure of having a continuous space implementation (i.e. Polygon) and a discrete space implementation (i.e. RasterizedPolygon). It seems redundant to have both, though maybe that’s not necessarily a bad thing.

Please let me know your thoughts on this, or if any of my comments/questions need further clarification.

Thanks,

Alison

Hello again!

I have a couple more ideas/questions/whatnots pertaining to ROIs, and I’d greatly appreciate your input on them.

Transformable.

  • Is there a difference between something being Positionable and something undergoing a translation?

I thought Positionable only applied to moving single points/accessors within a given space; whereas, translation would be shifting the space itself (like a region or an interval). For example, if I wanted to move one vertex of a Polygon then that vertex is Positionable but if I wanted to move the entire Polygon then that’s a translation. Is this distinction correct?

  • Would it make sense to create methods like Regions.rotate( … )?

This method would function similarly to Regions.positionable( … ). In other words, it would check if the given RealRandomAccessibleRealInterval is rotate-able and if so use its rotate method, otherwise use RealViews to do the transformation. Something similar could be done for shear, scale, etc. Provided there was a need for them.

Combine-able.
It seems as though there’s two possible ways to do this:

  1. Use binary operators to combine multiple regions (i.e. CompositeRegionOfInterest and @haesleinhuepf’s binary operators for ROIs)
  2. Use a list of closed curves and the even/odd winding rule (i.e. GeneralPathRegionOfInterest)

I feel like option two is useful when the user knows their desired shape. For example, creating the green region in the image below. Creating this shape is easy to do using option two, but is more cumbersome to create with option one because you’d have to create multiple ROIs and combine them a few times.

On the other hand, option one is useful if someone has two regions already defined, and would now like to define a third region which is the intersection of the two.

I can’t decide which one of these options is better, so please let me know your thoughts on these two options.

Rasterize.

  • Should there be a way of retrieving the original real space ROI from the rasterized version?

So if I create a RasterizedPolygon, should it store a reference to the Polygon it was created from? RandomAccessibleOnRealRandomAccessible does store a reference to the target RealRandomAccessible but there is no way to access it.

You could use Views.interpolate( … ) to try and reconstruct the original polygon, but it just seems like it would be easier to have the rasterized ROI keep track. Though if you transform the rasterized ROI, then you probably should use View.interpolate( … ) to retrieve the equivalent real space ROI. Thoughts?

Both the rasterize and combine-able points (specifically option 1), kind of lend themselves to an additional requirement:

Mechanism for persisting ROIs.
So if you combine, rasterize, etc. a ROI you should be able to retrieve the original ROI.

@tpietzsch, @dietzc, @axtimwalde, @haesleinhuepf please let me know your thoughts on the above. Also please feel free to let me know if you have any additional thoughts/comments/questions on ROIs, all input is welcome. :slight_smile:

And thanks again for all the feedback everyone! It has all been extremely helpful!

Regards,

Alison

1 Like

Hi @awalter17,

nice hearing from you again :slight_smile:

Transformable

I would not differentiate that, to keep it simple: A vertex (RealPoint?) is a Postionable and a Polygon is so as well. I’m not sure about the actual implementation, but I would say, if you translate a polygon, actually all vertices in the polygon are translated. If you translate a vertex, only its position changes.

From a theoretical point of view yes. However, I don’t remeber a project, where we needed that. So, I would put a low priority on features like rotating ROIs.

Combine-able

I would say, this is the standard use case.
Furthermore, the green region you showed can be created using a Polygon, right?

Maybe, @tpietzsch can tell us, why GeneralPathRegionOfInterest is deprecated?

Rasterize

I like this idea, but the next step would be, that every operation keeps references to their operands. At some point, this becomes hard to implement, even harder to maintain and the garbage collector may become unhappy. Again: Keep it simple. We already have algorithms (in imagej-ops) for getting polygons/meshes from binary rasterized images. It would be nice, if rasterizing and verctorizing are reversable. However, I would be happy they are almost reversable. I would put a higher priority on simplicity and maintainability of the API.

Mechanism for persisting ROIs

I kinda disagree here. If a developer wants to retrieve the original ROIs, he can keep references. If references are always kept, the heap will fill and you cannot do anything against it.
Just imagine a user using the brush tool on an image adding and removing regions for half an hour. These are a lot of binary union and subtraction operations. If we keep every single intermediate ROI, the program will become slower and slower with time.

Good luck with the project. :slight_smile: If you need external testers, or code reviewers with a far-away perspective, just let us know :wink:

Cheers,
Robert

3 Likes

Did you plan yet a mechanism for ROIs I/O ? A support for opening IJ1 ROIs would be nice also.

If you already know in which package it should live I can try to have a look depending on the status of imglib2-rois.

1 Like

Agreed, but there is so much design work to be done first to get ROIs conceptually “right” as discussed above, that I strongly suggest postponing I/O considerations. I have been involved in many ROI discussions over the past 10 years, and I/O considerations tend to pollute/complicate the design when considered too early.

6 Likes

Hello @tpietzsch, @dietzc, @axtimwalde, and @haesleinhuepf!

How should we handle rasterizing ROIs which don’t exist in discrete space?

For example, a 2D rectangle with corners { (0.7, 0.1), (0.79, 0.1), (0.79, 0.3), (0.7, 0.3) } or a 2D rectangle in 3D space with corners { (1, 1, 3.2), (1, 7, 3.2), (3, 7, 3.2), (3, 1, 3.2) }. Neither of those two ROIs include discrete space points (in their given spaces), so if they were rasterized using Views the returned RandomAccessible< BoolType > would never evaluate to true.

With imglib2-rois, I was just thinking of including this issue in the javadoc and having it be on the user to provide a ROI which exists in discrete space when rasterizing. Which I think would be fine, at least for now.

I was also talking with @ctrueden, about this issue and he mentioned that down the line we might want to have a way of still displaying these ROIs. For this issue, the thought was we could first transform the RealRandomAccessibleRealInterval< BoolType > to a RealRandomAccessibleRealInterval< T > where the T space value of true and false would be given to the method. Then a “fade” would be implemented, where points a certain distance away from the ROI boundary are included in this ROI (and are assigned a certain T value), via an out of bound strategy which would handle the interpolation/extrapolation. This would then allow the ROI to be displayed in discrete space.

Hopefully that makes sense, but if not please let me know and I can try to explain it in a different way. Also please let me know your thoughts on this issue as a whole, and on the display rasterization idea.

Thank you very much,

Alison

@awalter17

Then a “fade” would be implemented, where points a certain distance away from the ROI boundary are included in this ROI

It sounds like you’re describing a level set , which I highly recommend for rasterizing continuous ROIs, but I’m biased :). If we go in that direction, I’d be very happy to contribute / help.

The tricky cases you described can’t really be adequately represented by “classical” level sets (since the grid samples the ROI below the Nyquist rate) - and in that case, I would argue that its correct for the RandomAccessibleInterval< BoolType > to always return false. But using a level set, it will still be possible to “see that something’s there.”

John

Edit: We probably want a RealRandomAccessibleRealInterval< BoolType > to sometimes return true, but a RandomAccessibleInterval< BoolType > to always return false

3 Likes

Hello @tpietzsch, @dietzc, @axtimwalde, @ctrueden!

I’ve finished making several changes to the imglib2-rois structure on the branch shape-rois. I most likely won’t be making any additional changes to this branch until the hackathon (Feb. 21). As such, I figured now would be a good opportunity to have people look at the branch and hopefully provide me with some feedback.

Below is a list of the major changes this branch makes, as well as information on why I made some of these changes.

Changes this branch makes:

  • Modifies RealBinary(Unary)Operators:
    • Not depend on Contains interface (commit)
    • Work with any RealRandomAccessibleRealIntervals< B > (where B extends BooleanType< B >) (commit)
    • Implement Pair for RealBinaryOperator classes
  • Adds RealBinary(Unary)Operator methods to Regions (commit)
  • Removes rotation functionality from HyperRectangle/Ellipsoid, in favor of using imglib2-realtransform methods (commit 1, commit 2)
  • Adds GeomRegions (commit 1, commit 2, commit 3, commit 4)
  • Removes RasterizedPolygon, and adds general raster class (commit 1, commit 2, commit 3, commit 4, commit 5)
  • Adds method of putting a RealInterval on an AffineRealRandomAccessible (commit 1, commit 2, commit 3)
  • Modify contains(...) in HyperRectangle to include same boundary points as Polygon2D (I’m currently reading the papers mentioned in this post so we’ll see if this was actually a reasonable change) (commit 1, commit 2)
  • Creates Line region of interest (commit 1, commit 2)
  • Breaks apart and removes ROIUtils, most methods moved to Regions except getLabelingMapping which was moved to a new class Labelings (commit 1, commit 2)

Decisions/Rationale:

  • Rotation
    • Using real-transform allows for additional transformations to the shape to just be concatenated to the matrix, as opposed to having an affine transform and then having additional rotation/translations in deeper layers
    • Drawback -> can’t keep track of interval bounds for each transformation, so instead there’s Regions.interval(…) to put interval bounds on the transformed ROI but these bounds will not update as you transform the ROI
  • Combine
    • This version of combining ROIs keeps references to each input operand, the alternate to this would be something like GeneralPath which stores curves and uses even-odd winding
    • Would make sense to eventually have both methods
    • GeneralPath method (would need to be implemented without Java-AWT)
      • Memory efficient, can’t combine existing ROIs without converting them into curves (or other general structure)
    • RealBinary(Unary)Operators
      • Not efficient if you create combined regions using many intermediate shapes, easily extends to n-dimensions, can combine any existing ROIs in several ways
  • Rasterize
    • RasterizedPolygon, RasterizedHyperRectangle, RasterizedHyperEllipsoid would have all been the same
    • RasterizedRegion is intended for ROIs with area/volume
    • Consider making a separate class for rasterizing lines and curves
  • Line/Point
    • Current issue with RealPoint not working with the rest of the API (i.e. can’t be rasterized or combined with other ROIs, because it is not a RealRandomAccessibleRealInterval)
    • Rasterizing a line using Regions.raster would (in most cases) return a RAI containing only a few points -> consider different raster method (maybe using Bresenham)

See you at the hackathon!
Alison

3 Likes

Hello all,

I just wanted to share some of the major decisions regarding ROIs which were made at the hackathon:

  • Separate “shapes” and RealRandomAccessibles
  • A RealMask can be the result of unary/binary operations on RealMasks (ex: And)
  • RealMasks can be affine transformed (AffineRealMask)
  • Options for whether or not a RealMask should or should not contain all points on the boundary (ex: Box)
  • Should have implementations for discrete space equivalents of RealMasks when applicable (ex: rectangles)
  • Should create Rasterizable interface for RealMasks which know how to efficiently rasterize themselves, also have additional options for raster algorithms

@tpietzsch, @dietzc, @axtimwalde, @ctrueden please feel free to add anything I missed, or correct me if needed.

Regards,

Alison

6 Likes

Just a quick follow-up on the ROIs project: the other day, @awalter17 and I generalized RealMask to be simply Mask<L extends RealLocalizable>. So now you can have Mask<RealLocalizable> for continuous/real masks, and Mask<Localizable> for discrete/integer ones. This paves the way for discrete ROIs going forward, even if we don’t implement them all now. It also allowed us to generalize all the mask tree nodes (And, Or, Xor, etc.) to not care about whether the mask is real or integer, so it is now equally possible to generate unary/binary operation trees on either kind of mask. Work progresses on the shape-rois branch—be warned that that branch is undergoing heavy rebasing still, though.

4 Likes

@ctrueden @awalter17:
Do you have any design idea (or even example implementation) on how the ROIs will integrate with the ImgLabeling and Region w.r.t. sampling information from (possibly unrelated) Imgs?

2 Likes

Hello @stelfrich!

I haven’t done a lot with respect to sampling, but I do have adapters which can wrap Masks as RandomAccessibles (ex:
DefaultMaskAsRandomAccessible).

I’ve been mostly focused on creating additional real space ROIs. So in order to use them to sample from an Img you’d have to wrap them was a RealRandomAccessibleRealInterval using the adapter, then Views.raster(...), then Views.interval(...), then Regions.iterable(...), and then (finally) Regions.sample(...). The framework supports creating discrete space ROIs (Mask< Localizable >) which would be easier to use for sampling.

Cheers,

Alison

4 Likes

@tpietzsch Thank you very much for all your work on this at the hackathon! :smiley_cat:

I was looking over your changes, and I noticed that in your scheme it is not possible to retrieve the operands used to create a MaskPredicate which resulted from an or, and, etc. nor is it possible to tell which operation was performed. For example, if someone unions a rectangle and a circle there’s no way to retrieve the original circle and rectangle from the resulting MaskPredicate or figure out that the new MaskPredicate resulted from a union.

I need this functionality for my conversions in imagej-omero, though I did forget to add unit tests for this functionality on my imglib2-roi shape-rois branch :cry:. In imagej-omero if I’m given a RealMaskRealInterval to upload to OMERO, I need to check if this RealMaskRealInterval resulted from an operation between multiple MaskPredicates and if so convert the original MaskPredicates to their OMERO equivalent and then recombine them in the same way as before (but using OMERO data structures).

For example, if someone tries to upload a RealMaskRealInterval which is actually four Boxes union-ed together, then I need to be able to “unwrap” the RealMaskRealInterval into the four original Boxes and I need to know that these Boxes were union-ed.

Do you have any thoughts on how to achieve this? My thoughts are:

  1. Add four new classes (RealMaskOperationResult, RealMaskRealIntervalOperationResult, etc.), and these would have methods for retrieving operands and operation types

– OR –

  1. Add operands() and operationType() methods to MaskPredicate. Then the question is what do these methods return for things like Box, Sphere, etc
    • operands() could return null, Collections.emptyList(), Collections.singletonList(this), or …
    • operationType() could return null, an Enum, or …

Please let me know your thoughts on this. And once again thank you very much for all the work you did at the hackathon, I think the changes are a big improvement!

Cheers,

Alison

2 Likes

@awalter17 This is already there (your option 1.)

Have a look at CompositeMaskPredicate, UnaryCompositeMaskPredicate, and BinaryCompositeMaskPredicate.

I added a demo: AnalyzeCompositeDemo.java

For

RealMaskRealInterval composite = s1.and(s2.minus(s3)).and(s3).or(s1.minus(s3.negate()));

it prints

leaf  (net.imglib2.troi.geom.real.ClosedSphere@7cd84586)
OR  (net.imglib2.troi.composite.DefaultBinaryCompositeRealMaskRealInterval@30dae81)
 +--AND  (net.imglib2.troi.composite.DefaultBinaryCompositeRealMaskRealInterval@1b2c6ec2)
 |   +--AND  (net.imglib2.troi.composite.DefaultBinaryCompositeRealMaskRealInterval@4edde6e5)
 |   |   +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@7cd84586)
 |   |   +--MINUS  (net.imglib2.troi.composite.DefaultBinaryCompositeRealMaskRealInterval@70177ecd)
 |   |       +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@1e80bfe8)
 |   |       +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@66a29884)
 |   +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@66a29884)
 +--MINUS  (net.imglib2.troi.composite.DefaultBinaryCompositeRealMaskRealInterval@4769b07b)
     +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@7cd84586)
     +--NEGATE  (net.imglib2.troi.composite.DefaultUnaryCompositeRealMask@cc34f4d)
         +--leaf  (net.imglib2.troi.geom.real.ClosedSphere@66a29884)

The reason you didn’t see this is probably because CompositeMaskPredicate is never returned as a type. I was almost going to do that before https://github.com/imglib/imglib2-roi/commit/029ff8e79d40e1d55bf713433342cb349a58f0fb
MaskInterval.and could return BinaryCompositeMaskInterval, etc. However, for the leafs (and therefore for the operands of a composite) I think we should leave them as general Predicate<? super T>. Therefore there needs to be instanceof checks as you descend into nested structure anyway. So…

3 Likes

Dear @awalter17,

I am replying here to your request for review since I haven’t really looked at the implementation in depth.

Also, as you might have guessed from my previous comment, I am more concerned about how the new ROIs can be used in practice. Did I get that right, that your motivation was the saving of ROIs to OMERO (and loading from it) within the imagej-omero project? If so, that will be super useful.

From your previous explanation, I have gathered that the conversion to/from RAI<BooleanType> is pretty straightforward (thanks for the demos btw, that was really helpful!), which is awesome. I am, however, wondering how the new Masks integrate with the “old” Labelings. Do you/@tpietzsch have an idea how that integration will look like in future?

Best,
Stefan

1 Like

Hello @stelfrich!

That is correct! I am working on that on the rois branch in imagej-omero.

Unfortunately, I haven’t given Labelings much thought. So, I can’t give you an answer at this moment.

Cheers,

Alison

Hello all,

My work in imglib2-roi has been merged and released (see PR for details)! :smile_cat:

Thank you very much to everyone who helped with this (@tpietzsch, @ctrueden, @axtimwalde, @dietzc, @haesleinhuepf, @imagejan)!

I’ve also brought my roi-demo branch in the imglib2-roi repo up to date. So, feel free to take a look at that to get a feel for the new ROI API!

Cheers,
Alison

13 Likes