基于動態規劃的快速立體匹配算法

羅嗣卿，賈子書

（東北林業大學信息與計算機工程學院，哈爾濱150040）

·圖形圖像處理·

基于動態規劃的快速立體匹配算法

羅嗣卿，賈子書

（東北林業大學信息與計算機工程學院，哈爾濱150040）

為提高立體匹配算法的匹配速度使其滿足實時性要求，同時減少視差圖中的條紋現象提高匹配準確率，基于動態規劃原理提出一種快速立體匹配算法。利用快速自適應權重累積策略累積匹配成本，通過二維有序表結構加快動態規劃的計算速度，采用基于方向濾波的視差后處理方法減少視差圖中的條紋現象。實驗結果表明，該算法在保證視差圖準確的基礎上能有效提高立體匹配效率，可應用于實時匹配系統。

立體匹配；動態規劃；自適應權重；快速累積；積分圖像

1 概述

立體匹配是計算機視覺領域中的一個經典問題，目前國內外學者已提出大量的匹配算法來解決這個問題，但由于問題本身的病態性而導致較少有算法能完美解決匹配中的所有困難。文獻［1］對目前已有的各種算法進行了全面的分析和綜述。根據該文獻提出的分類標準，立體匹配方法可分為局部立體匹配方法和全局立體匹配方法。局部立體匹配方法的關鍵問題是確定支撐窗口。支撐窗口一方面要盡可能大以便包含足夠多的灰度信息變化從而增強匹配的可靠性，另一方面要盡可能小，以避免投影畸變和窗口內視差不一致而導致的不正確匹配。支撐窗口的選擇主要集中在2個方面：一方面集中在支撐窗口的尺寸與形狀，例如文獻［2-3］方法；另一方面集中在窗口內像素的支撐權重，例如文獻［4-5］方法。雖然局部立體匹配方法在匹配準確率上已取得了較大的進展，但是由于在匹配過程中沒有綜合考慮全局信息，導致在非紋理區域和物體邊界容易產生誤匹配。全局立體匹配方法綜合考慮了立體像對中的全局信息，通過優化算法最小化全局能量函數來求解最優視差，這類方法主要包括動態規劃［6-9］、置信傳播［10-11］和圖割［12-13］方法。基于圖割和置信傳播的立體匹配方法是一種基于整體圖像的全局匹配算法，其特點是匹配精度高、準確性好，但算法復雜度高。基于動態規劃的立體匹配算法是一種基于掃描行的全局匹配算法，其特點是實現簡單、效率高，但在匹配過程中由于缺少行間一致性約束而導致在視差圖中出現較為明顯的條紋現象。目前，大部分學者主要針對動態規劃立體匹配方法中的兩大問題進行研究：一是解決匹配中的條紋現象；二是加快動態規劃立體匹配的速度使之成為一種實時立體匹配方法。Birchfie等人提出一種點對點（Pixelto-Pixel）的動態規劃立體匹配方法［9］。該方法分為2個階段：匹配階段和后處理階段。匹配階段包括2個版本的動態規劃立體匹配算法：Backw ard-Looking算法和Forward-Looking算法。這2種算法在計算最優路徑的過程中執行了大量的冗余計算，為此，Birchfie又提出一種快速Forward-Looking算法，有效地縮短了Forw ard-Looking算法的計算時間。但該快速算法在理論上損失了最終解路徑的最優性，造成了視差精度損失，而且由于缺少成本累積階段也造成了一部分視差精度的損失。

本文針對快速Forward-Looking算法存在的缺點，提出一種基于動態規劃的立體匹配算法。首先根據快速自適應權重累積策略在視差空間圖中累積匹配成本，然后利用快速Backw ard-Looking算法計算視差，最后通過視差后處理方法去除視差圖中的條紋現象，提高視差精度。

2 視差空間建立

視差空間圖（Disparity-space Image，DSI）［6］是一個三維數據結構，該結構中的每一點（x，y，d）都代表參考圖像中的像素點（x，y）被賦予視差d時的匹配代價。本文提出的快速立體匹配算法利用這個數據結構來表達匹配中的遮擋和匹配，并通過動態規劃獲得一個最小成本路徑，其中路徑中的每一節點都代表一對匹配。

2.1 匹配成本

