Yliluomaの順序付きディザリングアルゴリズムの再訪
Revisiting Yliluoma's ordered dither algorithm (30fps.net)
要約
この記事は、Joel Yliluomaによる2011年の順序付きディザリングアルゴリズムを詳細に解説し、その内部構造を掘り下げています。さらに、簡略化された新しいバリアントを提示し、最先端のアルゴリズムと比較しています。1ビット画像とカラー画像への適用方法、およびKnollのアルゴリズムなどの関連手法についても触れ、ソースコードも提供しています。
全文翻訳
Yliluomaの順序付きディザリングアルゴリズムを再訪する
要約: この記事では、Joel Yliluomaによる2011年の順序付きディザリングアルゴリズム(左)を、他の解説よりも詳細に内部構造を説明し、新しい簡略化されたバリアント(中央)を提示し、結果を最先端のアルゴリズム(右)と比較します。ソースコードは最後に含まれています。
1ビット入門
まず、いくつかの基礎を説明します。順序付きディザリングがどのように見えるかを知っていると仮定します(知らない場合は、上記を参照してください)。白黒ではコーディングが簡単です。まず、どこかから閾値行列を取得します。たとえば、次のような4x4のベイヤー行列です。
\begin{bmatrix} 0 & 8 & 2 & 10 \ 12 & 4 & 14 & 6 \ 3 & 11 & 1 & 9 \ 15 & 7 & 13 & 5 \end{bmatrix}
行列をグレースケール画像に適用するには、各ピクセルを調べ、どの行列要素に対応するか(概念的には、行列は画像全体にタイル状に配置されます)を見つけ、行列から閾値を読み取ります。入力ピクセルのグレースケール値が閾値より高い場合は、白いピクセルを出力します。コードは次のようになります。
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 # process in [0,1] range
H, W, _ = img.shape
# The floating point output image
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
そして、以下にその結果を示します。
1ビット出力の場合、このような順序付き行列はかなりざらざらした結果を生み出します。もし選ぶなら、Atkinsonのエラー拡散ディザリングのようなものが白黒ではよりうまく機能するでしょう。
しかし、これは単なるウォーミングアップ演習でした。本当の問題は、カラー画像で同じことをどう行うかです。このようなものを作成するには:
[画像: 順序付きディザリングによる16色インデックス画像]
今日は、それが正確にどのように行われるかを議論します。
カラーでの順序付きディザリングは、思ったより難しく、そして簡単です
順序付きディザリングをうまく行うことは、驚くほど難しいです。しかし、始めるのは簡単です。閾値行列を構造化ノイズとして再解釈し、画像全体に繰り返し適用して元の色に追加し、各ピクセルで最も近い色を見つけることができます。1ビットの例コードは次のようになります。
# Assume "offset" is the average distance between two palette colors.
for y in range(H):
for x in range(W):
# input color
color = img_float[y, x]
# (0, 1) range threshold
threshold = (bayer_4x4[y%4,x%4] + 0.5) / 16.0
# bias threshold to (-0.5, 0.5) range, then add
moved = color + offset * (threshold - 0.5)
# find closest palette color to 'moved'
idx = find_index_of_closest(moved)
inds[y, x] = idx
これは、少なくとも私のテスト画像で使用されているパレットでは、予想以上にうまく機能します。唯一の問題はノイズの大きさ、上記のoffsetの値です。正しい答えはありませんが、私の実験ではこの魔法の式がうまく機能しました。
offset = dither_strength * 0.5 * median(pairwise_color_distances)
この「グレースケールオフセット」方式は次のようになります。
[画像]
悪くない!空の黒い点は少し粗いですが、ディザリング強度を減らすことでクリーンアップできるかもしれません。任意のパレットでは、このアプローチは残念ながら彩度の低い結果を生成する傾向があります。しかし、ここで画像のようにパレットが設計されている場合、うまくいきます。
N候補メソッド
カラー選択問題に対するより高度な解決策の1つのファミリは、各ピクセルに対してN個の候補パレットカラーのセットを収集し、それぞれに確率を割り当て、その後ランダムまたは閾値行列を介して1つを選択することを含みます。これらはN候補メソッドと呼ばれます。ここでは詳しく説明しませんが、2023年のブログ記事「Ordered Dithering with Arbitrary or Irregular Colour Palettes」を参照してください。このブログ記事には、あなたが知る必要があるすべてが説明されています。少なくともその「確率行列」セクションを読んでください。
これらのアルゴリズムが満たそうとする重要な特性は局所平均再現性です。ディザリングされた結果を遠くから(またはぼかして)見たときに、元の画像のように見えるべきです。これは、入力ピクセルカラー \mathbf{p} と、選択されたすべての候補の加重平均 w_1 \mathbf{r}_1 + ... + w_N \mathbf{r}_N の距離を最小化することに相当します。詳細については、上記でリンクしたブログ記事を参照してください。
Knollのアルゴリズム
[画像: Knollのアルゴリズムでディザリングされた16色画像。]
上記の距離を驚くほどうまく最小化するアルゴリズムの1つが、Adobe Photoshopで有名に使用されているThomas Knollのディザリングアルゴリズムです(彼はその発明者です)。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では次のようになります。
# Work arrays allocated outside the main loop
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]
# Clear work arrays
weights[:] = 0.0 # candidate weights
weight_sum = 0.0
error[:] = 0.0 # accumulated error compensation
# Find candidates, can be less than N unique colors
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
# Output the candidate index on which cumulative weight sum
# first crosses the threshold read from the 4x4 matrix
# If a palette index wasn't used, its weight will be zero
# and it won't be selected by this loop.
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++実装のバリアントに焦点を当てます。これをYliluoma-2と呼びましょう。
大まかに言うと、Yliluoma-2はKnollのような他のN候補アルゴリズムに似ています。各ピクセルで、パレットから加重候補カラーを選択し、閾値行列(またはノイズ)に基づいて1つを出力します。候補の選択方法が異なりますが、この場合、ユニークな誤差式を使用してすべてのパレットカラーをテストすることによって行われます。
複雑なカラー差計算は不要
高品質なディザリングには複雑なカラー差計算が必要だという一般的な考えがあります。私はこれは間違いであり、本当に必要なのは(a)緑チャンネルの重みを増やすことと(b)明るい色の違いを強調することだと考えています。
この記事では、輝度重み付けされた(以前にこのサイトで)カラー差式を提案しており、それを実装しました。左端の最初の画像でその結果を確認できます。同じことを達成するより簡単な方法は、ディザリング前に画像とパレットを脱色することです。最終的なインデックス画像は、元のカラフルなパレットを使用します。たとえば、libimagequantはRGBカラーを(0.5, 1, 0.45)で乗算し、各チャンネルを0.8乗します。私はそれを下の2番目の画像で行い、それは同様にうまく機能しました。
もちろん、高品質な再構成が必要な場合、「目を細めて見たときに元の画像のように見える」ような場合、線形空間でディザリングを行ってください。また、出力解像度が低くピクセルが大きい場合は、好きなように何でもできるとも主張します。あなたは、視聴者が元の画像と同じように解釈することを期待する、非常に異なる見た目のものを構築しているのです。
候補は線分への最近傍テストで選択される
本題に戻ります。私はコードで楽しい午後を過ごし、それを幾何学的に解釈しました。N候補メソッドが候補パレットカラーを見つけ、それらに重み(確率)を割り当てる方法を思い出してください。Yliluoma-2のカラー選択ループは、これまでに選択された候補カラーの指数移動平均(EMA)を追跡します。つまり、各検索反復で、ルーチンは新しい候補 \mathbf{r}_i を使用して移動平均 \mathbf{x}_i を \mathbf{x}_i+1 = (1 - t)\mathbf{x}_i + t\mathbf{r}_i で更新します。ここで、t \in [0,1] は各反復で変化する混合重みです(おそらくtはt_iと呼ぶべきでしょうか?)。
さて、候補はlerp()を介して実行平均に混合されます。しかし、候補はどのように選択され、混合係数tはどこから来るのでしょうか?候補点は、すべてのパレットカラー \mathbf{c}_k と現在の平均 \mathbf{x}_i の間の線分をテストすることによって選択されます。入力カラー \mathbf{p} に最も近い線が、候補 \mathbf{r}_i として選択されるパレットカラーを示します。
次に、tの値は、セグメント上で最も近い点を生成した混合係数になります。説明するのは難しいですが、視覚的にはもっと分かりやすくなるはずです。
[画像: 線分 \mathbf{x}_i から \mathbf{r}_i への入力 \mathbf{p} の最も近い点は、tによって特定されます。この例では、tは約0.6になります。]
要約すると、すべてのパレットカラーの中で、選択された候補は、現在の平均と線形に組み合わせられたときに、入力の最も良い近似になります。
この記事では、明示的な平均化ステップを含む定式化を選択することで、手順を理解しやすくしようとしました。元のC++コードは、加重実行平均として書かれています。それを指数移動平均と呼ぶのは私の独自の解釈です。
指数移動平均ループの詳細
以下にアルゴリズムをより詳細に示します。以下の開発を理解するためにこれを研究する必要はありませんが、文書化しておくのが賢明だと思いました。
最初の反復では、候補は入力に最も近いパレットカラーに設定されます:\mathbf{x}_1 = \text{closest}(\mathbf{p})。その重みは1です。残りの反復は次のように進行します。
Yliluoma-2の指数移動平均ループ(簡略化)
[画像]
- すべてのパレットカラー \mathbf{c}_k を候補として検討します。
- 平方距離 ||((1-t)\mathbf{x}_i + t \mathbf{c}_k) - \mathbf{p}||^2 を最小化する混合係数 t を見つけます。
- 距離がこれまでに発見された最短距離だった場合:
- t_\text{best} = t を更新します。
- \mathbf{c}_\text{best} = \mathbf{c}_k を更新します。
- k_\text{best} = k を更新します。
- 候補 \mathbf{r}_i = \mathbf{c}_\text{best} を選択します。
- 最良の混合係数を使用して、平均点を候補に移動させます:\mathbf{x}_i+1 = (1 - t_\text{best})\mathbf{x}_i + t_\text{best}\mathbf{r}_i
- t_\text{best} を候補 \mathbf{r}_i の重みに追加します。
- N回繰り返します。
重みを weights /= sum(weights) で正規化します。
Knollのアルゴリズムと同様に、Yliluoma-2も凸包を近似することになります。各反復で、目標 \mathbf{x}_i+1 は、以前に見つかったセグメント上の最も近い点に移動します。この点は \mathbf{x}_i と入力カラー \mathbf{p} の間にあるため、(大まかに言えば)\mathbf{p} の反対側にあります。だからこそ、目標である実行平均は \mathbf{p} の周りを移動するのです。
t の見つけ方
上記では、線分上の最も近い点を正確に見つける方法を未定のままにしていました。最も簡単な方法はパラメータスイープを実行することです。さまざまな t \in [0,1] の値をテストし、入力点に最も近かったものを保持します。ここに図を示します。AB線分上のCに最も近い点Dを見つけようとしています。以下では、赤点はテストしている個々のtの値を示しています。
[画像: 線分AB上のCに最も近い点を見つけたい。]
残念ながら、パラメータスイープでは最適なt値に正確に到達する可能性は低いです。時間もかかりますが、複雑なカラー差式がある場合は、それが唯一機能する方法かもしれません。しかし、輝度重み付けは前処理で実行できることをどのように確立したかを思い出してください。だからこそ、tを検索する際に知覚的なものを無視し、幾何学的な問題を直接解決できるのです。
解析的なt解
A \neq B と仮定すると、
t_closest = \frac{(C - A) \cdot (B - A)}{||(B - A)||^2}
ここで、「\cdot」は内積を表します。AとBの間の点を見つけたいので、範囲を[0,1]にクランプする必要があります。
t = \max(0, \min(1, t_closest))
そして以前と同様に、D = (1-t)A + tB です。
コードと同じ
c_k = palette_float[k] # B
delta = c_k - mean # B - A
t = 0.0
delta2 = delta.dot(delta) # ||B - A||^2
# Avoid division by zero
if delta2 >= 1e-9:
t = (p - mean).dot(delta) / delta2
# Limit the choice to the given range
t = max(min_t, min(max_t, t))
mix = (1-t) * mean + t * c_k # D
diff = p - mix
cand_dist = diff.dot(diff) # d^2
t の制限
正確な解は[0,1]のどこにでもなり得るため、非常に奇妙な点を選択することがあります。たとえば、t=0は平均をまったく移動させないことを意味し、おそらくあなたが望むものではありません。そのため、tのさまざまな最小値で実験し、0.2が妥当な妥協点であることを見つけました。したがって、実際には、最近傍点を計算する私のコードは次のようになります。
t = \max(\textcolor{red}{0.2}, \min(1, t_closest)).
私たちはすでに元のYliluoma-2アルゴリズムから遠く離れており、そのような制限はありません。さらに一歩進みましょう。
固定t
私の実験では、最適なtが97%の時間でゼロに近いことがわかりました。これは、平均カラーが入力カラーの近くにずれている状況を考えると理にかなっています。それを静止させておくことは誤差を最小化します。
これにより、tを解く代わりに、常に定数である代替方法が動機付けられました。t = 0.3 を選択しましたが、ほとんどの場合、結果は正確な方法と区別がつきません。
このアプローチは、入力カラーの方向にありますがかなり離れた候補を選択することとして考えることができます。実際には、その出力品質は正確な方法と同等に見えますが、わずかに劣る可能性があります。
3つのバリアントといくつかの観察
元のYliluoma-2アプローチを変更したため、上記の3つのバリアントを「EMA」カラー選択アルゴリズムと名付けました。
- EMA-Sweep: これはPythonで再実装されたYliluoma-2です。4x4の閾値行列を使用し、[0.2, 1.0)の範囲で8つのtの値をテストします。C++コードは、選択された候補の数に基づいて、(0.0, 1.0)の範囲で1〜16個の値をテストします。
- EMA-Exact: [0.2, 1.0)の範囲でtの正確な解を計算します。元のコードよりも少ない作業で済みます。
- EMA-Constant: 固定値t=0.3を設定します。3つの中で最もシンプルです。
新しいバリアントの時間計算量
K色、N候補と仮定します。Knollのアルゴリズムのピクセルあたりの作業量は、kd-treeで加速された最近傍探索を仮定すると、O(N \log K)です。Yliluoma-2は、テストされるtの異なる値の数がNに依存するように見えるため(コードからは完全には明らかではありません)、O(N^2 K)の作業を行う必要があります。
EMA-Sweepは各候補に対してセグメント上で8つの点をテストするため、O(NK*8) = O(NK)ですが、基本的にYliluoma-2と同じ速度です。EMA-ExactとEMA-Constantは各候補に対して1つのt値のみをテストするため、より高速ですが、同じO(NK)の複雑さクラスに属します。
結果と考察
これらの画像では、EMAとKnollのアルゴリズムはユークリッドsRGB距離を使用していますが、Yliluoma-2は輝度重み付け距離を使用しています。
まず、EMA-SweepとEMA-Exactは非常に似た結果を生成します。以下の2つの画像は区別できないことがわかります。EMA-Constantに選択されたt=0.3の定数は、わずかに弱いディザリングを作成します。固定t値の効果については、補足を参照してください。
EMA-Exactによって選択された正確なtは、Yliluoma-2のパラメータスイープに似た結果を生成します。解かれたtは[0.2, 1.0)にクランプされているため、結果のディザリングもYliluoma-2よりもわずかに弱くなります。
以下は、16色、N=16候補反復、および両方で4x4閾値行列を使用したEMA-Exact対Yliluoma-2の比較です。ほとんど同じように見えます。
候補数Nは、結果のノイズに大きな影響を与えます。これはすべてのN候補メソッドに当てはまります。以下の比較は、EMA-Exactを使用して、16候補が32候補よりもどれだけ悪く見えるかを示しています。たとえば、黄色とターコイズのコンゴウインコの背中を見てください。
十分な候補数があれば、EMA-ExactとEMA-Constantのバリアントは、それぞれ20%と10%のディザリング強度でのKnollのアルゴリズムと同等になります。少なくとも、Yliluomaの2011年の記事で例として使用されたChrono Crossのスクリーンショットではそうです。
以下は、記事で使用された固定パレットを使用した16色の比較です。N=32候補反復を使用しました。そのため、Yliluoma-2は除外されました。これはC++コードではN=16しか実行しないためです。補足で、Yliluoma-2との直接的なN=16の比較を参照してください。
結論
Yliluomaの2番目のカラー選択アルゴリズムは、知覚的なカラー差関数を必要としません。アルゴリズムは繰り返し加重平均を計算し、選択されたカラー候補セットの品質は、混合係数tと候補数Nによって決まります。ユークリッドカラー差式を使用する場合、tの最適な値は正確に解くことができます。K色画像に適したNは、N=2K程度と思われます。
簡略化された「EMA」バリアントは、より高速であるにもかかわらず、元のアルゴリズムと同等の品質を提供します。これらのバリアントは時折Knollのアルゴリズムの品質を上回りますが、ほとんどの場合そうではありません。また、バリアントは先行者の構造を引き継いでいるため、各候補検索反復でK色のパレットすべてをテストする必要があります。一方、Knollのアルゴリズムは、より高速なO(\log K)最近傍探索を使用できます。
軽いディザリングのみが必要な場合、EMA-Constantバリアントは、新しくシンプルな代替手段を提供します。しかし、Knollのアルゴリズムよりも依然として遅いため、推奨するのは困難です。
資料
記事の補足には、より多くの結果画像と、最後に人工的な2D比較が含まれています。
4x4閾値行列を使用したKnoll、EMA-Sweep、EMA-Exact、EMA-Constant、およびOffset順序付きディザーを実装したスタンドアロンスクリプト:
使用法: uv run color_selection.py bigbuckbunny_bird.png 16 32 --algo=ema-exact
元のYliluoma-2アルゴリズムの私の加工されたC++バージョン:
この記事は、私が執筆中の書籍のために行った研究に基づいています。カラーリダクションアルゴリズムに関するものです。興味がある場合は、こちらからサインアップしてください。
さらに読む
- K. Lemström, J. Tarhio & T. Takala: Color Dithering with n-Best Algorithm, 1996.
- K. Lemström & P. Fränti: N-Candidate methods for location invariant dithering of color images, 2000.
- Joel Yliluoma, Arbitrary-palette positional dithering algorithm, 2011.
- mateljou, Ordered Dithering with Arbitrary or Irregular Colour Palettes, 2023.
- mateljou, Thomas Knoll’s Pattern Dithering shader, 2023.
記事履歴
- 2026年6月19日: 公開。
- 2026年7月20日: Knollのアルゴリズムの初期化説明を修正。この解説と元のC++コードとの違いを明確化。