数字半色调技术中的误差扩散算法的研究.docx

数字半色调技术中的误差扩散算法的研究.docx

《数字半色调技术中的误差扩散算法的研究.docx》由会员分享，可在线阅读，更多相关《数字半色调技术中的误差扩散算法的研究.docx（14页珍藏版）》请在冰点文库上搜索。

数字半色调技术中的误差扩散算法的研究

数字半色调技术中的误差扩散算法的研究

作者：

张寒冰袁昕

来源：

《计算机应用》2010年第04期

        摘要:

误差扩散是一种非常优秀的调频半色调技术,但这种方法在图像高光和暗调以及阶调平滑区域会产生“蠕虫”,同时噪声较多,导致半色调图像的边缘不清晰。

在Floyd和Steinberg的误差扩散算法的基础上,设计一种新的基于平均阈值和改变扫描路径的误差扩散算法——阈值采用平均值法,通过优化平均阈值方法中的γ值得到最优的半色调图像,同时扫描路径采用“蛇型”路径。

实验结果表明该算法可以减少“蠕虫”,增强图像的边缘,提高半色调图像的主观视觉效果。

        关键词:

数字半色调;误差扩散;动态阈值;扫描顺序

        中图分类号:

TP391.4

        文献标志码:

A

        Studyonerrordiffusionalgorithmofdigitalhalftoning

        ZHANGHan-bing1,2,YUANXin3

        （

        1.CollegeofComputerScienceandTechnology,ZhejiangUniversity,HangzhouZhejiang325011,China;

        2.DepartmentofEngineeringTechnology,ZhejiangDongfangVocationalandTechnologicalCollege,WenzhouZhejiang325011,China;

        3.InstituteofArtificialIntelligence,ZhejiangUniversity,HangzhouZhejiang310027,China

        ）

        Abstract:

        TheerrordiffusionalgorithmperformswellasoneofFrequencyModulation（FM）halftoningmethods,exceptfortendingtoproducingwormartifactsonhighlightareasandgeneratingnoiseswhichblurtheedgeofimages.Anewerrordiffusionalgorithmbasedontheaveragethresholdwasproposedbychangingscanningorder.Usingadaptivethresholdbasedonspatialextension,thehalftoningimageswerereceivedbyoptimizingthresholdandusingaserpentinescanning.Theexperimentalresultsshowthattheproposedalgorithmcanreduceartifacts,enhanceedgeofimages,andgiveanappeasingperception.

        TheerrordiffusionalgorithmperformswellasoneofFrequencyModulation（FM）halftoningmethods,exceptfortendingtoproducingwormartifactsonhighlightareasandgeneratingnoiseswhichblurtheedgeofimages.Anewerrordiffusionalgorithmbasedontheaveragethresholdwasproposedbychangingscanningorder.Usingadaptivethresholdbasedonspatialextension,thehalftoningimageswereobtainedbyoptimizingthresholdandusingaserpentinescanning.Theexperimentalresultsshowthattheproposedalgorithmcanreduceartifacts,enhanceedgeofimages,andgiveanappeasingperception.

        Keywords:

        digitalhalftoning;errordiffusion;dynamicthreshold;scanningorder

        0引言

        数字半色调技术是一种二值量化技术,它利用人眼视觉特性使得二值图像可以在视觉上模拟连续的灰度图像[1]。

由于现在绝大多数的输出设备都是二值输出设备,数字半色调技术对输出图像的质量至关重要。

目前,数字半色调技术主要分为调幅加网和调频加网两类,其中前者在处理彩色图像时,容易产生明显的龟纹,而调幅加网可以避免这个问题。

尽管目前有很多调频加网算法,如抖动法、误差扩散半色调方法和迭代法,但相对调幅加网算法,调频加网算法几乎都是邻域处理,计算相对比较复杂。

其中,误差扩散算法是一种计算相对比较简单,效果比较好的一种调频加网算法。

        误差扩散算法[2]是将当前像素的量化误差按一定比例扩散到邻接像素上,这样局部的量化误差就在相邻像素上得到补偿。

