雙目視覺的立體匹配算法研究進展*

趙晨園，李文新，張慶熙

蘭州空間技術物理研究所，蘭州730000

1 前言

三維物體識別技術能提取目標物體的三維特征信息，進而對場景中一個或多個目標進行識別或分類，相較于傳統二維圖像識別更能準確全面地豐富物體的三維信息，從而進行更高維的特征提取以便處理更復雜的任務[1]，三維物體識別技術成為近年來計算機視覺領域的研究熱點之一，被廣泛應用于智能機器人、維修檢測、無人駕駛、軍事偵察等領域[2]。

雙目立體視覺技術模擬人眼獲取相同點產生的視差從而進行目標三維重建，獲取三維圖像[3]。與結構光傳感器、TOF（time-of-flight）相機等獲取深度圖像方式相比，雙目立體視覺技術對硬件、成本要求更低，所獲取的深度圖像更加密集、精確；與單目視覺深度估計相比，雙目立體視覺技術計算復雜度更小，系統實時性更高。雙目立體視覺技術更加適用于實際生產生活中的三維物體信息采集，有著巨大的發展空間和良好的應用前景[4]。

立體匹配是雙目立體視覺技術中的核心算法，旨在通過尋找雙目相機所獲取的兩張圖像中的同名點從而構建視差圖，一個良好的立體匹配算法直接決定三維重建的效果[5]，建立合適的立體匹配算法是提高基于雙目立體視覺技術的三維物體識別效果的關鍵。

本文在通過分析總結現階段主要的立體匹配算法的基礎上，展望未來立體匹配算法的發展方向，旨在為今后相關領域人員開展立體匹配算法的研究提供思路與參考。

2 研究現狀

立體匹配的目的是從兩張圖像中尋找同名點從而根據其視差計算出該點的深度信息[6]。Scharstein等[7]認為立體匹配算法通過匹配代價計算、代價聚合、視差計算/優化及視差校正四個過程實現。匹配代價是利用相似性函數計算左右圖中像素點的代價，常用的相似性度量方法有絕對差值平方和（sum of absolute differences，SAD）、零均值絕對誤差和（zero sum of absolute differences，ZSAD）、Census 變換（Census transform，CT）等；代價聚合通過鄰接像素間的聯系，用一定方法，對代價矩陣進行優化，以處理圖像在弱、無紋理區域中的代價值無法準確配對的問題，降低異常點的影響，提高信噪比；視差計算/優化采用“贏家通吃”（Winner-takes-all，WTA）原則，在視差搜索范圍內選擇代價值最小的點作為對應匹配點，并確定該點視差；視差校正是對匹配好的視差圖進行后處理，以解決遮擋點視差不準確、噪聲點、誤匹配點等問題，常用方法有左右一致性檢查（left-right check）、中值濾波（median filter）、局部一致性約束（locally consistent）等。立體匹配算法根據算法特點可以分為局部、全局、半全局和基于深度學習的立體匹配算法。

2.1 局部立體匹配算法

局部立體匹配算法又稱為基于滑動窗口的圖像匹配方法，以待匹配像素的局部窗口內的像素為約束，通過在另一個視角中水平移動窗口，計算每個視差窗口內所有像素的匹配代價，利用贏家通吃原則，選擇最小匹配代價值作為該點視差。局部立體匹配算法一般包含匹配代價計算、代價聚合和視差計算/優化三個步驟。

