距离变换算法：从D4距离到工程实践全解析

1. 距离变换算法概述

距离变换（Distance Transform）是计算机视觉和图像处理中的一项基础技术，它计算图像中每个像素到最近前景像素的距离。这项技术在图像分割、目标识别、形态学操作等领域有着广泛应用。

D4距离（又称曼哈顿距离）是距离变换中最常用的距离度量之一。它得名于在网格状道路系统中（如曼哈顿街区），两点之间的最短路径只能沿水平和垂直方向移动。数学表达式为：D4(p,q) = |x₁ - x₂| + |y₁ - y₂|。

与欧式距离（D8）相比，D4距离计算更简单快速，且在某些应用中（如VLSI布线、机器人路径规划）更符合实际场景的运动约束。在8×8的示例图像中，我们清晰地看到：

• 前景像素（值为1的点）的距离为0
• 背景像素的距离值随远离前景而递增
• 距离场呈现明显的"辐射状"扩散特征

2. 算法实现细节解析

2.1 基础实现方法

最直观的实现方式是暴力搜索法，这也是示例代码采用的方法。其时间复杂度为O(n²m²)，其中n和m是图像尺寸。对于8×8的小图像尚可接受，但对于大图像需要优化。

关键改进点包括：

1. 并行计算：利用现代CPU的多核特性，将图像分块处理
2. 提前终止：当找到距离d=1的像素时即可停止搜索
3. 空间索引：建立前景像素的空间索引结构加速查询

2.2 高效算法对比

实际工程中更常用的是两遍扫描算法（如Rosenfeld算法），时间复杂度降至O(nm)：

python复制def distance_transform(image):
    # 第一遍：左上到右下扫描
    for i in range(1, h):
        for j in range(1, w):
            if image[i,j] == 0:
                image[i,j] = min(image[i-1,j], image[i,j-1]) + 1
    # 第二遍：右下到左上扫描
    for i in range(h-2, -1, -1):
        for j in range(w-2, -1, -1):
            if image[i,j] != 0:
                image[i,j] = min(