雙目立體匹配算法的FPGA實現

韓劍輝　吳振　李蘭英

摘要：針對區域匹配算法在灰度變化比較大區域精度不高的問題，提出一種改進的匹配算法，利用sobel算子計算各像素點的梯度值，根據梯度幅度直方圖獲得自適應閾值，動態建立支持窗口，改進傳統的Census變換，用窗口內所有像素均值代替中心像素進行Census變換，在左右圖像中尋找最佳匹配點獲得視差圖，利用FPGA并行處理和硬件實現的優點，對大數據量實時地進行處理，提高運算效率，實驗結果表明：改進的立體匹配算法和硬件結構能夠獲得精度較高的視差圖，處理640×480的圖像對只需32.4 ms，

關鍵詞：立體匹配；Sobel算子；自適應閥值；Census變換；現場可編程門陣列

DOI：10.15938/j.jhust.2016.04.005

中圖分類號：TP391

文獻標志碼：A

文章編號：1007-2683（2016）04-0025-05

0引言雙目立體視覺是計算機視覺技術研究領域的熱點問題，立體匹配是實現立體視覺的重要環節，匹配結果的精度則是制約立體視覺技術發展的瓶頸，立體匹配的算法大致可以分為全局匹配算法和局部匹配算法，其中區域匹配算法由于能夠直接獲取視差信息，算法復雜度也相對較低，因而廣泛地應用在實時立體視覺系統的設計中，

區域匹配算法的性能很大程度上依賴匹配窗口的建立和相似性測度函數的選擇，文根據分割區域動態選擇窗口的形狀和大小的方法得到了較好效果，但對于復雜紋理圖像，無法做到較精確的色彩分割，Yoon和Kweon 利用像素間光度學和幾何學關系調配窗口中像素的權值，本質上類似于分割的思想，但卻回避了分割難題，此方法不依賴初始視差估計，同時在深度不連續和連續區域得到精確匹配，但其高時間計算復雜度問題有待解決，常用的相似性測度函數有像素灰度差的絕對值和（sumof absolute differences，SAD）、及像素灰度差的平方和（sum of squared differences，SSD）、以及非參數化方法的Rank變換和Census變換SSD、SDA算法容易受光照不均及遮擋問題的影響導致匹配誤差增大，Rank變換的思想類似濾波器，通過待匹配點與特征窗內各點灰度差，定義灰度等級Zabih把等級變換算法推廣到Census變換，通過編碼像素間的等級信息保留其空間分布，用加權平均編碼信息匹配圖像，由于這種方法依據灰度排序方式，提高了算法的魯棒性，但同時增加了窗口圖像信息的維度，計算更加復雜。

雖然上述算法已經能夠極大改善區域匹配的性能，但是對于存在灰度變化比較大區域的圖像會出現視差圖過渡平滑的現象，而且算法復雜度都比較高，難以滿足立體視覺系統高速、實時的要求，本文結合邊緣檢測，利用Sobel梯度算子、梯度幅度直方圖和Census變換改進基于傳統Census變換的區域匹配算法，并且借助現場可編程門陣列（field pro—grammable gate arrays，FPGA）開發專用的硬件并行處理系統實現該算法，

1.算法描述

1.1梯度幅值計算

Sobel是一階導數邊緣檢測算子，是一種有效的梯度計算方法，具體方法是通過3×3模板作為核與圖像中的每個像素點做卷積和運算。

利用Sobel算子計算圖像中一點的梯度幅值，需要以該像素點為中心建立一個3×3的窗口，然后將窗口內所有像素分別與兩個核做卷積獲得水平分量G_x和垂直分量G_y如式（1）～（4），

1.2自適應匹配窗口

匹配窗口尺寸的選取對于立體匹配至關重要，窗口太小，包括的圖像信息過少，不足以表達出區域的特征，導致誤匹配；窗口太大，則違背了匹配窗口內的像素的視差值是一致的假設，無法區分場景中物體和其背景，同時匹配速度也降低在實際匹配中，匹配窗口的大小需要隨著圖像像素灰度的變化而改變，以提高匹配的精度，

