特征融合的雙目立體匹配算法加速研究與實現

范亞博，王國祥，陳海軍，馮 威

(1. 西南交通大學地球科學與環(huán)境工程學院，成都 611756；2. 中鐵二院工程集團有限責任公司，成都 610031)

0 引言

立體視覺是機器認識世界的重要手段。立體匹配是雙目立體視覺技術中的一個重要環(huán)節(jié)，其通過左右兩幅圖像尋找匹配像素點，利用視差信息獲取空間物體距離拍攝位置的距離[1]。雙目立體匹配因其可靠、簡便的特點，使其在機器人導航、自動駕駛、三維重建及距離測量等領域得到了廣泛的應用。隨著圖像分辨率的提高以及實際應用場景中對數據信息實時性需求的愈發(fā)迫切，業(yè)界對立體匹配算法的實時性和準確性提出了更高的要求。

D.Scharstein等[2]對經典的匹配算法進行了總結，立體匹配算法通常分為以下4步：匹配代價計算、代價聚合、視差計算和視差優(yōu)化。目前，立體匹配算法根據算法特點可以分為局部、全局、半全局和基于深度學習的立體匹配算法[3]。全局算法通過最小化全局能量函數得到最優(yōu)視差，但計算復雜度較高，難以滿足實時性要求。局部算法精度劣于全局算法，但計算復雜度低，能滿足實時的要求。半全局匹配(Semi-Global Matching，SGM)算法結合局部和全局匹配算法的優(yōu)點，具有復雜度低、效率高和易于實現等優(yōu)點[4]。近來，卷積神經網絡(Convolutional Neural Networks，CNN)[5]被應用于立體匹配算法中，實現了更高的匹配精度，但CNN巨大的計算消耗和密集度，使其很難應用于硬件資源有限的實時立體匹配系統(tǒng)[6]。

Census變換算法憑借其易于并行的優(yōu)點成為主流的代價計算方法，但傳統(tǒng)的Census變換過于依賴中心像素點，且受支持窗口尺寸的影響[7]。為提高Census變換算法的性能，專家提出了很多改進策略，主要有：1)采用變換窗口內所有像素的加權平均值代替中心像素灰度值[8]；2)采用中心對稱Census變換以及稀疏Census變換[9]；3)改變Census變換窗口的尺寸和形狀；4)融合其他具有互補特性的代價計算方法[10-11]。這些算法雖然能達到很高的精度，但由于算法的計算復雜度較高，僅依靠中央處理器(Central Processing Unit，CPU)計算難以滿足實時性需求。近來，基于圖形處理器(Graphics Processing Unit，GPU)并行計算平臺對SGM算法進行并行加速取得了不錯的效果[1,12]。因此，利用GPU加速已成為實時獲取匹配信息的可行途徑。基于此，本文提出了利用統(tǒng)一計算設備架構(Compute Unified Device Architecture，CUDA)對雙目立體匹配算法進行并行加速，從而滿足實時性要求。

1 雙目立體匹配算法描述

算法具體實施步驟如下：首先，對校正后的圖像對進行直方圖均衡化預處理，在此基礎上，采用灰度差絕對值之和(Sum of Absolute Differences，SAD)融合傳統(tǒng)的Census變換以替代單一的匹配代價計算算法。利用四路徑SGM算法進行代價聚合，使用贏家通吃(Winner-Takes-All，WTA)優(yōu)化策略進行視差計算，最終通過左右一致性檢驗對遮擋點進行填充以及利用中值濾波剔除異常值，繼而得到優(yōu)化后的視差圖。基于CUDA加速的雙目立體匹配算法處理流程如圖1所示。

圖1 本文算法流程圖Fig.1 Flow diagram of SAD-Census algorithm

1.1 特征融合初始代價計算

SAD算法具體流程為：用i、j遍歷窗口W中每個像素，每進行一輪計算后d的數值增加1，以使右圖像中的窗口在視差范圍內移動。移動過程中，兩個子窗口計算的像素灰度差絕對值之和最小時，即找到了與左圖像窗口相匹配的像素塊，此時的d為視差值。SAD算法計算公式為

