確率モデルによる画像処理技術入門

ゆらぎが生み出す新しい情報処理技術
確率伝搬法と確率的画像処理
東北大学大学院情報科学研究科
田中和之
[email protected]
http://www.statp.is.tohoku.ac.jp/~kazu/
参考資料：第48回物性夏の学校講義ノート
「統計力学と情報処理 --- 自由エネルギーの生み出す新しい情報処理技術---」
(田中和之著，物性研究 2004年 2 月号に掲載)
http://www.statp.is.tohoku.ac.jp/~kazu/tutorial-lecture-note/SummerSchool-200308/
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
1
本講義の参考文献
西森秀稔，田中和之他著, “特集/知識情報処理の統計力学的
アプローチ”, 数理科学1999年12月号.
K. Tanaka: Statistical-mechanical approach to image
processing (Topical Review), J. Phys. A: Math. &
Gen.,vol.35, no.37, pp.R81-R150, September 2002.
田中和之・樺島祥介編, “ミニ特集/ベイズ統計・統計力学と情
報処理”, 計測自動制御学会誌「計測と制御」2003年8月号
甘利俊一，池田和司，田中和之他著, “特集/統計科学の最前
線 ― 新しい情報科学への技術と手法 ―”, 数理科学2004年
3月号.
田中和之，田中利幸，渡辺治，喜多一，堀口剛他著，``連載/
確率的情報処理と統計力学 ---様々なアプローチとその
チュートリアル---‘’，数理科学2004年11月号から開始．
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
2
確率的情報処理への統計力学的アプローチ
共通の数理
ギブス分布と指数関数分布属
自由エネルギーとカルバックライブラー情報量
統計力学
ベイズ統計
物性の理解・予言
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
情報科学
情報の抽出・加工
3
統計力学と情報処理の共通点
たくさん集まったものを扱っている．
関連しあって集まっているものを扱っている.
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
4
モノの理とコトの技の接点
モノの理を用いてコトの技を極める．
豊富な経験から得られた方法論の情報処理
への拡張→新しい知見
コトの技を通してモノの理を鍛える．
統計力学を守備範囲の広い強固な理論体系
へとバージョンアップ．
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
5
共通の数理構造
類似性：「たくさんが関
連」
11001100011110…
キーワードは「ベイズの公式」
PrB | APrA
PrA | B 
 PrB | APrA
A
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
6
確率の知識（１）
事象Ａの起こる確率
Pr{A}
事象Aと事象Bの結合確率 PrA, B  PrA  B
条件付き確率と結合確率
PrA, B
PrB A 
PrA
 PrA, B  PrB APrA
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
A
B
7
確率の知識（２ａ）
ベイズの公式
PrA B 
PrB APrA
 PrB APrA
A
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
8
確率の知識（２ｂ）
ベイズの公式の導出
A

PrA, B  PrB APrA

B
PrA, B  PrA BPrB

PrB   PrA, B

A

PrB APrA
PrA, B PrB APrA
 PrA B 


PrB
PrB
 PrB APrA
A
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
9
確率の知識（３）
結合確率分布と周辺確率分布の一般的関係
PrB   PrA, B, C , D
A C D
Ａ
Ｂ
Ｃ
Ｄ
周辺化
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
10
確率的画像処理
K. Tanaka, J. Phys. A, vol.35, no.37, 2002.
劣化画像（ガウス雑音）
確率的画像処理手法
MSE:520
MSE: 2137
ローパスフィルター
MSE:860
ウィナーフィルター
MSE:767
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
メジアンフィルター
MSE:1040
11
誤り訂正符号
誤り訂正符号におけるスピングラス理論の有効性
Y. Kabashima and D. Saad, Europhysics Letters, 1999.



符号化
 
G  J 0


J0
ノイズ


n

G   J
伝送路
  
J  J0  n
復号化
  


1 
P  , J   J ,G  P P 



Z
Prior



