雙目立體匹配算法的FPGA實(shí)現(xiàn)

韓劍輝　吳振　李蘭英

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

關(guān)鍵詞：立體匹配；Sobel算子；自適應(yīng)閥值；Census變換；現(xiàn)場(chǎng)可編程門陣列

DOI：10.15938/j.jhust.2016.04.005

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1007-2683（2016）04-0025-05

0引言雙目立體視覺是計(jì)算機(jī)視覺技術(shù)研究領(lǐng)域的熱點(diǎn)問題，立體匹配是實(shí)現(xiàn)立體視覺的重要環(huán)節(jié)，匹配結(jié)果的精度則是制約立體視覺技術(shù)發(fā)展的瓶頸，立體匹配的算法大致可以分為全局匹配算法和局部匹配算法，其中區(qū)域匹配算法由于能夠直接獲取視差信息，算法復(fù)雜度也相對(duì)較低，因而廣泛地應(yīng)用在實(shí)時(shí)立體視覺系統(tǒng)的設(shè)計(jì)中，

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

雖然上述算法已經(jīng)能夠極大改善區(qū)域匹配的性能，但是對(duì)于存在灰度變化比較大區(qū)域的圖像會(huì)出現(xiàn)視差圖過渡平滑的現(xiàn)象，而且算法復(fù)雜度都比較高，難以滿足立體視覺系統(tǒng)高速、實(shí)時(shí)的要求，本文結(jié)合邊緣檢測(cè)，利用Sobel梯度算子、梯度幅度直方圖和Census變換改進(jìn)基于傳統(tǒng)Census變換的區(qū)域匹配算法，并且借助現(xiàn)場(chǎng)可編程門陣列（field pro—grammable gate arrays，F(xiàn)PGA）開發(fā)專用的硬件并行處理系統(tǒng)實(shí)現(xiàn)該算法，

1.算法描述

1.1梯度幅值計(jì)算

Sobel是一階導(dǎo)數(shù)邊緣檢測(cè)算子，是一種有效的梯度計(jì)算方法，具體方法是通過3×3模板作為核與圖像中的每個(gè)像素點(diǎn)做卷積和運(yùn)算。

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

1.2自適應(yīng)匹配窗口

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

一般在像素灰度變化比較大的區(qū)域，對(duì)應(yīng)的像素梯度值變化也比較劇烈，視差變化也不連續(xù)，匹配窗口大小應(yīng)該設(shè)置得比較??；而對(duì)于梯度值較小的區(qū)域，往往是低紋理區(qū)域，此處匹配窗口應(yīng)該設(shè)置得比較大，因此需要?jiǎng)討B(tài)調(diào)節(jié)匹配窗口的大小，本文采用雙閾值確定匹配窗口的大?。哼x定兩個(gè)梯度幅值閾值，一個(gè)較高G_h另一個(gè)較低G_l；設(shè)定匹配窗口的尺寸標(biāo)準(zhǔn)分別為D₁、D₂、D₃（D₁>D₂>D₃）；當(dāng)梯度幅值G（x，y）>G_l時(shí)，匹配窗口的大小為D₁×D₂；當(dāng)梯度幅值G（x，y）3×D₃；其他情況時(shí)，匹配窗口大小為D₂×D₂

分析梯度直方圖得出閾值的計(jì)算方法，自適應(yīng)地動(dòng)態(tài)生成閾值，克服人為設(shè)定閾值的不足，

根據(jù)梯度直方圖可知，閾值的選擇問題實(shí)際上即為在梯度幅值直方圖中找出灰度變化平穩(wěn)的區(qū)域的尖峰與第一個(gè)灰度變化較大區(qū)域的尖峰之間的平滑區(qū)域，閾值可以選取為此區(qū)域內(nèi)任意一像素的梯度幅值，為了找到這段區(qū)域，對(duì)梯度幅值的相鄰兩點(diǎn)作差分，即

1.3改進(jìn)的Census變換

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

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

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

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

2.算法描述

FPGA完成圖像數(shù)據(jù)的存取、梯度計(jì)算、自適應(yīng)閾值的計(jì)算和立體匹配，算法模塊的RTL視圖如圖1所示，

2.1緩存窗口設(shè)計(jì)

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

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

2.2Sobel梯度鼻子

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

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

2.3自適應(yīng)閾值

自適應(yīng)閾值的選擇是基于梯度直方圖進(jìn)行的，因此首先需要對(duì)經(jīng)過非極大值抑制后的圖像進(jìn)行直方圖統(tǒng)計(jì)，自適應(yīng)閾值的產(chǎn)生電路如圖5所示，

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

2.4立體匹配

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

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

為了驗(yàn)證本文算法的有效性，將實(shí)驗(yàn)結(jié)果上傳到Middlebury網(wǎng)站平臺(tái)進(jìn)行評(píng)估，本文算法的支持窗口分別設(shè)置為D₁=7、D₂=5、D₃=3，為了分析匹配精度，選擇Middlebury網(wǎng)站上一些相近的算法進(jìn)行比較，匹配精度比較結(jié)果如表1所示，

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

另外，在Pc和FPGA上實(shí)現(xiàn)本文算法，計(jì)算兩者處理同一幀640×480像素圖像所用時(shí)間，比較結(jié)果如表2所示，

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

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

4.結(jié)論

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