電気・通信・電子・情報工学実験D 確率的情報処理の基礎技術 Part 4 (2012年4月) 本実験DのWebpage: http://www.smapip.is.tohoku.ac.jp/~kazu/ECEI-ExperimentD/2012/ 東北大学 大学院情報科学研究科 田中 和之 [email protected] http://www.smapip.is.tohoku.ac.jp/~kazu/ April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 1 本講義の参考文献 田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006. 田中和之著: ベイジアンネットワークの統計的推論の数理, コロナ社, 2009. 田中和之編著: 臨時別冊・数理科学SGCライブラリ「確率的情報処理と統計 力学 ---様々なアプローチとそのチュートリアル」, サイエンス社,2006. 安田宗樹, 片岡駿,田中和之共著 (分担執筆): ---CVIMチュートリアルシリー ズ--- コンピュータビジョン最先端ガイド3(八木康史,斎藤英雄編), 第6章.大 規模確率場と確率的画像処理の深化と展開,pp.137-179, アドコム・メディア 株式会社, December 2010. Kazuyuki Tanaka: Statistical-mechanical approach to image processing (Topical Review), Journal of Physics A: Mathematical and General, vol.35, no.37, pp.R81-R150, 2002. C. M. Bishop: Pattern Recognition and Machine Intelligence, Springer, 2007. M. Opper and D. Saad: Advanced Mean Field Method, MIT Press, 2001. H. Nishimori: Statistical Physics of Spin Glasses and Information Processing, --An Introduction---, Oxford University Press, 2001. M. J. Wainwright and M. Jordan: Graphical Models, Exponential Families, and Variational Inference (Foundations and Trends® in Machine Learning), Now Publishers, 2008. M. Mezard and A. Montanari: Information, Physics, and Computation, Oxford University Press, 2009. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 2 Contents 1. 2. 3. 4. 5. 6. April, 2012 序論:確率的情報処理とベイジアンネットワーク 確率の基礎知識 確率的計算技法の基礎 ---マルコフ連鎖モンテカルロ法と確率伝搬法--確率的画像処理とベイジアンネットワーク ---マルコフ確率場と確率伝搬法--確率推論とベイジアンネットワーク---グラフィカルモ デルと確率伝搬法--まとめ 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 3 画像処理 画像処理の基本操作 ノイズの除去 ぼけた画像からの輪郭線強調 画像の拡大 画像をコンピュータで加工 アプリケーション:Photo Shop, Paint Shop, etc. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 4 画像の基礎知識 画像を使いこなすには画像がどのような形式で数値 データとして保存されているかを理解することが必 要!!→画像表示 P3 640 480 255 192 209 190 202 219 200 213 201 221 218 206 226 210 209 215 211 210 216 211 208 217 211 208 217 210 203 210 217 210 217 216 210 220 217 211 221 218 213 219 218 ……………… コンピュータは数値は扱えるが光そのものは扱えない. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 5 画像表示の基礎 画素の場所→位置ベクトル x y 640 480 307200 Pixels 約30万画素 x ( x, y ) (1,1) (2,1) (3,1) (1,2) ( 2,2) (3,2) (1,3) ( 2,3) (3,3) y 基本単位は画素(ピクセル) April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 6 画像表示の基礎(モノクロ画像) x 画像は各画素ごとの強さの異なる光により表される. ( x, y) f x, y y f x, y 0 f x, y 255 256 256 65536 Pixels 基本単位は画素(ピクセル) 光の強さは0から255までの256段階 0が真っ黒,255が真っ白 各画素にその光の強さに応じて整数値(0,1,2,…,255)を割り当て, データとして保存し,加工する. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 7 画像表示の基礎(モノクロ画像) PGM 形式 f x, y 0 April, 2012 f x, y 1 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 8 画像表示の基礎 (モノクロ画像) PGM 形式 f x, y 0 f x, y 255 P2 # kazu 88 255 0 200 50 125 56 255 255 0 220 210 100 25 255 156 125 125 125 125 105 30 215 100 135 75 105 125 256 200 125 56 255 255 34 210 230 125 56 125 255 125 0 145 145 105 126 30 215 67 125 100 200 25 156 0 225 45 0 126 60 0 56 47 155 160 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 9 画像表示の基礎(カラー画像) x 画像は各画素ごとの赤、緑、青の光の3原色のそれぞれの 強さの異なる光により表される. f R x, y y 基本単位は 画素(ピクセル) 0 75 125 255 赤の光 の強度 f G x, y 緑の光 の強度 f B x, y 青の光 の強度 ( x, y) f x, y f R x, y , f G x, y , f B x, y f x, y 228,116,32 各画素に各色の光の強さに応じて3つの整数値を割り当て, データとして保存し,加工する. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 10 画像表示の基礎(カラー画像) PPM 形式 f x, y 220,210,100 f R x, y 0 75 125 255 赤の光 の強度 f G x, y 緑の光 の強度 f B x, y 青の光 の強度 P3 # kazu 33 255 220 210 100 25 255 156 125 125 25 125 125 105 30 215 80 135 75 54 105 125 256 200 125 56 55 255 156 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 11 モノクロ画像の加工(1) 平滑化フィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) f(x,y) f(x+1,y) f(x-1,y+1) f(x,y+1) f(x+1,y+1) 平均値 g(x,y) f x 1, y 1 f x, y 1 f x 1, y 1 1 g x, y f x 1, y f x, y f x 1, y 9 f x 1 , y 1 f x , y 1 f x 1 , y 1 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 12 モノクロ画像の加工(1) 平滑化フィルター f(x-1,y-1) f(x,y-1) f(x+1,y-1) 1/9 1/9 1/9 f(x-1,y) f(x,y) f(x+1,y) 1/9 1/9 1/9 f(x-1,y+1) f(x,y+1) f(x+1,y+1) 1/9 1/9 1/9 f x 1, y 1 f x, y 1 f x 1, y 1 1 g x, y f x 1, y f x, y f x 1, y 9 f x 1 , y 1 f x , y 1 f x 1 , y 1 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 13 1/9 1/9 1/9 モノクロ画像の加工(1) 1/9 1/9 1/9 平滑化フィルター 1/9 1/9 1/9 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 14 モノクロ画像の加工(1) 平滑化フィルター 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 April, 2012 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 15 モノクロ画像の加工(2) 微分は差分に置き換える 2 f x, y f x 1, y f x, y f x, y f x 1, y 2 x f x 1, y 2 f x, y f x 1, y 2 f x, y f x, y 1 f x, y f x, y f x, y 1 2 y f x, y 1 2 f x, y f x, y 1 ラプラシアン 2 2 f x, y 2 f x, y f x 1, y f x 1, y 2 x y f x, y 1 f x, y 1 4 f x, y April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 16 モノクロ画像の加工(2) 2 2 f x, y 2 f x, y f x 1, y f x 1, y 2 x y ラプラシアンフィルター f x, y 1 f x, y 1 4 f x, y f(x-1,y-1) f(x-1,y) f(x,y-1) f(x+1,y-1) f(x,y) f(x+1,y) f(x-1,y+1) f(x,y+1) f(x+1,y+1) 0 1 0 1 0 -4 1 1 0 g x, y f x, y 1 f x 1, y f x 1, y f x, y 1 4 f x, y April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 17 モノクロ画像の加工(2) April, 2012 0 1 0 1 -4 1 0 1 0 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 18 モノクロ画像の加工(2) 0 0 0 0 1 0 0 0 0 - 0 1 0 1 -4 1 0 1 0 0 -1 0 -1 5 -1 0 -1 0 ー April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 19 モノクロ画像の加工(線形フィルター) 様々の線形フィルター の設計が可能 f(x-1,y-1) f(x,y-1) f(x+1,y-1) a(x-1,y-1) a(x,y-1) a(x+1,y-1) f(x-1,y) f(x,y) f(x+1,y) a(x-1,y) a(x,y) a(x+1,y) f(x-1,y+1) f(x,y+1) f(x+1,y+1) a(x-1,y+1) a(x,y+1) a(x+1,y+1) g x, y a x 1, y 1 f x 1, y 1 ax, y 1 f x, y 1 a x 1, y 1 f x 1, y 1 a x 1, y f x 1, y a x, y f x, y a x 1, y f x 1, y a x 1, y 1 f x 1, y 1 a x, y 1 f x, y 1 a x 1, y 1 f x 1, y 1 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 20 モノクロ画像の加工(3) f(x-1,y-1) f(x,y-1) f(x+1,y-1) f(x-1,y) f(x,y) f(x+1,y) = f(x-1,y+1) f(x,y+1) f(x+1,y+1) 192 209 190 202 219 120 100 218 110 192 209 190 202 219 120 100 218 110 ソーティング 100 110 120 190 192 202 209 218 219 192 202 190 Median 202 219 120 192 100 218 110 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 21 モノクロ画像の加工(3) f ( x 1,y 1) g x, y Median f ( x 1, y ) f ( x 1, y 1) f ( x, y 1) f ( x, y ) f ( x, y 1) (3x3) メジアンフィルター April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] f ( x 1, y 1) f ( x 1, y ) f ( x 1, y 1) 22 モノクロ画像の加工(3) f ( x 1,y 1) g x, y Median f ( x 1, y ) f ( x 1, y 1) f ( x, y 1) f ( x, y ) f ( x, y 1) f ( x 1, y 1) f ( x 1, y ) f ( x 1, y 1) (3x3) メジアンフィルター f ( x 2, y 2) f ( x 2, y 1) g x, y Median f ( x 2, y ) f ( x 2, y 1) f ( x 2, y 2) f ( x 1, y 2) f ( x 1,y 1) f ( x 1, y ) f ( x 1, y 1) f ( x 1. y 2) f ( x, y 2) f ( x, y 1) f ( x, y ) f ( x, y 1) f ( x, y 2) f ( x 1, y 2) f ( x 1, y 1) f ( x 1, y ) f ( x 1, y 1) f ( x 1, y 2) f ( x 2, y 2) f ( x 2, y 1) f ( x 2, y ) f ( x 2, y 1) f ( x 2, y 2) (5x5) メジアンフィルター April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 23 モノクロ画像の加工(3) メジアンフィルター (3x3) メジアン フィルター (5x5) メジアン フィルター April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 24 カラー画像の加工 平滑化フィルター f(x-1,y-1) f(x-1,y) f(x-1,y+1) f(x,y-1) f(x,y) f(x,y+1) f(x+1,y-1) f(x+1,y) 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 f(x+1,y+1) f x 1, y 1 f x, y 1 f x 1, y 1 1 g x, y f x 1, y f x, y f x 1, y 9 f x 1, y 1 f x, y 1 f x 1, y 1 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 25 カラー画像の加工 平滑化フィルター f x 1, y 1 f x, y 1 f x 1, y 1 1 g x, y f x 1, y f x, y f x 1, y 9 f x 1, y 1 f x, y 1 f x 1, y 1 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 26 画像の様々の加工技術 ベクトルメジアンフィルター ウィナーフィルター 拘束条件付き最小自乗フィルター その他 各自インターネットで調べてみよう April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 27 ノイズ(モノクロ画像) 加法的ノイズ ノイズ g x, y f x, y nx, y 劣化画像 April, 2012 原画像 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 乱数 28 ノイズ(カラー画像) 加法的ノイズ ノイズ g x, y f x, y n x, y 劣化画像 April, 2012 原画像 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 乱数 29 モノクロ画像のノイズ除去(1) 平滑化フィルター April, 2012 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 30 モノクロ画像のノイズ除去(2) メジアンフィルター (3x3) メジアン フィルター (5x5) メジアン フィルター April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 31 カラー画像のノイズ除去 平滑化フィルター 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 1/9 April, 2012 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 1/25 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 32 画像修復の確率モデル 劣化画像 原画像 白色ガウス雑音 雑音 通信路 原画像 劣化画像 尤度 事前確率 事後確率 Pr劣化画像 | 原画像Pr原画像 Pr原画像 | 劣化画像 Pr劣化画像 周辺尤度 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 33 画像修復の事前確率分布 1 2 PrF f exp f i f j Z Prior 2 {i , j}E 1 2値画像の例 マルコフ連鎖モンテカルロ法によるサンプリング (fi=0,1) 2 4 1 E:すべての最近 接画素の集合 Paramagnetic V:すべての画 素の集合 April, 2012 Ferromagnetic α=1.76… 付近でゆらぎがおおきくなる. 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 34 劣化過程 2元対称通信路 (Binary Symmetric Channel) PrG g F f p 1 fi , gi 1 p fi , gi iV V:すべての画 素の集合 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 35 劣化過程 加法的白色ガウス雑音 (Additive White Gaussian Noise) PrG g F f iV 1 2 exp 2 f i gi 2 2 2 1 g i f i ~ N 0, 2 V:すべての画 素の集合 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 36 ベイズ統計・最尤推定と画像処理 PrG g F f PrF f f 事前確率 原画像 画素 g g 加法的白色ガウス雑音 劣化画像 または2元対称通信路 事後確率 PrF f G g fˆi PrFi f i G g PrG g F f PrF f PrG g PrF f \ fi f G g 計算困難 各画素ごとの周辺事後確率 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 37 画像処理とベイズ統計の事後確率 1 1 2 2 PrF f G g exp f i g i f i f j Z Posterior 2 {i , j}E 2 iV 1 1 p 2元対称通信路 2 ln p 加法的白色ガウス雑音 PrF f G g 1 1 2 f , f Z Posterior {i , j}E {i , j } i j 1 1 1 2 2 2 {i , j} f i , f j exp f i g i f j g j f i f j 8 2 8 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 38 確率的画像処理と ベイジアンネットワーク 事後確率 ベイジアンネットワーク PrF f G g PrG g F f PrF f PrG g 閉路のあるグラフ上の確率モデル 1 PrF f G g {i , j} f i , f j Z Posterior {i , j}E V:すべての画素の集合 E:すべての最近接画素対の集合 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 39 マルコフ確率場 PrF f G g f , f 1 Z Posterior {i , j}E {i , j } i j PrFi f i Fi f1 , , Fi 1 f i 1 , Fi 1 f i 1 , , FL f L , G g f , f PrF f G g P x x PrF z G g z , f {i , j } i j ji i {i , j } zi (V , E ) zi i i j j i j ji i (V , E ) マルコフ確率場 i :画素 i のすべての最近接画素の集合 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 40 確率伝搬法 閉路のあるグラフ上の確率モデル PrF f G g 1 f , f Z Posterior {i , j}E {i , j } i j V:すべての画素の集合 E:すべての最近接画素対の集合 PrF1 f1 G g PrF f G g f \ f1 3 4 1 5 April, 2012 2 M 21 f1 M 31 f1 M 41 f1 M 51 f1 M 21 z1 M 31 z1 M 41 z1 M 51 z1 z1 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 41 閉路のあるグラフ上の確率モデル M 12 f 2 z , f M z M z M z {1, 2} 1 3 5 2 1 2 1 31 1 41 1 51 1 z2 閉路のあるグラフ上でも局所的な 構造だけに着目してアルゴリムを 構成することは可能. ただし,得られる結果は厳密では なく近似アルゴリズム M M April, 2012 51 1 z , z M z M z M z z1 1 41 1 z1 {1, 2} 4 31 2 メッセージに対する固 定点方程式 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 42 確率伝搬法による2値画像の画像修復アルゴリズム Step 1: 8L 個のメッセージについての連立非線形方程式 1 z , f M z M z M z 3 4 1 2 M 12 f 2 z1 0 1 1 {1, 2} 31 2 41 1 51 1 1 z , z M z M z M z z1 0 z 2 0 5 1 {1, 2} 1 2 31 1 41 1 51 1 を反復法により数値的に解く. Step 2: 得られたメッセージを 3 4 1 5 P1 f1 2 M 21 f1 M 31 f1 M 41 f1 M 51 f1 1 z 0 M 21 z1 M 31 z1 M 41 z1 M 51 z1 に代入し,原画像の推定値を fˆ1 arg max P1 z により求める. z 0 ,1 具体的なアルゴリズムは 田中和之: 統計力学を用いた確率的画像処理アルゴリズムの基礎 -- 確率伝搬法と統計力学 --, ミニ特集「ベイズ統計・統計力学と情報処理」, 計測と制御, vol.42, no.8, pp.631-636, 2003. などを参照. April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 43 Binary Image Restoration by Gaussian Graphical Model p 0 .2 (α,p) の推定値 ̂ , p̂ は統計的学習理論 により劣化画像から決定 ̂ MSE p̂ p=0.1 0.07072 0.28981 0.07902 p=0.2 0.11864 0.38206 0.17184 p 0 .2 ̂ MSE p=0.1 0.04761 0.41097 0.04857 p=0.2 0.08319 0.39216 0.13290 MSE April, 2012 p̂ 1 f i fˆi | | i 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 2 44 Binary Image Restoration by Gaussian Graphical Model 原画像 April, 2012 劣化画像 p 0.2 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 修復画像 45 Image Restoration by Gaussian Graphical ˆ ,ˆは統計的学習理論 Model (α,σ) の推定値 により劣化画像から決定 40 ̂ MSE Belief Propagation 40 327 ̂ 260 MSE April, 2012 0.000611 MSE Belief Propagation ̂ ̂ 0.000574 1 f i fˆi | | i 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 36.302 33.998 2 46 Image Restoration by Gaussian Graphical Model and Conventional Filters Original Image Degraded Image 40 MSE Belief Propagation 327 Lowpass Filter (3x3) 388 (5x5) 413 Median Filter (3x3) 486 (5x5) 445 MSE Belief Propagation April, 2012 (3x3) Lowpass 1 fi fˆi | | i (5x5) Median 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 47 2 Image Restoration by Gaussian Graphical Model and Conventional Filters Original Image MSE Degraded Image 40 Belief Propagation 260 Lowpass Filter (3x3) 241 (5x5) 224 Median Filter (3x3) 331 (5x5) 244 MSE Belief Propagation April, 2012 (5x5) Lowpass 1 f i fˆi | | i (5x5) Median 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 48 2 Gray-Level Image Restoration (Spike Noise) Degraded Image Original Image Belief Propagation Lowpass Filter Median Filter MSE: 2075 MSE: 244 MSE: 217 MSE:135 MSE: 3469 MSE: 371 April, 2012 MSE: 523 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] MSE: 395 49 まとめ 画像処理の基礎 確率的画像処理としてのベイジアンネット ワーク 確率伝搬法によるアルゴリズム化 April, 2012 電気・通信・電子・情報工学実験D [Kazuyuki Tanaka Part 4] 50
© Copyright 2024 ExpyDoc