Kitagawa等[8]提出了基于高斯差分響應（response of the difference of Gaussian，DoG）的引導濾波匹配方法，使用SAD 和相鄰像素梯度值的加權和來計算匹配代價，根據每個像素選擇適當窗口，利用引導濾波對代價矩陣進行平滑聚合處理，時間效率高；Han等[9]改進了快速自適應窗口匹配算法，采用SAD計算顏色特征、梯度特征和紋理特征信息并分配不同權重作為匹配代價；Chai等[10]針對圖像有大量噪聲或視差不連續情況下存在虛假匹配的問題，將SAD 和Census 變換結合作為相似性度量函數進行立體匹配，建立了基于自適應窗口的引導濾波法進行代價聚合，結果表明該算法能提高匹配精度，對光畸變和邊緣信息也有較好的魯棒性；Hong 等[11]對基于加權引導圖像濾波（weighted guided image filtering，WGIF）的局部立體匹配代價聚合方法進行改進，通過基于局部方差的自適應權重法重新構造代價濾波器，該算法效果優于其他濾波算法；Hamzah等[12]提出了iSM算法，在固定窗口下利用幅度差的梯度匹配和（sum of gradient matching，SG）計算匹配代價，利用自適應權重的迭代引導濾波（adapive support weight with iterative guided filter，ASW-iGF）算法進行代價聚合，采用WTA方法確定最終視差并用聯合加權導頻濾波器（joint weighted guided filter，JWGF）對視差進行后處理以降低噪聲；Oussama等[13]利用改進的Census變換計算匹配代價，提出了基于交叉聚合的自適應代價聚合方法（cross-based aggregation method），算法能改善弱紋理區域誤匹配率高的問題。

Table 1 Effects of different local stereo matching algorithms表1 不同局部立體匹配算法效果

表1 是不同局部立體匹配算法的效果，表1 中，Middlebury為室內有遮擋物體圖像數據集，KITTI 為室外道路場景數據集，兩數據集均采用誤匹配率作為算法評價標準，誤匹配率計算公式如下：

式中，err為誤匹配率，N為圖像總像素個數，dC(x,y)是由算法得到的視差值，dT(x,y)為Ground truth視差值，δd為誤差閾值，大于該閾值表示該點沒有匹配成功，取值在0.5～4.0 之間。使用Middlebury 數據集能分別計算視差不連續區域disc、非遮擋區域nonocc和全區域all 的誤匹配率；使用KITTI 數據集能計算背景區域bg 的誤匹配率、前景區域fg 的誤匹配率和全區域all誤匹配率。本文表中誤匹配率為圖像的全區域all平均誤匹配率。

局部立體匹配算法通過滑動窗口，利用像素周圍的局部信息對處于同一極線約束的所有點計算匹配代價，從而找出同名點，相對于全局立體匹配算法，該匹配算法具有計算復雜度低，時間效率高的優點，但由于未充分考慮圖像的全局信息而導致其很難區分無、弱紋理區域的不同像素點，且對深度不連續區域存在魯棒性差的缺點。因此，研究者通過組合不同相似性度量方法及選用不同代價聚合方法以提高匹配精度。由表1可知，局部算法的平均誤匹配率為7.01%；Kitagawa 等[8]提出的算法在Middlebury數據集中誤匹配率為4.94%，匹配效果最好。該算法改善了傳統局部算法選擇的匹配窗口和聚合濾波窗口對不同區域適應性差的缺點，利用自適應窗口的引導濾波法進行代價聚合，為邊緣區域像素點選擇較小尺寸窗口，為無紋理區域選擇較大尺寸窗口，相比于傳統引導濾波方法，提高了匹配精度。

2.2 全局立體匹配算法

全局立體匹配算法又稱為全局能量函數最小法，該方法將局部匹配代價和平滑約束條件組合在一起構成全局代價函數，通過不斷迭代優化分配的視差值，直到全局能量函數最小化。全局立體匹配能量函數定義如式（2）所示。

式中，E(D)為全局能量函數；E(data)(D)為數據約束項，用于判斷像素點之間的相似性；E(smooth)(D)為相鄰點的平滑約束項，用于判斷相鄰點之間的連續性；λ為參數因子，用于數據項和平滑項的平衡。全局立體匹配算法通常包括匹配代價計算、視差計算/優化與視差校正三個步驟。經典的全局立體匹配算法有動態規劃[14]、圖割[15]和置信傳播法[16]。

