画像を SVG に変換する image2svg を作った

以前作った @marmooo/imagetracer のフロントエンドアプリとして image2svg を作りました。 image2svg の名前で利用したかったので分離しただけです。

image2svg

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

生成されるまでどうせ待たないといけないので Worker を使わず実装していますが、使ったほうが良いか微妙なところです。 だいたいのデータで 1秒以内に結果が得られます。 1秒以内に実行できれば他のアプリよりはかなり早いのですが、気持ちよく利用するにはまだまだ高速化が必要です。 とはいえシンプルな高速化はだいたいやりきったので、今後は Wasm 化やマルチスレッド処理を考えたほうが良さそうです。

デフォルトで使いやすいようにオプションは設定していますが、画像サイズに合わせて多少の調整は必要な気がします。 画像サイズが小さくなると lineTolerance/splineTolerance が大きくなったときに穴ができてしまうので、閾値を小さくすると良いです。 といって小さくしすぎると圧縮率が下がるので strokeWidth で調整すると良いというのがだいたいのイメージです。 しかし改めてオプションを弄ってみても、ほとんど出力が変わらないケースが多いです。 それだけ洗練されたとも言えるのですが、なかなか難しい。

画像を SVG に変換する @marmooo/imagetracer を作った

画像を SVG に変換する @marmooo/imagetracer を作りました。 他の有名なツールとしては vtracer, potrace, SVGcode, imagetracerjs があります。 これは imagetracerjs の改良・高速化版です。

OpenCV の限界

実のところ同じようなものを OpenCV を使って作ろうとしていました。 最初は 24bit color の画像に findContours アルゴリズムを適用し、 求めた輪郭から path を描写する方法を考えました。 これなら OpenCV の実装が流用できます。 ちなみに現実的には画像の情報量は多すぎるので、 cv.LUT() を使って簡易的な減色を行って情報削減することは必要です。 しかし作ってみたところ、24bit color で動く findContours は RETR_CCOMP (RETR_FLOODFILL) しかないので、 階層情報をきちんと取得できず画像を復元できないことあるとがわかりました。 また思いっきり減色しても輪郭数が数十万も残ってしまう問題が見つかりました。 findContours を自作するか、包含関係の推定を自作しないと厳しそうでした。

次に dilate で詳細な輪郭を抽出して 2値化し、RETR_TREE の findContours して、 輪郭ごとに平均色を算出する方法を考えました。 しかしこれは処理時間の大半を平均色の算出に持っていかれて、ボツとなりました。 findContours の処理で生成される内部配列を使えれば、 平均色の算出は理論上はかなり早くできるのですが、現実では使えないので駄目でした。 輪郭数は数万程度には抑えられる利点はありましたが、自作しないと早いものは厳しそうでした。 詰まるところ、findContours の実装などに色々と課題があるのですよね。 OpenCV はデファクトでしょうが、こういう問題は他にも結構あると思っています。

imagetracerjs の改良

さてどうしたものかと思って GitHub を探していて imagetracerjs を見つけました。 ラスター画像をベクター画像に変換することを bitmap tracing ということを、いまさら知りました。普通は image2svg だと思うじゃん…。 先に述べたライブラリもその後見つかったのですが、imagetracerjs は他より高速・高精度に動作するように見えます。 ただいかんせん実装が古くて使いにくいことが気になりました。そこで、 (1) 一部の不要な実装を削除して API を簡素化し、 (2) 減色と blur を外部化して汎用性を持たせ、 (3) Deno で使いやすいように ESM 化し、 (4) テストをたくさん書いて完璧な移植をし、 (5) ベンチマークをたくさん書いて高速化し、 (6) 減色処理をライブラリ化して複数選択可能にし、 (7) 生成 SVG を minify して出力するようにしたものを、 @marmooo/imagetracer として公開しました。

改良余地はかなりあるので、今後もたぶん色々改良すると思います。 たくさんテストとベンチマークを書いたので思ったより作るのに時間が掛かりました。 blur は削除してしまいましたが、このへんの前処理はそもそも他のライブラリを使ったほうが良いです。

オプションの改善

Wasm 化以外の速度改善は難しいと思うので、JavaScript 実装は細かな改善が今後の課題です。 いまはオリジナルの実装に付属していたオプションの見直しをしています。 例えばこんなことをやっています。

layering 廃止

オリジナルの実装ではエッジ検出の手法が 2つ用意されていて、layering オプションで切り替えます。 オリジナルの配列を使った実装ではあまり差がないので妥当ですが、TypedArray を使った実装に変更すると話が変わります。 色ごとに処理するよりまとめて処理するほうが圧倒的に早いのでオプションは廃止しました。 エッジ検出は最大 50倍くらい早くなっています。

mergePaths 追加