匹配成本是立體匹配方法的基礎，它測量的是2個位置的相似性或者不相似性。計算匹配成本最直接方法是采用像素點的灰度差絕對值，但該方法對噪聲和輻射差異的魯棒性很差，易造成能量函數中的數據項不能準確反應匹配約束。因此，在實際計算過程中經常采用截斷的匹配代價計算方法，其計算公式如下：

其中，IL（x，y）表示參考圖像；IR（x，y）表示匹配圖像；IS表示截斷閾值。

2.2 快速積累方法

在匹配過程中，經常需要對匹配成本進行累積以增加匹配的可靠性，其成本累積形式可表示為：

將式（3）代入式（2）整理得：

為了能使用積分圖像加速該權重函數的計算，本文將函數f（k）取為恒定的常數函數ω，為此，式（4）可簡化為：

針對式（5）中的c（p，d），c（p，d）IL（p），c（p，d）和IL（p）分別建立積分圖像，然后使用這些積分圖像累積匹配成本，從而提高累積過程的計算效率，使累積過程的計算復雜度與窗口大小無關。

3 動態規劃原理及快速實現

3.1 動態規劃原理

本文提出的立體匹配方法是一種基于掃描行優化的全局立體匹配方法，它把立體匹配中的對應搜索問題闡述為在每一掃描行y0所對應的二維代價矩陣φy0［d，x］=c（x，y0，d）中（如圖1（a）所示）查找最優成本路徑問題，其最優路徑上的每一節點代表著相應的匹配點。針對每一掃描行y0，其相應的能量函數可表達為：

其中，κOCC表示遮擋懲罰；kr表示匹配獎勵；c（xi，y0，d）表示匹配成本；NOCC和Nm分別表示遮擋數和匹配數。如圖1（b）和圖1（c）所示，根據次序性約束和遮擋約束，當前匹配點（di，xi）的直接前驅和直接后繼可分別表示為：

其中，Δ表示最大視差。利用動態規劃技術在代價矩陣φy0［x，d］上求解最優成本路徑，相當于計算如式（9）所示的遞歸公式：

反向追蹤找到最優成本路徑。在文獻［9］中根據圖1（b）更新代價矩陣的算法稱為Backward-Looking算法，而根據圖1（c）更新代價矩陣的算法稱為Forward-Looking算法。

圖1 動態規劃的搜索空間

3.2 快速Forward-Looking算法的最優性分析

Backward-Looking算法和Forward-Looking算法在計算最優路徑時執行了大量的冗余計算，為減少這部分冗余計算，文獻［9］提出了一種快速的Forw ard-Looking算法。該算法是在Forward-Looking算法的基礎上通過修剪策略減少這些不必要的計算，該修剪策略為：如果某一匹配的匹配成本大于其所在行中的最低匹配成本，則拒絕向右擴展該匹配；類似地，如果某一匹配的匹配成本大于其所在列中的最低匹配成本，則拒絕向下擴展該匹配。雖然該算法減少了大量的冗余計算，提高了算法的匹配速度，將優化部分的時間復雜度從O（nΔ2）降到了O（nΔlgΔ），但是該算法導致解路徑損失了最優性，造成了視差精度的損失。

如圖2所示，存在一匹配點p和及其后繼匹配點c，它們之間存在著左遮擋。現假設存在一點r，它與匹配點p位于同一掃描行并且假設r點的匹配成本小于p點的匹配成本即r0（r）＜r0（p）。那么當快速算法遇見匹配點p時，則拒絕向右擴展匹配點p，因為在它所在的行中存在更低的匹配成本。然而，如果p點左邊那些匹配點的匹配成本都大于p點的匹配成本時，則到c點的最優路徑很可能會經過p點，所以會使解路徑損失其最優性，從而導致視差精度的損失。

圖2 最優性損失

3.3 快速Backw ard-Looking算法

為了提高動態規劃立體匹配方法的匹配效率同時保證不損害解路徑的最優性，本文提出了一種快速Backward-Looking算法。該算法以Backward-Looking算法為基礎，通過二維有序表結構加快了動態規劃部分的計算，而且該算法在理論上沒有損失解路徑的最優性。快速實現動態規劃立體匹配算法的關鍵是快速實現遞歸公式（式（9））中的最小化操作。Birchfie提出的Forward-Looking算法和Backward-Looking算法實現最小化操作的時間復雜度為O（Δ），而其提出的快速Forward-Looking算法通過修剪策略減少了不必要的節點擴展，將最小操作的時間復雜度降低為O（lgΔ）。為了加快最小化操作的計算速度，本文首先分析式（9）中最小化操作的結構。由于式（9）中的遮擋懲罰κOCC是一個恒定的常數項，因此

