雙目視覺的匹配算法綜述

陳 炎，楊麗麗，王振鵬

(中國農業大學信息與電氣工程學院，北京 100083)

立體視覺是機器認識世界的重要手段。利用2幅圖像形成的視差可以計算得到像素點的深度，從而獲得三維的立體感知[1-2]。其工作流程主要包含4步：雙目標定、圖像校正、立體匹配和三維重建，而立體匹配是關鍵的步驟[3]。

立體匹配算法可以實現2幅圖像像素級的匹配，在該過程中，由于存在光照不均勻、遮擋、模糊以及噪聲等的影響，給提升匹配精度帶來了巨大的挑戰[4]。在雙目視覺的應用中，如自動駕駛、機器人等領域[5-6]，需要具備實時、準確的深度估計，因此對于系統的處理速度和精度提出了很高的要求。在以往的綜述性文章中[3,7-9]，研究者們對基于人工特征算法的原理及性能進行了總結，近年出現了許多基于深度學習的優秀算法，其在實時性和準確性上都有很大的提升。為了給相關研究人員提供參考，本文討論了各種立體匹配算法的發展，對基于深度學習和人工特征的算法特點加以分析，并給出了立體匹配算法的發展方向。

1 基于人工特征的匹配算法

立體匹配算法實現流程主要分為4步：代價計算、代價聚合、視差計算和視差求精[7]，流程如圖1所示。代價計算是對匹配區域像素點和參考區域進行相似度計算。由雙目相機的成像原理可知，人們只需要計算處于同一水平線上的左右圖像的像素相似值[10]，這一要求基于對極約束[11]來實現。極約束在立體匹配中起重要作用，其將對應關系的搜索限制為一行而不是整個圖像空間，從而減少了所需的時間和搜索范圍。代價聚合階段通過設置能量函數，將中心像素點的相似度值用某個范圍內的像素點代價計算結果替代。常用的相似性評價方法包括絕對差之和(sum of absolute difference, SAD)、平方差之和(sum of squared differences, SSD)、歸一化互相關(normalized cross correlation, NCC)、秩變換(rank transform, RT)和普查變換(census transform,CT)[9]。視差計算階段，可選取參考區域內相似度最高的像素點來計算。視差求精的目的是減少錯誤匹配的像素點，優化視差圖。優化步驟包括正則化和遮擋填充或插值[12]。

圖1 立體匹配算法流程Fig. 1 The framework of stereo matching algorithm

按照代價函數約束范圍的差別，立體匹配算法可分為全局匹配法和局部匹配法[8]。

1.1 全局立體匹配算法

全局匹配法的能量函數整合了圖像中的所有像素，以盡可能多地獲取全局信息。函數的表達式為

其中，Edata(D)為數據項，表示全部像素的匹配代價；Esmooth(D)為平滑項，表示相鄰像素對視差值的一致性；λ為權值參數，取正值；Ed為全局能量函數。根據Ed優化方法的不同，全局匹配法又可分為動態規劃法(dynamic programming, DP)、置信度傳播法(belief propagation, BP)和圖割法(graph cut, GC)[10]。

SUNG等[13]在求解Ed的過程中，應用極線間的相關性，構建了多路徑自適應的動態規劃求解方法。LI等[14]為了緩解動態規劃法引起的橫條紋效應，從左側和右側圖像分別提取改進的SIFT算法描述作為特征點完成匹配，有效地減少了這一現象。LEUNG等[15]使用四叉樹對動態規劃進行快速迭代，提高了算法的運行速度。BLEYER和GELAUTZ[16]使用圖割法，假設深度均勻變化，且深度變化邊界與圖像特征邊界重合，在初始視差段聚集形成一組視差層，通過全局成本函數的最小化選取最佳視差層，在大規模無紋理區域取得了良好的匹配效果。LEMPITSKY等[17]設計了多重標記的馬爾科夫隨機域圖形分割，提高了運行速度。WANG等[18]將圖形分割后的點分為可靠和不可靠點，在遮擋和無紋理區域的不可靠區域，使用可靠區域的迭代信息進行優化，結果比經典圖割法效率提高了90%。

1.2 局部立體匹配算法

局部匹配法將參考圖像分為若干圖像塊，再求取匹配圖像內預期相似度最高的圖像塊，生成深度圖[19]。局部匹配法與全局匹配法相比，能量函數只有數據項，而沒有平滑項，因此只能求取局部最優解[20]。算法原理如圖2所示，隨機選取左圖像中m×n的待匹配圖像塊，搜索右圖像視差(-d，d)的范圍，選取相似度最大的區域作為匹配單元。

圖2 局部立體匹配算法Fig. 2 Local stereo matching algorithm

