画像減色ツール Color Reducer を作った

減色ツール Color Reducer を作りました。

作った理由は cv.LUT() で色数を減らせるはずと思ったのですが、 ネットで解説が見つからなかったので、確認のために作りました。 他にもたくさん作り方はありますが、cv.LUT() を使うと高速なはずです。

Color Reducer

たとえばこんな感じの減色ができます。

特にひねりのないツールですが、D&D やクリップボードからコピー (Ctrl+V) など、 結構使いやすいようには作っているので、普段使いのツールとして重宝します。 opencv.js を使うと手軽に高速な実装ができるかなと思って作り始めたのですが、 今なら porffor に期待したほうがビルドサイズを抑えられて良いかも知れません。

減色アルゴリズムは 均等量子化、k-means、Median cut、Octree などがあるらしいです。 意外と少ない。良い感じのソフトで使っているのは Median cut が多いようです。 Median cut は細分化量子化法 (Tapered quantization) の一種で 他にも色々あるようですが、最初に雑に考えて作ったものは 均等量子化 (uniform quantization) でした。

Median cut も最適化すると結構早い

最初は cv.LUT() を使った均等量子化を確認するためだけに作り始めたアプリだったのですが、 きちんとした減色処理の実装が他のアプリで必要になってきたので、Median cut も Octree も JavaScript で確認用に実装しました。 ちなみに k-means quantization も実装はしてみたのですが、削除しました。 MSE の低さに利点はありますが、初期化の仕方、終了条件に曖昧性が高い問題があり、 なにより速度が絶望的に遅いです。

できる限り高速化してみると、たいていの画像は細分化量子化法と遜色ないレベルで動作しました。 Median cut や Octree の JS 実装としては鬼のように早いと思う。JavaScript もきちんと書けばできる子です。 一番の気付きは、RGB ずつカウント処理するより同時に Uint32Array で処理するほうが圧倒的に早いということです。 ただ RGB の平均色を求めようとしたりソートするときは変換コストが高いのか Array のほうが早かったりします。難しい。 結構色々な高速化を試したのでインパクトが大きかったものをまとめると以下です。

• String Map → int Map (x3)
• int Map → 2^24 Array (x2)
• 2^24 Array → 2^24 Uint32Array (x2)
• Array.sort() → bucket sort (x1.5)
• Object → Array (+30%)
• 色数のキャッシュ (+30%)

その他の改善ももちろん大切で、画像処理だと基本的にループの速度が命となります。 2^15 くらいまでのデータのループ処理は Array のほうが早いですが、それ以上は TypedArray のほうが早いです。 ループ処理の方法も、Array の for of は論外として、forEach は 2^16 くらいまで for と大差ないですが、2^24 だと明確に遅いです。 1920 x 1080 x 4 = 8294400 ≒ 2^23 なので forEach は使えません。 他に参考になったことは arr1.push(...arr2) です。 concat や 1個ずつの push と比較して高速ですが、Maximum stack call size に注意が必要です。 色数のソートに使っているのですが、理論上 65536 回呼び出す可能性があります。 spread 記法は Chrome だと 2^16 は許可されていますが、2^17 は駄目みたいで割と怖い。 駄目なら件数を絞って spread 記法を使うだけなんですが、2^17 でさえ弾かれたのはびっくりしました。

一番難しいと思ったのは、要素数が少ない時には通常の配列のほうが TypedArray の数倍くらい早いので、 小さなデータは多少のコストを支払ってでも通常の配列にしたほうが早いということです。 たとえば Uint32Array に入っている RGBA データをそのまま扱うより、シフト演算で Number を抽出して、通常配列に戻した上で処理するほうが早い。 このへんが Wasm との速度差になっているかもなあ。 他にも RGB を配列の添字で表現して抽出するより、RGBA 数字データからシフト演算で RGB を抽出するほうが早かったりするのは、データ構造を考える上では興味深かったです。

他にできそうなことはソート済みの色で min/max の計算を減らしたり、レンジをキャッシュしてバケットソートのロスを減らすなどの、地味な改善くらいでしょうか。 前者はループのキャッシュ効率のほうが影響が大きいため、ループを分けて書くと効果がありませんでした。 効果があるようキャッシュ効率を考えてコードを書くと行数がものすごく増えるので止めました。 あとは木構造のキャッシュで改善することはわかっていますが、劇的に改善する訳でもないので、いまは採用していません。 他にも Worker Threads の最適化も実験はしてみたのですが、 SharedArrayBuffer への複製コスト、Worker の起動コストが大きすぎて (50ms!)、重い処理以外は高速化できそうにありませんでした。 画像処理だと Web Worker でマルチスレッド処理しても遅くなることのほうが多そう。

画像の圧縮

