Bilateral Solverをソルブする（第０回）
ブログ開設から一週間。プログラミングの勉強のために始めたこのブログですが、何もやらずに過ぎてしまいました。というのも・・・
「黒猫のウィズ楽しいなぁwwwこまちゃん可愛いなぁwww」
じゃなくて、
「何も書きたいプログラムがないorz」
このままでは、さっそくブログ存続の危機です。テーマぐらい決めねばなりません。とりあえず、Hello World! はコンソールに出せるけど・・・。それってブログ記事に書くことなのか？ その記事見てすごいって思う人いるのか？ いやいや、全然かっこよくないしな、やっぱり今風のプログラムを書きたいよな。今風ってなんのことかわからないけど、試しに最新の論文でも調べてみるか！お、この論文の名前はかっこいいな。
Jonathan T.Barron著 "The Fast Bilateral Solver"
発表時期は2015年なので、最新といえます。なにより、Bilateral Solverの名前にピンときたので、プログラミングをするには最高のテーマに出会えたと感じました。これが、僕とバイラテラルソルバ（ここからはカタカナ表記でいきます）の出会いです。そして、半年に渡る苦悩の始まりでもあったのです・・・！
この連載は、バイラテラルソルバに出会ってから、解読するまでの戦いを描いたものです。始めた当時は簡単に実装できる予定だったのですが、それは甘い考えでした。費やした期間は約半年。それも遊び惚けていたわけではなく、それなりにリサーチをしての半年です。
解読が完了した時、スタート時への反省も踏まえて、ブログ記事を修正したい気持が湧きました（めんどいので保留中でした）。今回、このブログのアクセス数も微妙に増えてきたし、時間もできたので、第０回だけでも書き直してみました。
バイラテラルソルバ ガイダンス
バイラテラルソルバとは、画像処理向けの最適化問題の解法です。
・・・という風に僕は理解しています。あくまで素人が趣味（？）で調べただけなので、以下に記載する内容に自信はありません。一応僕はメーカで働いていますが、画像処理は専門外ですし、仕事とは全くの無関係です。
バイラテラルソルバを使えるようになるには、以下のキーワードを理解しなくてはなりません。
- バイラテラルグリッド
- 不完全コレスキー分解
- 共役勾配法
- 行列の二重確率化
普通に生活している分には、聞きなれない単語が並んでいますね。知らない人は試しにググってみてください。マジでたいした情報が出てきません。いくつかのキーワードについては、このブログが検索上位に出るぐらいです。バイラテラルソルバ解読の足跡ですが・・・それだけマイナーな内容です。詳しく知りたいなら、論文を読んでみるか、専門書で情報を集めてください。正直、僕は何度か心折れています。
そんなこんなで意味のわからないバイラテラルソルバですが、実装が成功した時の感動は忘れられません！ カラリーゼーション という色塗りアルゴリズムがあるのですが、オリジナルの方法では一枚の色を塗るのに何十分とかかりました。バイラテラルソルバを使うと数秒で完了します。これは凄いことです。例えば、他人にデモをリアルタイムで見せることができるのです！ 試しに彼女に見せましたが、「ふーん、凄いね」と枯れた反応が返ってきました・・・。まぁ、見てくれるだけうれしいですw
Bilateral Solverでカラリゼーション
少し専門的に
画像を見ていて、何かこうしたいなぁ、ってありませんか。例えば、写っている物体の奥行きを取りたいなぁとか。のんのんびよりを見ていて、こまちゃんのショットだけ取り出したいなぁとか。猫ちゃんの動画見ていて、モザイクとりたいなぁとか・・・
こんな時、画素を一つ一つの独立した存在として捉えて処理すると、あまり良い結果は得られないでしょう。もちろん画像処理のアルゴリズムとしてそういう方法もあるのですが、結果は粗雑になりがちです。高精度な結果を得たいなら、ある画素とその周辺画素の関係、さらには画像全体と各部の関係を見ることになります。
最適化問題とは、各要素の関係について数式を定義して、その数式について解を求めることです。画像の場合、要素とは画素や特徴点です。本当に求めたい答えを探り当てることは不可能なので、それっぽい答えを数学的に求めるのです。
バイラテラルソルバは、最適化問題の解法の一つであり、「画像処理に適した特性」を内蔵しています。単語でいうと、エッジ保持型平滑化、という特性になります。画像の中には、物体内の連続した領域、物体と物体の境界のような断続した領域（ = エッジ）が含まれています。エッジ保持型平滑化は文字通り、エッジは残して、それ以外の領域をボカす処理のことです。ボカすという処理は、情報を捨てているようにも思いますが、周辺の情報を参考にしているとも言えます。画像内のある物体についての情報を集める（＝ボカす）際、関係のない物体（=エッジの外）は収集の対象から外したいのです。ここら辺の話については、Guided FilterとかBilateral Filterとか調べてみてください。
エッジ保持型平滑化フィルタでボカしたアルパカ（OpenCVのDomain Transform Filter使用）
より具体的な実装の話に入って、本記事の最後とします。バイラテラルソルバとは、最適化問題をバイラテラルグリッド空間で解きます。バイラテラルグリッドを使う利点は次の２つです。
１つは、エッジ保持型平滑化の特性を内蔵することになります。バイラテラルグリッドはバイラテラルフィルタの亜種です。
もう１つは、式変形をうまく実施することで、最適化問題の解を高速に求めることができます。係数行列の二重確率化を実施後、前処理付き共役勾配法を適用します。
終わり
以上、少しはバイラテラルソルバのイメージがついたでしょうか・・・？ 大丈夫です。僕はさっぱり理解できていません。それでも実装できたのですから、興味があったら、根気よく取り組んでみてくださいね。