スピングラス
模型に対応
復号に平均場理論を用いると高性能の復号アルゴリズムができる．
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
12
誤り訂正符号
1
0
0
1
0
1
0
J
復号
誤り
検出
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
0
?
0
0

1
1
0
0
1
1
0
  
J  J0  n
0
0
0
０
0
1
J0
0
0
0
0
０
０
0
１
1
0
0
１
0
1
1
0
0
０
0
0
0
1
１
０

n
1
1
1
１
０
1
Noise
1
0
0
０
G  J 0
1
1
0

100 符号化
111
010 
並べ
替え
1
100111010
0
1
0

G   J
0

13
CDMA復調法の性能評価
T. Tanaka, IEEE Trans. Inform. Theory, 2002
移動体通信にスピングラス理論が使える．
ノイズ
話し手の信号

拡散符号系列
無線
通信
他人の
会話
拡散符号系列

復号処理
基地局の
受信信号
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
この復調方式をベイ
ズの公式で確率モデ
ル化するとスピングラ
ス模型で表される．
14
符号理論・移動体通信の参考文献
樺島祥介 “物理の世界/学習と情報の
平均場理論”, 岩波書店, 2002.
樺島祥介 “コトの物理学 ---誤り訂正符
号を例として---”,日本物理学会誌,
vol.58, no.4, pp.239-246, 2003.
田中利幸, ``移動体通信技術とスピング
ラスとの意外な関係”, 日本物理学会誌,
vol.56, no.9, pp. 660-666, 2001.
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
15
統計力学的アプローチによる公開鍵暗号
Y. Kabashima, T. Murayama and D. Saad, Phys. Rev. Lett., 2000.
ゴルフコース問題と情報の秘匿
カップが天辺にあれば
何度得ってもボールは
もどってくる
鍵
カップが底にあれば
どこから打ってもボー
ルはカップインする．
エネルギー関数による暗号設計の基本戦略
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
16
人工知能(詳細は次回)
ベイジアンネット
本村陽一, 人工知能学会誌, vol.17, no.5, 2002.
AC
AR
AS
AW
そのまま多体相互作用をもつ
物理モデルに対応づけられる
確率推論システム
平均場理論・転送行列法と同じ枠組みが人工知能では
確率伝搬法（Belief Propagation）として独自に発展
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
17
情報通信トラフィック
T. Horiguchi and S. Ishioka, Physica A, vol.297, 2001.
スピングラスの物理モデルがインターネットの
パケット流制御に使える．
スピングラスの物理モ
デルのある種のダイナ
ミックスとして書き換え
られる．
どの経路を通ってパケットが届けられるか
はその経路の距離と途中のルーターの混
みぐあいによって決まる．
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
18
画像修復の確率モデル
雑音
通信路
原画像
劣化画像
Pr劣化画像 | 原画像 Pr原画像 
Pr原画像 | 劣化画像  
Pr劣化画像 
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
19
画像処理と磁性体の共通の数理
たくさんのノードからなる規則格子．
近傍ノードが関連．
空間フィルターは「平坦さ・
滑らかさ」と「入力画像へ
の近さ」とのかねあいで出
力画像がきまる．
磁性体は「相互作
用」と「外場」のかね
あいで秩序がきまる．
理論的構造
の類似性
 1 1 1

1
 1 1 1
9

 1 1 1
Para
既存のフィルターではデータに
含まれるゆらぎを扱いきれない．
Critical Ferro
相転移温度付近で
ゆらぎが大きくなる．
磁性体の概念を画像処理に持ち込むことでデータのゆらぎを系統
的に扱えるフィルターの設計へとつなげることが可能か？
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
20
大規模情報処理としての確率的情報処理
計算困難の問題．
大規模確率モデルへの近似アルゴリズムの導入．
情報処理における統計力学への期待
平均場理論・確率伝搬法の導入
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
21
２値画像の劣化過程
雑音
y

通信路
原画像
劣化過程 PrG  g F  f  
(２元対称通信路)
  
x
劣化画像
 Wx , y  f x , y 
( x , y )

