张春晖　任晓蕾

摘要：目前，二维欧氏距离变换已经成为图像处理与模式识别领域的重要方法。最初它只是应用于二值图像的处理，但是经过近几年的发展，特别是布朗大学的Pedro F. Felzenszwalb对二维欧氏距离变换进行了革命性的扩展并提出了线性计算复杂度的求解方法，二维欧氏距离变换才真正被广泛应用于模式识别领域。本文就二维欧氏距离变换的三个演进阶段进行总结归纳，并给出各个阶段的相应的求解方法与应用分析，以期提供二维欧氏距离变换的扩展思路，进一步拓展它的应用领域。

关键词：二维欧氏距离变换；特征提取；目标检测；计算几何

中图分类号：TP391.4 文献标识码：A 文章编号：1007-9416（2017）04-0060-03

距離变换的概念在1966年被Rosenfeld首先提出[1]，它是计算并标识图像像素与前景目标最小距离的过程。由于可以表征图像中目标的结构特征，因此被广泛应用于图像处理、计算机视觉和模式识别领域。

最初，距离变换只是应用于二值图像的处理，变换结果不再是一幅二值图像，而是一幅灰度级图像，变换结果中的像素表示的是该像素到达背景区域的最短距离。假设存在一幅分辨率为的二值图像

其中，属于背景区域，表示像素和之间的距离量度。距离度量可以分为两大类：欧氏距离和非欧氏距离，常用的非欧氏距离度量有城市街区距离和棋盘距离。欧氏距离、城市街区距离和棋盘距离分别表示如下[2]：

我们在本文中只讨论二维欧氏距离变换。

在下面的内容中，我们将以二维欧氏距离变换的发展为线索，同时结合它在每个阶段的运算方法和应用来讨论。

1 二值图像的二维欧氏距离变换

结合式（1）和式（2），二值图像的二维欧氏距离变换可以表示为：

计算二值图像的二维欧氏距离变换通常有两类方法，一类是基于模板的近似计算方法[3][4]，另外一类是精确计算的方法[5][6]。在第一类方法中，文献[4]提出了欧氏距离的一种近似估计：Chamfer距离（式（3） 和式（4）所表示的城市街区距离和棋盘距离其实也是欧氏距离的近似表示形式）。Chamfer距离使用整数来代替欧氏距离变换的浮点数，降低了计算复杂度，同时它的精度高于城市街区距离和棋盘距离。在文献[7]中，作者采用下图1（a）（b） 所示的模板依次对二值图像进行腐蚀操作以达到Chamfer距离变换的目的。由此可见，该方法具有线性的计算复杂度（）。 处理效果如图1（c）所示。一般学术界认为，基于模板的近似计算方法的计算复杂度偏低，但是精度有限，而精确计算方法的精度高，但是计算复杂度也偏高[8]。在精确计算的方法中，布朗大学的Pedro F. Felzenszwalb作出了革命性的贡献，提出了一种在线性计算复杂度内精确计算欧氏距离变换的方法[6]，并将二值图像的欧氏距离变换泛化为多值图像的欧氏距离变换。在文献[6]中，距离变换的表达式（式（5））被修改为：

式（7）为文献[6]提出的泛化欧氏距离变换的特殊形式，在文中，作者采用计算几何的方法对泛化欧氏距离变换进行计算，计算复杂度为，计算方法请参考下一章节。采用并行运算技术也是解决欧氏距离变换运算时间长的一种思路，文献[9]采用分区域的思路将二值图像的欧氏距离变换的工作并行化。最近，GPU强大的并行计算能力正在被人们所认知和发掘，特别是NVIDIA公司开发的GPU拥有数以千计的运算核心，加以cuda作为运算平台，使GPU的运算效率比CPU快几十倍。例如，文献[10]采用了NVIDIA 的GTX280 芯片来计算二值图像的球面距离变换。

二值图像的二维欧氏距离变换作为图像处理的基础方法被广泛应用于计算机视觉领域，特别是骨架提取和边缘检测。文献[8]针对传统基于距离变换的骨架提取算法不能保证骨架连通性的问题，提出了一种以距离变换为约束，以种子点为起点，逐点生长出骨架的算法，同时该算法很容易被扩展到三维情况。该算法使用距离变换值最大的像素作为种子点，然后选择距离变换值下降最缓慢的点逐点生长，保证了骨架的连通性和准确性，但是该方法所选择的距离变换算法的计算复杂度偏高（），从而导致算法的效率偏低。文献[11]针对当前车道边缘检测不连续的问题，提出了基于行方向距离变换的车道检测算法，跟传统距离变换不同的是，行方向距离变换只计算与车道线水平方向的距离，如下式所示：