オリジナルの実装だとレイヤ (色) ごとに内部の path を別々にレンダリングするのですが、これはレンダリング速度が遅くなります。 そこで色ごとに path を 1つに merge する mergePaths を付けました。 SVG 生成速度は変わりませんが、ブラウザでのレンダリング速度は大幅に高速化できます。 手元の検証では 6倍速くらいになりました。

pathomit/linefilter 廃止 → filterHoles 追加

短い path をスキップする pathomit/linefilter オプションは高速化に役立つのですが、 ほとんど同じ処理をしているので 2つもいらない気がしますし、オリジナルの実装だと白抜きの穴ができてしまう問題があります。 細かな線を消すときには、その穴を補完する手段を用意しておかないといけません。 わかりやすいのは holed path の場合で、穴をなかったことにして親ノードの色で塗りつぶすことです。 これはおそらくオリジナルの TODO にも書いてあった課題です。

ただ non-holed path の場合、例えば前景と背景の輪郭部分では 1ドットだけ色が違うような領域が大量に発生し、 その 1ドットをどうやって補間すれば良いかの問題が起きます。 雑に考えると周囲 8マスを見てもっとも勢力の大きな色を借りれば良いと想像はでき、 これは issue #15 などでも報告されていました。 ただ non-holed path はエッジ同士が結びついて、大きさが大きくなったり最初の座標が変わる可能性があります。 オリジナルの実装はこれが原因で穴が空きます。 さらに言えば 短い non-holed path が隣り合っていたりすると、周囲から代替となる path を抽出するのが困難になります。 下手に取り除くとやはり穴になります。 この問題があるので、処理の起点は holed path で、その中にあるものを取り除くことに徹するほうが楽です。 他にも色々問題があって、色をマージする方式だと同じレイヤ内でもエッジが結びつく可能性もあります。 これはちょっとやそっとの処理では解決できないので、たぶんエッジ検出をやり直さないといけないでしょう。 結びついても別のエッジにするなら隣接ドットの置換で済みそうですが、実装は面倒臭そうです。

そこでまずは holed path に絞って filterHoles を作成することにしました。 まずは点の少ない holed path をリストアップします。 次に対応する non-holed path のレイヤ番号を知るために、path の points を 0/1 で bounding box の領域に書き込み、 bounding box の外側の点を起点として floodfill します。 その後、内側をインデックスカラー画像と照合することで対応するレイヤがわかります。 対応するレイヤがわかったら holed path より長さが短く、bounding box に含まれる path を探して削除します。 ちなみに 3x3 のサイズで □ の形ができるまでは holed path が存在せずレイヤ ID が一意に定まることを利用すると、 path length < 12 までは flooodfill をしないで済むので高速化ができます。 結果、見た目をほとんど変えずにファイルサイズを削減することに成功しましたが、意外と圧縮効果は低い (10% くらい) ともわかりました。 filterHoles オプションを作ったことで設定項目はかなり洗練されたと思います。

TODO

個人的には現状でも類似アプリの中では一番使いやすいかなあと思っているのですが、 あとは出力ファイルサイズがやや大きいところをなんとかしたいところです。 包含関係を持たず隣接しているだけのノードを良い感じにマージすればかなりサイズは小さくなりそうですが、結構難しそうです。 周囲が 8割くらい囲われていたら面積の多い方に色を寄せて path をマージしたりするのが良いかな？

Node.js でも動きますが、SVG を画像に変換して確認するテストが動かなかったです。 Deno なら動くのに test: false してリリースせざるを得ないのは負けた気分…。 制作物とはあまり関係のない resvg/sharp の細かなバグが原因なのかと思っていますが、JavaScript ランタイムの保証もなかなか難しいなと感じています。

様々な言語で作った Wasm をベンチマークした (2)

以前作ったお手軽ベンチマークを高度化してベンチマークの種類を増やしました。 減色処理では色のカウントアップの後に色のリストアップを行うのですが、 そのリストアップ処理までのベンチマークです。 前回 (countColors) は色のカウントアップ、 そのリストアップをして返す getColors、 リストアップした結果は返却せず内部に保持する initColors の 3種類にしました。 getColors は動的配列は使わなくても実装できるのですが、面倒なのでアルゴリズム上の変更はしません。 クラスや構造体や動的配列に対応していない言語、明らかに遅いとわかっている言語は実装しませんでした。 実装は @marmooo/wasm-bench にあります。

getColors ベンチマークの追加

getColors ベンチマークでは、すべて JavaScript の性能を下回りました。 結果は以下。

    CPU | Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
Runtime | Deno 1.46.3 (x86_64-unknown-linux-gnu)

