基于误差扩散的Dither算法研究与实现

夏 禹，王亚雄

(浙江大学电气工程学院VLSI研究所，浙江杭州 310007)

1 基于误差扩散的Dither处理方法

由于受成本等因素的限制，部分低成本液晶的点阵驱动显示设备的彩色达不到16 777 216(24 bit)种。如果用这样的显示设备显示真彩色，将会出现由于数据地位丢失造成的灰度级合并和彩色失真。要解决颜色压缩以及压缩后的颜色失真问题，Dither是一种有效的方法，可大幅提高图像的显示质量。误差扩散法是将当前点的初始值和前边点扩散后的误差相加，得到的结果舍去低位后输出到显示器，而被丢弃的低位数据作为误差扩散给后边的点，从而保证图像质量。

半影调技术是用两种颜色显示出灰度效果的方法。半影调图案法中，灰度可以用一定比例的黑白点组成的区域表示，从而达到整体图像的灰度感，黑白点位置的选取称为图案化。如图1中2×2的图案可以表示5级灰度。

图1 五级灰度表示图

同理，如要储存256级灰度的图案，就需要16×16的二值点阵，假设灰度级继续增大，是较为不利的。与此相比，还有一种较好的方法是储存一个整数矩阵，称为标准图案如图2(a)所示，其中每个点均可取值0～255中的数字。图像的实际灰度如图2(b)和图2(a)标准图案矩阵中的每个值进行比较，当标准图案中点的值大于等于实际灰度值时，对应点标注黑点，否则标注白点，图2为一个25级灰度图案示例。

图2 25级灰度图

目前惟一的问题就是标准图案矩阵的确定。先以一个2×2的矩阵开始，通过递归关系，设矩阵均为方阵，而且其中元素均为1。根据该算法，可得到16级灰度的标准图案。同理，其也为2×2的方阵，称为Bayer抖动表。

根据以上算法，如利用一个像素需要用的图案表示，则原本一幅图将变换大小。而自然的设想是能否在保持图像大小不变的情况下利用图案化技术。其中一种方法是重新取样，如果利用阵，则将原图中每点中取一点，然后再应用图案化技术，就可保持原图大小不变。实际操作中，该方法并不可行，首先要考虑应该如何取点较为合适，另外间隔过大，取不同点得到的结果差别同样较大。为解决这一问题，文中采用了以下方法:假设原图是256级灰度，利用Bayer抖动表，作如下处理。

其中，x，y代表原图的像素坐标以及该点的实际灰度。以上处理首先将灰度右移两位变成64级，然后将x和y作模8运算，找到Bayer表中的对应点并将两者相比较。该算法称为规则抖动(Regular Dithering)，其特点是，算法简单且容易实现，缺点是图案化较为明显。如图3(a)和图3(b)所示。

图3 灰色原图与规则抖动后对比图

2 Floyd－Steinberg抖动

规则抖动中，进行的是图像点值与标准图案上点值的比较，这一方法效果并不理想，容易产生较大误差，而解决的方法可利用误差扩散，将误差扩散到邻近像素。Floyd－Steinberg是一种较为经典的基于误差扩散的抖动算法，其误差就是转换前后像素颜色的差别值，具体的扩散方法如下。

(1)为每个像素寻找最接近的新色彩:1)如果是灰度图到黑白图的抖动，此步操作就是简单的阀值操作。2)如果是更为复杂的，假如从24位色到16位色的抖动，则应该将RGB分开处理，为每个分量分别寻找最接近的值。

(2)计算新色彩与原色彩之间的误差，即分割误差成多份，并将误差扩散到与当前像素邻近且未被访问过的元素上。在这些步骤中，最关键的步骤就是扩散误差，最经典的分割误差比例是其中已被访问过的像素，X是当前像素，误差被分割成16份，其中3份分入左下的像素，5份分入下方的像素，1份分入右下的像素，7份分入右方的像素。

