雙目立體相機中實時匹配算法的FPGA實現

單 潔，唐 垚，姜 暉

(西安郵電大學通信與信息工程學院，陜西西安710121)

1 引言

隨著機器視覺的發(fā)展，立體視覺系統(tǒng)得到越來越廣泛的應用［1－2］。雙目立體相機采用兩臺相機，模擬人眼成像原理，先通過尋找兩個相機中圖像對應點的光學，得到各個點處的視差，再根據視差信息和相機的投影模型恢復出原始景物的深度信息。所以，在通過立體相機計算場景信息的深度過程中，圖像獲取、相機標定、圖像匹配和三維重建成為了關鍵技術。

根據匹配基元的不同，圖像匹配可分為區(qū)域匹配［1－2］、特征匹配［1］和相位匹配［2－4］。其中，區(qū)域匹配以區(qū)域相似度為匹配基元，基本原理是在基準圖上選取一個模板窗口，在配準圖上選取同樣大小的一組窗口，再將這些窗口與基準圖中的模板窗口進行相似度比較，找出與模板窗口最相似的窗口，那么該窗口的中心點就是模板窗口中心點的匹配點，兩點的橫坐標差即為視差［1］。

區(qū)域匹配直接利用圖像的灰度信息，實質是利用局部窗口之間灰度信息的相關程度，并能取得致密的視差場。區(qū)域匹配適用于具有明顯紋理特征的圖像，可以直接獲得稠密的深度圖，但區(qū)域匹配選取一定大小窗口內的灰度分布特性作為匹配基元，決定了該算法具有以下局限性［5］:(1)計算量大;(2)對左右兩幅圖像中光照不均勻較敏感，在這種情況下容易造成匹配困難;(3)匹配窗大小難選擇。窗口選擇過大，在高度間斷處會出現誤匹配，選擇過小，區(qū)域內的灰度分布特性未得以充分展現;(4)對于視差不連續(xù)處的情況，如物體邊緣附近的區(qū)域，適應性較差。文獻［6］、［7］提出了在FPGA上基于SAD匹配準則的算法實現?；贔PGA實現圖像匹配算法，能夠充分發(fā)揮FPGA的特點，利用流水線和并行計算技術，提高運算效率和系統(tǒng)的吞吐率，解決了計算量大的問題，達到實時處理的要求。針對區(qū)域匹配對因亮度變化、噪聲等因素引起的幅度失真非常敏感的問題，先后有文獻提出了對幅度失真不敏感的匹配代價，其中主要有歸一化互相關(NCC)、互信息和 Rank、Census 非參數變換［8］等。Hirschmulle通過大量實驗發(fā)現:基于Census變換的匹配代價對圖像中的噪聲和亮度不一致性有很高的魯棒性，能獲得更優(yōu)的視差結果［9］。文獻［7］采用基于Census變換的匹配算法實現了圖像匹配的實時處理。此外，傳統(tǒng)的固定窗口存在變換窗口大小的選擇問題，若窗口太小，則匹配代價區(qū)分度過低，在低紋理區(qū)域容易出現誤匹配;若窗口過大，又會在深度不連續(xù)區(qū)域出現誤匹配。文獻［10］提出了基于Census變換與自適應窗口的局部匹配算法，對幅度失真具有良好的魯棒性。但是，經過研究表明，Census變換由于丟棄了圖像色彩信息而僅保留了像素間大小關系，容易造成誤匹配［11］，文獻［12］提出了多相關窗口的匹配方法。

本課題主要應用雙目立體相機進行障礙物檢測，不僅要求對數據的正確性，還要求算法需要較低的復雜度，同時還要具有較好的魯棒性，處理好噪聲、目標區(qū)域低紋理、遮擋和圖像邊界不連續(xù)等問題，實現最佳的立體匹配效果。為了解決區(qū)域匹配的局限性，對立體匹配算法的進展進行了研究，利用Census度量算法的特點，結合文中具體立體相機的硬件結構，提出了一種基于FPGA的并行實時Census變換立體匹配算法?；贔PGA的算法實現結合了多窗口匹配的方法，通過左右一致性約束，實現了基于FPGA的立體圖像匹配硬件結構，不僅保證了匹配精度，而且對幅度失真具有較好的魯棒性，為下一步的三維重建及深度測量打下了良好的基礎。

2 算法描述

2.1 Census變換

非參數變換［8］，如 Rank 或 Census，是首先對圖像進行非參數化變換，提取包含局部紋理信息的描述符。Census變換通過計算點在窗口中的灰度順序。變換以像素為中心選擇一個窗口，將窗口中心像素以外的像素變換為一個比特串。如果窗口中一個像素的灰度值比中心像素大，則相應位置為1，反之，即為0。Census變換公式如式(1)(2)所示:

式中，I(m，n)為變換窗口N對應的中心像素灰度值;I(x，y)為窗口內其余像素的灰度值，函數通過對這些像素值的比較，將結果串連(?)成比一個特向量code(m，n)，它表征了中心像素(m，n)與周圍像素的灰度值的比較關系。然后再利用Hamming距計算Census變換后比特串之間的差異程度，Hamming距越小，說明兩點的匹配度越高。

經過Census變換后，中心像素的灰度值被替換為一個0和1的比特串，該比特串僅與變換窗口中心像素和其他各個像素灰度大小有關，因此，Census變換對于幅度失真有著很好的抑制能力。

2.2 多相關窗口匹配

由于匹配窗口位于深度不連續(xù)的區(qū)域時會引入匹配誤差，本文中相關窗口的選取采用了文獻［10］提出的多相關窗口的匹配方法。當匹配窗口位于深度不連續(xù)的區(qū)域時，可以通過只采用深度連續(xù)區(qū)域的相關窗口來減小誤差。如圖2中(b)所示。

圖1 多窗口匹配示意圖

圖2中(c)所示為9窗口匹配方式，其中當中心窗口位于深度不連續(xù)的區(qū)域時，左右兩幅圖像的相關過程會存在歧義性。在這種情況下，假設中心窗口的代價值為C0，在周圍8個窗口中選取的代價值最小的4個窗口，設其代價值分別為分別為C1i1、C1i2、C 1i3和C1i4，那么最終的代價值C的計算入式(3)所示。

這種方法還可以擴展為25窗口處理的模式，如圖2(d)所示?？梢钥闯?，多匹配窗口可以通過通過小窗口與大窗口結合的方法以適應局部環(huán)境。采用周圍小窗口可以避免在圖像深度不連續(xù)的區(qū)域引入匹配誤差;另一方面，選用較大尺寸的相關窗口可以減少在弱紋理區(qū)域的錯誤匹配。

3 硬件實現

3.1硬件整體結構

根據任務需求，雙目立體相機中采用了一片FPGA進行左右兩路視頻數據的同步采集，預處理，在片上經過立體圖像匹配算法后，通過電路中預留的USB2.0接口，將得到的視差圖傳輸給PC機。整個相機的硬件系統(tǒng)包括視頻接口模塊，USB2.0數據傳輸模塊和視頻處理模塊。整個硬件結構原理圖如圖2所示。

圖2 基于FPGA的硬件結構原理圖

在立體圖像匹配時，要對兩組圖像做Census變換和相似度比較，在這幾個步驟中，采用流水線計算方式并對左右兩路圖像采用并行技術同時計算，大大提高了系統(tǒng)的運算速度。

3.2 多窗口相關匹配法在FPGA中的實現

對于硬件實現來說，Census變換和多窗口代價值計算是基于窗口的操作，在計算之前先要緩存與窗口高度相同的圖像行數。本文實現結構中采用了3×3子窗口和9個子窗口進行代價值計算的方式。首先，需要讀入并緩存3行數據，然后對中間的1行數據進行Census變換，變換完畢后將Census值緩存到另一個具有3行數據大小的緩存器中，為下一步的相關匹配窗口代價計算做準備。

進行數據緩存時，假設計算的是第2行數據，在計算完當前y列的數據進行第(y+1)列數據的計算時，就可以對第1行第y列數據進行更新。同樣，當計算第3行數據時，就可以對第2行數據進行同步更新。這樣，Census變換的計算與圖像像素采集形成了流水線結構，將以與圖像輸出同樣的速度進行運算，達到實時性。并且在這種情況下，對于寬度為1024的8bit灰度圖像來說，需要耗費的片上存儲資源為1K×3=3Kbyte。

在下一個相關匹配的計算單元中，因為采用3×3的子窗口，也要首先緩存3行Census值，再進行窗口代價的計算。在這一步中，需要計算不同視差情況下，匹配子窗口中中心窗口的代價值和周圍8個子窗口的代價值，并且找出其中代價值最小的4個，與中心窗口代價值進行累加。

通過以上的判決和累加后，找到代價值最優(yōu)的情況，就完成了多窗口的相關匹配，也就是得到了視差值。在本文中，立體視覺試驗系統(tǒng)將視差輸出給上位機，由上位機根據此視差值和相機的標定結果，計算出實際場景中物體的景深。圖3所示為FPGA中匹配算法的結構流程圖。

圖3 匹配算法結構流程圖

4 結果分析