benchmark                                   time/iter (avg)        iter/s      (min … max)           p75      p99     p995
------------------------------------------- ----------------------------- --------------------- --------------------------
JavaScript, Deno 1.46.3                            192.0 ms           5.2 (189.7 ms … 201.7 ms) 192.0 ms 201.7 ms 201.7 ms
AssemblyScript 0.27.30 (Number)                    286.1 ms           3.5 (233.6 ms … 322.7 ms) 307.5 ms 322.7 ms 322.7 ms
AssemblyScript 0.27.30 (Class)                     319.3 ms           3.1 (279.6 ms … 370.7 ms) 334.2 ms 370.7 ms 370.7 ms
Rust 1.81.0, wasm-bindgen 0.2.93 (Simple)             2.2 s           0.5 (   2.2 s …    2.2 s)    2.2 s    2.2 s    2.2 s
Rust 1.81.0, wasm-bindgen 0.2.93 (Serde)           337.3 ms           3.0 (316.3 ms … 355.4 ms) 351.8 ms 355.4 ms 355.4 ms
C++, emscripten 3.1.68                             390.2 ms           2.6 (368.9 ms … 401.8 ms) 398.0 ms 401.8 ms 401.8 ms

わかってはいましたが、オブジェクトの転送コストが大きいとものすごく遅くなります。 オブジェクトを転送しなければ早いので、とにかくオブジェクトを転送してはいけないことがわかります。 メモリで転送するのはプリミティブと TypedArray に留めたほうが良さそうです。

C++ は計算後に JavaScript オブジェクトへ変換するのが一番早かったです。 ちまちま JavaScript オブジェクトを触りながら作るとものすごく遅くなります。 この結果を見ると、Wasm では動的配列を JavaScript オブジェクトに変換すること自体が間違いでしょう。 Rust と AssemblyScript はメモリリークで結構ハマりました。 おそらく JavaScript オブジェクトを内部で使うと 解放のタイミングがわからなくなるのでメモリリークします。 AssemblyScript の対策はわかりやすくて、 内部オブジェクトで export しないように気を付ければいいだけです。 Rust もたぶん一緒なのですが、wasm-bindgen が自動変換してくるので見落としがちで、 きちんと手動で JavaScript オブジェクトに変換しないと怖い印象を受けました。

Rust はさらに serializer を使わないと異常に遅くなる問題に直面しました。 Rust はなんでこれが遅いの？ が結構ある気がします。 C++ や AssemblyScript は serializer を使うともっと早くなるのかも。 最終的には AssemblyScript が C++ より早くて少し驚きました。 他にも 2^20 くらいのループまでは Wasm のほうが JavaScript より早かったりするのもよくわからないところです。 メモリの再割当てが原因かな。

initColors ベンチマークの追加

getColors のようにオブジェクトの変換コストが大きいと Wasm 化する利点がないので、 変換せず内部に保持するようにした initColors ベンチマークでは、Wasm が圧倒的に高速で、最初の想像通りの結果になりました。 結果は以下。

    CPU | Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
Runtime | Deno 1.46.3 (x86_64-unknown-linux-gnu)

benchmark                          time/iter (avg)        iter/s      (min … max)           p75      p99     p995
---------------------------------- ----------------------------- --------------------- --------------------------
JavaScript, Deno 1.46.3                   188.9 ms           5.3 (173.5 ms … 213.0 ms) 194.7 ms 213.0 ms 213.0 ms
AssemblyScript 0.27.30                    148.8 ms           6.7 (123.7 ms … 187.2 ms) 160.3 ms 187.2 ms 187.2 ms
Rust 1.81.0, wasm-bindgen 0.2.93           70.3 ms          14.2 ( 63.0 ms … 104.4 ms)  74.9 ms 104.4 ms 104.4 ms
C++, emscripten 3.1.68                     43.7 ms          22.9 ( 42.4 ms …  48.8 ms)  44.0 ms  48.8 ms  48.8 ms

AssemblyScript はクラスをグルーコードとして生成できない課題があるので、 constructor と使いたいメソッドだけをクラスの外部に関数として定義するのが良いです。 面倒ではありますが、メモリリークの可能性が減るので悪くはない気がしました。 Rust は記法に慣れていないことによって時間掛かりましたが、そんなに悩みはしなかった気がします。 C++ は Array だと大きなメモリ確保ができなくて落ちることだけハマりました。 この 3つの言語は書くのも楽で、あまり迷うところがないです。 どれも uint8 を使わないほうが型変換が減るぶんだけわずかに早い気もしますが、 省メモリ動作も Wasm の利点なので真面目にしました。

結論としては C++ が鬼のように早いことがわかりました。Rust も結構早い。 opencv.js を見ていると Wasm は JavaScript より 4倍くらい早そうと思っていたのですが、 データ転送もオブジェクト変換もなければ、もっと早いかもなあ。

countColors ベンチマークの改善

前回作ったベンチマークも多言語サポートを進めました。 といっても試してみた結果、まだ実用段階にないことを確認することがほとんどでしたが。

Rust

Rust は速度が気になったので色々な方式で実装してみました。 まずはポインタを返り値として処理するときは C/C++ と同じ速度が出ることがわかりました。 しかし Vec, Box<[u32]> などを返り値として処理すると、 おそらく内部で wasm-bindgen が js_sys を使って自動型変換をしているのですが、遅くなります。 C++ の embind だと自動型変換をしても爆速なので課題を感じます。 他にもJavaScript 側で import の仕方を間違えた場合なども遅くなったりします。 unsafe { Uint32Array::view(&color_count) } の書き方を見つけてからは、これが一番楽そうかなと思っています。

