Image dithering－以256色模式顯示64K色或更高色深的影像

許多年前 (個人電腦還沒有 Windows 的時候)，曾自電腦圖學抄錄了一段 Floyd-Steinberg error diffusion 摘要在筆記本上，那是一種關於 2D 影像的演算方法，讓色彩深度受限制的顯示設備可以極佳的效果來呈現色彩深度較高的影像。例如，在 VGA 256 色模式顯示高彩 (high color, 16-bits) 或全彩 (true color, 24-bits) 影像。在那個大小事多半得自理的 PC/DOS 年代曾依此以 C 程式語言實作處理過由影像擷取卡擷取的高彩影像，今日或因高畫質的軟硬體設備已普及而不太需要自撰程式處理，然原理方法還約略記得，今藉 Javascript 並 html 再做一個簡易測試以複習整理。

色彩深度的影響

呈現影像的品質除了考慮解析度 (resolution, 呈現影像的像素數量) 外還有色彩深度 (color depth, 單一像素可以呈現出的顏色數量)，而描述一個像素 (pixel) 的位元數即表示色彩深度。例如， 8-bits 可呈現 256 色，16-bits 可呈現 65536 色，而 24-bits 則可呈現超過 1,600 萬色 。縱使解析度足夠，但倘若顯示設備的色彩深度不足，此時影像的像素原始顏色無法被精確地呈現，而會以較接近的顏色被顯示出來，如此高色彩深度影像中一些漸層色通常會被犧牲而呈現像帶狀的色塊，除了影響觀看的感覺，影像中的細節也會消失不見。

VGA 256 color palette

色彩模型

電腦顯示設備多以紅、綠、藍 (Red, Green, Blue) 三原色光為主要色彩模型 (color model)，有時在色彩處理與演算上若轉換成色相、飽和度、明度 (Hue, Saturation, Value) 會更得方便，因為較為直觀。例如在 VGA 256 indexed colors 的模式中，觀察其預設色盤的顏色會發現它就是一個以 HSV 色彩模型而排列的。
所謂 indexed color 是指影像的像素值並不直接描述色彩 RGB 值，而是一個索引值指向一個色盤 (palette) 的位置，設備會從而找出真正描述該像素的 RGB 值以顯示顏色。VGA 256 色模式的預設色盤顏色除去前面 32 色 (16 色相容 CGA，16 色灰階) 與末尾 8 色外，中間的 216 色可看作為 9 組 24 色的 HSV 色輪依色相次序排列，各組間又以飽和度/明度的差異依次排列。

處理色深不足的方法

Dither 是一類極有意思的數位信號處理技術，藉由刻意加入用來減少量化誤差的雜訊，讓人感官覺得數位採樣後再還原的視訊或音訊失真減少了。自然界的訊號大多是連續性的，採樣頻率可以使用兩倍於訊號最大頻率來捕獲資訊，但訊號還原時振幅量化卻是重要的因子，我們的設備表示振幅量化的位元數有限，量化誤差由此產生而讓人察覺到訊號失真。
色彩深度即是視覺訊號的振幅量化數值，Floyd-Steinberg Dithering 的原理是將每一像素的色深量化誤差散佈到鄰近的其他像素，人類視覺會混合相鄰像素的色彩而感覺到影像失真程度減少了。

以一幅高彩原始影像 (16-bits, red:green:blue=6:6:4) 執行測試，分別以三種方式顯示：
一、以與影像相符的色深 (65536 colors) 可完整顯示該影像所有顏色。

高彩色深顯示結果

二、限制色深為 256 indexed colors，不做 dithering 處理，明顯可見因色深受限而產生量化誤差的結果。

256 色 (no dithering) 顯示結果

三、以 Floyd-Steinberg Dithering 方法處理影像後顯示於 256 indexed colors，看得出來量化誤差經分散，結果已非常逼近高色深的顯示結果了。

256 色 dithering (Floyd-Steinberg) 顯示結果

dithering 部份程式碼

//-- read the raw image pixels,
//-- the raw pixel is in 16-bits color depth r:g:b=6:6:4
var img= new Uint16Array(reader.result);
//-- prepare 2 lines for dithering process
var lines= new Array(2);
lines[0]= new Array(640);
lines[1]= new Array(640);
for(var y= 0; y < 480; ++y){
  var x;
  //-- copy a line of pixels
  for(x= 0; x < 640; ++x){
    var i= x + 640 * y;
    //-- convert raw pixel to RGB color (24-bits)
    lines[1][x]= P664.rgb(img[i]);
  }
  if(y > 0){  //-- display and dithering
    for(x= 0; x < 640; ++x){
      //-- convert RGB to HSV
      var hsv= lines[0][x].toHSV();
      //-- get the approximate color
      var rgb= Color256.mappedRGB(hsv);
      //-- set the canvas context fill style color and draw the pixel
      ctx.fillStyle= rgb.toCSS();
      ctx.fillRect(x, y-1, 1, 1);
      //-- calculate the quantization error
      var errp= {};
      errp.red= lines[0][x].red - rgb.red;
      errp.green= lines[0][x].green - rgb.green;
      errp.blue= lines[0][x].blue - rgb.blue;
      //-- distribute the error to neighboring pixels
      lines[1][x].red= clamp(lines[1][x].red + 5*errp.red/16, 0, 255);
      lines[1][x].green= clamp(lines[1][x].green + 5*errp.green/16, 0, 255);
      lines[1][x].blue= clamp(lines[1][x].blue + 5*errp.blue/16, 0, 255);
      if(x < 639){
        lines[0][x+1].red= clamp(lines[0][x+1].red + 7*errp.red/16, 0, 255);
        lines[0][x+1].green= clamp(lines[0][x+1].green + 7*errp.green/16, 0, 255);
        lines[0][x+1].blue= clamp(lines[0][x+1].blue + 7*errp.blue/16, 0, 255);
        lines[1][x+1].red= clamp(lines[1][x+1].red + errp.red/16, 0, 255);
        lines[1][x+1].green= clamp(lines[1][x+1].green + errp.green/16, 0, 255);
        lines[1][x+1].blue= clamp(lines[1][x+1].blue + errp.blue/16, 0, 255);
      }
      if(x > 0){
        lines[1][x-1].red= clamp(lines[1][x-1].red + 3*errp.red/16, 0, 255);
        lines[1][x-1].green= clamp(lines[1][x-1].green + 3*errp.green/16, 0, 255);
        lines[1][x-1].blue= clamp(lines[1][x-1].blue + 3*errp.blue/16, 0, 255);
      }
    }
  }    
  lines[0]= lines[1].slice();
  //-- display the last line
  if(y == 479)
    for(x= 0; x < 640; ++x){
      ctx.fillStyle= Color256.mappedRGB(lines[0][x].toHSV()).toCSS();
      ctx.fillRect(x, y, 1, 1);
  }