基于SAD算法的立體匹配的實現*

岳陳平,孟麗婭

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

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

1 立體匹配算法

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

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

在常規的算法中，絕對值AD為:

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

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

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

2 算法流程及硬件實現

2.1 算法流程

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

2.2 硬件實現

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

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

表1 SAD算法所需要的資源

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

表2 不同匹配方案的比較

[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 basedon window-parallel-and-pixel-parallel architecture[C].Proceedings of the IEEE Int.Midwest Symp.on Circ.And Syst,2005.(收稿日期：2012-12-20)