Go

Go はポインタなら C/C++ に近い速度で動作します。 しかしオブジェクトを透過的に扱おうとすると、export ディレクティブが使えず、 JavaScript 化した関数をグローバルにエクスポートする処理を書く必要が出てきます。 サンプルなどを見ると globalThis にエクスポートしているのですが、 これは非常に邪魔なので ESM のように自由な名前でエクスポートしたいところです。 設計面での変更が必要そうです。

またベンチマークを取ると GC がうまく動いていないことがわかります。 Wasm は GC をセルフ実装することになるのでベンチマークを取ってみることは大切そうです。 他にも little endian がデフォルトの JavaScript と、 big endian がデフォルトの Go では整合性を取るのが大変ということがわかりました。 Go に慣れていればこのへん楽かも知れませんが、慣れていないのでね。 さらに syscall/js の Uint32Array から Index(i) して取得したデータをInt() でしか取得できないので、 uint32 で欲しい画像処理の場合、取得した時点で範囲外の数値が壊れます。 byte で取得できないと処理がかなり大変で、関数が不足しているように感じます。 範囲を指定してデータ取得もできないので、色々と限界はあります。 メモリコピーするしか解決策がわかってないのですが、これだとまあ遅くなります。

他にも GC=leaking ならテストが通るのに、その他だとテストが通らないような問題も発生しました。 さらに関数を JavaScript 化すると現状は非常に遅い問題などもあります。 issuses #32591, #46473 にも上がっていましたが、 報告からすでに 5年間も経っているので解決は時間が掛かりそうです。 使えない実装も残してはいるのでこのへんの問題が確認はできるようにしてあります。 実用面はまだまだこれからかなあ。

Zig

Zig は色々試してみましたが、文法から難しくてまだ理解できていないです。 理解の範疇でば Wasm を作りにくい気もしていて、その理由は関数の返り値です。 配列を JavaScript と共有するにはヒープに明示する必要があるようなのですが、 alloc の成否をチェックする必要があって error union ポインタが返り値になります。 しかし C 互換で export する時はこの機能を使えません。といってキャストもよくわからなかったです。 オプショナルポインタで表現するのも駄目なので、どうすれば良いのかわからなかったです。 C/C++ のポインタは実質 NULL を取り得るオプショナルポインタだと思うのですが、わからん。 グルーコードも生成してくれないので実行までのハードルも高いです。 zig-js とかあるし、できないことはないはずなんだけどなあ。

Java

Java はサンプルを見たら、割と簡単に変換できることがわかりました。 やはり設定ファイルがわかりやすいと、初心者にはわかりやすいです。 ただ Java には参照渡しがない問題があるので、どうするのかと思っていました。 案の定、issue #907 を見ていても、 メモリに領域を確保しようとしたときアドレスを渡す手段がない話をしていました。 アドレスを使わないと、バイナリデータの処理は、 値渡しで画像を渡して、処理して、値渡しで返す必要があるので遅いです。 あと uint32 がないので画像はバイト単位でシフト演算するしかないでしょうが、 わずかに遅くなることも予想できます。 つまり countColors と似たなにかは実装できても、同じものは実装できない認識です。 Java で配列などを Wasm を通じて透過的に処理するためには、 事実上変化がなくても変更可能性のある一般的なデータ型の内部位置をコンパイラ側で保証し、 マッピングする必要があるのでしょうかね。 人気言語の中では Wasm 利用に課題が多いかも知れません。

Kotlin

Kotlin は文法が簡単な一方で、設定ファイルが難しいのが欠点です。 サンプルで main 文を動かす方法はわかりましたが、関数のエクスポートがわかりません。 現状は Wasm のドキュメントが皆無なのでカスタマイズができないです。 まだ main 文以外はサポートしていないかな？ Java 派生ですが、Java と異なり UintArray があるのでマッピングは楽かも知れません。

Scala

Scala + Scala.js は サンプルプロジェクト を眺めてみたら、 独自の sbt 設定ファイルの内容が難しすぎて、書ける気がしなかったです。 それとも見たサンプルがいけなかったか。Scala も uint32 がない問題があります。

Dart

Dart は文法も簡単だし、簡単に Wasm を生成できるので良い感じです。 ただすぐに使える dart compile wasm コマンドでは main 文の export しか現状できないので、今後に期待です。 dart2wasm という非公開の公式ビルドツールを使うと wasm:export も使えるようなのですが、 ビルドツールを用意するのは大変そうなので諦めました。 wasm:export できるようになれば一気に使いやすくなると思いますし、 公式サポートされたらベンチマークもすぐ追加できそう。 Dart にもポインタがないですが、Uint32List があるのでマッピングは簡単そうです。