由式（9）可看出，该距离变换值对不连续车道具有很强的鲁棒性，且计算效率较高，该方法可为自动驾驶技术提供更高的行车安全保障。文献[12]针对传统边缘轮廓提取方法和Hough变换方法在边缘存在干扰的情况下不能准确确定SAR图像中矩形目标轮廓的问题，首先采用Canny边缘检测算子处理SAR图像，对结果图像进行二维欧氏距离变换，然后采用层次聚类法使用欧氏距离对像素进行聚类确定矩形位置，最后采用矩形的几何特征对矩形轮廓进行精确定位。实验结果表明该方法相比上述传统方法对图像干扰具有更强的鲁棒性，并且定位精度较高。文献[7]针对传统基于距离变换的边缘匹配方法容易受到干扰的问题，首先对图像进行二值距离变换，同时计算标记图（即每个像素与目标区域像素在进行距离变换时的对应关系图），最后使用遗传算法将原有模型跟距离变换结果和标记图进行匹配，实验结果表明，该方法可以达到更好的边缘匹配度。文献[13]为了达到快速检测人脸的目的，首先采用肤色信息对图像进行二值化，然后采用距离变换对二值图像进行处理，最后根据距离变换的极大值确定人脸的位置和尺寸。

2 多值图像的二维欧氏距离变换

二值图像的欧氏距离变换仅仅考虑了距离量度而没有考虑像素值的大小，如前章所述，二值图像的欧氏距离变换是文献[6]提出的泛化欧氏距离变换的特殊形式。泛化欧氏距离变换的表达式为：

由上式（10）可以看出像素值也被考虑进了距离度量中，因此又叫做多值图像的欧氏距离变换。

由于第一项与无关，因此式（10）可以变为

因此，式（10）的求解可以拆分为：（1）首先对图像的每一列数据作一维欧氏距离变换，（2）然后以第一步的计算结果为输入，对每一行数据作一维欧氏距离变换。一维欧氏距离变换可以表示为：

式（12）可以采用计算几何的方式来求解：首先对以（）为根点的一系列抛物线求取下包络，也就是下包络在处的值。文献[6]已经证明，一维欧氏距离变换的计算复杂度在最差情况下为，因此计算式（10）的计算复杂度最差为。而且该方法很容易扩展到任意维图像的欧氏距离变换。

由上一章可以看出，二值图像的欧氏距离变换主要应用于图像处理、特征提取领域。而多值图像的欧氏距离变换主要用于目标部件检测领域，用以发掘目标部件之间的结构特征。例如文献[14][15]提出了一种基于星形结构的目标部件检测模型，该方法的目标函数为：

其中，该模型共存在个部件，表示星形结构的顶点集，即部件集（个元素），表示星形结构的边集（个元素），表示图像的像素附近区域与部件的匹配代价，表示部件与部件的弹性代价。在文献[14]中，采用普通欧氏距离的形式：

其中，，，，为常数。因此，式（13）可以按照标准多值二维欧氏距离变换的方式来求解，然而在文献[15]中， 采用马氏距离的形式，需要将图像进行相应的旋转将马氏距离变为欧氏距离然后再作距离变换，最后将距离变换的结果重新旋转回原来的角度，也就得到了二维马氏距离变换的运算结果。最小化式（13）便可以同时保持部件之间的相对关系又使部件内部的局部纹理尽可能匹配，从而可以得到精确的目标部件位置（）。为了更加准确表征目标部件之间的相对关系，文献[16]采用树形模型来代替星形模型。文献[17]针对树形模型和星形模型不能准确约束部件位置的问题，提出了网状模型，实验结果表明，在匹配代价模型不准确的情况下，定位精度有所提高。以上所述的目标部件检测方法虽然模型方法不同，但最终目标函数的求解都用到了多值图像的二维欧氏距离变换。

3 拓展的多值图像的二维欧氏距离变换

虽然上一章所述的目标部件检测方法采用二维欧氏距离变换可以精确计算目标函数的最优值，定位精度很高，但是只适用于非旋转目标的检测。为了使目标检测方法对旋转鲁棒，文献[18]设计了与式（13）相似的目标函数，不同的是弹性代价函数：

