获取二值图像上两点之间的像素索引

Question

很抱歉，如果有任何类似的问题，但我没有找到。

我的问题很简单。我有如下图所示的二进制曲线图像。我想找到同一条曲线上给定两点之间的白色像素位置。我正在使用 Python，但任何算法方面的建议都会非常有帮助。

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()

蓝色点是给定的点，红色点是我想要得到的点。在代码中，我添加了 if 部分只是为了显示我想要获得的内容。

我正在处理 skeleton 化图像。因此，我正在为许多二值图像上的许多曲线寻找一种合理的方法。你知道任何algorithm/approach做这样的事情吗？提前谢谢你。

Answer 1

cv2 或 numpy 解决此问题的最佳方法是使用广度优先搜索。 A*算法不会总是return最小路径，而且比较复杂。此外，Dijkstra 对于这个问题来说太复杂了，因为像素之间没有权重。

下面是一些 Python 代码，用于执行原始广度优先搜索以获得起点和终点之间的最短路径。请注意，路径数组包含开始和结束之间的所有内容，而不是 start/end 本身。也很容易调整以包括开始和结束。

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}')

这是一个很好的方法，因为它使用了 O(height * width) 最差时间复杂度。由于您的图像主要是骨架，因此它应该运行比平均速度快得多。

Answer 2

使用 cv2.floodFill 是个好主意。该问题通常称为寻找测地线。这是我的代码：

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)

要可靠地将曲线分成几部分，您可以不使用点，而是使用更大的 3x3 元素，例如。

之前和之后：

获取二值图像上两点之间的像素索引

Getting pixel indices between two points on a binary image

python

curve

image-processing

line