MoonBit

MoonBit は簡単なので良い感じですが、グルーコードは生成できなそうに見えます。 クラスや構造体を定義するのはあまりにも面倒なので、進化に期待したいところです。

まとめ

Wasm ビルドのコードをたくさん書いてみた結果、言語自体の話は置いておくとして、 ビルド環境自体の使いやすさは以下で決まるとわかりました。

1. 簡単にビルドできる (Scala は課題あり)
2. グルーコードを自動生成できる (MoonBit と Zig は課題あり)
3. 関数が export できる (Dart と Kotlin は課題あり)
4. 高速安定動作する (AssemblyScript と Go は課題あり)
5. JS オブジェクトと自動型変換できる (現状 C++/Rust のみ)

4 までは実利用を考えると必ず欲しい機能です。 まとめると C++/Rust は現状 Wasm を非常に書きやすい言語ということです。 AssemblyScript もかなり良いです。 5 は現状最も実装の進んでいる emscripten や wasm-bindgen を使っても性能は出ないので、 実質的にはちょっとしたクラスや構造体のエクスポートと、 TypedArray をサポートしていることが重要になりそうです。

現状は C++ が一番楽だし高速そうですが、Rust も実用レベルと思います。 今回のコードでは適用できなかったですが、どちらも autovectorizer が組み込まれているので自動 SIMD 化も期待できます。 サクッと Wasm にしたいだけなら AssemblyScript も良い言語だと思います。 他の言語はまだ厳しいかなあ。でもどの言語もまだ Wasm 対応は始まったばかりなので、 今後に期待が良いと思います。次は Kotlin/Dart あたりが面白そうかな？

様々な言語で作った Wasm をベンチマークした (1)

Wasm は様々な言語から作ることができますが、その実行速度が気になったので調査しました。 計測に使ったのは減色処理をする時に必要な、画像内にある色のカウントアップ処理です。実用的です。 WasmGC を使うとまた特性が変わるような気もするのですが、ひとまず現状チェックです。 実装は @marmooo/wasm-bench にあります。



独断と偏見により AssemblyScript, C/C++, Rust を調査しました。 本当は Go も確認はしていて、int 処理くらいならできたのですが、 Uint8Array を引数として渡すことができなくて諦めました。 最近は TinyGo がかなり小さな Wasm を生成できるようになっていて (70KB〜)、速度が出るなら十分候補になるような気がします。 しかし Uint8Array などの型変換がまったくわからない…。

Zig も試してはみましたが、文法がわかってないのでうまくいきませんでした。 Zig のほうが文法はシンプルなので粘ればできたかもですが、ChatGPT さんも手助けにならないので粘っていません。 他に有名なのは Grain, MoonBit あたりでしょうか。 ざっとドキュメントを読んだ感じだと MoonBit は Uint8 がないのでまだ早い。 Grain はアリかも知れない。 ChatGPT さんの手助けが期待できるくらいになったら再チャレンジしてみるかも。

ベンチマーク結果

結論から言えば、C/C++ が最速で、その他の Wasm は JavaScript よりちょっと早いでした。 また C/C++ 以外の Wasm にほとんど差がないのがポイントです。

    CPU | Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
Runtime | Deno 1.46.3 (x86_64-unknown-linux-gnu)

benchmark                           time/iter (avg)        iter/s      (min … max)           p75      p99     p995
----------------------------------- ----------------------------- --------------------- --------------------------
JavaScript, Deno 1.46.3                    166.8 ms           6.0 (164.1 ms … 171.8 ms) 169.6 ms 171.8 ms 171.8 ms
AssemblyScript 0.27.29 (Wrap)              153.8 ms           6.5 (150.1 ms … 155.0 ms) 154.4 ms 155.0 ms 155.0 ms
AssemblyScript 0.27.29 (Shift)             175.2 ms           5.7 (174.1 ms … 175.8 ms) 175.4 ms 175.8 ms 175.8 ms
AssemblyScript 0.27.29 (DataView)          156.5 ms           6.4 (156.0 ms … 157.8 ms) 156.5 ms 157.8 ms 157.8 ms
Rust 1.81.0, wasm-bindgen 0.2.93           147.4 ms           6.8 (142.9 ms … 154.1 ms) 147.4 ms 154.1 ms 154.1 ms
C, emscripten 3.1.67 (Simple)              100.7 ms           9.9 ( 99.7 ms … 101.5 ms) 100.9 ms 101.5 ms 101.5 ms
C, emscripten 3.1.67 (Struct)              100.0 ms          10.0 ( 93.0 ms … 101.5 ms) 100.9 ms 101.5 ms 101.5 ms
C++, emscripten 3.1.67 (Simple)            102.6 ms           9.7 (100.5 ms … 103.3 ms) 103.0 ms 103.3 ms 103.3 ms
C++, emscripten 3.1.67 (Class)             102.1 ms           9.8 (101.6 ms … 103.4 ms) 102.2 ms 103.4 ms 103.4 ms

