一種改進的實時半全局立體匹配算法及硬件實現

趙晨園，李文新，張慶熙

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

0 概述

立體匹配是從雙目或多目圖像中尋找同名點并根據其視差計算場景深度信息的過程，是近年來計算機視覺領域的研究熱點之一?，F場可編程門陣列（Field Programmable Gate Array，FPGA）具 有成本低、開發周期短、并行計算的優點，是嵌入式應用的設計平臺?；贔PGA 的立體匹配技術可以實現實時獲取目標場景的深度信息，因此被廣泛應用于智能機器人、無人駕駛、目標跟蹤、三維重建等領域［1-2］。立體匹配算法主要分為局部［3］、全局［4］、半全局［5-6］、基于深度學習［7］算法。全局和基于深度學習的算法精度高，局部和半全局算法實時性強。半全局立體匹配（Semi-Global stereo Matching，SGM）算法是全局算法的改進，其將二維圖像的優化問題轉化為多條路徑的一維優化問題，在保留算法精度的基礎上減小了計算復雜度，算法并行度高，適用于資源占用小、實時性要求高的嵌入式系統。

SCHARSTEIN 等［8］將立體匹配算法分為匹配代價計算、代價聚合、視差計算與優化、視差校正4 個階段，其中匹配代價計算通過相似性函數計算左右兩點的代價值，是立體匹配算法的核心步驟。傳統匹配代價計算方法有灰度差值平方和（Sum of Squared Differences，SSD）［9］、零均值絕對誤差和（Zero Sum of Absolute Differences，ZSAD）、Census 變換（Census Transform，CT）［10］等。Census 變換對圖像局部區域進行編碼，具有結構簡單、相對次序性良好的優點，在立體匹配算法中應用廣泛，但該算法存在過度依賴中心點像素值及對噪聲敏感的缺點。文獻［11］利用十字交叉窗口內各像素灰度值的平均值代替中心像素點，增強了算法魯棒性；文獻［12］利用Census 變換融合其他相似性度量方法計算匹配代價，解決了匹配窗口選擇難的問題；文獻［13］將灰度絕對差值（Absolute Differences，AD）與Census 變換結合計算匹配代價，改善了相似紋理區域的誤匹配問題。然而，Census 變換對無、弱紋理區域匹配效果欠佳的問題仍未得到有效解決。左右一致性檢驗（Left-Right Check，LRC）是利用相同點視差相同的原理來實現對遮擋點的檢測，是視差校正常用算法之一，但該算法需要同時獲取左右兩幅圖像的視差圖，占用資源量大，不適用于小型嵌入式系統中。

本文提出一種改進的基于FPGA 的實時半全局立體匹配算法，以提高實時立體匹配精度。在匹配代價計算階段，利用帶權重的4 方向梯度絕對值差（Absolute Differences of Gradient，ADG）和改進 的Tanimoto 距離相結合的算法，以提高弱紋理和邊緣區域的匹配精度；在代價聚合階段，采用4 路徑并行結構的SGM 算法；在視差選擇階段，采用贏家通吃策略（Winner-Takes-All，WTA）；在視差校正階段，采用閾值檢測（Threshold Detection，TD）算法代替LRC算法，以減少硬件資源需求。

1 算法描述

1.1 匹配代價計算

傳統基于FPGA 平臺的立體匹配算法多利用Census 變換［11］作為匹配代價進行計算，根據周圍像素值與中心像素值的大小關系獲得比特串，利用Hamming 距離計算匹配代價。Census 變換公式見式（1）。

其中：ICensus(p)為Census 變換結果；D為I(p)點周圍鄰域；I(p)為中心像素灰度值；I(q)為I(p)周圍像素點灰度值；?表示按位連接。當I(p)>I(q) 時，ξ[I(p),I(q)]為1，當I(p)

其中：DH(a,b)為Hamming 距離計算結果；N為窗口大??；ai和bi為左右圖經過Census 變換獲得的比特串；⊕為按位異或操作。