通過流水線技術，采用循環(huán)數據更新結構，不僅使得計算可以實時進行，還可以充分利用緩存空間，大大降低了緩存的使用量。對于一幅尺寸為N×N個像素的圖像，假設相關窗口尺寸n×n，搜索視差的范圍是d，直接進行塊匹配計算時的復雜度為 O(N2n2d)，采用本文中的方法完成一幅灰度圖像的匹配所需的計算復雜度為 O(N2d)，與窗口尺寸無關。

在Stratix II FPGA EP2S30實驗板上實現了的文中提出的硬件結構，如圖4所示。

圖4 立體圖像處理實驗板

左右兩路輸入圖像通過視頻采集接口傳輸到實驗板，經過預處理后送入FPGA進行立體視覺算法的處理。匹配的視差圖像結果再通過USB2.0送給上位機，與Matlab變換的結果進行比較，實驗驗證了設計的正確性。圖5中，圖5(c)、圖5(d)所示為通過硬件仿真，分別將圖5(a)、圖5(b)兩幀圖像送入實驗板，經過FPGA變換后的結果。

通過與Matlab運算結果相比較，變換后的結果完全一致，驗證了硬件運算的正確性。FPGA硬件結構的描述全部采用VHDL語言，可以較方便的在不同FPGA平臺上進行移植。綜合和分析采用了QuartusII軟件，采用Modelsim進行功能仿真和時序仿真。實現1024×1024@30f/s灰度視頻圖像實時匹配功能，經過綜合，在 Stratix II FPGA EP2S30FPGA平臺中布局布線后的結果如表1所示。

圖5 FPGA實現Census變換結果

表1 FPGA綜合結果

5 結論

本文提出了在雙目立體相機中基于FPGA實現立體圖像匹配算法的一種設計。采用了改進的基于Census變換的方法，結合多窗口相關匹配和左右一致性原理，實現立體圖像匹配的實時運算。設計中結合FPGA結構的特點，充分利用流水線結構和并行執(zhí)行的思想，減少運算量和存儲器的使用，降低了資源的使用量，提高運算速度。實驗結果證明，該匹配算法結構具有較高的吞吐率和變換速度，可以工作在97.3MHz的頻率下，能夠實現1024×1024灰度圖像30f/s的圖像實時匹配。

［1］ Zhou Xing，Gao Zhi－ jun.Application and Future Development of Stereo Vision Technology［J］.Journal of Graphics，2010，04:50 －55.周星，高志軍.立體視覺技術的應用與發(fā)展［J］.工程圖學學報，2010，04:50 －55.

［2］ You Suya.State of the art and Future the development of stereo vision［J］.Journal of Image and Graphics，1997，01:17－22.游素亞.立體視覺研究的現狀與進展［J］.中國圖象圖形學報，1997，01:17 －22.

［3］ Xu Yanjun，Du Limin，Hou Ziqiang.A Scale － Adaptive Phase － Based Stereo Maching Method［J］.Acta Electronica Sinica，1997，07:38 －41.徐彥君，杜利民，侯自強.基于相位的尺度自適應立體匹配方法［J］，電子學報，1997，07:38 －41.

［4］ Zitova B，Flusser J.Image registration methods:a survey［J］.Image and Vision Computing，2003，21(11):977－1000.

［5］ Bai Ming，Zhuang Yan，Wang Wei.Progress in binocular stereo matching algorithms［J］.Control and Decision，2008，23(7):721 －729.(in Chinese)白明，莊嚴，王偉.雙目立體匹配算法的研究與進展［J］.控制與決策，2008，23(7):721 －729.

［6］ 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，Jun.17，2007:1 －6.

［7］ Chen L，Jia Yunde.A parallel reconfigurable architecture for real－time stereo vision［C］.Proceedings of the International Conference on Embedded Software and Systems，Hangzhou，May 25，2009:32 －39.

［8］ Zabih R，Woodfill J.Non － parametric local transforms for computing visual correspondence［C］//European Conference on Computer Vision，Stockholm，1994:151 －158.

［9］ Jin S，Cho J，Phan X，et al.FPGA design and implementation of a Real－ Time stereo vision system［J］.IEEE Transaction on Circuits and Systems for Video Technology，2010，20(1):15 －26.

［10］ Zhou L，Xu G L，Li K Y.Stereo matching algorithm based on Census transform and modified adaptive windows［J］.ACTA，2012，33:886 －892.(in Chinese)周龍，徐貴力，李開宇，等.基于Census變換和改進自適應窗口的立體匹配算法［J］.航空學報，2012，33:886－892.

［11］ Xiong G M，Li X.Color rank and census transforms using perceptual color contrast［C］//the 11th International，Conference on Control，Automation，Robotics and Vision，Singapore，2010:1225 －1230.

［12］ Hirschmüller H，Innocent P R，Garibaldi J.Real－ timecorrelation－based stereo vision with reduced border errors［J］.International Journal of Computer Vision，2004，47(1－3):229－246.