引言
现有的半色调技术种类繁多，生成的半色调图像的视觉效果也越发逼真，不过相应的代价就是较高的时间复杂度。有序抖动方法最简单而且能够完全并行处理整幅图像，但是生成的半色调图像视觉效果最差。误差传递方法产生的半色调图像视觉效果很好，但由于它的生成半色调图像过程的所要求的传递性，不能和有序抖动一样并行完成半色调过程。直接二元搜索法生成的半色调图像的视觉效果最好，但是计算复杂度却相当高，不合适在要求实时输出半色调图像的场合下使用。现在应用较广的误差传递方法在表现图像细节上仍需改进，其生成的半色调图像纹理从人眼观测看来不够细腻。我们需要根据人眼视觉系统的特性设计出视觉效果更加生动的半色调算法。
半色调技术是
指用少量的色彩将一幅连续色调图像(如灰度图像和彩色图像)量化为一幅二值图像或是只有少数几种色彩的彩色图像，并且量化后图像在一定距离的视觉效果和原始图像相似的技术。众所周知，数字半色调技术是指基于人眼视觉特性和图像呈色特性，利用数学、计算机等工具，在单色/多色二值呈色设备上实现图像的最优再现的一门技术。数字半色调是
利用人眼的低通特性，当在一定距离下观察时，人眼将图像中空间上接近的部分视为一个整体。利用此特性，人眼观察到的半色调图像局部平均灰度近似于原始图像的局部平均灰度值，从而整体上形成连续色调的效果。
连续调图像与半色调图像
在我们的日常生活中，所遇到的图像可大致分为两大类：连续调图像(Continuous-Tone Image)和半色调图像(Halftone Image)。
- 如我们常见的彩色照片就是一种连续调图像，在这种图像上，存在着由淡到浓或由深到浅的色调变化并且浓淡或深浅是以单位面积成像物质颗粒密度来构成的，并且这种图像的深浅变化有无数多级。另外,印刷工艺中的照相分色底片的连续调，是由单位面积内由金属银颗粒密度构成的；而各种彩色画稿的连续调，是由单位面积内由各种颜料颗粒密度构成的，单位面积内颜料颗粒多即为深色调，否则为浅色调。
- 半色调图像如常见的印刷品图像，其由浅到深或由淡到浓的变化，是靠网点面积大小或网点覆盖率来表现的。一般用于复制诸如照片之类的连续调原稿时，会采用这种半色调技术，它将图像分成许多点，通过点的不同大小来表现颜色的深浅。在印刷品的印刷时，印刷机用有限数量的一套油墨(只有黑墨或青、品红、黄、黑墨)来印刷数量不同、大小不同的细小点，印刷品画面上色彩和浓淡就是靠这些细小的点来表示的，由此可以给人眼产生许多灰度级或许多颜色的错觉。当观察印品画面时，网点面积大，颜色就深，称为暗调；网点面积小，颜色就浅，则称为亮调。由于网点在空间上是有一定的距离的，呈离散型分布，并且由于加网的线数总有一定的限制，在图像的层次变化上不能像连续调图像一样实现无级变化，故称加网图像为半色调图像。如加网的阳片菲林、阴片菲林、印刷图像等都是半色调图像。
半色调技术的发展历史
在印刷工艺中，半色调技术也称为加网技术，加网技术发展到现在己有上百年的历史。从早期的照相加网到现代的数字加网，从调幅加网到调频加网，从粗网点到精细网点，共经历了三个阶段：照相加网(即模拟加网)、电子加网和计算机数字加网三个发展阶段。
模拟加网
模拟加网是指利用网屏对光线的分割作用，将连续调图像分解成大小不同网点的网目调图像的方法。它的发展可分为玻璃网屏加网和接触网屏加网两个阶段。
- 网屏加网是德国的GocgrMeisnebach在1882年首创将连续调图像经加网分解成网目调图像进行制版印刷的加网技术，于1886年由美国人Ives和Ivey制造成功。投影网屏加网是加网技术的鼻祖，使印刷产品能反映图像的层次变化，但技术要求高，操作复杂。在制作玻璃网屏时，选用优质的光学玻璃，表面涂上耐强酸的漆膜，在专门雕刻机上划成等长的平行直线，线条的疏密由网屏的线数来确定。刻好后在玻璃背面也涂上耐酸保护膜，用氢氟酸腐蚀。经腐蚀凹下的部分涂上黑色油质，然后洗去耐酸膜层，这样就制成了透明与不透明相间的玻璃线条版。用两块这样的线条版垂直胶合在一起，边上镶好金属框，即制成玻璃网屏。加网时，光线通过网屏的网孔投射在感光版上。由于光线通过网孔后的衍射作用，就在湿版上产生大小不同的网点。通过网孔的光量强，网点就大；光量弱，网点就小。这样，就把原稿图像的明暗变化，映射到感光版上后转变成网点的大小变化。这种用网点大小表现明暗深浅的阶调，在工艺上称半色调(halftone)。由于网屏上网线的宽度与透明方格的宽度相同，4条网线才围出一个透光方格。所以，整个网屏面积中只有四分之一的面积是透光的。为了在感光版上形成足够大小的网点，就必须有足够的感光量。由于感光版感光性能本来就低，再加上玻璃网屏的透光率也低，所以加网必须有功率强大的光源和较长的曝光时间。这种网屏在七十年代以前照相制版中用了很长时间。玻璃网屏除有笨重、价昂等缺点外，使用时网屏与感光片之间必须有一定的距离(网距)，易损失图像层次，影响画面清晰度，所以逐渐被接触网屏取代.
- 接触网屏加网是Kodak公司在1940年根据半影理论第一次用工业方法研究成功的第二代加网技术。它克服了投影网屏的诸多缺陷：如在高光和暗调部位，网点的表现效果较差；需要备用各种点形、反差、线数的网屏；耐用性较差等。德国Klimsch厂在60年代生产了全阶调Gardar网屏，该网屏的线型是透明的，所以能把原稿上明亮部分的色调予以调节，有利于保证高调细节的完整性。 这种网屏一般是用玻璃网屏作母版，在制版照相机上用硬性感光胶片制成的。接触网屏为胶片状，用放大镜仔细观察，上面布满了网点，每个圆网点中间有一个很黑的核心，边缘密度递减。从整体上看网点的排列，每四个黑点中间有一个透明孔，或每四个透明孔中间有一个黑点。接触网屏具有价廉、体轻，加网时与感光胶片密合接触，进行曝光，光线通过接触网屏就会在感光胶片上形成大小不同的光洁网点，其加网效果同用玻璃网屏基本一样，减少了翻拍中的层次损失，具有使用方便，提高了画面清晰度等优点。
电子加网
电子加网是指将图像信号数字化后经计算机计算处理并转换成网点输出的新型加网技术，这种技术产生于80年代初，是在电子分色机上通过电子网点发生装置对原稿完成加网的过程。
其原理是：经过电子分色机处理的代表图像不同密度级次的数字信号，送入电子分色机图像输出记录系统的网点计算机，并通过比较回路形成网点大小、形状、角度的地址指令，由地址指令从网点计算机中获得控制激光记录系统的控制信号，加在电光调制器上，控制各个电光调制器的输出工作状态，最后把由调制器控制的光信号记录在感光材料上，就能获得与原稿图像信息相一致的、具有特定大小、形状和角度的网点。
由于电子加网是数字控制的，网点是由激光记录所得，因此具有网点实、密度高、边缘清晰；网点层次多，细微层次丰富并且可以根据需要在不同阶调处产生形状不同的网点，易于控制网点扩大等优点。
计算机数字加网
数字加网是指桌面出版系统中采用基于PosstcriPt框架下的网点技术。根据记录点的分布状态，可以将数字加网分为调幅加网和调频加网两大技术。
- 数字调幅加网技术(点聚集态网点技术)在数字加网技术中，调幅加网是用不可见的、行列排列有序的网格分割图像，每个网格按照一定的角度、加网线数生成面积不同的网点。在生成记录网点的黑/白(0/l)时，总要受到加网角度、网点形状和加网线数的限制，所以在每个位置上设置0/1的自由度相对较低。调幅加网技术又称为点聚集态网点技术，这种加网技术得到的是聚集态的记录点。我们通常将聚集在一起的点称为传统网点，它由图像信息的灰度层次来控制网点的增长。
- 数字调频加网技术(点离散态网点技术)调频加网从某种意义上来说又可以称为点离散态网点技术，该技术得到的是离散分布的记录点。这种加网计算不再受网格的限制，直接以发散无序的记录点阵象素群构成图像，在每个可记录位置上设置0/l的自由度高于调幅加网，这使得调频加网图像具有较高的信息容量。调频加网又称随机加网，/随机性0在数学中用于描述分析和预言粒子在粘稠液体中运动的过程，印刷中则用于描述精确摆放点子的方法，以产生随机性并产生色调级的感觉。实际上，网点位置是基于/计算的随机性0。网点的空间分布是通过算法来分配的，根据色调的统计估算值和图像邻近部分的细节来分布点子，不会出现明显的堆积或不需要的微型点累积。
半色调技术分类
目前半色调技术最普遍的分类法是按照它的处理方式分为：抖动法，误差扩散法，迭代法三大类。
抖动法
抖动法是点处理类方法的一种典型算法，主要分为随机抖动和有序抖动两大类。这两种算法都需要一个模板，也称为抖动矩阵或阈值矩阵，抖动矩阵不仅决定了当亮度或灰度值减小时网点变成黑点的顺序.而且也决定了半色调图像的质量，所以抖动算法的关键是抖动矩阵的构造。该算法与抖动矩阵进行比较，矩阵中的每个阈值的取值范围是图像的最大灰度值和最小灰度值之间，其数学公式化如公式1：
……………………….公式 1式中f(i，j)代表连续色调图像中的像素点灰度值，t(i，j)代表抖动矩阵的阈值，而h(i，j)代表半色调后的图像灰度值。
随机抖动矩阵是通过完全随机产生的，所以半色调后的图像质量常常很不理想，在实际中已经基本不再使用。但有序抖动的抖动矩阵是有规律的，具有良好的图像效果和高效的处理速度而被各大打印机厂商采用，有序抖动矩阵主要有两种类型：分散型和聚集型。典型的分散型抖动矩阵是Bayer有序抖动矩阵，而点局部聚簇整体分散是典型的聚集型矩阵，如图1所示。
(a) Bayer有序抖动阈值矩阵
(b)聚簇型抖动阈值矩阵
图
1 有序抖动阈值模板
虽然有序抖动算法比较简单，且具有较好的半色调图像质量，但其也具有致命的缺点，即含有明显的周期性人工纹理。即使抖动矩阵设计的非常完美，其输出的半色调图像依然存在瑕疵，且其半色调图像质量不如通过误差扩散算法获得的半色调图像。图2是有序抖动方法的输出结果 .
(a) 输入图像 (b) Bayer有序抖动结果
图 2 输入图像及Bayer有序抖动结
误差扩散法Error Diffusion
在有序抖动处理中，利用了像素点与抖动矩阵比较来判断是否在一个位置放置微点，实质是一种点处理过程。在1976年Floyd和Steinberg提出了误差扩散算法，它将半色调加网从“点处理”过渡到“邻域处理”。误差扩散算法的提出为半色调加网带来了革命性的技术变革，也是半色调技术上的里程碑，并促进了半色调技术的飞速发展。通过误差扩散处理后的半色调图像像素分布各异且无规律性，色调丰富，视觉效果较好。直到目前为止，它依然被视为易于实现且视觉效果较好的半色调技术之一，被广泛应用.
图 3 Floyd-Steinberg误差扩散示意图
给定阈值t，设原图像为x(i，j)，输出为y(i，j)。对整幅图像按从左到右、从上到下的顺序逐点的依次执行两步操作：
- 阈值化y(i，j):
- 把量化误差扩散到邻近的未被处理过的点。量化误差是指输入与输出之间的差：量化误差扩散即改变空间上相邻像素x(i，j+1)，x(i+l，j-1)，x(i+1，j)，x(i+l，j+1)的值，将当前像素的量化误差按7：3：5：1的比例转移并叠加到邻近的像素
图4为输入图像与采用误差扩散输出结果,如下图所示.
(a) 输入图像 (b) 误差扩散结果
图 4 输入图像与误差扩散结果
换句话说，误差扩散相当于把中值阈值法在每一个点上产生的误差再加到周围的点上，从而保持局部区域的总体灰度基本不变。量化误差扩散的参数可以用一个矩阵描述，称之为误差扩散过滤器，设为P，P={Nr，s}，(r，s)D为P中所有非零元素对应的下标集合。这里的下标r，s是整数，可以为正、为负或为0。这样上述公式可写为：
Floyod-Steinberg算法中的P如图3。矩阵中的圆点代表N0，0(以下类似)。圆点和空自位置的参数都为0。因为像素处理顺序是从左到右、从上到下，所以量化误差只能向右方、左下、下方和右下的相邻像素扩散。
阈值r的选取通常取中间值0.5。曾有人对其他阈值做过尝试，但结果没有明显的优点，所以大多数算法仍然简单的用0.5作为阈值。现举例说明阈值比较和扩散的过程：假设当前输入像素灰度为0.7，阈值为0.5，则该点输出1。量化误差为-0.3。Floyd-Steinberg算法的参数是7/16，3/16，5/16，1/16，即将量化误差-0.3分别乘以7/16，3/16，5/16和1/16叠加到四个相邻像素如图4所示。
过滤器有很多选择，如，Jarvis、Stucki、Shiau-Fan等等，如图5所示。它们大部分是在Floyd-Steinberg过滤器基础上做的改进。因为误差扩散抖动算法会一定程度上使图像边缘模糊，有的改进过滤器可以补偿性的增强边缘，使输出图像更清晰。还有一些过滤器在不同程度上对误差扩散的速度和效果做了优化。现在的过滤器结构变得越来越复杂，但并不是过滤器越复杂，输出图像效果就越好。
图5 常见的误差扩散滤波器
从整体上看，误差扩散的效果是很好的。目前已有的最好的半色调效果仍是基于误差扩散方法。误差扩散也有不足之处。从速度上看，中值阈值法对每个像素只做一次比较运算，速度很快。而误差扩散要进行大量的乘除法运算，速度相对较慢。如图6所示不同滤波器得到的误差扩散图。
图 6 不同滤波器得到的误差扩散图
clc
clear;
im=imread('test.jpg');
A=rgb2gray(im);
B=imcrop(A,[150,150,256,256]);%在图像的（150,150）处截取（256,256)大的图像
B=double(B)/255;%把矩阵由UNIT8转换为实型
I=zeros(256,256);%给数组B赋初值
subplot(121);
imshow(B,[0,1]);%显示图像B
a=7/16;
b=3/16;
c=5/16;
d=1/16;%定义误差分配规则
for i=1:256%对每行进行处理
for j=2:256%对每列进行处理
if B(i,j)<1/2%进行阈值比较
I(i,j)=0;
else
I(i,j) = 1;
end
wc=(B(i,j)-I(i,j));%定义误差
B(i,j+1)=B(i,j+1)+wc*a;
B(i+1,j-1)=B(i+1,j-1)+wc*b;
B(i+1,j)=B(i+1,j)+wc*c;
B(i+1,j+1)=B(i+1,j+1)+wc*d;%误差分配
end
end
subplot(122);
imshow(I,[0,1]);输出结果
迭代法
迭代法是一种搜索的方法，其思想是通过最小化原图像与半色调图像的误差来寻找最佳的二值输出。由这种算法得到的半色调图像质量很好，但同时也以牺牲时间开销和计算量大为代价。
迭代法中最具代表性的是 DBS（Direct Binary Search）算法，DBS 运用视觉模型，通过不断地将像素取反和与相邻 8 邻域交换来减少半色调图像与原始连续图像的视觉误差，原理如图：
图 7 DBS 算法框图
其中
那么由初始半色调图像与原始图像通过视觉模型产生的的误差均方为：
则E可以按如下公式表示
其中，
DBS 用一个迭代的交换程序来减少误差 E ，这种算法从随机获得的半色调图像开始，按照从左到右，从上到下的顺序扫描整个半色调图像，对于每个半色调像素，评价像素取反和将其余相邻8 邻域像素交换后的影响。如果取反和交换的任何改变能减少误差，那么这种减少误差的变换被保留，反复的执行上述过程，直到整个过程没有任何改变为止，算法结束。
经过 DBS 处理后的半色调图像，几乎没有结构性纹理，而且能够很好的再现图像的丰富色调，视觉效果令人满意，如图8所示。
图 8 直接二元搜索法结果
但由于它是一种迭代算法，在不断的搜索最佳图像二值点排列的过程中，时间开销大，计算量过大导致了它很难用于实时处理场合，尤其在宽幅面打印机中的时间开销更大。针对此问题，Lieberman和 David.J 提出一种分块策略，在进行迭代前，将最先粗糙半色调图像分割成非叠加区域，使迭代发生在块区域内部，如果在某块中出现两次迭代误差变化不大，就停止此块的迭代，这样相对减少了时间开销。FarhanA.Baqai 和 JanP.Allebach 指出在误差计算过程中的自相关和互相关函数是独立于原始图像和半色调图像，故可以将其预先计算出来，建立查找表，这样做也相对减少了时间开销，但算法计算量大的问题依然没有解决。Sagar等人提出进行 DBS 算法前先对最先的粗糙半色调进行局部分块，对每一小块寻求局部最小值，采用阈值优化和搜索优化来减少计算量，但算法是否有效还有待验证。
通过上述的三种主要半色调算法，通过表1来对比一下它们的优缺点.
表 1 三种半色调技术优缺点比较
参考资料
[1] Halftone http://en.wikipedia.org/wiki/Halftone.
[2] HalfTone Screens http://demonstrations.wolfram.com/HalfToneScreens/ .
[3] Web Browser’s Guide to Digital Halftoning.
[4] 王廷婷.图像半色调技术及其进展[J].印刷质量与标准化,2010,(2):8-12.
关于Image Engineering& Computer Vision更多讨论与交流，敬请关注本博客和新浪微博songzi_tea.