Goal-based Caustics
この論文の一部です。
 |
| こんな画像を |
 |
| こんなガウス分布で近似することで |
 |
| こんな感じになります |
画像をいわゆる画素ごとの輝度値ではなく、ガウス分布の重ね合わせで表現します。
イメージとしては、スポットライトをたくさん集めて、画像を作ろうぜ！みたいな。
暗い所はスポットライトの個数を減らして、そのかわり大きな面積に投影してやって、
逆に明るい所はたくさんスポットライトを集めて投影しようっていうアイデア。
どこにどんだけスポットライトを集めて投影するか(ガウス分布をどのように配置するか)
を決定するために、EMアルゴリズムを用いています。
EMアルゴリズム
反復計算によって、クラスタリングを行う手法です。
以下のような混合ガウス分布モデルを考えます。
%20%3D%20%5Csum_%7Bi%3D0%7D%5E%7Bm%7D%20%5Cfrac%7B%20w_i%20%7D%20%7B%202%5Cpi%20%5Csqrt%7B%5Cdet%20%5CSigma_i%7D%7D%0A%5Cexp%5Cleft(%0A-%5Cfrac%7B1%7D%7B2%7D%20%0A(%20%5Cmbox%7B%5Cboldmath%20%24x%24%7D%20-%20%5Cmu_i%20)%5ET%0A%5CSigma_%7Bi%7D%5E%7B-1%7D%0A(%20%5Cmbox%7B%5Cboldmath%20%24x%24%7D%20-%20%5Cmu_i%20)%0A%5Cright)%0A%5Cend%7Balign*%7D&f=c&r=300&m=p&b=f&k=f){kind=small}
この入力データに最もよくフィットするガウス分布のパラメータと、各データがどのガウス分布に属しているかのクラスタリングを行います。
EMアルゴリズムの由来は、以下のEステップとMステップの繰り返しを行うことからこののように呼ばれています。
Mステップ：各データがどれくらい各分布に近いかを表す負担率γ(znk)を計算
%0A%7D%7B%0A%5Csum_%7Bj%3D1%7D%5E%7BN%7D%7B%5Ccal%20N%20%7D(%20%5Cbf%7Bx_j%7D%20%5C%20%5Cbf%7B%20%5Cmu_j%20%7D%2C%20%5CSigma_j%20)%0A%7D%0A%5Cend%7Balign*%7D&f=c&r=300&m=p&b=f&k=f)
Eステップ：計算した負担率に基づき，分布のパラメータを決定
%20%0A(%20%7B%5Cbf%20x_n%7D%20-%20%5Cmu_%7Bk%7D%5E%7Bnew%7D%20)%20%5ET%0A%5Cend%7Balign*%7D&f=c&r=300&m=p&b=f&k=f){kind=small}
このEステップとMステップを繰り返すことで最適化を行います。
停止条件とか収束は、各パラメータの変動を見て、あまり変化がなければ終了ということでいいと思います。
大域的最適の保証はされませんが、各ステップでかならず更新されることは保証されます。
ソースコードはgistにアップロードしました。
https://gist.github.com/1708777
画像の読み込みやデータの入出力以外はシンプルな2次元EMアルゴリズムとして動くと思います。
初期解を与えてやる必要があるんですが、論文ではCCVT（容量保存ボロノイ分割）を用いています。多分K-meansでも動くと思いますが、
下手な初期解を与えると発散します。
この論文のシステム上、画像の画素数よりも少ないけど重ね合わせのできる仕組みを使って画像を表現する必要があるのですが、一般的な用途でも使い道がないわけではありません。
平均と分散がガウス分布のパラメータなので、一つの分布あたり６変数で決めることが出来ます。分布の数にもよりますが、512×512の画像を2048個のガウス分布で近似した場合、画素数は5%まで圧縮できます。
解凍はFFTなどを要しないのですぐにできるのですが、圧縮が1~2分くらいのオーダーでかかってくるので、そこがネックになると思います。