Census 算法對灰度變化范圍大的區域匹配效果較好，但對灰度變化小的弱紋理區域匹配效果較差，且對中心點像素值依賴性強。目前對此改進的方法主要有更換中心像素點［12，15］、多匹配代價融合［13，16］、選用自適應窗口［17-18］等，算法對中心點的依賴性得到改善，但仍存在對弱紋理、邊緣區域的像素點區分度低、誤匹配率高的缺點。

本文引入Tanimoto 距離替代傳統Hamming 距離作為匹配代價計算方法，Tanimoto 距離計算公式見式（3）。

其中：DT(a,b)為Tanimoto 距離；a和b為像素點比特串。像素點p在視差為d時的Tanimoto 距離記為DT(p,d)。

改進Tanimoto 算法附加權重如圖1 所示。以3×3 窗口為例，Tanimoto 距離 與Hamming 距 離的 比較結果見表1，經Census 變換獲得的比特串位數為8 位，為方便對比，表1 中將Hamming 距離除以比特位數進行計算。

表1 Hamming 距離、Tanimoto 距離與加權重的改進Tanimoto 距離Table 1 Hamming distance，Tanimoto distance and weighted improved Tanimoto distance

圖1 改進Tanimoto 算法附加權重Fig.1 Additional pixel weights of improved Tanimoto algorithm

Tanimoto 距離與Hamming 距離的區別在于，Tanimoto 距離在分母中去掉了對兩個比特位同時為零的計數，因此當比特串位變化很小時，Tanimoto 距離具有更高的區分度，可有效減少Census 變換在弱紋理區域的誤匹配率，但這樣同時也降低了當比特串位變化很大時（Σa∩b=0）的區分度，影響了匹配效果。針對這一問題，本文對Tanimoto 距離進行改進，改進后的Tanimoto 距離計算公式見式（4）。

算法先按照圖1（a）的加權模板為特定位增加權重，i=1，2，W1=1，W2=2，再對Σa∩b=0 的情況進行處理以增大在比特串位變化很大時的區分度。在利用式（4）計算的過程中，對圖中灰色像素部分乘以權重2，相當于特定位計數兩次，其他位保持不變。由圖1（b）可知，經過加權后的比特位權重由“11111111”變為“12122121”，n由8 變為12。加權重的改進Tanimoto 距離計算結果見表1，可以看出，改進算法進一步細化了匹配代價值分布，增大了區分度，同時保持了弱紋理區域和紋理充足區域的匹配效果；同時，為有效解決Census 變換引起的算法依賴中心點和對噪聲敏感的問題，研究者引入梯度絕對值差（ADG）。LI 所提的改進ADG 算法［19］由于根據窗口內0°和90°兩方向的像素梯度絕對值差計算匹配代價，因此僅對這兩個方向的圖像邊緣處理效果較好，但對其他方向的邊緣不敏感，導致匹配效果欠佳，為解決上述問題，考慮到圖像邊緣多為45°和135°兩個方向，本文提出改進的4 方向ADG 算法，在0°和90°基礎上，添加45°和135°兩個方向的梯度并增加權重進行計算，進一步提高算法在邊緣處的匹配效果，且3×3 小窗口算法對中心像素點的依賴性較小，對噪聲具有魯棒性。本文算法計算公式見式（5）。

其中：G(p,d)為梯度絕對值差；|?i(Il(p))-?i(Ir(p,d))|為4 個方向的梯度絕對值差；Wi為方向權重?？紤]到算法的實時性和占用資源情況，將45°和135°的計算結果左移一位以增加權重，增加了匹配點在邊緣區域的區分度。最后將相同像素點的ADG 和Tanimoto 距離的乘積作為該點的初始匹配代價值，計算式見式（6）。

1.2 SGM 代價聚合

代價聚合通過對相鄰像素的代價值進行聚合以及施加懲罰，以達到避免選擇錯誤同名點的效果，代價聚合能量函數定義見式（7）。

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

