Euclidean Distance Transform - EDT

EDT 欧式距离变换

距离变换是计算并标识空间点（对目标点）距离的过程，其中 EDT（Euclidean Distance Transform），欧式距离变换精度高，与实际距离相符，应用更广泛。
空间点： Free, 目标点(背景点): Occupied

暴力算法（Brute Force）

暴力迭代， 找出背景点，算呗

光栅扫描算法（Raster Scanning）

独立扫描算法（Independent Scanning）

Saito算法
Saito 和 Toriwaki [Saito and Toriwaki 1994] 设计了一种算法对 k 维图像进行 k 变换来产生EDT，每个坐标方向一个变换。对于 2D 图像，首先沿着每一行计算距离值(第一个变换)，然后使用这些值分别计算每列中每个元素的最小距离(第二次变换)。

1-DT

单行计算，从左到右
计算每个空间点对该行最近的目标点的距离， 这里其实表征的是空间点到最近的列距离

2-DT

从上到下，列计算， 这里表征的是（i,j）点对每一行的距离
1-DT 结果 + 2-DT 的平方和，取最小值，就是最后结果

算法篇 — EDT 欧式距离变换
欧几里得距离转换（EDT）算法

Maurer的算法对Saito改进

拓展到了GVD 维诺图

VD:
VR:
VS:

Felzenszwalb算法

先列后行， 用多项式拟合

欧几里得距离转换（EDT）算法

ESDF

Fast Planner——ESDF地图中距离计算（欧几里得距离转换EDT