一般在像素灰度變化比較大的區域，對應的像素梯度值變化也比較劇烈，視差變化也不連續，匹配窗口大小應該設置得比較小；而對于梯度值較小的區域，往往是低紋理區域，此處匹配窗口應該設置得比較大，因此需要動態調節匹配窗口的大小，本文采用雙閾值確定匹配窗口的大小：選定兩個梯度幅值閾值，一個較高G_h另一個較低G_l；設定匹配窗口的尺寸標準分別為D₁、D₂、D₃（D₁>D₂>D₃）；當梯度幅值G（x，y）>G_l時，匹配窗口的大小為D₁×D₂；當梯度幅值G（x，y）3×D₃；其他情況時，匹配窗口大小為D₂×D₂

分析梯度直方圖得出閾值的計算方法，自適應地動態生成閾值，克服人為設定閾值的不足，

根據梯度直方圖可知，閾值的選擇問題實際上即為在梯度幅值直方圖中找出灰度變化平穩的區域的尖峰與第一個灰度變化較大區域的尖峰之間的平滑區域，閾值可以選取為此區域內任意一像素的梯度幅值，為了找到這段區域，對梯度幅值的相鄰兩點作差分，即

1.3改進的Census變換

Census變換屬于非參數相似測度因子，基本思想是用一個矩形窗口遍歷圖像，把窗口內中心像素的灰度值作為參考值，將窗口內其余像素依次與參考值比較，灰度值小于參考值的像素點記為1，大于或等于參考值的像素點記為O，然后按位連接輸出一串二進制代碼。

式中：W（p）為以像素點P為中心的匹配窗口；I（p）為像素點P的灰度值，，（p）為W（p）內除像素點P以外任意一點的灰度值；表示按位連接，矩形窗口W（P）的尺寸是根據中心像素點的梯度幅值和梯度閾值比較之后確定的，函數E（X，y）定義為

但是傳統的Census變換過于依賴中心像素，當圖像受到干擾，中心像素發生畸變，就會增大誤匹配的幾率，本文用矩形窗口內所有像素值的平均值替代中心像素值，仍然按照式（8）、（9）進行變換，這樣增強了Census變換的抗干擾能力，

將兩幅圖像的匹配窗口中的所有像素進行改進的Census變換得到兩串01代碼，利用Hamming距離公式計算兩比特串之間的差異，Hamming距離越小則說明兩點的匹配代價越小，兩個像素點越相似匹配代價計算如下：式中：（x，y），）表示像素點的坐標值；w表示以點（x，y）為心中的鄰域；I_r（x，y）表示在左圖中像素點（x，y）的灰度值；I_r表示右圖像素的灰度值；XOR表示異或運算；d表示視差，

2.算法描述

FPGA完成圖像數據的存取、梯度計算、自適應閾值的計算和立體匹配，算法模塊的RTL視圖如圖1所示，

2.1緩存窗口設計

使用QuartusⅡ軟件中基于RAM的移位寄存器宏模塊ahshift_taps來實現緩存窗口的設計，宏模塊altshift_taps是一個可配置的、具有抽頭（Taps）輸出的移位寄存器，每個抽頭在移位寄存器鏈的指定位置輸出數據，例如，對于256×256的圖像，ahshifltaps模塊參數設置為8bit輸入、8bit輸出、3抽頭，相鄰的兩個抽頭相距256個寄存器，如圖2所示，其中相鄰兩個抽頭間的距離是根據圖像大小來設定的，

在工程實際中，3×3的窗口是經常用到的，Shift—RAM中存儲2行數據，同時輸入數據組成3行陣列，接著輸入row3_data數據，機構Shift_RAM移位存儲后就可以得到3×3的窗口數據陣列，移位寄存器仿真波形如圖3所示，

