Getting Pixel Indices Between Two Points On A Binary Image

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 pi

Solution 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 _ inrange(width)] for _ inrange(height)]
grid[start[0]][start[1]] = 0# The actual BFS algorithm
bfs = deque([start])
found = Falsewhilelen(bfs) > 0:
    y, x = bfs.popleft()
    # We've reached the end!if (y, x) == end:
        found = Truebreak# Look all 8 directions for a good pathfor dy, dx in delta:
        yy, xx = y + dy, x + dx
        # If the next position hasn't already been looked at and it's whiteif0 <= yy < height and0 <= 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
            if0 <= yy < height and0 <= 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.

Solution 2:

Using a cv2.floodFill is a good idea. The problem is generally called finding a geodesic curve. Here is my code:

import numpy as np
import cv2

img=cv2.imread('UA3xU.png', cv2.IMREAD_GRAYSCALE)
pts = np.array([[31,14],[34,51]])
mask = np.zeros((img.shape[0]+2, img.shape[1]+2), np.uint8)

mask1_image = img.copy()
mask1_image[pts[0,0], pts[0,1]]=0 # split curve in first point 
cv2.floodFill(mask1_image, mask.copy(), (pts[1,1], pts[1,0]), 0, flags=8)

mask2_image = img.copy()
mask2_image[pts[1,0], pts[1,1]]=0 # split curve in second point
cv2.floodFill(mask2_image, mask.copy(), (pts[0,1], pts[0,0]), 0, flags=8)

# combine images
all_mask=cv2.bitwise_or(mask1_image, mask2_image)
out=cv2.bitwise_xor(img, all_mask)
cv2.imwrite('curve_between_two_points.png', out)

To reliably split the curve into parts, you can use not points, but larger 3x3 elements, for example.

Before and after: