基于AS3.0的图像抖动实现

Posted on Apr 2, 2013

不知当初自己出于什么目的，OneNote 里留了一条关于 Floyd–Steinberg dithering 的笔记。好奇之余，打开链接看了一下，方才想起这个当初让我觉得新奇的古老算法。

概述

余忆童稚时，能张目对日，明察秋毫……”如果你对过去黑白报纸的图片仔细观察过的话，一定会发现，那些黑白照片由很多圆形或方形的图形组成。是的，那就是半色调（Halftone）和抖动（Dither ）技术。

Halftone

半色调（Halftone）是指为了模拟出连续调影像（色阶）的视觉感觉，一般用墨点（半色调网点）的大小或频率的改变，来模拟明暗的变化。半色调广泛应用于报刊出版等领域，当年那些黑白出版物上尤其常见，现在的牛奶包装上也能看出来。

阈值法（Thresholding）

当像素值大于设定阈值时，输出为亮点，否则输出为暗点，从而实现二值化。经过处理的图像往往失去细节，缺乏层次感。下图所示的就是二值化的图像。 lena_binary

模式法（patterning）

相对阈值法的二值化处理，这种方法使用一个黑白像素矩阵来表示一个像素点，这个矩阵里黑白点不同组合实现该区域的亮度变化，模拟这个像素点的不同灰度值，从而实现图像的灰度显示。

lena_gray

一个2阶矩阵，有4个点的位置，可能的组合为：4黑，1黑3白，2黑2白，3黑1白，4白。因此可以用来表示5级灰度。当图象中有一片灰度为的1的区域时，有明显的水平和垂直线条。

抖动（dithering）

patterning 方法虽然可行，但是消耗空间比较大，表示的灰度等级越高，需要的矩阵越大，256级灰度就需要16×16的矩阵空间来表示一个像素点。更坏的情况是，即使使用patternning，依然得不到要求的灰度等级。有没有一种只占用很少空间就可以表示的方法呢？显然有，这个时候抖动算法就派上用场了。

误差扩散（Error diffusion）

这个过程中用到了误差扩散算法，误差扩散的意思就是让误差扩散， ;-) 就是像素点在色彩深度降低时，产生的时误差扩散到其周围像素上。例如：当一个像素点灰度值为120，如果转换为16级灰度图像，120/16=7.5，取整后为7，误差为0.5，那么这0.5的误差就要按一定的算法规则扩散到其周围像素上。

Floyd–Steinberg 抖动算法

Floyd–Steinberg 是比较常见的抖动算法，误差扩散的规则用矩阵描述为：

$${1 \over 16} \begin{bmatrix} &* &7 \\ 3 &5 &1 \end{bmatrix}$$

* 为当前计算的像素点，数字为其周围像素点的误差分配。算法伪码为：

	for each y from top to bottom
	   for each x from left to right
		  oldpixel := pixel[x][y]
		  newpixel := find_closest_palette_color(oldpixel)
		  pixel[x][y] := newpixel
		  quant_error := oldpixel - newpixel
		  pixel[x+1][y] := pixel[x+1][y] + 7/16 * quant_error
		  pixel[x-1][y+1] := pixel[x-1][y+1] + 3/16 * quant_error
		  pixel[x][y+1] := pixel[x][y+1] + 5/16 * quant_error
		  pixel[x+1][y+1] := pixel[x+1][y+1] + 1/16 * quant_error

代码实现

Ralph Hauwert 很久以前就已经在ActionScript上完整地实现了

/**
 * applyFloydSteinberg(bitmapData:BitmapData, levels:int);
 * 
 * Floyd-Steinberg dithering is an image dithering algorithm 
 * first published in 1976 by Robert W. Floyd and Louis Steinberg.
 * Using error diffusion, this form of dithering is visually much better then ordered diffusion like Bayer's.
 * R.W. Floyd, L. Steinberg, "An adaptive algorithm for spatial grey scale". 
 * Proceedings of the Society of Information Display 17, 75–77 (1976).
 */
private static function applyFloydSteinberg(bitmapData:BitmapData, levels:int) : void {
var lNorm:Number = 255/levels;

//The FS kernel...note the 16th. Optimisation can still be done.
  var d1:Number = 7/16;
  var d2:Number = 3/16;
  var d3:Number = 5/16;
  var d4:Number = 1/16;
  
  var c:int, nc:int, lc:int;
  var r:int,g:int,b:int;
  var nr:int, ng:int, nb:int;
  var er:int, eg:int, eb:int;
  var lr:int, lg:int, lb:int;
  var x:int = 0, y:int = 0;
  
  for(y=0; y<bitmapData.height;y++){
    for(x=0; x<=bitmapData.width;x++){
      //Retrieve current RGB value.
      c = bitmapData.getPixel(x, y);
      r = c >> 16 &0xFF;
      g = c >> 8 & 0xFF;
      b = c & 0xFF;
      
      //Normalize and scale to the number of levels.
      //basically a cheap but suboptimal form of color quantization.
      nr = Math.round((r/255) * levels) * lNorm;
      ng = Math.round((g/255) * levels) * lNorm;
      nb = Math.round((b/255) * levels) * lNorm;
      
      //Set the current pixel.
      nc = nr<<16|ng<<8|nb;
      bitmapData.setPixel(x, y, nc);	
      
      //Quantization error.
      er = r-nr;
      eg = g-ng;
      eb = b-nb;
      
      //Apply the kernel.
      //+1,0
      lc = bitmapData.getPixel(x+1, y);
      lr = (lc>>16&0xFF) + (d1*er);
      lg = (lc>>8&0xFF) + (d1*eg);
      lb = (lc&0xFF) + (d1*eb);
      //Clip & Set
      lr < 0 ? lr = 0: lr > 255 ? lr = 255 : lr;
      lg < 0 ? lg = 0: lg > 255 ? lg = 255 : lg;
      lb < 0 ? lb = 0: lb > 255 ? lb = 255 : lb;
      bitmapData.setPixel(x+1, y, lr<<16 | lg << 8 | lb);
      
      //-1,+1
      lc = bitmapData.getPixel(x-1, y+1);
      lr = (lc>>16&0xFF) + (d2*er);
      lg = (lc>>8&0xFF) + (d2*eg);
      lb = (lc&0xFF) + (d2*eb);
      //Clip & Set
      lr < 0 ? lr = 0: lr > 255 ? lr = 255 : lr;
      lg < 0 ? lg = 0: lg > 255 ? lg = 255 : lg;
      lb < 0 ? lb = 0: lb > 255 ? lb = 255 : lb;
      bitmapData.setPixel(x-1, y+1, lr<<16 | lg<<8 | lb);
      
      //0,+1
      lc = bitmapData.getPixel(x, y+1);
      lr = (lc>>16&0xFF) + (d3*er);
      lg = (lc>>8&0xFF) + (d3*eg);
      lb = (lc&0xFF) + (d3*eb);
      //Clip & Set
      lr < 0 ? lr = 0: lr > 255 ? lr = 255 : lr;
      lg < 0 ? lg = 0: lg > 255 ? lg = 255 : lg;
      lb < 0 ? lb = 0: lb > 255 ? lb = 255 : lb;
      bitmapData.setPixel(x, y+1, lr<<16 | lg<< 8 | lb);
      
      //+1,+1
      lc = bitmapData.getPixel(x+1, y+1);
      lr = (lc>>16&0xFF) + (d4*er);
      lg = (lc>>8&0xFF) + (d4*eg);
      lb = (lc&0xFF) + (d4*eb);
      //Clip & Set
      lr < 0 ? lr = 0: lr > 255 ? lr = 255 : lr;
      lg < 0 ? lg = 0: lg > 255 ? lg = 255 : lg;
      lb < 0 ? lb = 0: lb > 255 ? lb = 255 : lb;
      bitmapData.setPixel(x+1, y+1, lr<<16 | lg << 8 | lb);		
    }
  }
}

应用示例

Ralph Hauwert demo的基础上做了少量的修改，性能有所改善之外，为方便比较增加了一个保存图像的功能。

总结

半色调抖动算法本身并不复杂，但是实用性非常高，误差扩散的思想值得学习，也很有意思。最近接触了不少关于图像处理方面的算法，大多属于简单实用的类型，另一方面没有系统地学习图像处理，多数是看到有意思的算法，自己研究学习，纯属自娱自乐。关于Demo的优化，实际上也只用到了两句代码：

  bitmapdata.lock();
  // do some pixel manipulation...
  bitmapdata.unlock();

性能提升明显，差不多提高了一倍。

Web逐渐步入3D时代，图像处理方面的应用应该也会更加广泛，Web图像处理和Web 3D 还是很有前景的。

p.s. 示例里测试图是有一段值得一书故事的，下次再说了。

参考资料