局部匹配法帶來了效率上的提升，但由于缺乏全局參數，生成的視差圖不甚理想。為了提升匹配效果，在代價計算階段可以使用更優的方法。HIRSCHMULLER[21]提出了半全局匹配方法，主要包含2點：一是基于互信息匹配的分層計算，二是使用一維最優求解全局能量函數，半全局匹配在保證算法運行效率的同時大大提升了匹配效果。WANG和ZHENG[22]在構建局部能量函數的過程中引入區域間的合作競爭機制，獲得了良好的視差效果。HOSNI等[23]提出在局部匹配時采用分割算法選取待匹配區域，可以提升視差圖的質量，在分割選取待匹配區域時，以距離中心像素的遠近分配不同的權重，改善了分割效果。YOON等[24]針對各分割區域，提出了一個非線性的基于擴散的權重聚合方法，有效改善了遮擋區域匹配效果。ZHANG等[25]提出自適應匹配的概念，并開發了具有任意自適應形狀的支撐區域，實現了很高的匹配精度。

局部匹配算法在提升效果的同時，不可避免的會帶來效率上的降低。為此，DI等[26]在匹配中引入特征點選擇，為了進一步提高運算效率，匹配圖像中的特征點進行WTA匹配，非特征點只進行簡單驗證，提高了邊緣的匹配效果。MATSUO等[27]在匹配成本計算階段使用基于AD算法和Sobel算子的局部方法，通過多次迭代和JBF固定窗口生成了精確的視差圖。

2 基于深度學習的匹配算法

手工設計的人工特征，缺乏對上下文信息的獲取，經驗參數的選擇對匹配效果影響很大，不適合在復雜環境下應用。深度學習通過卷積、池化、全連接等操作，對圖像進行非線性變換，可以提取圖像的多層特征用于代價計算，對提取的圖像特征進行上采樣過程中設置代價聚合和圖像增強方法，從而實現端到端的圖像匹配。深度學習的方法更多地利用了圖像的全局信息，通過預訓練獲得模型參數，提高了算法的魯棒性。用于立體匹配的圖像網絡主要可分為金字塔網絡、孿生網絡(siamese network)和生成對抗網絡。

2.1 圖像金字塔網絡

為了保證輸入圖片尺寸的一致性，常常需要對圖片進行裁剪、縮放等操作。為了解決這個問題，HE等[28]在卷積層和全連接層之間設置空間金字塔池化層，將不同尺寸的圖片特征轉化為固定長度的表示，避免了卷積的重復計算，在圖像分割、圖像匹配等領域獲得了極大的提升效果。?BONTAR和LECUN[29]首次提出使用卷積神經網絡提取圖像特征用于代價計算，設置跨成本交叉的代價聚合，運用左右一致性檢查消除錯誤的匹配區域，其標志著深度學習開始成為立體匹配的重要手段。CHANG和CHEN[30]將金字塔池化模塊引入到特征提取中，使用多尺度分析和3D-CNN結構，有效地解決了梯度消失和梯度爆炸的問題，在弱紋理、遮擋、光照不均勻等條件下獲得了良好的效果。DUGGAL等[31]提出一種全新可微的Patch Match算法。首先獲得稀疏的視差圖，以減少代價計算的復雜度，再推算出剩余像素點的匹配范圍，并在KITTI和SceneFlow數據集上實現了每對圖片62 ms的匹配速度。TONIONI等[32]構建了模塊化、輕量化的神經網絡，網絡子部分可獨立訓練，使用無監督算法模型，使網絡可以不斷更新，在不降低質量的前提下，達到了每秒40幀的處理速度。GUO等[33]構建了分組代價計算，ZHANG等[34]設計了半全局聚合層和局部引導聚合層，都可以代替3D卷積層，提高計算效率。

2.2 孿生網絡

孿生網絡的概念最早由BROMLEY等[35]提出，其基本結構如圖3所示。通過設置2個權重共享的卷積神經網絡，分別輸入左、右圖像，通過映射函數將卷積得到的特征轉化為特征向量，衡量2個特征向量間的L1距離就可以擬合2張圖片的相似度。文獻[36]對原有的孿生網絡進行了改進，使用RELU函數和小卷積核加深卷積層，提高了匹配精度。文獻[37]使用孿生網絡從左右圖像提取特征，首先在低分辨率的代價卷積中計算視差圖，再使用分層細化網絡引入高頻細節，利用顏色輸入作為指導，可以生成高質量的邊界。LIU等[38]提出通過連接2個子網絡獲取多尺度特征。第1個子網絡由孿生網絡和3D卷積網絡構成，可以生成低精度的視差圖；第2個子網絡是全卷積網絡，將初始視差圖恢復成原始分辨率，2個網絡用金字塔池化進行連接。文獻[39]在低分辨率的視差圖上對深度不連續區域進行改進，在視差求精階段恢復成原始分辨率，取得了良好的效果。

圖3 孿生網絡結構Fig. 3 Siamese network structure

2.3 生成對抗網絡

