岳陳平,孟麗婭

(重慶大學(xué) 光電工程學(xué)院，重慶400030)

立體視覺理論的提出和美國MIT的Robert完成的三維景物分析工作把過去的二維圖像分析推廣到了三維景物[1]。利用立體視覺來恢復(fù)物體的三維立體信息可以應(yīng)用在工業(yè)自動化生產(chǎn)線等檢測領(lǐng)域，如產(chǎn)品檢測、工業(yè)探傷、PCB印制板檢查以及各種危險場合工作的機(jī)器人等。而一個完整的立體視覺系統(tǒng)的核心工作就是立體匹配。立體匹配算法需要處理大量復(fù)雜數(shù)據(jù)，采用PC來實(shí)現(xiàn)數(shù)據(jù)的快速處理不僅會占用CPU的大量時間，而且在功耗方面也難以承受。而利用現(xiàn)場可編程門陣列FPGA(Field Programmable Gate Array)等硬件的方法來進(jìn)行立體視覺的研究，有益于實(shí)現(xiàn)系統(tǒng)的實(shí)時性并降低功耗。本文采用FPGA，利用補(bǔ)碼實(shí)現(xiàn)SAD匹配算法，基于窗口并行和像素串行完成匹配算法的流程，這種算法流程不僅效果好、速度快，而且具有較強(qiáng)的魯棒性，很適合采用硬件方式來實(shí)現(xiàn)。

1 立體匹配算法

立體匹配算法中基于區(qū)域匹配的算法其性能在很大程度上要依賴于相似性測度因子的選取，而最常用的測度因子有像素灰度差的絕對值和SAD(Sum of Absolute Differences)、像素灰度差的平方和SSD (Sum of Squared Differences)、歸一化相關(guān)方法NCC(Normalized Cross Correlation)[2]。SSD算法有平方運(yùn)算，NCC有除法和開方的運(yùn)算，而SAD只有加法運(yùn)算，從算法的復(fù)雜度和硬件實(shí)現(xiàn)的難易度來看，SSD和NCC將會占用FPGA大量的邏輯單元并且耗時量大。SAD算法表達(dá)式為[3]：

其中，disp為左攝像機(jī)拍攝的圖像上窗口在外極線上移動的距離，即視差；PL(i，j)表示基準(zhǔn)圖中的待匹配像素的灰度值，PR(i，j)表示配準(zhǔn)圖中的匹配點(diǎn)的灰度值。計算不同視差情況下的SAD值，選取SAD的最小值，此時，PR為PL點(diǎn)在配準(zhǔn)圖中的最佳匹配點(diǎn)。

在常規(guī)的算法中，絕對值A(chǔ)D為:

在硬件實(shí)現(xiàn)中，用這種方法來求取絕對值會耗費(fèi)較多的FPGA邏輯單元，如圖1所示。其中，MSB為選擇器MUX 的判斷信號，當(dāng) X＞Y 時，MSB=0，此時，AD＝X-Y;相反時,AD＝Y(jié)-X。

為了減少FPGA的邏輯單元使用率，采用補(bǔ)碼來計算 X、Y的絕對值，即：

在求絕對值過程中，如果X＞Y，則MSB=0；相反，MSB=1，ADXY的取值為X-Y的補(bǔ)碼,硬件實(shí)現(xiàn)過程如圖2所示。

2 算法流程及硬件實(shí)現(xiàn)

2.1 算法流程

為了能夠?qū)崿F(xiàn)快速實(shí)時的圖像處理，硬件結(jié)構(gòu)通常選擇并行操作來實(shí)現(xiàn)具有高效率和實(shí)時性的圖像處理算法。立體匹配算法有像素并行運(yùn)算 (pixel-parallel)和窗口并行運(yùn)算 (window-parallel)[2-3]兩種。在硬件資源的約束下，像素并行運(yùn)算方式只適用于窗口大小固定的立體匹配，窗口大小可變以及要考慮硬件資源的利用率時，像素并行運(yùn)算方法就不適用。因此，在一般的硬件實(shí)現(xiàn)立體匹配運(yùn)算中，為了獲得高效率的匹配值，這兩種并行結(jié)構(gòu)可適當(dāng)?shù)亟Y(jié)合使用或是有選擇地使用。當(dāng)把兩種并行結(jié)構(gòu)結(jié)合起來運(yùn)算時，可以分為像素并行和窗口串行PPWS(Pixel-Parallel and Window-Serial)以及像素串行和窗口并行PSWP(Pixel-Serial and Window-Parallel)[4-5]。綜合考慮，本文中采用了圖3所示的PSWP算法流程。圖3中共有n個匹配窗口，CWn表示第n個匹配窗口，Ri表示基準(zhǔn)圖中匹配窗口的像素值，C表示配準(zhǔn)圖中第n個匹配窗口中的像素值，AD表示求取兩個像素值絕對值差，在每個窗口中采用像素值串行的運(yùn)算方式,并同時計算n個窗口的數(shù)據(jù)。

