画像解析論講義資料11

画像解析論（１１）
画像解析論（１１）
－MAP-MRFに基づく画像処理－
東京工業大学長橋宏
主な講義内容
• ビジュアルラべリング
• 近傍システムとクリーク
• MRFとGRF
• MAP-MRFについて
1
画像解析論（１１）
2
ビジュアルラベリング
[Besag, J (1974)]
統計的手法による画像処理では，通常の画像処理の用語
以外にも，統計的手法の用語も用いられる．
サイト(site)
--- 画素や特徴などの配置情報識別子
（規則的配置と不規則的配置を含む）
m個のサイトのインデックス集合 S  {1,  , m}
例えば，画素，エッジ，領域などの集合
ラベル(label)
--- サイトに起きる事象．
（連続と離散，順序関係の有無などを表現）
離散ラベル集合 Ld  {l1 ,  , lM }(li  {1,  , M }) :
M種のインデックスの集合やM濃度階調の集合
画像解析論（１１）
●
サイト集合の例
m個のサイトのインデックス集合 S  {1,, m}
例えば，画素，エッジ，領域などの集合
●
ラベル集合の例
離散ラベル集合Ld  {l1 ,, lM }( {1,, M })　:
M個のラベル（インデックス）集合
連続ラベル集合Lc  [ X l , X h ]  R :
実数線上の区間 : [ X l , X h ]
濃度ラベル集合L  {0, 255}　:
M個の順序付きラベル集合
3
画像解析論（１１）
ラベリング問題
多くの画像処理問題が，ラベル L によるサイト S の
ラベリング問題として記述される．
サイト集合 S のサイト si (i  1,  , m)に，ラベル集合
L から１つのラベルを選び，割り当てる．
L   li | i  1,  , M 
S から L への写像関数 : f ( si )  f i , f i  {l1 , l2 , , lM }
f :S L
全てのサイトが同じラベル集合を共有するならば，
m
 配置空間 : 
L

L
L

L


