& 3 3 ' ' (., (Pixel), (Light Intensity) (Random Variable). (Joint Probability). V., V = {,,, V }. i x i x = (x, x,, x V ) T. x i i (State Variable),

Size: px

Start display at page:

Download "& 3 3 ' ' (., (Pixel), (Light Intensity) (Random Variable). (Joint Probability). V., V = {,,, V }. i x i x = (x, x,, x V ) T. x i i (State Variable),"

ぜんまのたけ
7 years ago
Views:

1 .... Deeping and Expansion of Large-Scale Random Fields and Probabilistic Image Processing Kazuyuki Tanaka The mathematical frameworks of probabilistic image processing are formulated by means of Markov random fields and Bayesian inference. Some practical algorithms are constructed by applying belief propagation methods. Markov random fields and belief propagation methods can be regarded as one of statistical-mechanical approaches to probabilistic information processing. In the present paper, we review some fundamental frameworks and statisticalmechanical approaches of probabilistic image processing.. (Genrrative Model).,,, Graduate School of Information Sciences, Tohoku University.,.,,,..,.,. (Bayes Formula).., (Compulational Complexity).,., (Belief Propagation) 98,,.,,, (Statistical-Mechanical Informatics). ) 3),..,,.., (Bayes Formula),,,. (Bayesian Inference). (Prior Probability),, (Posterior Probability). 9/6/ c 9 Information Processing Society of Japan

2 & 3 3 ' ' (., (Pixel), (Light Intensity) (Random Variable). (Joint Probability). V., V = {,,, V }. i x i x = (x, x,, x V ) T. x i i (State Variable), x (State Vector). i (Random Variable) X i, X = (X, X,, X V ) T, (Random Vector). x Pr{X = x}. Pr{X = x}...,..,. Pr{X = x},. Pr { X = x } {i,j} E exp ( α(x i x j ) ) () E {i, j}. V =,,, 3,. E = { {, }, {, 3}, {3, }, {5, 6}, {6, 7}, {7, 8}, {9, }, {, }, {, }, {, 5}, {, 6}, {3, 7}, {, 8}, {5, 9}, {6, }, {7, }, {8, } } (). V E (V, E) x = (x, x,, x ) T. (V, E) Pr{X = x}. &/3 5 '6 ' ( &/3 ) 3 * 3 + ( 3, ) ) 3 * * * ,, ) 3E- * 3F&G. + 3F&?&, 3H& - &/. && & 5 798:<;%=?> 7@;A=:<;B;%>C7@;B;A:<;BD> Lmn?opqb # $!!" #%$ IKJMLON5PFQRP<STPVURPFWXPZYOPZ[\PH]\PF^XP_N6`\P_NaN5PN5Q b cdjelxfn5pfq ghp@fiqrp<sjghp!fkstpvu ghp!fiwxphyrgp@fby\pz[xgp@fb[\pz]xgp@fb^\pn6`xgp@fnl`\pnmnoghp@fn6òpnmnoghp fnmnlp_n5q ghp@fnlpfwtghp!fqrphyrghp!fkstph[rgp@furpz]xgp@fbw\ph^tghp@fayopn6`xgp@fa[opnmnoghp!fb]\p_n5q gb x () Pr{X = x}. (Q = ). (). V = {, }, E = { {, } } x (V, E). x =, x,,. Pr{X = } = Pr{X = } > Pr{X = } = Pr{X = } (3) ( ).. 9/6/ V = {, }, E = {, } x = (, ) T, (, ) T, (, ) T, (, ) T () Pr{X = x}. c 9 Information Processing Society of Japan

