改進的基于α擴展移動的立體匹配算法

李惠光，翁良寶，姜洪磊

（燕山大學 電氣工程學院，河北 秦皇島066004）

0 引 言

立體匹配在計算機視覺研究是一個重要領域。它通過匹配給定的兩幅或多幅圖像，尋找圖像中的物體在另一張圖像中相對應點的關系，計算出兩者之間的視差 （Disparity），從而獲得物體深度等信息［1］。近年來，隨著圖論的發展和完善，圖割思想的算法在立體匹配方面逐漸成為一個熱點［2－3］，其中，由 Boykov等人［4－5］提 出 的α 擴 展 移 動 算 法的應用較為廣泛，該算法的匹配精度高，尤其在底紋理區域和不連續區域的匹配也可以獲得良好地匹配效果［6］，但是，α擴展移動算法在匹配過程中需要不斷構建網格圖，進行圖切割優化，這占用了大量的計算時間，針對這一問題，本文提出了一種改進的α擴展算法，該算法首先定義了一個循環停止參數，當計算的循環停止參數滿足循環停止條件時，停止循環，其次是改變了傳統α擴展移動算法的無序迭代，優先設定經初始視差計算后大概率分布視差值。

1 α擴展移動算法的相關知識

1.1 構造能量函數

計算機視覺里的很多問題都可以歸結為能量函數的優化問題［7］，比如圖像的立體匹配問題，可以通過構造能量函數，采用優化算法求解能量函數的最小值，與最小值對應的像素標記的視差值就是匹配的結果。

立體匹配的能量函數一般由數據項約束Edata（f）和光滑項約束Esmooth（f）組成，如下

則能量函數可以表示為

式中：P——圖片所有像素點的集合，p——集合中的一個像素點，｛p，q｝∈N——圖片中相鄰的兩個像素點，fp∈L——p的標記視差，L——視差范圍，則 Dp（fp）——p點在視差為fp時匹配代價，它的表達式為

式 （3）是圖像中相鄰像素間的懲罰項，它反應了區域內部的連續性和邊界的不連續性。本文選用了Potts模型的平滑項函數

其中k＝20，當fp＝fq時，T＝0；fp≠fq時，T＝1。

1.2 α擴展移動算法具體描述

由于能量函數E（f）的最小化求解是一個非確定性多項式問題，如果采用窮舉法，則算法的計算量過大，它的狀態空間為LH×W，其中L為視差范圍，H為圖片的高度，W為圖片的寬度；采用變分方法或者條件迭代模式算法 （iterated conditional mode，ICM 算法），在求解的過程中容易遇到對初始值敏感、易得到局部極小值的問題，因此，如何計算出全局最小值一直是個難題。針對這個問題，Boykov采用了ICM算法循環迭代的思想［8］，通過α擴展移動對求得的能量函數不斷迭代循環，使其最終收斂于最小值。與ICM算法不同的是α擴展移動算法是同時改變大部分的像素標記視差值，每次擴展移動都會使能量函數有很大變化，這樣就很好的克服了ICM算法的單個像素的移動中容易遇到局部極小值的問題，使能量函數向全局最小值收斂。α擴展移動算法的流程圖如圖1所示。

圖1 α擴展移動算法流程

a在流程圖中，步驟3到步驟5的執行稱為一次內部迭代，在內部迭代的過程，α是在視差的范圍里隨機設定的，步驟2到步驟5的執行稱為一次外部循環。其中，步驟中如何計算f＾＝argminE（f′）是一個非常關鍵的問題，Boykov構建了α擴展移動能量網格圖，首先對所有視差標記不為α的像素點建立能量網格圖，然后通過最大流最小割算法對能量網格圖進行 “切割”（可以簡單理解為優化），“切割優化”的結果使其中的部分像素視差被重新標記為α，而剩余的則保持原來不變的視差標記［9］。α擴展移動算法采用這樣的優化方式不斷循環修改每個像素的視差標記值，使能量函數逐漸收斂，最終收斂到全局最小值。

1.3 能量網格圖的構造

圖2為α擴展移動時構造的能量網格圖，為方便理解，把Gα設置成一維圖像。

圖2 α擴展移動算法網格

對于每個像素點p∈P通過t－linktap和t珔ap連接到源點α和匯點珔α，構造的輔助節點a｛p，q｝通過輔助邊ε｛p，q｝＝｛e｛p，a｝，e｛a，q｝，t珔αα｝連接到p，q，珔α點，所以圖2中所有點的連接邊為

各個連接邊的權值容量大小設置見表1。

表1 連接邊的權值設置

1.4 最大流最小割求解能量函數

在構建完能量網格圖后，利用最大流最小割求解能量函數E（f∧）。本文采用的是Boykov和Kolmogorov提出的最大流最小割算法，該算法是一種雙向搜索并重用搜索樹的增廣路徑算法，雖然算法的理論復雜度比較高，為，其中s是最大流算法的最大增廣數目，m和n分別是網格圖中的連接邊和節點，iter是收斂時需要迭代的次數，k是視差的數目，但是計算機視覺的實際應用中卻有著非常高的效率［10］，比其他最大流算法快了2～5倍，因此在立體匹配、圖像恢復等方面廣泛使用。

2 改進的α擴展移動算法

為分析匹配算法的性能，本文采用均方根誤差 （式（10））和錯誤匹配率 （式 （11））兩個指標

其中dc（x，y）是算法計算所得的視差值，dGT（x，y）是真實的視差值，δd是容許的錯誤視差閾值，本文中δd＝1。

2.1 構造循環停止參數簡化循環過程

以 Middlebury［11］提供的標準圖 Tsukuba （384＊288）為例，圖3為經過第i次循環后的視差值分布圖。

圖3 第i次循環后的視差值分布

本文以視差fp在視差值分布圖中的分布概率構造一個向量P，按照式 （12）構造一個循環停止參數θ

圖4是Tsukuba在α擴展移動后的能量函數E（f）變化圖，Run0為隨機標記視差后的能量函數的初始狀態。仔細觀察可以發現在最初的幾次外部循環后能量函數值 （直方柱表示）迅速下降，隨著循環次數的不斷增加而逐漸單調遞減，一直衰減到能量函數最小值時停止循環。然而，在不斷循環的過程中，能量函數值在接近最小值時，其收斂速度明顯減小，變化也越來越微弱，這說明α擴展移動算法的在后面的幾個循環中的效率越來越低。

圖4 循環過程中能量函數E（f）與Theta（θ）的變化

為了更全面的研究α擴展移動算法，本文也通過誤匹配率和均方根誤差這兩個指標去分析外部循環過程中的其他變化。如圖5所示，同樣也可以發現，隨著不斷地循環，誤匹配率和均方根誤差也逐漸單調減小，最后緩慢的收斂于最小值。

圖5 循環過程中誤匹配率與均方根誤差的變化

針對以上兩圖的分析，為了提高擴展移動算法的計算效率，節省算法的運行時間，根據式 （12）構造的θ，建立新的循環機制，即第i次與第i－1次之間的視差分布變化向量越來越小，當循環停止參數滿足循環停止閾值的條件θ＜θthreshold時 （θthreshold為循環停止閾值），就停止繼續循環，這樣相較于傳統的α擴展移動算法的循環過程，就減少了循環過程中能量函數變化很小的區間循環，縮短了算法的計算時間，提高了算法的計算效率。

2.2 改變α擴展移動順序

在α擴展移動算法的內部迭代過程中，α值的設定是在視差值范圍［fmin，fmax］隨機選取的。如果將α值按照標準視差分布圖中大概率的視差值優先設定，那么與其他的α小概率分布視差值相比，在進行α擴展移動時能量函數的變化會有更大的影響。因此，本文采用了將待匹配的圖像進行初始視差計算的方法，將α按照計算后的初始視差大概率分布視差值優先設定，這樣在內部迭代的過程中，能量函數能以更快的速度收斂于最小值。

由于初始視差計算的方法對視差計算的匹配精度結果要求不高，只要求計算出視差值范圍內的大概率視差值，本文選擇了基于區域的局部匹配算法中的SAD算法 （sum of absolute differences）。SAD算法是在左圖中待匹配像素點創建一個n×n的窗口，然后沿著極線在右圖視差范圍內選擇相似性最大的像素點作為匹配點。

2.3 改進的α擴展移動算法的流程圖

圖6是改進的α擴展移動算法的流程圖。和原始的流程圖比較，本文對步驟2、步驟7和步驟8做了修改，在步驟2中，優先將α按照初始視差計算后的大概率視差值設定，步驟7中，增加了θ的計算，步驟8中，增加一個閾值判定，即當計算的θ滿足循環停止閾值時就不再進行循環，計算停止，反之，則繼續循環。閾值θthreshold的選擇嚴重影響著算法的匹配時間和精度。表2是以Tsukuba為例在不同θthreshold條件下的實驗結果，如果θthreshold選擇過大，算法匹配時間縮短，但算法的匹配精度有很大誤差，如果θthreshold選擇過小，則算法匹配時間延長，匹配精度提高。本文改進α擴展移動算法選擇的θthreshold＝1。

表2 不同θthreshold的實驗結果

圖6 改進的α擴展移動算法的流程

3 實驗和結果

為了驗證改進的圖割算法的正確性，本文根據Middleburry上提供的標準圖像進行了實驗，實驗的數據結果以匹配時間、均方根誤差和錯誤匹配率作為評價指標。實驗圖像和數據結果如圖7和表3所示。

圖7 匹配后的視差圖對比

表3 視差圖的評價指標對比

