How to generate a list of coordinate pairs from a simple image of a line

Question

The task here is to generate a 2D path for a robot which replicates a (hand) drawn line. The line is a simple shape being a curve or squiggle and always has one start and one end point. An example of a squiggle is pictured here.

I used OpenCV's cv2.findContours which finds both sides of the line and so generates a list of coordinates that describe both sides. What I need is a single coordinate path that would (in effect) run down the center of the line, this being the path that the robot would follow.

scikit-image's skimage.measure.find_contours generated a similar result.

I tried with an image that has one edge such as:

so that the algorithm finds only one edge. The resulting coordinate path is closer to what I need however results in a closed polygon and a coordinate path like this:

The boundary (straight) edge of the image is included, which is not desired.

So I guess I have two options that I can see. One is an algorithm that finds the mid-point between two edges along a curve (rather than finding both edges). Option two is to ignore the boundary edge of the image simply by filtering out those coordinates in that region, but that seems clunky.

Answer 1

I have a solution to this particular problem which is to use cv2.findContours which as mentioned finds both sides of a line then generating the robot path by simply using only the first 50% of the points. This works as, conveniently, the algorithm must track along one side of the line then back along the other side. I only need one side and accuracy is not that important in this application.

Answer 2

Per my comments:

If you can drive a single pixel line you could get the coordinates from pillow or any other tool that load the images as an array starting from getting all the coords of black pixel and than using an algorithm that finds a first pixel than order them adding the first closest one coord to the first and doing the same for all the rest (can't go back to the previous pixel though) until you don't have any pixel left. Does it sound right?

Also:

CONTINUED FROM ABOVE ... on a second thought how would I find the start or end of trajectory? Maybe one of the two points that has only one neighbor in the one pixel distance range?

Using your one pixel image file, I called it curve.jpg :

The file is:

curve.png: PNG image data, 409 x 376, 8-bit colormap, non-interlaced

I tried my above mentioned approach up to the finding of the two tails (start and end point of the curve), code needs to be completed using same approach :

1. choose a starting point

2. loop over : find neighbor/neighbors, choose one and keep going of course removing pixel already picked-up in these steps, until hopefully the unchoosen tails

3. get the coords you stored while removing pixels from the starting pool of black ones you choose to loop on

4. Scale and translate path from picture coordinates system to the one used by robot

My code, so far:

import PIL as pil

from PIL import Image

import numpy as np

print(pil.__version__)


def neighbors(matrix: np.ndarray, x: int, y: int):
    """
    
    stolen from https://stackoverflow.com/questions/73811239/query-the-value-of-the-four-neighbors-of-an-element-in-a-numpy-2d-array
    
    """

    x_len, y_len = np.array(matrix.shape) - 1
    nbr = []
    if x > x_len or y > y_len:
        return nbr
    if x != 0:
        nbr.append(matrix[x-1][y])
        if y != 0:
            nbr.append(matrix[x-1][y-1])
        if y != y_len:
            nbr.append(matrix[x-1][y+1])
    if y != 0:
        nbr.append(matrix[x][y-1])
        if x != x_len:
            nbr.append(matrix[x+1][y-1])
    if x != x_len:
        nbr.append(matrix[x+1][y])
        if y != y_len:
            nbr.append(matrix[x+1][y+1])
    if y != y_len:
        nbr.append(matrix[x][y+1])
    return nbr




img_array = np.array(Image.open('curve.png'))

print('\n\n___________________________')

print(img_array)

print(img_array.shape , img_array.size , img_array.ndim)

# print(img_array)

print(np.where(img_array != 0))

max_ele = np.amax(img_array)  

min_ele = np.amin(img_array)

print(max_ele , min_ele)



# create a reverse imang 0 --> 1 , 1 -->0
img_array2 = 1 - img_array



print(img_array2.shape , img_array2.size , img_array2.ndim)

print(img_array2)

max_ele = np.amax(img_array2)  

min_ele = np.amin(img_array2)

print(max_ele , min_ele)



print(img_array2[0][0])




nei = neighbors(img_array2, 1, 1)

print(nei , len(nei))
    

tails = []

for i in np.ndenumerate(img_array2):
    
    # print(i ,type(i))
    
    if i[1] == 1:
    
        neib = neighbors(img_array2, i[0][0], i[0][1])
        
        # print(neib)
        
        if sum(neib) == 1:
            
            tails.append(i)
            
print('\n\n tails : ' , tails)



result = np.zeros((img_array2.shape[0], img_array2.shape[1], 4)).astype(np.uint8)

print(result.shape)


result[result == 0] = 255

for i in tails :
    
    result[i[0][0]][i[0][1]] = (0,0,0,255) 
    



print(np.where(result == (0,255,0,255)))

print(result[0][0])
print(result[192][173])
print(result[219][279])

# print(result)


image2 = Image.fromarray(result.astype(np.uint8) , 'RGBA')


image2.save('test.png')

my output file , to prove tails could be right ones : test.png ;

test.png: PNG image data, 409 x 376, 8-bit/color RGBA, non-interlaced

tails , highlighted :

merged with , input 'curve.png' file :

I am sure there are faster/better ways to accomplish this, my Numpy and Pillow are very basic level, but I believe could be double with a single pixel, continuous line as your example.

If your actual line is different, please post it, together with your OpenCV code, I am always interested in examples that show solutions to real life problems.

NOTE ON Pixel Neighbors:

They can be more than 2:

Kept going on, till the end, code in kind of messy, but I wanted to try to get the wanted result, I am reposting entire code:

import PIL as pil

from PIL import Image

import math

import numpy as np

print(pil.__version__)


def neighbors(matrix: np.ndarray, x: int, y: int):
    """
    
    stolen from https://stackoverflow.com/questions/73811239/query-the-value-of-the-four-neighbors-of-an-element-in-a-numpy-2d-array
    
    """

    x_len, y_len = np.array(matrix.shape) - 1
    nbr = []
    if x > x_len or y > y_len:
        return nbr
    if x != 0:
        nbr.append(matrix[x-1][y])
        if y != 0:
            nbr.append(matrix[x-1][y-1])
        if y != y_len:
            nbr.append(matrix[x-1][y+1])
    if y != 0:
        nbr.append(matrix[x][y-1])
        if x != x_len:
            nbr.append(matrix[x+1][y-1])
    if x != x_len:
        nbr.append(matrix[x+1][y])
        if y != y_len:
            nbr.append(matrix[x+1][y+1])
    if y != y_len:
        nbr.append(matrix[x][y+1])
    return nbr




img_array = np.array(Image.open('curve.png'))

print('\n\n___________________________')

print(img_array)

print(img_array.shape , img_array.size , img_array.ndim)

# print(img_array)

print(np.where(img_array != 0))

max_ele = np.amax(img_array)  

min_ele = np.amin(img_array)

print(max_ele , min_ele)



# create a reverse imang 0 --> 1 , 1 -->0
img_array2 = 1 - img_array



print(img_array2.shape , img_array2.size , img_array2.ndim)

print(img_array2)

max_ele = np.amax(img_array2)  

min_ele = np.amin(img_array2)

print(max_ele , min_ele)



print(img_array2[0][0])




nei = neighbors(img_array2, 1, 1)

print(nei , len(nei))
    

tails = []

points = []

for i in np.ndenumerate(img_array2):
    
    # print(i ,type(i))
    
    if i[1] == 1:
    
        neib = neighbors(img_array2, i[0][0], i[0][1])
        
        # print(neib)
        
        if sum(neib) == 1:
            
            tails.append(i)
            
        else :
            
            points.append(i[0])
            
print('\n\n tails : ' , tails)



result = np.zeros((img_array2.shape[0], img_array2.shape[1], 4)).astype(np.uint8)

print(result.shape)


result[result == 0] = 255

for i in tails :
    
    result[i[0][0]][i[0][1]] = (0,0,0,255) 
    

# print(result)

image2 = Image.fromarray(result.astype(np.uint8) , 'RGBA')

image2.save('test.png')


def neighbors_coords(matrix: np.ndarray, x: int, y: int):
    """
    
    stolen from https://stackoverflow.com/questions/73811239/query-the-value-of-the-four-neighbors-of-an-element-in-a-numpy-2d-array
    
    """

    x_len, y_len = np.array(matrix.shape) - 1
    nbr = []
    if x > x_len or y > y_len:
        return nbr
    if x != 0 : 
        if matrix[x-1][y] == 1:
            nbr.append((x-1,y))
        if y != 0:
            if matrix[x-1][y-1] == 1 :
                nbr.append((x-1,y-1))
        if y != y_len:
            if matrix[x-1][y+1] == 1:
                nbr.append((x-1,y+1))
    if y != 0:
        if matrix[x][y-1] == 1:
            nbr.append((x, y-1))
        if x != x_len:
            if matrix[x+1][y-1] == 1 :
                nbr.append((x+1 , y-1))
    if x != x_len:
        if matrix[x+1][y] == 1 :
            nbr.append((x+1 , y))
        if y != y_len:
            if matrix[x+1][y+1] == 1 :
                nbr.append((x+1 ,y+1))
    if y != y_len:
        if matrix[x][y+1] == 1:
            nbr.append((x, y+1))
            
    # print('nbr : ', nbr , x_len, y_len)
    
    nbr_dist = []
    
    for i in nbr :
        
        dist = math.dist([x,y], [i[0],i[1]])
        
        nbr_dist.append((i[0],i[1], dist))
        

    nbr_dist.sort(key=lambda tup: tup[2] , reverse = False)  # sort points to get closest one first
    
    print('nbr_dist : ', nbr_dist , x , y)
    
    return nbr_dist



print(tails)

# print(points, len(points), type(points))

print('points : ', len(points), type(points))


start = tails[0]

img_array2[tails[0][0][0]][tails[0][0][1]] = 0
# img_array2[tails[1][0][0]][tails[1][0][1]] = 0


print('\nstart , : ', start)


cnt = 0

coords = []

first = start[0]

print('first : ', first , first[0] , first[1])

coords.append(start[0])


while points != [] :
    
    print('first : ' , first)
    
    second_next = neighbors_coords(img_array2, first[0] , first[1])
    
    print('list : ', second_next)
    
    second_next = second_next[0]
    
    img_array2[second_next[0]][second_next[1]] = 0
    
    print('second_next : ', second_next)
    
    first = second_next
    
    print('first : ', first)
    
    print(len(points))
    
    points.remove((first[0],first[1]))
    
    coords.append(second_next[:2])
    
    cnt +=1
    
    print('cnt : ', cnt  )
    
# print('tails : ', tails[1][0])
coords.append(tails[1][0])

print('\n\nCoordinates : ' , coords , len(coords))
    
print('\n\n tails : ' , tails)
    
points_img = np.zeros((img_array2.shape[0], img_array2.shape[1], 4)).astype(np.uint8)

for i in coords :
    
    print(i)
    
    points_img[i[0]][i[1]] = (255,0,0,255) 
    

image3 = Image.fromarray(points_img.astype(np.uint8) , 'RGBA')

image3.save('check.png')

# image3.show()


from matplotlib import pyplot as plt

x = [-i[0] for i in coords]

y = [i[1] for i in coords]

s = [ n*n/200 for n in range(len(x))]

plt.scatter(y,x, s = s)

plt.show()
    
    

Output :

test.png: PNG image data, 409 x 376, 8-bit/color RGBA, non-interlaced as above ;

check.png: PNG image data, 409 x 376, 8-bit/color RGBA, non-interlaced , redrawn image to checkm my coordinates are complete

And matplotlib plot that draws coordinates from first to last increasing dot size at each coordinate, to show direction of 2D x,y path:

And here is evidence that my approach has not taken into account your starting image Pixel aspect ratio (PAC)! Ouch! or is it the print size that matters? ..... just a matplotlib issue?

Fixed using plt.axis('equal'):

Answer 3

Here's a short bit of code that does the following

1. Find the two end points, which are pixels with one neighbor.
2. Get the contour. It will run on the edge pixels of the shape. Where it's not properly thinned, both halves of the contour will differ. You'll see in the picutres.
3. Split contour by which points are end points
4. ???
5. Profit

Since your picture is all black, except for the alpha channel, I'll just use that. I'll also chop off the empty space around it.

im = cv.imread("ARuYh.png", cv.IMREAD_UNCHANGED)
mask = im[:,:,3] > 0 # bool array. you'll see me using astype() a few times
# and something involving cv.boundingRect() and slicing

Notice how the contour isn't properly thinned (apparent 4-connectivity in places). That can be a problem if any of the ends end diagonally instead of axis-aligned. A different thinning mode may work better.

Now let's count neighbors with 8-connectivity, for every pixel, even the unset ones:

neighbor_kernel = np.uint8([
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]])

neighbors_count = cv.filter2D(mask.astype(np.uint8), cv.CV_8U, neighbor_kernel)

Get the single contour:

contours, _ = cv.findContours(mask.astype(np.uint8), cv.RETR_EXTERNAL, cv.CHAIN_APPROX_NONE) # mask itself is a bool array
[contour] = contours # unpacking the single contour

Dissect it:

# find endpoint indices
endpoint_indices = [
    i for i, [(x,y)] in enumerate(contour)
    if neighbors_count[y,x] == 1
]

# there must be exactly two
[i0, i1] = endpoint_indices

# slice the contour
half_contour = contour[i0:i1+1]

And a little visualization: i0 is red, i1 is blue, half-contour is green. You can tell which half of the full contour it is by where the line isn't thinned properly and it's hugging one side of the line.

That wasn't much code and I think the concept is clear as well. Any further questions?