画像擬似階調化：11のアルゴリズムとソース

擬似調色：概要

グラフィックスのプログラミングに関する今日のトピック-擬似調色（ディザリング、擬似色混合）-たくさんの手紙を受け取りましたが、これは驚くべきことかもしれません。 擬似調色は、プログラマーが2012年にすべきことではないと思うかもしれません。 プログラマーとユーザー向けの1600万色のディスプレイが夢見ることしかできなかった時代の古風な技術の歴史を擬似的に混同していませんか？ 安価な携帯電話が32ビットグラフィックスの素晴らしさで動作する時代に、なぜ擬似調色に関する記事を書いているのですか？

実際、疑似調色は、実用的な理由（たとえば、白黒プリンターで印刷するためのフルカラーイメージを準備する）だけでなく、芸術にとってもユニークな方法です。 ディザリングはWebデザインにも適用され、この便利な方法を使用して画像の色数を削減し、品質を犠牲にすることなくファイルサイズ（およびトラフィック）を削減します。 また、編集用に48または64ビット/ピクセルのRAW形式のデジタル写真を24ビット/ピクセルのRGBに縮小するときにも使用されます。

そして、これらは画像の分野のみのアプリケーションです。 サウンドでは、ディザリングも重要な役割を果たしますが、オーディオのディザリングについてはここでは説明しません。 擬似調色画像のみ。

この記事では、次の3つの点に焦点を当てます。

• 画像ディザリングのハイライト
• よく知られているFloyd-Steinbergアルゴリズムのレベルを含む、11個の特定の2次元ディザリング公式。
• 汎用疑似ミックスエンジンの作成方法

疑似調色：例

次のフルカラー画像、 Portalゲームの有名なCompanion Cubeの壁紙を考えてみましょう。


この画像は、この記事のテスト画像です。 彼女を選んだのは、彼女がソフトグラデーションとハードエッジの素晴らしい組み合わせを持っているからです。

コンピューターのモニター、スマートフォン、テレビなど、最新のLCDまたはLEDディスプレイでは、このフルカラー画像を問題なく表示できます。 しかし、限られたカラーパレットをサポートする古いPCを想像してください。 このようなPCで画像を表示しようとすると、次のようになります。


これは上記と同じ画像ですが、Webセーフカラーパレットに制限されています。

かなり嫌ですよね？ さらに明るい例を考えてみましょう。この例では、キューブイメージを白黒プリンターで印刷します。 次に、次のようなものを取得します。


ここでは、画像はほとんど認識できません。

画像に含まれる色よりも少ない色をサポートするデバイスに画像が表示されるたびに問題が発生します。 元の画像の微妙なグラデーションは均一な色のスポットに置き換えることができ、デバイスの制限によっては、元の画像が認識できなくなる場合があります。

擬似緊張（またはディザリング）は、この問題を解決する試みです。 疑似調色は、利用できないアクセス可能な色の近似式を介して機能し、利用可能な色がブレンドされてアクセスできない色をシミュレートします。 例として、ここでは、想像上の古いPCの色に再び劣化した立方体の画像を示しますが、今回は擬似階調が適用されます。


擬似階調なしのバージョンよりも大幅に優れています！

よく見ると、この画像は擬似着色なしでコピーと同じ色を使用していることがわかります。 しかし、これらの少数の色は、他の色がたくさんあるかのように配置されています。

別の例として、これは似たような擬似調子の画像の白黒バージョンです：


具体的には、2行のSierraアルゴリズムに従って擬似調色が適用されます。

黒と白の色だけが存在しているにもかかわらず、立方体の形状を左右のハートまで区別することができます。 ディザリングは非常に強力な方法であり、データが作成された解像度よりも低い解像度で表示される必要があるあらゆる状況で使用できます。 この記事では画像に焦点を当てますが、同じ方法を任意の2次元データ（またはさらに簡単な1次元データ）に適用できます。

擬似調色の基本概念

要するに、擬似音調は基本的に誤差の分散に関連しています。

エラー分散は次のように機能します：グレースケールの写真を白黒に縮小して、純粋な黒（インク）または純粋な白（インクのない紙）色のみをサポートするプリンターで印刷できるようにする必要があるとします。 画像の最初のピクセルは暗い灰色で、0から255のスケールで96の値を持ちます。0は純粋な黒、255は純粋な白です。


この例でのRGB値の視覚化。

このようなピクセルを黒または白に変換する場合、単純な式を使用します。色の値は0（黒）または255（白）に近いですか？ 96は255よりも0に近いため、ピクセルを黒にします。

この時点での標準的なアプローチは、単純に次のピクセルに移動して同じ比較を実行することです。 しかし、96の値を持つ同様の灰色のピクセルがたくさんある場合、問題が発生します-それらはすべて黒に変わります。 元のグレーの色を十分に表現していない空白の黒いピクセルの巨大な部分を取得します。

