1.緒論

立體匹配是三維重建系統的關鍵步驟，并且作為一種非接觸測量方法在工業以及科研領域具有重要的應用價值。為了完成匹配工作以及獲取場景的稠密視差圖，可以通過構建能量函數對應立體匹配的約束條件。復雜能量函數的全局最優解通常是NP難問題。相對于其他全局優化算法相比如模擬退火、梯度下降、動態規劃等，圖割算法不僅精度高，收斂速度快，并且對于光照變化、弱紋理等區域的匹配效果也比其他算法好。

2.圖割算法

計算機視覺領域的大部分問題可以轉換為標號問題，在立體匹配中視差的求解就是對圖像的像素在視察范圍內的離散標號問題。離散標號的最優解問題可以采用能量函數的最小化來求解，圖割做為一種可以求解能量最小化問題的算法，在計算機視覺領域的應用非常廣泛，如圖像分割，圖像恢復，立體匹配等。

Kolmogorov指出了如何將能量函數最小化問題與立體視差計算聯系起來。通常使用圖割算法進行立體匹配分為三個步驟，建立網絡圖，圖割算法求解，生成視差圖。圖割算法由于其全局優化的特性能夠獲取效果良好的稠密視差圖，但是對于處理高分辨率圖像其運算量過大，為了降低運算量，一般思路都是采用分割后的圖像縮小網絡圖的規模從而降低計算量。然而由于采用自動化非交互的彩色圖像分割方法會把相同視差的區域分開或隱去了圖像的部分細節信息，導致分割誤差，而消除誤差需要引入其他方法，如通過引入初試視差估計等方法，但這些方法增加了立體匹配算法的整體復雜度，而且沒有有效利用分割信息。

在實際應用場景中為了獲取感興趣區域的精細視差圖，針對于以往基于圖像分割的立體匹配算法復雜、計算量大，沒有充分利用分割結果的信息等缺點，本文提出了一種基于圖像分割的立體匹配方法。該方法在圖像分割時采用可交互的圖割方法獲得感興趣目標，只針對感興趣目標進行立體匹配，因此運算量大大減少，同時保留了原有圖割算法具有的全局最優特性。

2.1 能量函數

使用圖割算法進行立體匹配的過程中，需要將圖割中的網絡圖和能量函數對應起來。能量函數定義為：
這里寫圖片描述
該能量函數的四項分別為數據項，遮擋項，平滑項，唯一項。每一項都表征匹配時待處理的問題。

1)數據項：
數據項是為了讓算法獲取最佳的像素匹配，像素之間的色彩相似度越高，數據項的值越小。

其中函數D(a)用來表征匹配像素p，q之間的不相似性，a = (p,q)表示如果p，q像素匹配，數據項約束生效并可以按照下式：進行展開計算。
2)遮擋項
遮擋項的作用依然是為了將匹配像素個數最大化，對于存在遮擋無法匹配的像素按照下式乘以懲罰系數，由公式可知遮擋像素越少，遮擋項的值越小。
3)平滑項
平滑項主要衡量的內容是對于臨近像素一般具有相似性特別是色彩相似這一特點，對于像素p而言其鄰接像素p1和p2應該具有相同的視差分配。

平滑項一般采用分段函數。其中可以按照距離度量展開成分段函數。平滑項的值越低意味著臨近像素的視差越相近。
4)唯一項
唯一項專注于立體匹配的唯一性約束，若待匹配點出現了不止一個匹配的情況則將懲罰值設置為無窮大。下式為其數學表達

2.2 網絡流

（一）最大流
對于帶有源點S和匯點T的有向圖，稱為網絡圖。在網絡圖中設f是定義在集合E上的非負函數。用fij表示f在弧e = (vi,vj)上的值，即為弧e上從vi到vj的流量稱為網絡流。網絡流fij滿足下列兩個條件：

1.流量Fij不超過弧的容量Cij，
2.對于任意頂點vi，從vi留出的流量等于從vi流入的流量。即：

滿足上述條件的所有網絡流中流量最大的一個，稱為最大流。

（二）最小割
網絡圖中一個S-T的割意味著將頂點集分為兩部分，這里寫圖片描述。割的代價為頂點集到所有割邊的容量和，容量和最小的割稱為最小割。設x 和y 是頂點集V中的兩個頂點，(x,y)表示從x 到y 的一條邊，其邊的權值表示為c(x,y)。因此對于圖G=(v,e)其一個割可以表示為：

