題圖為SGM算法的一個處理結果。

最近來看看一些雙目稠密匹配的算法。說來慚愧，SGM在航測領域是很重要的算法（當然也是最好的雙目稠密匹配算法之一），自己卻沒有認真讀過，只是大致有些了解。

看了論文，再結合網上一些資料，自己做了些論文筆記。

想到關于SGM論文網上還沒看到比較翔實的博客，就把自己做的筆記再加些解釋分享出來了（下文中的引用部分多為我自己的思考）。

其中還有一些是自己不理解的地方，準備后續寫代碼時研究。

也希望大家可以分享自己的見解，或對文章內容進行批評指正。

由于是論文筆記，所以有些中英夾雜，而且有些想想也不好翻譯，就不再改了。閑話少說，直接來看論文吧。

基礎

雙目圖像稠密匹配的4個基本步驟為：

Matching cost computation;

Cost aggregation: connects the matching cost within a certain neighborhood;

Disparity computation: selects the disparity with the lowest matching cost;

Disparity refinement: removing peaks,

interpolating gaps or increasing the accuracy by sub-pixel interpolation.

這4個都比較好理解，SGM論文也是按照這樣來組織的。

下面就按照論文的順序來詳細了解下SGM算法。

中心思想及要求

idea: 使用MI (Mutual Information) 來進行單像素匹配 + 多個一維平滑約束（來擬二維約束）來進行“全局”優化。

前提: 已知立體像對間的對極幾何關系。

Pixelwise cost calculation

SGM算法不用圖像塊進行匹配，只考慮當前像素。因為利用圖像塊進行匹配對應的隱性約束為塊內像素的視差是相同的，而這在深度變化（物體邊界）的地方是不成立的。

互信息（MI）：defined from the entropy（熵）of two images:

上式針對整張圖像而非單個像素，不能用作 cost。因此，對于一張圖像的聯合熵，有其他論文利用泰勒展開計算：

其中，公式內第一項為像素 p 的灰度值，第二項為匹配像素的灰度值。

這里，聯合熵被簡化為左圖所有像素點（及其對應點）的 h(i1,i2) 之和。

可以看到，由于極線矯正后左右圖十分相似，所以得到的聯合分布直方圖類似于一個對角矩陣。

以上計算并不包含被遮擋的像素（如何得知哪些像素是被遮擋的？）。因此，為了避免包含遮擋像素，建議將熵也這么計算：

此外，以上計算也只針對兩張圖像的重疊部分。

因此，一維直方圖也可以這么計算：

h(i) 即為 P(I1, I2) 第 i 行（列）像素之和。

最終，互信息的定義為

對于像素點 p，若取其視差為 d，則對應的 cost 為：

問題：想要對匹配圖像 Im 進行視差矯正就需要視差圖。

但我們的目標就是獲取視差圖。

解決：

迭代法：start with a random disparity map for calculating Cmi. And use the cost for matching and calculating a new disparity map.

論文表示大致迭代3次就可以了。

層次法：recursively use the up-scaled disparity map (half resolution). Start with a random disparity map of 1/16 resolution. 在這個1/16的視差圖上重復計算3次（每次迭代3次，然后每放大一倍迭代3次計算出新的視差圖。

Aggregation of costs

以上就是論文進行匹配的第一步。接下來就要進行一個“全局”上的優化。

pixelwise matching 還是不夠穩定，因此需要加上一些約束來保持同一平面的像素具有相同的視差并懲罰鄰域內視差不連續的像素（即平滑）。

所以最小化如下能量方程：

上式第一項為所有 MI cost 的和；

第二項對 像素p的鄰域內出現視差與p的視差相差1 的像素 加上一個懲罰項P1；

第二項對 視差相差大于1 的像素加入更大的懲罰P2.

作用：對于小的視差相差使用較小的懲罰以適應斜面或曲面；

對大的視差相差使用大的懲罰來防止深度（視差）不連續。

問題在于全局最小化 E(D) 是一個 NP 完全問題，很難解算。

單行（1D）約束可以利用動態規劃達到多項式時間。

因此很自然地想到優化多個單行的約束條件來擬合2D優化，作者建議至少要選擇待優化像素的8個方向。

The aggregated smoothed cost S(p, d) for a pixel p and disparity d is calculated by summing the costs of all 1D minimum cost paths that end in pixel p at disparity d.（也就是說S是所有L之和。）

考慮到上述代價最后可能非常大，可將之修改為：

注意到被減項對于該方向上，像素 p 的任意視差都是一個常數（上一個像素的視差及其對應的最小cost已經計算好）。

