Convert a set of points into an ROI

[Ghislain Bonamy]

I am trying to gage wether it is feasible to convert a set of points into an ROI. The set of points is not a polygon (ie, the order is not provided in a way that each point can be connected to the next one). Instead, data provided contains the coordinates for each points of the shape contours, sorted by increasing row (ie. not following the contour).

I have seen that the ImageJ ROI model supports several models other than Polygon: Poly-line, freehand, Traced, segmentedline, etc.

Is it actually possible to convert my set of points into an ROI? If so what type do I need to use. Are there any explenations as to how these different models differ? Any exemple some code would much appreciated.

If not, anyone has an idea where I can find a start point for contour-tracing of my shape in Java?

Best,

Ghislain

[ctrueden]

Hi Ghislain,

If your shape is convex, then all you need is to find the convex hull of
your collection of points. There are general algorithms for doing this, but
you may be able to take a shortcut depending on the structure of your data.
Do you have interior points, or do all your points lie on the hull? The
purpose of a ROI is generally to differentiate between two classes: "inside"
and "outside." Is that your sole need here?

-Curtis

On Mon, May 11, 2009 at 1:10 PM, Ghislain Bonamy <[hidden email]> wrote:

> I am trying to gage wether it is feasible to convert a set of points into
> an
> ROI. The set of points is not a polygon (ie, the order is not provided in a
> way that each point can be connected to the next one). Instead, data
> provided contains the coordinates for each points of the shape contours,
> sorted by increasing row (ie. not following the contour).
>
> I have seen that the ImageJ ROI model supports several models other than
> Polygon: Poly-line, freehand, Traced, segmentedline, etc.
>
> Is it actually possible to convert my set of points into an ROI? If so what
> type do I need to use. Are there any explenations as to how these different
> models differ? Any exemple some code would much appreciated.
>
> If not, anyone has an idea where I can find a start point for
> contour-tracing of my shape in Java?
>
> Best,
>
> Ghislain
> --
> View this message in context:
> http://n2.nabble.com/Convert-a-set-of-points-into-an-ROI-tp2864581p2864581.html
> Sent from the ImageJ mailing list archive at Nabble.com.
>

[Ghislain Bonamy]

Curtis,

Thanks for the reply. Unfortunatelly, most of the forms are not convex, but all of the points lie on the Hull. I have attached a zip file, ROI.zip, that contains: a picture showing the different ROI (different colors=different objects), and the coordinates for thes objects, which provide the outline of these objects. The x;y vaues are separted by ';' and the different points are separated by ','. This is not the final schema for the ROI format, but it should give you an idea about what I have cooking.

So the problem at hand is to be able to either order the points for each objects in an order that is suitable for the registration of the ROI. Could anyone explain what are the different type of ROI? In particular what is polyline? This might be the best type to use, but I do not know what it represents.

I think that one garante with the ROI outputed, is that for each pixels provided, there are only 2 adjacent points (ie, if you imagin a pixel, it can only be surounded by 8 pixels, since we are in a 2D space). So one strategy, would be to take one point and then look in this 8possibly surounding pixels which one is present. when this is done, keep iterating until the loop is closed (ie, all pixels around are blank or already in the ROI).

The only problem is that perhaps in the future some objects may have holes in them for instance.

My need for ROI, is mainly for display purposes, although perhaps, in the future, it might be used to skip some steps for the image analysis.

Any help would be most appreciated!

Best,

Ghislain

[karo03]

Hi Ghislaine,
I don't know about the problem of the origin being hen or egg, however,
if the hen is the set of isolated cells in an image with Analyze-
 >Analyze Particles "Add to Manager" activated you will get the roi of  
each cell (for any purpose),
if the egg is the set of points you can generate an image with one  
object set of points drawn, apply perhaps a small closing, "make  
binary" and edit->selection->create selection and add to manager to  
have a roi of that point set in the roi manager.

Hope I have not misunderstood you
Regards
Karsten

Am 12.05.2009 um 01:09 schrieb Ghislain Bonamy:

> Curtis,
>
> Thanks for the reply. Unfortunatelly, most of the forms are not  
> convex, but
> all of the points lie on the Hull. I have attached a zip file,
> http://n2.nabble.com/file/n2865999/ROI.zip ROI.zip , that contains: a
> picture showing the different ROI (different colors=different  
> objects), and
> the coordinates for thes objects, which provide the outline of these
> objects. The x;y vaues are separted by ';' and the different points  
> are
> separated by ','. This is not the final schema for the ROI format,  
> but it
> should give you an idea about what I have cooking.
>
> So the problem at hand is to be able to either order the points for  
> each
> objects in an order that is suitable for the registration of the  
> ROI. Could
> anyone explain what are the different type of ROI? In particular  
> what is
> polyline? This might be the best type to use, but I do not know what  
> it
> represents.
>
> I think that one garante with the ROI outputed, is that for each  
> pixels
> provided, there are only 2 adjacent points (ie, if you imagin a  
> pixel, it
> can only be surounded by 8 pixels, since we are in a 2D space). So one
> strategy, would be to take one point and then look in this 8possibly
> surounding pixels which one is present. when this is done, keep  
> iterating
> until the loop is closed (ie, all pixels around are blank or already  
> in the
> ROI).
>
> The only problem is that perhaps in the future some objects may have  
> holes
> in them for instance.
>
> My need for ROI, is mainly for display purposes, although perhaps,  
> in the
> future, it might be used to skip some steps for the image analysis.
>
> Any help would be most appreciated!
>
> Best,
>
> Ghislain
> --
> View this message in context: http://n2.nabble.com/Convert-a-set-of-points-into-an-ROI-tp2864581p2865999.html
> Sent from the ImageJ mailing list archive at Nabble.com.

Karsten
[hidden email]

[ctrueden]

Hi Ghislain,

OK, thanks for the link. If I understand your data correctly, you have an
explicitly enumerated set of boundary pixels for each relevant object.

Regarding your query about polygon selections, yes, I think it is the most
appropriate way for you to represent these sorts of regions. A polygon
selection is an ordered list of connected points, with the last point
connecting back to the first to create a closed structure. You could easily
describe your objects using the polygon ROI data structure.

I also think you are on the right track with your algorithm idea: check the
eight adjacent pixels, and "walk" along those discovered to create the
ordered list of points necessary for the polygon data structure. You will
need to be a little clever, though, to handle cases where there are
structures like:

1000
0110
0010
0001

The 1s in the middle do not comply with your assumption of only two adjacent
coordinates for a particular point. There are various heuristics that would
probably be OK to work around this issue, though. It may be that something
as simple as "pick one arbitrarily and move on" ends up working for you,
depending on how pathological your coordinate sets can become.

My question is: how did you end up with the data organized this way in the
first place? It is really unintuitive to me to ever store data this way.
Presumably you had some feature recognition code that identified these
regions in the first place and classified them into objects... was it just
an edge detection mechanism? Ideally your ROI detection algorithm would
output polygon data rather than points ordered by Y axis, and then your
conversion problem would disappear.

-Curtis

On Mon, May 11, 2009 at 6:09 PM, Ghislain Bonamy <[hidden email]> wrote:

> Curtis,
>
> Thanks for the reply. Unfortunatelly, most of the forms are not convex, but
> all of the points lie on the Hull. I have attached a zip file,
> http://n2.nabble.com/file/n2865999/ROI.zip ROI.zip , that contains: a
> picture showing the different ROI (different colors=different objects), and
> the coordinates for thes objects, which provide the outline of these
> objects. The x;y vaues are separted by ';' and the different points are
> separated by ','. This is not the final schema for the ROI format, but it
> should give you an idea about what I have cooking.
>
> So the problem at hand is to be able to either order the points for each
> objects in an order that is suitable for the registration of the ROI. Could
> anyone explain what are the different type of ROI? In particular what is
> polyline? This might be the best type to use, but I do not know what it
> represents.
>
> I think that one garante with the ROI outputed, is that for each pixels
> provided, there are only 2 adjacent points (ie, if you imagin a pixel, it
> can only be surounded by 8 pixels, since we are in a 2D space). So one
> strategy, would be to take one point and then look in this 8possibly
> surounding pixels which one is present. when this is done, keep iterating
> until the loop is closed (ie, all pixels around are blank or already in the
> ROI).
>
> The only problem is that perhaps in the future some objects may have holes
> in them for instance.
>
> My need for ROI, is mainly for display purposes, although perhaps, in the
> future, it might be used to skip some steps for the image analysis.
>
> Any help would be most appreciated!
>
> Best,
>
> Ghislain
> --
> View this message in context:
> http://n2.nabble.com/Convert-a-set-of-points-into-an-ROI-tp2864581p2865999.html
> Sent from the ImageJ mailing list archive at Nabble.com.
>

