问题描述
很抱歉，如果有与此类似的问题，但找不到.
I am sorry if there is any similar question to this, but I could not find it.
我的问题很简单.我有下面的二进制曲线图.我想找到同一条曲线上给定两个点之间的白色像素位置.我正在使用Python，但是任何算法方面的建议都将非常有帮助.
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()
蓝色点是给定的点，红色点是我要获得的点.在代码中，我添加了if部分，只是为了展示我想要得到的东西.
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.
推荐答案
尚未通过 cv2 或 numpy 来解决此问题的最佳方法是使用广度优先搜索.A *算法并不总是返回最小路径，而是更复杂.另外，由于像素之间没有权重，因此Dijkstra的问题太复杂了.
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.
以下是一些Python代码，可以进行原始的广度优先搜索，从而为您提供起点和终点之间的最短路径.请注意，路径数组包含开始和结束之间之间的所有内容，而不是开始/结束本身.也很容易进行调整以包括开始和结束.
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}')
这是一个很好的方法，因为它使用了 O(height * width)的最差时间复杂度.由于您的图片主要是骨骼，因此其运行速度应比平均速度快得多.
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.
这篇关于获取二进制图像上两点之间的像素索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！