Hallek等[17]利用零均值絕對差和（ZSAD）計算匹配代價，并用動態規劃法進行優化，建立了具有實時性的立體匹配系統；Cheng等[18]提出了粗加精的匹配思想，該方法為在建立新的全局邊緣約束（global edge constraint，GEC）基礎上，利用局部算法估計最優支持窗口，建立初始視差圖，并根據匹配結果構造數據項，將GEC 作為平滑約束納入全局能量函數中并利用圖割法進行最小化處理得到精確視差圖；San等[19]為了實現對無紋理區域更好的視差估計，將爬山算法（hill-climbing）應用于圖像分割，利用SIFT（scaleinvariant feature transform）和SAD融合的算法計算代價值，利用圖割法對能量函數進行最小化處理獲得最終視差；Ma 等[20]將絕對強度差（absolute intensity differences，AD）、絕對梯度差（absolute gradient differences，GAD）和基于梯度Census 變換（gradient-based Census transform，GCT）相似性度量方法組合成魯棒性強的代價組合指數函數，計算匹配代價，采用互一致性檢驗準則和隨機樣本一致性算法組成的“MCRANSAC”的視差優化方法濾除異常值，用置信傳播法優化能量函數得到較為精確的視差圖；Wang 等[21]將SAD 和Census 變換組合形成匹配代價，將其轉化為能量函數中的數據項并利用置信傳播法進行迭代推理獲取視差圖，利用中值濾波和交叉檢查濾波進行后處理優化，所選用的數據項在無紋理區域具有魯棒性；Lee等[22]將Census變換和梯度圖像匹配組合計算像素的初始代價，提出了一種新的自適應權重重啟隨機游走（adapt random walk with restart，AWR）視差優化算法，該算法復雜度較低；Tan等[23]利用像素點在0°、45°、90°和135°四個方向上的值擬合多項式函數，利用多項式函數計算該點視差值并作為數據項，利用置信傳播法進行視差優化，結果表明該算法在高度傾斜的曲面上具有良好的匹配性能，雖然增加了算法的復雜度，但算法具有高并行性，便于GPU加速；Shahbazi等[24]用內稟曲線（intrinsic curves）的幾何特征形成基于方向的稀疏視差假設值并將其作為遮擋項，非參數Census變換作為數據項，集成為全局能量函數，減少了由于圖像像素遮擋而產生的誤差，匹配率提升了2%。

全局立體匹配算法通常無代價聚合步驟，是通過不斷迭代，利用全局能量函數為每一個像素點進行視差分配，使得能量函數最小，全局算法獲得的視差值更接近真實視差值。誤匹配率的定義不是考察像素點對是否正確匹配，而是計算該點視差與真實視差的差值是否小于誤差閾值，全局算法平滑了相鄰像素點之間的視差值，故其對視差連續及無、弱紋理區域匹配效果較好，匹配精度高，但不斷的迭代增加了算法復雜度。為了提高識別精度和運行效率，研究者們通常對傳統全局算法進行優化以提高識別精度或更換加速平臺以提高時間效率。從表2 可以看出，全局算法的平均誤匹配率為5.75%，比局部算法低1.26 個百分點，其中以Ma 等[20]的算法匹配效果最好，在Middlebury數據集中誤匹配率為4.21%。該算法在改進能量函數并將置信傳播法作用于區域而非像素以減小算法復雜度的基礎上，結合局部自適應窗口的多相似度融合方法和全局置信傳播方法，有效降低了誤匹配率，但匹配代價的計算較為復雜，導致運行時間較長。利用局部和全局思想結合的方法取得最優視差圖，給研究者提供了一個很好的思路。

2.3 半全局立體匹配算法

半全局立體匹配算法（semi-global matching，SGM）是近年來的研究熱點之一，2005 年由Hirschmüller[25]提出，與全局匹配方法不同，該算法將二維圖像的優化問題轉化為多條路徑的一維優化問題，計算像素點的匹配代價，聚合來自8 個或16 個方向的路徑代價，并利用WTA 方法計算視差。半全局立體匹配算法一般步驟包括匹配代價、代價聚合、視差計算/優化和視差校正。半全局與全局立體匹配算法均采用最優化能量函數的思想，通過最小化全局能量函數估計最佳視差值，半全局方法采用的能量函數如下：

Table 2 Effects of different global stereo matching algorithms表2 不同全局立體匹配算法效果