SGM 算法［20］是全局算法的改進，其通過平等的聚合來自8 至16 條路徑的匹配代價，將二維圖像優化問題轉變為多路徑一維優化問題。當路徑為r、視差為d時，可得到像素點p的代價聚合函數，計算公式見式（8）。

其中：第1 項Cinit(p,d)為初始匹配代價；第2 項是路徑r上的前一個像素點p-r的最小匹配代價；第3 項是防止代價聚合值過大而減去的固定值。最后將像素點p在各個路徑上的聚合值相加即為該點在經過代價聚合后的匹配代價值，計算公式見式（9）。

1.3 視差選擇

本文選擇傳統立體匹配算法均采用的WTA 算法進行視差選擇，得到像素點的初始視差值，計算公式見式（10）。

其中：dinit(p)為初始視差值；dmax為最大視差范圍；E(p,d)為經過代價聚合后的代價值，最小代價值所在位置即為該點的視差值，dinit(p)?[0,dmax]。

1.4 視差校正

視差校正又稱為視差后處理，旨在對初始視差值中的誤匹配點進行修正，傳統立體匹配后處理方法主要有左右一致性檢驗（LRC）、中值濾波等。LRC 算法通過檢查左右兩張視差圖中同名點視差的差值來判斷是否為遮擋點，算法準確有效，但該算法在FPGA 上實現時，需要同時獲得左右兩張視差圖，這將比獲取一張視差圖的算法多占用一倍的硬件資源，算法運算效率低。

為了解決上述問題，筆者通過對WTA 獲得的初始視差值分析發現，遮擋點的代價值均大于某閾值，而正確匹配點的代價值均小于該閾值，這是由于遮擋點在參考圖中找不到最合適同名點，通過WTA 方法只能找到次合適同名點，故其選擇的最小代價值偏大。因此，提出通過設定閾值的方法來判斷是否為遮擋點，計算公式見式（11）。

若點d(p)視差值大于該閾值，則將視差值置0，視為遮擋點，否則保持不變。這樣就只需一張視差圖便可基本達到和LRC 一樣的結果，算法占用資源少，適合FPGA 實現。

完成遮擋檢測步驟后需對遮擋點進行填充，遮擋點由前景物體遮擋背景造成，應填充背景視差值，遮擋點填充算法的計算公式見式（12）。

其中：p為遮擋點；Dl為從該點開始向左第一個非遮擋點視差值；Dr為從該點開始向右第一個非遮擋點視差值，選取較小的視差值對p點進行填充。完成遮擋點檢測和填充后的視差圖會產生條紋效應，利用中值濾波對圖像中其余誤匹配點和條紋進行填充和改善。

2 FPGA 算法實現

將算法模塊封裝成IP 核，目標圖和參考圖以數據流的方式同時流入算法模塊，模塊與模塊之間利用為乒乓緩存結構連接，算法整體硬件結構如圖2 所示。

圖2 本文算法實現整體硬件結構Fig.2 The overall hardware architecture of the proposed algorithm implementation

2.1 匹配代價計算模塊

匹配代價模塊分為Tanimoto 模塊和ADG 模塊，兩模塊并行運算，運算結束后得出初始匹配代價。圖3 為Tanimoto 算法結構。數據流首先流入FIFO行緩存，緩存足夠的像素值后移入窗口緩存，進行Census 變換獲得比特串，按照式（4）將數據按位進行與或邏輯運算，計數后送入除法模塊。經檢驗Census 窗口過大或過小均會導致誤匹配率增加，其中窗口為7×7 時效果最佳，對應的Tanimoto 加權模板見圖1（b）。除法模塊由相減移位操作組成，被除數和除數的位寬為[lb(72-1)]=6 位，將被除數位寬增大到2 倍，高6 位為0，與除數進行相減移位操作，除法計算需迭代6 次，所得結果位寬為12 位，高6 位為余數，低6 位為商，像素與像素之間并行計算以減少延遲，滿足Pipeline 流水線設計要求，除法模塊結構如圖3 所示。