エラー分散は、問題に対するよりスマートなアプローチに従います。 ご想像のとおり、誤差の分散は、各計算の誤差を隣接するピクセルに「分散」または拡散することで機能します。 アルゴリズムが値96のグレーピクセルを検出した場合、96が255よりも0に近いことも判断するため、ピクセルが黒になります。 ただし、アルゴリズムは変換の「エラー」を考慮に入れます。 特に、エラーは、黒にしたグレーピクセルが実際には黒から96ステップ離れていることです。

エラー分散アルゴリズムは、次のピクセルに移動すると、前のピクセルのエラーを現在のピクセルに追加します。 次のピクセルの灰色も96である場合、黒にするのではなく、アルゴリズムは前のピクセルから96の誤差を追加します。 これにより、値は192になり、実際には255に近くなります。したがって、白に近くなります。 したがって、アルゴリズムはこのピクセルを白にし、再びエラーを考慮します。 この場合、192は63が255より小さいため、エラーは-63です。これは、このピクセルが変更された値です。

アルゴリズムが機能し続けると、エラーの分散により黒と白のピクセルが交互になり、このセグメントの値96のグレー色をかなりよく模倣します。 これは、行のすべてのピクセルを黒で着色するよりもはるかに優れています。 原則として、画像ラインの処理が終了したら、追跡したエラー値を破棄し、次の画像ラインからエラー「0」で再開します。

以下は、説明したアルゴリズムを使用したキューブの画像の例です。 特に、各ピクセルは黒または白に変換され、変換エラーが記録され、右側の次のピクセルに送信されます。


これは、エラー分散擬似階調化の最も単純なアプリケーションです。

残念ながら、エラー分散擬似階調化には独自の問題があります。 仮に、擬似階調化は常に目立つポイントまたは破線の外観につながります。 これは、少数の利用可能な色で作業することの避けられない副作用です-それらの数のために、これらの色は何度も繰り返されます。

エラー分散アルゴリズムの上の簡単な例では、別の問題が明らかです。非常に似た色のブロックがあり、エラーを右にのみプッシュすると、すべての「ポイント」が同じ場所にあります。 これにより、擬似階調のない元のバージョンとほぼ同じくらい気を散らす楽しい点線ができます。

問題は、1次元の誤差分散のみを使用することです。 エラーを一方向（右）にのみ拡散したため、あまりうまく分散していません。 画像には2つの次元（水平および垂直）があるため、エラーを複数の方向に向けてみませんか？ これにより、エラーがより均等に分散され、上記のエラーの分散の例で考慮されるポイントの奇妙な線を避けるのに役立ちます。

二次元誤差分散擬似調音

2次元でエラーを拡散させる方法は多数あります。 たとえば、エラーを1つ以上のピクセルを右、左、上下に伝播できます。

計算を簡単にするため、すべての標準ディザリング式はエラーを前方にのみ進めます。 画像をピクセルごとに左上隅から右に移動していく場合、エラーを後方（たとえば、左および/または上）に考慮する必要はありません。 この理由は明らかです。エラーをスローバックすると、すでに処理されているピクセルに戻る必要があり、逆方向に移動するとエラーが増加します。 その結果、エラーの伝播が無限に繰り返されます。

したがって、標準的なサイクル動作（画像の左上隅から始まり、右に移動する）の場合、ピクセルは右および下にのみ移動する必要があります。


お粗末なイメージをおIびしますが、これが正しいエラー分布の本質を説明するのに役立つことを願っています。

エラーを広める具体的な方法については、私よりも賢い多くの人がこのタスクを破っていました。 これらの式をあなたと共有させてください。

（注：これらのディザリング式は、インターネット上のいくつかのサイトで入手できますが、私が見つけた最も包括的なリファレンスはこれです。）

フロイド・スタインバーグ誤差散逸アルゴリズム

最初の、おそらく最もよく知られている誤差分散式は、1976年にロバートフロイドとルイスタインバーグによって公開されました。 エラーの分散は次のように発生します。

X 7 3 5 1 (1/16) 

上記の表記では、Xは現在のピクセルを表します。 下部の端数は、エラーの除数です。 つまり、Floyd-Steinbergの式は次のように記述できます。

  X 7/16 3/16 5/16 1/16 

しかし、そのような指定は長くてずさんなので、私はオリジナルに固執します。

ピクセル値を96から0（黒）または255（白）に変換する元の例に戻りましょう。 ピクセルを黒で色付けすると、96のエラーが発生します。このエラーを周囲のピクセルに伝播し、96を16（= 6）で割った後、対応する値で乗算します。次に例を示します。

  X +42 +18 +30 +6 

