python - How to automate editing of x,y-path

Question

This is a pretty abstract questions, and isn't necessarily attached to a language/module. Sorry for the lack of specifics.

I'm making an object-tracing program in Python (for my biology lab I work for) using OpenCV. So far, I'm converting microscope videos into frames and then detecting the organisms swimming around.

The videos have lots of buggers that look like this:

I have successfully found ways to get x,y-paths that can outline these. When successful, it looks like this (where the x,y-path is the border around the green):

However, quite frequently, I get x,y-paths that look more like this:

As you can see, the x,y-path encompasses much but not all of the edges of the worm. I'll call this improper path an "edge mask". What I need is the second picture. I could explain to any human how to recognize this edge mask ('extreme' concavity, looping in on itself), but I'm struggling to find an algorithm that would be able to take the x,y-path in the third image and return something close to that in the second. Any ideas?

In python, the x,y-paths that make up the green masks above are stored like this in my program:

lst = [x0, y0, x1, y1, x2, y2, ..., xn, yn]

...where the (xn, yn) point is treated like it also wraps around and connects with the (x0, y0) point. I'm using this form, but it is easy to convert it to a list of tuples if necessary.

What I'm imagining is some kind of algorithm that would be able to identify the parts of the path that are completely "contained" (so to speak) by the rest of the path, aka the x,y points that are on the inside of the mask (like the red part in the picture below). If I could identify an algorithm that can identify the points on the red path and delete them, then the path would correctly contain/mask the worm.

One issue I'm seeing: Concavity alone won't help here. The worm itself is bent, and its right edge is completely concave, so I can't use concavity alone to identify the red line in the image above.

I would attach code, but the code I have is not the problem, it's finding an algorithm to adjust the output of the code I'm using. I believe my question shouldn't require & can't provide a minimum reproducible example. I think that's why they say "When appropriate..." in reference to using mre. Thanks!

---

After I've posted this, I've been thinking about it and I think I have one idea of what to do and I'd like to hear what people think:

For each x,y point on the path, I can check with evenly spaced rays to see approximately what % of rays intercept with another part of the path. The points on the red edge in the fourth picture above would have a much lower % of "escaping" rays than those on the outside, and even lower than those on the concave right side of the worm. I could delete points having a low % of escaping rays (using an arbitrary threshold) and the path would be fine. Thoughts?

---

Example raw data:

