乐者为王

Do one thing, and do it well.

图象的半影调和抖动技术

在介绍本讲内容之前,先提出一个问题?普通的黑白针式打印机能打出灰度图来吗?如果说能,从针式打印机的打印原理来分析,似乎是不可能的。因为针打是靠撞针击打色带在纸上形成黑点的,不可能打出灰色的点来;如果说不能,可是我们的确见过用针式打印机打印出来的灰色图象。到底是怎么回事呢?你再仔细看看那些打印出来的所谓的灰色图象,最好用放大镜看。你会发现,原来这些灰色图象都是由一些黑点组成的,黑点多一些,图象就暗一些;黑点少一些,图案就亮一些。下面这几张图就能说明这一点。

halftone-l401 图1. 用黑白两种颜色打印出灰度效果

图中最左边的是原图,是一幅真正的灰度图,另外三张图都是黑白二值图。容易看出,最左的那幅和原图最接近。由二值图象显示出灰度效果的方法,就是我们今天要讲的半影调(halftone)技术,它的一个主要用途就是在只有二值输出的打印机上打印图象。我们介绍两种方法:图案法和抖动法。

图案法(patterning)

图案法是指灰度可以用一定比例的黑白点组成的区域表示,从而达到整体图象的灰度感。黑白点的位置选择称为图案化。在具体介绍图案法之前,先介绍一下分辨率的概念。计算机显示器,打印机,扫描仪等设备的一个重要指标就是分辨率,单位是dpi(dot per inch),即每英寸点数,点数越多,分辨率就越高,图象就越清晰。让我们来计算一下,计算机显示器的分辨率有多高。设显示器为15英寸(指对角线长度),最多显示1280 * 1024个点。因为宽高比为4:3,则宽有12英寸,高有9英寸,则该显示器的水平分辨率为106dpi,垂直分辨率为113.8dpi。一般的激光打印机的分辨率有300dpi * 300dpi的,有600dpi * 600dpi的,720dpi * 720dpi。所以打出来的图象要比计算机显示出来的清晰的多。扫描仪的分辨率要高一些,数码相机的分辨率更高。

言归正传,前面讲了,图案化使用图案来表示像素的灰度,那么我们来做一道计算题。假设有一幅240 * 180 * 8bit的灰度图,当用分辨率为300dpi * 300dpi的激光打印机将其打印到12.8 * 9.6英寸的纸上时,每个像素的图案有多大?这道题很简单,这张纸最多可以打(300 * 12.8) * (300 * 9.6) = 3840 * 2880个点,所以每个像素可以用(3840 / 240) * (2880 / 180) = 16 * 16个点大小的图案来表示,即一个像素256个点。如果这16 * 16的方块中一个黑点也没有,就可以表示灰度256,有一个黑点,就表示灰度255,依次类推,当都是黑点时,表示灰度0,这样,16 * 16的方块可以表示257级灰度。比要求的8bit共256级灰度还多了一个,所以上面的那幅图的灰度级别完全能够打印出来。

这里有一个图案构成的问题,即黑点打在哪里?比如说,只有一个黑点时,我们可以打在正中央,也可以打16 * 16的左上角。图案可以是规则的,也可以是不规则的。一般情况下,有规则的图案比随即图案能够避免点的丛集,但有时会导致图象中有明显的线条。如图2中,2 * 2的图案可以表示5级灰度,当图象中有一片灰度为的1的区域时,如图3所示,有明显的水平和垂直线条。

halftone-l402 图2. 2 * 2的图案

halftone-l403 图3. 规则图案导致线条

如果想存储256级灰度的图案,就需要256 * 16 * 16的二值点阵,占用的空间还是相当可观的。有一个更好的办法是:只存储一个整数矩阵,称为标准图案,其中的每个值从0到255。图象的实际灰度和阵列中的每个值比较,当该值大于等于灰度时,对应点打一黑点。下面举一个25级灰度的例子加以说明。

halftone-l404 图4. 标准图案举例