AssemblyScript

AssemblyScript は、ほぼ TypeScript で記載できる Wasm 生成用言語です。 Union と型エイリアスと destructures を使えないのがつらいけど、まあなんとかなります。

コンパイルオプションが非常に多いです。 色々と最適化しながら計測してわかったことは、Wasm の実行速度の大半は GC に依存していることです。 GC を切ると 2倍以上速度が上がります。 デフォルトの Incremental GC では JavaScript より遅いですが、 --runtime minimal --exportRuntime オプションを付けて GC を手動にすると、 Rust で作った Wasm と同じ速度になり、安定します。

デフォルトの Incremental GC はかなり実行速度にブレがあって、 少し書き方を変えるだけでとんでもなく速度に差が出ます。 先ほど 2倍以上と書きましたが、書き方によっては 4倍くらい遅くなります。 これだと検証が大変になってあまりよろしくないですが、 手動の GC にするだけで非常に安定した性能になることから、 性能低下の大半が GC によるものだとわかります。 GC が性能の大半を占める特徴は、他の言語で作った Wasm にも言えることだろうと思います。

現時点では手動 GC でないと厳しい印象ですが、 そこさえ許容すれば実用に耐える状態に仕上がっている印象です。 ベンチマークにも AssemblyScript を使った様々な実装を残してあるので、 オプションを変えて実行すれば Incremental GC の挙動は確認できます。

AssemblyScript は GC 以外にも様々なオプションがありますが、 GitHub の issues などを眺めていると、 ファイルサイズは最適化しないほうが速度面で良いようです。 まあインライン化などの最適化をした時にサイズが増えることから、想像は付きますね。 現在利用している実行オプションは以下のようになっていますが、一番よく効くのは先に書いた --runtime minimal --exportRuntime で、 残りのオプションはちょっとずつ効果があるという感じです。

asc countup.ts -o countup.wasm --bindings esm \
  --runtime minimal --exportRuntime \
  -O3 --converge --noAssert --uncheckedBehavior always

C

C はポインタ以外は JavaScript と書き味が一緒なので、割と気軽に書けます。 面倒なのはたいていドキュメント不足の環境整備ですが、Wasm を作るだけなら emscripten をインストールするだけなので迷うことはないです。 C/C++ で作った Wasm はメモリリークの危険性がある手動管理です。 GC でマークを付けないことが大きそうで、Rust / AssemblyScript より明確に早いです。 そんな訳で Wasm で速度を出したいときには C/C++ が最強のような気はします。

ただ Rust / AssemblyScript で作った Wasm と異なり、JavaScript からの呼び出しが面倒です。 malloc してポインタとサイズを渡して使い終わったら free が必要です。 データのサイズを渡さないといけないので実装が複雑になります。 他の言語に慣れているとかなり面倒で、早いとわかっていてもあまり使いたくないです。 AssemblyScript で同様のメモリ管理機能ができたら、絶対そっちを使うと思う。 薄いラッパーがあれば欲しいです。ラッパーがあればかなり使いやすくなる気はします。 というわけで JavaScript でお手軽な Struct <-> TypedArray ラッパーを書いて、簡単に使えるようにして (?) 比較してみましたが、速度低下はありませんでした。

実行オプションはこんな感じ。実質 -O3 だけで、他は利用しやすくするための設定です。 今回書いた程度のベンチマークでは大差ないようですが、 -flto --closure 1 も入れておくと良い みたいです。 -s EXPORTED_FUNCTIONS=_malloc,_free は入れておかないとメモリ管理ができないので、実質的に必須です。

emcc countup.c -o countup.js -O3 -flto --closure 1 \
  -s MODULARIZE \
  -s EXPORT_ES6=1 \
  -s ALLOW_MEMORY_GROWTH=1 \
  -s EXPORTED_FUNCTIONS=_malloc,_free

C++

C++ もポインタ以外は JavaScript と書き味が近いので、まあなんとかなります。 C++ で作った Wasm は Embind がクラスと関数の定義を渡せば自動でバインディングしてくれます。 バインディングの方法は理解するのに非常に時間が掛かりましたが、わかれば非常に使いやすいです。 コンパイルするときはクラスをバインディングするために --bind を付けるだけです。 固定配列ではなく std::vector にバインディングされるので、将来的に TypedArray が可変的になった時にも対応しやすいです。 TypedArray は今は固定長だけど、ES2024 Resizable ArrayBuffers には注意が必要なのかも知れません。 でも C++ なら心配なさそう。 欠点は Wasm のサイズが少し大きくなることですが、許容範囲です。 Wasm を作るのにはかなり良い言語だなと思いました。

emcc countup.c -o countup.js -O3 -flto --closure 1 \
  --bind \
  -s MODULARIZE \
  -s EXPORT_ES6=1 \
  -s ALLOW_MEMORY_GROWTH=1

Rust

