カラービットマップ画像を白黒2値(1bit)に誤差拡散法(Sierra Lite)でディザリング

GR-SAKURA(KAEDEも)とmbed用にメモリ液晶のライブラリを書いて公開しました。
メモリ液晶直接駆動ライブラリGR-SAKURA版はRenesasRulzに置いてます
mbed版はmbedのリポジトリに置いてます(サンプルプログラムはSHARP_MEMORYLCD_WJ)
mbed版はSDカードスロットが無く、RAMサイズが少ないボードが多いので実装を見送りましたが
GR-SAKURA版にはSDカードスロットが付いていてRAMサイズがデカイので
SDカードからBMP画像を読み込んで白黒2値で表示する関数を実装しています。
この関数を実装するにあたり、誤差拡散法のアルゴリズムを調べたのですが、今回はそれの話。


bmp1bitscal.png
bmp1bitdither.png

まず、白黒2階調のディスプレイに画像を表示しようとするにあたり、
「カラー画像なんか色落として、それを2値化したら終わりやろww余裕余裕www」
とか考えてる人に説明すると、カラー画像を読み込んで、色を落として2値化しただけではこうなります。

まぁなんとなくわからなくはないけど、濃淡がわからず、もうアレですね・・・。
そんな単純なものはアルゴリズムとしてはゴミです。
では、ゴミにならないようにするには、白黒2値でなんとか濃淡を表さなければなりません。
これを実現するのが誤差拡散・ディザリングです。


誤差拡散アルゴリズムはWikipediaの記事に示されているように、たくさんのパターンが既に開発されています。
一般的なプログラムの勉強だと、フロイド-スタインバーグ・ディザリング(Floyd–Steinberg dithering)
というものを多用するそうで、これに関する日本語の記事もたくさん見つかります。
しかし、Wikipediaの記事を読み進めると、
「Jarvis, Judice, and Ninke dithering」
高速化・改良した「Sierra dithering」
高速化した「Two-row Sierra」
をさらに高速化した「Sierra Lite」
というものが開発されています。 パワーアップしすぎ。 おまえらサイヤ人か。
この「Sierra Lite」が暫定最強かどうかはわかりませんが、今回はこれを採用することにしました。
一般的に多用される「Floyd–Steinberg dithering」より「Sierra Lite」が優れている点は

  • 誤差確定用配列のピクセルが1個少ない
  • 単純なかんじがしてわかりやすい(小学生並の感想)

ぐらいでしょうか。ぶっちゃけ変わらんかもしれん


Sierra Liteのアルゴリズム

Sierra Liteのアルゴリズムを日本語でわかりやすく簡潔に書くと、

  1. 画像のピクセル情報を左上から右下に向かって読む
  2. 現在の1ピクセルの明るさを取得
  3. 現在の1ピクセルの明るさに求めた誤差を加算
  4. 算出した明るさが規定値以上ならそのピクセルは白で、誤差を消すために明るさをゼロにする。そうじゃなかったらそのピクセルは黒とする
  5. 算出した明るさから、近隣ピクセルの誤差を求める(右隣:明るさ×0.5、左下:明るさ×0.25、真下:明るさ×0.25)
  6. 次のピクセルへ

こんなかんじ。


これを、現実のプログラム的に書くとこうなる。

  1. 誤差を記憶する配列を作成する(画像横幅と同じサイズの浮動小数配列)
  2. ビットマップの1ピクセルのRGBの値の合計を算出(R+G+B=明るさ)
  3. 明るさに、現在位置の誤差を加算する
  4. もし現在の誤差加算済みの明るさが規定以上なら白、そうでないなら黒にする。白の場合は誤差を消すため明るさをゼロに
  5. 誤差配列の右隣の値に、現在の明るさ*(1/2)を加算
  6. 誤差配列の左下の値に、現在の明るさ*(1/4)を加算
  7. 誤差配列の下の値に、現在の明るさ*(1/4)を加算
  8. 2から7を画像全てのピクセルが確定するまで繰り返す

そしてこれを、実際のプログラム(C++)として書いたのがコチラ。
(メモリ液晶ライブラリから抜粋)

//ディザリング処理(Sierra dithering algorithm - "Sierra Lite")
short w1 = bmpWidth+1;
int szw1 = sizeof(float) * w1;
float r0err[w1]; //現在行の誤差配列
float r1err[w1]; //次の行の誤差配列
memset(r0err, 0, szw1); //配列ゼロクリア
memset(r1err, 0, szw1); //配列ゼロクリア
for(short rows=0, rp=top+rows; rows<enrows; rows++, rp++){
    //ファイルポジションを算出して行の先頭にシーク
	pos = bmpOffset + rs * (bmpHeight - (rows + 1));
	f.seek(pos);
	//画素の明るさを計算し、0.5以上なら白
	unsigned short bgr = f.read() + f.read() + f.read();
	float brightness = (bgr / 765.0f) + r0err[cols];
	if(brightness >= 0.5f){
		brightness -= 1.0f; //白の時の処理
	}else{
		pixel(cp, rp, mode, false); //黒の時の処理(黒なので打点する)
	}
	//"Sierra Lite"
	r0err[cols+1] += brightness * 0.5;
	r1err[cols] += brightness * 0.25;
	if(cols > 0) r1err[cols-1] += r1err[cols]; //+= brightness * 0.25;
}
memcpy(r0err, r1err, szw1); //次の行の誤差配列を現在行の誤差とする
memset(r1err, 0, szw1); //次の行の誤差はゼロクリア

ここだけ見るとゴチャゴチャしててわけわからないと思いますが、
大事なのは18行目から26行目です。
上に書いたアルゴリズムの説明と照らし合わせながら
どれがどういう処理なのか理解すれば
他の言語にも転用可能
かと思います。
以上です。
この記事に限り、画像とか転載してもらっても構いません
学校とかでそういう課題が出たとき(論文とか)にでも参考にしてください。
まぁ・・・Sierra Liteの日本語の詳細記事がなかったので、そういうことをしたってのをひけらかしたかっただけです。


参考になったサイト:
Dither(Wikipedia-en)
2値化して、1bppの白黒画像を作成する(http://dobon.net)
Image Dithering: Eleven Algorithms and Source Code(Tanner Helland (dot) com)


dith-color.png
dith-gray.png
dith-1bit.png

コメントを残す