這里寫圖片描述

Ford 和 Fulkerson 早在1962年證明了最大流和最小割的等價對應關系。通過求網絡圖的最大流來等價其最小割，進而可以獲取此最小割對應能量函數的全局最小值。一個值得注意的工作為Boykov等人提出的基于圖割理論有效的能量函數優化方法。在該方法中，作者提出標號函數的兩種比較大的移動，擴張移動
(expansion moves)和交換移動(swap moves)，并證明了其擴張算法所獲得的局部小和全局小相差一個已知的常數，而交換算法可以處理更一般的能量函數形式。本文使用擴張移動算法。

3.立體匹配網絡圖的構造

在使用圖割算法進行立體匹配過程中首先需要構建網絡圖，對于上文提到的網格圖由節點和連接節點的有向邊組成。源點S，匯點T為兩個特殊節點。邊分為兩種，一種視差邊，一種是平滑邊。視差邊對應于能量函數(公式(1))第1項，平滑邊對應于能量函數第2項。
網格圖的具體構建過程如下：

1.建立3維坐標系O-XYZ，把圖像置于OXY平面，得的原點，X軸、Y軸與OXY平面的原點以及相應的軸重合。
2.在Z軸的正半軸上，從原點開始等距離的放置向量了l1,l2,…ln，在l1即原點O的地方放置q0，對于i=1,2,…n-1在li和li+1的中點放置點qi，最后在ln處放置qn。

至此，由OXY平面中像素點p=(px,py)以及Z的正半軸上點q0,q1,…qn構成了一個立方體網格。我們可以知道，對i=1,2,…n-1，在Z軸上的每個區間[qi,qi+1]恰好包含一個li+1。記(p,qi)=:(px,py,qi)為立方體網格上的節點，N(P)為像素點P的鄰域。在網絡圖兩端分別添加兩個節點，即源點S，匯點T。并在S到I1中每個屬于左視圖分割模版(圖(1))中標記為前景的像素點之間添加一個邊，在T到集合這里寫圖片描述即立方體網絡上與OXY平面相對的另一個面上的節點，添加到匯點的邊。由此，獲得一個無向圖G=< v,e >即：

這里寫圖片描述

則網絡圖中各邊的容量為：

(1)源點，匯點連接邊的容量為：匯點鏈接邊的容量

這里寫圖片描述

(2)視差邊的容量為：對任意，邊的容量為：

在對視差邊的處理上，視差邊對應能量函數的數據項，既(1)式的第一項，在彩色圖像中我們對RGB三通道分開處理，再求加權平均，這樣保留了顏色信息，結果更加精準，特別的，為了更進一步的準確，本文采用線性最近鄰插值算法添加了亞像素信息。上式可以擴展為：

這里寫圖片描述
為彩色圖像各個通道的權值，可取0.29，0.11，0.58，或者0.33。

(3)光滑邊的容量：p, q為衣服圖像中相鄰兩像素：

于是網絡圖構建完成，如圖所示：

4.基于圖割算法的圖像分割

本文以圖割算法為基本框架，采用基于圖像分割的辦法來實現對于感興趣物體的立體匹配。由于彩色圖像分割算法會影響到后期立體匹配的結果，所以選取合適的分割算法非常重要。

基于自動化非交互的分割方法可能會把相同視差的區域分開或者隱去了圖像的部分細節信息，這就造成了誤差，而消除誤差需要引入其他方法，如通過引入局部匹配算法為分割模版提供初試視差估計等方法，但這些方法提升了立體匹配算法的整體復雜度，而且沒有有效利用分割信息。所以本文采用基于圖割算法的圖像分割，在構建立體匹配網絡圖的同時進行圖像分割。

在圖像分割問題中我們定義如下的能量函數形式：
這里寫圖片描述

傳統基于圖割算法的圖像分割將上式映射為求解對應加權圖的最大流/最小割問題，對于低分辨率的簡單圖像交互分割效果良好但是計算復雜度較高，內存開銷大。為了提高分割速度并且適用于高分辨率圖像，將圖像分割融入立體匹配的流程中。本文采用文獻[22]中的方法，通過添加輔助索引節點，并使用新的能量函數形式：
這里寫圖片描述

