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

古城微笑少年丶 2022-09-21 01:43 350阅读 0赞

**0 前言**

欧几里得距离转换(Euclidean Distance Transform, EDT)简单的说即是以最常用的欧几里得距离作为

距离度量，找到每一个前景点到最近的背景点之间的距离。文中提及所有的算法中，均是将二维图片

转为两个一维向量的方式进行。

一些基本定义：

背景点为0，黑色，为感兴趣点，Voronioi elements，sites；

前景点为1：白色；

VR:某一背景点的VR指的前景点集合，这些前景点到此背景点的距离比到其他背景点距离都要短。

VS：某一前景点的VS指的是背景点的集合，这些背景点到此前景点距离比到其他前景点距离都要短。

***1. Saito的算法：***

**step1：1-D Transformation**

上到下，计算每一行中前景点到**本行**背景点距离最近的平方，得到中间结果G；

如下图，（a）为原图（b）为同一行的距离平方图，即G，公式如下：

![20150416180332929][]

![20150416180042220][]

**step2：2-D Transformation**

从左到右，对每一列，对中间结果G进行操作，计算本列背景点与本行背景点距离平方和的最小值，得到距离图（Distance Map）H；

如下图（4即使最近距离的平方）。

![20150416180603781][]

***2. Maurer的算法对Saito改进：***

第一步中的1-D Transformaion是一样的。只不过由先行后列改为先列后行。

第二步的改进基于一个事实：

**对于每一列来说，并不是所有的sites（背景）都对Distance Map起到关键作用，而仅仅取决于与这一行有交集的VR，这里用到VR的概念。**

先列后行，在经过列的1-DT后，找到与当前行有交集的VD，这些对Distance Map有作用，其他的删除。并只保留最近的VR。![20150416194146481][]

如图，这样与step2相比，每一行需要计算的前景点数量由图（a）变为最终的图（c）

判断哪个VR与这一行R有交集的标准如下两条（相关VR的选取）：

1. 在每一列的背景点（sites）中，只保留这一列与R最近的sites，如上图（a）到（b）的变化；

2. 在第一步保留的点中，有三点u、v、w按照横坐标由小到大排列，即：![Center][]。![Center 1][]

是在R与u和v垂直平分线的交点，![Center 2][]同理，如下图所示。如果![Center 3][]，即![Center 1][]在![Center 2][]的右

侧，则删除v，参照上图（b）到（c）的变化。

![Center 4][]

保留下的背景点可以按照从左至右的顺序排列保存。算法复杂度为：![Center 5][]。

***3. Felzenszwalb算法\[***3\]

该算法可以在线性的时耗进行，推荐。

![Center 6][]表示p点EDT的计算，此处已转换为一维空间，对于一行n个点，计算p

的EDT公式如下：

![Center 7][]

q也是此列中的一点，f(q)可以看做是q点的消耗函数（对于二维图像，可以认为是

上面所述的1-D Transformation）。![Center 6][]是一个以( q, f(q) )为最小值的抛物线。对

于n个q点，即有n个以( q, f(q) )为最小值的抛物线，如下图。

![20150423173846854][]

因此，对于属于\[0, n-1\]的p来说，其EDT就是这些抛物线的下包络(lower envelope)。

算法的步骤就是首先计算这些抛物线的下包络，然后根据下包络得到没一点p的EDT。

这个算法最重要的步骤就是下包络的计算。

在此,有一个事实是：图中任意两个抛物线有且仅有一个交点(intersect point)。这个

交点在一维坐标轴的投影位置s计算如下式：

![20150424145154354][]

其中，r，q为两个抛物线的凹点。可以看到若q<r,在交点的左侧，q所属抛物线低于r的，在交点右侧反之。

这里，用两个数组来从左至右顺序的得到下包络。

下包络中，第i个抛物线的水平位置（凹点）保存在数组*v\[i\]；*下包络中第i个个抛物线的范围保存在*z\[i\]*和*z\[i+1\]（每个z\[i\]保存的是交点），k*表

示下包络中包含的抛物线个数。

现有一新的抛物线，与v中最右侧的抛物线k比，只有两种可能，交点s在z\[k\]左边或z\[k\]右面，如下图所示。

![Center 8][]

若：

1：新抛物线q与队列中最后一个抛物线v\[k\]的交点s在z\[k\]右侧，则下包络添加q为最后一个抛物线，k=k+1，

z\[k\]指向s，v\[k\]指向q的凹点。如图(a)。

2：s在z\[k\]左侧，则v\[k\]不再属于下包络，更新z\[k\]为s，v\[k\]为q的凹点，如图(b)。

其排列好后每一点对应下包络的y值极为EDT，算法伪代码如下所示。

![20150506170655184][]

参考文献：

\[1\] Fabbri R, Costa L D F, Torelli J C, et al. 2D Euclidean distance transform algorithms: A comparative survey\[J\]. ACM Computing Surveys (CSUR), 2008, 40(1): 2.

\[2\] Meijster A, Roerdink J B T M, Hesselink W H. A general algorithm for computing distance transforms in linear time\[M\]//Mathematical Morphology and its applications to image and signal processing. Springer US, 2000: 331-340.

\[3\] Felzenszwalb P F, Huttenlocher D P. Distance Transforms of Sampled Functions\[J\]. Theory of computing, 2012, 8(1): 415-428.

[20150416180332929]: /images/20220721/acdf308ecdf149588c793a55ed1e6bbb.png
[20150416180042220]: /images/20220721/13f8a0ba907f49b9901c86d95b860ae0.png
[20150416180603781]: /images/20220721/7b60e6bfe6f346d5bc110d87798385f0.png
[20150416194146481]: /images/20220721/d13b694f2ca14545b6d6e583e2f00f0f.png
[Center]: https://img-blog.csdn.net/20150420112831682?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdGlhbndhaWZlaW1hbw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: /images/20220721/b53c7094c28f495aa9bfb9a0662825e0.png
[Center 2]: /images/20220721/5509c6fe852e415a9244383c2e0ad7a7.png
[Center 3]: https://img-blog.csdn.net/20150420113731808?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdGlhbndhaWZlaW1hbw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: /images/20220721/11e4fe991a32454f980b51f4d39d3afd.png
[Center 5]: /images/20220721/720c71389f9d4ef7b0efd670813aa90a.png
[Center 6]: /images/20220721/acbaddb6bf794d1390050d1934db0e46.png
[Center 7]: /images/20220721/25953ce26b1d4f54a86e53eeeb8471d6.png
[20150423173846854]: /images/20220721/db8574ac6c644c19b897d24b20e3bab9.png
[20150424145154354]: /images/20220721/478054e81935422793a7c02ab0d21afb.png
[Center 8]: /images/20220721/52b023511f344bc59f7fd456b599af5f.png
[20150506170655184]: /images/20220721/9b9e52bc9ced4892b9124c0c4a44ff9b.png