如何用Python实现沿二值掩码图像计算像素的L1最短距离？

现成Python工具实现 #

方法1：使用scikit-image的MCP类 #

scikit-image的skimage.graph.MCP（移动成本规划器）专门适配网格场景的最短路径计算，完全符合你的需求：

• 先将二值掩码转换为成本数组：掩码像素（值为1）设为可通行（成本1，对应L1每步的代价），非掩码像素（值为0）设为不可通行（成本设为np.inf）。
• 初始化MCP对象后，调用find_costs方法传入种子点(4, 0)，即可得到所有掩码像素到种子点的L1最短距离。

示例代码：

import numpy as np
from skimage.graph import MCP

# 假设你的二值掩码数组名为mask
mask = np.random.randint(0, 2, (100, 200))  # 示例掩码
mask[4, 0] = 1  # 确保种子点在掩码内

# 创建成本数组：掩码区域成本为1，非掩码为不可通行
costs = np.where(mask == 1, 1, np.inf)

# 初始化MCP，仅考虑四邻域（对应L1距离）
mcp = MCP(costs, fully_connected=False)
# 计算种子点到所有点的距离
distances, _ = mcp.find_costs([(4, 0)])

# 最终结果：distances数组中，掩码像素的位置存储了到种子点的L1最短距离，非掩码位置为inf

方法2：基于BFS的简易实现 #

如果不想引入额外库，手动实现BFS也非常高效——因为L1距离的最短路径本质就是网格中的最少步数，BFS天然适配这种场景：

• 初始化距离数组，种子点距离设为0，其余掩码像素设为-1（未访问）。
• 用队列遍历种子点的四邻域掩码像素，依次更新距离，直到所有可达掩码像素都被访问。

转稀疏图的效率分析 #

将掩码区域转为稀疏图后用最短路径算法处理100x200的图像完全没有性能压力：

• 掩码像素最多20000个，每个像素最多有4个有效邻接（上下左右的掩码像素），稀疏图的边数最多80000条，规模极小。
• 由于所有边的权重都是1（L1每步代价），可以用BFS优化的最短路径算法，时间复杂度为O(N+E)（N是掩码像素数，E是边数），处理这个规模的数据几乎瞬间完成。

若手动构建稀疏图：

1. 给每个掩码像素分配唯一ID。
2. 遍历每个掩码像素，检查其四邻域的掩码像素，添加权重为1的边。
3. 用scipy.sparse.csgraph.shortest_path计算单源最短路径，指定method='breadth_first'利用L1距离特性加速。

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