《计算机视觉》课程教学资源（教材）第四章边缘检测.doc_大学文库

第四章边缘检测 4.1最优边缘检测算子 41.1最优检测准则 41.2最优定位准则 41.3消除多重响应 42一维台阶边缘的检测 43二维或高维的边缘检测 44需要多窗口的检测算子景物的几何或物理性质的突变,例如深度、反射或表面方向的不连续性等,总是以图象中灰度突变的形式出现的,这些灰度突变构成了图象中的边界。对人类视觉系统的实验表明, 图象中的边界特别重要,边缘检测过程可以在保留关于物体边界有用的结构信息的同时,极大地降低处理的数据量,从而简化图象的分析过程。有的情况下,根据画出了边界的物体轮廓,就可以识别物体。马尔在研究初始简图时指出,在边界处包涵的信息最丰富,它是构成初始简图的主要成分。除此以外,在以下章节中要讨论的双目立体视觉、运动视觉、表面方向检测和恢复等问题中边缘也是基本的特征。因此边界检测是图象处理和计算机视觉中的第一个基本的处理步骤一般来说物体的边界具有复杂的形状,难以根据图象中的灰度变化直接找出物体的边界,因此需要把边界分解成一系列的局部边缘。局部边缘是图象中局部灰度级以简单(即单调)的方式作极快变化的小区域。这种局部变化可用一定窗口运算的边缘检测算子来检测。灰度变化的几何形状可以有以下几种 (1)边缘(edge)。边缘两边相邻区域中的灰度相对地均匀,只是在通过边缘时灰度发生突变,理想的情况下边缘的横截面如图4-1(a)所示,实际情况下难免有一些噪声或模糊的影响,这时边缘处的灰度分布就如图4-1(c)所示。 (c)图4.1灰度变化的各种情况(d) (2)直线或曲线的边线。这时除了沿一条很细的带状区域以外,灰度的分布相对地均匀, 在边线的横截面上灰度的分布形成一个尖锐的脉冲,如图4.1(b)所示。值得提出的是边线

75 第四章边缘检测 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)所示。值得提出的是边线 (b) (a) (c) (d)

78 两个响应的商。 ( ) ( ) ( ) SNR G x f x dx n f x dx w w w w = −     − + − +  0  2 1 2 4-3 4.1.2 最优定位准则对定位准则来说，最好定义某种随定位性改善而增加的测量。为此，采用检测出的边缘点与实际边缘点中心之间的均方根距离的倒数作为定位性的测量。因为把图象对 f (x) 算子响应的局部极大点标志为边缘点，所以算子响应的一阶导数在边缘点应为零。同时因为边缘的中央在 x = 0 处，所以在没有噪声时， x = 0 处将是响应的局部最大值。但当有噪声时就不是这样。设： Hn (x) 表示滤波器单独对噪声的响应， HG (x) 是滤波器单独对边缘的响应。假设，滤波器总的响应在 x = x0 处有一个局部的的极大值。那么有 Hn (x0) + HG  (x0) = 0 4-4 如对 HG  (x0 ) 在原点作泰勒级数展开 ( ) (0) (0) ( ) 0 2 HG  x0 = HG  + HG  x0 + o x0 = 4-5 因为在没有噪声时，滤波器的响应在原点处有一个局部的极大值。所以 HG  (0) = 0 ，这样上式中的第一项可略去，如果实际极大值的位移 x0 很小，那么二阶和更高阶的项可被忽略。由方程(4-4)和(4-5)可得： HG (0)x0  −Hn (x0) 或 ( ) ( ) x H x H n G 0 0 0 = −   4-6 其中 Hn  (x0 ) 是一个高斯随机变量，因为它是白色高斯噪声与冲激响应为 f (x) 的滤波器的卷积输出，它的方差 ( )   E H x n  0 2 可表示为： ( )   E H x n f (x) dx n w w  =  − + 0  2 0 2 2 4-7 其中 E y 是 y 的期望。根据(4-6)式，并利用上述结果，可得到 x0 的方差  x0 2 等于   ( ) ( ) ( ) 2 2 2 0 2 0 2 0      −   = =   + − + − w w w w G x f x dx n f x dx  x E x 4-8 定位性定义为  x0 2 的倒数，即 ( ) ( ) ( ) Localization G x f x dx n f x dx w w w w =  −   − + − +  0  2 4-9 (4-3)和(4-9)两式是最优检测和定位准则的数学形式，这样滤波器的设计就简化为这两项同时为最大的问题。为此，我们要使(4-3)和(4-5)的乘积最大，也就是使下式为最大