最近の高速化でよく使われる癖つよ言語ですが、Wasm は割と簡単に作れます。 wasm-pack をインストールして、Cargo.toml に設定するだけで作れるので、言語仕様の理解だけが問題です。 正確な速度差はさらに調査しないとわかりませんが、上記の結果では Rust で作っても AssemblyScript で作っても速度差はそれほどなさそうと思いました。 癖つよの言語仕様を覚えるよりかは、AssemblyScript でも良いかなと思ったりもしました。

ただ、特別なメモリ管理をしないでも速度が出る利点を考えると、やはりライブラリには使いやすいのかな。 今回調査した以外の言語で Wasm を作る場合も、特別なメモリ管理をしないでも速度が出るかどうかは、それなりに重要な差になりそうです。 Cargo.toml は以下の最適化を入れています。

[profile.release]
lto = true
codegen-units = 1
opt-level = "z"

あとは wasm-pack で release モードの Wasm で出力するだけです。

wasm-pack build --target web --release

ネットでは AssemblyScript が遅い！の記事が多かったのですが、最適化すると割と戦えるっぽいです。 もうしばらく AssemblyScript で遊んでみようと思います。 --runtime stub にしたとき C/C++ と同じようなメモリ管理ができると良いのですが、できないっぽいかな？ いまいちよくわからないです。 ベンチマークの種類も増やすかも。

画像減色ツール 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 も使っていこうと思います。

画像を線画に変換する Lineart Converter を作った

AIを使わないで写真を線画へ変換するアプリ Lineart Converter を公開しました。 絵柄が変わることなく高速・省メモリに動作します。 線画以外も生成できます。素材生成にご利用ください。

Lineart Converter

何も設定しないでもこれくらいの変換はできます。 設定するともっと色々できます。

最近の AI は高性能なのでみんなが色々なことをやっていますが、 私はメインマシンのメモリが 4GB なので GPU ゴリゴリの話はあんまりなあと思っています。 ただ AI を使って色々やっている人のを見ていて、 画像から線画を作るくらいなら OpenCV で十分じゃないのと思ったので、 お手軽な線画変換ツールを作ってみました。色塗りで遊ぶくらいならこれで十分そうです。

Wasm + SIMD + Threads でサクサク動作しますが、JavaScript もかなり高速なので、1つでも処理をミスると JavaScript のほうが早かったりします。 たとえば白黒画像を透明化する機能も作ってはみたのですが (GUI にはないけど…)、JavaScript のほうが早かったです。 JavaScript は 24bit 画像に直接書き込めるので最適化しやすいですが、 OpenCV だと 8bit にしたり 24bit にしたり色々やることが多く最適化しにくいので、場合によっては遅くなるということです。 OpenCV の詳しいコードまで見ていないので正確なことはわかりませんが、 きちんと最適化すると案外 SIMD を使わなくても JavaScript のほうが早いケースが結構あるかも。

アルゴリズム

線画を作るアルゴリズムは Canny と adaptiveThreshold と dilate の 3つに大別できると思います。

Canny

Canny はベタ塗りや太い線が白抜きになり、また線が正確に抽出できなかったり、閉路になりにくい欠点があります。 特に線画正確に抽出できないのが今回は厳しいので、何らかの改善がないと利用は厳しいかなあと思っています。 改善手法などを軽く探していたら、計算過程を可視化した良いエントリがありました。 線画に適したものは初期段階で十分抽出できていますが、 途中で大量に drop することがわかります。線画には使えそうにないかな。

adaptiveThreshold

adaptiveThreshold はベタ塗りや太い線が保持され、線が正確に残る利点があります。 局所的な陰影を頑張って拾うのでたいていの写真で申し分ない二値化ができますが、 アニメ絵のように割とフラットな画像では、頑張った結果ノイズになることもあります。 境界の薄い画像は、灰色化した後に二値化することから、エッジが失われる可能性がそれなりにあります。 その場合は平凡な threshold で輝度をフィルターすると良いことが多いです。 cv.LUT() で輝度フィルターした後に adaptiveThreshold を 適用する方法も考慮の余地はありますが、そこまですべきかは微妙です。 threshold の輝度フィルターで色の薄い部分が除去できていると考えれば大差ない気もします。

dilate

dilate は 1回適用しただけで、濃淡の薄い画像も含めてほぼ完璧なエッジが得られる利点があります。 ただし見えにくいノイズがたくさんあって、またエッジが取れすぎてしまうので、除去が難しいことが欠点です。 結局は adaptiveThreshold か threshold を利用することになりそうです。 やはり adaptiveThreshold がうまくいくケースが多いですが、 ノイズが複雑なときは大局的なフィルターのほうが良い時もたまにあります。 薄い線をバキッと消したい時には threshold も使えます。

TODO

