原理+代碼詳解 | 稠密重建之SGM/tSGM算法

2021-04-28 16:14 作者:計算機(jī)視覺life 0人讀過 | 我要投稿

注：本文來自計算機(jī)視覺life獨(dú)家課程?視覺三維重建：原理剖析+逐行代碼詳解?中的課件及注釋代碼。

目錄：

立體匹配算法介紹?

SGM算法?

tSGM算法?

SGM/tSGM代碼實(shí)現(xiàn)

立體匹配算法介紹

全局立體匹配算法

全局立體匹配算法主要是采用了全局的優(yōu)化理論方法估計視差，建立全局能量函數(shù)，通過最小化全局能量函數(shù)得到最優(yōu)視差值；
通過二維相鄰像素視差之間的約束（如平滑性約束）而得到更好的匹配效果，但是對內(nèi)存的占用量大，速度慢不適合實(shí)時運(yùn)行。主要的算法有圖割（graph cuts）、信念傳播（belief propagation）、動態(tài)規(guī)劃等算法。

局部立體匹配算法

主要是采用局部優(yōu)化方法進(jìn)行視差值估計，局部立體匹配算法有 SAD，SSD 等算法，與全局立體匹配算法一樣，也是通過能量最小化方法進(jìn)行視差估計，但是在能量函數(shù)中，只有數(shù)據(jù)項(xiàng)，而沒有平滑項(xiàng)；
該算法由于每個像素計算互不干擾可以并行計算，所以可以實(shí)時。但由于所基于的局部窗口視差相同的假設(shè)在很多情況下并不成立導(dǎo)致匹配效果較差。

半全局立體匹配算法SGM

綜合上述局部和全局算法的優(yōu)缺點(diǎn)，半全局算法依舊采用全局框架，但是在計算能量函數(shù)最小化的步驟時使用高效率的一維路徑聚合方法來代替全局算法中的二維最小化算法，使用一維最優(yōu)來近似二維最優(yōu)，得到的視差圖在效果上和全局算法沒有太大的差別，但是算法效率卻有非常大的提升。

SGM算法

參考文獻(xiàn)：

[1]Stereo Processing by Semi-global Matching and Mutual Information
[2]SURE: Photogrammetric Surface Reconstruction from Imagery

SGM算法詳細(xì)介紹

匹配代價計算

文獻(xiàn)[1]中介紹的SGM的代價計算是基于互信息（Mutual Information，MI）的匹配測度計算算法來計算匹配代價，互信息是一種對影像明暗變化不敏感的相關(guān)性測度。但由于原理復(fù)雜且計算需要迭代效率比較低，在實(shí)際應(yīng)用中，更簡單有效的方法如Census變換，故在此不再介紹MI。
Census變換：

使用像素鄰域內(nèi)的局部灰度差異將像素灰度轉(zhuǎn)換為比特串即為census值；
基于Census變換的匹配代價計算方法是計算左右影像對應(yīng)的兩個像素的Census變換值的漢明（Hamming）距離（兩個比特串的對應(yīng)位不相同的數(shù)量：先進(jìn)行異或運(yùn)算，再統(tǒng)計運(yùn)算結(jié)果中1的個數(shù)）

代價聚合

采用全局立體匹配算法，即找到每個像素的最優(yōu)視差使得整體能量最小。能量方程如下：

$%0Aenergy(X%2CD)%3D%5Csum_%7Bi%7DDataCost(d_i%2Cx_i)%2B%5Csum_%7Bj%3Dneighbor(i)%7DSmoothCost(x_i%2Cx_j)%0A%09%09%09%09%09$

式中， $C$ 為匹配代價，第二項(xiàng)和第三項(xiàng)是平滑項(xiàng)，我們期望的是視差是連續(xù)的。所以如果當(dāng)前像素 $x_b$ 與鄰域像素 $x_N$ 視差相差比較?。?個像素）我們會給一個比較小的懲罰 $P_1$ ,如果大于一個像素則給一個大的懲罰 $P_2$ 。但是實(shí)際場景中肯定會有一些視差不連續(xù)區(qū)域相差比較大（比如：前景和背景）如圖示：

為了處理這種情況，我們對 $P_2$ 進(jìn)行調(diào)整：

$P_2%3DP%5E%7B'%7D_2*(1%2B%CE%B1*e%5E%7B(-(I_%7Bx_b%7D-I_%7Bx_N%7D)%5E%7B2%7D%2F(2*%5Cbeta%5E%7B2%7D))%7D)$

思考：為什么這樣調(diào)整第二個懲罰項(xiàng)？

答案：如果像素和它的鄰域像素亮度差很大，那么該像素很可能是位于視差非連續(xù)區(qū)域，則一定程度上允許其和鄰域像素的視差差值超過1個像素，對于超過1個像素的懲罰力度就適當(dāng)減小一點(diǎn)。

具體求解過程中，SGM路徑代價聚合的思路：

將像素所有視差下的匹配代價進(jìn)行像素周圍所有路徑上的一維聚合得到路徑下的路徑代價值，然后將所有路徑代價值相加得到該像素聚合后的匹配代價值。