2.2Sobel梯度鼻子

Sobel梯度算子的硬件實現可以分為圖像數據緩存模塊和梯度結合模塊，其中，圖像數據緩存模塊采用移位寄存器（shift register）實現，梯度結合模塊采用可編程宏模塊和Verilog HDL語言相結合的方法實現，

根據卷積運算公式，可以使用QuartusⅡ軟件中的可編程加法器altmult_add模塊以及可編程多路并行加法器parallel add模塊來實現卷積運算，將運算得到的垂直方向和水平方向的梯度值求平方和G_x2+G_y2，利用QuaausⅡ中的宏模塊ALTSQRT求解

2.3自適應閾值

自適應閾值的選擇是基于梯度直方圖進行的，因此首先需要對經過非極大值抑制后的圖像進行直方圖統計，自適應閾值的產生電路如圖5所示，

這些寄存器用于存儲不同梯度值像素點的個數，梯度值作為寄存器組的地址，在每幅圖像開始時，對這些寄存器清零，梯度值輸入后，通過地址選擇器，相應地址的寄存器的內容被取出來送人累加器1，加l后再寫入該寄存器，直到整幅圖像的所有像素點統計完畢，在時鐘保持有效期內，每個時鐘到來累加器2的內容自加1，累加的結果作為寄存器組的地址，相應地址寄存器的內容以及下一個地址寄存器的內容分別送人寄存器1和寄存器2，對寄存器1和寄存器2的內容按式（6）進行差分，比較器比較差分的結果是否為0，若為0則發出停止累加信號，停止累加器2的累加，此時累加器2的值即為高閾值G_h，G_h右移一位（即除以2）得到低閾值G₁。

2.4立體匹配

為了提高系統的實時性，Census模塊的設計采用了以資源換取時間的并行優化方法，例如，對于7×7的局部變換窗口，Census變換模塊如圖6所示，將移位寄存器組擴展為8行，每一列讀入8個像素數據，在窗口水平移動中，每隔8個時鐘周期對Census變換窗口的數據更新一次，當Census變換窗口移至每行末尾時，便獲得了相鄰兩行像素的Census局部變換，從資源方面分析，并行后比較器的數量增加了1倍，但移位寄存器的數量只增加了1/7，優化結果卻使Census局部變換的速度提高了近1倍，運算頻率由1/7（像素/周期）提高到1/5（像素/周期），

3.實驗結果與分析

為了驗證本文算法的有效性，將實驗結果上傳到Middlebury網站平臺進行評估，本文算法的支持窗口分別設置為D₁=7、D₂=5、D₃=3，為了分析匹配精度，選擇Middlebury網站上一些相近的算法進行比較，匹配精度比較結果如表1所示，

通過比較，ADCensus算法能夠達到很低的誤點率，但算法較為復雜，本文算法與SSD+ASW、Cen—BUS+ASW算法相比誤匹配率要低，對比而言本文提出的算法綜合考慮了算法匹配精度與實時性，達到了較好的效果。

另外，在Pc和FPGA上實現本文算法，計算兩者處理同一幀640×480像素圖像所用時間，比較結果如表2所示，

選擇Middlebury平臺中的Teddy圖像作為參考圖像，比較SSD+ASW、Census+ASW和本文算法的匹配結果，

由圖7（b）可以看出本文算法得到的視差圖較Census+ASW和SSD+ASW算法更為清晰，能夠比較準確地反應圖像的深度信息，

4.結論

本文提出了一種基于Sobel梯度算子和改進的Census變換相結合的立體匹配算法，并借助FPGA硬件實現該算法，經過試驗表明此算法的匹配效果好于傳統Census變換的算法，所獲得視差圖比較稠密，而且有效提高了算法的實時性，但是，在遮擋情況下，視差邊緣不準確，在后續的研究中將對這一方面進行完善。