图4中,左边为标准图案,右边为灰度为15的图案,共有10个黑点,15个白点。其实道理很简单,灰度为0时全是黑点,灰度每增加1,减少一个黑点。要注意的是,5 * 5的图案可以表示26种灰度,灰度25才是全白点,而不是24。下面介绍一种设计标准图案的算法,是由Limb在1969年提出的。以一个2 * 2的矩阵开始halftone-l4formu01,通过递归关系有halftone-l4formu02,其中2n * 2n是阵列中元素的个数,Un是一个2n * 2n 的方阵,所有元素都是1。根据这个算法,可以得到halftone-l4matrix01,为16级灰度的标准图案。M3(8 * 8阵)比较特殊,称为Bayer抖动表。M4是一个16 * 16的矩阵。根据上面的算法,如果利用M3,一个像素要用8 * 8的图案表示,则一幅N * N的图将变成8N * 8N大小。如果利用M4,就更不得了,变成16N * 16N了。能不能在保持原图大小的情况下利用图案化技术呢?一种很自然的想法是:如果用M2阵,则将原图中每8 * 8个点中取一点,即重新采样,然后再应用图案化技术,就能够保持原图大小。实际上,这种方法并不可行。首先,你不知道这8 * 8个点中找哪一点比较合适,另外,8 * 8的间隔实在太大了,生成的图象和原图肯定相差很大,就象图1最右边的那幅图一样。我们可以采用这样的做法:假设原图是256级灰度,利用Bayer抖动表,做如下处理if (g[y][x] >> 2) > bayer[y & 7][x & 7] then 打一白点 else 打一黑点。其中,x,y代表原图的像素坐标,g[y][x]代表该点灰度。首先将灰度右移两位,变成64级,然后将x,y做模8运算,找到Bayer表中的对应点,两者做比较,根据上面给出的判据做处理。

我们可以看到,模8运算使得原图分成了一个个8 * 8的小块,每个小块和8 * 8的Bayer表相对应。小块中的每个点都参与了比较,这样就避免了上面提到的选点和块划分过大的问题。模8运算实质上是引入了随机成分,这就是我们下面要讲到的抖动技术。

下面的图5就是利用这个算法,使用M3(Bayer抖动表)阵得到的,图6是使用M4阵得到的,可见两者的差别并不是很大,所以一般用Bayer表就可以了。

halftone-l405 图5. 利用M3抖动生成的图

halftone-l406 图6. 利用M4抖动生成的图

图案法源程序

抖动法(dithering)

让我们考虑更坏的情况:即使使用了图案化技术,仍然得不到要求的灰度级别。举例说明:假设有一幅600 * 450 * 8bit的灰度图,当用分辨率为300dpi * 300dpi的激光打印机将其打印到8 * 6英寸的纸上时,每个像素可以用(2400 / 600) * (1800 / 450) = 4 * 4个点大小的图案来表示,最多能表示17级灰度,无法满足256级灰度的要求。可有两种解决方案:1.减小图象尺寸,由600 * 450变为150 * 113;2.降低图象灰度级,由256级变成16级。这两种方案都不理想。这时,我们就可以采用抖动法的技术来解决这个问题。其实刚才给出的算法就是一种抖动算法,称为规则抖动(regular dithering)。规则抖动的优点是算法简单;缺点是图案化有时很明显,这是因为取模运算虽然引入了随机成分,但还是有规律的,另外,点之间进行比较时,只要比标准图案上点的值大就打白点,这种做法并不理想,因为,如果当标准图案点的灰度值本身就很小,而图象中点的灰度只比它大一点儿时,图象中的点更接近黑色,而不是白色。一种更好的方法是将这个误差传播到邻近的像素。下面介绍的Floyd-Steinberg算法就采用了这种方案。

假设灰度级别的范围从b(black)到w(white),中间值t为(b + w) /2,对应256级灰度,b = 0, w = 255, t = 127.5;设原图中像素的灰度为g,误差值为e,则新图中对应像素的值用如下的方法得到:

1
2
3
4
5
6
7
8
9
if g > t then
    打白点
    e = g - w
else
    打黑点
    e = g - b
    3 / 8 * e 加到右边的像素
    3 / 8 * e 加到下边的像素
    1 / 4 * e 加到右下方的像素