这种邻域扩散的方法,使系统具有自我校正能力,成为了一个负反馈系统。

误差扩散算法最早由Floyd和Steinberg于1976年首次提出的,此后人们相继对该算法进行改进,如文献[2]中根据人眼视觉模型,提出的DBS半色调方法;文献[3]中提出基于模型的半色调算法。

后来有学者引入了信号处理中最小均方误差的思想,提出了一些自适应的半色调方法。

传统的误差扩散方法得到的半色调图像像素点有各向异性和无规律性,因此色调丰富,视觉效果好,但是仍存在缺点。

例如在中间调50%处容易产生龟纹;在高光和暗调部分会产生和处理方向有关的滞后现象,且在边缘部位容易出现不连续的过渡,处理速度相对较慢。

        本文旨在消除标准误差扩散半色调算法中出现的“蠕虫”现象,并改善误差扩散算法固有的缺陷:

容易产生噪声,导致图像边缘模糊,使得到的半色调图像视觉质量更好。

因此在简单误差扩散半色调方法的基础上,通过改变阈值的选择方式,优化平均阈值方法中的γ值及改变扫描顺序得到视觉质量相对较好的半色调图像,并用常用的评价参数对得到的半色调图像进行了评价。

实验证明,用该方法处理后的半色调图像,图像再现细节的能力更强,图像视觉效果更好。

        1误差扩散半色调技术的基本原理和特点

        误差扩散法由于其具有视觉效果好、易于实现等特征,因此被认为是最理想的半色调算法之一。

        误差扩散法的基本思想是将灰度图像的当前像素值与一个阈值相比较,得到一个二值输出,然后将像素点输入与输出灰度差以一定的方式扩散到未经处理的相邻像素上。

误差扩散算法的原理如图1所示。

        图1中:

Q（•）是阈值量化器,u（m,n）是该灰度值与部分量化误差的和,u（m,n）大于阈值时,Q（•）值为常数l,否则其值为0。

e（m,n）为量化误差,f（m,n）为输入信号,f（m,n）∈[0,1]。

对u（m,n）进行阈值处理得到表示信号b（m,n）,b（m,n）∈{0,1}。

H是误差扩散滤波器,滤波器系数为h（k,l）且有∑k,lh（k,l）=1。

        Floyd-Steinberg标准误差滤波器如式

（1）所示:

        h（k,l）=116000

        007

        351

（1）

        图片

        图1误差扩散的流程

        误差扩散算法所对应的数学模型为:

        u（m,n）=f（m,n）+∑k,lh（k,l）×e（m,n）

（2）

        b（m,n）=Q（u（m,n））=1,u（m,n）>T

        0,u（m,n）≤T（3）

        e（m,n）=b（m,n）-u（m,n）（4）

        其中:

f（m,n）为输入图像像素点的像素值;e（m,n）为量化误差值;hm,n（k,l）为滤波器的系数;b（m,n）为输出像素值;T为阈值。

        第4期张寒冰等:

数字半色调技术中的误差扩散算法的研究

        计算机应用第30卷

        图2为误差扩散算法的结果。

圆圈区域显示“蠕虫”问题。

由图2可见误差扩散算法高光及暗调区域以及阶调平滑区域会产生“蠕虫”现象,同时图像中边缘比较模糊,如图2（c）像框中的图比较模糊。

从误差扩散算法的原理看,导致如上问题产生主要有三个关键的因素:

一是误差扩散滤波器H。

误差扩散算法是通过误差扩散滤波器把各像素的量化误差传递给其相邻的像素的,它对半色调图像的质量至关重要。

误差扩散滤波器是非对称的滤波器,扫描顺序（即处理图像各像素的顺序）对图像的质量波动性比较大。

此外,此滤波器窗口较小,导致半色调图像不够清晰。

