摘  要: 利用FPGA并行性計(jì)算和合理的流水線設(shè)計(jì)完成了立體視覺(jué)中最核心的部分——立體匹配以及硬件結(jié)構(gòu)，選取SAD區(qū)域立體匹配算法，利用補(bǔ)碼來(lái)實(shí)現(xiàn)SAD算法，在算法流程中采用窗口并行和像素串行來(lái)完成。在獲得視差圖時(shí)，采用128×128圖像對(duì)，窗口大小為3×3，視差為24，在系統(tǒng)時(shí)鐘為50 MHz情況下，實(shí)現(xiàn)了每秒425幀的處理速度，最后給出了視差圖。實(shí)驗(yàn)證明，選用FPGA來(lái)實(shí)現(xiàn)立體匹配系統(tǒng)的設(shè)計(jì)是可行的，具有一定的魯棒性。
關(guān)鍵詞: 立體匹配；區(qū)域匹配；SAD；FPGA

    立體視覺(jué)理論的提出和美國(guó)MIT的Robert完成的三維景物分析工作把過(guò)去的二維圖像分析推廣到了三維景物[1]。利用立體視覺(jué)來(lái)恢復(fù)物體的三維立體信息可以應(yīng)用在工業(yè)自動(dòng)化生產(chǎn)線等檢測(cè)領(lǐng)域，如產(chǎn)品檢測(cè)、工業(yè)探傷、PCB印制板檢查以及各種危險(xiǎn)場(chǎng)合工作的機(jī)器人等。而一個(gè)完整的立體視覺(jué)系統(tǒng)的核心工作就是立體匹配。立體匹配算法需要處理大量復(fù)雜數(shù)據(jù)，采用PC來(lái)實(shí)現(xiàn)數(shù)據(jù)的快速處理不僅會(huì)占用CPU的大量時(shí)間，而且在功耗方面也難以承受。而利用現(xiàn)場(chǎng)可編程門(mén)陣列FPGA(Field Programmable Gate Array)等硬件的方法來(lái)進(jìn)行立體視覺(jué)的研究，有益于實(shí)現(xiàn)系統(tǒng)的實(shí)時(shí)性并降低功耗。本文采用FPGA，利用補(bǔ)碼實(shí)現(xiàn)SAD匹配算法，基于窗口并行和像素串行完成匹配算法的流程，這種算法流程不僅效果好、速度快，而且具有較強(qiáng)的魯棒性，很適合采用硬件方式來(lái)實(shí)現(xiàn)。
1 立體匹配算法
    立體匹配算法中基于區(qū)域匹配的算法其性能在很大程度上要依賴于相似性測(cè)度因子的選取，而最常用的測(cè)度因子有像素灰度差的絕對(duì)值和SAD(Sum of Absolute Differences)、像素灰度差的平方和SSD(Sum of Squared Differences)、歸一化相關(guān)方法NCC(Normalized Cross Correlation)[2]。SSD算法有平方運(yùn)算，NCC有除法和開(kāi)方的運(yùn)算，而SAD只有加法運(yùn)算，從算法的復(fù)雜度和硬件實(shí)現(xiàn)的難易度來(lái)看，SSD和NCC將會(huì)占用FPGA大量的邏輯單元并且耗時(shí)量大。SAD算法表達(dá)式為[3]：

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

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

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

    本文完成了一個(gè)基于FPGA實(shí)現(xiàn)立體匹配的算法過(guò)程，結(jié)合硬件結(jié)構(gòu)的存儲(chǔ)和資源的限制，在實(shí)現(xiàn)SAD算法過(guò)程中采用了并行計(jì)算和流水線結(jié)構(gòu)，并且在具體的運(yùn)算中選取了PSWP的運(yùn)算流程。本方案共消耗該系列FPGA 3 620個(gè)邏輯單元，約相當(dāng)于總數(shù)的29%；消耗FPGA內(nèi)部容量為263 424 bit，約為總?cè)萘康?3%。將本文方案與其他方案進(jìn)行比較，由于采用的匹配算法不同，獲得的視差圖也是不同的，因此直接比較每個(gè)方案占用的邏輯單元來(lái)判斷幀率的大小是不可取的，但是可得到這樣的結(jié)論：在簡(jiǎn)化算法和合理地采用并行流水線結(jié)構(gòu)的條件下,選擇SAD算法運(yùn)用硬件方法來(lái)實(shí)現(xiàn)匹配比用軟件方法更勝一籌。因此，在搭建一個(gè)低功耗的立體視覺(jué)系統(tǒng)時(shí)，F(xiàn)PGA器件是最佳的選擇。
參考文獻(xiàn)
[1]  STEGER C， ULRICH M， WIEDEMANN C.機(jī)器視覺(jué)算法與應(yīng)用[M].楊少榮,等譯.北京:清華大學(xué)出版社，2008.
[2] MARR D. 視覺(jué)計(jì)算理論[M]. 姚國(guó)正，劉磊，汪云久,譯.北京:科技出版社，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 bas  on window-parallel-and-pixel-parallel architecture[C].Proceedings of the IEEE Int.Midwest Symp. on Circ. And Syst, 2005.