《图像压缩编码方法》课件第6章

第6章分形编码提取图像边缘6.1引言6.2图像边缘的提取方法6.3分形维数应用图像边缘的提取6.4基于局部IFS理论提取图像边缘6.5实验结果

6.1引言

图像边缘提取是图像处理、理解和分析的重要技术，同样在图像编码中起到关键作用；如果对静态图像压缩分析，就会发现，无论任何编码方法，在高压缩比时，图像失真最大的是边缘。视觉生理和心理学的研究表明，边缘信息对图像的感知及主观质量具有重要的作用。这些信息的严重失真必然造成整体图像质量严重恶化。由此可见，为了获得高的压缩比，必须对图像边缘信息的提取、表征与编码予以足够的重视。在图像的研究和应用中，人们往往对图像中的某些部分感兴趣。这些部分常为目标，它们一般是对应图像中特定的、具有独特性质的区域，对这些区域编码效率的提高，就是基于人视觉的分辨率。这些区域的区分也是基于图像的边缘的提取来划分的。因此，近年来，图像边缘的提取在图像压缩编码中起着越来越重要的作用，如近几年来出台的国际标准MPEG-IV中的模型基/目标基就是一个非常好的验证例子，它就是基于图像边缘的提取为出发点的。

边缘是图像最基本的特征。边缘提取在计算机视觉、图像分析等应用中起着重要的作用，是图像分析与识别的重要环节，这是因为图像的边缘包含了用于识别的有用信息，所以边缘提取是图像分析和模式识别的主要特征提取手段。所谓边缘是指其周围像素灰度有阶梯变化或屋顶变化的那些像素的集合，它存在于目标与背景、目标与目标、区域与区域、基元与基元之间。它是图像分割所依赖的重要的特征，也是纹理特征的重要信息源和形状特征的基础；图像的纹理形状特征的提取又常常依赖于图像分割。图像的边缘提取也是图像匹配的基础，因为它是位置的标志，对灰度的变化不敏感，它可作为匹配的特征。

图像的其他特征都是由边缘和区域这些基本特征推导出来的。边缘具有方向和幅度两个变化。沿边缘走向，像素值变化比较平缓；而垂直于边缘走向，则像素值变化比较剧烈，这种剧烈呈现阶跃状，也可能呈现斜坡状。边缘上像素值的一阶导数较大；二阶导数在边缘处值为零，呈现零交叉。经典的最简单的边缘检测方法是对原始图像按像素的某邻域构造边缘算子。由于原始图像往往含有噪声，而边缘和噪声在空间域表现为灰度有比较大的起落；在频域则反应为同是高频分量，这就给边缘检测带来困难。

Marr和Hildrth提出的零交叉边缘检测是一种十分有效的方法，他们认为。其一，图像强度的突变将在一阶导数中产生一个峰或等价于二阶导数中产生一个零交叉(zero-crossing)；其二，图像中的强度变化是以不同的尺度出现的，故该应用若干大小不同的算子，才能取得良好的检测效果。 6.2图像边缘的提取方法

1.梯度法

比较经典的边缘算子首推梯度法(一次差分法)，其思想是利用一阶微分算子计算各像素灰度的空间导数给出微分锐化图像。当所计算得到的梯度方向模的量值超过某个门限时，就认为存在一个边缘像束。最常用的有罗伯特交叉(Robertcross)算子，它的两个2×2模板(见图6.1(a))；还有浦瑞特(Prewitt)和索贝尔(Sobel)算子，它们都用两个3×3模板(分别见图6.1(b)、(c))。图6.1几种常用梯度算子的模板

2.曲面拟合法

在这类方法中，用一个解析函数来逼近灰度外形，然后将这个解析函数用于计算导数或理想边缘的最佳拟合，比较著名的有Huekel算子和Haralick面模型算子。

Huekel算子的基本是灰度表面用径向Fourier级数的前9个系数来逼近。对参数化的理想边缘计算这些系数，并确定给出最佳拟合边缘的参数。若量值超过某个门限，则认为检测到一条边缘。该门限与理想边缘或与逼近灰度形状之间的拟合程度有关。