根據圖7原始算法和改進算法匹配后的視差圖對比，直觀上觀察改進算法獲得了幾乎和原始算法一致的稠密視差圖，根據表格3中的均方根誤差和誤匹配率的指標對比，原始的α擴展移動算法和改進的α擴展移動算法匹配的都獲得了良好的匹配效果，而表格2視差圖的匹配時間表明，改進算法比原始算法在效率上卻明顯提高，計算時間大大縮短，這是由于構造的循環停止參數滿足條件時停止循環，減少算法的循環過程，將α優先按初始匹配后的大概率視差分布設置則使能量函數以更快的速度收斂，這樣使改進的算法不僅可以得到精確視差圖的同時，匹配時間也大大減小了。

4 結束語

在計算機視覺領域中，采用α擴展移動算法去解決立體匹配問題是一種有效的方法，通過建立能量網格圖不斷的循環優化求解能量函數最小值，在低紋理區域也可以獲得稠密精確的視差圖，但該類算法的復雜度很高，匹配時間比較長。本文仔細研究了α擴展移動算法能量函數的優化過程，提出了兩個改進，一是在外部循環的過程中提出了循環停止機制，，二是改變了原始算法α設定的隨機性。實驗結果表明，改進的算法 “遺傳了”α擴展移動算法的優點，不僅可以獲得幾乎一致匹配精確高的稠密視差圖，而且在算法的匹配時間大大縮短了，與原始算法比較減少了60～75%。由于α擴展移動也應用于計算機視覺的其他領域如圖像恢復和圖像分割等方面［12－14］，不同的是能量函數表達式不一樣，因此改進的算法也可以在圖像處理方面的其他領域里獲得應用。

［1］BAI Ming，ZHUANG Yan，WANG Wei.Progress in binocular stereo matching algorithms ［J］.Control and Decision，2008，23 （7）：721－729（in Chinese）.［白明，莊嚴，王偉.雙目立體匹配算法的研究與進展 ［J］.控制與決策，2008，23 （7）：721－729.］

［2］WANG Nian，FAN Yizheng，BAO Wenxia.An images matching algorithm based on graph cuts ［J］ACTA Electronica Sinica，2006，34 （2）：232－236 （in Chinese）.［王年，范益正，鮑文霞.基于圖割的圖像匹配算法 ［J］.電子學報，2006，34 （2）：232－236.］

［3］ZHANG Lingtao，QU Daokui，XU Fang.An improved stereo matching algorithm based on graph cuts［J］.Robot，2010，32 （1）：215－219（in Chinese）.［張令濤，曲道奎，徐方.一種基于圖割的改進立體匹配算法 ［J］.機器人，2010，32 （1）：215－219.］

［4］Boykov Y，Veksler O，Zabih R.Fast approximate energy minimization via graphcuts ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23 （11）：1222－1239.

［5］Kolmogorov V，Zabin R.What energy functions can be minimized via graphcuts ［J］.IEEE Transon Pattern Analysis and Machine Intelligence，2004，26 （2）：147－159.

［6］LU Ali，TANG Zhenmin.Anα－expansion stereo algorithm based on segment－constraint ［J］.PR＆AI，2010，23 （3）：385－395 （in Chinese）.［盧阿麗，唐振民.基于分割約束的α擴展體視算法［J］.模式識別與人工智能，2010，23 （3）：385－395.］

［7］WU Chunhong，FU Guoliang.A stereo matching method based on K－means segmentation and neighborhood constraints relaxation ［J］.Chinese Journal of Computers，2011，34 （4）755－760 （in Chinese）.［伍春洪，付國亮.一種基于圖像分割及鄰域限制與放松的立體匹配方法 ［J］.計算機學報，2011，34 （4）755－760.］

［8］Gong M.A performance study on different cost aggregation approaches used in real－time stereo matching ［J］.International Journal of Computer Vision，2007，75 （2）：283－296.

［9］XU Sheng，YUN Ting，YE Ning.Research on stereo matching algotithm based on disparity map optimization ［J］.Computer Engineering and Design，2012，33 （2）：658－664 （in Chinese）.［徐昇，云挺，業寧.基于視差圖優化的立體匹配算法研究 ［J］.計算機工程與設計，2012，33 （2）：658－664.］

［10］Candemir S，Akgul Y S.Adaptive regularization parameter for graph cut segmentation ［C］／／Proceedings of the 7th International Conference on Image Analysis and Recognition.Springer Berlin Heidelberg，2010：117－126.

［11］Microsoft research of disparity matching algorithm ［EB／OL］.［2009－07－26］.http：／／vision.meiddlebuty.edu／stereo／.

［12］Boykov Y，Funka－Lea G.Graph cuts and efficient N－D image segmentation ［J］.International Journal of Computer Vision，2006，70 （2）：109－131.

［13］Boykov Y，Veksler O.Graph cuts in vision and graphics：Theories and applications ［C］／／Handbook of Mathematical Mode－ls in Computer Vision.New York：Springer US，2006：79－96.

［14］LIU Songtao，YIN Fuliang.The basic principle and its new advances of image segmentation methods based on graph cut［J］.Acta Automatica Sinica，2012，38 （6）：911－922 （in Chinese）.［劉松濤，殷福亮.基于圖割的圖像分割方法及其新進展 ［J］.自動化學報，2012，38 （6）：911－922.］