lst = [17, 297, 17, 303, 15, 305, 15, 309, 16, 310, 17, 310, 20, 313, 21, 313, 32, 324, 32, 326, 33, 326, 35, 328, 38,
       328, 39, 327, 39, 323, 38, 322, 37, 322, 36, 321, 36, 320, 35, 319, 35, 313, 36, 312, 42, 312, 43, 313, 44, 313,
       45, 314, 46, 314, 47, 315, 50, 315, 51, 316, 52, 316, 53, 317, 54, 317, 55, 318, 56, 318, 57, 319, 58, 319, 59,
       320, 60, 320, 62, 322, 63, 322, 67, 326, 70, 326, 74, 330, 75, 330, 78, 333, 79, 333, 83, 337, 83, 338, 84, 339,
       84, 340, 85, 340, 92, 347, 93, 347, 95, 349, 96, 349, 99, 352, 100, 352, 106, 358, 106, 359, 110, 363, 110, 364,
       112, 366, 113, 366, 116, 369, 117, 369, 119, 371, 119, 378, 118, 379, 112, 379, 110, 377, 109, 377, 105, 373,
       104, 373, 93, 362, 92, 362, 88, 358, 88, 357, 87, 357, 81, 351, 80, 351, 77, 348, 76, 348, 67, 339, 66, 339, 61,
       334, 60, 334, 58, 332, 57, 332, 56, 331, 55, 331, 54, 330, 48, 330, 48, 333, 49, 333, 50, 334, 51, 334, 52, 335,
       53, 335, 61, 343, 62, 343, 69, 350, 70, 350, 73, 353, 74, 353, 75, 354, 75, 355, 76, 355, 82, 361, 83, 361, 85,
       363, 85, 364, 86, 365, 87, 365, 99, 377, 100, 377, 104, 381, 105, 381, 107, 383, 108, 383, 109, 384, 111, 384,
       113, 386, 114, 386, 116, 388, 117, 388, 118, 389, 120, 389, 121, 390, 121, 392, 122, 393, 123, 393, 124, 394,
       125, 394, 126, 395, 127, 395, 128, 396, 128, 397, 129, 398, 130, 398, 133, 401, 142, 401, 143, 400, 143, 399,
       144, 398, 144, 394, 143, 393, 143, 389, 140, 386, 140, 385, 138, 383, 137, 383, 132, 378, 132, 377, 131, 376,
       130, 376, 128, 374, 128, 373, 127, 372, 127, 371, 119, 363, 118, 363, 114, 359, 114, 358, 113, 358, 110, 355,
       110, 353, 106, 349, 105, 349, 103, 347, 102, 347, 99, 344, 98, 344, 90, 336, 89, 336, 88, 335, 88, 334, 87, 333,
       87, 332, 85, 330, 84, 330, 81, 327, 80, 327, 79, 326, 78, 326, 76, 324, 75, 324, 73, 322, 72, 322, 68, 318, 67,
       318, 65, 316, 64, 316, 63, 315, 62, 315, 61, 314, 60, 314, 59, 313, 58, 313, 57, 312, 56, 312, 55, 311, 52, 311,
       51, 310, 50, 310, 49, 309, 48, 309, 47, 308, 46, 308, 45, 307, 44, 307, 43, 306, 42, 306, 41, 305, 40, 305, 39,
       304, 32, 304, 32, 308, 31, 309, 25, 309, 24, 308, 24, 302, 25, 301, 28, 301, 28, 299, 27, 299, 26, 298, 22, 298,
       21, 297]

question from:https://stackoverflow.com/questions/65660398/how-to-automate-editing-of-x-y-path

Answer 1

I went ahead and coded my idea that I had and it seems to be working well so far. Borrowed from this page about finding if two line segments intersect.

def ccw(A, B, C):
    return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])


# Return true if line segments AB and CD intersect
def intersect(A, B, C, D):
    return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)


def rayEscape(point, degree, path, radius, indx=-1):
    """Returns True if a ray going from 'point' at an angle of 'degree' (defined like in polar coordinates)
    never intercepts with path. False otherwise."""
    ray_end_point = (point[0] + radius * cos(degree), point[1] + radius * sin(degree))
    for i in range(0, len(path), 2):
        j = (i + 2) % len(path)
        seg_point_0 = path[i:i+2]
        seg_point_1 = path[j:j+2]
        if indx != i and indx != j and intersect(point, ray_end_point, seg_point_0, seg_point_1):
            return False
    return True


def deleteInsidePoints(path, num_rays, cutoff=0.0):
    """For each point, calculates the proportion of rays that go from the point and never hit any
    part of the path again. If the proportion is strictly greater than the cutoff, the point is kept in the return list.
    Otherwise, it's ignored."""
    final = []
    max_len = ((min(path[::2]) - max(path[::2])) ** 2 + (min(path[1::2]) - max(path[1::2])) ** 2) ** 0.5
    for i in range(0, len(path), 2):
        point = path[i:i+2]
        num_escape = 0
        for j in range(num_rays):
            num_escape += int(rayEscape(point, 2 * pi * j / num_rays, path, max_len, i))
        if num_escape / num_rays > cutoff:
            final.extend(point)
    return final

lst2 = deleteInsidePoints(lst, 25, 0.3)

Here are two real-life applications:

In the second one, you can see it was a bit overzealous in deleting on the left side and left a straight line, but overall it's pretty good.

Side-note: My code here is edited slightly from the first time I posted it. I forgot to not have the program check if the ray intersected with segments of the path including the point the ray was coming from. Now, the "indx" variable in the rayEscape function allows skipping of segments that include the point of interest.