算法的意思很明白,以256级灰度为例,假设一个点的灰度为130,在灰度图中应该是一个灰点。由于一般图象中灰度是连续变化的,相邻像素的灰度值很可能与本像素非常接近,所以该点及周围应该是一片灰色区域。在新图中,130大于128,所以打了白点,但130离真正的白点255还差的比较远,误差e = 130 - 255 = -125 比较大。将3 / 8 * (-125)加到相邻像素后,使得相邻像素的值接近0而打黑点。下一次,e又变成正的,使得相邻像素的相邻像素打白点,这样一白一黑一白,表现出来刚好就是灰色。如果不传递误差,就是一片白色了。再举个例子,如果一个点的灰度为250,在灰度图中应该是一个白点,该点及周围应该是一片白色区域。在新图中,虽然e = -5也是负的,但其值很小,对相邻像素的影响不大,所以还是能够打出一片白色区域来。这样就验证了算法的正确性。其它的情况可以自己推敲。图7是利用Floyd-Steinberg算法抖动生成的图

halftone-l407 图7. 利用Floyd-Steinberg算法抖动生成的图

Floyd-Steinberg算法的源代码

bmp2txt(bmp to txt)

在讲图案化技术时,我突然想到了一个非常有趣的应用,那就是bmp2txt。如果你喜欢上BBS(电子公告牌系统),你可能想做一个花哨的签名档。瞧,这是我好朋友Casper的签名档,胖乎乎的,是不是特别可爱?

halftone-l408 图8. Casper的签名档

你仔细观察一下,就会发现,这是一幅全部由字符组成的图,因为在BBS中只能出现文字的东西。那么,这幅图是怎么做出来的呢?难道是自己一个字符一个字符拼出来的。当然不是了,有一种叫bmp2txt的应用程序(2的发音和“to”一样,所以如此命名),能把位图文件转换成和图案很相似的字符文本。是不是觉得很神奇?其实原理很简单,用到了和图案化技术类似的思想:首先将位图分成同样大小的小块,求出每一块灰度的平均值,然后和每个字符的灰度做比较,找出最接近的那个字符,来代表这一小块图象。那么,怎么确定字符的灰度呢?做下面的实验就明白了。

打开Notepad,输入字符“1”,选定该字符,使其反色。按Alt+PrintScreen键拷贝窗口屏幕。打开Paintbrush,粘贴,然后把图放到最大(*8),打开“查看” -> “缩放” -> “显示网格”菜单,如下图所示:

halftone-l409 图9. 字符“1”的灰度

这时数数字符“1”用了几个点?是22个。我想你已经明白了,字符的灰度和它所占的黑色点数有关,点越少,灰度值越大,空格字符的灰度最大,为全白,因为它一个黑点也没有;而字符“W”的灰度值就比较低了。每个字符的面积是8 * 16(宽 * 高),所以一个字符的灰度值可以用如下的公式计算(1 - 所占的黑点数 / (8 * 16)) * 255。下面是可显示的字符,及对应的灰度,共有95个。这可是casper辛辛苦苦整理出来的呦!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static char ch[95] = {
    ' ',
    '`', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '-', '=', '\\',
    'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p', '[', ']',
    'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', ';', ''',
    'z', 'x', 'c', 'v', 'b', 'n', 'm', ',', '.', '/',
    '~', '!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '_', '+', '|',
    'Q', 'W', 'E', 'R', 'T', 'Y', 'U', 'I', 'O', 'P', '{', '}',
    'A', 'S', 'D', 'F', 'G', 'H', 'J', 'K', 'L', ':', '"',
    'Z', 'X', 'C', 'V', 'B', 'N', 'M', '<', '>', '?'
};

static int gr[95] = {
    0,
    7, 22, 28, 31, 31, 27, 32, 22, 38, 32, 40, 6, 12, 20, 38, 32, 26, 20, 24, 40,
    29, 24, 28, 38, 32, 32, 26, 22, 34, 24, 44, 33, 32, 32, 24, 16, 6, 22, 26, 22,
    26, 34, 29, 35, 10, 6, 20, 14, 22, 47, 42, 34, 40, 10, 35, 21, 22, 22, 16, 14,
    26, 40, 39, 29, 38, 22, 28, 36, 22, 36, 30, 22, 22, 36, 26, 36, 25, 34, 38, 24,
    36, 22, 12, 12, 26, 30, 30, 34, 39, 42, 41, 18, 18, 22
};

bmp2txt源程序

其实利用图案化技术,还可以实现更有趣的应用,如下面这幅图,你仔细看看,贝多芬的头像是由许多个音乐符号组成的。

halftone-l410 图10. 贝多芬的头像

Comments