数学がわからない

日々の勉強をアウトプットする。

論文 "The Fast Bilateral Solver" ④

論文"The fast bilateral solver. "[0]を読む。4回目。遅々として進まない。

gyokan.hatenablog.com

前回まで

論文[0]について、式(1)から式(4)までをある程度理解した。

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

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

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

二重確率化によってバイラテラル親和性行列から親和性行列を作ることができるらしいが、「二重確率化」がわからない。論文[0]では説明されていない一般的な用語なのだろうか?

  • “splat/blur/slice”手続き

バイラテラルフィルタを高速化するために、バイラテラル親和性行列を“splat/blur/slice”に対応するように行列因数分解するのが式(3)。親和性行列を同様に行列因数分解するのが式(4)と理解した。どちらも詳細には分からない。文献[1,2,5]、特に式(4)の説明に引用されている文献[2]を読まなければならないのだろうか?

  • 信頼度c_iの作り方

最初からずっと不明。


さて、論文[0]を読み進めれば上記の疑問が解決するのだろうか?

バイラテラルソルバー[0] 「2 Problem Formulation」後半

論文[0]の続きを読む。

バイラテラル空間からピクセル空間に戻すための式(5)

Barronら[2]はまた、変数置換(variable substitution)を行っている。変数置換は、低次元のバイラテラル空間頂点に関して、高次元のピクセル空間最適化問題を再定式化する処理である。

 \begin{align}
\textbf{x}=S^T \textbf{y}
\tag{5}
\end{align}

ここで、\texbf{y}はバイラテラル空間の頂点を表す小さなベクトルで、\texbf{x}ピクセルの値を表す大きなベクトルである。

バイラテラル空間からピクセル空間に戻す処理"slice"を表す式と思われる。

ピクセル空間の損失関数(式1)からバイラテラル空間の損失関数(式6)へ

これらのツールを用いると、ピクセル空間の損失関数である式(1)をバイラテラル空間へ再定式化できるだけでなく、バイラテラル空間での損失関数を二次形式(quadratic form)で書き換えることができる。

 \begin{align}
\underset {y}{minimize} \  \displaystyle \frac{1}{2} \textbf{y}^TA\textbf{y} - \textbf{b}^T\textbf{y} +c
\tag{6}
\end{align}

 
\begin{gather}
A=\lambda(D_m-D_n\bar{B}D_n)+diag(S\textbf{c})\ \ \ \ 
\textbf{b}=S(\textbf{c}\circ\textbf{t})\ \ \ \ 
c=\displaystyle\frac{1}{2}(\textbf{c}\circ\textbf{t})^T\textbf{t}
\end{gather}

ここで\circアダマール積(要素ごとの掛け算)である。

この再定式化の導出は補足に記されている。式(1)の最適化問題を単純に解くのは計算量が多く現実的ではないが、このバイラテラル空間で定式化された最適化問題は高速に実行することができる。

ピクセル空間における式(1)を直接解くのは計算量が多すぎるので、"splat"を使ってバイラテラル空間に変換した式(6)を解こうという話。式(6)はtextbf{y}の最小化問題であるが、textbf{y}は式(5)を用いてtextbf{x}に戻すことができるので、目的である精密なセグメンテーション済み画像textbf{x}の取得は達成できる。

ピクセル空間の損失関数(式1)を解くために実際に計算する(式8)

この2次形式を最小化することは、スパース線形システムを解くことと同じである。

 \begin{align}
A\textbf{y}=\textbf{b}
\tag{7}
\end{align}

単純にその線形システムへの解をスライスすることによってピクセル空間解\hat{x}を生成することができる。

 \begin{align}
\hat{\textbf{x}}=S^T(A^{-1}\textbf{b})
\tag{8}
\end{align}

「最小化問題を解く」とは、具体的には式(7)を解いて\textbf{y}を取得することである。これは、二次形式で表されている式(6)を\textbf{y}について微分したものをゼロとすることで、極小値を求めようとしている(と考えればよいはず)。

さらに、式(5)と組み合わせれば\textbf{x}を求める式(8)になる(論文で\textbf{x}ではなく\hat{\textbf{x}}となっている意味は不明。近似だから?)。

長々と読み解いてきたが、結局のところ目的である精密なセグメンテーション済み画像\textbf{x}の取得は式(8)の計算により達成できる。

式(8)を計算するためにはS^TA^{-1}Aを構成する\lambda, D_m, D_n, \bar{B}, S、信頼度画像\textbf{c})、\textbf{b}が必要になる。しかし、これらはいまのところ疑問点として後回しにしてきた事柄である。

バイラテラルソルバーアルゴリズムの概略まとめ

さて、論文[0]の2章「Problem Formulation」の残りにもう式はない。

式(8)で「バイラテラルソルバー」アルゴリズムが記述できる。

ソルバーへの入力は、参照画像、改善したいノイズを含むターゲット画像、および信頼性画像である。