式中，E(D)為半全局能量函數；p是目標像素點，q為像素p鄰域中的一點，Dp和Dq分別為兩點視差，C(p,Dp)為視差圖D下所有像素點的匹配代價，P1是平滑約束懲罰因子，是對相鄰像素視差等于1(|Dp-Dq|=1)時添加的懲罰因子；P2是邊緣約束懲罰因子，是對相鄰像素視差大于1(|Dp-Dq|＞1)時添加的懲罰因子，P2＞＞P1。

Banz 等[26]根據數據流流入行緩存的方式，利用秩變換進行匹配代價計算，將8路代價聚合改為4路并行代價聚合，實現了對FPGA（field programmable gate array）的算法優化。在最大視差為128像素和時鐘頻率39 MHz 情況下吞吐量為37 frame/s（640×480像素），算法具有實時性；Li等[27]利用Census變換計算匹配代價，采用圖像金字塔對每一層進行8 方向SGM處理，建立了一個由粗到精并行立體匹配算法，減少了匹配時間；Juarez等[28]利用GPU 對4路徑實時SGM 算法進行并行加速，將其應用于實時輔助駕駛系統，吞吐量為42 frame/s（640×480像素）；Wang等[29]針對現有立體匹配算法對弱紋理和視差不連續區域匹配精度低的問題，提出了匹配代價組合的SGM 方法，用自適應權重SAD 和GAD 的組合計算匹配代價，用8路徑的半全局方法進行代價聚合；Chai等[30]提出了基于最小生成樹（minimum spanning tree，MST）的新型SGM 方法，該算法根據4 個規劃路徑上的像素點計算匹配像素點的代價值，根據葉節點到根節點和根節點到葉節點兩個步驟之和計算代價聚合。視差圖像在圖像邊緣產生的誤匹配點比經典SGM算法少；Li等[31]利用灰度和梯度的融合信息計算匹配代價，利用互信息進行匹配代價的相似性度量，采用5條自適應加權路徑進行代價聚合，匹配精度提高了1.74%，采用尖峰濾波器（spike filter，SPF）和左右一致性檢查進行視差校正，系統吞吐量為197 frame/s（1 280×960 像素）；Rahnama 等[32]針對傳統算法在FPGA上實現會產生條紋效應的問題，利用Census變換計算代價，改進能量函數并將8路徑代價聚合變為4 個相鄰像素點的聚合，利用中值濾波法降低噪聲，系統吞吐量為71 frame/s（1 242×375像素），系統功耗低，適用于低功耗的實時性系統。

由式（3）的算法能量函數可知，SGM算法實質上是全局算法的一種改進，綜合了全局和局部算法的優點，利用多條路徑下的一維代價聚合問題來代替全局能量函數的最優問題，即將全局算法中的視差計算步驟簡化并作為代價聚合步驟。算法在保留了匹配精度的同時，減小了計算復雜度，但匹配效果依賴于選取路徑數目，算法對無、弱紋理區域的匹配效果與路徑聚合數目成正比。另外，SGM 在利用硬件加速時往往受限于運算機制，例如算法在FPGA上實現時，為保證算法實時性而舍棄像素下半部分未讀取路徑的代價聚合，造成條紋效應，影響匹配精度。因此，如何在減少聚合路徑前提下，通過優化算法保證匹配精度是SGM 在硬件平臺上實現的難點之一，目前主要通過改變不同路徑及添加權重以提高算法精度。在算法速度方面，研究者們利用GPU和FPGA并行計算的特點，通過增大空間復雜度、減小時間復雜度以實現實時性。由表3可知，半全局算法平均誤匹配率為7.09%，比全局算法高1.34 個百分點，但利用FPGA或GPU硬件加速平臺的算法運行時間均在1 s以下，可用于實時性要求高的系統中。

Table 3 Effects of different semi-global stereo matching algorithms表3 不同半全局立體匹配算法效果

2.4 基于深度學習立體匹配算法

基于深度學習的立體匹配算法是近年來興起的一種算法，可分為兩類，分別是深度學習與傳統算法相結合的立體匹配算法和端到端的深度學習立體匹配算法。深度學習與傳統算法相結合的算法是將深度學習算法應用于傳統匹配算法的步驟中，讓計算機自動學習匹配代價、代價聚合等，減少了人為設計造成的誤差。基于端到端的方法直接以左右兩張圖像為輸入，視差圖作為輸出，利用深度算法學習原始數據到期望輸出的映射。