其中的最小化操作可以簡化為：

如果已知：

則式（10）可以簡化為：

通過式（13）計算動態規劃中的最小化操作只需3次比較，與視差范圍Δ無關。由于二維數組a，b存在如式（14）與式（15）所示的遞歸關系：

因此，本文設計2個二維有序表a和b，其中的每一點都分別代表垂直方向和對角方向上的最小值，而且維護每個二維有序表僅需要一次比較，其二維有序表的結構如圖3所示。其中，成本矩陣φ中每個元素對應著視差空間圖中相應的元素；有序表a中每個元素都是一個三元組（v，d，x），v代表φ［0，x］～φ［d，x］之間的最小值，d和x代表其相應的坐標；有序表b中每個元素也都是一個三元組（v，d，x），v代表φ［d+x，0］～φ［d，x］之間的最小值，d和x代表其相應的坐標。

圖3 最小化操作的快速實現過程

本文以計算φ［4，4］為例來說明這一快速計算過程，如圖3中代價矩陣所示，φ［4，4］為圖3中的黑色單元格。如果根據式（9）計算該單元格的值，則有：

式（16）表明計算每個單元格需要Δ次比較。如果根據有序表a和b計算該值，則有：

式（17）表明根據有序表計算該值僅需要3次比較，而且維護有序表a和b僅需要2次比較，通過該快速計算方法可以節省大量的計算時間，而且沒有損失解路徑的最優性。

本文提出的加速方法僅適用于Backward-Looking算法，因為當計算當前節點最優匹配代價時，它的所有前驅節點都已計算完成，而且可以在計算最優代價的同時來維護這2個有序表，具體算法如下所示：

3.4 基于方向濾波的視差后處理

由于動態規劃立體匹配算法在優化過程中缺少行間一致性限制導致在視差圖中產生了條紋現象。因此本文提出一種基于方向濾波的視差后處理方法，該方法的優點是實現簡單、速度快，可以有效地減少條紋現象。

在該視差后處理方法中，首先提出一種線狀濾波器族，該濾波器族中的每個濾波器之間間隔相等的角度，且每個濾波器與水平方向分別成θi角度，然后分別使用這些濾波器對視差圖中的每個像素進行處理。

圖4顯示了一個線狀濾波器族，圖中的每個濾波器之間相隔15°。

圖4 線狀濾波器族

一般來講，每個線狀濾波器含有2 l+1個像素，且與水平方向成θi角度，其數學表達式為：

基于方向濾波的視差后處理方法的具體過程如下：

（1）在濾波器族中選擇一濾波器fθi（x，y）。

（2）在視差圖中選擇一像素點（x，y），然后對在該點濾波器內的像素進行統計生成視差直方圖，視差直方圖內視差出現頻率最高的視差即為mode，其頻率為max（x）；（x，y）點的視差d及其左右相鄰視差d-1，d+1的出現頻率分別為hist［d］，hist［d-1］，hist［d+1］，它們的頻率和為inertia=hist［d］+ hist［d-1］+hist［d+1］。

（3）如果max（x）＞inertia，則當前點（x，y）的視差為mode，否則如果hist［d-1］＞max（x），則當前點（x，y）的視差為d-1，否則如果hist［d+1］＞max（x），則當前點（x，y）的視差為d+1。

經過上述濾波處理之后，已基本去除視差圖中的條紋現象，而且可以有效提高視差的準確度。在實際應用當中，一般選擇較少的濾波器即可獲得較好的效果，本文選擇了4個濾波器，即θi∈［0°，45°，90°，135°］。

4 實驗與結果分析

4.1 實驗環境

為驗證本文算法的性能，本文使用了C++語言實現了該算法，并在CPU Pentium IV 2.2 GHz，內存2 GB，操作系統W indow s XP的環境下對M iddlebury網站上提供的立體數據集Tsukuba，Venus，Saw tooth和Map進行了測試。

4.2 經驗參數分析

在本文提出的立體匹配方法當中涉及到了一些經驗參數的選擇，這些參數會直接影響立體匹配方法的匹配精度，要選擇合適的經驗參數保證達到最好的匹配效果。為此，本文以M ap立體像對為測試對象，分析了成本截斷閾值、遮擋成本及匹配獎勵對立體匹配精度的影響以確定合適的經驗參數。