最終，對于像素 p，選擇視差 d 的cost 就是：

S(p,d)=∑rLr(p,d)

選擇使 S(p, d) 最小的視差d. 若要到亞像素精度，可以利用 neighboring costs 來擬合一個二次曲線。

Multi-baseline matching

對左圖計算完視差圖后，還可以以同樣的方法來對右圖進行視差圖的計算，在將二者融合起來。也可以利用多個立體像對來計算多張稠密視差圖。

問題：areas which are not seen by all images will become invalid.

解決：取多視差圖的并集而非交集。

對于左圖來說，它的視差圖是恒定值（參考依據視差計算深度的公式），因此可以通過多圖匹配來優化。

對左圖計算一個視差圖后，也可對右圖計算一個視差圖。然后進行一致性校驗：

如此，確保 one to one mapping (uniqueness constrain).

Disparity Refinement

之后，是對所得的視差圖進行優化處理。個人覺得這是雙目稠密匹配很重要的一步，因為對于很多算法，其得到的視差圖之間的差別并不會特別大。

重要的是對所得的視差圖進行后處理，提高深度計算的精度。

移除極值

采用聯通域分割法，將視差相差在1個像素以內的像素4鄰域歸為一個聯通域來分割所得的視差圖。

根據場景事先確定一個大小閾值，去除像素數量過少的聯通域。

Intensity Consistent Disparity Check

這步是SGM后處理比較核心的一步。

室內場景的前后景之間會有視差不連續。

但前述的能量方程對于發生視差不連續的位置沒有偏好，這種不連續可能在錯誤的地方出現，因此會造成錯誤的前后景物體邊界，或者一個斜面。

先前的將像素梯度與懲罰值P2關聯可以部分解決該問題。

但在一些視差不連續的不對稱的情況（如前景物體沒有完全出現，只在出現的一邊產生視差不連續）下可能失敗（原因待解）。

室內環境中，后景常常為無紋理區域，如墻等。為解決這個問題，先提出以下三個假設：

無紋理區域內部沒有視差不連續現象（即視差變化伴會隨梯度變化）；

無紋理區域包含一些弱紋理（否則也無法進行像素匹配）；

無紋理區域的表面可以用一個平面表示（參考1，如此則區域內視差恒定。否則為兩個可以分割開的區域）。

解決步驟：先對圖像進行分割，得到前后景區域。問題就變為如何正確選擇后景（無紋理區域）的邊界和視差，較好的分割出前景物體。

利用 fixed bandwidth Mean Shift Segmentation 方法分割原始圖像，得到各個無紋理區域（假設1），忽略過小區域，所得區域表示為 Si。

利用聯通域分割法分割步驟1得到的無紋理區域（假設2），忽略過小區域，所得分割區域表示為 Sik；

針對2得到的區域擬合平面 Fik （假設3）。將得到的各個可能平面推廣到所在的整個無紋理區域，取能量方程最小的平面。

遮擋判斷子步驟：對于像素p，若其匹配像素q有了另一個匹配，且新的匹配像素的視差大于像素p，則像素p認為被遮擋；

該無紋理區域內的視差都替換為最佳擬合平面所對應的視差；

Discontinuity Preserving Interpolating

后處理完的視差圖可能因為遮擋或誤匹配而存在缺失區域。對這些區域的視差進行插值前要對其性質進行分類，以使用不同的插值方法：

遮擋：用背景的視差進行外插值，而不使用前面的遮擋物的視差；

誤匹配：可以利用其周圍像素進行內插值。

注意：對與遮擋相連的誤匹配區域，同樣利用背景像素進行外插值。

區分：由于遮擋會照成視差不連續。被遮擋位置的像素的極線不與disparity function（即視差隨位置變化的方程）相交；誤匹配像素則相反。

如上圖，點p1處就是因為遮擋而造成點缺失；而點p2則是因為誤匹配。

插值仍然是從像素周圍的8個方向計算出8個可能的視差值，然后

該式的第一項是選擇待選視差中第二小 (second lowest) 的視差。第二項為選擇待選視差的中值，這樣有利于在物體邊界處保持視差不連續。

該插值方法獨立于立體相對匹配算法。

最后可以再用中值濾波對得到的視差圖進行去噪處理。

最后，作者還介紹了對于超大幅的航空影像進行分塊處理的方法和加速技巧.

以及解釋了文章中不先對右影像整張影像進行極線矯正的原因（對于推掃式的航空/航天影像，其極線為曲線，因此無法進行矯正，只能實時計算）。

但對于其他普通立體像對，這些內容都是不必要的，就不再解釋了。

審核編輯：湯梓紅