如何从100×100像素图像中提取从A到B的有序路径点列表？

我们有一张100×100像素的图像，红色线条代表一条路径。逐行扫描得到的红色像素是无序的，现在需要将这些像素整理成从起点A到终点B的有序点列表。

现有红色像素提取函数 #

from PIL import Image

# 需提前定义常量：BORDER_OFFSET（边界偏移量）、STEP（扫描步长）、COLOR_ROAD（目标红色RGB值）
def getRoad(imgPng) -> list:
    img = Image.open(imgPng)
    pix = img.load()
    width, height = img.size

    road = []

    for y in range(BORDER_OFFSET, height-BORDER_OFFSET, STEP):
        for x in range(BORDER_OFFSET, width-BORDER_OFFSET, STEP):
            color = pix[x, y]
            if (COLOR_ROAD[0]-7 <= color[0] <= COLOR_ROAD[0]+7 and 
                COLOR_ROAD[1]-7 <= color[1] <= COLOR_ROAD[1]+7 and
                COLOR_ROAD[2]-7 <= color[2] <= COLOR_ROAD[2]+7):
                road.append((x, y))

    return road

解决方案实现 #

要将无序像素排序为有序路径，核心是利用像素邻接关系进行路径遍历，步骤如下：

1. 自动识别起点A和终点B

单线条路径的端点通常只有1个邻接像素，可据此自动识别：

def find_start_end(points):
    # 构建每个点的邻接点映射
    neighbor_map = {}
    point_set = set(points)
    for point in points:
        x, y = point
        neighbors = []
        # 检查4邻域内的相邻点（适配单像素线条）
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            neighbor = (x+dx, y+dy)
            if neighbor in point_set:
                neighbors.append(neighbor)
        neighbor_map[point] = neighbors
    
    # 邻接点数量为1的点即为路径端点
    endpoints = [p for p, ns in neighbor_map.items() if len(ns) == 1]
    return endpoints[0], endpoints[1]

2. 基于深度优先搜索生成有序路径

从起点出发，依次遍历未访问的邻接点，直到到达终点：

def sort_path(unordered_points, start_point, end_point):
    point_set = set(unordered_points)
    visited = set()
    ordered_path = []

    def dfs(current):
        visited.add(current)
        ordered_path.append(current)
        if current == end_point:
            return True
        # 遍历当前点的4邻接点
        x, y = current
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            neighbor = (x+dx, y+dy)
            if neighbor in point_set and neighbor not in visited:
                if dfs(neighbor):
                    return True
        # 路径回溯（移除当前点）
        ordered_path.pop()
        return False
    
    dfs(start_point)
    return ordered_path

3. 完整调用流程

# 示例调用
if __name__ == "__main__":
    # 定义常量
    BORDER_OFFSET = 1
    STEP = 1
    COLOR_ROAD = (255, 0, 0)  # 目标红色RGB值
    
    # 获取无序红色像素列表
    unordered_road = getRoad("path_image.png")
    # 自动识别起点和终点
    start, end = find_start_end(unordered_road)
    # 生成有序路径
    ordered_road = sort_path(unordered_road, start, end)
    
    print("有序路径点列表：", ordered_road)

注意事项 #

• 若路径为粗线条，可将邻域检查改为8邻域（增加(-1,-1), (-1,1), (1,-1), (1,1)四个方向）。
• 若路径存在分支，需额外添加路径走向判断逻辑；单线条路径无需处理。
• 自动识别端点失败时，可直接手动指定起点和终点坐标。

内容的提问来源于stack exchange，提问作者Kirill