Haralick面模型算子是把邻域内图像灰度值用二维离散正交多项式集来逼近。首先，由选定的窗口大小和多项式的线形组合来进行计算。一旦完成了多项式逼近的计算，我们就有了表示图像的解析函数，于是可用解析方法来计算导数。Haralick选择了二阶方向导数，这时图像中的边缘形成二阶导数的“零交叉”，零值像束即为边缘。

用曲面来对图像进行最佳拟合，然后在曲面上进行边缘检测，然而这些都是基于以下假设的：平滑后的曲面与原图像具有相同的凹凸性(方向性)。在实际应用中，逼近程度的函数性能及开窗大小都直接影响到边缘检测效果。这种方法的结果并未达到理想的程度，在抗干扰和检测出复杂形状的边缘之间仍存在着尖锐的矛盾，在平滑窗大小的选择上也没有很好地解决。

3.模板匹配

模板匹配是将理想边缘“模板”与图像进行卷积，在图像和模板相似的地方将出现高输出。它利用理想的微小边缘区域构成边缘板，探测图像中各个像素与样板的匹配程度，给出边缘图像，如Nevation和Babu给出方向模板，可以检测出不同方向上的边缘。

这种方法不但直观而且容易实现，并且有一定抑制噪声的性能和定位比较精确的功能，但是计算量比较大。另一方面对于大图像库，提取库中所有图像的边缘是个艰巨的任务。由于每幅图像都有自己特定的目标和背景，必然不可能有固定的阈值。用此方法有些图像很可能将某些假边缘也提取出来，而有些目标和背景之间灰度变化较小的图像则取不到目标边缘，即漏取边缘。

4.二阶导数法

图像的二阶导数在边缘处为零，在边缘的两边侧各有一正一负两个峰。因此，可用局部零交叉来作边缘检测。

拉普拉斯算子是一种二阶导数算子，是无方向性的算子，它比前述一阶算子计算多个方向导数算子的计算量小，因为只需用一个模板，且不必综合各模板的值。对图像中的噪声相当敏感，另外它常产生双像素宽的边缘，且也不能提供边缘方向的信息。不适合于精确定位，而利用二阶差分算子的过零点可以精确定位。因此，后人在此基础上提出保持优点、克服不足的改进方法。马尔(Marr-Hildreth)提出：适用的算子为拉普拉斯-高斯算子(LOG)，其中，先用高斯函数起平滑作用，减少噪声影响，然后运用拉普拉斯算子确定边缘的位置，但是高斯函数与图像卷积会模糊图像，并且其模糊程度正比于高斯函数的方差。在该算子中，高斯函数的方差是非常重要的。在实际处理过程中，LOG算子遇到了许多问题，零交叉检测器本质上是一个二阶微分算子，不可避免地放大噪声，因此在有噪声的情况下是不稳定的。此外，高斯滤波的零交叉点不一定全部是边缘点，还需要进一步对其真伪进行确认。一般来说，LOG算子滤波器的噪声平滑能力与边缘定位能力是矛盾的，为了获得好的噪声抑制效果，必须采用较平坦的高斯函数，但是大的方差高斯函数又使得边缘位置发生严重偏移，而且，高斯函数的方差增大会带来运算量的增加，从而造成实用性的降低。

5.基于图像整体线索法

边缘往往包含着图像中的重要信息，因此边缘提取是对图像的识别和理解至关重要的。早期的边缘检测采用微分算子的方法，然而这种仅使用了局部信息的方法根本无法处理含有噪声、低对比度、模糊化的图像。经过研究，许多学者认为好的边缘提取方法应该既利用局部信息，又使用整体特征。启发式搜索的方法是利用幅度、相位、曲率等局部和整体信息并结合估计的图像边缘的位置得到一个代价函数。在边缘搜索过程中使用代价最小来引导、优化。这种方法存在许多问题，第一，仅进行依次搜索，这要求每一步搜索必须绝对正确和最优，一旦搜索错误无法修正，就使得搜索很难在高噪声图像进行；第二，需要提前对边缘位置进行估计，当遇到复杂图像时，估计很难准确，会出现断点和漏搜索的边缘。松弛标记的方法是从边缘增强的方向出发的，它使用边缘点的幅度、梯度矢量、曲率等信息，来初始化松弛网络像素的标记，根据边缘曲线上的点的局部具有一致性和相关性，而噪声的信息是随机的、无规律的特点，进行邻域点信息的相互作用，增强有规律的边缘信息，同时削弱无规律的噪声，但这种方法也存在一些难以克服的问题。它对边缘的增强是使用固定点的领域进行的、相互独立的不同边缘无法被区分增强，易于产生干扰。

