Bilateral Solverをソルブする（第４回）

　連載中のバイラテラルソルバの解読をそろそろ終わらせたい！　やる気があまり起きないから長らく停滞中なんですけどね・・・。しかし理論はだいたいわかっているので、現状のまとめを今回書いてみます。実装はいつか挑戦してみます。
→バイラテラルソルバの実装完了しました！（Colorizationを高速化してみた - らんらん技術日記）。特に需要もなさそうですし、これにてバイラテラルソルバの最終回の予定です。

Bilateral Solverとは何か

　第 ${0}$ 回ではいい加減な説明をしていますが、だいぶ真実がわかりました。
　バイラテルソルバは画像処理向けのソルバです。入力画像と参照画像の情報を元に、出力画像を作成します。
　元々はステレオマッチング向けのアルゴリズムだったみたいですが、他の画像処理でも使えるように改良されました。という訳で、ステレオマッチングを例に、モデルを紹介します。

f:id:yukirunrun:20160611171926p:plain:w160

f:id:yukirunrun:20160611171940p:plain:w160

f:id:yukirunrun:20160611172841j:plain:w160

　左の雑な深度画像が入力になります。中の参照画像からエッジ等の情報を抽出します。そして右の高精度な深度画像を生成する、というのがアイディアです。あくまでアイディアの話なので、↑は実際の結果ではありません。数式に落とすと以下のモデルになります。

${\mathop{minimize}_{X}}\frac{\lambda}{2}\sum_{i}\sum_{j}\hat{W}_{i,j}(x_i-x_j)^2+\sum_{i}c_i(x_i-t_i)^2$

ここで、 ${t}$ は入力画像のピクセル、 ${W}$ は参照画像から作成した係数、 ${x}$ は出力画像のピクセルです。 ${c}$ は信頼度という係数で、入力画像の信憑性を人手または計算によって設定します。考えとしてはGuided Filterに似ているかも。あちらはローカル処理ですが。

なぜバイラテラル？

　上記のパラメータ ${W}$ はバイラテラルグリッドの係数になります。バイラテラルグリッドはバイラテラルフィルタの亜種です。とはいえ、なんでバイラテラルグリッドを選ぶのでしょうか。モデル式を見る限りは、エッジを保持しつつ平滑化する特性のフィルタであれば、なんでもよさそうです。
　その答えはモデル式を単純にできるからです。モデル式は２次元の複雑な方程式になっていますが、バイラテラルグリッド上では連立一次方程式に置き換えることができます。

${ {\bf A}{\bf y}={\bf b}}$
${ {\bf A}}$ と ${ {\bf b}}$ は新しく計算する係数、 ${ {\bf y}}$ が解になります。このように、バイラテラルグリッド上で最適化問題を解くと計算が楽になります。これがバイラテラルソルバです！

計算方法

　以下の手順で計算します。
　①バイラテラルグリッドの構成行列を作る。
　②構成行列の一つを二重確率化する
　（オプションで信頼度行列を作成する）
　③連立一次方程式の係数行列を①と②から作成する。
　④連立一次方程式を共役勾配法で解く。
　⑤連立一次方程式の解を、元空間に射影する。

バイラテラルグリッドの構成行列を作る

　バイラテラルグリッドは、splat処理、blur処理、slice処理に分けることができます。またそれぞれの処理を、行列の形で表すことができます。

${\bf W = S^T\overline{B}S}$
　 ${ {\bf W}}$ はバイラテルグリッドの係数行列、 ${ {\bf S^T}}$ はslice行列、 ${ {\bf \overline{B}}}$ はblur行列、 ${ {\bf S^T}}$ はsplat行列になります。計算で ${ {\bf S^T}}$ 、 ${ {\bf \overline{B}}}$ 、 ${ {\bf S}}$ を求めましょう。 ${ {\bf W}}$ は不要です。

構成行列の一つを二重確率化する

　blur行列を二重確率化することを考えます。厳密には二重確率化と似たようなことをします。理由等はともかく・・・必要なのは行列 ${ {\bf D_n}}$ を計算することだけです。 ${ {\bf D }}$ は対角行列（diagonal matrix）を意味します。適切な対角行列を作用させることで、二重確率化できることが知られています（Sinkhorn-Knoppの定理）。

${{\bf m} = { \bf S 1}}$
${{\bf n_0} = { \bf 1}}$
${ {\bf n_i} = \sqrt{ \frac{{\bf n_{i-1} \bigotimes m}}{{\bf B n_{i-1} }}} }$
${ {\bf D_n} = diag({\bf n} )}$
${\bf n}$ は、繰り返し計算により ${\bf n_i}$ が収束した結果です。この過程により、以降の計算式が単純になります。

連立一次方程式の係数行列を作成する

　以下の計算式に従って作成します。

${ {\bf D_m} = {\bf S S^T} = diag({\bf m}) }$
${ {\bf A} = \lambda( {\bf D_m - D_n \overline{B} D_n} + diag({\bf S c}))}$
${ {\bf b} = {\bf S(c \bigotimes t)}}$
　 ${{\bf c}}$ はアプリケーションに応じて計算方法が違うみたいです。 ${{\lambda}}$ もです。論文を参照くださいな。