(1)

式中，IL(x,y)、IR(x,y)分別為左、右圖像中(x,y)位置的像素灰度值；d為視差范圍。

Census變換[13]是一種局部非參數變換算法，以某一像素點為中心取一個m×n(一般m、n為奇數)的變換窗口，通過將鄰域窗口內的像素灰度值與窗口中心的像素灰度值進行比較，將得到的布爾值連接成一個二進制比特串。對左、右圖像得到的兩個比特串進行異或運算，統(tǒng)計計算結果為1的個數，即為漢明距離(Hamming distance)，最后用漢明距離代替原來中心像素的灰度值。基于Census變換的初始匹配代價計算過程如圖2所示。

圖2 基于Census變換的初始代價計算示意圖Fig.2 Calculation of the initial costs based on Census transform

SAD算法匹配速度快，但對曝光度和光照變化較為敏感。Census變換是基于窗口內的相對亮度差，對整體的明暗變化并不敏感，在重復紋理區(qū)域易產生誤匹配。因此，將兩個算法進行融合不但可以提高匹配精度，而且對光照條件和曝光差異也可以保持良好的魯棒性。同時，SAD和Census變換都是基于局部窗口運算，每個像素之間互不影響，可以獨立運算，該特性使其可以設計多線程并行計算模型，但融合時需要考慮兩個算法在不同場景下的權重。為了使得到的初始代價值更可靠，將SAD和Census變換窗口的尺寸考慮進公式中，特征融合后的初始代價值計算公式為

(2)

式中，C是代價值；a是SAD算法窗口的大小；m、n表示Census變換窗口的大小。

1.2 匹配代價聚合

由于初始代價計算只考慮了局部窗口信息，易受噪聲的影響。為了獲得更準確的代價值，本文采用SGM算法[4]進行代價聚合。算法主要是將二維圖像的優(yōu)化問題轉換為多條路徑的一維最優(yōu)問題，使用從整個圖像各個方向聚合的路徑優(yōu)化來近似全局能量。聚合路徑的數量會影響視差圖的質量和算法的性能。對于像素點p，沿著某條路徑r在視差為d時的代價聚合公式為

(3)

式中，第一項為初始匹配代價值；第二項為路徑r上前一個像素點的最小匹配代價，P1和P2為視差不連續(xù)懲罰因子，且P1>P2；第三項是為了防止聚合代價值過大而減去上一像素的最小代價值。

將各個路徑上的代價值相加即為該像素點的最終代價值，計算公式為

(4)

1.3 視差計算與視差優(yōu)化

對代價聚合步驟得到的匹配代價，采用比較經典的WTA算法進行視差計算，即為每個像素選擇所有視差下代價值中最小的代價值所對應的視差作為最優(yōu)視差。

為了對視差計算步驟得到的視差圖做進一步的優(yōu)化處理，獲得更加準確和密集的視差圖，本文采用左右一致性檢驗有效地檢測遮擋點和誤匹配點，遮擋區(qū)域大多來自于背景，所以往往用背景視差值填充。由于圖像對本身存在噪聲以及填充后的視差可能存在異常值，采用中值濾波進行剔除，最終得到優(yōu)化后的視差圖。

2 雙目立體匹配算法并行加速

利用CUDA進行算法加速設計時，首先要最大程度地利用GPU多線程的優(yōu)勢；其次合理使用各種設備內存，優(yōu)化內存訪問速度；最后利用多個CUDA流同時啟動多個內核，實現核函數之間的并行加速計算。CUDA程序的并行層次主要分核函數內部的并行和核函數外部的并行。

2.1 核函數內部的并行

核函數內部并行的高性能很大程度上取決于對各種設備內存的合理使用。由于設備內存的帶寬可能是性能瓶頸，高效的CUDA代碼應該促進共享內存和寄存器內存上的數據重復利用。由于圖像對數據從CPU傳入GPU時需要占據較大的顯存空間，一般是存放在全局內存中。非連續(xù)的、重復的訪問全局內存，會使算法的性能大大下降。