6.变换域法

随着变换技术的发展，有一类较新的边缘算子应运而生，它们主要基于Hough和形状变换来提取边缘。

Hough变换是由PoulHough在1962年提出的，是实现图像边缘检测的一种有效的方法。计算量足够大，需要巨大的存储空间，难以实现边缘定位和不能区分共线段等。针对Hough变换存在的缺点，人们在图像处理和计算机中经常利用图像全局特性而提取图像中的目标边缘信息。Hough变换实现的是一种从图像空间到参数空间的映射关系，它将图像空间中复杂的边缘特征信息转化为参数空间中的聚类检测问题。这使Hough变换具有明了的几何解析性、一定的抗干扰能力和易于实现并行处理等优点。另一方面，它也存在着人们相继提出了一些改进的方法，如采用四叉树结构的快速Hough变换、以梯度信息为引导的边缘算法，它们的优劣亦众说纷纭，Shao对一些有关算法有一Hough变换、分层Hough变换、采用聚焦算法的Hough变换、自适应Hough变换和图像空间和参数的多分辨率Hough变换等作了归纳性的总结。初步总结如表6.1所示。表6.1各种提取图像边缘算子的性能对比 6.3分形维数应用图像边缘的提取

1.图像区域的DFBR场模型

1)分数布朗随机场

Mandelbort首先提出用分数布朗运动描述具有统计自相似性的一类随机过程，将分数布朗运动用于描述空间分布的随机场，得到分数布朗随机场(FractionalBrownianrandfield，FBRF)。有关概率简述如下：

定义一：设H满足0<H<1，b0为任意实数，若随机函数满足

则称BH(t，ω)为分布布朗运动(FBM)，H为分形参数，b0为初始值，ω为样本空间Ω，当 时，分数布朗随机场就为通常的布朗运动。(6-1)定义二：设BH(t)为一个高斯随机场，对于0<H<1，若对任意t和Δt，满足

则称BH(t)为各向同性的FBRF。式中F(y)为零均值高斯随机变量的分布函数，Pr(·)为概率测度，‖·‖表示范数，H为Hurst分形指数。(6-2)定义三：若t和Δt取离散值为n和m，则称c(n，m)=BH(n)－BH(n－m)为离散分数布朗随机场(DFBR场)。

由上述定义可知，分数布朗随机场是非平稳的，对应的离散增量(DFBR场)具有统计平稳自相似性，即DFBR场满足

E{|BH(n+m)－BH(n)|}=E{|BH(n+1)－BH(n)|}·||m||H

(6-3) E{|BH(n+m)－BH(n)|2}=E{|BH(n+1)－BH(n)|2}·||m||2H (6-4)

可见DFBR场的一、二阶绝对矩具有各向同性。

DFBR场模型是描述自然景物自相似性的一种有效模型,其局部统计特性能有效地吻合图像区域的局部统计特性。因此，用DFBR场模型作为描述图像区域的数学模型，H参数能够表征同一图像区域的自相似性(即灰度面的均匀程度)，则对应的图像区域灰度表面的分形维数D可由H参数获得：

D=DT+1－H (6-5)

其中DT为图像表面的拓扑维数。一般DT=2为图像区域的拓扑维数。

2)图像的H参数定义

设图像区域的灰度面满足DFBR场模型，I(x0，y0)表示图像中(x0，y0)处的灰度值，由DFBR场模型的性质得

E{|I(x2，y2)－I(x0，y0)|}=E{|I(x1，y1)－I(x0，y0)|}ΔrH (6-6)

