誤差拡散法(2)
前回は誤差拡散法の概観を見ました。
今回は誤差の拡散（差分値の振り分け）はどのようなアルゴリズムでおこなわれるのか、その種類を見てみます。
いきなり wonderfl 投稿コードから。それぞれのボタンをクリックすると、それぞれのアルゴリズムに基づいた結果を表示します。
Error Diffusion – wonderfl build flash online
併せて、英語版ウィキペディアの "Dither" のだいぶ下の方に各種の誤差拡散法で2値化した画像がずらっと並んでいることもお知らせします（ディザ法によるものが上段、中段と下段に誤差拡散法によるものが4種類ずつ計8種類示されています）。
ずいぶんいろいろありますが、解説するのは2種類に留めます。この2つだけ押さえておけば誤差拡散法は充分っぽい。
まぁ基本的な流れさえ把握しとけば、あとは枝葉ですからね。
まずは誤差拡散法の中でも一番メジャーと思われる Floyd-Steinberg アルゴリズム。これは Floyd と Steinberg によって開発されました。詳細はリンク貼った先を見てもらうとして、肝心の、差分の振り分け範囲および配分を見てみましょう。
-, *, 7/16,
3/16, 5/16, 1/16
これは * が評価ピクセルで、右隣に差分の16分の7を、左下に差分の16分の3を、直下に差分の16分の5を、右下に差分の16分の1を振り分ける、という意味です。
前回述べたとおり、左隣はすでに評価が完了しているので振り分けません。
ConvolutionFilter のマトリックスと同じような感じですね。ConvolutionFilter の方は評価ピクセルがマトリックスの中心ですけど。
ConvolutionFilter のマトリックスを援用すると、以下のような表記ができます。繰り返しになりますが、評価ピクセルの位置は、これでは1行目の2列目になっています。
matrix = [0, 0, 7,
3, 5, 1];
divisor = 16;
ところで、振り分けられる割合の合計ですが、 (7 + 3 + 5 + 1) / 16 なので、1 つまり100％です。
もう1つ Atkinson アルゴリズムを見てみます。これは以下のように差分を振り分けます。
matrix = [0, 0, 0, 1, 1,
0, 1, 1, 1, 0,
0, 0, 1, 0, 0];
divisor = 8;
ここで注目してもらいたいのは配分値の合計が 6 なのに対して divisor が 8 である点。
つまり、あるピクセルで発生した差分は100％ではなく75％だけ拡散するということです。
これは Atkinson アルゴリズム特有っぽい。
調べた範囲で見つかった他の誤差拡散法は、すべて発生した差分の100％を配分していました。
100％じゃなく75％にすることで、明るい部分はより明るく、暗い部分はより暗くなるようです。
もうひとつ Atkinson という名前に注目。
これは Floyd-Steinberg アルゴリズム同様開発者の名前です。開発者は Bill Atkinson。
かつてアップルはアップル・コンピュータという会社名で、マッキントッシュというコンピュータを販売していました。マッキントッシュ最初のマシンから数世代に渡る一体型マッキントッシュ、今はクラシック・マックと呼ばれるマシンに関わっていた人物です。
ハイパーカードというすばらしいソフトウェアを開発したことで有名な人でもありますね。
で、これらクラシック・マックのディスプレイはモノクロだったんですよ。
その白か黒しか表示できないディスプレイでカラーイメージを表示させるために Bill Atkinson が考案したのが Atkinson アルゴリズムらしいです。
ウチにいらっしゃる方々はマカーが多いようですが、マカーだったら彼に敬意を評してもバチは当たりませんよ
ちなみに iPhone アプリに 1-bit camera というのがあります。
その UI はクラシック・マックの UI を模したもので、撮影した画像を Atkinson アルゴリズムか組織的ディザ法の Bayer パターンのいずれかでハーフトーニングするというカメラアプリです。
なかなか郷愁を誘う UI ですが、最近の若い人には、何じゃこりゃな感じすかねー。
なお、Floyd-Steinberg と Atkinson 以外のアルゴリズムに興味のある方は、コード内に記述された URL をご参照ください。
Comments
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!