画像のディザリング — Floyd-Steinberg 1976 から GIF 256 色・ASCII アートの量子化まで

連続階調 (continuous tone) の画像を、限られた色や輝度で再現する処理を「量子化 (quantization)」と呼びます。素朴な量子化 = 「最も近い値に丸める」だと、グラデーションがバンディング (色の段差) として見え、ベタ塗りの帯ができてしまいます。

ディザリングは、量子化誤差を空間的に分散させることでバンディングを「ノイズ」に置き換える技法です。人間の視覚系は低空間周波数のバンディングは敏感に検知する一方、高空間周波数のノイズには鈍感なので、結果として自然な階調に見えます。

用途としては:

• GIF 化 (256 色化): フルカラー → パレット色への変換
• 白黒2値印刷 (新聞・FAX): グレースケール → 黒/白
• ASCII アート: 256 階調 → 70 文字程度
• 低ビット表示: 16-bit / 8-bit ディスプレイ
• 画像減色保存: PNG-8 / WebP lossless パレット

1973 年、Eastman Kodak の Bryce E. Bayer (デジタルカメラの「Bayer 配列」と同一人物) は IEEE ICC 1973 で "An Optimum Method for Two-Level Rendition of Continuous-Tone Pictures" を発表。あらかじめ計算しておいた閾値の行列を画像にタイリングして比較する手法を提案しました。

4×4 の標準 Bayer 行列 (D₄) は次のとおりです (0-15 を 0-255 にスケールして使う)。

D₄ = | 0  8  2 10 |
     |12  4 14  6 |
     | 3 11  1  9 |
     |15  7 13  5 |

各ピクセル (x, y) について:

threshold = (D₄[y mod 4][x mod 4] + 0.5) / 16
output    = (input / 255 > threshold) ? white : black

Bayer 行列は再帰的に拡張でき、2×2 / 4×4 / 8×8 / 16×16 と細かくしていけます。

D_(2n) = | 4·D_n         4·D_n + 2·U_n |
         | 4·D_n + 3·U_n 4·D_n + 1·U_n |   (U は全要素 1 の行列)

順序型ディザの最大の利点は各ピクセルの計算が完全に独立であることです。並列処理・GPU 実装に向き、フレームをまたいでもパターンが揺れないのでビデオ向きでもあります。一方で規則的なクロスハッチ模様が目に見えるという欠点があり、写真の高品質変換には不利です。

1976 年、スタンフォード大学の Robert W. Floyd と Louis Steinberg は SID Symposium Proceedings に "An Adaptive Algorithm for Spatial Greyscale" を発表。各ピクセルの量子化誤差を、まだ処理していない隣接ピクセルに「拡散」させる手法を提案しました。

処理順は左→右、上→下のラスター順。あるピクセル (x, y) を量子化したときの誤差 ε = 元値 − 出力値 を、4つの近傍に重み付き分配します。

          *   7/16
3/16 5/16 1/16

* = 処理中の現在ピクセル
誤差を:
  右       (x+1, y  ) に 7/16
  左下     (x-1, y+1) に 3/16
  下       (x  , y+1) に 5/16
  右下     (x+1, y+1) に 1/16
分配する。

分母が 16 に揃っているのは整数演算で実装しやすいよう Floyd と Steinberg が選んだ数字です。重みの合計は (7+3+5+1)/16 = 16/16 = 1 なので、誤差は失われずに後続のピクセル群に均等に流れていきます。

結果は順序型と比べて規則性のないノイズ状の分布になり、写真などの自然画像で圧倒的に高品質です。GIMP の「色の量子化」、Photoshop の "Diffusion" モード、ImageMagick の -dither FloydSteinberg はすべてこのアルゴリズムです。

誤差拡散法は分配先のセル数と重みのバリエーションで多くの派生があります。代表的なものを並べると:

Atkinson は Apple の Bill Atkinson (HyperCard / MacPaint 開発者) が初代 Macintosh 向けに考案。誤差の 1/4 を意図的に「捨てる」ため、コントラストが強調されるのが特徴。1984 年の Mac の白黒画面に味わいを与えたディザは現在でもレトロ調の表現として愛用されています。

Jarvis-Judice-Ninke はベル研究所の Jarvis らが Floyd-Steinberg と同年に発表した拡張版で、3 行に分散する分品質が高い反面、計算量が増えます。

