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

フロイド-スタインバーグ・ディザリング（Floyd–Steinberg dithering）は画像用ディザリングアルゴリズムであり、1976年、ロバート・フロイドと Louis Steinberg が発表した。画像操作関係のソフトウェアで広く用いられており、例えば最大256色までしか使えないGIF形式への変換の際に使われている。各ピクセルの量子化誤差をそれに隣接するピクセル群に拡散させることでディザリングを実現するアルゴリズムである。隣接ピクセルへの誤差の分配は次のようになる。: <math>\\frac{\\displaystyle 1}\\begin & * & 7 \\\\3 & 5 & 1 \\\\\\end</math>星印 (*) が現在見ているピクセルを表している。このアルゴリズムでは、画像を左から右、上から下にスキャンし、ピクセルの値を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_