Implementation plan for Imglib2-rois 2D

omero
imagej
imglib
roi

#21

Hi Alison,

very nice to see progress in this project. Some of us really need that stuff and are curious how it will look like. :slight_smile:

I absolutely agree. It is very convenient to write rai = Regions.union(rai1, rai2). I would furthermore support if there were overloaded versions for discrete binary RAIs. You may again copy some stuff, I recently programmed: https://github.com/haesleinhuepf/imgtools_binary_ops/blob/master/src/main/java/de/mpicbg/scf/imgtools/geometry/filter/operators/BinaryOperatorUtilities.java

Now I will just think loudly in writing: From my point of view, any region could be an annotation. But not any annotation (such as points and texts) is a region. This sounds like inheritance. But when I look back to the inheritance tree of ROIs in ImageJ1, we really need to be careful here. It would be very nice to do it right this time :wink:

Maybe I understood you wrong, but I kind of disagree here. Lines and polylines are no regions, because they are infinitely thin and thus, surround/describe/represent no area. But regions must do. Maybe, it would make sense to introduce a Polygon as a closed collection of lines and a PolygonRegion representing the surrounded area.

From my point of view, a point collection is no region for the same reason. But: A PixelCollection could be, as it is just a representation of a discrete binary image :wink: A RasterizedPolygonalChain could be a region as well. I could also imagine a class representing list of cylinders along a polyline being a region. But that’s maybe something for Version 2.0 . Let’s concentrate on the basic stuff…

Is there already some kind of prototype code for the RasterizedPolygonalChain available online? Would be interesting to see how you plan to implement this.

Thanks for taking care for the ROI stuff. Your efforts are really appreciated :slight_smile:

Cheers,
Robert


#22

RasterizedPolygon?

PointCollection base on Localizables and can therefore be IterableRegions. https://github.com/imglib/imglib2-roi/blob/master/src/main/java/net/imglib2/roi/geometric/RasterizedPolygonalChain.java is a IterableRegion as well (as it is a PointCollection).

I have no strong opinion on infinite small Lines, Points etc and actually there are enough people out there with an opinion and a way better understanding of the topic than me (@ctrueden, @axtimwalde, @tpietzsch). However, I think we really should get the naming straight for this discussion and I suggest that we stick to what is already implemented in Imglib2-ROI. IterableRegion, PointCollection, Polygon, RasterizedPolygon, PolygonalChain, RasterizedPolygonalChain. etc. See https://github.com/imglib/imglib2-roi/tree/master/src/main/java/net/imglib2/roi/geometric. I’m not saying that this is how we should do it, just giving some basis for discussion (e.g. I don’t know anything about Annotations?! :-)).

And: Thank you to everyone contributing to this topic. As mentioned above, it’s not easy, there are many ways to do it, we just need to agree on the best one ;-).


#23

I think the dicussion came from a structure describing pixels along a polygon. If I’m right, this is not available in imglib-roi, as the Polygon there already represents the area inside the polygon; its contains function suggests that https://github.com/imglib/imglib2-roi/blob/master/src/main/java/net/imglib2/roi/geometric/Polygon.java#L73-L100 . So probably the naming is the issue why I’m understanding something wrong here?

I remember another disucssion where I was taught that pixels have no area. From this point of view points and pixels are the same. So, I do not entirely understand why a point can be a region, but I withdraw my comment from my last post - to keep things simple. I can accept that points may be regions. I guess it makes things more complicated if we differentiate at that point.


#24

https://github.com/imglib/imglib2-roi/blob/master/src/main/java/net/imglib2/roi/geometric
/RasterizedPolygonalChain.java ?

Maybe the problem here is RealPoint vs. Point? I mean, we use PointCollection as a PixelCollection as Point is Localizable in our case, i.e. only has integer coordinates.


#25

No, I was looking for the continous Polygon… :wink:


#26

Hello again!

Both PointCollection and RasterizedPolygonalChain already exist, my apologies for not linking to these classes in the first place! And a RasterizedPolygonalChain is a region which contains only the points along the boundary of a polygon, not the points inside.

That helps clear things up! I wasn’t thinking about the points as pixels, but with that in mind it does kind of make sense to have this be a region.

So I guess the question now is can lines/polylines be regions if the points used to define them are Localizables? In other words would rasterized lines and polylines be regions?

If that were the case then the groupings would look something like:

Is a Region: Polygon, RasterizedPolygon, HyperRectangle, RasterizedHyperRectangle, HyperEllipsoid, RasterizedHyperEllipsoid, PointCollection, RasterizedPolygonalChain, RasterizedLine, RasterizedPolyline, Point

Not a Region: PolygonalChain, Line, Polyline, RealPoint, floating text

But this distinction seems a bit strange … Or possibly confusing?

The idea of annotations and regions is also referenced on this wiki page: http://imagej.net/ROIs

As such I thought it would be useful to have an Annotations class, so people could use it (like GeomRegions) to get instances of various annotation objects. Additionally, I thought it would help differentiate regions from annotations.

I guess this all boils down to where’s the cutoff between region and annotation? And do we want to make this distinction at all?

Please let me know your thoughts on these issues, or any ideas/concerns/questions you have related to this topic. And thank you everyone for your responses. Your feedback and insights are greatly appreciated. :slight_smile:

Regards,

Alison


#27

Hello!

So after discussing with @ctrueden, it became apparent that maybe we’re getting too bogged down with all the details at this point. And perhaps it would be beneficial to take a step back. With this goal in mind, we compiled a list of requirements for ROIs. Please review the list of requirements, and feel free to add, remove, or edit any requirements (@tpietzsch, @dietzc, @axtimwalde, @haesleinhuepf).

