How to extract vertices of open curved lines/contour in image?

Question

I have images like below and I want to extract the contour and having the vertices in clockwise or counterclockwise order. I need to use them for some calcuations so it must ordered so the points are found by traversing the outline.

I tried using cv2.findContours() however, it returns the contour closed.

Title is the script's current execution time.

You can see that it clearly doubles back.

I tried extracting just the unique coordinates but that causes some issues with the ordering. (Ignore the red line)

Code to extract contour:

code

 dirPictures = os.listdir(sourcePath)

 for path in dirPictures:
    if( '.' in path and path.split('.')[-1].lower() in acceptedFileTypes):
        
        #Reset plots to default figure size
        plt.rcParams["figure.figsize"] = plt.rcParamsDefault["figure.figsize"]
        plt.gca().invert_yaxis()
        
                    
        # Extract contour
        img = cv2.imread(sourcePath + '/' + path, cv2.IMREAD_GRAYSCALE)
        cont, hier = cv2.findContours(img, cv2.RETR_LIST, cv2.CHAIN_APPROX_NONE)

Edit:

I thought the idea of using np.where() and sorting worked but it still fails in a few cases. The countour vertices are not starting at the edges of outline so I don't believe sorting will work.

End position:

Edit 2: I attempted to use the svg path but that also failed. I utilized tatrize's potracer here

Code:

        # Extract contour
        img = cv2.imread(sourcePath + '/' + path, cv2.IMREAD_GRAYSCALE)
        img = np.array(img)

        # Create a bitmap from the array
        bmp = potrace.Bitmap(img)
        
        # Trace the bitmap to a path
        path = bmp.trace()

        # Iterate over path curves
        x = []
        y = []
        
        for curve in path:
            print ("start_point =", curve.start_point)
            for segment in curve:
                print(segment)
                end_point_x, end_point_y = segment.end_point.x, segment.end_point.y
                if segment.is_corner:
                    c_x, c_y = segment.c.x, segment.c.y 
                else:
                    c1_x, c1_y = segment.c1.x, segment.c1.y
                    c2_x, c2_y = segment.c2.x, segment.c2.y
                    x.append(c1_x)
                    y.append(c1_y)
                    x.append(c2_x)
                    y.append(c2_y)

        #turn into array of coord pairs [[x,y]...]         
        k = np.stack((x,y), axis=-1)

        #Keep unique, ordered points
        _, idx = np.unique(k, axis=0,  return_index=True)
        k = k[np.sort(idx)]
        
        plt.plot(k[:,0], k[:,1], 'g.-')
        plt.show()

nobody has implemented that for opencv. there might be code to draw from in the implementation of Canny. part of it is tracing along ridges, passing/blocking with hysteresis. — Christoph Rackwitz, Aug 03 '23 at 11:45
you could either write your own line following algorithm (use numba to make it fast) or you could use a closed contour and _not_ turn it into a set but simply follow the contour and remove duplicates in order. — Christoph Rackwitz, Aug 03 '23 at 14:37
The contour goes all the way around, visiting each pixel twice, except for the first and last points of your line, which are visited only once. So find the two pixels that are represented only once in the contour, and keep the points in between. The remainder you can discard. — Cris Luengo, Aug 03 '23 at 21:08
You can get the coordinates using np.where and np.non_zero. Then you would need to sort or follow the coordinates. — fmw42, Aug 03 '23 at 21:55
sorting by any expression involving coordinates should fail. there is no general strategy to *sort*, in the *sorting* sense, a set of nodes to extract nearest neighbor ***adjacency***. — Christoph Rackwitz, Aug 04 '23 at 09:48

score 2 · Answer 1 · answered Aug 03 '23 at 19:13

You may find it easier to use potrace to convert your shape to an SVG and parse its output. So if you save your shape as a PGM file, you can run:

potrace YOURIMAGE.PGM --svg

and you'll get the following:

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20010904//EN"
"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd">
<svg version="1.0" xmlns="http://www.w3.org/2000/svg"
 width="88.000000pt"     height="51.000000pt" viewBox="0 0 88.000000 51.000000" preserveAspectRatio="xMidYMid meet">
<metadata>
Created by potrace 1.16, written by Peter Selinger 2001-2019
</metadata>
<g transform="translate(0.000000,51.000000) scale(0.100000,-0.100000)"
fill="#000000" stroke="none">
<path d="M0 255 l0 -255 424 0 c284 0 427 3 431 10 4 6 -23 39 -59 74 -54 52
-66 68 -66 95 0 30 -5 34 -82 72 -46 22 -94 38 -108 37 -25 -3 -25 -4 -22 -78
3 -68 2 -77 -20 -96 -14 -13 -43 -25 -73 -28 -44 -6 -54 -4 -84 18 -45 34 -71
33 -103 -4 -14 -17 -36 -30 -47 -30 -13 0 -25 -9 -31 -22 -5 -14 -9 -17 -9 -7
-1 20 19 39 41 39 10 0 30 14 45 30 32 37 59 38 104 4 30 -22 40 -24 84 -18
78 10 89 25 81 110 -9 110 22 119 159 46 64 -34 70 -40 73 -71 3 -27 17 -48
69 -97 35 -35 62 -68 58 -74 -3 -5 -1 -10 4 -10 8 0 11 82 11 255 l0 255 -440
0 -440 0 0 -255z"/>
</g>
</svg>

Yes, this is also returning closed paths and the start and end points are not strictly at the ends of the outline. Even after ordering the points, there was no improvement — user22034139, Aug 04 '23 at 08:31

How to extract vertices of open curved lines/contour in image?

1 Answers1