四种常用的数字半色调算法

　　众所周知，数字半色调技术是指基于人眼视觉特性和图像呈色特性，利用数学、计算机等工具，在二值（或多色二值）呈色设备上实现图像的最优再现的一门技术。数字半色调是利用人眼的低通特性，当在一定距离下观察时，人眼将图像中空间上接近的部分视为一个整体。利用此特性，人眼观察到的半色调图像局部平均灰度近似于原始图像的局部平均灰度值，从而整体上形成连续色调的效果。

　　半色调技术应用于印刷领域已有一个多世纪，应用在数字输出设备上也有40多年。随着激光打印机、喷墨打印机、数字印刷机、数码相机和等离子显示屏等数字输出设备应用越来越普遍，数字半色调技术受到生产厂家和研究机构的普遍关注。数字半色调技术除了在印刷与图像输出方面的应用，还应用于压缩存储、纺织以及医学等领域。因此，数字半色调技术具有重要的理论意义和使用价值。

　　根据数字半色调的应用特性和不同领域，人们提出了许多算法。按照算法的处理方式对之进行分类时，可分为点处理算法、邻域处理算法和迭代法。点处理算法是最简单的方法，这类算法利用数字方式来模拟印刷工业中传统的接触加网过程，其产生的半色调图像中的每个像素单元仅取决于像素的阶调。其中最重要的方法有半色调模板法和抖动法；邻域处理算法对连续调图像待处理像素的邻域内多个像素进行计算，以获得半色调图像的像素值。这类算法中较典型的是误差扩散算法；迭代法是一种迭代处理的算法，它需要多次比较计算以获得最优的半色调图像。所以，其计算量最大。下面介绍四种具有代表性的数字半色调算法：

　　1、点扩散法(Dot Diffusion)

　　Knuth提出的点扩散半色调算法是一种企图保留误差扩散的优点的同时提供并行处理的一种算法。点扩散算法只有一种设计参数，即类矩阵C，它决定了像素被半色调处理的顺序，一个连续调图像像素的位置  根据被划分到IJ类中，I和J都是不变的整数。

　　2、迭代半色调算法

　　迭代半色调算法的思想是先用一种简单的方法得到初始的半色调图像，然后对初始半色调图像进行迭代处理，使每次处理得到的半色调图像具有更小的误差，最后得到视觉最优的半色调图像。迭代半色调算法的优点是得到的半色调图像视觉效果非常优秀，基本上没有结构性纹理；能够正确地再现丰富的色调。但是基于这种算法的计算复杂度，迭代半色调算法一般很难用于实时处理场合，仅可以作为一种标准测试程序使用。

　　3、误差扩散算法（Error Diffusion）

　　误差扩散算法是一种比较流行且半色调效果较好的算法，这种算法最早是由Floyed-Steinberg提出的。这种算法需要进行邻域处理，它能够为印刷机提供更高的半色调质量并且不引起网点增大，产生的半色调图像色调丰富，像素点的分布具有各向异性。

　　其基本思想是先按照一定的扫描路径阈值量化图像像素，然后将量化误差以一定的方式扩散到相邻的未处理的像素上。

　　DBS用一个迭代的交换程序来减少误差E，这种算法从随机获得的初始半色调图像开始，按照从左到右，从上到下的顺序扫描整个半色调图像，对于半色调图像的每个像素，评价将像素取反和将其值与周围八个像素交换对得到的半色调图像质量的影响。如果任何的改变减小了误差，这种使得误差减小的变换就被保留，反复地在半色调图像上执行上述过程，直到整个过程没有任何变换操作，DBS算法结束。

　　4、有序抖动算法（ordered dither）

　　在这种加网算法中，将输入图像和一个周期的阈值矩阵（或称为加网矩阵）进行比较。阈值矩阵，这里N定义了阈值矩阵的周期。

　　对于一个特定的阈值矩阵t(n) ，其有序抖动加网算法可以如下描述：

　　输入图像应该被归一化，即0≤x(n)≤1。当h(n)=0时，半色调输出的像素为白点，当h(n)=1时，半色调出的像素为黑点。阈值矩阵决定了当亮度减小时网点变成黑点的顺序，它也决定了半色调图像的质量。有序抖动算法随着阈值矩阵的不同设计而具有不同的特点，最简单的阈值矩阵是那种每个像素点都是固定值的矩阵：t(n)=0.5。如果对图像实行具有这种阈值矩阵的有序抖动算法，大多数存在连续调图像的细节被丢失，并且得到的相应半色调图像对比原连续调图像存在很大的失真。

　　一般来说，有序抖动分为点聚集有序抖动和点离散有序抖动。点聚集有序抖动的加网矩阵被精心设计以模拟半色调处理过程。当连续调图像的像素密度减小时，网点将在像素的周围生成。点离散有序抖动的设计规则是由Bayer提出的。他的研究指出，非理想人工纹理的可见性可以通过对不同亮度等级的网点模式进行傅立叶分析得到。当一个一致色块的网点模式在不同波长都有成分时，有限波长中最长波长对应的成分就是可见度最高的成分。基于这个标准，Bayer设计了优化的加网矩阵，应用这个矩阵的点离散有序抖动得到的半色调图像包含了更多的可见细节。

　　尽管点离散有序抖动保留了更多的细节，但由于“网点增加”的原因，在实际应用中却经常使用点聚集有序抖动。网点增加是由打印机的非理想特性造成的，虽然可以假定理想的打印机能够产生具有预先定义的几何形状如方形的网点，但由于油墨从预先定义的几何形状向周围像素的扩散，就会产生网点增加现象。而当连续调图像的像素密度降低时，网点将从周围像素生成，所以点聚集有序抖动更易于阻止网点增加，从而在整体上减少了半色调图像中的网点增加效应。

　　总体说来，在这些半色调算法中，产生的半色调图像质量最好的是迭代算法，但是由于过于复杂的计算量，一般不在实时处理算法中使用。误差扩散算法是目前最为流行的半色调算法，其产生的半色调图像无明显龟纹，视觉效果较好。抖动算法实现简单，但在阶调再现、空间分辨率和可见纹理等方面都存在一定的缺陷。而点扩散算法实现了并行处理，但半色调图像质量方面还有待改善。