Colorizationを高速化してみた

　ここ最近ブログの更新が停滞気味ですが、怠けているわけではありません！８月になって艦コレの夏イベントが始まったので、少しづつ攻略中です。レアポケモンをGETするために重い腰をあげて、遠出をしなければなりません。いやー忙しいですね・・・・。
そんな中暇を見つけてはプログラムを書いてみたので、ブログを更新してみます。

前回のカラリゼーションの問題点

　２ヶ月前のこと、ふと思いついてカラリゼーションをC++で実装してみた、というのが以前のお話です。このブログで扱うカラリゼーションは以下の論文ですよ。
A. Levin D. Lischinski and Y. Weiss著：Colorization using Optimization
　実装したはいいものの、そこには大きな問題がありました。
　計算時間がめちゃくちゃかかるのです！
　例えば、の画像の色を塗るのに20分を要し、の画像になると計算が終わるのを待つことができませんでした。まぁ・・・僕の実装方法が悪いのですが、こんなプログラムは使いものになりません。
　そこで、以下の論文の方法で実装してみることにしました。
Jonathan T.Barron著：The Fast Bilaterarl Solver
　このブログで散々とり扱ってきたバイラテラルソルバです。今回の記事は、半年間も取り組んできたバイラテラルソルバ解読の成果になります！！！！

高速化の肝

　バイラテラルソルバを使うと計算時間が早くなる理由、それは共役勾配法を適用できることにあると思われます。Levinらのカラリゼーションの中身を見ると、大規模な連立１次方程式を解いているだけです。以下の式になります。

　

　Levinらのアルゴリズムでは、行列は非対称な行列になります。そのような連立方程式を解く良い方法を僕は知らないので、試しにガウスの消去法を採用したのが前回の失敗でした。
　一方で、Barronらは行列を対称で正定値となるように、アルゴリズムを変更しています。正定値対称行列であれば、共役勾配法で解を求めることができるので、比較的に計算時間が高速になると考えられます。
　以上のように、共役勾配法というのがポイントであって、別にバイラテラルソルバである必要はないと思いますよ。

実装しました

　ソースコードは以下のリポジトリからとってください。
github.com
あくまでα版なので、可読性は低いと思います。完成版はそのうち作成予定です・・・。
　

　実行結果を紹介します。使用しているパソコンはMacbook air、Intel Core i5 1.7GHz、メモリ4G byteです。

①まずは花の画像。で処理時間は２秒ほど。上が入力、下が出力です。一応Googleで「非営利目的の改変後の再使用許可」で検索してみました。

②「のんのんびより　りぴーと」の壁紙です。こちらは再使用の許可がありませんw　で処理時間は７秒ほど。


入力が雑なので、出力の色が不自然です。こまちゃんやれんちょんがオッドアイになっていますが、アルゴリズム上仕方がありません。こんなもんでしょう。

　それにしても久々に見るとみんな可愛いなぁ。特にこまちゃん(*´ ∇｀*)　ちなみに今期アニメは見るものがないので、今更ながらシリアルエクスペリメンツ　レインとか見ています。なんか殺伐としているし、話がよくわからないし、心が落ち着きません・・・。

最後に

　無事、カラリゼーションの高速化を図ることができました！これ以上はやる気が起きないのでやりません。そしてバイラテラルソルバも一応解読できました。こちらもやる気が起きません。ブログで記事として始めた以上、区切りをつけようという意思だけでここまできました。ようやく解放された気分です。しゅーりょう、終了♫