potrace.js解説

ラスタ画像のアウトラインをトレースし，svg等のベクタ画像に変換するpotraceですが，javascript版の高速化を行った際にざらっと分かった処理の流れについてまとめてみます．なお，パス演算等のアルゴリズム的な所についてはよく判っていません．が，まあ動いているからいいんじゃない？

処理の概要

1. 画像をグレイスケール化する．
2. 閾値を元に画像を２値化（白黒化）する．
3. ２値化した画像を元にパスの素となる頂点リストの配列を生成する．
4. 頂点リスト毎に直線部と曲線部とを算出し，カーブリストに変換する．→カーブリストの配列となる．
5. カーブのリストの配列を元にsvgのd操作文字列を生成する．

まずは画像をグレイスケール化する訳ですが，これはcanvas要素を利用して行います．canvas要素は画像を描く機能の他に，画像を構成しているピクセルの色情報をバイト配列（状のオブジェクト）として取得する機能（getImageDataメソッド）をもっており，この色情報を直接操作することで，様々な画像処理を行うことが可能となります．

例えばグレイスケール化は色を明るさに変換する処理ですが，ピクセル毎のr(赤)g(緑)b(青)値が得られれば，次の公式で計算することが出来ます．

r'=r*0.298912+g*0.586611+b*0.114478
g'=r*0.298912+g*0.586611+b*0.114478
b'=r*0.298912+g*0.586611+b*0.114478

これらの値を元のピクセルに上書きすることでカンバス画像グレイスケール化が完了します．

次にグレイスケール化した画像を２値化して白と黒の画像に変換します．閾値を大きくすればするほど暗い色が黒に変換され，全体として黒っぽい画像となります．この処理は次のアウトラインを求める際の基礎情報となります．

２値化された画像に対し，黒ピクセルで囲まれた領域の外周をパスの候補として頂点リストを算出します．パスの候補が得られたら，パスの外の領域を黒く塗り潰し，全体の色を反転します．すると先ほどの領域の中身が黒ピクセルで囲まれているはずなので，この領域の外周もパスの候補として頂点リストを取得します．なお，色を反転する毎に頂点リストを算出する方向を時計回りと反時計回りと逆にしておきます． この操作をパスが得られなくなるまで繰り返し，頂点リストの配列を得ます．

上記で得られた頂点のリストを直線と曲線に変換します．このアルゴリズムはあまりよく判っていませんが，だいたいこんな処理を行なっているものだと考えられます．

この変換結果を元にsvgのd操作文字列を生成するのですが，先程の「画像の外周から内周に向かって処理が行われる」ことと，「途中でパスの方向が反転する」というところがミソで，全てを繋げて一つのpath要素とした場合にうまい具合に中抜きとできるし，複数のpathに分けた場合もパスの方向毎に塗り分けの色を変えてやれば，内周に相当するpath要素ほど上に重なるので，正しい図形が得られることになります．（この部分説明しにくいので，実際にpotraceHtmlで試してみて下さい．）

高速化について

オリジナルのpotrace.jsではこれ以上劇的にはパフォーマンスは上がらないとのことでしたが，javascript特有の対処を入れることでかなりの高速化を実現することが出来ました．

potraceでの処理は巨大な配列のループ処理ばかりです．従ってこのループ処理のコストを軽減できればかなりの高速化が見込めそうです．

最も気になったのがループ処理内部で次のようなコードが多数含まれていた点です．hogeの長さは非常に大きいと考えて下さい．

for(var i = 0, len = hoge.length; i<len; i++){
    hoge[i].a=1;
    hoge[i].b=2;
    hoge[i].c=3;
    hoge[i].d=4;
    hoge[i].e=5;
}

それほど問題がなさそうですが，javascriptでは配列ですらハッシュとして実現されていることを考えると，このhoge[i]という処理はそれほど高速ではなさそうです．また，他の言語ではコンパイル時に様々な最適化処理が為されるため，hoge[i]の呼び出しの部分をまとめてくれそうですが，javascriptでは律儀に５回繰り返してしまいます．従ってこの処理を次のように書き換えることで相応のパフォーマンス改善が見込めます．

for(var i = 0, len = hoge.length; i<len; i++){
    var hogei = hoge[i];
    hogei.a=1;
    hogei.b=2;
    hogei.c=3;
    hogei.d=4;
    hogei.e=5;
}

配列のインデックス参照を１度に抑え，ローカル変数の参照に変更しました．その他，javascriptでは変数の参照を行う際，スコープチェーンとプロトタイプチェーンという機構を利用しますが，これも多用されるとループ文の中でパフォーマンスの劣化を招きます．”遠い”部分で定義されていて良く使う関数や変数は，一旦ローカル変数に保管してから用いるとパフォーマンスが良くなります．その反面コードの簡潔さ・可読性が損なわれますので，多用は禁物です．今回のような汎用的なライブラリにおいては有効なテックニックと言えます．