論文 "The Fast Bilateral Solver" ⓷ - 数学がわからない

論文"The fast bilateral solver. "[0]を読む。3回目。

gyokan.hatenablog.com

前回までで、バイラテラルソルバーが解こうとしている最適化問題（式（１））と、式（１）を構成する平滑化項（式（２））について読み進めた。

\begin{align}
\underset {x}{minimize} \ \displaystyle \frac{\lambda}{2} \displaystyle \sum_{i,j} \hat{W}_{i,j}(x_i-x_j)^2 + \displaystyle \sum_{i} c_i (x_i - t_i)^2
\tag{１}
\end{align}
$\begin{align} W_{i,j}=exp\left( - \displaystyle \frac{\|[p^x_i,p^y_i] - [p^x_j,p^y_j]\|^2}{2\sigma^2_{xy}} - \displaystyle \frac{(p^l_i-p^l_j)^2}{2\sigma^2_l} - \displaystyle \frac{\|[p^u_i,p^v_i] - [p^u_j,p^v_j]\|^2}{2\sigma^2_{uv}} \right) \tag{２} \end{align}$

目的

現時点での疑問点は次の二つ。

親和性行列 $\hat{W}_{i,j}$ の作り方

式（２）は、バイラテラルソルバーが用いる親和性行列ではなく、バイラテラルフィルタが用いるバイラテラル親和性行列についての式である。次は、バイラテラル親和性行列から親和性行列を作る方法「二重確率化」について理解できれば、親和性行列を作ることができるはず。

信頼度 $c_i$ の作り方

①から不明。

今回、論文を読み進めて、「二重確率化（bistochastized）」について理解する。それにより親和性行列 $\hat{W}_{i,j}$ が作れるようになるはず。

論文[0]の続き（引用・和訳）

“splat/blur/slice”

バイラテラル親和性行列 $W$ は一般にバイラテラルフィルタで用いられている。バイラテラルフィルタは、エッジ保存フィルタであり、領域内を、エッジを越えないようにぼかすことを、画像内容にフィルタを局所的に適用することによって行う。
バイラテラルフィルタには高速化手法[1,5]がある。これは、フィルタを“splat/blur/slice” 手続きで扱うものである。

splat：ピクセルをグリッド[2,5]または格子(lattice)[1]内の小さな頂点の集合に変換する。

blur：頂点の値をぼかす。

slice：ぼかし処理を行った頂点の値を補間することでフィルタ済みピクセル値を取得する。

このような“splat/blur/slice”フィルタリングアプローチはすべて、行列Wのコンパクトで効率的な因数分解：
$\begin{align} W=S^T\bar{B}S \tag{3} \end{align}$
に対応している。

さて、知りたいことは行列Wの二重確率化であったが、論文は行列Wを使用するバイラテラルフィルタの高速化手法に話題が移っている。

文献[1,2,5]が引用されているように、ここに書かれていることだけでこの高速化手法について理解することはできなさそう。

とりあえず、行列Wは式（３）のように、3つの行列 $S^T, \bar{B}, S$ に分解される、ということだけ理解する。またこれらはそれぞれ、“splat/blur/slice” 手順に対応しているはず。

しかし具体的にどうやって行列Wを分解すればいいのかは分からない。

新たな疑問：行列因数分解（式（３））において、どうやって $S^T, \bar{B}, S$ を計算するのか。

$\hat{W}$ の“splat/blur/slice”

さらに論文[0]を読み進める。

Barron ら[2] は、この考え（“splat/blur/slice”）に基づき、最適化問題を"splatted"し、バイラテラル空間で解いた。彼等は「単純化された」バイラテラルグリッドと次式にて与えられる二重確率行列（bistochastization matrices） $D_n, D_m$ を生成する手法を用いる。
$\begin{align} \hat{W}=S^TD^{-1}_mD_n\bar{B}D_nD^{-1}_mS\ \ \ \ \ SS^T=D_m \tag{4} \end{align}$

バイラテラルフィルタのバイラテラル親和性行列 $W$ は式（３）のように行列因数分解できたが、バイラテラルソルバーの親和性行列 $\hat{W}$ は式（４）のように行列因数分解できるということ。

具体的な方法はやはりこの論文を読むだけではわからなそうで、詳細を理解するには引用文献[2]を読む必要がありそう。

実際に使うだけであれば詳細に理解する必要はないが、式（４）において、 $\hat{W},S^T,D^{-1}_m,D_n,\bar{B},S$ のいずれも作り方が分からない（ $D_m$ だけは $S$ の作り方が分かれば作れそうだが）。

新たな疑問：行列因数分解（式（４））において、どうやって $\hat{W},S^T,D^{-1}_m,D_n,\bar{B},S$ を計算するのか。

まとめ

論文[0]を読み進め、式（３）、式（４）まで進んだ。

バイラテラルソルバーの最適化問題に含まれる平滑化項の重みである親和性行列は式（４）のように行列因数分解できる。親和性行列は式（３）で示されるバイラテラル親和性行列を二重確率化したものである。行列因数分解は“splat/blur/slice”手続きという、バイラテラルフィルタを高速化する方法に対応している。

現時点で理解できていないのは以下の二つ。

親和性行列 $\hat{W}_{i,j}$ の作り方

今回、バイラテラル親和性行列から親和性行列を作る方法「二重確率化」について論文に書かれていると期待していたが、そんなことはなかった。もしかして「二重確率化」という言葉だけで説明されなくても理解すべき一般的な用語なのだろうか？

“splat/blur/slice”手続き

バイラテラル親和性行列を“splat/blur/slice”に対応するように行列因数分解するのが式（３）。親和性行列を同様に行列因数分解するのが式（４）と理解したが、どちらも具体的な方法が分からない。文献[1,2,5]、特に式（４）の説明に引用されている文献[2]を読まなければならないのだろうか？

信頼度 $c_i$ の作り方

最初からずっと不明。

参考文献

[0] Jonathan T Barron and Ben Poole. 2016. The fast bilateral solver. ECCV (2016).
[1]. Adams, A., Baek, J., Davis, M.A.: Fast high-dimensional filtering using the permutohedral lattice. Eurographics (2010)
[2]. Barron, J.T., Adams, A., Shih, Y., Hern´andez, C.: Fast bilateral-space stereo for synthetic defocus. CVPR (2015)
[5]. Chan, T.F.: Rank revealing qr factorizations. Linear algebra and its applications (1987)