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

フロイド-スタインバーグ・ディザリング（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.