其中，(6-7)H参数的估计分为时域估计和频域估计法，但频域估计法需要数量大，计算量也较大，实时实现较困难，因此，实际中常用时域法。ΔI(r)=|I(x，y)－I(x0，y0)|，式(6-6)、式(6-7)只能二者选一。

E{ΔI(r)n}=E{ΔI(1)2}·rnH，n=1，2 (6-8)

由DFBR场模型的定义及性质可知：DFBR场为平稳过程，满足DFBR场一、二阶绝对矩的历经性，则(6-9)

式中，Nr为点(x，y)到点(x0，y0)之间距离r的像素点总数。

通过线性最小二乘法数据点对{log(E|ΔI|)n，log|r|}，由拟合直线的斜率即可求出H。(6-11)(6-10)

2.图像边缘的分形检测

当图像相同的区域与DFBR场相吻合时，H值就会满足0<H<1。若图像中存在不同的区域时，则在求取图像表面的H参数值时，会出现H>1的情况。H>1意味着图像表面的分形维数小于图像表面的拓扑维数，但这是不可能的。其原因在于不同区域的交界处，破坏了DFBR场的一致性，因而也再不满足各向同性的条件，即不再满足DFBR场模型，故求出的H参数会发生奇异。换句话说，H参数发生奇异的位置说明了图像中不同区域边缘的存在，因此，可以采用分形维数的方法，通过图像表面的分形维数来检测图像边缘。

1)H参数的估计

采用DFBR场模型估算局部范围的分形维数，需要逐点计算其分形维数。为了简化计算，以图像中任一点(x0，y0)为中心，设7×7的矩形窗口，如图6.2所示。从(x0，y0)点开始，按公式(6-11)通过线性最小二乘法的数据对来估计分形维数。当r=2和r=3时，则拟合直线的斜率为H。然后沿着水平方向和垂直方向逐点移动窗口。图6.2估计分形维数的窗口

2)边缘检测准则

由图像区域的DFBR场模型假设及H的估算方法可知：当(x0，y0)位于区域内部时，分形参数估计应在0与1之间，即0<H<1，而局部分形维数D则介于2～3之间，若(x0，y0)位于图像区域的边缘处，分形参数估算将超出其理论范围(0，1)，即H<0或H>1。因此，相应的边缘检测准则可定义为：

亦即，当0<H<1时，(x0，y0)为非边缘，对应边缘影像像素取值为0，当H<0或H>1时，(x0，y0)为边缘，对应边缘影像像素取值为1。(6-12)

3)实验结果与讨论

利用上述算法，进行图像边缘提取，检测结果如图6.3所示，由此可见，分形维数在图像边缘检测中对噪声不敏感，能有效地提取图像边缘，好于经典的方法检测边缘；但是，在应用时，该算法计算量大，H>1提取的边缘较粗，局部维数的窗口大小与抗干扰能力和提取图像细节是相互制约的，如何选择最优的窗口，甚至边缘点维数值如何选取，有待以后研究和完善。图6.3图像提取边缘方法 6.4基于局部IFS理论提取图像边缘

1.理论分析

在IFS理论应用图像压缩中，通常还会对压缩的结果进行分析，以进一步改进压缩方法来提高压缩效果。在分析该方法的图像压缩效果中，发现了图像的失真与图像边缘存在很大的关系，从而推导出分形IFS理论在图像边缘提取的方法。因此，从分析IFS理论压缩图像中得到了其提取图像边缘的依据。