在深度學習與傳統算法相結合的立體匹配算法方面，Zbontar 和LeCun[33]首次以成對小圖像塊、標注圖像（ground truth）為輸入，匹配代價為輸出，訓練有監督學習的匹配代價卷積神經網絡（matching cost convolutional neural network，MC-CNN），使用交叉代價聚合方法聚合匹配代價，通過SGM 方法實現平滑性約束，對遮擋區域進行左右一致性檢驗，通過中值濾波器和雙邊濾波獲得最終的視差圖；Chen 等[34]針對現有監督學習方法普遍存在過擬合問題，提出在MC-CNN 基礎上通過卷積層中選擇2×2 小尺寸卷積核并在決策層中利用dropout正則化方法的圖像塊匹配代價算法，結合SGM 方法進行視差優化并采用左右一致性檢驗等多種方法進行視差校正，算法具有更好的泛化能力；Yan等[35]提出了對MC-CNN得到的視差圖進行優化的后處理方法，該方法用馬爾科夫推理估計像素點和遮擋區域的平均視差以進行全局優化，用貝葉斯推理進行視差優化達到局部優化，算法效率高；Williem 等[36]提出一種基于深度卷積網絡的自我引導的代價聚合方法，并應用于局部立體匹配。該方法的深度學習網絡由動態權值和下降濾波兩個子網絡組成，網絡中結合特征重建損失和像素均方損失函數以保持邊緣特性；Lee等[37]針對精確立體匹配算法占用內存多的問題，提出具有高效且魯棒的置信度參數SGM（confidence-based parametric SGM，cbpSGM）算法，該算法對8路徑SGM算法進行改進，組合高斯混合模型（Gaussian mixture model，GMM）參數聚合與eSGM[38]中兩步聚合策略進行代價聚合，引入隨機森林框架作為代價優化方法，算法內存低，為傳統SGM的3%以下。

在端到端的深度學習立體匹配算法方面，Mayer等[39]于2016年首次將端到端神經網絡模型應用于立體匹配領域，建立了大規模合成數據集并訓練端到端卷積神經網絡DispNet，該算法利用自動編碼-解碼結構，直接輸出視差圖，無后處理步驟，精度高；Pang等[40]提出了一種新的二級級聯結構CNN（convolutional neural network），第一級通過增加額外的上卷積模塊對DispNet改進使視差圖具有更多細節；第二級用串聯殘差學習網絡（cascade residual learning，CRL）進行視差細化，利用多個尺度上產生的殘差校正視差；Kang 等[41]針對算法在深度不連續和低紋理區域方面匹配效果不佳的問題，提出改進DispNet神經網絡的學習算法，該算法用擴展卷積建立上下文金字塔特征提取模塊，構建基于圖像塊的匹配代價計算方法，將視差梯度信息引入損失函數進行后處理以保持局部細節；Brandao等[42]在Siamese神經網絡中使用反卷積提取目標像素周圍特征并進行特征點匹配，優化特征聚合算法，將學習網絡變為淺層架構，降低了算法復雜度；Nguyen等[43]為解決弱紋理區域的誤匹配問題，提出廣域上下文學習網絡和帶空間擴散模塊的堆疊式編碼-解碼二維CNN，該網絡利用擴展卷積層和空間金字塔池化層提取全局上下文信息，利用提取的信息構成匹配代價，對匹配代價進行上下文代價聚合，算法無需后處理。

深度學習算法在立體匹配算法中的應用取得了巨大突破，其算法精度普遍超過傳統立體匹配算法。針對傳統方法在算法和參數選擇上依賴經驗、與實際問題適應性差、效率低下的問題，深度學習與傳統方法相結合的匹配方法通過在傳統算法中嵌套一個或多個深度學習算法，利用神經網絡自主學習匹配代價或代價聚合以達到比傳統方法更好的效果，通過直接學習原始圖像，使得模型具有更好的泛化能力，算法難點在于算法與算法之間的契合問題；基于端到端的神經網絡利用單個神經網絡解決多步驟問題，規避了多步驟所產生的誤差累積，避免了模塊與模塊間相互影響和人工設計的淺層表達產生的誤差，將立體匹配完全轉化為定位回歸問題，充分利用卷積神經網絡的特征提取能力和模型表達能力，自發地從圖像數據中學習約束表達，是未來的發展趨勢之一。但基于端到端的神經網絡算法往往需要大量的數據集進行訓練以增強模型泛化能力，且算法多為卷積計算，因此相比于非端到端的神經網絡，端到端神經網絡在有足夠充足的訓練集情況下具有更好的收斂性和泛化能力，但也會提高算法的時間復雜度。