算法優(yōu)化的思路如下：設圖像對的寬、高分別為W和H，匹配窗口的大小為m×n，視差范圍為d。計算SAD特征和Census變換時，每個線程對應一個像素點，為每個線程塊(Block)分配32×32個線程，考慮到線程塊的邊緣線程無法通過共享內存訪問相鄰Block的數據，因此相鄰Block之間需要一定的重疊，整張圖像被劃分為(W-[m/2])/(32-[m/2])×(H-[n/2])/(32-[n/2])個Block([*]表示向下取整運算)。左、右圖像每個線程塊中需要讀入共享內存的數據如圖3藍色矩形所示，紅色矩形表示當前操作要處理的線程塊，右圖中的紅色矩形在視差范圍內向右移動。利用同步函數進行處理后，線程塊內的所有線程都可以從共享內存中讀取數據進行計算。算法將大量重復、非連續(xù)的訪問全局內存改為重復訪問速度更快的共享內存，大大地提高了算法的執(zhí)行效率。

圖3 SAD和Census變換算法加速模型Fig.3 SAD and Census transform algorithm acceleration model

2.2 核函數外部的并行

要想使算法獲得更高的性能，需盡量減少主機與設備之間的數據傳輸以及在主機中進行的計算。因此，算法設計時把立體匹配算法比較耗時的4個步驟都放在設備中進行計算。該方式可以減少主機與設備之間數據傳輸帶來的額外開銷。同時，利用多個非默認CUDA流(stream)實現核函數之間的并行，進一步提高了設備利用率。

SAD算法和Census變換都是基于輸入的圖像對進行操作，兩者相互獨立，可以并行計算，但完成不同的CUDA流彼此間可能需要等待，因此需要同步操作。在核函數的執(zhí)行配置中必須包含一個流對象，核函數的調用方式為：kernel <<>>(函數參數)。實驗中發(fā)現，核函數之間的并行能夠縮短算法總運行時間。串行運行和多流并發(fā)執(zhí)行性能對比，如圖4所示。

圖4 串行運行和多流并發(fā)執(zhí)行性能對比Fig.4 Performance comparison of serial operation and multi-stream concurrent execution

考慮到每個像素的聚合代價值都是上、下、左、右4條路徑下的代價值累加的結果，在一條指定路徑下,需按順序依次執(zhí)行每個像素的代價聚合，這在一定程度上影響了算法的并行性。但每條路徑只是聚合方向不同，其他操作完全相同。因此，幾條路徑間是彼此獨立執(zhí)行的，所以，為每條路徑單獨設置一個核函數，利用共享內存且執(zhí)行同步操作，待所有核函數執(zhí)行完畢后，把各個路徑的代價值相加，得到最終的代價聚合值。

3 實驗結果與分析

3.1 測試平臺和測試數據集

為了充分測試算法的匹配精度和執(zhí)行效率，對實驗環(huán)境進行搭建，實驗環(huán)境和平臺信息如表1所示。采用Middlebury立體匹配算法測試平臺[14]提供的Venus、Teddy及Cones標準彩色圖像對算法進行實驗，以此來評價算法的準確性和實時性。

表1 實驗環(huán)境平臺介紹

3.2 立體匹配算法性能分析

本文采用速度評估標準和精度評估標準測試CUDA算法的優(yōu)化效率和匹配準確性。速度評估標準指算法的運行時間，精度評估標準是與Middlebury數據集提供的標準視差圖進行比較，計算出整張圖像全區(qū)域的誤匹配率。

在測試算法的效率優(yōu)化性能時，對實驗過程中的變量進行控制，將各圖像對的視差范圍依次設置為64像素和128像素。經過多次實驗，匹配效果最佳時，其他參數設置如下：SAD窗口尺寸為5×5，Census變換窗口尺寸為9×7，聚合代價路徑數為4。利用本文算法對不同分辨率的圖像對進行測試,結果如表2所示。

表2 不同視差情況算法匹配耗時