さて公開しようかと思った矢先に ブラウザの toBlob() だと 出力オプションの設定ができないせいで、減色はできているのに PNG のファイルサイズが減らないことに気付いたので、 ファイルサイズの圧縮もできるようにしました。 設定なしで PNG8 にするのは困難としても、toBlob() の quality すら動かないのは如何なものか。

PNG

PNG の圧縮が地味に課題で、ライブラリに困りました。 古いライブラリだと Node.js 依存の pngjs か、 ESM 非依存と実装の問題がある UPNG.js あたりが使われるのかも知れません。 ただまあ上記の理由によりどちらも使いにくいです。 たまたま見つけたのだと image-js は使いやすいかも知れませんが、JS 実装です。 速度だけをみると sharp というのが凄いみたいですが、Node-API だからこれも使えないです。 将来的には livips の wasm として wasm-vips が有望なのかも知れませんが、少しファイルサイズがでかい気もします。 つまり何を使えばよくわからない。そんなせいもあってか自作している人もいるのですが ( 1, 2)、 これらもライブラリとしては使いにくい。

どうしたものかと思っていた時、denosaurs/pngs を見つけて採用しました。 使ってみた感触としても、シンプルでかなり良い感じです。 他には squoosh の Wasm や wasm-codecs を見つけましたが、 内部で使われている Oxipng はロスレス圧縮なのでインデックスカラーには対応していません。

GIF / JPEG

GIF にもインデックスカラーを使った減色方式があるのですが、ロスレス圧縮ですし、アニメーションなどを対応するのは難しいので今回はサポートしていません。 JPEG にはインデックスカラーがありません。 JPEG は mozjpeg / Guetzli / QOI など圧縮ツールによってアルゴリズムが違うのですが、 私はまったくこだわりがないので、ブラウザさんの出力する JPEG 画像にお任せしたい気持ちしかありません。 mozjpeg は Chrome の JPEG 実装より少し効率的らしいのですが、WebP のほうが効率的だしなあ。

今時使われる画像形式は、.png, .jpg, .webp (と .gif) くらいなので、ブラウザの機能を活かしてこの 3つだけサポートしました。 細かな圧縮オプションについては対応していたらキリがないし、無意味なオプションが増えるだけなので、最強圧縮だけサポートしました。 色々遊んでみましたが、今となっては画像圧縮ツールは Scratch のような WebP をサポートしていないアプリに対応するくらいの意味合いしかない気がします。 最近は WebP をサポートしていないアプリはだいぶ減ってきて、Blogger でさえサポートしました。 サポートしていないのは Scratch くらいに感じます。

ベンチマーク

他のアプリでも使うのでベンチマークを取ってみたところ、 opencv.js の Wasm と JavaScript で実装した均等量子化の速度が 4倍ありました。 やはり画像処理などでは Wasm のほうがかなり高速のようです。 それ以外の実装については、画像のサイズにもよりますが、何の推論も行わない均等量子化と比較して、 Median cut が 〜2倍、Octree が 〜1.5倍くらいの差しか生まれませんでした。かなり早い。 頻度を考慮した時に Octree より高速な分割処理は計算の省略以外ではほぼ考えられないので、ベースライン的な速度になりそうです。 重要なのは Median cut のような精度面の改善になりそうですが、k-means まで来ると使い物にならないです。

Wasm

既にかなり高速ではあるのですが、さらに 4倍近く高速化できそうなので、早く porffor を使って wasm 版も作りたいです。 既にコンパイルできることは確認しているのですが、Wasm exports したときにどうやら動かないので、引数で ImageData を渡して実行するのが難しいのが現状です。 何らしらの import/export 機能さえあれば、あとはちょっとしたコードの変換で動くものはできるはずですなので、早く欲しい。 JavaScript で Wasm を書ければ、下手に C や Rust で Wasm を書くより管理が楽そうなのも porffor の良いところですね。

ちなみに AssemblyScript も軽く試してみたのですが、TypeScript にした上でいくつかの記法をダウングレードしないといけなくて、気軽な変換は難しい印象でした。 Union と型エイリアスを使えないのが痛すぎる印象で、変更量がかなり多くなります。 ちなみに Wasm は元々クラスをサポートしていないので、クラスを使うにはインスタンスを生成するだけの関数を作って export するのが逃げ道のようです。 同じことは Rust を使った Wasm にも言えて、クラスのように扱おうとすると JavaScript 側でのラップが必要です。 オプションなども定義し直さないといけない問題があります。

まとめ

勉強ついでに雑に 1日で作るつもりだったのですが、median cut に手を出したら色々必要になってしまい、なぜか力が入ってしまったアプリになりました。 既存のアプリと比較しても高速・高機能なので、これからは自作の Color Reducer も使っていこうと思います。