Table 4 Effects of different stereo matching algorithms based on deep learning表4 不同基于深度學習的立體匹配算法效果

從表4可以看出，基于深度學習的算法平均誤匹配率為4.50%，優于局部、全局、半全局算法；深度學習與傳統方法結合的算法均利用CPU 進行實現，而端到端算法均通過GPU 并行加速實現，端到端的深度學習算法比深度學習與傳統方法結合的算法時間效率平均提高66倍，且匹配精度沒有明顯下降。

3 展望

近年來，雙目立體視覺技術在工業上表現出巨大的應用前景和發展潛力，成為研究者們探索的熱點之一，在立體匹配方面不斷涌現出新的算法，推動匹配算法向高精度、實時性方向發展。

（1）現有研究的立體匹配算法大都依靠Middlebury、KITTI等數據集對算法進行學習、訓練和驗證，沒有利用實際生產生活中的圖像，實際拍攝的圖像往往存在著無、弱紋理及反光、遮擋等區域。針對該問題，雖然Ran和Xue等[44-45]進行了有益的探討，改善了弱紋理區域誤匹配問題，但提高了算法復雜度。未來提出對弱匹配區域具有魯棒性及實時性強的立體匹配算法仍具有重要意義。

（2）現有的研究普遍關注提升算法的匹配精度，但利用Middlebury 數據集建立的匹配算法中精度前十名的算法運行時間均超過120 s，不滿足計算實時密集型任務的要求[35]。在傳統立體匹配算法方面，可通過多種匹配代價算法融合，同時適當減小匹配窗口或聚合路徑，在保證算法準確度情況下，減小算法復雜度；在深度學習算法方面，可通過優化卷積核，將深度學習算法與傳統算法進行融合以減小對大量數據集的依賴，同時也要防止算法過擬合。此外，FPGA 和GPU 具有流水線并行計算的能力和可對大規模數據流進行并行處理的優點，未來利用FPGA和GPU硬件加速平臺實現算法并對其進行優化將是解決圖像實時匹配問題的一種思路。

（3）當前算法處理的圖像分辨率普遍較低，許多算法利用1/4精度或半精度圖像進行算法驗證，無法達到應用要求。隨著計算機視覺技術的發展，高分辨率圖像的立體匹配算法將成為一種發展趨勢。下一步，在保證實時性前提下，提出高精度、高分辨率的立體匹配算法是未來發展方向。

（4）現有研究表明，深度學習算法對立體匹配的精度較高，成為近年來的熱門研究方向之一，也是未來的發展方向，其中的深度學習與傳統立體匹配算法用來優化立體匹配中匹配代價、代價聚合等，但模型之間存在著難以融合的缺點。下一步，將深度學習算法與傳統算法并行處理，結合使用，解決算法與算法之間的調優問題以進一步提升模型的泛化能力；端到端的深度學習方法匹配精度高，一個神經網絡就可完成多個匹配步驟，將被越來越多地應用于立體匹配領域。因此，如何利用像素上下文信息，充分發揮卷積神經網絡的作用，并減小內存消耗，是研究者需要考慮的問題。

4 結束語

立體匹配是雙目立體視覺技術中實現三維重建的關鍵，對雙目立體視覺技術的應用及發展有著決定性的意義。下一步立體匹配算法的研究重點為解決在無、弱紋理區域匹配精度不佳的問題，開發基于深度學習的高精度立體匹配算法和具有高實時性、可實際用于生產需要的立體匹配算法。本文對提高雙目立體視覺技術中立體匹配的水平具有參考價值。