圖3 Tanimoto 距離算法硬件實現Fig.3 Hardware implementation of Tanimoto distance algorithm

圖4 為ADG 算法結構圖。將緩存窗口中的數據同時進行卷積，所得結果進行相加運算，匹配代價計算分別由Tanimoto 模塊和ADG 模塊組成，兩模塊雖并行計算，但所需時鐘周期不同，Tanimoto 模塊由于除法模塊的存在比ADG 相加模塊多消耗[lb(72-1)]-1=5 個時鐘周期，因此在ADG 模塊中增加FIFO 行緩存即可同步兩者輸出。初始匹配代價計算結構如圖5 所示，所得結果以數據流形式流入下一模塊。

圖4 ADG 算法硬件實現Fig.4 Hardware implementation of ADG algorithm

圖5 初始立體匹配算法硬件實現Fig.5 Hardware implementation of initial stereo matching algorithm

2.2 4 路徑代價聚合模塊

傳統8 方向代價聚合算法通過聚合來自8 個路徑的匹配代價值計算出最終代價值，但在FPGA 上實現傳統8 方向的聚合算法將緩存大量像素值，因為圖中淺灰色的4 條路徑不符合FPGA 流水線 的設計思想。圖6 為4 方 向SGM 代價聚合算法結構圖。為了控制算法消耗資源量，保證算法運行效率，采用圖6 中深灰色4 條路徑作為算法的代價聚合路徑。在行緩存內有足夠數據后送入4 個并行計算的代價聚合模塊，按式（8）計算后以數據流形式輸出。

圖6 代價聚合路徑Fig.6 Cost aggregation paths

2.3 視差選擇模塊

圖7 為WTA 算法的并行化實現結構圖，在最大視差范圍64 情況下，將整個結構分為[lb 64]=6 級，共采用63 個比較器單元。模塊輸入為匹配代價值，輸出是將最小代價值所在位置作為視差值，由于后接的截斷閾值檢測（TD）模塊須同時使用最小代價值和對應視差值，故將兩者同時輸出。遮擋點檢測算法如圖8 所示，模塊由一個比較器和一個選擇器組成，設置合適的截斷閾值并接收WTA 模塊傳來的最小代價值和對應視差值。若最小代價值大于設定閾值，則判定該點為遮擋點且對應視差值無效，將該點視差值置零并輸出；若最小代價值小于設定閾值，則判定該點為正常點，輸出視差值。

圖7 WTA 模塊和TD 模塊的硬件實現Fig.7 Hardware implementation of WTA module and TD module

圖8 4 路徑SGM 算法硬件實現Fig.8 Hardware implementation of four-path SGM algorithm

2.4 視差校正模塊

視差校正模塊分為無效點填充模塊和中值濾波模塊，其中無效點填充模塊是對視差圖中的異常點和遮擋點進行填充，填充分為向左填充和向右填充，分別對應兩個寄存器Dl和Dr，向右填充部分首先將數據流存入大小為1×dmax的行緩存中，若判定當前像素為無效值，則取行緩存中第一個有效值存入Dr；向左填充部分等待數據流入并將第一個有效值存入Dl，Dl和Dr取最小值作為該無效點的視差值并輸出。

圖9 為中值濾波算法結構，選擇3×3 窗口內所有點的中值代替窗口內所有點的值，可以有效消除視差圖中的異常點和條紋效應。算法首先需對窗口內的值進行排序，然后計算得出中值，為提高排序效率，算法分為兩步，首先分別計算3 行值的最大、最小和中值；然后將獲得的3 個值排序，獲得的中值即為所有點的中值。

圖9 中值濾波模塊的硬件實現Fig.9 Hardware implementation of median filter module

3 實驗結果與分析

本文利用Xilinx 的高級綜合工具（High Level Synthesis，HLS）進行模塊的設計與實現，通過SDK 軟件進行軟硬件協同設計并生成比特流文件導入XC7Z035 開發板中，采用Middleburry 數據集中1/4 分辨率 的4 幅圖像Tsukuba、Venus、Teddy 和Cones 對算法效果進行驗證，最大視差分別為16、20、64、60，將測試圖像存入SD 卡，經由開發板讀取、運算并由HDMI 顯示。