2.2 硬件實(shí)現(xiàn)

利用FPGA實(shí)現(xiàn)立體匹配算法。設(shè)計的關(guān)鍵在于，在片內(nèi)RAM帶寬和容量制約的前提下，充分利用FPGA并行性計算和合理的流水線設(shè)計來實(shí)現(xiàn)并行計算，并且能夠把算法直接映射到結(jié)構(gòu)上[6]。在FPGA上實(shí)現(xiàn)的具體流程如圖4所示。將采集到的圖像數(shù)據(jù)首先經(jīng)過圖像的中值濾波預(yù)處理，左圖像數(shù)據(jù)經(jīng)過緩存單元輸送至SAD計算單元，右圖數(shù)據(jù)輸送到由FIFO構(gòu)成的移位寄存器組，通過移位寄存器組后，在控制單元的作用下與左圖像緩存后的數(shù)據(jù)同時輸送到SAD計算單元，在SAD計算單元計算不同視差值情況下的SAD值，經(jīng)比較得出最小的SAD值，輸出最小SAD值所對應(yīng)的視差值。

采用Altera公司的Stratix系列EP2S15F672C3器件，利用Verilog HDL語言編寫了程序代碼，并且在QUARTUS II和Modelsim 6.0中進(jìn)行功能和時序仿真。本文以圖像大小128×128為例，窗口大小設(shè)置為3×3，視差為 24，通過對算法的簡化，實(shí)現(xiàn)SAD算法。所需的資源如表1所示。圖5所示為最后的結(jié)果圖。表2為本算法與其他算法性能對比。

表1 SAD算法所需要的資源

本文完成了一個基于FPGA實(shí)現(xiàn)立體匹配的算法過程，結(jié)合硬件結(jié)構(gòu)的存儲和資源的限制，在實(shí)現(xiàn)SAD算法過程中采用了并行計算和流水線結(jié)構(gòu)，并且在具體的運(yùn)算中選取了PSWP的運(yùn)算流程。本方案共消耗該系列FPGA 3 620個邏輯單元，約相當(dāng)于總數(shù)的29%；消耗FPGA內(nèi)部容量為263 424 bit，約為總?cè)萘康?3%。將本文方案與其他方案進(jìn)行比較，由于采用的匹配算法不同，獲得的視差圖也是不同的，因此直接比較每個方案占用的邏輯單元來判斷幀率的大小是不可取的，但是可得到這樣的結(jié)論：在簡化算法和合理地采用并行流水線結(jié)構(gòu)的條件下,選擇SAD算法運(yùn)用硬件方法來實(shí)現(xiàn)匹配比用軟件方法更勝一籌。因此，在搭建一個低功耗的立體視覺系統(tǒng)時，F(xiàn)PGA器件是最佳的選擇。

表2 不同匹配方案的比較

[1]STEGER C，ULRICH M，WIEDEMANN C.機(jī)器視覺算法與應(yīng)用[M].楊少榮,等譯.北京:清華大學(xué)出版社，2008.

[2]MARR D.視覺計算理論[M].姚國正，劉磊，汪云久,譯.北京:科技出版社，1998.

[3]AMBROSCH K,HUMENBERGER M,KUBINGER W,et al.Hardware implementation of an SAD based stereo vision algorithm[C].Proceedings of the Conference on Computer Vision and Pattern Recognition Workshops,Minneapolis,2007:1-6.

[4]CHEN L,Jia Yunde.A parallel reconfigurable architecture for real-time stereo vision[C].Proceedings of the International Conference on Embedded Software and Systems,2009:32-39.

[5]HARIYAMA M,KAMEYAMA M.VLSI Processor for Reliable stereo matching based on window-parallel logic-inmemory architecture[C].Proceedings of the Symp on VLSI Circuits Digital of Technology Papers,2004.

[6]HARIYAMA M,YOKOYAMA N,KAMEYAMA M,et al.FPGA implemetation of a stereo matching processor basedon window-parallel-and-pixel-parallel architecture[C].Proceedings of the IEEE Int.Midwest Symp.on Circ.And Syst,2005.(收稿日期：2012-12-20)