9/6/ V = {,, 3,, 5, 6, 7, 8, 9} () E = { {, }, {, 3}, {, 5}, {5, 6}, {7, 8},

$5 i, x i = ( i V \{5}) 5 x 5 = x 5 = Pr{X = x} x 5 = ( 3 ).$ V = {,,, } E ().

3 9/6/ V = {,, 3,, 5, 6, 7, 8, 9} () E = { {, }, {, 3}, {, 5}, {5, 6}, {7, 8}, {8, 9}, {, }, {, 5}, {3, 6}, {, 7}, {5, 8}, {6, 9} } (5) (V, E) 5. 5 i, x i = ( i V \{5}) 5 x 5 = x 5 = Pr{X = x} x 5 = ( 3 ). 3 V = {,,, 9}, E (5) 5, x i = ( i V \{5}) 5 x 5 = x 5 = () Pr{X = x} x 5 =. V = {,,, } E (). (V, E) 6 7, ( x i ) = (i {,, ( 5, 9, ) }), x i = ( (i {3, ), 8,, }) 6 7 x 6 =,,, Pr{X = x} x 7 x 6 =., (), 6, 7 x 7.., V V = {,,, }, E () 6 7,! x i = (i {,!,! 5, 9, }),! x i! = (i {3,, 8,, }) 6 7 x 6 =,,, Pr{X = x} x 7!! x 6 =. x 7., Pr { X = x } x., x = x = = x V,., x = x = = x V x., E {i, j} x i = x j {i, j} (x i x j {i, j} ) x. () Pr { X = x } (Markov Chain Monte Carlo: MCMC) ),5), x = (x, x, x V ) T 5. 5 () Pr X = x x = (x, x, x V ) T. 5 α. 3 c 9 Information Processing Society of Japan

4 , x i x j {i, j} K(x) (x i x j) = ( δ xi,x j ) (6) {i,j} E {i,j} E. x K(x) Pr { X = x }. K(x) % x A = {x K(x)/ E.} Pr{A} Pr { X = x } Ā {x K(x)/ E >.} Pr{Ā} {x K(x)/ E.} {x K(x)/ E >.}. α Pr { X = x } Pr{A} > Pr{Ā} (7),,, α, Pr{A} < Pr{Ā} (8). A Pr{X = x}, A, Pr{A}. α x i = x j ({i, j} E) x, x i = x j({i, j} E) x. 5 α x. (7) (8) α.. 5 α = α α.... Cov[X i, X j ] (x i µ i )(x j µ j )Pr{X = x} ( {i, j} E) (9) x =x = x V =. µ i X i. µ i x =x = x V = x i Pr{X = x} () V + (9) Cov[X i, X j] α 6, α = α = 6 V + (9) Cov[X i, X j ].. 5 α =, ( 7 ).. x 8. Q = 56 () 3. 3 V \{5} 5. 9/6/ Pr{X 5 = x 5 X =, X =, X 3 =, X =, X 6 =, X 7 =, X 8 =, X 9 = } Pr{X =, X =, X3 =, X =, X5 = x5, X6 =, X7 =, X8 =, X9 = } = Pr{X =, X =, X 3 =, X =, X 6 =, X 7 =, X 8 =, X 9 = } () c 9 Information Processing Society of Japan

