穴日記

どうだ明るくなったろう

たのしいメトロポリス法のメモ

適当なメモなので間違っていたら突っ込んでください

Metropolis法でレンダリングするのが最近ますます流行っているらしいです。SIGGRAPH2012のQuasi-Monte CarloのコースでもMetropolis Light Transportとかが話題になってたみたいです。

https://sites.google.com/site/qmcrendering/

さて、よく聞くMetropolis法とは実はただのサンプリング手法でしかありません。手元の「パターン認識機械学習 下巻」でも「第11章 サンプリング法」のところで出てきます。これによると、Markov Chain Monte Carlo(いわゆるMCMC)というのは最初物理学に起源があり、Metropolis先生とかが開発したそうです。
Metropolis法とはマルコフ連鎖モンテカルロによってある確率分布pに従うランダムな値を得たいときに使われる手法なわけです。仲間としては重点サンプリングとか棄却サンプリングとかが並べられます。あの辺もある確率分布に従うランダムな値を得るときに頻繁に使われます。

で、Metropolis法をうまいこと一般化とかして使いやすくなったのがMetropolis-Hasingsアルゴリズムです。

確率密度関数一次元の場合のMetropolis法の例とかがあったのでリンクを貼っておきます。

MCMC-1D

確かにサンプリングできていますね。このページは大変勉強になります。二次元の場合等の例もあります。

さて、それではなぜMetropolis法を使うとCGのレンダリングがイケてる感じになるの?という話です。
CGのレンダリングというのはつまるところ目に届く光のシミュレーションに他なりません。光源から出た光が物体に反射とかして目に届くことで人間は物体を知覚するわけですが、基本的にはその過程をシミュレーションすることでレンダリングを行っているわけです。(ただし、光源から光をだすと目に届かないでどっかいっちゃう光がたくさん出てきて効率が悪いので、実装上は観測者側から光の軌跡を逆方向に追跡していますね)

この辺の光の振る舞いとかを数式に落とし込めば便利じゃないか、ということで生まれたのがいわゆるレンダリング方程式 [Kajiya 1986]です。

L_o(\mathbf x, \omega, \lambda, t) = L_e(\mathbf x, \omega, \lambda, t) + \int_\Omega f_r(\mathbf x, \omega', \omega, \lambda, t) L_i(\mathbf x, \omega', \lambda, t) (-\omega' \cdot \mathbf n) d \omega'\!

Kajiya先生はとても偉い方でいまはマイクロソフトリサーチのCG部門のボスをやっているそうです。あそこの研究所のCG部門は毎年SIGGRAPHに死ぬほどたくさん論文を出すことで有名です。
このレンダリング方程式を解けば目に届く光が求められてハッピーなわけですが解析的に解くことがとても難しかったりします。そこで現実にはモンテカルロ積分をはじめとして数値解法を適用することで解いています。

さて、このモンテカルロ積分によるアプローチですが、これは確率的な手法なので適当にランダムな値をたくさんサンプリングする必要があります。具体的にはいろんな方向にレイを飛ばしてレイトレーシングしたりする必要があります。ここで、光源から視点へのある光のパスが一つのサンプルであると考えることが出来ます。そう、ここでサンプリングの話が出てくるわけですね。よくある重点的サンプリングでウマウマやろうというのはまさにここの部分の話題で、あれは無数にありうるサンプル(光のパス)のうち、特に最終的な結果画像に対する影響が大きそうなサンプルをたくさん生成することで精度を上げようという話です。最終的な結果画像に対する影響が大きいとは、そのパスを通って光源から運ばれてくる光の量が大きいということです。一様サンプリング(何も考えないでランダムにレイを飛ばしてサンプリングする方法)だと最終的な結果画像にほとんど影響がないようなサンプルもたくさん生成されるわけですがそんなサンプルまで考慮するのは意味がないわけです。

Metropolis法も考え方としては同じです。あれは確率密度関数pに従うランダムな値を得る手法だったわけですが、pに従うということはつまりpの値が大きい範囲のサンプルがたくさん持ってこれるわけで、pの値が小さい範囲のサンプルはあまり生成されないわけです。このpが最終的な結果画像に対する寄与度だと思ってみると、Metropolis法で生成されるサンプルというのは最終的な結果画像に対する影響が大きいサンプルが多くなります。結果として一様にランダムにサンプルを持ってくるよりも精度の向上が期待できます。つまりMCMC過程でズンズン生成されるサンプルの一つ一つが有効な光源から視点へのパスになるわけで、しかもそれは単なる一様サンプリングによるサンプルに比べて最終的な画像への寄与に基づいたサンプルなわけですからそれを使ってMonte Carlo積分を解けばより高速な分散の収束が見込めということになります。

特に、集光模様のように画像への寄与度が極端に高いようなシーンのレンダリングには効果を発揮します。一方で、pの値すなわち寄与度が大きい部分からばかりサンプルをとってくるために他の部分のサンプルがおろそかになって結果として全体の効率が落ちる、ということもありえます。