另外，误差的扩散方向同样需要考虑。因为像素是按照某个方向逐个扫描而来，而误差不可扩散给已经访问过的元素，当水平扫描时就存在从左向右扫描和从右向左扫描两种方式。在实际应用时，文中采用交叉扫描进行，也就是一行从左向右扫描，下一行从右向左扫描。这样可有效地防止流水效应，即两行像素因色彩极为接近，在同向扩散时一些色彩突出的像素将出现在同一列附近，如图4(a)与图4(b)所示。

图4 灰度原图与Floyd－steinberg抖动处理后对比图

从以上程序得到的图像可知，运用 Floydsteinberg抖动所得的图像要明显优于使用Bayer表抖动所得图像，误差扩散可提高图像的质量。

3 动态阀值

误差扩散是一种调频半色调技术，但该技术在图像高光和暗调以及阶调平滑区域会产生“蠕虫”，同时噪声较多，导致半色调图像的边缘不清晰。在Floyd和Steinberg的误差扩散算法的基础上，设计一种新的基于平均阈值和改变扫描路径的误差扩散算法——阈值采用平均值法，通过优化平均阈值方法中的γ值得到最优的半色调图像。

在误差扩散半色调技术过程中，量化阈值影响对图像中轮廓边缘的影响较大。由于半影调图像只有两个色调并无中间其他色调，图像纹理轮廓的形成决定于量化阈值判定各像素的色调。当然这也将受到邻域传递的误差值影响，但适合的量化阈值可使得半影调图像的边缘轮廓较为清楚。文中的误差扩散算法的阈值量化器中量化阈值为常数127.5，此处采用动态阈值的方法来选择阈值T(m，n)。由同理可得到动态阀值的24位色向16位色进行Floyd－Steinberg抖动的方法。

4 图像评价

文中使用的图像评价指标为峰值信噪比(PSNR)。如认为标准参考影像为信息，且处理结果影像与标准参考影像的差异为噪声，那么定义结果影像峰值信噪比(PSNR)表达式为其中，M和N分别为影像的宽和高;以Rij和Fij分别为标准影像和结果影像在对应的像素点(i，j)处的灰度值。实验结果表明，该方法可较好地评价图像的带噪和模糊情况，正常情况下，其仍然是评价图像质量的首选指标。

以4组照片对算法的优劣进行比较，分别计算峰值信噪比。如图5(a)～图5(d)所示。

图5 峰值信噪比计算与对比图

表1是对以上各图峰值信噪比(PSNR)的计算结果比较。

表1 峰值信噪比(PSNR)的计算结果

从以上比较可知，对于颜色渐变图而言，无抖动的峰值信噪比最佳，动态阈值的FS抖动次之，固定阈值的FS抖动PSNR最差，但从直观的图像可看出无抖动的图像颜色突变较为严重，而应用FS抖动的两种处理方式效果较好。

尽管从上述图像中无法直观看出动态阈值的优化作用，动态阈值的FS抖动比固定阈值的FS抖动模糊，但其颜色分布较为平滑，且从峰值信噪比同样可以看出动态阀值优于固定阀值，可推断假设使用更为合适的选取动态阈值的方法从而得到最优动态阈值，在一定情况下可以优化图像。

［1］闫敬文.数字图像处理［M］.北京:国防工业出版社，2007.

［2］徐涛，李冠章.基于小波变换的彩色图像自适应细节增强算法［J］.计算机应用与软件，2011(3):246 －248，301.

［3］张寒冰，袁昕.数字半色调技术中的误差扩散法的研究［J］.计算机应用，2010(4):925 －928.

［4］江玉珍，朱映辉.基于调色板分析及误差扩散抖动的迷彩仿造［J］.计算机工程与应用，2011(9):1－6.

［5］张寒冰，袁昕.数字半色调技术中的误差扩散算法的研究［J］.计算机应用，2010(4):75－78.