誤差拡散法 – AS3.0

誤差拡散法。
前回紹介したディザ法と同じく疑似階調表現アルゴリズムのひとつです。
こちらはディザ法よりも一般的に品質が良いとされています。

誤差拡散法の基本的な考え方は、減色処理によって生じた誤差を近傍の画素に拡散させ、画像全体としての誤差を最小にしようとする手法になります。
フルカラー画像を限定されたカラーパレットで表現された画像への変換を行う場合、元の色に最も近い色をパレット内から選び出し、その色に変換していくことで減色処理を行います。この変換を行う時に、元の色がパレット内に存在しない限り誤差が発生するので、これを周囲の画素に拡散させることで全体としての誤差を小さくします。
一般に誤差拡散法ではFloyd&Steinberg型が有名で、デジタルカメラやイメージスキャナ、プリンタなどで広く使われています。
この手法は右、左下、下、右下の4画素に比率を変えて誤差を拡散させます。

　○ 　　●　　7/16
1/16　3/16　5/16
(●：注目画素)

ActionScriptでの例は以下のようになります。
・RGB256階調を16階調に減色

// Floyd&Steinberg型 誤差拡散法

private function errorDiffusion(img:IplImage):void{
  //カラーパレット(RGB各16色)
  var paletteR:Vector.<int> = Vector.<int>([0,0,255,255,0 0,255,255,128,0,128,128,0,0,128,64]);
  var paletteG:Vector.<int> = Vector.<int>([0,0,0,0,255,255,255,255,128,0,0,0,128,128,128,64]);
  var paletteB:Vector.<int> = Vector.<int>([0,255,0,255,0,255,0,255,128,128,0,128,0,128,0,64]);
  //2行分のバッファ確保 (+2は両端2画素分)
  var mx:int = img.width + 2;
  var errorR:Vector.<int> = new Vector.<int>(mx*2, true);
  var errorG:Vector.<int> = new Vector.<int>(mx*2, true);
  var errorB:Vector.<int> = new Vector.<int>(mx*2, true);
  var r:int = 0, g:int = 0, b:int = 0;
  var re:int = 0, ge:int = 0, be:int = 0;
  var ee:int = 0, est:int = 999999, bst:int = 0;
  var adr:int = 0;
  for(var y:int=0;y<img.height;y++){
    for(var x:int=0;x<img.width;x++){
      adr = x+1;
      //誤差加算
      r = img.imageData[img.widthStep*y + x*4 + 1] + (errorR[adr]/16);
      g = img.imageData[img.widthStep*y + x*4 + 2] + (errorG[adr]/16);
      b = img.imageData[img.widthStep*y + x*4 + 3] + (errorB[adr]/16);
      // 減色 (パレットから一番近い色を選ぶ)
      bst = 0;
      est = 999999; //十分大きな値
      for(var i:int=0;i<16;i++){
        ee = Math.pow(r - paletteR[i], 2) + Math.pow(g - paletteG[i], 2) + Math.pow(b - paletteB[i], 2);
        if(est>ee){
          bst = i;
          est = ee;
        }
      }
      //誤差算出
      re = r - paletteR[bst];
      ge = g - paletteG[bst];
      be = b - paletteB[bst];      
      //誤差拡散
      //右へ
      errorR[adr+1] += re*7;
      errorG[adr+1] += ge*7;
      errorB[adr+1] += be*7;
      //左下へ
      errorR[adr+mx-1] += re*3;
      errorG[adr+mx-1] += ge*3;
      errorB[adr+mx-1] += be*3;
      //下へ
      errorR[adr+mx] += re*5;
      errorG[adr+mx] += ge*5;
      errorB[adr+mx] += be*5;
      //右下へ
      errorR[adr+mx+1] += re*1;
      errorG[adr+mx+1] += ge*1;
      errorB[adr+mx+1] += be*1;
      
      img.imageData[img.widthStep*y + x*4 + 1] = paletteR[bst];
      img.imageData[img.widthStep*y + x*4 + 2] = paletteG[bst];
      img.imageData[img.widthStep*y + x*4 + 3] = paletteB[bst];
    }
    //バッファずらし
    for(var j:int=0;j<mx;j++){
      errorR[j] = errorR[j+mx];
      errorG[j] = errorG[j+mx];
      errorB[j] = errorB[j+mx];
      errorR[j+mx] = 0;
      errorG[j+mx] = 0;
      errorB[j+mx] = 0;
    }
  }     
}

・出力結果

Flashが表示されない人はこちら→ErrorDiffusion.swf

やや冗長ですが、わかりやすさを意識して書きました。

下部に拡散させた誤差は下部行の処理が終わるまで保持しておかなければなりません。そのため誤差を格納するバッファを用意して記録していきます。処理の終わった画素に対する誤差は保持する必要はないので、バッファは2行分だけ用意します。

また今回は、あらかじめ用意したカラーパレットを利用していますが、適応的にカラーパレットを生成するアルゴリズム(メディアンカット法等)がいくつか提案されています。誤差拡散法はそれらの減色アルゴリズムと併用して利用するのが一般的です。以前、電子透かし関連の研究で減色アルゴリズムを基礎として学びましたが、画像処理入門レベルをちょっと越えている気がしたのでここでは説明を省きます。

誤差拡散法はディザ法と比べると処理速度は遅いですが、品質では良好な結果が得られる場合が多いです。
ただ前回も言いましたが、FlashのBitmapDataは各チャンネル8ビット固定なのでデータ量は削減できません。
これも画像効果の一つということで。。

誤差拡散法 – AS3.0

あわせて読む:

コメントを残す