一維聚合路徑示意圖（圖中各個箭頭方向就是聚合各個路徑）：

某一維路徑代價計算公式如下：

$%5Cbegin%7Baligned%7D%0AL_%7B%5Cmathbf%7Br%7D_%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D%2C%20d%5Cright)%3D%26%20C%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D%2C%20d%5Cright)%2B%5Cmin%20%5Cleft(L_%7Br%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D-%5Cmathbf%7Br%7D_%7Bi%7D%2C%20d%5Cright)%2C%5Cright.%5C%5C%0A%26%20L_%7B%5Cmathbf%7Br%7D_%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D-%5Cmathbf%7Br%7D_%7Bi%7D%2C%20d-1%5Cright)%2BP_%7B1%7D%2C%20%5C%5C%0A%26%20L_%7B%5Cmathbf%7Br%7D_%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D-%5Cmathbf%7Br%7D_%7Bi%7D%2C%20d%2B1%5Cright)%2BP_%7B1%7D%2C%20%5C%5C%0A%26%5Cleft.L_%7B%5Cmathbf%7Br%7D_%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D-%5Cmathbf%7Br%7D_%7Bi%7D%2C%20i%5Cright)%2BP_%7B2%7D%5Cright)%20%5C%5C%0A-%26%20%5Cmin%20_%7Bk%7D%20L_%7Br%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D-%5Cmathbf%7Br%7D_%7Bi%7D%2C%20k%5Cright)%0A%5Cend%7Baligned%7D$

式子中 $L%7B%5Cmathbf%7Br%7D%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D%7Bb%7D%2C%20d%5Cright)%3CC%7Bmax%7D(x_b%2Cd)%2BP_2$

則最終代價值（所有路徑之和）：

$S(x_b%2Cd)%3D%5Csum_%7Br_i%7DL_%7B%5Cmathbf%7Br%7D_%7Bi%7D%7D%5Cleft(%5Cmathbf%7Bx%7D_%7Bb%7D%2C%20d%5Cright)$

視差計算
代價聚合后，每個像素直接找聚合代價最小對應(yīng)的視差值就是我們所要求的視差值。
視差優(yōu)化

視差一致性檢查
將左右圖互換，得到R-L視差圖。與L-R視差圖對比，根據(jù)左圖的視差找到在右圖中的對應(yīng)視差，如果兩者小于閾值則認(rèn)為是準(zhǔn)確的，反之是錯的把該值剔除。如下圖：

亞像素計算
上述計算的視差圖是像素級別的，在實(shí)際使用中精度是無法滿足需求的。SGM通過在上述計算的最小代價的視差層附近進(jìn)行插值找到亞像素級的精度。如下圖：

tSGM算法

與SGM基本相同，區(qū)別主要是在代價聚合的時候：

使用金字塔圖像計算視差（由粗糙到精細(xì)即從低分辨率到高分辨率計算匹配代價）
每個像素的視差范圍都不同，只在真值附近搜索大大減少搜索范圍和內(nèi)存占用，如下圖：
每個像素的視差范圍計算方法：
如果當(dāng)前像素的視差值$d(x)$無效，在搜索窗口 $win$ =31, 反之 $win$ =7
以當(dāng)前像素為中心，窗口大小 $win$ 搜索所有有效視差存儲在 $max$ 中， $disps$ 的大小是 $numdisp$ ,中值是 $disps$ ,最大值,最小值 $min%0A$ :
$%5Bd_%7Bmax%7D%2Cd_%7Bmin%7D%5D%3D%5Cbegin%7Bcases%7D%0A%5Bmin(width*2%2F3%2C32)%2C%20-min(width*2%2F3%2C32)%5D%2C%26numdisp%3C3%5C%5C%0A%5Bdisp%2B(numDisp%2B1)%2F2%2C%20disp-numDisp%2F2%5D%2C%263%3D%3Cnumdisp%3CmaxNumDisp%20%5C%5C%0A%5Bdisp%2B(maxNumDisp*(max*2%2B1-disp)%2B1)%2FnumDisp%EF%BC%8C%5C%5Cdisp-(maxNumDisp*(disp-min*2)%2B1)%2FnumDisp%5D%20%26numdisp%3E%3DmaxNumDisp%5C%5C%0A%5Cend%7Bcases%7D$
代價聚合時，SGM由于每個像素視差范圍都一樣，所以各個搜索路徑都有對應(yīng)的視差，tSGM由于每個像素視差范圍不一樣有的可能都沒有重疊范圍，所以之前的代價聚合計算方法需要調(diào)整，把沒有重合的情況考慮進(jìn)去。
調(diào)整如下：
$if%20%5Cquad%20d%3Ed_%7Bmax%7D(x_b-r_i)$
$L_%7Br_i%7D(x_b%2Cd)%3DC_%7Br_i%7D(x_b%2Cd)%2BP_2$
$if%5Cquad%20d%3Cd_%7Bmin%7D(x_b-r_i)$
$L_%7Br_i%7D(x_b%2Cd)%3DC_%7Br_i%7D(x_b%2Cd)%2BP_2$
$else%3A$
$L_%7Br_i%7D(x_b%2Cd)%3DSGM$