« ディザリング(パターン・ディザ) | トップページ | 24bit → 8bit 減色 »

誤差拡散法


リンク
画像の変換(目次ページ)
ディザ関連
パターン・ディザ
・誤差拡散法
24bit→8bit減色

【誤差拡散法 (Error Diffusion Method)】
誤差拡散法について理解する前に、
それよりも単純な『繰り越し法 (Carry Over Method)』について理解しましょう。
注)『繰り越し法』, "Carry Over Method" といのは、
私が勝手に名付けたので、世の中で通用するかどうかは知りません。


繰り越し法は次のようなアイデアです。
・累積が 255 になったらプロットする。
・プロットできなかったら次のピクセルに持ち越す。


実際には、プロットする条件を “128 以上”とした方が原画に近くなります。
すなわち、
・累積値(A)が 128 以上になったらプロットする。
・A<128 の場合は、次のピクセルに貯金(A)を繰り越す。
・A≧128 の場合は、次のピクセルに借金(255ーA)を繰り越す。

この方法によって得られたのが次の絵です。
《繰り越し法 (256色→2色)》
convert to monochrome by carry over method

《繰り越し法》
(R,G,Bそれぞれ256色→2色)
256 color to 2 color for each R,G,B by carry over method

『パターン・ディザ法』に比べて幾何学模様は無くなりましたが、
代わりに、点と点が波模様になってウネウネっとしていますね。
これを『モアレ』と呼びます。

この『繰り越し法』ではモアレがひどすぎて使用に堪えません。
『誤差拡散法』はこれを改良したものです。



『誤差拡散法』では、貯金を次の1ピクセルだけに渡すのでは無くて、
周囲のピクセルにばらまきます(押しつけます)。

『誤差拡散法』の中で代表的な Floyd-Steinberg 法では、
・直後のピクセルに 7/16 渡す。
・1ライン下の3ピクセルに それぞれ 3/16, 5/16, 1/16 で分配する。
という方法をとります。
「誤差」を「まき散らす(拡散する)」ので『誤差拡散法』と呼ばれます。
注)「Floyd-Steinberg 法」以外の方法は、
分配率がいろいろと変えられています。
分配率を変える事で、画質が変わったり、計算処理スピードが変わります。


この『誤差拡散法』によって得られたのが次の絵です。
《誤差拡散法(Floyd-Steinberg)》
(256色→2色)
convert to monochrome by error diffusion method

《誤差拡散法(Floyd-Steinberg)》
(R,G,Bそれぞれ256色→2色)
256 color to 2 color for each R,G,B by error diffusion method

パターン・ディザに比べても、ずっと金魚っぽいですね。
とても8色とは思えません。
しかし、よくよく見てみると、
(背景部分などに)波線模様『モアレ』が出ています。

この『モアレ』を低減するために、
奇数ラインと偶数ラインとで走査方向を入れ替える手法が取られます。

『モアレ』を完全に取り除く事はできませんが、低減できます。
《誤差拡散法(Floyd-Steinberg)》
(走査線を左から右、右から左)
256 color to 2 color for each R,G,B by error diffusion method

走査線を「右から左」「左から右」だけではなく、
もっと複雑(ジグザグ)にする方法もあるらしいです。
『ヒルベルト曲線』や『ペアノ曲線』という曲線で行うらしいです。

「しかし、その場合はどのピクセルに誤差を押し付けるんだろう?」
疑問です。


最後に、画質を比較しておきましょう。
(とは言っても主観比較ですが。)
「客観的評価について」
画質の比較を定量的に行う方法が無いわけでもなさそうです。
しかし、単純に PSNR を求める事を考えても、
色の階調が違うので、
エッジ検出したり、ガンマ補正掛けたりと、とんでもなく大変そう。
知覚特性もあるだろうし。
(そんな理由で、主観比較のみです。)
《元データ (24bit RGB)》
source data (24 bit color)

《パターン・ディザ》
(R,G,Bそれぞれ256色→2色)
256 color to 2 color for each R,G,B by pattern dither

《誤差拡散法(Floyd-Steinberg)》
(走査線を左から右、右から左)
256 color to 2 color for each R,G,B by error diffusion method

代表的な誤差拡散パターン
【Floyd-Steinberg】
  curr 7/16
3/16 5/16 1/16

【JaJuNi (Jarvis, Judice & Ninke)】
    curr 7/48 5/48
3/48 5/48 7/48 5/48 3/48
1/48 3/48 5/48 3/48 1/48

【Stucki】
    curr 8/42 4/42
2/42 4/42 8/42 4/42 2/42
1/42 2/42 4/42 2/42 1/42

【Burkes】
    curr 4/16 2/16
1/16 2/16 4/16 2/16 1/16

|

« ディザリング(パターン・ディザ) | トップページ | 24bit → 8bit 減色 »

画像フォーマット」カテゴリの記事

コメント

大学で最適化について研究している学生です.
誤差拡散法について調べていたらこのブログに至りました.
よろしければ《元データ (24bit RGB)》の画像を研究に使わせてほしいのですが,よろしいでしょうか.
ご返事をメールアドレスまでしてくださると助かります.

投稿: 学生 | 2012年2月17日 (金) 17時11分

モアレ対策にはもう一つ。オーバーサンプリングがあります。
ループの開始位置をマイナスから始めて、座標の選定は絶対値で取得し、擬似的な鏡あわせのデータで座標ゼロから描画します。
---- 簡略一例 ----
for dy=-30 to 255
cy=abs(dy)
for cx=0 to 255
cl=point(cx,cy)
---- 以下省略 ----

誤差のサンプリングに適度な値が入るので、いい感じに散らばる可能性を高めます。

投稿: | 2017年4月25日 (火) 15時52分

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 誤差拡散法:

« ディザリング(パターン・ディザ) | トップページ | 24bit → 8bit 減色 »