基于模板的圖割立體匹配算法

曾培龍

摘要：近年來，基于圖像或視頻的三維重建技術的研究和應用越來越受到人們的關注，尤其是基于圖像的三維重建技術。立體匹配技術是三維重建中的關鍵環節。提出了一種全局立體匹配算法——基于模板的圖割立體匹配算法（TGC），該算法包括三個步驟：參考圖像的分割、視差平面估計、使用圖割方法為視差平面分配標簽。選取Middlebury測試集，將文中的算法與立體匹配領域中的經典算法在PBM值和運行效率上進行了對比和分析，取得了較好的效果。

關鍵詞：立體匹配； 模板分割； 視差平面； 圖割算法

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-2163（2013）05-0050-05

0引言

近些年來，已有越來越多的立體匹配算法涌現出來，這些算法的基本構架是：在基元相似的條件下，找到一種約束的匹配規則進行最優搜索，并且保證這種搜索能最終找到近似的最優解。但是立體匹配問題的解決本身就存在著模糊性，比如：噪聲干擾、弱紋理區域、遮擋區域、重復紋理區域和深度不連續性。

立體匹配的算法性能依賴于三個因素：準確的匹配基元、與基元相對應的匹配準則、構建能夠準確匹配所選基元的穩定算法[1]。

2001年，Tao et al.提出了一個基于色彩分割的立體匹配算法的框架[2]，該框架建立在一種重要的假設之上，即：實現分割的區域之內是沒有較大視差變化的。其主要思想是：如果假設的視差值是正確的，則根據這個視差值將參考圖像變換到另外一個視角，即匹配圖像中，使其呈現出能夠與匹配圖像相匹配的效果。因為，立體匹[JP2]配問題就是通過最小化全局圖像的能量函數而得到解決的。圖像的色彩分割表示法旨在減少解決問題的步驟，且可以強化區域內的視差的平滑性約束。通過鄰近視差值假設的方法提出的貪婪區域的搜索機制進一步縮減卷積代價、為不匹配區域找到更好的視差值。[JP]

Boykov et al.和Kolmogorov 連同Zabin提出了基于Graph cuts的立體匹配算法[3，4]，以找到與觀察到的數據相一致的光滑視差圖像。在其提出的算法中，立體匹配問題可等價為一個能量最小化的問題，能量方程中通常包含：

（1）衡量在相鄰像素對之間視差值平滑性的平滑項Es；

（2）衡量給予像素的標簽不一致性的數據項Ed。

找到能量方程后，就可以據此方程建立一個帶權圖，在這個圖中，結點代表像素，圖的標簽集或者是說終點與所有可能的視差值（或者是視差范圍區間內的任何一個具體值）且圖中的邊的權值與已經定義好的能量方程中的項相一致。Graph cuts算法機制可以得到近似的優化解，這個優化解就是將視差值（標簽）分配到對應的像素（圖中的結點）上。

綜合基于色彩的分割算法和Graph cuts的思想，本文提出了基于模板的圖割立體匹配算法（TGC）。在TGC算法中，參考圖像可分割為不重疊、無交集的一個個的圖像部分，而要找到一個假設的視差值的集合，場景結構則近似地等價為視差空間內的平面集合，且這些平面不必是相互平行的。那么立體匹配算法就成為將視差空間中的平面與分割后的參考圖像的部分相匹配的問題，這樣做的目的是因為在分割后的小區域內建立能量評價函數更為容易。

TGC使用與Boykov et al.論文中Graph cuts類似的方式來找到能量方程的近似最優解，但是在建立圖像時圖像中的結點代表的是分割后的圖像部分而非像素點。所以，在大多數立體匹配處理的圖像中，圖像分割后的部分數是遠遠少于像素點數的，這就直接使建立得到的圖像簡單且會有更快的計算速度。另外，跟Birchfiel和Tomasi提出的算法思想類似[5]，TGC使用平滑視差項代表被加強了分段連續性的視差連續的區域，但是遮擋區域通常會在合并之后進行處理，并且是在分割部分的區域內建立圖像，正因為此，將降低Graph cuts階段的計算的復雜度。

1參考圖像的分割

TGC則建立于如下假設上：立體匹配算法處理的圖片的大的視差的不連續僅僅會在分割后的部分與部分之間的邊界處。嚴格地將視差連續性加強在區域內，次分割部分由于在分割后的部分與部分之間的平滑性約束（定義為能量方程中的Esmoth項）在很大程度上被容忍。

2視差平面估計

TGC使用一個視差連續的表面表示場景結構，近似地可以認為每一個表面均是一個平面，而不是不規則的曲面，但是這種平面是可以想象為任何復雜的曲面的。當然，這種近似的平面也會使得在計算時，視差的準確度相應地有所降低。但是這種近似使得模型得到簡化，同時也能夠應用于更多的領域，如：視覺合成、三維重建等。在這個部分中，使用下面的步驟估計場景中的視差平面。首先，使用區域立體匹配的規則找到初始的粗糙視差值。其后，為每一個分割后得到的模板找到表示模板函數的內部參數，在這里計算時，將跳過分割得到的太小的模板。最后，在得到的模板參數描述的基礎上，對相似模板通過擬合操作，以進一步減少模板數目，并且在下一部分使用Graph cuts算法而建立了簡單圖，由此達到提高算法效率的目的。

[HTH]2.1像素級的區域匹配[HTSS]

在標準的立體匹配研究中，所有的立體匹配圖像都是已經完成對極處理的。因此，一對匹配點，若在參考圖像I中的點（x，y），其匹配點在匹配圖像中I′中為（x′，y′），自然可以得到公式（1）：

（2）

對于所有的可能的視差值，均需計算其匹配代價，最后，得到的最小的匹配代價對應的視差值d即為該像素點處的視差值，可記為d[DD（-*2]^[][DD）]（x，y）。

[HTH]2.2從單一的模板中擬合出初始視差平面[HTSS]

在Tao等的文章中已經將如何從單一模板的初始視差中擬合得到視差平面的算法給出了框架。在此部分中，就使用了這樣的算法框架。首先，對于分割得到的模板使用一個視差平面來代表整個模板中的連續視差，這個視差平面可以使用公式（3）來表示：

d=ax+by+c[JY]（3）

式（3）中，[a，b，c]表示視差平面的參數，而d則表示像素點（x，y）的相應視差。文中使用最小二乘法即可以求得這個線性方程的解[a，b，c]，如公式（4）所示：

A[a，b，c]T=B[JY]（4）

在這個線性方程中，矩陣[WTHX]A[WTBZ]中的第i行為[xi，yi，1]，其含義表明為某一像素，在以列向量表示的矩陣[WTHX]B[WTBZ]中，對應著該像素的就是第i列像素值即d（xi，yi）。

在對初始視差模板擬合之后，使用迭代的步驟來更新模板。在每一次迭代中，像素視差的改變是在已經擬合的初始視差平面的一定的范圍之內，且得到的視差平面的擬合參數也是隨之而相應變化的[7]。

TGC加入了一些機制增加視差模板的擬合算法的魯棒性。分析如下：