轉載BP算法介紹好文

本文轉載自《Belief Propagation 解決計算機視覺問題》，作者lansatiankong

Belief Propagtion在計算機視覺視覺中有相當廣泛的應用，當然這一切離不開MRF、CRF等圖模型的使用。 

很多視覺問題可以表述成一個能量函數的形式，例如，圖像的語義分割或者叫做image parsing問題可以表述成：

E(f)=∑p∈PDp(fp)+∑(p,q)∈NW(fp,fq)

我們的目标是求這個函數的最小值，其中 P 是圖像的像素集合， L 是圖像的像素所屬的标簽集合，這些标簽對應着我們要求的像素的某些量值，例如圖像恢複問題中的原本的像素值，或是更進階的圖像語義分割中像素所屬于的類别。一個标注labeling  f 所做的就是給圖像的每個像素一個标簽，可以把 f 看成一個向量或是矩陣，對應配置設定給圖像的每個像素 p∈P 一個标簽 fp∈L 然後我們用一個能量函數衡量這個标注的好壞。大部分能量函數都是由兩個部分組成，第一個一般叫unary potential，叫一進制勢函數，第二項一般叫pairwise potential，點對勢函數。一般一進制勢函數的作用是展現單個像素點似然标簽，屬于某個标簽的機率高，那麼這個值越小，也有叫label cost，将标簽賦予該像素的損失，例如在圖像恢複裡面，像素有很大的可能性是沒有被noise更改的，這樣可以設原本像素的unary potential小一些；或者根據在圖像語義分割裡面每個像素求到的類條件機率 Dp(fp)=1−P(fp|p) ，似然越高，label cost當然越小。pairwise potential一般是衡量像素與像素之間的标簽關系的，例如MRF，隻會考慮位置相鄰的像素的标簽關系，關于相鄰标簽關系，一方面由于圖像連續性，我們希望圖像的相鄰像素(特别是顔色紋理等特征相似的相鄰像素)會有相同的标簽，另一方面，我們也希望在一些必要的地方，例如物體的邊緣什麼的位置，能夠保持這種邊緣關系，能夠有不同的标簽，不要都over smooth成一個标簽了，一般這個叫做discontinuity preserving property。 N 一般在CV裡面一般就是圖像的像素構成四連接配接grid graph的邊。在【1】中解釋到， Dp(fp) 是将标簽 fp 配置設定給 p 的cost， W(fp,fq) 是配置設定兩個相鄰像素的标簽為 fp,fq 的cost，也叫不連續cost，最小化這個函數和最大化MRF的後驗機率是等價的。 

接着上面的讨論，一般來說discontinuity cost是和相鄰像素的內插補點有關系的，是以一般可以這樣定義 W(fp,fq)=V(fp−fq) ，這樣的話求的能量函數就成了

E(f)=∑p∈PDp(fp)+∑(p,q)∈NV(fp−fq)

要解決這個問題可以用前一篇提到的belief propagation.也就是message passing 

簡單就是說對于每個像素都有一個屬于某個類的belief，每個像素是四連接配接的，可以通過連接配接的邊把這個belief傳遞出去，直到收斂，傳播過程趨于穩定。 

類似于上一篇，首先定義一個傳遞的消息， mtpq 就表示在第 t 次疊代中，從節點 p 傳遞給 q 的消息， m0pq 可以初始化成0。很明顯，這個 mtpq 是一個 |L| 維的向量，|L|是标簽的個數。 

第一步，首先要計算Message

mtpq(fq)=minfp(V(fp−fq)+Dp(fp)+∑s∈Np∖qmt−1sp(fp))

然後計算每個node屬于不同label的belief 

bq(fq)=Dq(fq)+∑p∈Nqmtpq(fq)

就是本身的label cost加上周圍所有節點的message。 

剩下的就是根據計算得到的belief  bq(fq) 得到每個點的label 

f∗q=min{bq(fq)}

整個過程下來的時間複雜度是 O(nk2T) , n 是像素的個數 k 是label的個數， T 是收斂的到疊代次數。每個message需要計算 O(k2) （本身是k維的，而且還有的min函數），一共有 n 的像素，這樣的話每一輪就需要 O(k2)O(n) 次疊代。 

