Bilateral Gridの行列因子分解

（Bilateral Soverの解読連載４回目。元論文に配慮してタイトルからは外します。）

　最終更新から20日以上経過しました。というのもPS vitaを買ったことが原因です。私には前々からやりたかったゲームがありました。「トトリのアトリエ」です。

　トトリができるぞぉぉーーー！ってことで、中古ゲーム屋へ直行、しばらくは錬金術師・・・もとい廃人をやってました（・ω・）次はメルルもやりたいなと思いつつ本題に入ります。

　今回はBilateral Gridの行列因子分解(matrix factorization）についてです。Bilateral GridをSplat, Blur, Slice処理に対応する行列の積として表すことで、最適化問題に組み込みやすい形とします。

Simplified Bilateral Grid

　行列因子分解の前に、アルゴリズムの変更です。前回まではChenらが提案したオリジナルのBilateral Gridを扱ってきました。これから取り上げるのはBarronらが提案したSimplified Bilateral Gridです。以下の２点の違いがあります。

①Slice処理の単純化

　Slice処理の補完方法を最近傍補完にします。オリジナルのBilaterl GridはSplat処理で最近傍補完、Slice処理で線形補完を使うのですが、

「ええいめんどうだ！どっちとも同じ方法でいい！精度なんて知らん！」

というのがこの変更です（本当か？）。て訳で、精度を犠牲にして計算効率を手に入れます。

②不要なGridの削除

　Bilateral Gridは基本的に疎行列（sparse matrix）になります。下の図に示しますが、データが入っていないGridが非常に多いのです。計算が重くなるだけなので、無駄なものは消しちゃいましょう。代わりに個別の番号をふってあげましょう。

行列因子分解

　それでは、Simplified Bilateral Gridを行列の積に分解しましょう。以下の式で表されます。

ここで、WはBilateral Gridのアフィニティ行列（前回の記事参照）、はSlice行列、はBlur行列、はSplat行列です。Splat行列の転置がSlice行列になることがポイントです。

①Splat行列を求める

　Splat行列のイメージは、入力信号がどのGridに入るのかを示す対応表です。先ほど各Gridにふった番号を使用して、列に入力信号(0,1,......,n)、行にGrid番号(0,1,....,m)の成分をもった行列を作ります。

②Blur行列を求める

　Blurとして3x3のGussianフィルタを想定します。まずはオリジナルのBilateral Grid上において、Gussianフィルタのアフィニティ行列を求めます。ここからSipmplified Bilateral Grid上のグリッドに対応する成分だけを残してください。

       

左の３本線がBilateral Grid上のBlur行列。右がSimplified Bilateral Grid上のBlur行列です。左の行列は100x100に対して、右は30x30のサイズ。計算量がとても小さくなります。

③Slice行列を求める

　Splat行列を転置してください。

以上でSplat、Blur、Sliceの行列が求まったと思うので、Bilateral Gridのアフィニティ行列を計算できます。

Bilateral Gridのアフィニティ行列

　左の入力信号に対して、Simplified Bilateral Gridのアフィニティ行列Wを求めた結果です。

　　

参考までにBilateral Filterのアフィニティ行列です。

　なんとなく雰囲気は似ていますよね。Simplified Bilatertal Gridは計算をシンプルにしている分、カクカクになっているんだと推測されます。画素の連続性が失われているので、画像処理応用には問題がありそうです。最適化問題にはこれでも十分なんでしょうか・・・？これから読み進めていきます。

　以上、今回はこれで終了です！