加速分割并減少運算量。公式(5)數據項中跟表示前景物體跟背景的非歸一直方圖，平滑項中
這里寫圖片描述，為圖像中所有⊿I的均值。該方法簡化了圖割計算時間，并且得到了非常精準的分割結果。如下所示(藍色種子點用來標記背景，紅色種子點用來標記前景)：


baby1左視圖種子點設置	左視圖分割結果

baby1右視圖種子點設置	右視圖分割結果

5.圖割算法立體匹配

在立體匹配問題中，視差圖的標號問題可以等價為全局能量函數的最小化求值問題，通常表示為Greig能量函數形式
這里寫圖片描述
在圖1中，點表示源點，點表示匯點，視差邊對應于能量函數式（1）中的第一項，平滑邊對應于能量函數第二項。求解式（1）的能量函數的最小值可以等價為求解圖的最小割問題，獲得全局最優的視差圖。

為了減少立體匹配的運算量，本文根據圖像分割的結果得到感興趣物體與分割模版，由分割模版構建網絡圖，使用圖割算法進行立體匹配，有效利用了分割信息。綜上所述本文算法可以概括為兩大步驟：1感興趣目標的提取，2利用網絡圖進行立體匹配。算法流程圖如圖2所示：

這里寫圖片描述
Figure 2 Flow chart of the Algorithm

本文相對于傳統方法，根據每個像素構建網絡圖的算法有所不同。對于圖，在兩端分別添加源點，匯點之后，只在到中每個屬于左視圖分割模版中標記為目標的像素點之間添加邊，在T到集合即立方體網絡上與平面相對的另一個面上的節點，添加對應到匯點的邊。通過上述方法，可以大大減少計算量。

為了進一步優化匹配結果，本文在對網絡圖中視差邊的處理上，針對彩色圖像采用RGB三通道分開處理，用線性最近鄰插值算法在圖像的橫坐標方向添加了亞像素信息。即將(2)式擴展為：
這里寫圖片描述
式中為彩色圖像各個通道的權值。

按照上述的方法法構造網絡圖，并給各個邊賦相應的權值，采用基于增廣路的最大流算法求解，得到全局最小值，即為最優視差匹配。

參考文獻

[16]Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(9): 1124-1137.
[19]Roy S, Cox I J. A maximum-flow formulation of the n-camera stereo correspondence problem[A]// IEEE International Conference on Computer Vision[A], 1998 January 4-7, Bombay India:492-499.
[20]Hong L, Chen G. Segment-based stereo matching using graph cuts[A]// IEEE Conference on Computer Vision and Pattern Recognition[C],2004 June 27-July 2,Washington DC USA:74-81.
[23]Tang M, Gorelick L, Veksler O, et al. GrabCut in One Cut[A]// IEEE International Conference on Computer Vision[C], 2013 Dec 01 - 08, Sydney, Australia 1769-1776.
[24]王年, 范益政, 鮑文霞等. 基于圖割的圖像匹配算法[J]. 電子學報, 2006, 34(2):232-236.
[25]Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[C]// Stereo and Multi-Baseline Vision, 2001. (SMBV 2001). Proceedings. IEEE Workshop on. IEEE, 2001:131-140.
[28]Deng Y, Yang Q, Lin X, et al. A symmetric patch-based correspondence model for occlusion handling[C]// Proceedings / IEEE International Conference on Computer Vision. IEEE International Conference on Computer Vision. 2005:1316-1322 Vol. 2.
[29]Freeman W T. Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters[C]// Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on. IEEE, 2003:900.
[30]Kolmogorov V. Graph based algorithms for scene reconstruction from two or more views[D]. Cornell University, 2004.
[31]Kolmogorov V, Zabih R. Multi-camera scene reconstruction via graph cuts[M]//Computer Vision—ECCV 2002. Springer Berlin Heidelberg, 2002: 82-96.

論文資源合集

立體匹配綜合論文集 : http://download.csdn.net/detail/wangyaninglm/9591251

基于圖像分割的立體匹配論文合集 : http://download.csdn.net/detail/wangyaninglm/9591253

并行立體匹配論文合集 : http://download.csdn.net/detail/wangyaninglm/9591255

基于置信傳播的立體匹配論文合集 : http://download.csdn.net/detail/wangyaninglm/9591256

基于稠密匹配的論文合集： http://download.csdn.net/detail/wangyaninglm/9591259