Canva Ship Shape：手描きの図形をベクターに変換するShape Assist
(canva.dev)- CanvaのShape Assistは、Draw toolで揺れた線で描かれた単一ストロークの図形をブラウザ内で認識し、きれいなベクターグラフィックに変換する機能
- ルールとしきい値に依存するコンピュータービジョンのヒューリスティックは、四角形・円・三角形には使えたが、雲・星・ハートのような複雑な図形や新しい図形の追加には限界があった
- モデルはストロークを画像ではなくx・y座標シーケンスとして扱い、クライアント側で実行するためにCNNではなくRNN/LSTMベースの構造とカスタム推論コードを採用
- 最終モデルは
P = 25、H = 100、N = 9設定の単一LSTMレイヤーとGemmレイヤーで構成され、64,109個のパラメーターと約250KBのサイズで、最新のノートPCでは10ms未満で実行される - サーバー往復なしで動作しつつ、ユーザーが図形を描いたあとカーソルを1秒以上保持し、事前定義された図形と十分に一致する場合にのみ自動置換されるよう設計されている
Draw toolとShape Assistの役割
- CanvaのDraw toolは、ユーザーがデザインに直接描いた絵を追加できるようにする
- Shape Assistは、手ぶれのある落書きをより滑らかなベクターグラフィックに変換するために作られた
- 分類のレイテンシーが重要な条件だったため、サーバー処理ではなくブラウザ内実行を選んだ
- ユーザーは図形を描くとすぐにフィードバックを受け取れる
- サーバーベースの処理で生じる遅延を避けられる
- 継続的なインターネット接続がなくてもオフラインで利用できる
ヒューリスティックからMLモデルへ移行した理由
- 初期のShape Assistは、ユーザーが描いた座標の幾何学的特性を分析するコンピュータービジョンのヒューリスティックを使用していた
- 四角形、円、三角形のような特定の図形をルールとしきい値で検出していた
- 座標はデカルト座標系の点として分析された
- 基本図形の認識には機能したが、新しい図形を追加したり、より複雑な図形を扱ったりするのは難しかった
- 初期実装は単一ストロークで描ける図形に限定されていた
- 提案された図形リストには、雲、星、ハートのようにヒューリスティック方式では処理しにくい図形が含まれていた
- MLモデルはユーザーの手描きデータセットから多様なスタイルや変形を学習できるため、単純な幾何図形を超えて、より複雑な図形へShape Assistを拡張できた
手描きデータと座標ベースの表現
- Canvaは、単一ストロークの図形を描く簡単なUIでユーザーの手描きデータを収集した
- 各ストロークはx・y座標シーケンスとして記録された
- この方式は、図形を二値画像として保存するよりも前処理とデータ拡張に柔軟性がある
- 画像ベースなら、反転、回転、せん断のような空間的拡張を適用できる
- 座標ベースなら、座標のランダム削除、点位置のランダムな揺らぎ、点順序の反転のような拡張も可能
- ボランティアのデータだけでもかなりのデータセットを集めたが、エンジニアとデザイナーの絵は平均的なCanvaユーザーをうまく代表していなかった
- MLエンジニアは敵対的なデータを提供する傾向があった
- デザイナーの絵は上手すぎたため、一部には利き手ではない手で描くよう指示した
- より厳格なガイドラインと期待値を提供したあと、十分なデータセットを確保した
モデル設計と学習方法
- モデルはクライアントで実行される必要があり、ページ読み込み時間に悪影響を与えてはならなかったため、サイズを最小化する必要があった
- Canvaは点をピクセルに変換する必要があるCNNではなく、ストロークのx・y座標を直接使うRNNを実験した
- 最適なモデル特性を見つけるためにハイパーパラメーター探索を行った
- 入力サイズ、レイヤー数、hidden stateの特徴量数などのパラメーターを調整した
- ユーザーごとに描く速度が異なるため、同じ図形でも点リストの長さが変わる
- ゆっくり描くユーザーはより多くの点を残す
- 速く描くユーザーはより少ない点を残す
- 点の数を固定するために均等分布の区間別線形補間を使うこともできたが、重要な点が削除されて細部情報の損失が生じた
- 代わりにCanvaはRamer-Douglas-Peuckerアルゴリズムの変種を開発した
- RDPは曲線の重要な細部を保ちながら点数を減らす曲線単純化アルゴリズム
- 単純化された曲線から意味のある形で外れていない点を再帰的に削除する
誤った自動置換を減らす分類方式
- Shape Assistは、手描きが事前定義クラスのいずれかに十分似ていなければ自動置換してはならない
- 正解になり得る図形は1つだけなので、softmax活性化とcross-entropy損失が自然な選択だった
- 最高確率クラスの信頼度がしきい値より低ければ予測を拒否する方式
- しかしこのアプローチでは、モデルが間違っているときでも高い信頼度を示す問題があった
- 最終的には、各出力クラスにsigmoid活性化を使うマルチクラス・マルチラベル分類器として学習した
- どのクラスもしきい値を超えなければ予測を拒否する
クライアント推論の構成
- MLモデルは通常、大きく計算量も多いため、クラウド上の強力なコンピューターで実行されることが多い
- Shape Assistモデルは小さく数学演算も少ないため、すべての処理をクライアントアプリケーション内で実行できた
- この方式はサーバー接続の必要性をなくし、サーバー往復時間を排除して、ほぼ即座に図形を認識できるようにする
モデルアーキテクチャとサイズ
- 最終モデルは単一LSTMレイヤーの後ろにGemmレイヤーを付けた構造
- GemmはDenseまたはFully Connectedレイヤーとも呼ばれる
- 主な設定値は次のとおり
- 補間された点数:
P = 25 - hidden size:
H = 100 - 事前定義図形数:
N = 9
- 補間された点数:
- パラメーター数は次のように計算される
- LSTM:
4H * 2 + 4H * H + 8H = 41,600 - Gemm:
P * H * N + N = 22,509 - 合計:
64,109
- LSTM:
- IEEE754 32ビット浮動小数点基準でパラメーターあたり4バイトを使うと、モデルサイズは約250KB
- 非圧縮の360p 16:9画像1枚と同程度のサイズ
- より低い精度でパラメーターを保存すれば、さらに削減できる可能性がある
- Canvaは汎用MLエンジンではなく、LSTMとGemm演算をTypeScriptで直接実装した
- より複雑なモデルにはうまく一般化されないアプローチ
- 実装は300行未満
- 最新のノートPCで10ms未満で実行される
図形の置換と整列
- モデルが手描き図形を判別したあと、Canvaはテンプレートマッチング方式で手描きパスをベクターグラフィック表現に合わせる
- 整列プロセスは入力図形とテンプレート図形を正規化したあとに行われる
- テンプレート図形を15°単位で回転して試す
- 回転された座標空間で入力点の1次・2次モーメントを計算する
- 入力点とテンプレート図形の間の非類似度を計算する
- 非類似度が最も小さい回転を最適角度として選ぶ
- ユーザーが図形を描いたあとカーソルを同じ位置に最低1秒間保持すると、事前定義図形と十分に一致する場合にShape Assistが図形を置換する
1件のコメント
Hacker Newsのコメント
この問題には再帰型ニューラルネットワーク（RNN）はやりすぎな気がするし、シンプルでエレガントな $1 unistroke recognizer のほうが適しているように見える
ジェスチャーごとにサンプルを1つだけ学習させてもかなりうまく動くし、どんなプロジェクトでも半日あれば組み込んで、ジェスチャー認識でUIをもっと親しみやすくできる
各文字が1ストロークならPalmの Graffiti テキスト入力にもかなり安定して動作し、元論文も読みやすく理解しやすく書かれている
https://depts.washington.edu/acelab/proj/dollar/index.html
たとえば円を描くときは反時計回りで描く必要があり、より自然に感じる時計回りで描くとキャレットとして認識されてしまう
ユーザーが実装の詳細を知らない自由描画の文脈では、実際には使いにくい
リンク先の論文[0]ではエラー率を扱っており、例をいくつか追加するだけでもかなり速く改善する
[0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , 8ページ
自分が描いた四角形はキャレットに、ジグザグは中括弧として認識された
矢印のような 2ストロークで描く図形 もサポートしていない
サンプル図形の「delete」と「x」を比べると、性能がどれだけ悪いか確認しやすい
毎回同じやり方で図形を描くと期待するジェスチャーインターフェースの出発点としては悪くないが、ここで扱っている ダイアグラム作成 の用途にはあまり合っていない
大学のプロジェクトとして ES6実装 を作ったので、興味があればここにある: https://github.com/gurgunday/onedollar-unistroke-es6
「マウスやトラックパッドで引いた単純な直線ですら、酔ったリスの通り道のように見えることがある」という説明はわかるが、Canvaで誰がマウスで図形を直接描く必要があるのかはわからない
以前Miroには、マウスで星をざっくり描くと幾何学的に正確な星、円、三角形などに変換してくれる機能があり、すごいと思ったが実際には一度も必要にならなかった
ダイアグラムを作るときはあらかじめ用意された図形を使うほうが速いし、アイコンを作るときはブール演算、ポイント移動、Penツール中心の別ワークフローを使い、たいていIllustratorのような専用プログラムを使う
実際にイラストを描くときはタブレットを出して使うので、技術自体はすごいとしても ユースケース が何なのか気になる
アセットライブラリが非常に大きく、写真やベクターグラフィックを含む数百万、ひょっとすると数千万の画像がある
限定的に使った経験では、欲しい単純な図形が何かを正確にわかっているのに、延々とライブラリを検索しなければならないのが特に面倒だったし、このツールはおそらくその苦痛を減らそうとしているのだと思う
数年前にCanvaで働いていたことがある
内部事情はまったく知らないが、Canvaは競争力のあるダイアグラムツールにもなりたがっているので、このユースケースは重要なのかもしれない。ただ、現在のユーザーの99%のデザイン体験を根本的に変えることはできない、という制約がありそうだ
図形がメニューなしですぐ使えるとしても、カーソル1つで全体を描くほうが、複数のアイコンを配置・リサイズしてから矢印機能に切り替えて矢印を追加するより速い場合がある
Canvaが線描画に使っているライブラリも興味深いかもしれない: https://github.com/steveruizok/perfect-freehand
「Ramer-Douglas-Peucker（RDP）アルゴリズムの変種を開発した」という部分を見て、昔のサイドプロジェクトを思い出した
2018年の Strange Loop 発表でDouglas-PeuckerをPicassoに適用した
Picasso's Bulls: Deconstructing his design process with Python
https://rrherr.github.io/picasso/
20年以上も前の Macromedia Flash が、どうやって似たようなことを実現していたのか気になる
当時のCPU性能は今よりはるかに制約されていたのに、自由曲線を描くときに曲線を滑らかに整えてくれるのを見て、鮮明に驚いた記憶がある
それでも、ブラウザで軽快かつ高速に動くようにするのは依然として成果だ。結局、重要なのはいつでもユーザー体験だ
https://en.wikipedia.org/wiki/MessagePad#User_interface
ほぼ直線を描いたときに制御点が100個できたなら、ソフトウェアがそれを4個程度の点に減らすようなものだ
描画が終わったら、同じ点群を入力として スプライン曲線アルゴリズム で線を描き直していたのではないか
スプラインを描く計算自体が格段に難しいわけではないが、末尾に点を1つ追加すると、すでに描いた線の一部が変わるという点が重要だ
するとその線の後ろにあるものをすべて再描画しなければならないので計算コストが高く、60fpsで確実に処理できると保証するのは難しい
良い記事だし、作業もとても興味深い
少数派の好みかもしれないが、不思議なことに、滑らかなベクターグラフィックよりも手描きの 揺れる落書き感 のほうが好きに感じる
もちろん文脈によって好みは変わるだろうし、機能そのものは素晴らしい。人工的な完璧さがあふれる世界では、本物の手描きの成果物に本質的に惹かれる面がある
こういう機能を実装するなら、ぜひ 選択可能 にして、オンのときははっきり分かるようにしてほしい
ツールが賢すぎるふりをして、しかも完璧に当てられないと本当に腹が立つ。自分でもそういう失敗をしたことがある
最近の機械学習/AIブームより何年も前に、子どもたちに人気だった Scribblenauts というゲームがあり、かなり粗い落書きを驚くほど多様な物体に変えてくれた
どうやっていたのかは分からないが、自分も感心したし、子どもたちは魔法のように感じていた
https://store.steampowered.com/app/218680/Scribblenauts_Unli...
これが オープンソース だったらいいのにと思う
最近は小型のモデルがいくつも出てきている。このモデルは250KBで、大きなモデルを微調整するような単純な作業では50KB程度のモデルもあった
実用的なアプリケーションで再び小さなモデルを本当に使えるようになる時期が来るのを楽しみにしている
五芒星 とキラキラした星形は同じものではない。これは過少適合の例だろうか？