其中，表示部件与部件之间的平均距离。该弹性代价函数将两两部件之间的距离约束在一定范围内，因而该方法对旋转是鲁棒的。于是产生了拓展的多值图像的二维欧氏距离变换：

为了方便计算，文献[18]在式（16）中引入了两个辅助变量，于是式（16）变为：

当=0时，式（17）将退变为式（10）。受到式（12）计算的启发，上式同样可以采用计算几何的方式来计算：首先对以（）为根点的一系列抛物曲面求取下包络，也就是下包络上沿着一个圆（以为圆心，为半径）的最小值。文献[18]已经证明整个计算过程的计算复雜度平均为。

4 结语

本文就二维欧氏距离变换的发展进行了逐一介绍，在每个发展阶段，分别介绍了它的计算方法和应用。二值图像的欧氏距离变换主要用于图像处理和图像特征提取领域，而多值图像的欧氏距离变换多用于目标部件检测领域，拓展的多值图像的欧氏距离变换由于起步较晚，目前只应用于具有旋转不变性的目标部件检测领域。在众多二维欧氏距离变换的计算方法中，我们比较看好Pedro F. Felzenszwalb提出的基于计算几何技术的运算方法，它不但具有高的计算精度，而且拥有线性的计算复杂度。

参考文献

[1]Azriel Rosenfeld and John L Pfaltz. Sequential operations in digital picture processing[J]. Journal of the ACM，13（4）：471-494，1966.

[2]Ricardo Fabbri， Luciano Da F Costa， Julio C Torelli， and Odemir M Bruno. 2deuclidean distance transformalgorithms[J]： A comparative survey. ACM Computing Surveys， 40（1）：2-45，2008.

[3]StinaSvensson and GunillaBorgefors. Digital distance transforms in 3d images using information from neighborhoods up to 5×5×5[J].Computer Vision and Image Understanding， 88（1）：24-53，2002.

[4]GunillaBorgefors. Hierarchical chamfer matching： A parametric edge matching algorithm[J].IEEE Transactionson Pattern Analysis and Machine Intelligence，10（6）：849-865，1988.

[5]Toyofumi Saito and Jun-Ichiro Toriwaki. New algorithms for euclidean distance transformation of an n-dimensionaldigitized picture with applications[J].Pattern Recognition， 27（11）：1551-1565，1994.

[6]Pedro Felzenszwalb and Daniel Huttenlocher. Distance transforms of sampled functions[J]. Theory and Computing，8：415-428，2012.

[7]张煜，孙家抦，张晓东.一种基于距离变换与标记图的边缘匹配方法[J].武汉大学学报 （信息科学版），31（8）：675-678，2006.

[8]丁颐，刘文予，郑宇化.基于距离变换的多尺度连通骨架算法[J].红外与毫米波学报，24（4）：281-285，2005.

[9]崔峰，汪雪林，彭思龙.近似欧氏距离变换的一种并行算法[J].中国图象图形学报，9（6）：693-698，2004.

[10]陈伟锋，王锐，潘明皓，等.基于GPU的快速球面距离变换[J].计算机学报，34（3）：499-507，2011.

[11]蒋如意，刘洪涛，胡文，等.改进的图像距离变换方法在车道检测中应用[J].上海交通大学学报， 46（9）：1450-1454，2012.

[12]李慧平，李映，张秀伟.结合 Canny 和距离变换的矩形模式特征提取方法[J].计算机工程与应用，47（18）：166-182，2011.

[13]曹灿，吴向前.基于肤色信息和距离变换的快速人脸检测算法[J].信阳农业高等专科学校学报，19（2）：111-113，2009.

[14]Pedro F Felzenszwalb，Ross B Girshick， David McAllester， and Deva Ramanan. Object detection with discriminatively trained part-based models[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，32（9）：1627-1645， 2010.

[15]David Crandall， Pedro Felzenszwalb， and Daniel Huttenlocher. Spatial priors for part-based recognition usingstatistical models[C]. In Computer Vision and Pattern Recognition， volume 1， pages 10-17. IEEE， 2005.

[16]Pedro F Felzenszwalb and Daniel P Huttenlocher. Pictorial structures for object recognition. InternationalJournal of Computer Vision[J]， 61（1）：55-79，2005.

[17]张春暉.基于信息融合的目标检测和 PET 目标重建方法[D].西安电子科技大学，2015.

[18]Chunhui Zhang， Jimin Liang， Jun Zhang，and Heng Zhao. A new shape prior model with rotation invariance[J].Pattern Recognition Letters，54：82-88，2015.