$X x X x x X X3 x3 X3 x3 X x X x XV = X5, XV \{5} =, xv = x5, xv$ $\{5} = X6 x6 X6 x6 X7 x7 X x 7 7 X8 x8 X8 x8 X X9 X9 x x9 (3) x9$ $この記号をつかうと式 ()-() は画素 5 以外の画素の輝度値が xi ( i V \{5}) であるときの画素 5$ $Pr{X5 = x5 XV \{5} = xv \{5} } = Pr{XV \{5} = xv \{5} } = 図 8 式$ $Y Pr{X5 = x5 XV \{5} = xv \{5} } exp α(x5 xj ) Pr{X =, X =, X3$ $=, X =, X6 =, X7 =, X8 =, X9 = } = X Pr{XV = xv } Pr{XV \{5} =$ $= } () (5) (6) j 5 x5 = () 5 {,, 6, 8} (7) Pr{X5 = x5 XV \{5} =$

5 9/6/ 情報処理学会研究報告図 7 通常の自然画像を値化した画像と図 5 の α = のときの生成画像の類似性. X x X x x X X3 x3 X3 x3 X x X x XV = X5, XV \{5} =, xv = x5, xv \{5} = X6 x6 X6 x6 X7 x7 X x 7 7 X8 x8 X8 x8 X X9 X9 x x9 (3) x9 という記号を導入する. この記号をつかうと式 ()-() は画素 5 以外の画素の輝度値が xi ( i V \{5}) であるときの画素 5 の輝度値に対する確率は次のように与えられる. Pr{X5 = x5 XV \{5} = xv \{5} } = Pr{XV \{5} = xv \{5} } = 図 8 式 () の確率分布におけるマルコフ連鎖モンテカルロ (Markov Chain Monte Carlo) 法による生成画像 x. X x5 = Pr{XV = xv } 式 ()-(5) に式 () を代入すると次の式が得られる. Y Pr{X5 = x5 XV \{5} = xv \{5} } exp α(x5 xj ) Pr{X =, X =, X3 =, X =, X6 =, X7 =, X8 =, X9 = } = X Pr{XV = xv } Pr{XV \{5} = xv \{5} } Pr{X =, X =, X3 =, X =, X5 = x5, X6 =, X7 =, X8 =, X9 = } () (5) (6) j 5 x5 = () 5 {,, 6, 8} (7) Pr{X5 = x5 XV \{5} = xv \{5} } = Pr{X5 = x5 Xk = xk, k 5} (8) 5 は画素 5 のすべての最近接画素の集合をあらわしている. 式 (6) 式が長いのでが成り立つことを示している. 同様にして, 図の例で V \{6, 7} の画素の状態が固定されている場合に 5 c 9 Information Processing Society of Japan

6 X V = X X X 3 X X 5 X 6 X 7 X 8 X 9 X X X, X V \{6,7} = X X X 3 X X 5 X 8 X 9 X X X, x V = x x x 3 x x 5 x 6 x 7 x 8 x 9 x x x, x V \{6,7} = x x x 3 x x 5 x 8 x 9 x x x (9), 6 7. Pr{X 6 = x 6, X 7 = x 7 X V \{6,7} = x V \{6,7} } = Pr{X V \{6,7} = x V \{6,7} } = x 6 =x 7 = ()-() (). Pr{X 6 = x 6, X 7 = x 7 X V \{6,7} = x V \{6,7} } ( exp ( α(x 6 x k ) )) k 6\{7} exp ( α(x 6 x 7 ) )( Pr{X V = x V } Pr{X V \{6,7} = x V \{6,7} } () Pr{X V = x V } () k 7\{6} exp ( α(x 7 x k ) )) () {6} {, 5, 7, }, {7} {3, 6, 8, } (3) Pr{X 6 = x 6, X 7 = x 7 X V \{6,7} = x V \{6,7} }. = Pr{X 6 = x 6, X 7 = x 7 X k = x k, k {6, 7}} () () (),. X V (Markov Random Field: MRF),. Pr{X i = x i X V \{i} = x V \{i} } = Pr{X i = x i X k = x k, k {i}} ( i V ) (5) i i., () () (V, E). Pr{X i = x i X V \{i} = x V \{i} } exp ( α(xi x k) ) (6) k i Pr{X i = x i, X j = x j X V \{i,j} = x V \{i,j} } ( exp ( α(x i x k ) )) k i\{j} exp ( α(xi xj))( 3. k j\{i} exp ( α(xj x k) )) (7) (),.. x. (Additive White Gaussian Noise). n i (i V ) n = (n, n,, n V ) y = (y, y,, y V ). y = x + n (8) y = (y, y,, y V ) Y = (Y, Y,, Y V ) ( 9 ). Pr{Y = y X = x} exp ( σ (y i x i ) ) (9) i V 9/6/ Pr{Y = y X = x} x y, y x Pr{X = x Y = y}. () (9) (Bayes 6 c 9 Information Processing Society of Japan

3 3 -. / -. / 3 3-75 -+- - -65 -+- - 5 6 7 8 9 5 6 7 8 9 : 3>; 33 3 : 3<; 3=3 3 9/6/ #"! 9 "!#!#!$ % & %'& ()*+*!#!#!,+ % & %'& (9). %$'&, '&#()(*(+& -,- $. /&&#()()(+&, -,- (3).

Pr{Y = y X = x}pr{x = x} Pr{Y = y} exp ( σ (y i x i ) ))( {i,j} E (3) Pr{X = x Y exp ( α(x i x j ) )) (3) = y} (Posterior Probability)., Pr{X = x} (Prior Probability).

7 / -. / : 3>; 33 3 : 3<; 3=3 3 9/6/ #"! 9 "!#!#!$ % & %'& ()*+*!#!#!,+ % & %'& (9). %$'&, '&#()(*(+& -,- $. /&&#()()(+&, -,- (3). Pr{X = x Y = y},. X i ( ), E[X i] = Q Q x =x = Q x V = x ipr{x = x Y = y} (3) Formula). Pr{X = x Y = y} = ( i V (9) y. Pr{Y = y X = x}pr{x = x} Pr{Y = y} exp ( σ (y i x i ) ))( {i,j} E (3) Pr{X = x Y exp ( α(x i x j ) )) (3) = y} (Posterior Probability)., Pr{X = x} (Prior Probability). () Pr{X = x} (3) Pr{X = x Y 9. = y}. O(exp( V )). ( ) (Belief Propagation). {i, j} M i j (x j ) M j i (x i ) (Message). (3) (Message Propagation Rule) ( ). Q M j i (x i ) Constant exp ( α(x i z) σ (z y j) ) z= M k j (z) ( {i, j} E) (3) k j \{i} 7 c 9 Information Processing Society of Japan

$Q M i j(x j) Constant exp ( α(xj z) (z yi)) σ z= M k j (z) ( {i, j} E) (33) k i \{i} j j, j \{i} j i. (3)-(33),, k j \{i} O()., O( V ).$

8 Q M i j(x j) Constant exp ( α(xj z) (z yi)) σ z= M k j (z) ( {i, j} E) (33) k i \{i} j j, j \{i} j i. (3)-(33),, k j \{i} O()., O( V ). {M i j (x), M j i (x) {i, j} E}, ). 98,, (Low Density Parity Check: LDPC), (Code Division Multiple Access: CDMA), (Satisfiability: SAT). 3),6) 8). 3),6),9). (Sample Average)., () x, x (9) y., y Pr{ X Y = y} x x = x(y) x x d(x, x) = (xi xi) V i V,.,.,,., Q Q Q ( d ( x, x(y) ) x =x = x V = Pr{Y = y X = x}dy dy dy V )Pr{X = x} (3),. (3) (Spin Glass Theory), (Configuration Average).,,,, CDMA, 3),) ). 9/6/ 8 c 9 Information Processing Society of Japan