人間が調整する必要はありますが、AI と十分勝負はできてると思います。 課題があるとすれば、(1) ギザギザの線の平滑化、(2) 濃淡のないラフ画への対応などでしょうか。 1 は頑張れば解決できる気はしますが、2 は線を消すのが難しそう。 考えるべきことは色々ありますが、だいたい動くようになったので、いったんリリースです。

作ってみて改めて思ったのは、 AI を使わないで漫画風やアニメ風の画像を用意するのが、すごく大変ということでした。 雑にどこかの著作物である画像をサンプルに載せるのは簡単なのですが、 きちんと権利関係を処理しながら載せようとすると、サンプルを用意するだけでも大変でした。 AI を使うとそのへんの問題がサクッとしてしまうので、うーんという気分です。

簡易的な暗視カメラ Nocto Camera を作った

OpenCV の練習で簡易的な暗視カメラ Nocto Camera を作りました。 暗視カメラと書いていますが、露出不足の環境でも綺麗に撮影ができるカメラアプリです。 画像のコントラストを補正する画像アプリとしても使えます。 暗視カメラとか使ったことないし、使う人もそんなにいない気がするのですが、 今回は OpenCV のアルゴリズムの精度と速度を確認する勉強目的で作ったので、まあ良いです。

Nocto Camera

たとえばこんな感じになります。

アルゴリズムは CLAHE ヒストグラム平均化を利用しています。 類似アルゴリズムとしては ToneMap を使った HDR (High Dynamic Range Imaging) があります。

Tonemap

ToneMap は露出時間の異なる撮影を行った画像が複数枚必要なので、 CLAHE ほど手軽には使えないアルゴリズムなのかなと理解しています。 ToneMap を使うとしたら露出時間の異なる撮影データを自動で用意しないといけません。

Web 上だとカメラ撮影でも複数の撮影データを自動で用意するのはなかなか難しいです。 iPhone/Android の 自動 HDR はおそらく ToneMap を利用していますが、 カメラが 1つしかない iPhone 7 時代から HDR 機能はあるので、 露出時間を変えたものを同時に撮影して ToneMap をしていると予想できます。 ただこれと同じようなことを Web 上で実現しようとすると、 まずは exposureTime を設定してカメラを起動する必要があります。 iOS では exposureTime の設定自体が存在しないので、現状できません。 iOS 以外だとカメラの設定変更と撮影を繰り返せば実現はできそうですが、 切替に多少時間が掛かるため撮影に時間が掛かりそうです。

ビデオ撮影の場合、最近の iPhone のようにカメラが複数付いていれば、 露出時間をそれぞれ変化させて動画撮影して ToneMap させたり、 カメラの撮影条件を微妙に変えて推定できるのかなと思ったりしましたが、 ハード依存が強いのでパスしました。

CLAHE

さて CLAHE についてですが、完全に真っ暗の環境で Webcam 撮影した時は、あまりうまく行きませんでした。 暗すぎると物体があるかどうかすらきちんと判断できないので、 綺麗な表示をするためにはある程度の光源が必要です。 光源が強くないときちんと動作しないようでは暗視カメラとしては残念ですけね。

ただ表示の綺麗さを求めなければ、 clip limit を 0 にしたとき良い感じの暗視カメラとして動作します。 これは輝度値が 0/1 の差しかなくても反応するモードなのでノイズが非常に多いですが、物体も発見しやすくなります。 パソコンの黒画面程度の光しかない環境でも、近場にあるものは非常に綺麗にカラー判別できることがわかりました。 ちなみにパソコンの白画面程度の光があれば、数メートル離れたところにあるものは何となく判別できる、くらいの精度では動作します。

ノイズが大きいのは 8bit で処理しているせいもあるかも知れませんが、ビット数を増やすと処理速度の問題が出てきそうです。 確認していませんが、CLAHE は 16bit で処理させることもできるようです。clip limit = 0 の時には使えるかも？

equalizeHist, Gamma correction

equalizeHist() でもだいたい良い感じの結果は得られます。ただ明るい部分だけが明るくなりすぎるのが欠点です。 Gamma correction は色を暗い環境に合せて表示できるので、安定した結果が得られます。 ただ暗すぎるときは詳細を得られません。 色を変えずに詳細部分を強調したいなら CLAHE が向いていますが、暗すぎるとあまりうまく行きません。 そこである程度暗いときには equalizeHist() + CLAHE か、Gamma correction + CLAHE のように組み合わせるのが良い感じです。 詳細を得るにはやはり CLAHE はあったほうが良さそうです。 どちらのメソッドも 8bit で動くので、ノイズに関してはあまり深く考えないほうが良いかも。 ただこれらは 8bit でも影響は少ない気がします。

TODO

とりあえず現状でもまあまあ使えるかも知れませんが、カメラの起動オプションなどを弄ればさらに精度は上がる可能性があります。 ただ Web API からいじるのは現状だと不安定感があり、iOS のサポートもできないので、 現状ではこれ以上は欲張らないほうが良さそうです。 iOS が advanced options をサポートしたらまた改良してみます。