Floyd-Steinberg は元々グレースケール用に考えられましたが、RGB 各チャンネルに独立に適用するか、3 次元色空間で「最近傍パレット色」を選ぶ拡張で容易にカラー対応します。

カラー量子化の標準的な流れ (libimagequant / pngquant の実装):

1. 画像を解析してパレット 256 色を決定する (Median Cut, K-means, Octree など)
2. 各ピクセルを RGB 距離で最近傍のパレット色に量子化
3. 誤差ベクトル (ΔR, ΔG, ΔB) を Floyd-Steinberg で拡散
4. 次のピクセルでは入力に拡散誤差を加算してから量子化

距離計算には素朴な L² ノルム (sqrt(ΔR²+ΔG²+ΔB²)) より、人間の感度を反映した CIEDE2000 や OKLab 距離を使うとさらに自然な減色になります。本サイトの CSS color-mix() と OKLCH の記事で OKLab の理論を扱っています。

GIF89a の実装では、本サイトの GIF 作成ツールでも採用している gif.js (MIT) が NeuQuant (1994) 系のニューラルネット量子化 + Floyd-Steinberg ディザを組み合わせています。

ASCII アート変換は本質的に「8-bit 輝度 (0-255) を文字数 N (例: 70) のステップに量子化」する処理です。素朴に行うと階調の断面でバンディングが目立ちます。

本サイトの ASCII アートコンバータはゼロ依存実装で、輝度計算は ITU-R BT.601 標準式 (Y = 0.299R + 0.587G + 0.114B) を使い、文字インデックスは:

idx = floor((255 - Y) / 255 × (charSet.length - 1))

誤差拡散はあえて入れていません。等幅フォントの ASCII では文字間の隙間がディザの「自然さ」を阻害することが多く、また文字密度自体が一種のディザ機能を兼ねるためです。一方、ピクセル単位で出力するレトロ調 ASCII アート (例: Pixoor の 8-bit エフェクト) では Floyd-Steinberg を併用することで階調の連続性が大幅に改善します。

Floyd-Steinberg は左→右に処理するため、画像の左側で発生した誤差が右側に流れ込みます。一様なグラデーションでは問題ありませんが、大きな単色領域では誤差が一方向に蓄積し、ピクセル境界付近で「すじ」(serpentine artifacts) として見えることがあります。

対策として:

• 蛇行スキャン (serpentine scan): 偶数行は左→右、奇数行は右→左で処理。誤差の流れる方向が交互になり、すじが目立たない
• Riemersma ディザ (1998): ヒルベルト曲線に沿って処理。2 次元的な相関のみが残る
• blue noise マスク: 順序型だが Bayer のような規則性のない高品質マスクを事前計算 (Ulichney 1987)

蛇行スキャンは GIMP / Photoshop の標準的な実装に含まれており、追加コストもほぼゼロなので無効化する理由はあまりありません。

2020 年代に入ってもディザリングは廃れていません。むしろ用途が広がっています。

• HDR → SDR 変換: 16-bit から 8-bit にトーンマッピングするときバンディングが目立つので blue noise を併用
• 3D レンダリング: Unreal Engine / Unity の Temporal Anti-Aliasing でフレーム間のディザを使う
• WebGPU シェーダ: GPU で順序型ディザを並列実行、UI のグラデーション描画で活用
• 機械学習: Neural Network 内の量子化 (INT8 推論) でも誤差拡散の発想が応用されている

50 年前の Floyd-Steinberg や 50 年前以上前の Bayer 行列が、現代でも GPU パイプラインや AI モデル推論の中で生き続けているのは、これらが情報理論的に最適に近いからです。

• ディザリング = 量子化誤差を空間に分散して滑らかに見せる技法
• Bayer 1973 の順序型: 行列タイリング、並列実装に強い
• Floyd-Steinberg 1976 の誤差拡散: 4 セルに 7/3/5/1 で分配
• 派生: Jarvis-Judice-Ninke / Stucki / Burkes / Sierra / Atkinson
• カラーは RGB 独立 or 3次元最近傍 + パレット決定 (Median Cut 等) と組み合わせ
• 蛇行スキャンで誤差拡散の「すじ」が低減
• HDR・WebGPU・AI 量子化など、現代でも応用範囲が広い