グラフカット以前のエネルギー最小化

今更ながらグラフカットについて学ぼうとしている。まずは基礎からということで、コンピュータビジョン最先端ガイドの2章を読み進めることに。
学んだことについてメモを記していくけど、まずはエネルギー最小化について。

2値画像のノイズ除去

エネルギー最小化によって2値画像のノイズを除去する場合、まず場所を表すサイトの集合 ${ V }$ を定義する。画像 ${ Y }$ が与えられたとして、その画素の1つ1つがサイトと考えられる。

${ V=\{\left(i,j\right) \mid i=1,\dots,n; j=1,\dots,m\} }$

2値画像なので各画素の取りうる値（ラベル）は以下のようになる。

${ L=\{0,1\} }$

ノイズを除去した2値画像は各画素に0か1を割り振りなおす形で得られる。各サイトにラベルを割り振ることを配置といい、 ${ V }$ から ${ L }$ への写像と言える。これを ${ (V,L) }$ の配置と呼ぶ。配置 ${ X }$ といったとき、 ${ X }$ はサイト ${ u \in V }$ にラベル ${ X_u \in L }$ を割り振るものとする。
ノイズ画像において隣接画素間の変化が少なくなるような ${ X }$ を探して、それを除去画像とするわけだけど、やりすぎると完全に一色の画像となってしまう。これらのトレードオフをエネルギーという関数で定義することでエネルギー最小化の問題を解くことができる。
以下の式における ${ X }$ を動かして ${ E(X) }$ が最小となる ${ X }$ を見つける。

${ E(X) = \displaystyle \sum_{v \in V} \lambda | Y_v - X_v | + \displaystyle \sum_{(u,v) \in E} \frac{\kappa}{2} | X_u - X_v | }$

${ u, v }$ : ${ V }$ の元
${ E }$ : ${ (u, v) }$ 全体からなる集合 ( ${ E \subset V \times V }$ )
${ \lambda, \kappa }$ : 正の定数
${ Y }$ : ノイズ入り画像を表す配置

一般の場合

↑の式を少し抽象的にすると以下の式の形になる。

${ E(X) = \displaystyle \sum_{v \in V} g_v(X_v) + \displaystyle \sum_{(u,v) \in E} h_{uv}(X_u, X_v) }$

${ V }$ : 画素など「場所」を表すサイトの集合
: サイト間の隣接関係を表す集合
- ${ (u, v) \in E }$ のときサイト ${ u }$ と ${ v }$ は隣接している
- ${ (u,v) \in E \Leftrightarrow (v, u) \in E }$

解くべき問題は ${ V }$ の各サイトにラベルを割り振ること。ラベルの有限集合を ${ L }$ として、 ${ (V, L) }$ を配置と呼ぶ。
${ (V, L) }$ の配置 ${ X }$ とは、 ${ V }$ の各サイト ${ v }$ にラベル ${ X_v \in L }$ を与える写像。

${ \begin{eqnarray} X \colon V &\mapsto& L\\ v &\mapsto& X_v \end{eqnarray} }$

${ V }$ を画素の全体、 ${ L }$ として全体の色を取れば、 ${ n \times m }$ 画素の RGB ビットマップ画像は、各画素に色をひとつずつ与える配置 ${ X }$ と考えることが出来る。

${ L = \{\left(r,g,b\right) \mid r =0,\dots,255; g=0,\dots,255; b = 0, \dots, 255 \} }$

${ \begin{eqnarray} X \colon V &\mapsto& L\\ (i,j) &\mapsto& X_{(i,j)} = (r_{i,j}, g_{i,j}, b_{i,j}) \end{eqnarray} }$

このような ${ X }$ にエネルギー ${ E(X) }$ を与えるのが↑の式になる。
2値画像での例を持ち出すと、

${ g_v(X_v) = \lambda | Y_v - X_v | }$

$h_{uv}(X_u, X_v) = \frac{\kappa}{2} | X_u - X_v |$

になる。　 ${ g_v(X_v) }$ はサイトとそのサイトに付与されたラベルのみによる値なのでデータ項、 ${ h_{uv}(X_u, X_v) }$ は隣接するサイト間で ${ X }$ に与えられるラベルがどのような関係にあるべきかを示す（普通は隣接ラベル間の変換を平滑化する）ため平滑化項と呼ばれる。

${ E(X) }$ のようなエネルギー式はマルコフ確率場（ MRF ）の最大事後確率（ MAP ）推定のときによく使われる。

$P(X | D) = \frac{P(D | X)P(X)}{P(D)}$

において、データ ${ D }$ が与えられたとき、 ${ D }$ は固定済みなので ${ P(D) }$ は定数となり、 ${ P(D | X)P(X) }$ を最大化することで ${ P(X | D) }$ が最大となり、MAP 推定としては最大化する ${ X }$ を求めれば良いことになる。このとき、 ${ D }$ の尤度 ${ P(D | X) }$ がデータ項に、 ${ P(X) }$ が平滑化項に、それぞれ対数値の -1 倍となって表現される。