確率モデルによる画像処理における統計的学習理論

Presentation on theme: "確率モデルによる画像処理における統計的学習理論"— Presentation transcript:

1 確率モデルによる画像処理における統計的学習理論
東北大学 大学院情報科学研究科 田中 和之 6 November, 2008 IEICE-MIH (Sendai）

2 Contents 序論 確率的画像処理 確率伝搬法 まとめ 6 November, 2008 IEICE-MIH (Sendai）

3 必要なデータが完全に得られるわけではない． 大量のデータは得られるが必要な情報の抽出が難しい．
情報処理の守備範囲の推移 数値計算のための情報処理 作業手順が与えられている． 理詰めの情報処理 法則・命題群からの予測 コンピュータの発達により現実化 現実世界の情報処理 現象の起こる要因の多様性 必要なデータが完全に得られるわけではない． 大量のデータは得られるが必要な情報の抽出が難しい． 「すぐ分かること」と「本当に知りたいこと」のギャップからくる不確実性→何とかして克服したい!! 確率的情報処理 6 November, 2008 IEICE-MIH (Sendai）

4 不確実性を確率・統計を用いて表現することの代償
確率的情報処理における計算の壁 不確実性を確率・統計を用いて表現することの代償 起こりやすいことも起こりづらいこともまじめに考慮して計算 計算量的困難 統計的計算技法の改良による計算困難の打破 6 November, 2008 IEICE-MIH (Sendai）

5 たくさんが関連して集まり構成されたシステム： 情報と物理が扱う対象に共通する概念
ビットが集まってデータを形成し，コトとなる． 主な研究対象 情報工学：コト データ 物理：モノ 物質・自然現象 ０,1 ビット コト（データ） 並びをきちんと決めることによって意味のある文章になる． More is different in informatics as well 共通点：たくさんが関連 分子が集まって物質を形成し，モノになる． 分子 モノ（物質） 分子同士は引っ張り合っている． 6 November, 2008 IEICE-MIH (Sendai）

6 More is Different 宇宙 社会 素粒子物理学 クォーク 生命 中性子 材料 陽子 原子核 物質 物性物理学 電子 化合物
分子 原子 P. W. Anderson 6 November, 2008 IEICE-MIH (Sendai）

7 確率的画像処理 確率的画像処理手法によるノイズ除去 基本単位は画素 画素上の数字は ディスプレイの 光の強度 最も簡単な既存のフィルター
192 202 190 192 202 190 202 219 120 202 173 120 100 218 110 100 218 110 信号処理の知見をもとにした画像処理の確率モデル化 マルコフ確率場モデル 確率的画像処理 アルゴリズム化 6 November, 2008 IEICE-MIH (Sendai）

8 Contents 序論 確率的画像処理 確率伝搬法 まとめ 6 November, 2008 IEICE-MIH (Sendai）

9 画像修復の確率モデル 雑音 通信路 原画像 劣化画像 6 November, 2008 IEICE-MIH (Sendai）

10 2値画像の事前確率(Prior Probability)
= > p ？ 問題設定 画素の周辺の状態が固定されて いるとき着目画素の状態は？ > 赤い線が少ないほど確率が高くなるように確率モデルを設計 周りが白ければ着目画素も白くあるべき 6 November, 2008 IEICE-MIH (Sendai）

11 2値画像の事前確率(Prior Probability)
= > ？-？ 問題設定 画素の周辺の状態が固定されて いるとき着目画素の状態は？ > = > 画素がいくつか集まると周りの画素の状態をよく見ながら自分の状態を決めないといけなくなる 赤い線が少ないほど確率が高くなるように確率モデルを設計 もっとたくさん集まったらどうなるか? 6 November, 2008 IEICE-MIH (Sendai）

12 ゆらぎが大きいときに何が実際に起こっているのか?
p 最近接画素間の共分散 Markov Network lnp p が大きい p が小さい マルコフ連鎖モンテカルロ法によるサンプリング 無秩序状態 秩序状態 ゆらぎが大きく点の近くのパターン 6 November, 2008 IEICE-MIH (Sendai）

13 ゆらぎが大きいときのパターンを画像処理に使えるか?
p 最近接画素間の共分散 Markov Network 小 ln p 大 似ている 6 November, 2008 IEICE-MIH (Sendai）

14 = = > = > p p p 255 強磁性体と確率モデル Ising モデル
共通点：まわりと同じ状態をとろうとする p > = 画像は各画素ごとの 強さの異なる光で あらわされる． 255 Markov Random Field (MRF) モデル 6 November, 2008 IEICE-MIH (Sendai）

15 Prior Probability in Probabilistic Image Processing
Samples are generated by MCMC. Markov Chain Monte Carlo Method 6 November, 2008 IEICE-MIH (Sendai）

16 Additive White Gaussian Noise
Degradation Process Additive White Gaussian Noise Histogram of Gaussian Random Numbers 6 November, 2008 IEICE-MIH (Sendai）

17 画像処理は平均，分散，共分散の計算に帰着
ベイズ統計と画像処理 事前確率 加法的白色ガウス雑音 または２元対称通信路 劣化画像 原画像 事後確率 Ω：すべての画素の集合 B：すべての最近接画素対の集合 画像処理は平均，分散，共分散の計算に帰着 計算困難 6 November, 2008 IEICE-MIH (Sendai）

18 Statistical Estimation of Hyperparameters
Hyperparameters a, b are determined so as to maximize the marginal likelihood Pr{G=g|a,b} with respect to a, b. Original Image Degraded Image Marginalized with respect to F In the image restoration, we usually have to estimate the hyperparameters alpha and p. In statistics, the maximum likelihood estimation is often employed. In the standpoint of maximum likelihood estimation, the hyperparameters are determined so as to maximize the marginal likelihood defined by marginalize the joint probability for the original image and degraded image with respect to the original image. The marginal likelihood is expressed in terms of the partition functions of the a priori probabilistic model and the a posteriori probabilistic model. We can calculate these partition functions approximately by using the Bethe approximation. Marginal Likelihood 6 November, 2008 IEICE-MIH (Sendai）

19 Maximization of Marginal Likelihood by EM Algorithm
Q-Function EM (Expectation Maximization) Algorithm E-step and M-Step are iterated until convergence: In the image restoration, we usually have to estimate the hyperparameters alpha and p. In statistics, the maximum likelihood estimation is often employed. In the standpoint of maximum likelihood estimation, the hyperparameters are determined so as to maximize the marginal likelihood defined by marginalize the joint probability for the original image and degraded image with respect to the original image. The marginal likelihood is expressed in terms of the partition functions of the a priori probabilistic model and the a posteriori probabilistic model. We can calculate these partition functions approximately by using the Bethe approximation. 6 November, 2008 IEICE-MIH (Sendai）

20 Contents 序論 確率的画像処理 確率伝搬法 まとめ 6 November, 2008 IEICE-MIH (Sendai）

21 計算困難のポイントは何か 2L 通りの和が計算できるか？ L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法
このプログラムでは L=10個のノードで1秒かかるとしたら L=20個で約17分， L=30個で約12日， L=40個で約34年かかる． 厳密に計算するのは一部の特殊な例を除いて難しい． L 重ループ マルコフ連鎖モンテカルロ法 確率伝搬法 今回 6 November, 2008 IEICE-MIH (Sendai）

22 扱いやすい確率モデルのグラフ表現 扱いやすい確率モデルの数理構造 扱いやすくない確率モデルの数理構造 A D B C 木構造をもつグラフ表現
別々に和を計算できる A 扱いやすくない確率モデルの数理構造 B C 閉路を含むグラフ表現 別々に和を計算することが難しい 6 November, 2008 IEICE-MIH (Sendai）

23 転送行列法＝確率伝搬法（1） 1次元鎖 6 November, 2008 IEICE-MIH (Sendai）

24 転送行列法＝確率伝搬法（2） パスはひとつ 漸化式 6 November, 2008 IEICE-MIH (Sendai）

25 閉路のないグラフ上の確率伝搬法 閉路が無いことが重要!! 同じノードは２度通らない 6 November, 2008
IEICE-MIH (Sendai）

26 確率的画像処理における 確率伝搬法(Belief Propagation)
着目画素とその近傍画素だけを残すと木構造になる． 確率伝搬法(Belief Propagation)の統計的近似アルゴリズムとしての転用 6 November, 2008 IEICE-MIH (Sendai）

27 閉路のあるグラフ上の確率モデル の確率伝搬法(Belief Propagation)
２ １ ３ ４ ５ 閉路のあるグラフ上でも局所的な構造だけに着目してアルゴリムを構成することは可能． ただし，得られる結果は厳密ではなく近似アルゴリズム メッセージに対する固定点方程式 平均，分散,共分散はこのメッセージを使ってあらわされる 6 November, 2008 IEICE-MIH (Sendai）

28 確率的画像処理における 確率伝搬アルゴリズムの基本構造
４近傍の場合は3入力1出力の更新式 ひとつの画素ごとに４種類の更新パターン 画素上での 動作の様子 の一例 6 November, 2008 IEICE-MIH (Sendai）

29 Belief Propagation BP EM
Input Update Rule of BP ２ １ ３ ４ ５ BP EM Output 6 November, 2008 IEICE-MIH (Sendai）

30 Maximization of Marginal Likelihood by EM Algorithm
Exact In the image restoration, we usually have to estimate the hyperparameters alpha and p. In statistics, the maximum likelihood estimation is often employed. In the standpoint of maximum likelihood estimation, the hyperparameters are determined so as to maximize the marginal likelihood defined by marginalize the joint probability for the original image and degraded image with respect to the original image. The marginal likelihood is expressed in terms of the partition functions of the a priori probabilistic model and the a posteriori probabilistic model. We can calculate these partition functions approximately by using the Bethe approximation. Loopy Belief Propagation 6 November, 2008 IEICE-MIH (Sendai）

31 Image Restoration by MRF and Conventional Filters
MSE Statistical Method 327 Lowpass Filter (3x3) 388 (5x5) 413 Median Filter 486 445 Original Image Degraded Image Restored Image Finally, we show only the results for the gray-level image restoration. For each numerical experiments, the loopy belief propagation ca give us better results than the ones by conventional filters. MRF (3x3) Lowpass (5x5) Median 6 November, 2008 IEICE-MIH (Sendai）

32 Digital Images Inpainting based on MRF
Markov Random Field Input Output M. Yasuda, J. Ohkubo and K. Tanaka: Proceedings of CIMCA&IAWTIC2005. 6 November, 2008 IEICE-MIH (Sendai）

33 結合ガウス・マルコフ確率場モデル ライン場についての事前情報 6 November, 2008 IEICE-MIH (Sendai）

34 量子力学的に拡張されたライン場を導入した確率場モデル
結合ガウス・マルコフ確率場モデル ライン場のない確率場モデル 原画像 劣化画像 ライン場を導入した確率場モデル 量子力学的に拡張されたライン場を導入した確率場モデル 6 November, 2008 IEICE-MIH (Sendai）

35 Contents 序論 確率的画像処理 確率伝搬法 まとめ 6 November, 2008 IEICE-MIH (Sendai）

36 確率伝搬法（Belief Propagation）
確率モデルによる画像処理技術入門 ベイズ統計をつかった画像処理 画像処理の事前分布 磁性体の物理モデルとの類似性 確率伝搬法（Belief Propagation） 6 November, 2008 IEICE-MIH (Sendai）

37 標本平均による統計的性能 Mean Square Error の標本平均 Markov Network Prior Probability
Nishimori and Wong (1999): Physical Review E Mean Square Error の標本平均 スピングラス理論による解析的評価が可能 Noise Markov Network Prior Probability 脳の物理モデル の記憶容量， パーセプトロンの容量 の評価に類似の議論 原画像 劣化画像 推定画像 マルコフ連鎖モンテカルロ法 6 November, 2008 IEICE-MIH (Sendai）

38 統計的性能評価 劣化過程 事前確率 事後確率 劣化画像 原画像 修復画像 6 November, 2008
IEICE-MIH (Sendai）

39 References K. Tanaka: Statistical-Mechanical Approach to Image Processing (Topical Review), J. Phys. A, 35 (2002). A. S. Willsky: Multiresolution Markov Models for Signal and Image Processing, Proceedings of IEEE, 90 (2002). 6 November, 2008 IEICE-MIH (Sendai）