それぞれ異なる値を持ついくつかのピクセルにエラーを伝播することにより、エラー分散アルゴリズムの元の例で目立つドットを含むすべての注意散漫なストライプを最小化します。 Floyd-Steinbergアルゴリズムを使用した立方体の画像を次に示します。


フロイド・スタインバーグ誤差散逸アルゴリズム

悪くないでしょ？

Floyd-Steinbergエラー分散アルゴリズムは、おそらく最もよく知られているエラー分散アルゴリズムです。 それはかなり良い品質を提供し、1つのフロントアレイ（次の行に伝播されたエラー値が格納される画像内の1次元アレイ）のみを必要とします。 さらに、除算器は16なので、除算の代わりにビットシフトを使用できます。 したがって、このアルゴリズムは古い機器でも高速を実現します。

エラーの伝播に使用される1/3/5/7の値については、グレー画像に対して均一な市松模様を作成するため、特別に選択されました。 賢い！

Floyd-Steinbergアルゴリズムに関する警告-一部のプログラムでは、他のより単純な擬似階調式を使用し、それらを「Floyd-Steinberg」と呼び、人々が違いを知らないことを期待します。 これらの「Floyd-Steinberg False Algorithms」の1つを説明する素晴らしいディザリング記事があります：

  X 3 3 2 (1/8) 

元のFloyd-Steinbergアルゴリズムのこの単純化により、著しく悪い結果が得られるだけでなく、速度（またはメモリ、次の行のエラー値を格納するための配列が必要なため）に関して大きな利点もありません。

しかし、もし興味があれば、「偽のフロイド・スタインバーグ」の通過後の立方体の画像は次のとおりです。


現在のFloyd-Steinbergアルゴリズムよりも多くのポイントのクラスターがあるため、この式は使用しないでください！

Jarvis、Judice、およびNinkeアルゴリズム（Jarvis、Judice、Ninke）

フロイドとスタインバーグが有名なディザリングアルゴリズムを発表した年に、あまり知られていないがはるかに強力なアルゴリズムが公開されました。 Jarvis、Judis、およびNinkeフィルターは、Floyd-Steinbergフィルターよりもはるかに複雑です。

  X 7 5 3 5 7 5 3 1 3 5 3 1 (1/48) 

このアルゴリズムを使用すると、エラーはFloyd-Steinbergの3倍のピクセルに分散されるため、より滑らかで微妙な結果が得られます。 残念ながら、除数48は2の累乗ではないため、ビットシフトを適用できません。 1 / 48、3 / 48、5 / 48、および7/48の値のみが使用されるため、これらの値は1回計算し、速度を少し上げるために数回掛けることができます。

JJNフィルターのもう1つの欠点は、エラーを1行ではなく2行押し下げることです。 これは、2つの配列が必要であることを意味します。1つは次の行用で、2つ目はその後の行用です。 これは、アルゴリズムが最初に公開された時点では問題でしたが、最新のPCやスマートフォンでは、この追加要件によって違いは生じません。 正直なところ、2つの単一行格子を何度も消去するよりも、単一のエラーサイズの画像アレイを使用した方が良い場合があります。


ジャービス、ジュディス、ニンケの擬似調色

ディザリングピース（Stucki）

Jarvis、Judis、Ninkeのディザリング公式の公開から5年後、Peter Stuckiは処理時間を改善するためにわずかな修正を加えた調整バージョンを公開しました。

  X 8 4 2 4 8 4 2 1 2 4 2 1 (1/42) 

除算器42は2の累乗ではありませんが、エラー分散値はyesです。 したがって、エラーは42で除算され、ビットシフトを使用して散乱の特定の値を取得できます。

ほとんどの画像では、StuckアルゴリズムとJJNアルゴリズムの違いはごくわずかです。 したがって、最初の方が速度の利点が小さいため、より頻繁に使用されます。


擬似調色ピース

アトキンソンディザリング

1980年代半ば、コンピューターのハードウェアがより強力なビデオアダプターとディスプレイドライバーをサポートするようになったため、擬似階調化はますます一般的になりました。 当時の最高のディザリングアルゴリズムの1つは、MacPaint（元のMacintosh用にゼロから作成した）からHyperCardおよびQuickDrawまですべてに取り組んだAppleの従業員であるBill Atkinsonによって開発されました。

Atkinsonの式は、エラーの全体ではなく一部のみを配布するため、このリストの他の式とわずかに異なります。 最新のグラフィックスアプリケーションでは、この方法は「フェージングの低減」という名前で見つかります。 エラーの一部のみを散乱させると粒子の粗さを減らすことができますが、画像の連続した明るい部分と暗い部分は色を失う場合があります。

  X 1 1 1 1 1 1 (1/8) 

アトキンソンの擬似調色

バークの擬似調色

StucksがJarvis、Judis、およびNinkeアルゴリズムの改善を発表してから7年後、Daniel Burkesはさらなる開発を提案しました。

  X 8 4 2 4 8 4 2 (1/32) 

