Colorizationを実装してみた - らんらん技術日記

前回、応用情報試験に落ちて以来の更新ですね。あれからというもの画像処理への情熱は消え失せ、家に帰ってからは黒猫のウィズをやってダラダラする毎日です。戦闘中の精霊ボイスだけが毎日の癒しです。。とまぁ半分は嘘なのですが、半分ほどは本当です笑
傷も癒えてきたということで、久しぶりに更新してみます！

Colorization（カラリゼーション）

これまでバイラテラルソルバの解読を進めてきたところ、僕はあることに気づきました。
「実現したいアプリケーションがない・・・orz」
そうです。理論がわかったところで、応用先が見つからなければ役に立たないのです。
というわけで、応用先として目星をつけたのがカラリゼーション（Colorization）です。Deep Learningを用いた高度な技術もあるみたいですが、僕が実装するのは↓になります。

A. Levin D. Lischinski and Y. Weiss著：Colorization using Optimization

簡単に説明すると、白黒写真に色をつける技術です。人手で少しだけ色を塗ると、残りの領域はコンピュータが自動的に色を塗ります。詳細はリンク先をみてください。デモがとてもよくできています。
この技術ですが、論文の著者がMatlabのコードを公開しています。しかし僕にはMatlabのライセンスがありません。なぜなら大学のような研究機関に属さず、企業で製品開発をしている訳でもなく、ひっそりと勉強しているだけだからです苦笑　
ならばMatlabコードを解読して、C++で実装しようじゃないか！！！

理論

論文の解釈には以下のページを参考にしました。
http://homepage3.nifty.com/mogami/diary/d0510.html#16t2
ここの説明と同じことを述べます。アルゴリズムの発想ですが、画像に対して次の関係が成り立つことを仮定しています。
ある画素とその近傍画素に対して、
・輝度の大きさが近いとき、２つの画素の色は似ている。
・輝度変化が大きいとき、２つの画素の色は似ていない。

この仮定に基づいて、入力画像（YUV空間）に以下のモデルを適用して、出力画像を作成します。
$\min \{ \sum_{r}(U(r) - \sum_s w_{rs}U(s))^2 \}$
ここで、 $U(r)$ はU空間における画素rの値、sは画素rの周辺画素です。sの範囲はrの第一近傍と第二近傍になります。

$w_{rs}$ は画素間の輝度値の関係を記述するパラメータで、以下の特性をもちます。
・画素rと画素sの輝度値が近い時、 $w_{rs}$ は大きい
・画素rと画素sの輝度値が遠い時、 $w_{rs}$ は小さい
・ $\sum_{s}w_{rs}=1$
つまりこのモデル式は、
ある画素の色の決定には、隣接する輝度値の近い画素を参考にしよう
ということを言っているだけです。

C++実装に挑戦！

さて、C++実装に移るにあたり不可解な点があります。参考ブログにも書いてある通り、ソースコードと論文式に違いがあります。
実際に計算しているのは、以下の連立一次方程式です。
　 $\bf Ax=\bf b$
　 ${\bf A} = \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{12n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \dots & a_{n,n} \end{array} \right) 　= \left( \begin{array}{c} \bf r_{1}\\ \bf r_{2}\\ \vdots\\ \bf r_{n} \end{array} \right)$
${\bf b} = \{b_1, b_2,\dots,b_n \}$
ここで、 $n$ は入力画像の画素数です。行列 ${\bf A}$ は画素間の輝度値（Y空間）の関係を示し、ベクトル ${\bf b}$ はユーザが指定した色相（U空間とV空間）を示します。
行列 ${\bf A}$ を構成する行ベクトル ${\bf r}_{i}(i=1,2, \dots ,n)$ 、およびベクトル ${\bf b}$ は以下のルールで求めます。
① $U(i) \neq 0$ の時（厳密にはU(i)があるしきい値より大きい時）
　 ${\bf r}_{i}= (a_{i,1}, a_{i,2}, \dots, a_{i,i-1}, a_{i,i}, a_{i,i+1}, \dots, a_{i,n})= (0, 0, \dots, 0, 1, 0, \dots, 0)$
　 $b_i = U(i)$
② $U(i) = 0$ の時
　 ${\bf r}_{i}= (a_{i,1}, a_{i,2}, \dots, a_{i,i-1}, a_{i,i}, a_{i,i+1}, \dots, a_{i,n})$
　 $\quad =(-w_{i,1}, -w_{i,2}, \dots, -w_{i,i-1}, 1, -w_{i,i+1}, \dots, -w_{i,n})$
　 $b_i = 0.0$
要は、①ユーザが色指定した画素は固定する、②ユーザが色指定していない画素は近傍画素を参考にする、ことを意味しています。
②についてですが、必要な $w$ は $8$ 個だけです。画素iの近傍でない画素に対しては $w$ は全て $0$ になります。また、ベクトル ${\bf b}$ はU成分の他にも、V成分で計算する必要があります。 $w$ の計算は論文の(2)式をみてください。
それでは具体例に入ります。

〇入力画像の準備

相変わらずになりますが、入力画像はのんのんびよりから引用します。今回はこまちゃんとほたるんです。
オリジナルイメージ（左）から、一部を残してグレーにします（右）。これが入力です。本当はグレー画像に自分で色を塗る、というのがベストですが、実装するのが面倒でした。

小さい画像を使っているのは理由があります。それは後ほど・・・。

〇行列およびベクトルの作成

行列 ${\bf A}$ およびベクトル ${\bf b}$ を作成しましょう。以下のような行列 ${\bf A}$ ができあがると、理解は正しいと思います。

非ゼロの要素を黒色に着色していますが、見づらいですね・・・。色を指定した画素に対応した行に非ゼロ要素は１つ、指定していない画素に対応した行に非ゼロ要素は８つあればOKです。（境界部を除く）

〇連立１次方程式を解く

面倒なので、僕はopenCVのsolve関数を使いました。しかもガウスの消去法を選択です！！！
では実行です。

カタカタ。。。「./execute input.png」
パソコン「ウィーーーーーーン」
僕「さて、トイレでもいくか」

〜　戻る　〜
僕「結果はどうなってるかなぁ」
パソコン「ウィーーーーーーン」
僕「・・・」
僕「風呂でも入るか」

・・・・大規模疎行列をガウスの消去法で解くのは適切ではありません。なんとなく知っていましたが、こんなに時間かかるのか。計算時間はMacbook airのCore i5で128*128の画像に対して約20分程かかりました。まともなサイズの画像を使うといつ終わるのかわかりません（；ﾟДﾟ）ﾌﾞﾙﾌﾞﾙ

結果

なにはともあれ結果です。

左がオリジナル、中が入力、右が出力です。
・・・このアルゴリズムすごくないですか！？オリジナルと出力がかなり似ています。テキトーに実装したにも関わらずこの完成度、びっくりです！
　ただし現状では連立一次方程式の解き方に問題があります。もう少し改良できたら、いよいよGithubデビューでしょうか？　それでは今回はこれで。

2016/8/21 追記：
高速化できたので、ソースコードを上げておきます
https://github.com/timuda/colorization_s_demo