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

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

0 引言

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

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

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

1 雙目立體匹配算法描述

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

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

1.1 特征融合初始代價(jià)計(jì)算

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

(1)

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

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

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

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

(2)

式中，C是代價(jià)值；a是SAD算法窗口的大?。籱、n表示Census變換窗口的大小。

1.2 匹配代價(jià)聚合

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

(3)

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

將各個(gè)路徑上的代價(jià)值相加即為該像素點(diǎn)的最終代價(jià)值，計(jì)算公式為

(4)

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

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

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

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

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

2.1 核函數(shù)內(nèi)部的并行

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

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

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

2.2 核函數(shù)外部的并行

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 測(cè)試平臺(tái)和測(cè)試數(shù)據(jù)集

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

表1 實(shí)驗(yàn)環(huán)境平臺(tái)介紹

3.2 立體匹配算法性能分析

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

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

表2 不同視差情況算法匹配耗時(shí)

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

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

表3 本文算法與其他加速算法的對(duì)比

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

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

(a)左圖像

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

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

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

(a)左圖

4 結(jié)論

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

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

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

3)算法在運(yùn)行高分辨率圖像(1241×376)時(shí)依然能夠達(dá)到很好的實(shí)時(shí)顯示性能(112.4fps)。同時(shí)，面對(duì)復(fù)雜的室外道路場(chǎng)景時(shí)，本文算法的準(zhǔn)確性和實(shí)時(shí)性也表現(xiàn)突出。