后来有学者提出不同的误差扩散滤波器（见式（5）和式（6））,试图去除扫描顺序的影响,并增大滤波器的窗口,提高半色调图像的清晰度,但这些修改又会产生较高的相关性噪声。

        图片

        图2Floyd和Steinberg算法中的蠕虫效果

        hStucki（k,l）=142000842484212421

        （5）

        hJavis（k,l）=148000753575313531（6）

        影响误差扩散质量的第二个因素是量化阈值。

在误差扩散半色调技术过程中,量化阈值影响对图像中轮廓边缘的影响比较大。

由于半色调图像只有两个色调没有中间其他色

        调,图像纹理轮廓的形成决定于量化阈值判定各像素的色调（是黑还是白）[4]。

当然,这也会受到邻域传递来的误差值的影响,但适合的量化阈值可以使得半色调图像的边缘轮廓比较清楚。

目前,误差扩散算法比较常用的阈值方法有中值法、平均值法、动态阈值法、极值点阈值法、最优阈值法和依赖坐标的阈值选取方法[5]。

本文就是通过优化平均阈值方法中的γ值得到最优的半色调图像。

        扫描顺序（或扫描路径）也是影响半色调图像质量一个因素。

扫描路径是误差滤波器的前进方向,也是对像素进行处理的顺序。

最早的像素处理路径是按照顺序扫描的方式（逐行扫描处理）,目前改进的扫描方法有如下几种:

“蛇形”扫描方式、Hilbert曲线扫描方式、基于上下文相关的空间填充曲线的扫描方式[6]。

其中除了逐行扫描方式和“蛇形”扫描方式外,其他方法的计算相对比较复杂。

        在误差扩散算法中并没有一种最优的扫描方式,扫描顺序对加网质量影响程度与滤波器有很大的关系,它对使用非对称的误差扩散滤波器算法的影响比较大,如在Floyd和Steinberg算法中使用逐行扫描方式,易于在亮光和暗调部位出现龟纹现象以及与处理方向有关的滞后现象[7-8]。

但对使用对称的误差扩散滤波器的算法影响比较小,特别是在逐行扫描方式和“蛇形”扫描方式之间。

我们将根据本文的误差算法选择适合扫描顺序。

        2误差扩散半色调方法

        误差扩散抖动算法有两个比较显著的效果:

边缘增强和噪声成形[9-10]。

本文提出了一种改进的误差扩散算法,该算法主要从两个方面来改进:

在输入像素值与阈值比较之前,先对输入像素值做一个乘法,（k-1）*u（m,n）,通过改变参数k的数值可以改变输出图像的边缘增强效果,进而改善半色调图像的视觉质量。

对于阈值的选择,不再是一个常值,而是采用平均值法,使得不同像素点的阈值不同,进而改善半色调图像的视觉质量。

        1）确定合适的参数k。

        参数k值的选取不同,得到的图像效果不同。

在这个算法中,通过比较阈值T与[K*u（m,n）-e（m,n）]大小,得到输出图像的像素值（0或者1）。

当k=1时,这个算法就演化为标准误差扩散抖动算法,将k值与输入像素值相乘,就决定了参与阈值比较的图像信息的大小。

k值越大,说明在误差扩散过程中有越多的图像信息参与;反之,则运用了较少的图像信息。

        2）确定阈值。

        传统的误差扩散算法的阈值量化器Q（•）中量化阈值T为常数127。

本文采用动态阈值的方法来选择阈值T（m,n）,首先了解动态阈值的原理,其数学表达式（3）改为:

        b（m,n）=Q（u（m,n））=1,f（m,n）>T（m,n）0,f（m,n）≤T（m,n）（7）

        其中T（m,n）的表达式为:

        T（m,n）=19∑1y=-1∑1x=-1f（m+x,n+y）（8）

        在图像再现的过程中,为了控制再现图像的对比度,加强图像的锐化性能,对平均阈值法进行了改进,改进后如式（9）、（10）所示:

        φ（m,n）=γ+T（m,n）×（1-2×γfmax）（9）

        b（m,n）=Q（u（m,n））=1,f（m,n）>φ（m,n）0,f（m,n）≤φ（m,n）（10）

        其中:

Pm,n为邻域的平均值;fmax为原图像像素的最大灰度值。

        参数γ决定了最终二值图像的对比度,且与图像像素的噪声统计有关,因此采用这种方法进行半色调时,γ值的恰当选取是非常重要的。

        在本文中,通过大量的实验图像和数据得到一个相对恰当的γ值。

γ值决定了半色调图像的对比度,当γ值的绝对值增大时,图像的对比度增强,背景噪声得到了抑制,景物突出;但是,当参数γ的绝对值增大到一定程度时,背景噪声虽进一步抑制,但是景物的细节也会有所丢失。

        在标准误差扩散抖动算法中,阈值采用的是128或者127,即采用中值法。

本文的实验环境是Matlab7.0,在实验中,所用的图像质量评价参数有主观评价参数和客观评价参数。

第一步,初定的γ值区间为[50,225],包含了灰度图像的中间调部分,并以5为间隔,通过图像质量评价参数来确定合适的γ值区间;第二步,针对相对合适的γ值区间,以1为间隔,处理其邻近的10个备选γ值,进而得到更为精确的γ值。

        本文以Lena图为例来确定合适的γ值,所用的评价参数主要有通用质量评价参数（UniversalQualityIndex,UQI）、峰值信噪比（PeakSignalNoiseRatio,PSNR）和权重信噪比（WeightedSignalNoiseRation,WSNR）。

通过重复实验,得到最合适的γ值,如由实验数据形成的曲线如图3所示。

        图片

        图3γ值分别与UQI、PSNR和WSNR的曲线

        3改进的算法的编程实现

        该实验的工作环境是Matlab,在算法实现的过程中,对于边缘像素而言,可以采用不处理最边缘像素点的方法。

算法实现步骤如下。

        1）根据平均阈值的原理求出连续调图像二值化的阈值。

        2）对连续调图像采用行扫描方式,奇数行从左到右扫描,偶数行从右到左扫描。

        3）误差滤波器仍然采用标准误差扩散抖动的过滤器,即将待处理像素7/16的误差被加到X（输入像素值）的右边像素上,3/16的误差被加到X的左下方像素上,5/16的误差被加到X的正下方像素上,剩下1/16的误差被加到X的右下方像素上。

        4）重复1）~3）,直到最终将所有的像素处理完。

对于边缘像素而言,可以采用边缘去除的方法来处理。

        其算法的具体流程如图4所示。

通过该算法计算后得到的半色调图像如图5所示。

        这种算法也有缺点,可以看到在得到的半色调图像中仍然存在结构性的纹理,主要是对于γ值的选取问题。

选择合适的γ值可以得到较高质量的半色调图像,同时γ值的选取与图像噪声统计分布有关。

在本文中,γ值的选取是通过大量实验数据得到,没有很具体的数学依据,所以难免有些误差。

        通过该方法处理的半色调仍然存在一些结构性、规律性的人工纹理,但可以通过调节γ值来改善半色调图像的质量。

实验表明,它与标准误差扩散半色调算法计算速度相当,处理效果要优于标准误差扩散算法。

        图片

        图4算法流程

        图片

        图5不同误差扩散算法的效果

        4半色调图像质量评价

        传统的图像质量评价方法可分为主观评价和客观评价两类[11]。

主观评价法通过对观察者的评分归一化来判断图像质量,主要方法有主观平均分法（MeanOpinionScore,MOS）。

客观评价方法是指以再现图像偏离原始图像的误差来衡量再现图像的质量,主要方法有归一化均方误差（NominalizationMeanSqureError,NMSE）、峰值信噪比（PSNR）、权重信噪比（WSNR）以及交叉熵（Cross-entropy）等。

对于半色调图像的质量评价,本文采用峰值信噪比（PSNR）、归一化均方误差（NMSE）和清晰度。

        1）峰值信噪比。

        如果认为标准参考影像是信息,且处理结果影像与标准参考影像的差异是噪声,那么定义结果影像峰值信噪比（PSNR）表达式为:

        PSNR=10lg2552×MN∑Mi=1∑Nj=1[f（i,j）-b（i,j）]2（11）

        其中:

M,N分别为影像的宽和高;f（i,j）,b（i,j）分别为标准影像和结果影像在对应的像素点（i,j）处的灰度值。

        峰值信噪比是较早的用于评价图像质量的方法,它与均方误差本质是相同的,它们具有相同的优点和缺点。

实验结果表明,这种方法可以很好地评价图像的带噪和模糊情况,一般情况下,它仍然是评价图像质量的首选指标。

        2）加权信噪比。

        研究发现,图像的离散傅里叶变换矩阵与视觉敏感度函数相乘的结果可以模拟人眼视觉系统观察图

        像并得到相似的效果。

将这种原理应用到信噪比的数学模型中即得到加权信噪比[12-13]。

加权信噪比是衡量非线性失真以及噪声情况的一个量度,加权信噪比（WSNR）的计算方法如下:

        WSNR=10lg∑0≤i

        其中:

X（i,j）和Y（i,j）分别代表原始图像和待测图像;C（i,j）表示视觉敏感度函数的离散傅里叶变换;M×N为图像的大小。

WSNR定义了平均信号能量与平均噪声能量之比。

WSNR值越大,原始图像与再现图像越接近。

        3）通用质量评价参数。

        文献[14]中提出了一种对图像通用质量进行评价的模型,通用质量评价模型Q的计算公式如下:

        Q=4σxyxy（σ2x+σ2y）[（x）2+（y）2]（13）

        其中:

x=1N∑Ni=1xi,y=1N∑Ni=1yi。

        σ2y=1N-1∑Ni=1（yi-y）2（14）

        σxy=1N-1∑Ni=1（xi-x）（yi-y）（15）

        该模型的优点在于将再现图像与原图像之间的误差归结为三个不同的因素:

相关性丢失、亮度失真和对比度失真。

为了便于理解,可以将Q重新定义如下:

        Q=σxyσxσy•2xy（x）2+（y）2•2σxσyσ2x+σ2y（16）

        其中:

第一项是原始图像（x）与半色调图像（y）之间的相关性系数,它的范围为[-1,1],当它为最佳值1时,表示x,y是线性相关的。

第二项衡量了原始图像（x）与半色调图像（y）之间的平均亮度逼近度,其取值范围为[0,1],仅当=,且当σx和σy可以看作x,y的对比度估计值时,第二部分取得最佳值1。

最后一项衡量了两幅图像对比度的相似度,其取值范围为[0,1],仅当σx=σy时,其取得最佳值1。

所以Q∈[0,1],Q值越接近1,原始图像与再现图像的差异越小。

实验结果如表1~3所示。

        表格（有表名）

        表1三种算法参数对比（Lena图）

        算法

        参数

        UQIPSNRWSNR

        标准误差扩散抖动0.25906.75327.7942

        S型误差扩散抖动0.25776.74587.7839

        基于平均阈值的误差扩散0.24606.78547.6619

        由表1~3的质量评价参数结果可以看出,客观评价方法能够从总体上反映原始图像和再现图像的差别。

同时从图像误差整体统计特征的角度上看,由于各种算法的峰值信噪比不同,再现图像误差的整体统计特性也不同。

从PSNR值可以看出,采用标准误差扩散算法得到的再现图像的PSNR值小,采用动态阈值误差扩散抖动的峰值信噪比值最大,所以说再现图像整体统计特性最好是采用动态阈值误差扩散抖动算法处理的图像。

从P【指代什么值,是PSNR吗?

需交代清楚。

值这一栏可以看出,通过采用动态阈值误差扩散算法处理的图像的P【值最小。

通过以上结果分析可以看出,通过动态阈值调节的误差扩散算法的再现图像,总体上来说要优于其他几种算法得到的半色调图像的质量。

        表格（有表名）

        表2三种算法参数对比（boat图）