Structure-based ASCII Art

SIGGRAPH2010の論文、Structure-based ASCII Artを実装しました。

この手法は、画像の濃淡を利用したTone-basedにアスキーアートを生成する手法に対して、画像の形を利用してアスキーアートを生成するというものです。

手法の概要は以下のようでした。

1. 1. 最終的に使用する文字フォントデータの特徴ベクトルを事前計算により求める。（この時、Log-polarにサンプリングするのがこの手法の肝だとか）
   2. 入力画像をベクター画像に変換する
   3. ベクター画像をラスタライズし、出力のアスキーアート一文字一文字に対応するグリッドで分割、グリッド毎に上記手法と同様にして特徴ベクトルを算出、事前計算したフォント特徴ベクトルと比較してもっともマッチングするものを選び出し、画像全体をアスキーアートに変換する。
   4. 入力ベクター画像から適当に頂点を選び出し、ちょっとずらす。
   5. 3に戻る。

3,4,5のループにおいて、画像と文字のマッチングの具合と、画像を歪ませたことによる変化の二つの要素に基づいて計算された指標値を最小化する最適化問題に帰着します。元の論文では焼き鈍し法で最小化を試みていました。

つまり、入力そのままの画像からアスキーアートを生成するのでは不自然な場合に、入力画像を変化させることでアスキーアートとしてより自然なものにする、という手法でした。

今回私の実装も、基本的には論文のとおりに進めましたが、論文自体にいくつか不明瞭な点があったり、解釈がおかしいのか式がおかしいのかよくわからん部分があったり、入力データ用意するのが予想以上に面倒だったりと、結構大変でした。しかし、いくつかのインプットで試したところ、画像を大きくは歪ませることなく、ほどよくより良いアスキーアートが生成されたような気がするので、まあいいでしょう。

以下が結果です。
元画像。

結果。
左が単純に入力からアスキーアートを生成したもの。
右が何回か反復して改善された（？）結果。
髪の毛の右側や、襟などはちょっと良くなってる。
ただ、元論文だともっと良くなってるので、これはどちらかというアルゴリズムのせいではなく、フォントの特徴ベクトル生成があんまりうまくいかなったからじゃないかなーと想像している。
まあ半角固定幅アスキー文字のみ、という条件にしてはそこそこ？