9 5.. (),,. 5). ),). (No.879, No.8798) COE. ) K. Tanaka: Statistical-Mechanical Approach to Image Processing (Topical Review), Journal of Physics A: Mathematical and General, Vol.35, No.37, pp.r8- R5,. ) :,, 6. 3) ( ): SGC,, 6. ) :, (3). 5), : II,, 5. 6),,,, : I,, 3. 7) C. M. Bishop Pattern Recognition and Machine Learning, Springer, 6. 8) M. J. Wainwright and M. I. Jordan: Graphical Models, Exponential Families, and Variational Inference, now Publishing Inc, 8. 9) M. Opper and D. Saad (eds): Advanced Mean Field Methods Theory and Practice, MIT Press,. ) :,, 999. ) H. Nishimori: Statistical Physics of Spin Glasses and Information Processing, An Introduction, Oxford University Press,. ) : /,,. 3) Y. Kabashima and D. Saad: Statistial Mechanics of Low-Density Parity-Check Codes (Topical Review), Journal of Physics A: Mathematical and General, Vol. 37, No.6, pp.r-r3,. ) M. Mézard and A. Montanari: Information, Physics, and Computation, Oxford University Press, 9. 5) A. S. Willsky: Multiresolution Markov models for signal and image processing, Proceedings of IEEE, vol.9, no.8, pp ,. ( 5 9 ) ( ) ,,,, IEEE-CIS. 9/6/ 9 c 9 Information Processing Society of Japan

main.dvi

main.dvi 1 10,.,,.,,,.,,, 2. 1,, [1].,,,.,,.,,,.. 100,,., [2]. [3,4,5]. [6,7,8,9,10,11]. [12, 13, 14]. 1 E-mail: [email protected] CDMA [15, 16].. 1970, 1980 90, 1990 30,,. [17, 18]. [19, 20, 21]. [17,