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

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

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

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

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

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