分別進行3組實驗測試經驗參數對匹配精度的影響。

實驗1 分析了成本截斷閾值TS對匹配精度的影響。首先假定遮擋成本κOCC=15，匹配獎勵kr= 30，然后測試成本截斷閾值對匹配精度的影響，具體測試結果如表1所示。實驗1結果表明成本截斷閾值為30時，壞點比例最低，立體匹配效果最好。

表1 成本截斷閾值對匹配精度的影響

實驗2 分析匹配獎勵kr對匹配精度的影響。首先假定遮擋成本κOCC=15，成本截斷閾值TS=30，測試匹配獎勵kr對匹配精度的影響，具體測試結果如表2所示。實驗2結果表明匹配獎勵為40，45，50時，壞點比例最低，具有較好的匹配效果。

表2 匹配獎勵對匹配精度的影響

實驗3 分析遮擋懲罰κOCC對匹配精度的影響。首先假定匹配獎勵kr=40，成本截斷閾值TS=30，測試遮擋懲罰對匹配精度的影響，具體測試結果如表3所示。實驗3結果表明遮擋懲罰為15時，壞點比例最低。

表3 遮擋懲罰對匹配精度的影響

通過以上3組實驗可以看出，當匹配獎勵kr= 40，成本截斷閾值TS=30及κOCC=15時，可以達到最佳的匹配效果。因此，在后續的測試當中，選擇該組參數進行測試。

4.3 時間復雜度分析

為提高匹配精度，本文在匹配之前加入了成本累積，該累積策略只包含了值域支撐支持，忽略了空間支撐；然后選擇了二次函數作為窗口函數；最后通過積分圖像加速該過程的計算速度使其與窗口大小無關。本文提出的快速自適應成本累積的計算時間與沒有使用積分圖像累積過程的計算時間對比如圖5所示。可以看出，當沒有使用積分圖像時，累積速度隨著窗口大小的增加而迅速增加；而當使用積分圖像時，該過程的計算時間與窗口大小無關，其計算時間表現為平行于x軸的一條直線。

圖5 累積過程的時間對比

Backw ard-Looking算法和Forw ard-Looking算法的時間復雜度為O（nΔ2），其中，n為圖像寬度，Δ為最大視差搜索范圍；快速Forw ard-Looking算法的時間復雜度為O（nΔlgΔ）；而本文提出的快速Backw ard-Looking算法的時間復雜為O（nΔ）。上述4種算法的運行時間對比如圖6所示，可以看出本文的快速算法具有更快的匹配速度，而且該算法沒有導致解路徑損失最優性造成視差精度損失。

圖6 運行時間對比

4.4 匹配精度分析

為驗證本文算法的立體匹配效果，利用本文算法對Tsukuba，Venus，Saw tooth和M ap進行實驗，結果分別如圖7～圖10所示。可以看出，經過視差后處理之后視差圖中的條紋現象明顯減少，本文算法的最終視差圖非常接近于真實視差圖，具有較好的匹配效果。

圖7 Tsukuba圖像實驗結果

圖8 Venus圖像實驗結果

圖9 Saw tooth圖像實驗結果

圖10 M ap圖像實驗結果

將本文算法與同類算法（傳統DP，SO，GCP+ DP算法、Two-Pass算法、TreeDP算法和Pixel-to-Pixel算法）的壞點比例進行對比，結果如表4所示。可以看出，本文提出的后處理算法復雜度非常低，處理實驗中的立體像對的時間一般在0.2 s左右。為了給出匹配精度的定量分析，本文同時計算了非遮

擋區域all、非紋理區域untex和視差不連續區域disc的誤匹配率，并與其他同類算法進行了對比。

表4 本文算法與其他算法的處理結果對比%

由表4可見，本文算法的優于其他動態規劃算法，而且該匹配算法具有較快的匹配速度。實驗結果表明，本文算法是一種高效可靠的立體匹配算法，它不僅可以獲得準確性較高的視差圖，而且具有較快的匹配速度，有效地提高了算法的匹配效率，可以應用于實時匹配系統。

5 結束語