純化バイラテラルグリッドは参考画像から構築される。単純化バイラテラルグリッドは、[2](詳細は補足を参照)のように二重確率化される。二重確率化された単純バイラテラルグリッドを用いて行列Aとベクトル\textbf{b}を式(6)で示すように構築する。行列Aとベクトル\textbf{b}を用いて式(8)の線形システムを解き、出力画像を生成する。

ここまで何をやってきたかをまとめている。

複数のターゲット画像がある場合

(同じ参照画像と信頼度画像を持つ)複数のターゲット画像がある場合は、ベクトル\textbf{b}が多くの列を持つ、より大きな線形システムを構築し、同じ行列Aを用いて各チャンネルを同時に解くことができる。このターゲットが多い場合、ベクトル\textbf{b}が低ランクであればそのプロパティを利用して最適化を加速できる(補足に記載)。

複数のターゲット画像がある場合について。良く分からない。セグメンテーションが2値化ではなく多値化を目的とした場合のことを言っている? としたら、多値化セグメンテーションを行う場合はもう少しちゃんと理解する必要がある。とはいえ、これだけでは説明不足、補足を読まなければならないか。

バイラテラルソルバーアルゴリズムの利点

我々のピクセル空間損失(式1)は、重み付き最小二乗フィルタリング[8,9,31]と似ているが、大きな違いはバイラテラル空間最適化を用いて、効率的な最適化を行うことが可能になっているところである、バイラテラル親和性の大きな空間サポートを使用する場合でも。これにより、出力品質とアルゴリズムの速度を改善できる。

我々のアルゴリズムは[2]のステレオ技術の根底にある最適化問題に類似しているが、単純な最小二乗問題に帰着することから、次のような利点がある。

  • 標準的な方法を使って最適化を行うことが可能(我々は[36]のpreconditioned conjugate gradient(共役勾配法アルゴリズムを用いる。詳細については補足を参照)
  • ソルバーを効率的に逆伝播でき(3章)、ディープラーニングパイプラインに統合することが可能
  • 最適化中の収束速度を改善、正確さを保証、前処理と初期化のための高度な技術を使用することが可能(4章)
  • ソルバーのロバストで多変量一般化が可能(補足を参照)。

最後はバイラテラルソルバーの利点について。色々な利点があるとのことだが、詳細には関連する章や補足を読む必要がある。

まとめ

論文[0]について、2章 Problem Formulation を読み終えた。ここまで理解したことをまとめる。

バイラテラルソルバーは、最適化問題(式(1))を解くことで低品質のセグメンテーション結果\textbf{t}から高品質のセグメンテーション結果\textbf{x}を生成する。

しかし、式(1)をそのまま解くのは計算量が多すぎるので、“splat/blur/slice”手続きというバイラテラルフィルタ高速化手法を用い、問題をピクセル空間からバイラテラル空間へと変換した式(6)を解くことにする。

式(6)を解くということは、微分してゼロとなる\textbf{y}を計算するということである(式(7))。さらに本来の目的の高品質のセグメンテーション結果\textbf{x}を得るために式(5)と合成して得られる式(8)を計算することが、最適化問題(式(1))を解くということに対応している。

今回、残った疑問は以下の3つ。

  • 式(8)を計算するために必要な行列、ベクトルの作り方。

具体的にはS^TA^{-1}Aを構成する\lambda, D_m, D_n, \bar{B}, S、信頼度画像\textbf{c})、\textbf{b}、何一つ分からない。

これらはバイラテラル親和性行列\hat{W}_{i,j}を行列因数分解して取得する(式(4))はずなので、“splat/blur/slice”が理解できれば良いのだろうか?だとすると、文献[1,2,5]、特に式(4)の説明に引用されている文献[2]を読めばよい?

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

なお、バイラテラル親和性行列\hat{W}_{i,j}は神話性行列W_{i,j}を二重確率化したものとのことだが、これも具体的なやり方は分からない。二重確率化というのは一般的な用語なのか?

  • 信頼度c_iの作り方

最初からずっと不明。

すべて前回から引き続いて分からないことだが、いくらか疑問が詳細になって来たといったところか。

また、キーワードが出てきたが詳細は他の章や補足に記載、とされたものもある。いつか調べたいのでメモしておく。

  • 複数のターゲット画像がある場合(多値化の場合?)→補足
  • preconditioned conjugate gradient(共役勾配法アルゴリズム →補足、文献[36]
  • ディープラーニングパイプラインに統合→(3章)
  • 前処理と初期化のための高度な技術を使用→(4章)
  • ソルバーのロバストで多変量一般化→ 補足

次からは、式(8)を計算するために必要な行列、ベクトルの作り方を調べるために文献[2]を読んでみようと思う。他に参考になりそうなのは、補足、文献[1,5]といったところか。

参考文献

[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)
[36]. Shewchuk, J.R.: An introduction to the conjugate gradient method without the agonizing pain. Tech. rep., Carnegie Mellon University (1994)