Additionally please note, this list does not reflect the work already done with ROIs, as a number of these requirements are already satisfied by the current ROI implementation. But rather this list is intended to be a general list of the requirements (functionalities) a ROI API should have in order to fulfill various use cases (i.e. running an algorithm on a certain subset of pixels in an image, etc.).

Requirements:

  • UI agnostic. (for rendering)
  • Transformable. via RealViews
    • Re-sizeable
    • Moveable
    • Rotatable
  • Location knowledge. Knowledge of position in space relative to axes
  • Shape characteristics. Knowledge of shape
    • Different ROI cases e.g. an ellipse knows its center and its axes
    • For transformed ROIs this knowledge is buried under the surface
  • Display parameters. Related relevant display information (color, fill, etc.) (optional / attached)
    • RichImage will address this
  • Independent. Able to stand alone or be related to an image
  • Iterate members. Can define a region within an image, such that pixels within that region can be sampled from the image (and only those pixels within in region can be sampled)
  • Contains. Fast inclusion/exclusion test for position
    • Consider whether boundary pixels are a separate case, besides true/false
  • Iterate boundary. Loop over all samples on boundary for discrete ROIs
  • Combine-able. Ability to combine ROIs into composite region
    • Need superclass for ROI types
  • Rasterize. Defined in real space and discrete space
  • Fuzzy ROIs. Using [0, 1] for probability of each point instead of binary true/false
  • Spatial relations. Linked to image as spatial meta-data (i.e. transformations affect both image and related ROI)
    • Should get for free with RichImage
  • Compatibility. Compatible with current labeling methods

Additional Possible Requirements:

  • Mutability

Hopefully once we have a list of requirements, it will provide a clear unified vision of what everyone wants from ROIs which in turn will help inform us about the structure of ROIs.

As always, please let me know your thoughts on this and if you have any questions.

Thanks,

Alison


#28

Hi Alison,

I love the list and would hardly change anything. However, there is one thing, which may be part of the “display parameters”: It would be nice if an ROI could have name and/or a list of tags. This is often practical, but I’m not 100%ly sure if this should be part of an ROI class or RichImage or whatever.

Thanks again for your efforts! :slight_smile:

Cheers,
Robert


#29

Hi Alison,

yes, I think taking a step back is a good idea. Thanks for your work and patience! Your list is a great start. Here are some thoughts and comments on individual points:

This applies only to continuous ROIs, obviously.
There should be something like Views.interpolate() to go from a discrete region to a continuous one. Actually, because every discrete ROI should be RandomAccessible<B extends BooleanType<B>> one can simply use Views.interpolate() to do this.

I’m not sure, what that means. A RandomAccessibleInterval<B extends BooleanType<B>> has its Interval boundaries to somehow locate it in space. If you want to move it around (this is all discrete), my idea was to make PositionableIterableRegion. The plan was to have Regions.positionable(Regions.iterable(RAI)) to make every arbitrary RAI<BooleanType> into such a PositionableIterableRegion. In principle of course one could always use Views to move stuff around, but the idea was that some regions might already be Positionable (for example LabelRegion) and can be moved around much more efficiently than calling Views methods for every re-positioning. At some point it would be great if the neighborhoods framework (Shape etc) and ROIs can be expressed in a unified manner. For this, going through Views would be prohibitive. That’s why we need something like Regions.positionable.

I have a strong preference for “attached”. I’m not sure whether display information should even be in imglib2-roi.

This is already implemented as Regions.sample.

I don’t think this is necessary. With (R)RAI<BooleanType> you can ask “contains” questions using RandomAccess and multiple contains queries by moving the RA around can be much more efficient than asking contains(Localizable) multiple times.

This is also a problem I have with @haesleinhuepf’s PR. The boolean operations there are build on contains and a new interface RealRandomAccessibleRealIntervalContains. I’m opposed to building on this (interface), because there is no reason that boolean operations shouldn’t work on two Img<BitType> for example.

This is already implemented in Boundary although not yet conveniently accessible through Regions.

We don’t need additional superclasses. [Real]RandomAccessible[Interval]<B extends BooleanType<B>> is sufficient. Actually, this leads to one point I would like to add to the list:

  • Compatibility with existing imglib2. It should be trivial to use for example a Img<BitType> as a ROI, e.g., combine it with a rasterized ellipsoid using a boolean operator.

Having new superclasses/interfaces would defeat this goal.

In principle Views.rasterize() should be sufficient.
We might still add Regions.rasterize() to allow shortcuts for regions that know how to rasterize more efficiently than by querying real coordinates. But in any case the results should be equivalent to Views.rasterize().

Unless there is a concrete need for it now, I would postpone this. It complicates everything considerably. In my opinion it is more realistic to get something working with boolean regions first.

Btw, @ctrueden is there a plan/timeline for RichImage? Please let me know when you need the Meta-Views stuff! (I didn’t move it to the imglib2 yet, it’s still in that janelia-hackathon-2016 repository, but it’s ready when you need it…)

best regards,
Tobias


#30

It is currently third down my priority list, after 1) the ImageJ2 paper and 2) improved Ops type matching. I fear it will not be done before the December hackathon, and I will have to work on it during that hackathon—unless other more urgent projects materialize.

Don’t worry—I was planning to just cherry pick it out of there myself. Thank you very much for all your efforts on it.


#31

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


#32

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.


ImageJ2 scripting questions
#33

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


#34

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


#35

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


#36

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.


#37

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.


#38

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


#39

@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


#40

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