然後作者就想着怎麼對這個過程進行加速了，首先是計算Message update的複雜度可以用 min convolution 的方法從 O(k2) 降低到 O(k) ,而且，對于一些特殊的graph，例如grid，計算belief隻需要一半的message update就可以，而且這樣隻需要計算特定位置的message，還可以減少存儲message所需要的記憶體.還有就是可以用一種coarse-to-fine 的方式進行message更新，使得疊代次數也可以減少。 

1.降低計算Message的複雜性 

首先，可以講Message的計算公式重新寫成 

mtp→q(fq)=minfp(V(fp−fq)+h(fp))

這裡， h(fp)=Dp(fp)+∑mt−1s→p(fp)  

這樣把含有 fq 的項拿了出來，這個形式和圖像的卷積公式有點類似，不過這裡兩個函數之間是加号，而卷積是乘法，這裡外面是求最小值，是以這個式子一般叫 min convolution ，但是這樣如何能夠做到 O(k) 的複雜度呢？主要是考慮CV裡面pariwise label cost的特殊結構，具體可以先看下面幾個例子： 

首先是最簡單的例子，Potts Model, 

Potts Model的一般形式 

V(x)={0dif x=0otherwise

由于pairwise label cost隻有兩種可能,這樣的話我們就可以隻用一次最小化函數， 

mtp→q(fq)=min(h(fq),minfp(h(fp))+d)

到這裡就很明顯了，裡面有一個 O(k) 的操作求 minfp(h(fp)) ，但是這個在每次求 fq 的message中是個定值，是以隻需要算一次就好，用不着每次循環都計算，是以最終的複雜性仍然是 O(k) ，另外不同的節點之間cost不同其複雜度也是 O(k) 的。 

第二種情況是線性模型的cost，假設pairwise cost是根據label不同有不同的值， 

V(x)=min(c|x|,d)

取 d 和 c|x| 之間的最小值，設定一個上屆 d 主要是為了保證discontimuity preserving. 

為了證明是如何保持複雜度 O(k) 的,先考慮一個簡單的情況，label cost沒有被截斷的時候， 

mtp→q(fq)=minfp(c|fp−fq|+h(fp))

這個式子該怎麼看呢，【2】的作者給了一個很好的思考角度。為了友善了解我們先看裡面， c|fp−fq|+h(fp) ,這明顯就是一個二維的錐形，斜率是c，不過是平移到了點 (fp,h(fp)) ， mtp→q(fq) 就是在所有的這些k個平移了的錐形裡面取在 fq 位置的下屆，用一個圖可以很好的表示 

那麼 mtp→q 這個向量就是從位置0到 k−1 所有錐形的下屆組成的向量，可以用上圖的最小面的粗線在0,1,2,3位置的值表示，但是這個值應該怎麼用 O(k) 的算法求出來呢，因為我們仍然有k個錐形和k個位置要比較最小值。 

這裡用了兩個循環，首先把 h(fq) 指派給 mtp→q(fq) ,這是每個錐形的最小值，而且随之向兩邊伸展，每一個機關高度增加一個c，但是這個錐形的最小值并不是消息的值，消息的值有兩個可能，一個是本身錐底位于該位置的錐底的值，另一個就是其它所有錐在該位置的值， 

是以我們需要兩層傳播，第一次可以從做往右，把前面的錐在後面每個位置的最小值一次傳遞過去，我們隻需記錄該位置的最小值 m(fq) ，後面位置的最小值，要麼是錐底在 fq+1 的錐底的值，要麼和 m(fq) 在同一個錐上，值為 m(fq)+c ， 

是以兩次循環為 

for fq from 1 to k−1m(fq)←min(m(fq),m(fq−1)+c)

第二次循環把右邊的資訊更新到前面 

for fq from k−2 to 0m(fq)←min(m(fq),m(fq+1)+c)

在圖上的例子裡面，初始值是(3,1,4,6),c=1,第一次前向循環，(3,1,2,2),第二次後向循環，(2,1,2,2) 

然後對于截斷的Potts Model， m′(fq) 是兩次循環得到的message 

m(fq)=min(m′(fq),minfph(fp)+d)

參考： 

【1】http://wenku.baidu.com/view/0483de18a76e58fafab00384.html 

【2】Efficient Belief propagation for Early Vision