分形图像编码的性能取决于Rang块与Domain块的相似程度。Jacquin根据Range块和Domain块几何形状特点，把它们分为三大类：阴影块(Shade)、中值块(Midrange)和边缘块(Edge)。阴影块是平滑的，没有显著的梯度变化。中值块是指有中等的梯度变化，但没有确定的边界，假定它近似是各向同性的，并无特定优先的取向，精细纹理方块亦属于这一类。边缘块是沿着一条曲线其周围的灰度值有强烈的变化，一般是对象的边缘部分。图像完全由不重叠的Range块覆盖的，而且这三大类的Range块交为空集。对分形图像压缩分析后发现，不管Range块大小，分形图像压缩有一普遍的特点：阴影块的仿射变换效果最好，即失真度最小，寻找最佳匹配的Domain块需要的时间最短；边缘块的仿射变换效果最差，即失真度最大，而且寻找最佳匹配的Domain块时间最长；中值块在仿射变换的效果和寻找最佳匹配的Domain块介于它们之间。因此，根据这一特点，我们认为：若以MSE作为Range块与Domain块的相似性失真测度时，MSE的数值大小反映了边缘的强弱，即可以用该值的大小作为是否含有边缘块的依据。从分形维数来解释，这与分形维数提取边缘的理论相吻合，Pentlant证明了自然界中的大多数物体表面是空间各向同性的分形表面。由此说明，阴影块和中值块满足DFBR场的一致性，图像区域表面具有统计意义上的自相似性，比较容易找到最佳匹配的Domain块；而边缘块，存在不同纹理交界面，破坏了DFBR场的一致性，分形维数发生了奇异变化，超出它的正常取值范围，而发生奇异的位置即表明不同纹理的边缘信息，故边缘块难以找到失真度小于某阈值的Domain块，因为它们的相似性遇到了破坏。从IFS理论角度来讲，即使边缘块的Range块遇到一个类似形状的Domain块，但它们失真度也是非常大的。这是由两方面原因造成的：一方面，在仿射变换中平均抽样操作把Domain块的突变信息消除了一些，造成了Domain块中的边缘信息减弱；另一方面，在寻找最佳匹配的Domain块中，压缩因子pi，0起到了一个平滑作用，把Domain块的边缘部分进一步模糊化。因此，对于边缘块的Range块难以寻找到小于某一阈值失真度的Domain块。由此可见，虽然分形IFS理论与分形维数提取边缘的形式各不相同，但是根本思想是统一的——相似性。因此用分形维数理论也可以解释IFS理论提取边缘的方法思想。

2.基于IFS理论提取边缘方法

我们检测图像边缘，以最小二乘法作为求解Range块Ri与最佳匹配Domain块Dj的参数方法，以均方误差为测量它们之间的失真度，它的数值大小反映了边缘的强弱，当计算的失真度值越大时，对应的边缘块越强，否则，对应的边缘块越弱。设定一个阈值，是来区分边缘块的界限；与最佳匹配Domain块Dj的失真度大于阈值的Range块Ri，被划为边缘块。分形在图像边缘提取中的一般具体步骤为：

(1)将图像分成大小为2i×2i且互不重叠的子块，这些子块被称为rangeblock(R)；

(2)对于每一个R，在原图像中寻找一个大小为2i+1×2i+1的父块domainblock(D)，D经过空间变换和灰度值仿射变换后，与R的平方误差达到最小值d(最小二乘法求d)，通常空间变换包括图像块空间压缩(一般指四邻域平均)和图像块空间变换(一般8个旋转或反射变换)；

(3)对于每一个R，在搜索寻找最佳匹配的父块D时，若一旦d小于阈值，则停止搜索，立即进行下一个R，若R与最佳匹配D的失真度dmin大于阈值时，则记录R的地址；

(4)把失真度dmin大于阈值的子块R变成边缘测度空间，采用零交叉法进一步提取图像的边缘。

(5)二值化处理后得到图像的边缘。提取图像边缘方法是借鉴于分形图像压缩的方法——基于IFS理论提取图像边缘。Barnsley提出的分形图像编码之所以能够压缩数据，是因为自相似性普遍存在于图像之中，分形图像编码是利用仿射变换来消除图像中的自相似冗余而实现数据压缩的。但是分形图像编码需要花费很长的编码时间，主要集中在寻找最佳匹配的过程。为了减小最佳的匹配搜索的范围，从全局搜索变为区域搜索，从而达到降低编码时间的目的。大量的统计实验表明：对于给定位置的Range块Ri，搜索到其最佳匹配自相似的Domain块Dj位置的概率几乎都集中在Ri的附近。因此把搜索范围限制在Ri附近区域。用IFS理论提取图像边缘的目的是找出边缘块的Range块Ri来，而边缘的定义是指其周围像素灰度有阶梯变化或屋顶变化的那些像素的集合，更没必要将一个Range块Ri来寻找最佳匹配的Domain块的范围扩大到全局，只需要在Range块Ri的附近区域寻找，这样，就能保证寻找出与周围Domain块不相似的边缘块的Range块Ri(此块与周围区域有突变)，也符合边缘的定义。