在博弈論的基礎上，文獻[40]構建了生成式對抗網絡(generative adversarial networks, GAN)。網絡由生成模型和判別模型構成。生成模型學習樣本特征，生成圖像與原圖像相似，而判別模型則用來分辨“生成”圖片與真實圖片。這個過程不斷迭代運行，最終判別結果達到納什均衡，即真假概念均為0.5。PILZER等[41]提出了基于雙目視覺的GAN框架，其由2個生成子網絡和1個判別網絡構成。2個生成網絡在對抗學習中分別被用來訓練重建視差圖，通過相互制約和監督，生成2個不同視角的視差圖，融合后輸出最終數據。實驗表明，這種無監督模型在光照不均勻的條件下可以得到良好的效果。文獻[42]使用生成模型對遮擋區域進行處理，恢復得到了良好的視差效果。文獻[43]提出了深卷積生成對抗模型，可以通過相鄰幀獲得多幅深度圖，進一步改進了遮擋區域的深度圖效果。文獻[44]通過左右相機拍攝的2幅圖像，生成一幅全新的圖像，用于改進視差圖中匹配效果較差的部分，實驗表明，該方法對于光照強度較差的區域視差圖提升效果明顯。

3 算法測試與評估

3.1 算法測試框架

目前，立體匹配算法主要有Middlebury和KITTI 2個測評數據集，主要對算法的誤匹配率和運行時間進行準確的測評，并提供算法的排名。這2個數據集都構建了標準的視差圖，可用于計算誤匹配率。KITTI提供了統一的云平臺運行算法，保證了算法運行時間測評的硬件一致性。

Middlebury[7,45-48]由卡內基梅隆大學雙目實驗室創建，評價系統可以求取整張圖片、遮蔽和深度不連續區域的誤匹配率，并對提交的算法進行橫向對比排名。

2011年，德國的卡爾斯魯厄理工學院和芝加哥豐田技術研究所聯合創立了Kitti立體匹配測試平臺，并在2015年進行了更新[49-50]。數據集包含車載相機采集的市區、鄉村和高速公路圖像，旨在為自動駕駛提供技術準備和評估。

3.2 算法測試指標

目前，立體匹配算法的主要評價標準為視差圖精度和時間復雜度。視差圖精度的評價指標有誤匹配率，平均絕對誤差和均方誤差。誤匹配率的計算式為

其中，dc(x,y),dGT(x,y)分別為生成視差圖和真實視差圖的像素值；δd為評價閾值需設置，當差值大于δd時，此像素記為誤匹配像素；N為視差圖的像素總數。平均絕對誤差式為

均方誤差的計算式為

其中，N為所有像素的總數和非遮擋區域的像素數量。

部分算法的評價結果見表1。

表1 部分立體匹配算法評價結果Table 1 Some stereo matching algorithm evaluating results

3.3 2種不同類型的算法評估

基于人工特征的立體匹配算法，將數學原理的發展廣泛應用于實際需求，推動了雙目視覺系統在各行各業的應用。其擁有完整的數學模型和方便可調的參數，模型的可調整性和堆疊性較好，在魯棒性要求不高的應用場景中，通過多次實驗，可以得到良好的視差效果[8,51-52]。

基于深度學習的立體匹配算法，可以提取更多的圖像特征用于代價計算。相比于人工特征，深度學習可以獲取更多的上下文信息，提高算法的魯棒性，使用GPU加速技術，得到更快的處理速度[30]。在自動駕駛、機器人等領域，深度學習通過大量數據對網絡進行訓練，可以獲得高精度的視差圖，滿足了精度和實時性的要求[32]。

人工特征中的局部匹配算法誤匹配率較高，一般在10%~30%之間[7]，運行時間上最快的BM算法處理一對1432×1004大小的RGB圖片只需0.05 s，誤匹配率為32.45%[23]，精度和速度平衡性較好的SGBM算法處理一對相同大小圖片用時大約為0.53 s，誤匹配率為18.36%[21]。全局匹配算法的精度比局部匹配法要高，誤匹配率一般在10%左右[7]，但運行速度較低，處理圖像的時間較長。KITTI平臺中的精度排名最高的全局匹配算法誤匹配率為5.12%，運行時間達到65 s?；谏疃葘W習的匹配算法通過大量數據訓練可以達到很高的精度，KITTI平臺中精度排名最高的深度學習算法誤匹配率只有1.41%，在僅使用單核CPU運算的條件下運行速度為0.52 s，表現出深度學習強大的應用前景。對于基于人工特征和深度學習的匹配算法的特點總結見表2。

表2 算法特點對比Table 2 Comparison of algorithm features

4 結 論

立體匹配是實現雙目視覺的核心點，匹配的效果直接影響后續的目標識別、三維建模等工作。

基于人工提取特征的立體匹配算法由于數學解釋性高，堆疊性好等優點，目前廣泛應用于固定場景的識別。通過多種方法進行融合，可以取得良好的效果。

基于深度學習的立體匹配算法已成為自動駕駛、機器人領域的主流，目前要解決的難題主要分為以下3個方面：

(1) 提高算法的實時性和準確性。對于自動駕駛領域尤為重要，但目前算法在這2方面很難做到兼顧。

(2) 增強算法的魯棒性。深度學習算法受限于數據集的訓練，這使得算法對于農田、山地等陌生環境的匹配準確率有所降低。

(3) 提高算法的適應性?，F實世界中雨霧天氣下拍攝的圖像可能存在反光、模糊、噪聲等各種問題，這對算法提出了較高的要求。

人工特征的應用有助于深度學習網絡的完善，而近年來，強化學習、圖神經網絡等領域的不斷發展，也都為立體匹配算法的改進提供了參考。