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 ランタイムの保証もなかなか難しいなと感じています。
0 件のコメント:
コメントを投稿