Yliluomaの順序付きディザリングアルゴリズムの再訪

Yliluomaの2番目のディザリングアルゴリズム EMA-Constant Knoll (強度10%) この記事は、Joel Yliluomaによる2011年の順序付きディザリングアルゴリズム（左）を論じ、他の解説よりも詳細にその内部構造を説明し、新しく簡略化されたバリアント（中央）を提示し、結果を最先端のアルゴリズム（右）と比較しています。ソースコードは最後に含まれています。 1ビット入門 まず、いくつかの基礎を説明します。順序付きディザリングがどのように見えるかご存知かと思います（そうでなければ、上記を参照してください）。白黒ではコーディングは簡単です。まず、どこかから閾値マトリクスを取得します。例えば、以下のような4x4のBayerマトリクスです。 \[ \begin{bmatrix} 0 & 8 & 2 & 10 \\ 12 & 4 & 14 & 6 \\ 3 & 11 & 1 & 9 \\ 15 & 7 & 13 & 5 \end{bmatrix} \] マトリクスをグレースケール画像に適用するには、各ピクセルを調べ、どのマトリクス要素に対応するか（概念的には、マトリクスは画像全体にタイル状に配置されます）を見つけ、マトリクスから閾値を取得します。入力ピクセルのグレースケール値が閾値より高い場合、白いピクセルを出力します。コードは以下のようになります。 ```python bayer_4x4 = np.array([ [ 0, 8, 2, 10], [12, 4, 14, 6], [ 3, 11, 1, 9], [15, 7, 13, 5] ]) def dither_bayer4x4_1bit(img: np.ndarray): img_float = img / 255 # [0,1] の範囲で処理 H, W, _ = img.shape # 浮動小数点出力画像 out = np.zeros((H, W, 1), dtype=float) for y in range(H): for x in range(W): color = img_float[y, x] threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0 if color > threshold: out[y, x] = 1 else: out[y, x] = 0 return out ``` そして、以下にその結果を示します。 グレースケール画像 4x4 閾値マトリクスで1ビットにディザリング 1ビット出力の場合、このような順序付きマトリクスはかなりざらざらした結果を生み出します。もし選ぶなら、Atkinsonのエラー拡散ディザリングのようなものが白黒ではよりうまく機能するでしょう。しかし、これは単なるウォーミングアップ演習でした。本当の問題は、カラー画像で同じことをどう行うかです。 このようなものを作成するには： 16色インデックス画像 順序付きディザリング 今日は、それが正確にどのように行われるかを議論します。 カラーでの順序付きディザリングは、あなたが思うより簡単でもあり、難しくもあります 順序付きディザリングをうまく行うことは、驚くほどトリッキーです。しかし、始めるのは簡単です。閾値マトリクスを構造化ノイズとして再解釈し、画像全体に繰り返し適用して元の色に追加し、各ピクセルに最も近い色を見つけることができます。1ビットの例のコードは、次のようになります。 ```python # "offset" は2つのパレット色の平均距離であると仮定します。 for y in range(H): for x in range(W): # 入力色 color = img_float[y, x] # (0, 1) の範囲 # 閾値 threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0 # 閾値を (-0.5, 0.5) の範囲にバイアスし、加算します moved = color + offset * (threshold - 0.5) # "moved" に最も近いパレット色を見つけます idx = find_index_of_closest(moved) inds[y, x] = idx ``` これは、少なくとも私のテスト画像で使用されているパレットでは、予想よりもうまく機能します。唯一の問題はノイズの大きさ、上記のoffsetの値です。正しい答えはありませんが、私の実験ではこの魔法の式がうまくいきました。 offset = dither_strength * 0.5 * median(pairwise_color_distances) この「グレースケールオフセット」方式は次のようになります。 オリジナル 16色画像 上記のコードでディザリング 悪くない！空の黒い点は少し粗いですが、ディザリング強度を下げることでクリーンアップできるでしょう。任意のパレットでは、このアプローチは残念ながら彩度の低い結果を生成する傾向があります。しかし、ここで画像用に設計されたパレットでは、うまくいきます。 N候補メソッド カラー選択問題に対するより高度な解決策の1つのファミリーは、各ピクセルに対してN個の候補パレット色のセットを収集し、それぞれに確率を割り当て、ランダムまたは閾値マトリクスを介して1つを選択することを含みます。これらはN候補メソッドと呼ばれます。ここでは詳細には触れませんが、2023年のブログ記事「Ordered Dithering with Arbitrary or Irregular Colour Palettes」を参考にしてください。このブログ記事には、あなたが知る必要があるすべてが説明されています。少なくともその「The Probability Matrix」セクションを読んでください。 これらのアルゴリズムが満たそうとする重要な特性の1つは、ローカル平均再現です。ディザリングされた結果が遠くから（またはぼかして）見られたときに、元の画像のように見えるべきです。これは、入力ピクセル色 \(\mathbf{p}\) と、選択されたすべての候補の重み付き合計 \(w_1 \mathbf{r}_1 + ... + w_N \mathbf{r}_N\) との間の距離を最小化することに相当します。詳細については、上記でリンクしたブログ記事を参照することをお勧めします。 Knollのアルゴリズム Knollのアルゴリズムでディザリングされた16色画像。 上記の距離を驚くほどうまく最小化するアルゴリズムの1つが、Thomas Knollのディザリングアルゴリズムです。これはAdobe Photoshopで有名に使用されています（彼はその発明者ですから）。Knollのアルゴリズムは、まず目標色 \(\mathbf{x}_1\) を入力色 \(\mathbf{p}\) に最も近いパレット色に設定します。このパレット色 \(\mathbf{r}_1\) が最初の候補色です。次に、アルゴリズムは \(\mathbf{r}_1\) と \(\mathbf{p}\) の間の誤差を測定し、反対方向に目標を移動させます：\(\mathbf{x}_{2} = \mathbf{x}_1 + (\mathbf{p} - \mathbf{r}_1)\)。ここでプロセスが繰り返され、目標 \(\mathbf{x}_2\) に最も近い新しい点が検索されます。これが2番目の候補色になります。それは以前の候補の誤差を補償します。最初のパレット色が見つかった色が青すぎた場合、この色は黄色っぽくなるでしょう。N回のこの反復の後、その反復は \(\mathbf{p}\) の周りの異なる色を訪れます。各色は複数回訪問される可能性があり、最終的な候補確率は訪問頻度に対する相対値となります。 プロセスは次のように要約できます。 Knollのアルゴリズムのエラー補償ループ 目標点 \(\mathbf{x}_i\) に最も近いパレット色 \(\mathbf{r}_i\) を見つけます。 \(\mathbf{r}_i\) の重みを1増やします。 目標を移動させます \(\mathbf{x}_{i+1} = \mathbf{x}_i + (\mathbf{p} - \mathbf{r}_i)\)。 N回繰り返します。 重みをNで正規化します。 \(\mathbf{x}_{i+1}\) に対してプロセスが繰り返されるとき、最も近い点クエリは \(\mathbf{p}\) の反対側で行われます。このように連続した点を選択することは、凸包を近似します。この手順はまだ抽象的に思えるかもしれませんが、アルゴリズムはシンプルかつ効果的であるという点が重要です。明るさでソートしてカラー選択を一貫させるなどの微妙な点もありますが、Pythonでは次のようになります。 ```python # 作業配列はメインループの外に割り当てられます weights = np.zeros(K, dtype=float) error = np.zeros(3, dtype=float) for y in range(H): for x in range(W): color = img_float[y, x] # 作業配列をクリアします weights[:] = 0.0 # 候補の重み weight_sum = 0.0 error[:] = 0.0 # 累積誤差補償 # 候補を見つけます。ユニークな色数はNより少なくなることがあります for _ in range(N): idx = find_closest(color + error * dither_strength) weights[idx] += 1 weight_sum += 1 error += color - palette_float[idx] weights /= weight_sum threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0 # 累積重み合計が閾値を超える最初の候補インデックスを出力します # 4x4マトリクスから読み取ります # パレットインデックスが使用されなかった場合、その重みはゼロになり、 # このループでは選択されません。 cumulative_sum = 0.0 for idx in luma_order: w_ko = weights[idx] cumulative_sum += w_ko if cumulative_sum > threshold: break inds[y, x] = idx ``` ディザリング強度を誤差補償のスケールを調整することで変更できることに注意してください。Mateljouのシェーダーバージョンを研究することもできます。これは、次に提示される代替ソリューションを理解するための十分なコンテキストになるはずです。 Yliluomaのアルゴリズム 2011年、Joel YliluomaはKnollのアルゴリズムの代替として一連のディザリングアルゴリズムを発表しました。それらは彼のウェブサイトの記事「Arbitrary-palette positional dithering algorithm」で説明されていました。私の知る限り、それらはあまり注目されていません。私はそれらを注意深く研究し、特に興味深いものを1つ見つけました。 Yliluoma-2 簡略化 前の16色画像がYliluomaのアルゴリズム2でディザリングされたもの。 私は記事で提示された2番目のアルゴリズムに焦点を当てます。具体的には、そのC++実装のバリアントです。それをYと呼びましょう