m
4
画像解析論（１１）
近傍システム
画像処理と同様に，MRFでも近傍系という概念が
重要な役割を果たす．
サイト集合 S 内の各要素は隣接システム（N - system)に
よって互いに関係付けられる．
N - system : N  {N i | i  S }
N i は，サイト i に隣接するサイトの集合．ただし，
1) i  N i ,
2) i  N j  j  N i
規則的サイトの例
0
0 x 0
0
0 0 0
0 x 0
0 0 0
1次隣接系(NS1) ２次隣接系(NS2)
5
4
3
4
5
4
2
1
2
4
3
1
x
1
3
4
2
1
2
4
5
4
3
4
5
１～５次隣接系
5
画像解析論（１１）
6
クリーク（Clique)
クリークとは
無向グラフG  (V , E )，
(V：頂点集合，E：エッジ集合)の
クリーク C とは，
𝐶 ⊆ 𝑉,かつ𝐶に属する任意の2頂点を繋ぐ辺が𝐺に存在
する（完全グラフとなる）頂点の集合
クリークに属する頂点数をクリークの
大きさと呼ぶ
2
1
6
完全グラフの例
左のグラフにおけるクリークは
{1,2,4}のみ．その大きさは３
4
5
3
画像解析論（１１）
7
クリークの表現
NS2システムにおけるクリークの型と接続関係
(d)
C1  {{i} | i  S }
(e)
(g)
C2  {{i, i ' } | i '  N i , i  S }
(f)
(h)
（シングルサイト）
（ペアサイト）
C3  {{i, i ' , i '' } | i, i ' , i ''  Sで互いに隣接}（トリプルサイト）
全てのクリークを集めたもの：C  C1  C2  C3  
クリーク中のサイトには順序関係がある  {i, i ' }  {i ' , i}
画像解析論（１１）
Markov Random Field (MRF)
物理現象における空間的，文脈的な依存
関係を解析するための確率論の１つ．
サイト集合 S 上のランダム変数の族
F  ( F1 , F2 ,  , Fm )
において，各ランダム変数 Fi はラベル集合
L内の１つの値をとる．この値をf i  {l1 , l2 ,  , lM }と
するとき，　( Fi  f i ) と表す．
結合事象 ( F1  f1 , F2  f 2 ,  , Fm  f m ) を，
F  f , f  ( f1 , f 2 ,  , f m )
と簡略表記．
8
画像解析論（１１）
9
Fi が値 f i をとる確率：
P( Fi  f i )，P( f i )と略記．
その結合確率：
P( F1  f1 ,  , Fm  f m )， P( f )と略記．
連続なラベル集合 Lに対しては，
確率密度関数 : p ( Fi  f i ), p ( F  f )
𝑭が次の２つの条件を満たすとき，
1) P( f )  0, f  F　, (F：結合事象集合) 正値性
2) P( f i | f S {i} )  P( f i | f N i ) マルコフ性
𝑓𝑁𝑖 = {𝑓𝑗 |𝑗 ∈ 𝑁𝑖 }
『𝑭は，隣接システム𝑁に関するサイト集合𝑺上の
マルコフ・ランダム場である．』
(Markov Random Field)
画像解析論（１１） 10
Gibbs Random Field (GRF)
ランダム変数Fの事象配置がGibbs分布に従うとき、
Fは，Nに関するS上のGibbsランダム場と呼ばれる．
P( f ) : 特定の配置パターン f の生起確率(事前情報）．
Gibbs分布：P( f )  Z 1  e
Z
e
1
 U( f )
T
1
 U ( f ')
T
f 'F
U ( f )   Vc ( f )
；正規化定数
Ｆ：結合事象（パターン）集合
; エネルギー関数
cC
Vc ( f ) : 全ての可能なC上のクリークポテンシャル
画像解析論（１１） 11
あるGRFのVc ( f )が、S上のクリークCの
相対的な位置に依存しないとき，
　均一性GRF
方向に対して独立なとき，　　等方性GRF ．
エネルギー関数：U ( f )
U ( f )   Vc ( f )
cC

 V ( f )  V ( f , f
{i}C1
1
i
{i , j }C 2
2
i
j
)
V ( f , f
3
{i , j , k }C3
i
j
, fk )  
ペアサイトクリークまでを考慮した場合，
U ( f )   V1 ( f i )    V2 ( f i , f j )
iS
iS jN i
総和のサイト表現
画像解析論（１１） 12
Markov-Gibbs Equivalence
局所的な性質で特徴付けられるMRF
等価
大局的な性質で特徴付けられるGRF 
MRFの結合確率P( f )を特定する手段の提供
同時に，MRF に基づく確率統計モデルの最適化問題を
エネルギー最適化問題とすることが可能．
画像解析論（１１） 13
文脈情報の表現
画像処理・理解では，文脈情報が重要．
確率の観点からは，局所的な条件付確率
によって文脈情報を表現．
サイトi におけるラベル f i
サイトj ( j  Ni )におけるラベル f j
条件付確率　P( f i | f Ni ), f Ni  { f j | j  N i }
直接的に観測可能な局所的情報から
大局的情報を推論する．
画像解析論（１１） 14
MRFによる画像特徴表現
基本的な概念：
２つのラベル間の文脈的拘束：
単純，低コスト  広く利用．
 通常，ペアサイトクリークまでを考慮．
U ( f )  V1 ( f i )   V2 ( f i , f j )
iS
iS jN i
 V1 ,V2を目的毎に選択．
特定のMRF(GRF)を構成可能．
幾つかの代表的なモデルが存在．
画像解析論（１１） 15
ベイズの定理と条件付き確率
𝑃 𝑓1 , ⋯ , 𝑓𝑚 =
（𝑓1 , 𝑓2 , ⋯ , 𝑓𝑚 の結合事象の生起確率）
𝑃 𝑓𝑖 𝑓1 , ⋯ , 𝑓𝑖−1 , 𝑓𝑖+1 , ⋯ , 𝑓𝑚 𝑃(𝑓1 , ⋯ , 𝑓𝑖−1 , 𝑓𝑖+1 , ⋯ , 𝑓𝑚 )
𝑓𝑖 が，サイト𝑖の近傍値のみに依存すると仮定
𝑃 𝑓𝑖 𝑓1 , ⋯ 𝑓𝑖−1 , 𝑓𝑖+1 , ⋯ , 𝑓𝑚 = 𝑃 𝑓𝑖 𝑓𝑁𝑖 ,
𝑓𝑁𝑖 = {𝑓𝑗 |𝑗 ∈ 𝑁𝑖 }
一方，𝑃(𝑓1 , ⋯ , 𝑓𝑖−1 , 𝑓𝑖+1 , ⋯ 𝑓𝑚 )は，
𝑃 𝑓1 , ⋯ , 𝑓𝑖−1 , 𝑓𝑖+1 , ⋯ , 𝑓𝑚 =
𝑓𝑖 ∈𝐿 𝑃(𝑓1 , 𝑓2 , ⋯ , 𝑓𝑖 , ⋯ , 𝑓𝑚 )
従って，サイト𝑖における事象𝑓𝑖 の条件付き確率は，
𝑃 𝑓𝑖 𝑓𝑁𝑖
𝑃(𝑓1 , 𝑓2 , ⋯ 𝑓𝑚 )
=
𝑓𝑖 ∈𝐿 𝑃(𝑓1 , 𝑓2 , ⋯ , 𝑓𝑖 , ⋯ , 𝑓𝑚 )
画像解析論（１１） 16
Auto Logistic Model
𝑓𝑖 ∈ 𝐿 = {0,1}で，ペアサイトまでの文脈を考慮．
ポテンシャル関数，条件付き確率を以下のように仮定．


U ( f )    i f i    i , j f i f j    i f i    i , j f i f j とすると，
{i}C1
{i , j }C 2
iS 
jN i

exp{ i f i   jN  i , j f i f j }
i
P( f i | f Ni ) 
 f {0,1} exp{ i f i   jN  i, j f i f j }
i

i
exp{ i f i   jN  i , j f i f j }
i
1  exp{ i   jN  i , j f j }
i
ただし，𝑓𝑁𝑖 = 𝑓𝑗 |𝑗 ∈ 𝑁𝑖
分布が均一ならば、 i   ,  i , j  として良い．
画像解析論（１１） 17
Multi-Level Logistic Model
𝑓𝑖 ∈ 𝐿 = 1, ⋯ , 𝑀 とし，ペアサイトクリークまでを考慮．
（Auto Logistic Modelの一般化）
 単一サイトクリーク：
V1 ( f i )   i , もし f i  i  L
 ペアサイトクリーク：
  C , {i, j}  C2が同一ラベル
V2 ( f i , f j )  
 C , それ以外
ここで， i : ラベルiに対するポテンシャル，
 C ( 0) : ペアサイトポテンシャル．
ポテンシャル関数は
U ( f )  V1 ( f i )   V2 ( f i , f j )
iS
iS jN i
画像解析論（１１） 18
クリークポテンシャルの例
i
i
j
i

1
j
2
j
i
3
i
j
4
モデルが等方性の場合， C  1   2   3   4 で，
このときのMLLにおける条件付確率は
𝑃 𝑓𝑖 = 𝑚 𝑓𝑁𝑖
𝑒𝑥𝑝{−𝛼𝑚 − 𝛽𝑐 ∙ 𝑛𝑖 𝑚 }
= 𝑀
𝑚=1 𝑒𝑥𝑝{−𝛼𝑚 − 𝛽𝑐 ∙ 𝑛𝑖 𝑚 }
ni (m) : mのラベルを持つ，近傍集合N i中のサイト数
画像解析論（１１） 19
(不規則サイトの例）
a
b
h
c
p
f
q
n
i
m
近傍系の定義
e
l

g
Ni
d
k
t
o
r
u
j
s
Nj

画像解析論（１１） 20
Bayes推定
あるリスクを最小化して最適値を推定する
推定値 f * のBayesリスクは，
R( f * )  
f F
C ( f * ,f ) P( f | d )df
（リスクCの期待値）
C ( f * , f ) : コスト関数，　d : 観測値
p( d | f ) P( f )
P( f | d ) 
, 事後確率
p(d )
p(d | f ) : ラベリング f の尤度関数
画像解析論（１１） 21
１次のコスト関数
*

0
,
||
f
 f ||  のとき
*
C( f , f )  
1, それ以外のとき
２次のコスト関数
C ( f * , f ) || f *  f || 2
C( f * , f )
C( f * , f )

(a)

f* f
f* f
(b)
画像解析論（１１） 22
１次コスト関数によるBayesリスク
R( f * )  
f :|| f  f ||
*
 1 
P( f | d )df
f :|| f *  f ||
P( f | d )df
R( f * )を最小化する f *　
f :|| f * f ||
P( f | d )df を最大化
２次コスト関数によるBayesリスク
R( f * )  
f F
R( f * )
0
*
f
|| f *  f || 2 P( f | d )df
f*
f F
f  P( f | d )df
（ラベリング f の事後確率平均）
画像解析論（１１） 23
１次コストによる推定では一般に  0．
従って，最小リスク推定は，f *  arg max P( f | d )
f F
MAP (maximum a posterior)推定
観測されたdに対する確率p(d )を一定とすると
P( f | d ) 
p(d | f ) P( f )
 p ( d | f ) P( f )
p(d )
MAP推定は等価的に：f *  arg max{ p(d | f ) P( f )}
f F
さらに，事前確率P( f )をフラットと仮定すると
f *  arg max p(d | f )　；最尤推定
f F
画像解析論（１１） 24
MAP-MRF Labeling
P( f | d )の導出  MRF
1 U ( f )
P( f )  e
, U ( f )：事前エネルギー
Z
P( f | d ) p(d )  p(d | f ) P( f )
p(d | f ) P( f )
P( f | d ) 
 p(d | f ) P( f )より、
p(d )
事後エネルギーU ( f | d )に関して
U ( f | d )  U (d | f )  U ( f )
MAP推定：事後エネルギーを最小化する f
f *  arg min U ( f | d )  arg min U (d | f )  U ( f )
f
f
画像解析論（１１） 25
MAP-MRF法の概要
1. 与えられた問題を適切なMRFモデルで表現．
2. MAP解を定義する事後エネルギーを導く．
2  1) サイト集合S上の近接システムNと，Nに対する
クリーク集合を定義．
2  2) U ( f )を定義する事前クリークポテンシャル
VC ( f )を定義．
2  3) 尤度エネルギーU (d | f )を導く．
2  4) 事後エネルギーU ( f | d )  U ( f )  U (d | f )を得る．
3. MAP解を探す．
画像解析論（１１） 26
MAP-MRF法と正則化
ビジョンにおける不良設定問題を良設定化する
一般的枠組み：正則化（Regularization)
滑らかさ拘束条件の付加(事前仮説）
MAP- MRF法において
[ f ( n) ]2 の事前エネルギーを考えた場合と等価．
画像解析論（１１） 27
主な参考文献
Besag, J. ;”Spatial interaction and the statistical analysis of lattice systems'‘,
Journal of the Royal Statistical Society, Series B, 36, pp192--236 (1974).
S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the
Bayesian restoration of images," IEEE Trans. on PAMI, vol. PAMI-6, no. 6, pp.
721--741, (1984).
S.Z.Li, Markov Random Field Modeling in Computer Vision, Springer-Verlag,
(1995)

Download Report