mieki256's diary

pip install Pillow -U
pip install tqdm -U

使い方は以下のような感じ。--mode N でアルゴリズムを選べる。

py yliluoma_ordered_dither.py -i scene.png -o scenedither_m0_8x8.png --mode 0
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m1_8x8.png --mode 1
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m2_8x8.png --mode 2
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m3_8x8.png --mode 3
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m4_8x8.png --mode 4
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m5_8x8.png --mode 5
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m6_8x8.png --mode 6
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m7_8x8.png --mode 7
py yliluoma_ordered_dither.py -i scene.png -o scenedither_m8_8x8.png --mode 8

一応、ヘルプ表示も載せておく。

> py yliluoma_ordered_dither.py --help
usage: yliluoma_ordered_dither.py [-h] -i INPUT -o OUTPUT [-p PALETTE] [-d DITHER] [-m MODE] [-c]

Yliluoma ordered dithering 1, 2, 3, 4

optional arguments:
  -h, --help            show this help message and exit
  -i INPUT, --input INPUT
                        Input png filename
  -o OUTPUT, --output OUTPUT
                        Output png filename
  -p PALETTE, --palette PALETTE
                        Palette file (.png or .gpl)
  -d DITHER, --dither DITHER
                        Dither type 2,4,8 (2x2,4x4,8x8). default: 8
  -m MODE, --mode MODE  job kind 0 - 8. default: 3
  -c, --ciede2000       Enable CIEDE2000 (mode 6 only

mode の違いは以下のような感じ。元記事を読まないと分からないとは思うけど…。

• mode 0: アルゴリズム1。2色の組み合わせを意識して差し替えるべき色を求める。かなり遅い。
• mode 1: アルゴリズム1。mode 0 の改良版。突飛な色の組み合わせは除外する。かなり遅い。
• mode 2: アルゴリズム1。mode 1 の改良版。ガンマ値を正しく反映させる。かなり遅い。
• mode 3: アルゴリズム1。mode 2 の処理高速化版。ループを回さずに数式で近似値を求める。少し早い。
• mode 4: アルゴリズム1。3色の組み合わせを意識して処理する。かなり遅い。
• mode 5: アルゴリズム2。N色の組み合わせを意識しないで色を求める。かなり遅い。
• mode 6: アルゴリズム2。mode 5 の改良版。ガンマ値を正しく反映させる。かなり遅い。
• mode 7: アルゴリズム3。mode 6 の改良版。かなり遅い。
• mode 8: Adobe Photoshop っぽいアルゴリズム。結構早い。

このスクリプト、とにかく処理が遅い…。CPU: AMD Ryzen 5 5600X を使って、289x176ドットの画像に対して、16色でディザリングをかけるのに、最悪8分ぐらいかかる…。もちろん、使うアルゴリズムにもよるのだけど…。

比較的変換処理が速いのは、--mode 3 と --mode 8。

• mode 3 は、ループを回して総当たりで相応しい色を探さずに、数式で大まかに合いそうな色を探すアルゴリズム。ただ、速くはなるけれど、生成画像の品質は落ちる。
• mode 8 は、Adobe Photoshop で使われていたらしいアルゴリズム。品質と処理速度のバランスが取れている。ただ、生成画像は全体的にボケ気味な印象を受けた。

それ以外のアルゴリズムは、まあ、遅い。とんでもなく遅い。

改善策は、いくつか思いつく。

元記事のソースは 8x8 のディザで処理しているけれど、見た感じ、4x4 のディザでも十分かなと思えた。8x8のディザだと、一番深いところで64回ループが回るけど、4x4なら16回のループで済むので、単純計算で約4倍の速さになりそう。

並列処理を導入するのも手かもしれない。Python で並列処理をさせる方法が分からなかったので今回は試してないけど、今時のCPUなら4コアだの6コアだの持ってるだろうから、1/4、1/6 の処理時間で済むのではなかろうか。実際、元々のC++版は、OpenMP(?) を有効にしてビルドして、並列処理する実行バイナリにしたら爆速になった。

画像の全てのドットに対して、毎回ループを回して、適切なパレットカラーを求めているあたりがアレだろうなという気もする。どれかしらの要素を事前に計算してキャッシュしておいて、そのキャッシュを使い回すようにすれば、もうちょっと改善されるかもしれない。例えばベタ部分が多い画像の場合、画像内に出てくる色の数は限定されるはずで、以前計算したことがある色が出現したら、その時の計算結果を再度使う、という作りにするだけでも効果はありそう。

元記事にも書いてあるけど、kd-tree 等を導入すれば改善される可能性もあるのだろうなと…。画像内のとある色について、差し替えに相応しい色はどれか、と探すあたりで時間がかかっているので、探索時間が短くなれば効果はあるはず。

このスクリプトで実験した後、減色ツールの OPTPiX や Yukari を使って減色をしてみたら、どれも一瞬で結果が返ってきて…。もしかすると1秒もかかってないのでは…。

それらはおそらくC/C++で書かれているのかなと想像するのだけど、それにしても処理時間が違い過ぎる。おそらく、アルゴリズムからして、もっと上手いやり方があるのだろう…。