在 RGB 图像中查找 Point 之间的路径
Finding a path between Point in a RGB image
我有一张 RGB 图像，它是一张包含道路和车站的地图。
我正在尝试找到彼此最近的车站，它们之间有一条路。
道路显示为黑色，车站显示为红色。我添加了名称，这样会更容易理解。
O -> M
A -> B
B -> C
E -> F
G -> H
G -> C
M -> N
.
.
.
两个车站之间的距离是根据它们之间的道路长度计算的。
关于解决这个问题的一些想法：
我在考虑从道路上移除车站，我们已经断开了道路，然后使用等高线来计算道路的长度（以像素为单位）。但在某些情况下（如 F 或 E），车站不会完全覆盖道路，也不会将道路分成三个不同的部分。
请告诉我你的想法，你是如何解决的。
去掉车站道路会变成这样：
这是没有标签的主图。
如果可能的话，跟踪两个站之间的路径并创建路径图像。例如从A站到C站：
哇，解决这个问题很有趣！ :-)
我用我的想法扩大红色车站斑点以确保它们接触到它们相关的道路，并且 @Micka 的“波前”解算器的想法计算出沿路线的距离形成距离图。
计算完这些距离图后，查找从 A 到 B 的距离只需读取 B 地图中 A 位置的值即可（反之亦然）。
代码
诚然，代码有点长，但应该添加注释以便您了解发生了什么。 :)
您可以找到包含额外 Matplotlib 内容的代码来生成诊断和图像 over here at GitHub。
from itertools import count, combinations
import cv2
import numpy as np
def inrange_thresh(image, color, thresh, binarize_thresh=None):
"""
Apply cv.inRange with a threshold near the given color, optionally threshold the final image.
"""
min_color = tuple(c - thresh for c in color)
max_color = tuple(c + thresh for c in color)
image = cv2.inRange(image, min_color, max_color)
if binarize_thresh is not None:
t, image = cv2.threshold(image, binarize_thresh, 255, cv2.THRESH_BINARY)
return image
def find_feature_bboxes(image):
"""
Find contours in the image and return their bounding boxes.
:return: Iterable of (x, y, w, h)
"""
cnts, *_ = cv2.findContours(image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for c in cnts:
yield cv2.boundingRect(c)
def distance_from_point(input_mask, start_point):
"""
Build a distance map following truthy paths in the input mask image, starting from start_point.
:return: Tuple of distance map matrix and infinity value for the matrix
"""
binary_mask = (input_mask > 127)
# Figure out a suitably large number to serve as "infinity" for the mask.
infinite_distance = max(binary_mask.shape) * 2
# Generate a distance map with unreachable points, then seed it with our start point.
dist_map = np.full_like(input_mask, infinite_distance, dtype="uint32")
dist_map[start_point[::-1]] = 0
# Precompute a structuring element we can use to dilate the "wavefront" to walk along the route with.
struct_el = cv2.getStructuringElement(cv2.MORPH_RECT, (3, 3))
for step in count(1):
# Compute a zero map for new neighboring pixels.
neighbor_map = np.full_like(dist_map, 0, dtype="uint8")
# Mask in all of the pixels that were filled in by the last step.
neighbor_map[dist_map == (step - 1)] = 255
# Dilate the map with the structuring element so new neighboring pixels would be included.
neighbor_map = cv2.dilate(neighbor_map, struct_el)
# Figure out which pixels in the dist map should be filled
new_dist_mask = (
(dist_map > step) & # must be more distant than we've already filled
(neighbor_map > 0) & # must be one of these new neighbors
binary_mask # must be walkable
)
if not np.any(new_dist_mask):
# If there are no new pixels, we're done.
break
dist_map[new_dist_mask] = step
return (dist_map, infinite_distance)
def main():
image = cv2.imread("hHwyu.png", cv2.IMREAD_COLOR)
marker_color = (239, 30, 40)[::-1] # RGB -> BGR
route_color = (0, 0, 0)[::-1]
# Grab a grayscale image of the markers only
markers = (inrange_thresh(image, marker_color, 5, 5) > 0).astype(np.uint8)
# Use the center of their bounding boxes as a station location
station_positions = [(int(x + w / 2), int(y + h / 2)) for x, y, w, h in find_feature_bboxes(markers)]
station_positions.sort(key=lambda pair: pair[1])
# Dilate the markers a bit so they'll always sit on the roads, then splat them on.
# We'll use this as the base map for the contour-walking algorithm so it's all connected.
markers_dilated = cv2.dilate(markers, cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)))
routes_binary = inrange_thresh(image, route_color, 25, 0)
routes_binary[markers_dilated > 0] = 255
station_infos = []
for station_id, start_point in enumerate(station_positions, 1):
print(f"Computing distance map for station {station_id} at {start_point}")
distmap, inf = distance_from_point(routes_binary, start_point)
station_infos.append((station_id, start_point, distmap, inf))
for (sa_id, sa_point, sa_map, sa_inf), (sb_id, sb_point, sb_map, sb_inf) in combinations(station_infos, 2):
distance = sa_map[sb_point[::-1]]
if distance >= sa_inf:
distance = np.inf
print(f"Distance between {sa_id} ({sa_point}) and {sb_id} ({sb_point}): {distance}")
if __name__ == '__main__':
main()
输出
输出（格式化为距离矩阵）是
B / A | #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11
#1 | - 356 288 370 212 inf 574 304 inf 455 inf
#2 | 356 - 68 232 495 inf 436 587 inf 317 inf
#3 | 288 68 - 164 427 inf 368 519 inf 249 inf
#4 | 370 232 164 - 509 inf 379 601 inf 260 inf
#5 | 212 495 427 509 - inf 713 176 inf 594 inf
#6 | inf inf inf inf inf - inf inf inf inf inf
#7 | 574 436 368 379 713 inf - 805 inf 212 inf
#8 | 304 587 519 601 176 inf 805 - inf 686 inf
#9 | inf inf inf inf inf inf inf inf - inf 114
#10 | 455 317 249 260 594 inf 212 686 inf - inf
#11 | inf inf inf inf inf inf inf inf 114 inf -
给定距离图和站点，如下面的诊断图像所示。
基于 6、9 和 11 与网络的其余部分断开连接（并且 6 与所有内容断开连接！）并且它们往往在输出中获得 inf 距离这一事实，我会说这个有效。 :-)
插图
每个站点的距离图
漂亮的动画
这些加速的 gif 说明了距离地图和邻居地图“波前”如何为左上站工作
距离图构建
邻居图构建
我有一张 RGB 图像，它是一张包含道路和车站的地图。
我正在尝试找到彼此最近的车站，它们之间有一条路。 道路显示为黑色，车站显示为红色。我添加了名称，这样会更容易理解。
O -> M
A -> B
B -> C
E -> F
G -> H
G -> C
M -> N
.
.
.
两个车站之间的距离是根据它们之间的道路长度计算的。
关于解决这个问题的一些想法： 我在考虑从道路上移除车站，我们已经断开了道路，然后使用等高线来计算道路的长度（以像素为单位）。但在某些情况下（如 F 或 E），车站不会完全覆盖道路，也不会将道路分成三个不同的部分。
请告诉我你的想法，你是如何解决的。
去掉车站道路会变成这样：
这是没有标签的主图。
如果可能的话，跟踪两个站之间的路径并创建路径图像。例如从A站到C站：
哇，解决这个问题很有趣！ :-)
我用我的想法扩大红色车站斑点以确保它们接触到它们相关的道路，并且 @Micka 的“波前”解算器的想法计算出沿路线的距离形成距离图。
计算完这些距离图后，查找从 A 到 B 的距离只需读取 B 地图中 A 位置的值即可（反之亦然）。
代码
诚然，代码有点长，但应该添加注释以便您了解发生了什么。 :)
您可以找到包含额外 Matplotlib 内容的代码来生成诊断和图像 over here at GitHub。
from itertools import count, combinations
import cv2
import numpy as np
def inrange_thresh(image, color, thresh, binarize_thresh=None):
"""
Apply cv.inRange with a threshold near the given color, optionally threshold the final image.
"""
min_color = tuple(c - thresh for c in color)
max_color = tuple(c + thresh for c in color)
image = cv2.inRange(image, min_color, max_color)
if binarize_thresh is not None:
t, image = cv2.threshold(image, binarize_thresh, 255, cv2.THRESH_BINARY)
return image
def find_feature_bboxes(image):
"""
Find contours in the image and return their bounding boxes.
:return: Iterable of (x, y, w, h)
"""
cnts, *_ = cv2.findContours(image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
for c in cnts:
yield cv2.boundingRect(c)
def distance_from_point(input_mask, start_point):
"""
Build a distance map following truthy paths in the input mask image, starting from start_point.
:return: Tuple of distance map matrix and infinity value for the matrix
"""
binary_mask = (input_mask > 127)
# Figure out a suitably large number to serve as "infinity" for the mask.
infinite_distance = max(binary_mask.shape) * 2
# Generate a distance map with unreachable points, then seed it with our start point.
dist_map = np.full_like(input_mask, infinite_distance, dtype="uint32")
dist_map[start_point[::-1]] = 0
# Precompute a structuring element we can use to dilate the "wavefront" to walk along the route with.
struct_el = cv2.getStructuringElement(cv2.MORPH_RECT, (3, 3))
for step in count(1):
# Compute a zero map for new neighboring pixels.
neighbor_map = np.full_like(dist_map, 0, dtype="uint8")
# Mask in all of the pixels that were filled in by the last step.
neighbor_map[dist_map == (step - 1)] = 255
# Dilate the map with the structuring element so new neighboring pixels would be included.
neighbor_map = cv2.dilate(neighbor_map, struct_el)
# Figure out which pixels in the dist map should be filled
new_dist_mask = (
(dist_map > step) & # must be more distant than we've already filled
(neighbor_map > 0) & # must be one of these new neighbors
binary_mask # must be walkable
)
if not np.any(new_dist_mask):
# If there are no new pixels, we're done.
break
dist_map[new_dist_mask] = step
return (dist_map, infinite_distance)
def main():
image = cv2.imread("hHwyu.png", cv2.IMREAD_COLOR)
marker_color = (239, 30, 40)[::-1] # RGB -> BGR
route_color = (0, 0, 0)[::-1]
# Grab a grayscale image of the markers only
markers = (inrange_thresh(image, marker_color, 5, 5) > 0).astype(np.uint8)
# Use the center of their bounding boxes as a station location
station_positions = [(int(x + w / 2), int(y + h / 2)) for x, y, w, h in find_feature_bboxes(markers)]
station_positions.sort(key=lambda pair: pair[1])
# Dilate the markers a bit so they'll always sit on the roads, then splat them on.
# We'll use this as the base map for the contour-walking algorithm so it's all connected.
markers_dilated = cv2.dilate(markers, cv2.getStructuringElement(cv2.MORPH_RECT, (5, 5)))
routes_binary = inrange_thresh(image, route_color, 25, 0)
routes_binary[markers_dilated > 0] = 255
station_infos = []
for station_id, start_point in enumerate(station_positions, 1):
print(f"Computing distance map for station {station_id} at {start_point}")
distmap, inf = distance_from_point(routes_binary, start_point)
station_infos.append((station_id, start_point, distmap, inf))
for (sa_id, sa_point, sa_map, sa_inf), (sb_id, sb_point, sb_map, sb_inf) in combinations(station_infos, 2):
distance = sa_map[sb_point[::-1]]
if distance >= sa_inf:
distance = np.inf
print(f"Distance between {sa_id} ({sa_point}) and {sb_id} ({sb_point}): {distance}")
if __name__ == '__main__':
main()
输出
输出（格式化为距离矩阵）是
B / A | #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11
#1 | - 356 288 370 212 inf 574 304 inf 455 inf
#2 | 356 - 68 232 495 inf 436 587 inf 317 inf
#3 | 288 68 - 164 427 inf 368 519 inf 249 inf
#4 | 370 232 164 - 509 inf 379 601 inf 260 inf
#5 | 212 495 427 509 - inf 713 176 inf 594 inf
#6 | inf inf inf inf inf - inf inf inf inf inf
#7 | 574 436 368 379 713 inf - 805 inf 212 inf
#8 | 304 587 519 601 176 inf 805 - inf 686 inf
#9 | inf inf inf inf inf inf inf inf - inf 114
#10 | 455 317 249 260 594 inf 212 686 inf - inf
#11 | inf inf inf inf inf inf inf inf 114 inf -
给定距离图和站点，如下面的诊断图像所示。
基于 6、9 和 11 与网络的其余部分断开连接（并且 6 与所有内容断开连接！）并且它们往往在输出中获得 inf 距离这一事实，我会说这个有效。 :-)
插图
每个站点的距离图
漂亮的动画
这些加速的 gif 说明了距离地图和邻居地图“波前”如何为左上站工作