[Ghislain Bonamy]

Quick follow up:

Does anyone have an understanding of what the different type of ROI actually correspond to? I think Polygon, line, point are easy to figure out what they are. Some other flavors such as polyline etc. are not as easy to understand.

Karsten,

Thanks for the info. I actually was aware of the possibility of doing something like that, but this is for a high content system where of millions of images are generated. ImageJ may not be fast enough to run this. At this point generating a tool for line tracing of a closed set (like the one I have uploaded), should be fairly easy and hopefully quick. In addition it would allow to avoid distorting the ROI that were used for the data analysis by adding an opening operation.
If anyone has code available to do this great!

Curtis,

Thanks for the long and detailed answer. I was planning to add this line tracing algorithm inside loci.plugins.util.? If this is OK with you. Perhaps you have a suggested Package/Class name? I have already though a bit to the case scenario you proposed. The way I intend to solve this is to check for points which are across and then diagonals. In addition, for the first point, I will force the trace to be clockwise (only check for pixels that are right, top, bottom, right-top diag, right-bottom diag) and force to start at the upper left corner of the shape. Finally, I would erased the points that were already used so that I would not trace backwards.
A more problematic event would be:

010
111
000
However, I am pretty sure that this would never occur. Since it would be represented by:
010
101
000
For the code, I plan to use List<Point> to store the initial coordinate and move them one by one into a Vector<Point> (corresponding to  the Polygone calculated). Note: List.contains(currentPoint) works correctly, even if currentPoint is not the same object as the one entered. Let me know if you think the point structure is not ideal, or anything else is not ideal. Once this is written perhaps someone can see if it is optimized?

For the format of the file, I have elected to output it this way (in a convoluted table of coordinates). If you have some suggestions as to the format, perhaps you could show me what you think would be a better format. Currently, the software (Acapella) outputs a list of X-coordinates Y-Coordinates and a list of objects boundaries (each objects has several pixels). So I have to map each XYCoordinateID to an ObjectID. For compactness, I have elected to put all the coordinates for each objects on a same line (thereby avoiding to repat the ObjectID X times, as well as all the other info I want to fit).Unfortunately, the current version does not output an actual ROI file. So I had to generate my own file. I can change the format any way I want. I also intend to add in this file, the ParentObjectType (ex. Nuclei, cytoplasm, etc.), ParentID and ObjectType. In addition to save space, I would have these files added to a zip archive with a directory structure reflecting: field#, Stack#, Time point#). The other advantage is that I can store all of my objects Features in a file with a similar structure. This being said, I am amendable to adopt an alternate solution if you have some other suggestions. I would also generate for bioformats a fileReader to read these ROI. Perhaps we can take this off-line if necessary.

[Gabriel Landini]

On Tuesday 12 May 2009 23:46:42 Ghislain Bonamy wrote:
> Thanks for the long and detailed answer. I was planning to add this line
> tracing algorithm inside loci.plugins.util.? If this is OK with you.
> Perhaps you have a suggested Package/Class name? I have already though a
> bit to the case scenario you proposed. The way I intend to solve this is to
> check for points which are across and then diagonals. In addition, for the
> first point, I will force the trace to be clockwise (only check for pixels
> that are right, top, bottom, right-top diag, right-bottom diag) and force
> to start at the upper left corner of the shape. Finally, I would erased the
> points that were already used so that I would not trace backwards.

This is not a good idea. You need to scan points depending where your previous
point detected point was, not in any arbitrary order. See suggestion 1 below.

> A more
> problematic event would be:
>
> 010
> 111
> 000

No, you cannot blindly erase points that have been traversed already.
Think of this:

01000
10121
01000

You have to traverse point 2 twice. If you delete the first time, your
algorithm fails to reach the start ever again. Something like this happens in
the yellow particle near 730,561.

> However, I am pretty sure that this would never occur. Since it would be
> represented by:
> 010
> 101
> 000

I doubt that it will never occur.

> For the code, I plan to use List<Point> to store the initial coordinate and
> move them one by one into a Vector<Point> (corresponding to  the Polygone
> calculated). Note: List.contains(currentPoint) works correctly, even if
> currentPoint is not the same object as the one entered. Let me know if you
> think the point structure is not ideal, or anything else is not ideal. Once
> this is written perhaps someone can see if it is optimized?

