第四章 边缘检测
4.1 最优边缘检测算子
4.1.1 最优检测准则
4.1.2 最优定位准则
4.1.3 消除多重响应
4.2 一维台阶边缘的检测
4.3 二维或高维的边缘检测
4.4 需要多窗口的检测算子
景物的几何或物理性质的突变，例如深度、反射或表面方向的不连续性等，总是以图象中灰度突变的形式出现的，这些灰度突变构成了图象中的边界。对人类视觉系统的实验表明，图象中的边界特别重要，边缘检测过程可以在保留关于物体边界有用的结构信息的同时，极大地降低处理的数据量，从而简化图象的分析过程。有的情况下，根据画出了边界的物体轮廓，就可以识别物体。马尔在研究初始简图时指出，在边界处包涵的信息最丰富，它是构成初始简图的主要成分。除此以外，在以下章节中要讨论的双目立体视觉、运动视觉、表面方向检测和恢复等问题中边缘也是基本的特征。因此边界检测是图象处理和计算机视觉中的第一个基本的处理步骤。
一般来说物体的边界具有复杂的形状，难以根据图象中的灰度变化直接找出物体的边界，因此需要把边界分解成一系列的局部边缘。局部边缘是图象中局部灰度级以简单（即单调）的方式作极快变化的小区域。这种局部变化可用一定窗口运算的边缘检测算子来检测。
灰度变化的几何形状可以有以下几种：
(1) 边缘（edge）。边缘两边相邻区域中的灰度相对地均匀，只是在通过边缘时灰度发生突变，理想的情况下边缘的横截面如图4-1(a)所示，实际情况下难免有一些噪声或模糊的影响，这时边缘处的灰度分布就如图4-1(c)所示。
图4.1 灰度变化的各种情况
(2) 直线或曲线的边线。这时除了沿一条很细的带状区域以外，灰度的分布相对地均匀，在边线的横截面上灰度的分布形成一个尖锐的脉冲，如图4.1(b)所示。值得提出的是边线经常与边缘同时出现。例如，遥感图象中，在生长不同作物的田野之间的道路其图象就属于这种情形。在理想条件下这种情况的灰度分布截面如图4.1(d)所示。
4.1 最优边缘检测算子
为了便于导出描述最优边缘算子的准则，Canny首先研究了一维边缘的情况，即假设在二维图象的局部区域中，在某个方向上，边缘灰度分布的截面（简称截面）保持不变。例如，在平滑的边缘轮廓上就大致是这种情况。这时边缘检测问题可以描述为：
已知截面的边缘被白色的高斯噪声所干扰（图4.2(a)中所示为台阶边缘的情况），把边缘与所选择的滤波器作卷积。滤波器可以是各种类型，例如图4.2(b)和4.2 (d)所示分别为差分算子和高斯函数一阶微分算子。卷积以后的输出如图4.2 (c)和(e)所示。卷积输出中的局部极大值就被确定为所检测边缘的中心。这样，边缘检测算子的设计就成为一个按下述准则来寻找具有最优特性的滤波器的问题：
(1) 优良的检测特性
即漏检实际边缘和检测虚假边缘的概率都很低。由于这两种概率都是卷积输出信／噪比的单调降函数。所以这个条件相当于要求信／噪比最大。
(2) 优良的定位性
由算子检测出的边缘点应尽可能地靠近实际边缘的中心。
(3) 无多重响应
即对单个边缘只有一个响应。这点要求可以认为是蕴含在第一个准则中，因为如果对单个边缘产生两个响应，那么其中必有一个是虚假的边缘点。但第一个准则的数学形式并未表达对多重响应的要求，所以要明确规定这个要求。
图4.2 (a)带有噪声的台阶边缘，(b)差分算子，(c)对边缘应用差分算子的结果，
(d)高斯算子的一阶微分，(e)高斯函数的一阶微分算子应用于边缘卷积的结果。
4.1.1 最优检测准则
需要把上述准则用数学形式表达出来。设：滤波器的冲激响应为f(x)，边缘本身可表示为G(x)，同时边缘中心位于x=0处。那么滤波器对位于此中心的边缘的响应HG可由卷积积分表示：
4-1
图象中的噪声是随机信号，因此滤波器对噪声的响应也是随机信号。这时通常用一阶或二阶统计特性来描述滤波器的输出。如果滤波器为有限冲激响应，其边界为，并且噪声是功率谱为常数的白噪声，那么利用帕斯瓦尔公式[ ]可得到滤波器对噪声的均方根响应为：
4-2
其中是单位长度的均方噪声幅度。这样，第一个准则，即输出的信／噪比就被定义为这两个响应的商。
4-3
4.1.2 最优定位准则
对定位准则来说，最好定义某种随定位性改善而增加的测量。为此，采用检测出的边缘点与实际边缘点中心之间的均方根距离的倒数作为定位性的测量。因为把图象对算子响应的局部极大点标志为边缘点，所以算子响应的一阶导数在边缘点应为零。同时因为边缘的中央在处，所以在没有噪声时，处将是响应的局部最大值。但当有噪声时就不是这样。设：表示滤波器单独对噪声的响应，是滤波器单独对边缘的响应。假设，滤波器总的响应在处有一个局部的的极大值。那么有
4-4
如对在原点作泰勒级数展开
4-5
因为在没有噪声时，滤波器的响应在原点处有一个局部的极大值。所以，这样上式中的第一项可略去，如果实际极大值的位移很小，那么二阶和更高阶的项可被忽略。由方程(4-4)和(4-5)可得：
或 4-6
其中是一个高斯随机变量，因为它是白色高斯噪声与冲激响应为的滤波器的卷积输出，它的方差可表示为：
4-7
其中是的期望。根据(4-6)式，并利用上述结果，可得到的方差等于
4-8
定位性定义为的倒数，即
4-9
(4-3)和(4-9)两式是最优检测和定位准则的数学形式，这样滤波器的设计就简化为这两项同时为最大的问题。为此，我们要使(4-3)和(4-5)的乘积最大，也就是使下式为最大。
4-10
4.1.3 消除多重响应
上述检测准则测量了滤波器在原点处区分信号与噪声的有效性，但并未考虑滤波器在边缘中心附近区域的特性。根据积分的许瓦兹不等式可很简单地求得上述两个测量的上限值。根据(4-3)式，SNR的上界为：
定位性Localization（(4-9)式）的上界为
在 区间中，当时，SNR和Localization都达到上界，从而SNR·Localization得到最大值。因此，根据前两个准则，对台阶边缘来说最优的边缘检测算子是差分算子，或截短的台阶算子。但差分算子的频带很宽，当台阶边缘包含噪声时，在输出响应中常会出现很多极大值，这时就会造成严重的问题。根据第一个准则，这些额外的边缘都应被看作错误。但上述准则的解析公式是根据在单个点（即边缘中心）处的响应得出的，并未考虑周围若干点的相互作用。从图4.2 (c)可看到差分算子对有噪声的台阶边缘的响应大致是三角形的峰，但在边缘附近有许多很陡的极大值。
这些极大值点相互靠得很近，以至难以区分哪个是台阶边缘的响应，哪些是噪声。所以需要限制滤波器在台阶附近的响应，使得检测多于一个边缘的概率很低。理想情况下，我们希望在噪声情况下的响应其峰点之间的距离大致等于边缘检测算子对单个边缘所产生响应的宽度，这个宽度是算子宽度W的若干分之一。
为了把这个准则表示为对滤波器的约束，这里需要得到相邻噪声峰点之间距离与之间的表达式。不难看出输出中相邻极大点之间的平均距离是算子输出一阶导数中相邻过零点之间距离的２倍，因为输出中的极小点也会产输出一阶导数中的过零点。因此，Canny利用Rice得到的结果：函数g对高斯噪声的响应中过零点之间平均距离是：
4-11
其中是的自相关函数。
和
在这里的情况下，所寻找的是函数对高期噪声响应中的过零点平均间距
4-12
的噪声响应中相邻极大值之间的距离用表示。。这个距离可取为算子宽度的某个分数K。这被认为是多重响应约束。
4-13
这个约束是很自然的，因为滤波器的响应将集中在宽度2W的区域中。在此区域中噪声极大值个数的期望为
4-14
确定了，就是确定了在此范围内可导致错误响应的噪声极大值的数量。至于这些噪声极大值造成错误检测的可能性大小，还要取决于信噪比的大小。为减少错误检测，在信噪比小时，应使更少些，即选大些。选定以后，如何按（4-12）式求得的问题将在下一节中介绍。
这里需要指出的是（4-12）式所表示的极大值之间的间距与算子的宽度成正比。对这点可这样来说明：假设我们先定义一个算子 ，它是延伸倍的结果，即。然后把它代入（4-12）式。可以发现对来说，极大值之间的间距是
4-15
因此，如果在某个值条件下，满足多重响应约束（4-13）式，并假设，与成比例，那么函数也满足（4-13）。所以对任何固定的，相对于的空间比例来说，多重响应准则具有恒常性。
4.2 一维台阶边缘的检测
一般来说很难找到符合多重响应约束，并使（4-10）式极大的函数。甚至当是很简单的形式（例如，是台阶边缘）时，仍然是很复杂的。但在离散的情况下可以用数字化方法来求解。以下用输入是台阶边缘的情况来说明求解的方法。我们取，其中是函数（delta函数）的第阶导数，是边缘台阶的幅度。这就是
4-16
用置换（4-3），（4-9）中的，则得
4-17
4-18
由上述两公式可见，这两项准则都可直接通过提高而得到改变。可被看作是图象的信／噪比。现在我们去除这些与图象有关的部分，并定义两个性能测量和，它们只与滤波器本身有关。
4-19
4-20
以下我们先分析一下滤波器的宽度，或空间比例，对和的影响。假设我们从产生一个与成空间比例的滤波器，前面已证明了多重响应准则不受空间比例的影响。当把代入（4-19）和（4-20）时可得到空间比例滤波器的性能测量为
4-21
这两个公式中的第一个公式的含义比较直观。即，用于台阶边缘时，冲激响应函数较宽的滤波器的信／噪比要比冲激响应函数较窄的高。因为与成正比。第二个公式表明较窄的滤波器比宽的滤波器有较好的定位性。因为与成反比。这就是存在于台阶边缘检测算子的检测性能与定位性能之间的不确定性原理。通过对在空间上作比例变换，我们可在检测特性和定位性之间作综合平衡，但我们不能同时改善这两者。这意味着把综合准则选择为（4-19）和（4-20）的乘积是很自然的。因为这个准则在比例变化时保持不变。
4-22
现在求解的问题就变成了根据（4-22）式寻找f使极大的问题。式（4-22）中有四项积分，难以直接用变分法求解。为此，Canny把（4-22）式的极大值问题演绎成在使其余３项积分保持不变的条件下，使SNR项分母中的积分极小的问题，即求解使下述积分极小的函数
(4-23)
与此同时要求满足下述约束条件：
(4-24)
利用拉格朗日（Lagrange）乘子法首先生成一个复合函数，这个函数是出现在要求极小化的表达式和约束条件中的函数的线性组合。求解的无约束极大值等价于求解原来的约束条件下的极大值。这时就可以按变分法，用欧拉（Euler）方程求解，求得在范围内的通解形式为
4-25
这个函数满足下述边界条件：
其中是未知常数，它等于函数在原点处的斜率。因为是反对称的，可利用把上述定义扩展到的范围，利用上述边界条件来求解。这样函数是由参数和来表示。现在仍需寻找能使综合准则积分的商最大的这些参数。经过上述推导，Canny把这个在无限维空间中的函数优化问题演绎为一个在变量和（只是附加常数，与复合准则无关）中非线性优化问题。遗憾的是得到的结果（它还要满足多重响应的约束）过于复杂，不可能求得解析形式的解。因此，最后的解不得不以数值计算的方法来求得。
的形状取决于多重响应约束，即它将取决于我们要强迫相邻的响应离得多远。图4-3中所示为在选择不同间距时的形状。前面已经提到过对任意的不存在单个的最优函数，而是一类函数。这类函数是通过以对典型函数作比例运算求得。当图象中信／噪比较低时，我们就希望使响应的极大点能相互远离。但不太清楚对单个算子来说，合适的信／噪化应是多大。所以在应用这个算子时应使用若干不同宽度的算子，并有一个决策过程来从中选择一个宽度最小，但其输出中的信／噪比仍高于阈值的算子。我们试图选择一个间距，使得在此间距下多重响应的误差与由于阈值引起的误差可相比拟。在假设噪声的概率密度分布是高斯函数的条件下，根据检测的错误率与多重响应错误率相等的条件，可求得
4-26
其中是确定的、允许的、信噪比的阈值，。
不过实际上不可能找到满足上述条件的滤波器，所以改为要求满足下述条件
4-27
其中(要求尽可能接近于1。图4-4中所示为具有不同参数的几个滤波器的性能指标。
图 4.3 不同间距时f函数的形状
根据有约束的数字优化方法，在时滤波器的最大值可达。但如果我们稍微放松对多重响应特性参数(的要求，那么可以在和这两个特性方面有显著的改进。这就如图4.4中第4、5两个滤波器的特性所示。
滤波器参数
n
Xmax
1
0.15
4.21
0.215
24.59550
0.12250
63.97566
2
0.3
2.87
0.313
12.47120
0.38284
31.26800
3
0.5
2.13
0.417
7.85869
2.62856
18.28800
4
0.8
1.87
0.515
5.06500
2.56770
11.06100
5
1.0
1.33
0.561
3.45580
0.07161
4.8084
6
1.2
1.12
0.576
2.05220
1.56939
2.91540
7
1.4
0.75
0.484
0.00207
3.50350
7.47700
图4.4 不同参数下滤波器的性能
其中时的滤波器可以用高斯函数，的一阶导数来近似。高斯函数的一阶导数冲激响应函数等于
可以证明，这时的
与原来的滤波器6的特性相比，特性下降大约20%，多重响应大约下降了10%。在用于实际的图象时，这样的特性下降是难以分辨的，因此是可以接受的。这样的近似带来的优点是不但简化了计算，而且在二维的情下计算要方便得多。
4.3 二维或高维的边缘检测
在一维时，我们可以用一维坐标来说明台阶边缘在空间中的位置。在二维图象时，还要说明边缘的方向。我们把边缘定义为二维空间中边缘轮廓的切线方向。设与边缘垂直的方向为。在一阶情况下Canny算子可以用高斯函数的一阶微分算子来近似，那么在二维时就应用二维高斯函数沿某个方向的一阶方向导数来近似，也就是说
4-28
因为是予先不知道的方向，所以可用梯度方向来估计，即
4-29
边缘点可由算子与图象I卷积后所得图象中的局部最大点来确定。这个局部最大点可根据方向导数为零来求，即
4-30
把代入上式，得
4-31
在这些边缘点，边缘强度将等于
4-32
由（4-31）式，根据卷积与微分的结合律，可先用对称的高斯函数作卷积，然后由寻找二阶方向导数的零点来确定边缘的位置，并可用式（4-32）来估计边缘的强度。这与用方向算子来检测和定位边缘点等价，但在卷积以前并不需要知道方向。
把这样的二阶方向导数算子的性能与Laplacian算子的性能作一比较是有益的。二维的Laplacian可分解成在任意二个垂直方向上的分量。如果把梯度方向取为其中的一个方向，那么这时Laplacian算子的一个分量的作用与上述二阶方向导数算子的作用相同，而另一个分量则对检测和定位边缘不起作用，而只会增加噪声。
4.4 需要多窗口的检测算子
在确定了检测算子的最优形式以后，还要解决如何选择算子宽度的问题，以便在某个特定的应用条件下，在检测和定位性之间达到最佳的综合平衡。
由于图象内各个边缘点的信噪比不同，所以一般来说需要采用不同宽度的算子，然后
图4.5 (a) 时检测的边缘， (b) 时检测的边缘，
，(a)和(b)中边缘的迭加，(d)应用特征综合方法求得的边缘
把不同算子的结果综合起来。canny提出了把不同算子运算结果综合起来的基本原则是只要算子的输出具有足够的，那么就要用宽度小的算子，因为这时边缘的定位性最好。以这条从细到粗的启发式准则为起点，然后需要一个局部的决策过程，以便当在此领域中对不同宽度的算子有多个响应时，确定是否应该标志一个或多个边缘点。很可能出现的情况是：较大宽度算子检测出的边缘点与一个由最小宽度算子检出的边缘点不会完全吻合。如果只保留第一个边缘点，而把其它的边缘点都去除，这时就会产生不希望的效果，使较大的算子不能检测出与陡峭变化的边缘相重迭的缓慢边缘。因此，Canny提出采用“特征综合”（feature synthesis）的方法。首先标出所有用最小宽度算子检测到的边缘，并由这些边缘点合成产生如果在此图象中只有这些边缘点时，大宽度算子的输出大小，然后把使用上述大宽度算子的实际输出与合成产生的输出相比较。如果实际的输出远大于由合成产生的输出时，那么就要增加标志新的边缘；反之，则不增加。这样的过程可随算子宽度的增加不断的重复。在此过程中不断的加入用较小宽度算子未检测到的边缘点。最后产生一幅迭加的边缘点图。事实上，经常出现的情况是较小的算子可检测出大部分的边缘点，而较大的算子则检测出大部分阴影和灰度缓慢变化的边缘或纹理区域的边缘。图4.5所示为应用特征综合时得到的结果。从图中所示的例子可发现，较小尺度的算子已能检测出大部分边缘点，但是当把使用和的算子时检测到的边缘相迭加时发现，在大多数情况下两个算子对同一边缘的响应并不重合。当使用特征综合方法时就能把较大算子产生的多余响应消除，从而得到较清晰的图象边缘，如图4.5 (d)所示。
参考文献：
[Can 86] Canny, J., A Computational Approach to Edge Detection, IEEE trans. on Pattern Analysis and Machine Intelligence, vol PAMI-8, No 6, Nov, 1986, 679(698.
