Getting pixel indices between two points on a binary image

Question

I am sorry if there is any similar question to this, but I could not find it.

My question is quite simple. I have the binary curve image like one below. I want to find the white pixel locations between given two points on the same curve. I am working with Python, but any algorithm-wise suggestions would be very helpful.

import numpy as np
import cv2
import matplotlib.pyplot as plt


curve = cv2.imread('curve.png',-1)

pts = np.array([[31,14],[34,51]])

y,x = np.nonzero(curve)

fig,ax=plt.subplots()

ax.scatter(pts[:,1],pts[:,0],s=10,c='b')

for xx,yy in zip(x,y):
    if 51>xx>14:
        ax.scatter(xx,yy,s=10,c='r')
ax.imshow(curve,cmap='gray')

plt.show()

The blue points are the given points, the red points are the points I am trying to get. In the code, I added the if part just to show what I am trying to get.

I am working on skeletonized images. So, I am looking for a reasonable approach for many curves on many binary images. Do you know any algorithm/approach to do such a thing? Thank you in advance.

Answer 1

The best approach to this problem that's not already cv2 or numpy is to use a breadth-first search. The A* algorithm will not always return the smallest path, and it's more complex. Also, Dijkstra's is too complex for this problem since there is no weight between pixels.

Here is some Python code to do a raw breadth-first search to get you the shortest path between the start and end points. Note the the path array contains everything between the start and end, not the start/end themselves. It is easy to adjust to include the start and end too.

import numpy as np
import cv2
import matplotlib.pyplot as plt
from collections import deque
import sys

curve = cv2.imread('curve.png', -1)
height, width = len(curve), len(curve[0])

# The start and end point you're looking at
start, end = (31, 14), (34, 51)

# All 8 directions
delta = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]

# Store the results of the BFS as the shortest distance to start
grid = [[sys.maxsize for _ in range(width)] for _ in range(height)]
grid[start[0]][start[1]] = 0

# The actual BFS algorithm
bfs = deque([start])
found = False
while len(bfs) > 0:
    y, x = bfs.popleft()
    # We've reached the end!
    if (y, x) == end:
        found = True
        break

    # Look all 8 directions for a good path
    for dy, dx in delta:
        yy, xx = y + dy, x + dx
        # If the next position hasn't already been looked at and it's white
        if 0 <= yy < height and 0 <= xx < width and grid[y][x] + 1 < grid[yy][xx] and curve[yy][xx] != 0:
            grid[yy][xx] = grid[y][x] + 1
            bfs.append((yy, xx))

if found:
    # Now rebuild the path from the end to beginning
    path = []
    y, x = end
    while grid[y][x] != 0:
        for dy, dx in delta:
            yy, xx = y + dy, x + dx
            if 0 <= yy < height and 0 <= xx < width and grid[yy][xx] == grid[y][x] - 1:
                path.append((yy, xx))
                y, x = yy, xx
    # Get rid of the starting point from the final path
    path.pop()

    # Display the final path on the plot
    fig, ax = plt.subplots()
    ax.scatter([start[1], end[1]], [start[0], end[0]], s=10, c='b')
    for y, x in path:
        ax.scatter(x, y, s=10, c='r')
    ax.imshow(curve, cmap='gray')

    plt.show()
else:
    print(f'No path found between {start} and {end}')

This is a good approach, since it uses O(height * width) worst time complexity. Since your image is mostly skeletons, it should run significantly faster than that on average.