Wx, y f x, y  p 1   f x , y , g x , y  1  p  f x , y , g x , y
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
f x, y  1
g x, y  1
0 p
1
2
22
２値画像の画像修復の事前確率分布


 1
2
2 
exp     f x , y  f x 1, y    f x , y  f x , y 1  
2 ( x , y )


P rF  f  
 1
2
2 
 f x, y  f x1, y    f x, y  f x, y 1  
f exp  2  ( x
, y )



y


  0.25
  0 .5
 1
( 1  4)
( 1  2)
( 1  1)
x
Paramagnetic
Ferromagnetic
  0.44068付近でゆらぎが大きくなる．
臨界点　物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
23
事後周辺確率最大化
結合確率分布と周辺確率分布の一般的関係
PrB   PrA, B, C
A C
Px , y ( f x , y ) 
A, B, C\ B  A, C
PrF  f G  g

 
f \ f x,y
P rF  f G  g 
事後周辺確率最大化
P rG  g F  f P rF  f 
P rG  g
fˆx, y  arg max Px, y ( f x, y )
f x,y
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
24
確率伝搬法（Belief Propagation）
のメッセージ伝搬規則
 Wxx, y1, y  f x, y , f x 1, y   x 1, y
x , y 1
x , y 1






M
f
M
f
M

x, y
x, y
x, y
x, y
x, y  f x, y 


Wx 1, y  f x 1, y  
f x,y 
x, y
M x 1, y  f x 1, y  
 Wxx, y1, y  f x, y , f x 1, y   x 1, y
x , y 1
x , y 1






M
f
M
f
M


x, y
x, y
x, y
x, y
x, y  f x, y 


Wx 1, y  f x 1, y  
f x , y f x1, y 
( x, y  1)
M
( x  1, y )
x , y 1
x, y
単純な固定点方程式
 
( f x, y )
M xx,y1, y ( f x, y )
M xx, 1y, y ( f x1, y )
( x, y )
M xx,,yy 1 ( f x, y )
( x, y  1)
  
M  M
( x  1, y )
反復法で数値的に
解ける
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
25
固定点方程式と反復法
固定点方程式
反復法
繰り返し出力を入力に入れることにより，
固定点方程式の解が数値的に得られる．
 
 
 


M1   M 0


M 2   M1


M3   M2

 
*  *
M  M
yx
y
M1
0
y  (x)
M * M1
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
M0
x
26
２値画像の画像修復
数値実験（ハイパパラメータは周辺尤度最大化で決定）
原画像
劣化画像
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
修復画像
27
多値画像の画像修復
数値実験（ハイパパラメータは周辺尤度最大化で決定）
原画像
劣化画像（30%）
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
修復画像
28
ガウシアングラフィカルモデル
を用いた画像修復
原画像
劣化画像
MSE: 1512
厳密解
平滑化フィルター
MSE:315
2
1

MSE 
f x, y  fˆx, y 

||
MSE: 411
x, y 
平均場近似
確率伝搬法
MSE: 591
MSE: 325
ウィーナーフィルター
メジアンフィルター
MSE: 545
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
MSE: 447
29
ガウシアングラフィカルモデル
を用いた画像修復
原画像
厳密解
平均場近似
確率伝搬法
MSE: 1409
MSE: 593
MSE: 324
ウィーナーフィルター
メジアンフィルター
MSE: 369
MSE: 259
平滑化フィルター
MSE:306
MSE 
劣化画像
MSE: 268


1
ˆ 2
f

f
 x, y x, y
|  |  x, y 
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
30
まとめ
統計力学と情報処理の不思議な共通点
（モノの理とコトの技）
磁性体と画像処理の共通の数理
データのゆらぎを系統的に扱えるフィルターの設
計へ（確率伝搬法）
詳細はhttp://www.statp.is.tohoku.ac.jp/~kazu/SMAPIP-KazuKazu/
チュートリアル講義ノート，お試し用の基本プログラムも公開中
物理フラクチュオマティクス論講義
（２００４年４月２０日，東北大学）
31

Download Report