從表2可以看出，本文所提立體匹配算法對于不同分辨率的圖像基本上都能實現實時匹配。當圖像分辨率為384×288，視差范圍為64像素時，幀率最高可達到666.7fps；當圖像分辨率為1241×376，視差范圍為128像素時，幀率較低，可達到112.4fps。表2中的結果表明，基于CUDA加速的立體匹配算法具有較好性能，在處理較大圖像分辨率圖像時也可滿足實時性要求。

為了更全面地驗證本文算法的效率，將該算法與其他加速算法進行比較。雖然不同算法的運行環(huán)境均不相同，但平臺的性能差異相差不大。實際上算法自身的并行性、算法的優(yōu)化策略以及算法中涉及的一些參數都會影響運行環(huán)境平臺的性能。在圖像分辨率和視差范圍相同的情況下比較算法的測試結果，如表3所示。

表3 本文算法與其他加速算法的對比

由表3可知：本文所提算法的實時性優(yōu)于其他算法，在NVIDIA GeForce GTX 1650平臺上實現了非常高的實時性能。處理450×375圖像分辨率，視差范圍為64時，最高可達384.6fps的匹配效率，比原始的SGM算法快687倍。與稀疏Census變換算法相比，可實現5.1倍的加速比。除去平臺自身性能優(yōu)勢，加速效果也很不錯。

為了驗證算法的匹配精度，圖5所示為算法的測試結果。由于Venus圖像的紋理豐富，生成的視差圖邊緣較準確；而對于弱紋理較多的Teddy圖像，部分葉子連成一體，但能較大程度上恢復出玩具熊和房子的輪廓；Cones視差圖中圓錐和面具模型的輪廓都比較清晰，邊緣部分略有噪點，這進一步說明融合算法的準確性得到提高。

(a)左圖像

為了更好地評估生成視差圖的效果，圖6所示為各圖像在不同算法下的全區(qū)域誤匹配率。通過計算所有區(qū)域下各個測試集圖像的誤匹配率的平均值，得出本文算法的平均誤匹配率為10.4%。由圖6也可知，本文算法的立體匹配精度高于Edge-Gray算法[16]和V-SAD算法[17]，平均誤匹配率分別下降了8.05%和3.22%，并且Edge-Gray算法和V-SAD算法在執(zhí)行高分辨率圖像時，實時性效果遠不如本文所提算法。

圖6 不同算法的視差圖誤匹配率Fig.6 Disparity map mismatching rates of different algorithms

此外，為了進一步驗證算法在復雜道路場景下的準確性和實時性，本文測試了KITTI 2012數據集中自動駕駛場景下的圖像，得到的視差圖如圖7所示(未對孔洞插值補全)。面對不同的光照和遮擋環(huán)境，本文算法得到的視差圖可以清楚地看到路上行人、街道兩旁樹木以及汽車的輪廓。由上文可知，對于1241×376分辨率的室外道路圖像，在128視差范圍下能達到112.4fps的實時性能。由此可以得出該算法在復雜的室外道路場景下仍具有較好的適用性。

(a)左圖

4 結論

針對傳統(tǒng)雙目立體匹配算法計算復雜度高且難以滿足實時性要求的問題，本文提出了將SAD和Census變換特征融合的結果作為初始匹配代價，并對立體匹配算法耗時的4個步驟設計了基于CUDA的并行計算加速模型。算法分析與實驗結果表明：

1)利用SAD和Census變換特征融合計算代價可以改善Census變換過于依賴中心像素點帶來的影響，并且它們都是基于局部窗口運算，每個像素之間獨立運行，使其可以設計并行計算模型。

2)數據傳輸過程中，最大化地利用共享內存、寄存器內存以減少全局內存的讀取次數，使用多個CUDA流操作實現了不同核函數之間的并行。將本文算法與相關加速算法進行對比實驗，結果表明，所提算法平均誤匹配率下降了8.05%，且比原始SGM算法快687倍。

3)算法在運行高分辨率圖像(1241×376)時依然能夠達到很好的實時顯示性能(112.4fps)。同時，面對復雜的室外道路場景時，本文算法的準確性和實時性也表現突出。