提取图像边缘采用IFS理论压缩图像方法，可借鉴分形压缩的改进方法。为了加快分形编码的速度，常用的有自适应的四叉树法。利用四叉树法，可以提取边缘在空间的分辨率由“由粗到细”逐步地精确定位原始图像边缘。在大的Range块寻找最佳匹配的Domain块过程，可以抑制噪声，剔除图像伪边缘，迅速锁定含有边缘的Range块，然后逐步缩小搜索含有边缘的范围。对于含有边缘的Range块，无法获得最佳匹配的Domain块，则要将该块一分为四，再进行分形匹配，抛弃无边缘的Range块，保留含有边缘的Range块，逐渐地缩小含有边缘的范围，提高提取边缘的效率。既要考虑边缘提取的精确位置，要求含边缘的Range块越小越好，但不能出现假边缘，又要考虑方法的抗干扰能力，要求含边缘的Range块越大越好，但不漏掉真边缘。但是，如果开始分形编码时，采用过大的Range块，就会遗漏含有边缘的Range块，这是由于边缘点数占到Range块的总像素比例过小，几乎被平滑区域所淹没了，又由于它的匹配的失真度对总失真度占得份额太小，不足够引起匹配的失真度大于某阈值的Range块，误被判为没有边缘的Range块。若开始采用过小的Range块，虽然能精确锁定含有边缘的Range块，但是抗干扰能力下降，就会产生伪边缘。一般而言，Range块取得越小，边缘的局部化性能越好，反之，检测出的边缘越粗。因此，采用四叉树的分形编码提取图像边缘方法，开始时采用适当大的Range块。一般情况，最大的Range块边长为32，最小的为4。

3.平抑白噪声

白噪声是孤立的、不相关的干扰信号。由于众多原因，图像不可避免地常常受到随机噪声的干扰。采用分形编码方法提取图像边缘，不仅不会像微分算子那样加强白噪声，而且在一定范围内起到平抑白噪声的作用。虽然边缘和白噪声都是高频信号，但是它们有本质的区别，边缘不是孤立的，而是连续的。用分形维数术语来讲，白噪声可以看作分数布朗运动，具有统计自相似的一类随机信号，分形维数是有一致性的；而边缘破坏分形的一致性，分形维数发生奇异，就没有统计自相似。在理论上，白噪声不会影响采用分形编码方法的边缘提取。实际上，大的Range块和其最佳匹配的Domain块，都有相同的DFBR场的一致性，它们的噪声可以相互抵消掉，噪声造成的总失真度很小，抗噪声能力加强。当然，过大的Range块，可以加大漏掉边缘的几率。过小的Range块，增加了区分白噪声和边缘的难度，不能用分形维数解释，难以抵消白噪声引起的失真，会产生伪边缘。采用四叉树法，逐渐减弱白噪声的影响。从计算角度来看，求解的Domain块仿射变换的压缩因子和亮度偏移量的方法，采用最小二乘法，从本质上讲，就是一种消除噪声影响能力的比较有效方法。

4.改进算法的具体步骤

为了有效、准确和迅速地检测图像边缘，采用自适应四叉树法和邻近搜索法结合的思想，来提高工作效率。设ε为一个分形编码中的阈值，2Rmax、2Rmin分别为子块的最大边长和最小边长，邻近搜索范围区域为2L×2L，它以匹配子块为中心，其步骤如下：

(1)原始图像A，分割成不相交的2Rmax×2Rmax的子块Ri作为初始的分割，R的左上角位于(k，l)的位置上。

(2)搜索子块Ri的最佳匹配父块Dj，以Ri位置为中心，在2L×2L范围内寻找Ri的最佳匹配父块Dj。

(3)在搜索过程中，若它们的失真度小于ε，则停止寻找其最佳匹配父块。若最佳匹配父块