フロイド-スタインバーグ・ディザリング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
RGB 24bits palette sample image.jpg RGB 24bits palette sample image - 3-bit RGB.png
24ビットRGB画像(左)とそれを3ビットRGB(8色)画像に変換する際にフロイド-スタインバーグ・ディザリングを施した例(右)
ダビデ像の画像にフロイド-スタインバーグ・ディザリングを施した例

フロイド-スタインバーグ・ディザリングFloyd–Steinberg dithering)は画像用ディザリングアルゴリズムであり、1976年、ロバート・フロイドと Louis Steinberg が発表した。画像操作関係のソフトウェアで広く用いられており、例えば最大256色までしか使えないGIF形式への変換の際に使われている。

ピクセル量子化誤差をそれに隣接するピクセル群に拡散させることでディザリングを実現するアルゴリズムである。隣接ピクセルへの誤差の分配は次のようになる。


\frac{\displaystyle 1}{\displaystyle 16}
\begin{bmatrix}
 & * & 7 \\
3 & 5 & 1 \\
\end{bmatrix}

星印 (*) が現在見ているピクセルを表している。

このアルゴリズムでは、画像を左から右、上から下にスキャンし、ピクセルの値を1つずつ量子化していく。毎回の量子化誤差は隣接するピクセル群に分配されるが、既に量子化が済んだピクセルの値は変更しない。これにより、あるピクセルの値が量子化によって切り下げられたら、次のピクセルにその誤差が反映されて切り上げられることになり、全体として量子化誤差がゼロに近づくことになる。

実装によっては、水平のスキャン方向を毎回逆にすることもある(蛇行式または牛耕式)。

以下に擬似コードを示す。

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

元のピクセル値が発色可能な色と色のちょうど中間だった場合、誤差拡散係数は市松模様のようなパターンを生成するように設定されている。例えば50%の灰色は白と黒の市松模様となる。最適なディザリングにするには、丸め誤差が結果に影響することを防止するため、量子化誤差を十分な精度で求める必要がある。

例えば色深度を16ビットから8ビットにする場合、find_closest_palette_color() は次のように単純な丸めをすればよい。

find_closest_palette_color(oldpixel) = oldpixel / 256 * 256

参考文献[編集]

  • Floyd–Steinberg Dithering (Graphics course project, Visgraf lab, Brazil)
  • R.W. Floyd, L. Steinberg, An adaptive algorithm for spatial grey scale. Proceedings of the Society of Information Display 17, 75–77 (1976).

外部リンク[編集]

  • PTRANS Stand-alone ANSI-C programming language implementation.