Contour classes are wrong when using SLOPE overlap resolution

[thorstenwagner]

To reproduce:

Configuration: Sigma: 2.52 Lower Threshold: 2.21 Upper Threshold: 9.00

All contour classes are now of type "closed".

[thorstenwagner]

@hinerm You assign the contour class here: https://github.com/thorstenwagner/ij-ridgedetection/blob/master/src/main/java/de/biomedical_imaging/ij/steger/SlopeOverlapResolver.java#L482

But the junctions points are not updated, so the contour class reconstruction do not work correctly because it depends on correct junction points: https://github.com/thorstenwagner/ij-ridgedetection/blob/master/src/main/java/de/biomedical_imaging/ij/steger/LineDetector.java#L610

[hinerm]

@thorstenwagner looking at this and #19 I'm not quite sure what the correct solution is...

What I think I should happen in this case:

• Based on the contour class documentation these lines are closed since they don't have junction points at either end.
• Given that these lines are closed, the original junction point(s) between the fragments should be deleted

For a general algorithm to do this clean up, I think we want:

1. When the merged lines are created, map the old line id's to new merged id
2. Find all the junction points that reference an old line id and replace the reference with the new id
3. Delete any duplicate junction points (both pointing to the same pair of lines) or junction points that aren't pointing to the start/end of at least one line
4. Using this new set of junction points, update the contour class of the merged lines as appropriate

Does that sound right?

[thorstenwagner]

Based on the contour class documentation these lines are closed since they don't have junction points at either end.

I guess it should be cont_no_junc, /* no end point is a junction */? In my opinion cont_closed is for contours where start and enpoint is the same (e.g. circles).

Given that these lines are closed, the original junction point(s) between the fragments should be deleted

Yes!

Your clean up algorithm sounds good, but for the example above this procedure would mean that there are no junction points. I think this is not what the normal user expects. For me, its not a junction point, it is more a crossing point between the lines. Maybe we have to introduce a new type? We could search for this type of crossing using the Bentley–Ottmann algorithm listed here: https://en.wikipedia.org/wiki/Line_segment_intersection

The JTS library seems to be helpful here: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/noding/FastSegmentSetIntersectionFinder.html http://sourceforge.net/projects/jts-topo-suite/files/jts/1.13/ https://search.maven.org/#artifactdetails%7Ccom.vividsolutions%7Cjts%7C1.13%7Cjar

The line class simply had to implement th SegmentString interface: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/noding/SegmentString.html

[hinerm]

I guess it should be cont_no_junc, /* no end point is a junction */?

Oh.. of course it should. You're absolutely correct; sorry, I totally missed that.

Maybe we have to introduce a new type? We could search for this type of crossing using the Bentley–Ottmann algorithm listed here:

Yes I like that idea. Just an "IntersectionPoint" I think?

I am not confident one way or another about the intersection search algorithm. To use it, wouldn't you need some way of knowing which line segment belongs to which line at the point of intersection? Which is knowledge I assumed we didn't have. But maybe it's actually an alternative to a slope-based heuristic?

Anyway in the case of applying a slope-based heuristic we don't need to scan for intersections because the junction points are the intersection points, so they can just be converted. I think this will work well.

So in the sample image above, if you use slope detection, you will get 2 cont_no_junc lines and one IntersectionPoint.

My question is - what if you have 3 segments intersecting and do slope detection? You will end up with 2 lines such that one line intersects the other along its body. Should that be a junction or an intersection? I'm leaning towards intersection...

[thorstenwagner]

Anyway in the case of applying a slope-based heuristic we don't need to scan for intersections because the junction points are the intersection points, so they can just be converted. I think this will work well.

I don't think so, because if two ridges are crossing, it is very likely that the algorithm outputs two junction points. But in the example above, a single IntersectionPoint would be the optimal solution.

So in the sample image above, if you use slope detection, you will get 2 cont_no_junc lines and one IntersectionPoint.

Not if you simply convert the junction points into intersection points

I am not confident one way or another about the intersection search algorithm. To use it, wouldn't you need some way of knowing which line segment belongs to which line at the point of intersection?

I think you got me wrong. The algorithm should NOT be an alternative for your slope approach. After the merging stuff is done, we analyse all merged lines if there are intersections with other merged lines or segments which are not part of the merged line itself.

[thorstenwagner]

My question is - what if you have 3 segments intersecting and do slope detection? You will end up with 2 lines such that one line intersects the other along its body. Should that be a junction or an intersection? I'm leaning towards intersection...

@hinerm Could you give an example image?

[hinerm]

I don't think so, because if two ridges crossing, it is very likely that the algorithm output two junction points. But in the example above, a single IntersectionPoint would be optimal solution.

Ah, sorry, I wasn't clear - after merging lines I need to clean up any junction points:

• We can update JP references by using a map from the original lines to merged lines.
• If, after this update, a JP has 2 references to the same merged line :arrow_forward: delete the junction point
• If a JP has references to two different lines, then we convert it to an IntersectionPoint
• Then we create a map for the two source lines + x,y coordinates :arrow_forward: 'IntersectionPoint'. If there's already an entry for a given line pair and x,y coords we don't need to create a new 'IntersectionPoint'

I think this will lead to a single 'IntersectionPoint' using information we've already collected.. do you agree?

[hinerm]

Could you give an example image?

@thorstenwagner - Yeah!

So here suppose we merge AB - "junction point" between AB - C.

I think I would call that an intersection - it's the terminal of C with a nonterminal area of AB.

Then a Junction is used only for terminal - terminal meetings of segments.

[thorstenwagner]

I'm not sure if I got it right. Lets reiterate and translate it my words:

If, after this update, a JP has 2 references to the same merged line :arrow_forward: delete the junction point

If the two line references of a junction point are both segments of a merged lines, delete it.

If a JP has references to two different lines, then we convert it to an IntersectionPoint

I'm struggling here. If a JP reference to two different lines, nothing have to be done. But if one reference to a segment which part of the new merged line and the other reference not, then we could convert it into a intersection point. Did I get it right?

Then we create a map for the two source lines + x,y coordinates :arrow_forward: 'IntersectionPoint'. If there's already an entry for a given line pair and x,y coords we don't need to create a new 'IntersectionPoint'

Sorry, I do not understand this point. Which source lines?

[thorstenwagner]

I think I would call that an intersection - it's the terminal of C with a nonterminal area of AB. Then a Junction is used only for terminal - terminal meetings of segments.

I agree :-)

[hinerm]

If the two line references of a junction point are both segments of a merged lines, delete it.

of the same merged line, then yes - exactly.

Did I get it right?

Sorry, I do not understand this point. Which source lines?

I think you mostly got it, but it would be clearer if I gave an example using my 3-segment A,B,C image above:

Before merge - create junction points

The three segments meet at the same spot, so we make 3 junction points

• JP1: A, B
• JP2: A, C
• JP3: B, C

After merge - update Junction Points

We merged segments A and B, so in each junction point we replace instances of either with a reference to the merged line

• JP1: AB, AB
• JP2: AB, C
• JP3: AB, C

After merge - prune unneeded Junction Points

• JP1 - both lines are the same so we can discard JP1
• JP2 - We use our map to look up if there is already a junction point between lines AB and C at these coordinates. There is not, so we keep JP2 and add it to the map.
• JP3 - We again look up junction points at AB and C at these coordinates and find that JP2 is already mapped here. So we can discard JP3.

Final junction points

• JP2: AB, C

Let me know if this proposed algorithm is still unclear. Thanks @thorstenwagner! :smile:

[thorstenwagner]

Yippi! I got it. Sounds great!

Thanks for the clear explanation @hinerm