題圖為SGM算法的一個(gè)處理結(jié)果。

最近來(lái)看看一些雙目稠密匹配的算法。說(shuō)來(lái)慚愧，SGM在航測(cè)領(lǐng)域是很重要的算法（當(dāng)然也是最好的雙目稠密匹配算法之一），自己卻沒(méi)有認(rèn)真讀過(guò)，只是大致有些了解。

看了論文，再結(jié)合網(wǎng)上一些資料，自己做了些論文筆記。

想到關(guān)于SGM論文網(wǎng)上還沒(méi)看到比較翔實(shí)的博客，就把自己做的筆記再加些解釋分享出來(lái)了（下文中的引用部分多為我自己的思考）。

其中還有一些是自己不理解的地方，準(zhǔn)備后續(xù)寫(xiě)代碼時(shí)研究。

也希望大家可以分享自己的見(jiàn)解，或?qū)ξ恼聝?nèi)容進(jìn)行批評(píng)指正。

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

基礎(chǔ)

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

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個(gè)都比較好理解，SGM論文也是按照這樣來(lái)組織的。

下面就按照論文的順序來(lái)詳細(xì)了解下SGM算法。

中心思想及要求

idea: 使用MI (Mutual Information) 來(lái)進(jìn)行單像素匹配 + 多個(gè)一維平滑約束（來(lái)擬二維約束）來(lái)進(jìn)行“全局”優(yōu)化。

前提: 已知立體像對(duì)間的對(duì)極幾何關(guān)系。

Pixelwise cost calculation

SGM算法不用圖像塊進(jìn)行匹配，只考慮當(dāng)前像素。因?yàn)槔脠D像塊進(jìn)行匹配對(duì)應(yīng)的隱性約束為塊內(nèi)像素的視差是相同的，而這在深度變化（物體邊界）的地方是不成立的。

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

上式針對(duì)整張圖像而非單個(gè)像素，不能用作 cost。因此，對(duì)于一張圖像的聯(lián)合熵，有其他論文利用泰勒展開(kāi)計(jì)算：

其中，公式內(nèi)第一項(xiàng)為像素 p 的灰度值，第二項(xiàng)為匹配像素的灰度值。

這里，聯(lián)合熵被簡(jiǎn)化為左圖所有像素點(diǎn)（及其對(duì)應(yīng)點(diǎn)）的 h(i1,i2) 之和。

可以看到，由于極線(xiàn)矯正后左右圖十分相似，所以得到的聯(lián)合分布直方圖類(lèi)似于一個(gè)對(duì)角矩陣。

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

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

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

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

最終，互信息的定義為

對(duì)于像素點(diǎn) p，若取其視差為 d，則對(duì)應(yīng)的 cost 為：

問(wèn)題：想要對(duì)匹配圖像 Im 進(jìn)行視差矯正就需要視差圖。

但我們的目標(biāo)就是獲取視差圖。

解決：

迭代法：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. 在這個(gè)1/16的視差圖上重復(fù)計(jì)算3次（每次迭代3次，然后每放大一倍迭代3次計(jì)算出新的視差圖。

Aggregation of costs

以上就是論文進(jìn)行匹配的第一步。接下來(lái)就要進(jìn)行一個(gè)“全局”上的優(yōu)化。

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

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

上式第一項(xiàng)為所有 MI cost 的和；

第二項(xiàng)對(duì) 像素p的鄰域內(nèi)出現(xiàn)視差與p的視差相差1 的像素 加上一個(gè)懲罰項(xiàng)P1；

第二項(xiàng)對(duì) 視差相差大于1 的像素加入更大的懲罰P2.

作用：對(duì)于小的視差相差使用較小的懲罰以適應(yīng)斜面或曲面；

對(duì)大的視差相差使用大的懲罰來(lái)防止深度（視差）不連續(xù)。

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

單行（1D）約束可以利用動(dòng)態(tài)規(guī)劃達(dá)到多項(xiàng)式時(shí)間。

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

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.（也就是說(shuō)S是所有L之和。）

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

注意到被減項(xiàng)對(duì)于該方向上，像素 p 的任意視差都是一個(gè)常數(shù)（上一個(gè)像素的視差及其對(duì)應(yīng)的最小cost已經(jīng)計(jì)算好）。

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

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

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

Multi-baseline matching

對(duì)左圖計(jì)算完視差圖后，還可以以同樣的方法來(lái)對(duì)右圖進(jìn)行視差圖的計(jì)算，在將二者融合起來(lái)。也可以利用多個(gè)立體像對(duì)來(lái)計(jì)算多張稠密視差圖。

問(wèn)題：areas which are not seen by all images will become invalid.

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

對(duì)于左圖來(lái)說(shuō)，它的視差圖是恒定值（參考依據(jù)視差計(jì)算深度的公式），因此可以通過(guò)多圖匹配來(lái)優(yōu)化。

