*確率伝搬法 とは 　画像などの複数の要素を持つデータに，要素間の整合性を考えた最適なラベルを設定するアルゴリズムの１つです．同じ目的のアルゴリズムに[link:グラフカット]があります．確率伝搬法は，画像上で類似する領域をラベリングする処理や非連続な信号を取り除くノイズ除去などに良く利用されます．図１は，入力画像を単純に各画素の値のみに基づいたラベリング結果と，確率伝搬法を使って画素の連続性を考えたラベリング結果を表します． [img:twkg] {{small:図１ 左：入力画像　右A：単純なラベリング，右B：確率伝搬法によるラベリング}} 　図１のAは，各画素の値だけを見てラベルを設定しているため，細かなラベルの変動が目立ちます．一方，図１のBはラベルの変動が少なく，Aに比べると画像の各領域をうまく区別できているように見られます． 　 　確率伝搬法について詳しく学びたい場合，[1]の文献が参考になります．基本的アルゴリズムに加え，画像を入力とした場合の効率的な計算方法が提案されています． {{small:[1]P.F.Felzenszwalb, D.R.Huttenlocher, "Efficient Belief Propagation for Early Vision", Computer Vision and Pattern Recognition (CVPR), 2004}} {{small:[link:http://cs.brown.edu/people/pfelzens/papers/bp-cvpr.pdf] }} *サンプルコード (C++) ライブラリ：[link:simplesp] サンプルコード：simplesp/sample/sp/beliefpropagation Lennaの画像をラベリングします． *アルゴリズム 　確率伝搬法では，要素間でメッセージと呼ばれる数値をやり取りします．そして，それを繰り返すことで要素全体にメッセージを伝搬させます．具体的に，要素間のメッセージは文献[1]の式(2)により計算することになります． [img:jqv3] {{small:図２ 要素間のメッセージ}} 　図２の式（２）の{$m_{pq}^t(f_q)$}（赤矢印）は要素{$p$}から要素{$q$}へのメッセージを表します．メッセージは，接続関係のあるすべての要素（画像の場合，例えば各画素の４近傍）について定義しますが，ここでは簡単のため要素{$p$}から要素{$q$}へのメッセージにのみ注目して説明します． 　まず，メッセージ{$m_{pq}^t(f_q)$}の素性ですが，要素{$q$}に{$f_q$}のラベルを設定するとした場合に，要素{$p$}の側から見たときにその設定が良いか悪いかを表すコストです．このコストは{$V(f_p, f_q)$}，{$D_p(f_p)$}，{$m_{sp}^{t-1}(f_p)$}（緑矢印）によって計算します．なお，{$t$}は繰り返し計算の何回目かを表す数値です．確率伝搬法の処理は，すべての要素間でメッセージを計算した後，また同じ処理を繰り返します．一回目のメッセージのやり取りでは，隣り合う要素の情報しか考慮されませんが，繰り返し行うことで遠くのメッセージも考慮した数値が計算できます． 　次に，式（２）の各項について説明します． 　{$V(f_p, f_q)$}は，要素{$p$}と{$q$}にそれぞれ{$f_p$}と{$f_q$}のラベルを設定する時に必要なコストです．これは平滑化項とも呼ばれます．通常，同じラベルを設定する場合に低い値，異なるラベルを設定する場合に高い値を設定します．{{small:詳しくは文献[1]の式（３）の次の式を参考にしてください}} 　{$D_p(f_p)$}は要素{$p$}の保持する値（例えば画素の輝度値）だけを見て設定するコストです．例えば，その画素の輝度値に適しラベル{$f_p$}を設定する場合に低い値，適さないラベル{$f_p$}を設定する場合に高い値を設定します．これはデータ項とも呼ばれます． 　{$m_{sp}^{t-1}(f_p)$}（緑矢印）は１つ前の時点で，要素{$p$}に送られたメッセージです．具体的には，要素{$p$}の周囲にある{$a$}，{$b$}，{$c$}から送られたメッセージです．ちなみに一度目の繰り返しの時点では，{$m_{sp}^{t-1}(f_p)$}はゼロとします． 　このメッセージの計算を所定の回数繰り返し，最後に各要素について，自身に向かうメッセージとデータ項を合計した値{$b_q(f_q)$}に基づいて，各要素のラベルを設定します．