バークスの提案は、Stuckiアルゴリズムで行列の最下行を省略することでした。 これにより、2つの配列が不要になるだけでなく、2の倍数である除数が得られました。この変更により、エラーの計算に関係するすべての数学を単純なビットシフトでわずかな品質低下で実行できるようになりました。


バークの擬似調色

シエラの偽造

最後の3つのディザリングアルゴリズムは、フランクシエラによって作成されました。フランクシエラは、1989年と1990年に次のマトリックスを公開しました。

  X 5 3 2 4 5 4 2 2 3 2 (1/32) 

  X 4 3 1 2 3 2 1 (1/16) 

  X 2 1 1 (1/4) 

これらの3つのフィルターは、一般にSierra、Two-Row Sierra（Sierraの2行アルゴリズム）、およびSierra Liteと呼ばれます。 テストキューブイメージの最終的なイメージは次のとおりです。


Sierra（Sierra-3と呼ばれることもあります）


2列Sierra（Sierraアルゴリズム）


シエラライト

その他の擬似調色に関する考慮事項

上記の画像を別のプログラムの擬似調色結果と比較すると、わずかな違いが見つかる場合があります。 同様のことが期待されます。 驚くほど多くの変数があり、擬似調色アルゴリズムの出力の精度に影響を与える可能性があります。 それらの中で：

• 浮動小数点または整数でエラーを追跡します。 整数メソッドは、量子化エラーのために解像度をいくらか失います。
  
• 変色を減らします。 一部のソフトウェアは、指定された値のエラーのマージン（おそらく50％または75％）を減らして、隣接するピクセルの漂白の量を減らします。
  
• 黒または白のクリッピングしきい値。 127または128の値が一般的ですが、一部の画像では他の値が役立つ場合があります。
  
• カラー画像の場合、明るさの計算方法が重要です。 HSL輝度式（[max（R、G、B）+ min（R、G、B）] / 2）を使用します。 その他は（[r + g + b] / 3）またはITU公式の 1つを使用します 。 YUVまたはCIELABはさらに良い結果を達成します。
  
• ガンマ補正またはその他の予備的な修正。 白黒に変換する前に画像を正規化すると便利なことがよくあります。 この方法の選択は明らかに結果に影響します。
  
• サイクルの方向。 標準の「左から右、上から下」のアプローチについて説明しましたが、いくつかの巧妙なディザリングアルゴリズムは、左から右への方向が逆になる蛇行した経路に従います。 そのため、均一なポイントのスポットを減らして、より多様な外観を与えることができますが、それらの実装はより困難です。
  

この記事のデモ画像では、元の画像を前処理しませんでした。 すべてのカラーマッチは、127のカットオフでRGB空間で実行されます（値<= 127は0に設定されます）。 サイクルの方向は、左から右へ上から下へ標準です。

使用できる特定の方法は、プログラミング言語、処理の制限、および目的の結果によって異なります。

9個のアルゴリズムをカウントしましたが、11個を約束しました！ さらに2つはありますか？

これまでのところ、この方法は静的な非拡散アルゴリズムよりも優れた結果を提供するため、エラーの分散に関する疑似音調のみに焦点を当ててきました。

ただし、完全を期すために、順序付けられたぼかしを使用した2つの標準的な擬似階調化方法を示します。 順序付けられたぼかしを使用した擬似階調化は、誤差分散を伴う擬似階調化よりもはるかに多くのポイント（およびより悪い結果）につながりますが、次の行の配列を必要とせず、非常に高速に動作します。 順序付けられたぼかし擬似階調化の詳細については、 関連するウィキペディアの記事を参照してください 。


4×4マトリックスによる順序付きぼかし擬似階調化


8×8マトリックスを使用した順序付きぼかし擬似階調化

これらの方法に基づいて、この記事では11の異なる擬似調色アルゴリズムについて説明します。

汎用の擬似調色アルゴリズムの作成

今年の初めに、 PhotoDemon （オープンソースの写真編集者）用の完全に機能する汎用擬似階調ジェネレータを作成しました 。 すべてのコードをここに投稿する代わりに、GitHubの適切なページに移動させてください 。 白黒画像変換エンジンは350行目から開始します。このページに記載されているアルゴリズムをカバーするコードについて質問がある場合はお知らせください 。追加の説明を掲載します。

このエンジンは、この記事と同じ方法で、擬似階調マトリックスを事前に指定できるようにすることで機能します。 次に、このマトリックスを疑似調色エンジンに渡し、残りを実行します。

このエンジンはモノクロ変換に基づいて設計されていますが、カラーパレットで動作するように簡単に変更できます。 カラーパレットの場合の最大の違いは、単一の輝度エラーではなく、赤、緑、青の個々のエラーを追跡する必要があることです。 それ以外の場合、すべての数学は同じです。