読者です 読者をやめる 読者になる 読者になる

しえログ

qiita との使い分けに悩んでる

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

グラフカット エネルギー最小化 コンピュータビジョン

今更ながらグラフカットについて学ぼうとしている。まずは基礎からということで、コンピュータビジョン最先端ガイドの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 }: 画素など「場所」を表すサイトの集合
  • { E \subset V \times 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 | }

{ \displaystyle 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 )推定のときによく使われる。

{ \displaystyle 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 倍となって表現される。

所感

メモとしては一般の方だけで良かったな・・・。せっかく書いたし両方乗っける。
次はグラフカットの本流についても勉強してコードまで落としこめてまたエントリ書きたい。

コンピュータビジョン最先端ガイド1[CVIMチュートリアルシリーズ]

コンピュータビジョン最先端ガイド1[CVIMチュートリアルシリーズ]

  • 作者: 倉爪亮,石川博,加藤丈和,佐藤淳,三田雄志,八木康史,斎藤英雄
  • 出版社/メーカー: アドコム・メディア
  • 発売日: 2008/12/03
  • メディア: 単行本
  • 購入: 9人 クリック: 71回
  • この商品を含むブログ (11件) を見る