通過分析成本函數結構發現，利用恒定的遮擋懲罰能大幅簡化成本函數的結構，使用2個二維有序表可有效提高算法的計算速度。為此，本文在此基礎上提出了一種基于動態規劃的快速立體匹配算法。首先利用積分圖像加快自適應權重累積策略的計算速度，使計算量與窗口大小無關，然后通過一種二維有序表結構在保證不損失解最優性的情況下提高動態規劃部分的運算速度，最后采用視差后處理方法減少視差圖中的條紋現象。實驗結果表明，該算法是一種高效可靠的立體匹配算法，可以應用于實時匹配系統。下一步將研究保存邊緣的濾波方法以改善成本累積過程，并嘗試將本文算法移植到GPU平臺，以加快匹配速度。

［1］ Scharstein D，Szeliski R.A Taxonomy and Evaluation of Dense Two-frame Stereo Correspondence Algorithms［J］. International Journal of Computer Vision，2002，47（1）：7-42.

［2］ Yang Qingxiong.Stereo Matching Using Tree Filtering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，37（4）：834-846.

［3］ 祝世平，李 政.基于改進梯度和自適應窗口的立體匹配算法［J］.光學學報，2015，35（1）：123-131.

［4］ Heo Y S，Lee K M，Lee S U.Robust Stereo Matching Using Adaptive Normalized Cross-correlation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（4）：807-822.

［5］ 翟振剛，陸 耀，趙 紅.利用塊幾何約束及視差概率的立體匹配算法［J］.軟件學報，2010，21（11）：2985-2998.

［6］ Bobick A F，Intille S S.Large Occlusions Stereo［J］. International Journal of Computing Vision，1999，33（3）：181-200.

［7］ Kim JC，Lee K M，Choi B T，et al.A Dense Stereo Matching Using Two-pass Dynamic Programming with Generalized Ground Control Points［C］//Proceedings of IEEE Computing Society Conference on Computing V ision and Pattern Recognition.San Diego，USA：IEEE Press，2005：1075-1082.

［8］ Veksler O.Stereo Correspondence by Dynamic Programming on a Tree［C］//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego，USA：IEEE Press，2005：384-390.

［9］ Birchfield S，Tomasi C.Depth Discontinuities by Pixelto-Pixel Stereo［J］.International Journal of Computing Vision，1999，35（3）：269-293.

［10］ Da Feipeng，He Fu，Chen Zhangwen.Stereo Matching Based on Dissimilar Intensity Support and Belief Propagation［J］.Journal of Mathematical Imaging and Vision，2013，47（1/2）：27-34.

［11］ 張驚雷，王艷姣.基于圖像區域分割和置信傳播的立體匹配算法［J］.計算機工程，2013，39（7）：257-260，278.

［12］ Wang Daolei，Lim K B.Obtaining Depth Map from Segment-based Stereo Matching Using Graph Cuts［J］. Journal of Visual Communication and Image Representation，2011，22（4）：325-331.

［13］ 祝世平，楊 柳.基于自適應分水嶺的圖割的立體匹配算法［J］.光學學報，2013，33（3）：228-236.

編輯金胡考

Fast Stereo Matching Algorithm Based on Dynamic Programming

LUO Siqing，JIA Zishu
（College of Information and Computing Engineering，Northeast Forestry University，Harbin 150040，China）

A fast stereo matching algorithm based on dynamic programming is proposed to improve the efficiency of stereo matching to meet the real-time requirement and reduce the streaking phenomenon in a disparity map to increase matching accuracy.In this algorithm，the fast adaptive weight aggregation is firstly used to aggregate raw matching costs. Secondly，the stage of dynamic programming for computation of disparities is accelerated by two dimensional order tables.Finally，a disparity post processing method based on oriented filters is em ployed to reduce the streaking phenomenon in a disparity map.Experimental results show that the proposed algorithm can improve the efficiency of stereo matching and the matching accuracy.It can be applied in real time matching system.

stereo matching；dynamic programming；adaptive weight；fast aggregation；integral image

羅嗣卿，賈子書.基于動態規劃的快速立體匹配算法［J］.計算機工程，2015，41（11）：224-231.

英文引用格式：Luo Siqing，Jia Zishu.Fast Stereo Matching Algorithm Based on Dynamic Programming［J］.Computer Engineering，2015，41（11）：224-231.

1000-3428（2015）11-0224-08

A

TP391.41

10.3969/j.issn.1000-3428.2015.11.039

國家自然科學基金資助項目（71473034）。

羅嗣卿（1964-），男，副教授、碩士，主研方向：圖像處理，數據挖掘；賈子書，碩士。

2015-06-01

2015-07-21 E-m ail：luosq@nefu.edu.cn