A few suggestions:
1. Do not reinvent the wheel. What you are trying to recreate is Freeman's
chain encoding algorithm which is already implemented in the particle analyzer
and in the particles4, particles8 and lines8 plugins.

2. Do not make assumptions of what might or not might occur in your images. If
you implement Freeman's algorithm correctly, it should deal with all cases,
and it is likely that what one thinks *might* not happen, will eventually
happen in some other image or when you change the segmentation conditions,
etc.

3. From what you say, your coordinate points are supposed to be 8-connected. I
would avoid repeating code if that already exists. The following would work:
Create an empty image and cell by cell:

plot the points,
extract the ROI
store it,
delete the points.
(you will need the last step because some of your objects touch neighbouring
objects, which makes it impossible to tell them appart in terms of foreground-
background (i.e. there is no space between objects).

4. The proper solution however is to get the coordinates already sorted by the
program that generates the boundaries.

I  hope it helps

G

[Ghislain Bonamy]

Dr Landini,

Thank you so much for the great answer! Lots of good stuff in your response (as usual). In particular, thank you for pointing me to Freeman Chain code. After looking to the images, I had came up with a similar solution, but this definitively puts a nail in the coffin (since it is validated).

I agree that it would be great if Acapella could return there “stencil” in a vectorial format. However, implementing my own polygonal ROI extracter is currently faster than waiting for this to be implemented by a commercial solution.

Thanks again for pointing me in the right direction. Hopefully the code will be available through LOCI and I will update this thread when I have written the code.

Best,

Ghislain

[Ghislain Bonamy]

Gabriel, Curtis,

I have written the tool to vectorized my shape. For some reason I had some problems implementing Freeman's solution, but since I had came up with a very similar method and that it seemed like it worked I stuck with.

Curtis let me know if I can put this in bioformats.

One quick question. I assume that because I return a polygon, points that lay on the line are not required? For Instance:

10000001
10000001
01111111
00000000

Can be represented as:

X;Y
0;0
0;1
1;2
7;2   <- Here I spiked 2;2 3;2, etc.
7;0  <- Here I skip 7;1

Do you see any major problems with doing this? It would have the advantage of saving some space!

In addition, do you have any advices as to things I should avoid doing wile writing my ROI object?

Finally Does anyone know what the polyline ROI model is? If I use my previous schema:
10000001
10000001
01111111
00000000

Would a polyline representation be:
0;0 -> 7;0
0;1 -> 7;1
1;2 -> 7;2

If this is the case, that might be  better to use for objects that have "holes" such as
11111111
10010001
10101001
10010001
01000001
01111111
00000000

Since I can get the object represented bellow, it would be very easy to implement the polyline, (if it is what I suggested above).
11111111
11111111
11101111
11111111
01111111
01111111
00000000

Looking forward to your advices,

Ghislain

[Gabriel Landini]

On Thursday 14 May 2009 20:19:34 Ghislain Bonamy wrote:

> One quick question. I assume that because I return a polygon, points that
> lay on the line are not required? For Instance:
>
> 10000001
> 10000001
> 01111111
> 00000000
>
> Can be represented as:
>
> X;Y
> 0;0
> 0;1
> 1;2
> 7;2   <- Here I spiked 2;2 3;2, etc.
> 7;0  <- Here I skip 7;1

It depends, if you are counting 8 connected the chain code should be (going
clockwise):
X;Y
0;0
0;1
1;2 (now do the RLE, if you want)
6;2 (the next one is diagonally up)
7;1
7;0 (now you can jump down)
7;2 (and another RLE)
1;2
0;1
0;0 (you arrived to the start again)


If you are checking neighbours anti-clockwise:
X;Y
0;0
0;1
1;2 (now do the RLE, if you want)
7;2
7;0
7;1
6;2
1;2
0;1
0;0 (you arrived to the start again)

Think of this object
> 10000001
> 10001001
> 01111111
> 00000000

If you are checking anti clockwise, and stop at 7;0 you would have missed 4;1.
I think you'll have to assume that they are all closed contours and some of
these will have near 0-thickness.

That is why I still suggest that you implement a tested algorithm. You can
take a look at the code in particles8 plugin to get an idea of the order in
which one needs to do the checking.

Cheers
G.