"o(-)y()algr(+( mov-tw 2(dr nov[+/ 2(do 4.1.3消除多重响应上述检测准则测量了滤波器在原点处区分信号与噪声的有效性,但并未考虑滤波器在边缘中心附近区域的特性。根据积分的许瓦兹不等式可很简单地求得上述两个测量的上限值。根据(4-3)式,SNR的上界为 G2(x)dx 定位性 Localization((4-9)式)的上界为 (x 在[m可]区间中,当f(x)=G(-x)时,SNR和 Localization都达到上界,从而 SR· Localization得到最大值。因此,根据前两个准则,对台阶边缘来说最优的边缘检测算子是差分算子,或截短的台阶算子。但差分算子的频带很宽,当台阶边缘包含噪声时,在输出响应中常会出现很多极大值,这时就会造成严重的问题。根据第一个准则,这些额外的边缘都应被看作错误。但上述准则的解析公式是根据在单个点(即边缘中心)处的响应得出的,并未考虑周围若干点的相互作用。从图4.2(c)可看到差分算子对有噪声的台阶边缘的响应大致是三角形的峰,但在边缘附近有许多很陡的极大值。这些极大值点相互靠得很近,以至难以区分哪个是台阶边缘的响应,哪些是噪声。所以需要限制滤波器在台阶附近的响应,使得检测多于一个边缘的概率很低。理想情况下,我们希望在噪声情况下的响应其峰点之间的距离大致等于边缘检测算子对单个边缘所产生响应的宽度,这个宽度是算子宽度W的若干分之为了把这个准则表示为对滤波器∫(x)的约束,这里需要得到相邻噪声峰点之间距离与 f(x)之间的表达式。不难看出输出中相邻极大点之间的平均距离是算子输出一阶导数中相邻过零点之间距离的2倍,因为输出中的极小点也会产输出一阶导数中的过零点。因此, Canny利用Rice得到的结果:函数g对高斯噪声的响应中过零点之间平均距离是: 其中R()是g的自相关函数 R(0)=Cg2(x)和R"()=_g2(xt 在这里的情况下,所寻找的是函数f’对高期噪声响应中的过零点平均间距X2(0) 4-12 f"(xdx ∫的噪声响应中相邻极大值之间的距离用Xmax表示。Xma(0=2Xx。这个距离可取为算

79 ( ) ( ) ( ) ( ) ( ) ( ) G x f x dx n f x dx G x f x dx n f x dx w w w w w w w w −   −   − + − + − + − +    0  2 0 2 4-10 4.1.3 消除多重响应上述检测准则测量了滤波器在原点处区分信号与噪声的有效性，但并未考虑滤波器在边缘中心附近区域的特性。根据积分的许瓦兹不等式可很简单地求得上述两个测量的上限值。根据(4-3)式，SNR 的上界为： n G (x) dx w w 0 −1 2 − +  定位性 Localization（(4-9)式）的上界为 n G (x) dx w w 0 −1 2 − +   在 −w,w 区间中，当 f (x) = G(−x) 时，SNR 和 Localization 都达到上界，从而 SNR·Localization 得到最大值。因此，根据前两个准则，对台阶边缘来说最优的边缘检测算子是差分算子，或截短的台阶算子。但差分算子的频带很宽，当台阶边缘包含噪声时，在输出响应中常会出现很多极大值，这时就会造成严重的问题。根据第一个准则，这些额外的边缘都应被看作错误。但上述准则的解析公式是根据在单个点（即边缘中心）处的响应得出的，并未考虑周围若干点的相互作用。从图 4.2 (c)可看到差分算子对有噪声的台阶边缘的响应大致是三角形的峰，但在边缘附近有许多很陡的极大值。这些极大值点相互靠得很近，以至难以区分哪个是台阶边缘的响应，哪些是噪声。所以需要限制滤波器在台阶附近的响应，使得检测多于一个边缘的概率很低。理想情况下，我们希望在噪声情况下的响应其峰点之间的距离大致等于边缘检测算子对单个边缘所产生响应的宽度，这个宽度是算子宽度 W 的若干分之一。为了把这个准则表示为对滤波器 f (x) 的约束，这里需要得到相邻噪声峰点之间距离与 f (x) 之间的表达式。不难看出输出中相邻极大点之间的平均距离是算子输出一阶导数中相邻过零点之间距离的２倍，因为输出中的极小点也会产输出一阶导数中的过零点。因此， Canny 利用 Rice 得到的结果：函数 g 对高斯噪声的响应中过零点之间平均距离是： ( ) ( ) X R R ave = −         0 0 1 2 4-11 其中 R(c) 是 g 的自相关函数。 R(0) g (x)dx 2 = −   和 ( ) =  ( ) −  R 0  g x dx 2 在这里的情况下，所寻找的是函数 f  对高期噪声响应中的过零点平均间距 Xzc ( f ) ( ) ( ) ( ) 2 1 2 2 '            =    −  − f x dx f x dx X f zc  4-12 f 的噪声响应中相邻极大值之间的距离用 X max 表示。 Xmax( f ) = 2Xzc 。这个距离可取为算

80 子宽度的某个分数 K。这被认为是多重响应约束。 Xmax ( f ) = 2Xzc ( f ) = KW 4-13 这个约束是很自然的，因为滤波器的响应将集中在宽度 2W 的区域中。在此区域中噪声极大值个数的期望为 N W X K n = = 2 2 max 4-14 确定了 K ，就是确定了在此范围内可导致错误响应的噪声极大值的数量。至于这些噪声极大值造成错误检测的可能性大小，还要取决于信噪比的大小。为减少错误检测，在信噪比小时，应使 Nn 更少些，即选 K 大些。选定 K 以后，如何按（4-12）式求得 f (x) 的问题将在下一节中介绍。这里需要指出的是（4-12）式所表示的极大值之间的间距与算子的宽度成正比。对这点可这样来说明：假设我们先定义一个算子 f ，它是 f 延伸  倍的结果，即 f (x) f( ) x   = 。然后把它代入（4-12）式。可以发现对 f 来说，极大值之间的间距是 Xzc ( f) = Xzc ( f ) 4-15 因此，如果在某个 K 值条件下， f 满足多重响应约束（4-13）式，并假设， w 与  成比例，那么函数 f 也满足（4-13）。所以对任何固定的 K ，相对于 f 的空间比例来说，多重响应准则具有恒常性。 4.2 一维台阶边缘的检测一般来说很难找到符合多重响应约束，并使（4-10）式极大的函数 f 。甚至当 G 是很简单的形式（例如，是台阶边缘）时， f 仍然是很复杂的。但在离散的情况下可以用数字化方法来求解。以下用 G(x) 输入是台阶边缘的情况来说明求解的方法。我们取 G(x) = Au−1(x) ，其中 un (x) 是  函数（delta 函数）的第 n 阶导数， A 是边缘台阶的幅度。这就是 u (x) x x − =      1 0 0 1 0 4-16 用 u−1(x) 置换（4-3），（4-9）中的 G(x) ，则得 ( ) ( ) SNR A f x dx n f x dx W W W = − − +   0 0 2 4-17 ( ) n f (x)dx A f Localization W  W + −   = 2 0 0 4-18 由上述两公式可见，这两项准则都可直接通过提高 A n0 而得到改变。 A n0 可被看作是图象的信／噪比。现在我们去除这些与图象有关的部分，并定义两个性能测量  和  ，它们只与滤波器本身有关

SMR=∑()∑( o r(=e)dr 4-19 f2(x)dx Localisation==Auu) I(o f(xds 以下我们先分析一下滤波器的宽度,或空间比例,对∑()和A()的影响。假设我们从产生一个与f成空间比例的滤波器m,fm=/(%)前面已证明了多重响应准则不受空间比例的影响。当把f代入(4-19)和(4-20)时可得到空间比例滤波器的性能测量为 ∑()=V0∑()^(a)=-=入( 4-21 这两个公式中的第一个公式的含义比较直观。即,用于台阶边缘时,冲激响应函数较宽的滤波器的信/噪比要比冲激响应函数较窄的高。因为∑()与√o成正比。第二个公式表明较窄的滤波器比宽的滤波器有较好的定位性。因为A(fa)与√成反比。这就是存在于台阶边缘检测算子的检测性能与定位性能之间的不确定性原理。通过对∫在空间上作比例变换,我们可在检测特性和定位性之间作综合平衡,但我们不能同时改善这两者。这意味着把综合准则选择为(4-19)和(4-20)的乘积是很自然的。因为这个准则在比例变化时保持不变。 ∑()^(f)= ow /(x)dr (o) f"()dr 现在求解f(x)的问题就变成了根据(4-22)式寻找f使∑()^()极大的问题。式(4-22) 中有四项积分,难以直接用变分法求解。为此, Canny把(4-22)式的极大值问题演绎成在使其余3项积分保持不变的条件下,使SNR项分母中的积分f2(x)极小的问题,即求解使下述积分极小的函数f(x) 与此同时要求满足下述约束条件: ouf()dx=Ci, Lwf2(x)dx=C2 (4-24) ow"()dx=C3,/'(o) 利用拉格朗日( Lagrange)乘子法首先生成一个复合函数vx,f,f,f"),这个函数是出现在要求极小化的表达式和约束条件中的函数的线性组合。求解v(x,f,f,)的无约束极大值等价于求解原来的约束条件下的极大值。这时就可以按变分法,用欧拉( Euler)方程求解∫(x),求得在[HQ范围内的通解形式为 f() +a2e cos ax +aze-an 这个函数满足下述边界条件: f0)=0,f(-H)=0.f(o)=S,f(-1)=0

81 ( ) ( ) ( ) ( ) SNR A n f f f x dx f x dx W W W =   =   − − + 0 0 2 , 4-19 ( ) ( ) f (x)dx f f f n A Localization W  W + − =     = '2 0 '(0) , 4-20 以下我们先分析一下滤波器的宽度，或空间比例，对 ( f ) 和 ( f ) 的影响。假设我们从 f 产生一个与 f 成空间比例的滤波器 f， f f( ) x   = 前面已证明了多重响应准则不受空间比例的影响。当把 f 代入（4-19）和（4-20）时可得到空间比例滤波器的性能测量为 ( f)  ( f ) ( f) ( f )   =  ,   =   1 4-21 这两个公式中的第一个公式的含义比较直观。即，用于台阶边缘时，冲激响应函数较宽的滤波器的信／噪比要比冲激响应函数较窄的高。因为 ( f) 与  成正比。第二个公式表明较窄的滤波器比宽的滤波器有较好的定位性。因为 ( f  ) 与  成反比。这就是存在于台阶边缘检测算子的检测性能与定位性能之间的不确定性原理。通过对 f 在空间上作比例变换，我们可在检测特性和定位性之间作综合平衡，但我们不能同时改善这两者。这意味着把综合准则选择为（4-19）和（4-20）的乘积是很自然的。因为这个准则在比例变化时保持不变。 ( ) ( ) ( ) ( ) ( ) ( ) f f f x dx f x dx f f x dx W W W W W   =        − − − 0 2 2 0 4-22 现在求解 f (x) 的问题就变成了根据（4-22）式寻找f使 ( f )( f ) 极大的问题。式（4-22）中有四项积分，难以直接用变分法求解。为此，Canny 把（4-22）式的极大值问题演绎成在使其余３项积分保持不变的条件下，使 SNR 项分母中的积分 f (x)dx W 0 2 −  极小的问题，即求解使下述积分极小的函数 f (x) f (x)dx W 0 2 −  (4-23) 与此同时要求满足下述约束条件： ( ) ( ) ( ) ( ) f x dx C f x dx C f x dx C f C W W W − − −    =  =  =  = 0 1 0 2 2 0 2 3 0 4 , , (4-24) 利用拉格朗日（Lagrange）乘子法首先生成一个复合函数 (x, f , f  , f ) ，这个函数是出现在要求极小化的表达式和约束条件中的函数的线性组合。求解 (x, f , f  , f ) 的无约束极大值等价于求解原来的约束条件下的极大值。这时就可以按变分法，用欧拉（Euler）方程求解 f (x) ，求得在 −W, 0 范围内的通解形式为 f (x) a e x a e x a e x a e x C x x x x = + + + + − − 1 2 3 4         sin cos sin cos 4-25 这个函数满足下述边界条件： f(0) = 0, f(−W) = 0, f (0) = S, f (−W) = 0

82 其中 s 是未知常数，它等于函数 f 在原点处的斜率。因为 f (x) 是反对称的，可利用 f (−x) = − f (x) 把上述定义扩展到 −W, W 的范围，利用上述边界条件来求解 a1 a2 a3 a4 , , , 。这样函数 f 是由参数 ,, 和 c 来表示。现在仍需寻找能使综合准则积分的商最大的这些参数。经过上述推导，Canny 把这个在无限维空间中的函数优化问题演绎为一个在变量 , 和  （ c 只是附加常数，与复合准则无关）中非线性优化问题。遗憾的是得到的结果（它还要满足多重响应的约束）过于复杂，不可能求得解析形式的解。因此，最后的解不得不以数值计算的方法来求得。 f 的形状取决于多重响应约束，即它将取决于我们要强迫相邻的响应离得多远。图 4-3 中所示为在选择不同间距时 f 的形状。前面已经提到过对任意的  不存在单个的最优函数，而是一类函数。这类函数是通过以  对典型函数作比例运算求得。当图象中信／噪比较低时，我们就希望使响应的极大点能相互远离。但不太清楚对单个算子来说，合适的信／噪化应是多大。所以在应用这个算子时应使用若干不同宽度的算子，并有一个决策过程来从中选择一个宽度最小，但其输出中的信／噪比仍高于阈值的算子。我们试图选择一个间距，使得在此间距下多重响应的误差与由于阈值引起的误差可相比拟。在假设噪声的概率密度分布是高斯函数的条件下，根据检测的错误率与多重响应错误率相等的条件，可求得 ( ) =  f S 0  4-26 其中  是确定的、允许的、信噪比的阈值，  S ( ) W W = f  x dx −  2 。不过实际上不可能找到满足上述条件的滤波器，所以改为要求满足下述条件 ( ) =  f r S 0  4-27 其中要求尽可能接近于 1。图 4-4 中所示为具有不同参数的几个滤波器的性能指标

84 f (x) x x = − −           2 2 2 2 exp 可以证明，这时的  = = = =  8 3 4 15 0 92 0 51  . r . 与原来的滤波器 6 的特性相比，  特性下降大约 20%，多重响应大约下降了 10%。在用于实际的图象时，这样的特性下降是难以分辨的，因此是可以接受的。这样的近似带来的优点是不但简化了计算，而且在二维的情下计算要方便得多。 4.3 二维或高维的边缘检测在一维时，我们可以用一维坐标来说明台阶边缘在空间中的位置。在二维图象时，还要说明边缘的方向。我们把边缘定义为二维空间中边缘轮廓的切线方向。设与边缘垂直的方向为  n 。在一阶情况下 Canny 算子可以用高斯函数的一阶微分算子来近似，那么在二维时就应用二维高斯函数沿某个方向  n 的一阶方向导数 Gn 来近似，也就是说 G x y = −  +        exp 2 2 2 2 G G n n G G G x i G y j n = =   = +          , 4-28 因为  n 是予先不知道的方向，所以可用梯度方向来估计，即 ( ) ( )  n G I G I =     4-29 边缘点可由 Gn 算子与图象 I 卷积后所得图象中的局部最大点来确定。这个局部最大点可根据方向导数为零来求，即   n G I n * = 0 4-30 把 G G n n =   代入上式，得   2 2 0 n G * I = 4-31 在这些边缘点，边缘强度将等于 Gn  I = (G * I) 4-32 由（4-31）式，根据卷积与微分的结合律，可先用对称的高斯函数作卷积，然后由寻找二阶方向导数的零点来确定边缘的位置，并可用式（4-32）来估计边缘的强度。这与用方向算子 Gn 来检测和定位边缘点等价，但在卷积以前并不需要知道方向。把这样的二阶方向导数算子的性能与 Laplacian 算子的性能作一比较是有益的。二维的 Laplacian 可分解成在任意二个垂直方向上的分量。如果把梯度方向取为其中的一个方向，那么这时 Laplacian 算子的一个分量的作用与上述二阶方向导数算子的作用相同，而另一个

《计算机视觉》课程教学资源（教材）第四章 边缘检测

《计算机视觉》课程教学资源（教材）第四章边缘检测