對(duì)左圖計(jì)算一個(gè)視差圖后，也可對(duì)右圖計(jì)算一個(gè)視差圖。然后進(jìn)行一致性校驗(yàn)：

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

Disparity Refinement

之后，是對(duì)所得的視差圖進(jìn)行優(yōu)化處理。個(gè)人覺(jué)得這是雙目稠密匹配很重要的一步，因?yàn)閷?duì)于很多算法，其得到的視差圖之間的差別并不會(huì)特別大。

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

移除極值

采用聯(lián)通域分割法，將視差相差在1個(gè)像素以?xún)?nèi)的像素4鄰域歸為一個(gè)聯(lián)通域來(lái)分割所得的視差圖。

根據(jù)場(chǎng)景事先確定一個(gè)大小閾值，去除像素?cái)?shù)量過(guò)少的聯(lián)通域。

Intensity Consistent Disparity Check

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

室內(nèi)場(chǎng)景的前后景之間會(huì)有視差不連續(xù)。

但前述的能量方程對(duì)于發(fā)生視差不連續(xù)的位置沒(méi)有偏好，這種不連續(xù)可能在錯(cuò)誤的地方出現(xiàn)，因此會(huì)造成錯(cuò)誤的前后景物體邊界，或者一個(gè)斜面。

先前的將像素梯度與懲罰值P2關(guān)聯(lián)可以部分解決該問(wèn)題。

但在一些視差不連續(xù)的不對(duì)稱(chēng)的情況（如前景物體沒(méi)有完全出現(xiàn)，只在出現(xiàn)的一邊產(chǎn)生視差不連續(xù)）下可能失敗（原因待解）。

室內(nèi)環(huán)境中，后景常常為無(wú)紋理區(qū)域，如墻等。為解決這個(gè)問(wèn)題，先提出以下三個(gè)假設(shè)：

無(wú)紋理區(qū)域內(nèi)部沒(méi)有視差不連續(xù)現(xiàn)象（即視差變化伴會(huì)隨梯度變化）；

無(wú)紋理區(qū)域包含一些弱紋理（否則也無(wú)法進(jìn)行像素匹配）；

無(wú)紋理區(qū)域的表面可以用一個(gè)平面表示（參考1，如此則區(qū)域內(nèi)視差恒定。否則為兩個(gè)可以分割開(kāi)的區(qū)域）。

解決步驟：先對(duì)圖像進(jìn)行分割，得到前后景區(qū)域。問(wèn)題就變?yōu)槿绾握_選擇后景（無(wú)紋理區(qū)域）的邊界和視差，較好的分割出前景物體。

利用 fixed bandwidth Mean Shift Segmentation 方法分割原始圖像，得到各個(gè)無(wú)紋理區(qū)域（假設(shè)1），忽略過(guò)小區(qū)域，所得區(qū)域表示為 Si。

利用聯(lián)通域分割法分割步驟1得到的無(wú)紋理區(qū)域（假設(shè)2），忽略過(guò)小區(qū)域，所得分割區(qū)域表示為 Sik；

針對(duì)2得到的區(qū)域擬合平面 Fik （假設(shè)3）。將得到的各個(gè)可能平面推廣到所在的整個(gè)無(wú)紋理區(qū)域，取能量方程最小的平面。

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

該無(wú)紋理區(qū)域內(nèi)的視差都替換為最佳擬合平面所對(duì)應(yīng)的視差；

Discontinuity Preserving Interpolating

后處理完的視差圖可能因?yàn)檎趽趸蛘`匹配而存在缺失區(qū)域。對(duì)這些區(qū)域的視差進(jìn)行插值前要對(duì)其性質(zhì)進(jìn)行分類(lèi)，以使用不同的插值方法：

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

誤匹配：可以利用其周?chē)袼剡M(jìn)行內(nèi)插值。

注意：對(duì)與遮擋相連的誤匹配區(qū)域，同樣利用背景像素進(jìn)行外插值。

區(qū)分：由于遮擋會(huì)照成視差不連續(xù)。被遮擋位置的像素的極線(xiàn)不與disparity function（即視差隨位置變化的方程）相交；誤匹配像素則相反。

如上圖，點(diǎn)p1處就是因?yàn)檎趽醵斐牲c(diǎn)缺失；而點(diǎn)p2則是因?yàn)檎`匹配。

插值仍然是從像素周?chē)?個(gè)方向計(jì)算出8個(gè)可能的視差值，然后

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

該插值方法獨(dú)立于立體相對(duì)匹配算法。

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

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

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

但對(duì)于其他普通立體像對(duì)，這些內(nèi)容都是不必要的，就不再解釋了。

審核編輯：湯梓紅