3.1 匹配精度

圖10 為算法測試結果，從中可以看出，算法在弱紋理和深度不連續區域匹配效果有所改善，但在無紋理區域的背景部分仍存在誤匹配的問題，這是因為為了保證匹配速率，算法采用7×7 窗口進行匹配代價計算，遇到大面積相同像素值區域時就無法進行有效區分，導致誤匹配。增大匹配窗口會導致計算量增大，但誤匹配率效果改善不明顯。

圖10 Middleburry 測試數據庫實驗結果Fig.10 Experimental results in Middleburry test database

本文算法與其他算法誤匹配率比較如表2 所示，誤匹配率計算表達式見式（13）。

其中：err 為誤匹配率；N為圖像總像素個數；dC為算法得到的視差值；dT為真實視差值，當兩者差值大于誤差閾值δd時，判定為誤匹配點，Nerr(x,y)=1，否則為0，δd?[0.5,4]，本文取1。不同算法的誤匹配如表2 所示，其中，Nonocc 為非遮擋區域誤匹配率，All 為全區域誤匹配率，Disc 為深度不連續區域誤匹配率。由表2 可知，通過計算所有區域下各個測試集圖像的誤匹配率的平均值，得出算法的平均誤匹配率為7.52%，算法匹配精度低于文獻［11］的基于改進Census 變換和動態規劃的局部算法，略低于文獻［19］的TAD SGM 算法，普 遍優于R3SGM 算法［21］和傳 統SGM 算法［22］。

表2 不同算法的誤匹配率Table 2 Percentage of Missmatch rate of different algorithms %

綜上所述，本文所提算法在識別精度方面較傳統基于FPGA 算法有明顯提升，優于現有基于FPGA的改進SGM 算法，算法對弱紋理和深度不連續區域的誤匹配情況也有所改善。

3.2 匹配速率

表3 為算法速率及資源占用情況，對比算法的誤差閾值均為1，算法在最大視差為64 個像素，圖像大小為450×375 像素且時鐘頻率為100 MHz時，可以達到98 frame/s，占用LUT 為88K，每秒處理百萬個視差數（Million Disparity Estimations per Second，MDE/s）為1 058。由表3 可知，本文算法在FPS 和MDE/s 上略遜于文獻［21-22］算法，這是因為算法含有除法器模塊，處理一個像素所用時間多于兩種算法。本文算法在得到更高匹配精度的前提下仍能滿足實時性要求，優于文獻［23-24］算法。

表3 不同算法在Zynq-7000 XC7Z035 的速率及資源占用情況Table 3 Processing speed and corresponding resource utilization of different algorithms on Zynq-7000 XC7Z035

4 結束語

本文提出一種新型實時半全局立體匹配算法。利用改進的Tanimoto 距離代替Hamming 距離并與帶權重4 方向的改進ADG 算法相結合作為初始匹配代價，降低針對弱紋理區域和邊緣區域的誤匹配率。同時利用4 路徑的半全局代價聚合方法代替原8 路徑方法，在保證算法精度前提下提高了算法運行效率。此外，采用截斷閾值檢測算法代替左右一致性檢驗，只需一張視差圖便可完成檢測，減少了資源占用率。本文算法在Middleburry 數據集上的平均誤匹配率為7.52%，在FPGA 上實現時吞吐率為98 frame/s，在保證實時性的前提下可使基于FPGA的雙目立體匹配系統匹配精度得到提高。但由于本文算法存在除法模塊，處理一個像素點需多個時鐘周期，在實時性方面稍遜于其他基于FPGA 的算法，并且需要保證實時性而選擇小窗口，在處理大片無紋理區域時存在誤匹配現象。后續將研究如何在小窗口下提高算法對于無紋理區域的匹配精度，并進一步提高算法的實時性。