SGM算法源于《Stereo Processing by Semi-Global Matching and Mutual Information》一文，我認為這篇文章是立體比對算法中最給力的，放眼KITTI，可以發現目前排名前五十的算法幾乎一半都是對SGM的改進，具有最強的實用價值。SGM中文名稱“半全局比對”，顧名思義，其介于局部算法和全局算法之間，所謂半全局指的是算法既沒有隻考慮像素的局部區域，也沒有考慮所有的像素點。例如，BM計算某一點視差的時候，往往根據目标像素周圍的矩形區域進行代價聚合計算；DoubleBP在計算目的像素視差的時候，考慮的則是圖像所有的像素點。抛開具體的方法不說，SGM中考慮到的隻有非遮擋點，這正是定義為半全局的原因。
(轉載請注明：http://blog.csdn.net/wsj998689aa/article/details/49464017, 作者：迷霧forest)
有的童鞋這時可能會想到Non-Local，為啥它要叫“非局部”，難道也是一種半全局算法？我認為不是，NLCA的目的是建構代價聚合項，它沒有能量函數建構優化過程，而建構代價聚合基本上是局部算法才要做的事情，然而基于的卻是所有的像素點，是以被稱為非局部，并且NLCA和SGM的套路也完全不同。
我總是喜歡在部落格開頭扯一點之前寫過的算法，回歸正題，SGM的文獻比較晦澀，作者Heiko Hirschmuller進行了大篇幅的論述，其中涉及到了很多的細節，最開始讀這篇文獻的時候我完全不了解算法的細節，但是SGM又經典的不行，沒辦法隻能在反複了解論文的同時，結合代碼進行了解。這篇文章主要涉及三個部分：分層互資訊的代價計算+基于動态規劃的代價聚合+其他，我打算分别基于這三個部分寫三篇部落格，與童鞋們分享我對SGM的了解。
和所有的立體比對算法一樣，SGM的第一步也是代價計算，它采用了基于互資訊的計算方法，互資訊是一種熵。那我們就先說說熵，熵是用來表征随機變量的不确定性（可以了解為變量的資訊量），不确定性越強那麼熵的值越大（最大為1），那麼圖像的熵其實就代表圖像的資訊量。互資訊度量的是兩個随機變量之間的相關性，相關性越大，那麼互資訊就越大。可以想想看，兩幅圖像如果比對程度非常高，說明這兩幅圖像相關性大還是小？顯然是大，知道一幅圖像，另外一幅圖像馬上就知道了，相關性已經不能再大了！！！反之，如果兩幅圖像配準程度很低，那麼兩幅圖像的互資訊就會非常小。是以，立體比對的目的當然就是互資訊最大化。這就是為什麼使用互資訊的原因。熵和互資訊的定義分别如下所示：
其中，互資訊的前兩項是圖像的熵，最後一項叫做聯合熵，聯合熵是熵的變種，其依賴的自然是聯合機率分布（熵依賴的是機率分布），聯合熵的公式如下所示：
這時，一個最自然的問題是，圖像的機率分布P是什麼意思？答案一句話，圖像的灰階直方圖。圖像的灰階值是0~255，每個灰階值對應的像素個數除以圖像像素個數就是該灰階值對應的機率，單幅圖像的機率密度是一維的，那麼自然地，兩幅圖像的聯合機率密度就是二維的，它的定義域取值就是（0，0）~（255，255），公式如下所示：
其中，（i，k）指的是像素灰階值對，I1和I2分别代表了左圖和矯正之後的右圖，p代表像素點，n代表着像素的總數，公式的含義是統計不同灰階值對的個數并歸一化。是以，兩幅圖像對應的機率分布可以用一幅圖表示，這幅圖的大小一定是256*256，弄清楚這點很重要，我之前一直誤以為上述公式中的（i，k）指的是像素坐标，其實上面的公式隻想告訴我們一件事情：聯合機率分布就是歸一化之後的統計直方圖。
弄清楚了P的含義，就可以進一步說說熵的構造了，作者先說了聯合熵的定義，在這裡作者引用了其他文獻的研究成果，直接用泰勒展開近似聯合熵為像素和的形式，如下所示：
其中，作者稱h為資料項，注意看它的自變量是像素灰階值，是以可以事先建立一個查表，将每個灰階值對的h值都儲存下來（一共有256*256），那麼聯合熵的計算速度就會很快，h的計算公式如下所示：
其中，g(i,k)指的是高斯平滑，正如前面所說，P是一幅表征機率值的圖像（分辨率恒為256*256），正是針對這幅圖像進行平滑處理，但是作者卻在這裡稱之為Parzen估計，我想來想去覺得是一個意思，Parzen估計是一種非參數估計方法，不需要事先假設數學模型的參數形式而直接估計單點的機率值，最常用的Parzen窗函數就是高斯核函數。作者提供了一個圖示也可以說明這個問題：
其中，第一個坐标系就是聯合機率分布圖，由于事先要對比對圖像（一般是右圖）基于視差圖進行修正（warp），調整右圖像素的位置，使得左右兩圖盡可能相同之後計算同一像素位置的聯合機率，由此導緻了諸如（10,10）、（25,25）、（125,125）這樣的灰階值對的機率值更大一些。再對這樣的圖像進行7*7視窗大小的高斯平滑處理，高斯平滑的目的是消除噪音，因為這裡基于的視差圖是很粗糙的（隻有非遮擋點才有視內插補點，遮擋點的視差都為0），根據這樣的視差圖對右圖進行處理，難免一些位置所對應的兩圖灰階值不相等，展現在P圖上就是噪音，這個時候當然要平滑。例如可能有（10,100）這樣的灰階值對出現，這說明右圖該點經過warp之後很可能是錯誤的，但是這種情況肯定是少數，對應的機率值也就是很小，展現在P圖上就是一個噪音點，用高斯平滑處理，一下子就沒了。其實這就是檢測outlier，去除outlier的另外一種手段，隻不過SGM是從機率分布的角度處理罷了，而其他的算法一般都是從空間分布來處理outlier。進一步，取負對數便得到了h值的圖示，最後得到了圖像的聯合熵圖。
其實，平滑歸平滑，也隻是基于256*256的圖像進行平滑，隻需根據像素位置計算出權重即可，同樣可以根據查表的方式實作，這和具體的雙目圖像大小仍舊無關，一個不小的優點哦！
作者為什麼要用互資訊來計算代價比對值？根據文獻給出的資訊，作者是考慮到了互資訊對光照具有魯棒性，我們注意看下面的公式，這個計算方式很有意思，我們已經得到了互資訊圖，剩下要做的事情隻是根據左圖和右圖挑選出來的像素點的灰階值對，在互資訊圖中直接查找就行（又是一個速度優勢），注意：要取個負号，這點直覺上很好了解，互資訊越大->相關性越大->兩個點的比對程度越高->代價計算值理應越小，童鞋們千萬不要忘記WTA是怎麼運作的啊！！！！
大家有沒有覺得作者在此處的思維很是特别？先根據一個視差圖作為先驗來确定互資訊圖，然後基于這樣的互資訊圖去計算各個視差的代價，這在理論上顯然會導緻第一步得到的視差圖非常近似于初始視差圖！！！難怪作者花了大篇幅介紹HMI，但是卻沒有給出中間結果。好比是法官審判一個殺人罪犯，他的判罰依據竟然是另一個搶劫罪犯的判罰結果，而不是根據其他殺人罪犯的判罰結果。此處我覺得有點怪，拿出來說說，大家都想想看哈。
本來熵和聯合熵的計算方法不同，但是由于遮擋點的問題，将二者都設定為相同，都采用泰勒近似的方式。具體來說，圖像的熵是基于圖像的機率分布來計算的，但由于遮擋點的存在，有些像素根本就不會有比對點，如果也将這樣的像素考慮在内恐怕不合适，别忘了我們的目的是令能夠比對的點盡量比對，不能比對的點我們根本就沒必要讓它們比對，于是将目光放在了聯合熵的定義上，聯合熵是基于聯合機率分布的，其基于的點可以保證都是比對點，這樣的機率公式如下所示：
進一步，基于這樣的機率分布得到的圖像熵公式如下所示：
最後，作者采用分層互資訊（HMI）進行代價比對計算，由于機率分布圖和圖像大小無關（一直都是256*256），是以可以采用分層計算的方式來加速（反正不同層都是256*256），每一層的計算對應一次疊代，别忘記首次疊代需要基于視差圖對右圖進行warp，沒有視差圖怎麼辦？文章裡面說是随機生成就好，并且由于像素個數很多，随機生成的個别錯誤可以被容忍，warp之後的右圖和左圖的比對程度還是會比較高，疊代次數也相對較低，這也是SGM的一大優點。
作者還對HMI的時間複雜度進行了計算，由于單次疊代的時間複雜度是O(WHD)，每次下采樣都會令三個參數同時減半，是以上次疊代将會是目前疊代速度的1/8，假設我們有4次疊代，那麼相比較于BT算法，隻比它慢了14%，注意，算法首次疊代使用的是最小的視差圖，并且乘以3的原因是随機生成的視差圖十分不靠譜，需要反複疊代3次才能得到同樣分辨率下的靠譜視差圖，然後再參與後續高分辨率的計算。
總結：HMI是SGM的重要一步驟，通過HMI計算得到的代價比對值對光照魯棒，一旦這步做好了，後續的代價聚合，疊代求精等等操作弄起來就輕松多了。
後記：今天回答了關于這篇文章的幾位朋友的提問，又重新看了HMI這部分内容，其實HMI的計算過程我雖然進行了解釋，但是仍舊有兩個核心問題沒有明确說明，這兩個問題是:
1. 對互資訊基于泰勒展開進行近似計算的具體過程是什麼？
2. 聯合熵中的兩個卷積是根據泰勒展開得到的，還是故意加上的？
因為此部分内容涉及到公式推理，在《Visual Correspondence Using Energy Minimization and Mutual Information》一文中有比較詳細的推理過程，感興趣的朋友可以去仔細看看，本文中就不詳細說明了，希望和大家繼續探讨。