基于多窗體的改進視差圖算法及其應用

熊邦書，程 駿

(無損檢測技術教育部重點實驗室(南昌航空大學)，南昌330063)

0 引言

隨著攝像硬件設備性能的提高，立體視覺技術廣泛應用于三維測量領域，而視差圖計算又是立體視覺技術中的關鍵技術，決定三維測量的精度和效率，近年來得到國內外學者的廣泛關注。視差圖算法按照不同的匹配基元，可分為全局匹配算法［1-4］和區(qū)域匹配算法［5-12］2 類。全局匹配算法利用了圖像的全局約束信息，對于局部區(qū)域敏感度小、匹配精度高，但它的計算代價很高，很難應用到有實時性要求的工程中，典型的全局匹配算法有圖割算法［4］和置信傳播算法［3］2類。局部匹配算法選取特征點鄰域內的1個或多個子窗口(又稱為聚合窗)，在另一幅圖像中的1個區(qū)域內，根據某種相似性判斷依據，尋找與子窗口圖像最為相似的子圖，對應的像素點為該特征點的匹配點，其優(yōu)點是效率高，但對于遮擋和單一紋理圖像誤匹配率高、魯棒性不佳。局部匹配算法可分為自適應聚合窗(Adaptive Window)算法［8-9］、自適應權值聚合窗算法［10］和多窗聚合(Multi-window)算法［11］等。傳統(tǒng)的多窗算法采用大小為3的聚合窗，對左右視圖的圖像進行匹配代價計算，并選擇匹配度最好的像素作為匹配像素。由于其聚合窗尺寸小無法有效過濾圖像的噪聲以及景物邊緣影響，導致算法的誤匹配率高，無法滿足工業(yè)檢測的精度需求，因此提出了使用大型聚合窗的多窗算法［11］。使用大窗的多窗算法在匹配代價計算過程中，并未對傳統(tǒng)多窗算法進行改進，僅采用了尺寸為9的大型聚合窗進行匹配代價計算，隨著聚合窗的尺寸增大，圖像在匹配過程中能夠更好的過濾噪聲并減小邊緣影響，但計算量大，這也導致算法時間度增加，無法將其應用在時間度要求較高的工程中。通過提取圖像邊緣，縮小目標像素匹配范圍，并對傳統(tǒng)的多窗算法進行改進及優(yōu)化，以提高本算法的精度和效率。

1 算法描述

本算法的主要步驟有:1)邊緣提取，對左右視圖的圖像進行邊緣提取，縮小像素點的可能匹配區(qū)域;2)匹配代價計算(代價聚合)，利用改進的多窗算法［1-2，11］對左右視圖進行匹配代價計算;3)視差選擇，按照WTA(winner takes all)勝者為王算法［1-2］對匹配代價進行選擇，確定視差圖。

1.1 邊緣提取

根據立體視覺中極線理論［1-2，13］的約定，左右視圖的同一個像素點必然處于同一根掃描線上(在兩幅掃描線對齊的圖像意味著處于同一水平線上)，則左視圖中的像素點(圖像坐標為(x，y))一定出現在右視圖中圖像坐標為(x+1，y)至(x+d，y)這一段區(qū)域中，d的取值可以在雙目攝像機標定時進行估算。傳統(tǒng)的多窗算法為了確定一對匹配像素點，需要進行d次匹配代價計算，增加了算法的計算時間。

首先通過Canny算子提取圖像邊緣，然后為左視圖的每一個像素點，在右視圖中遍歷1到d這一區(qū)域，找出灰度值相同的點，由此區(qū)分邊緣與背景像素的匹配范圍，邊緣區(qū)域只需針對邊緣匹配區(qū)域范圍進行匹配代價計算，背景區(qū)域只需針對背景匹配區(qū)域范圍進行匹配代價計算。

1.2 匹配代價計算

匹配代價計算是視差圖算法最重要的一步，匹配代價計算的好壞直接影響到將來視差計算的正確與否。本算法的匹配代價計算采用SAD算法［1］，SAD算法在聚合窗覆蓋范圍內對每對像素點進行AD運算(差的絕對值)，然后累加得到結果，該算法具有計算簡單以及運算速度快的特點，其計算公式為

其中，IL(x+i，y+j)代表左視圖中像素點(x+i，y+j)處的灰度值，IR(x+d+i，y+j)代表右視圖中像素點(x+d+i，y+j)處的灰度值，N代表聚合窗的大小。

在匹配代價的計算過程中，大型的聚合窗能很好地過濾噪聲和曝光強度影響，但計算量大導致算法的速度無法保證，而小型聚合具有較快的計算速度，但對于噪聲和曝光強度的影響表現很敏感，容易產生誤匹配。經過大量的試驗分析，本算法使用大小為9的聚合窗，具有較好的過濾噪聲及曝光強度的效果，并通過優(yōu)化算法提高算法的效率，圖1為優(yōu)化算法聚合窗的示意圖。

圖1 聚合窗示意圖Fig.1 Sketch map of aggregation window

傳統(tǒng)的多窗算法通過在聚合窗上滑動核來改變聚合窗的覆蓋范圍，減小聚合窗在物體邊緣位置時由背景所產生的匹配誤差。為了保證匹配的精度，不固定核的位置，聚合窗上的每一個位置都可以作為核位置，這也使得算法無法使用大型聚合窗，曝光和噪聲的影響也隨著增大。本算法在傳統(tǒng)的多窗算法基礎上進行改進，沿用大窗多窗算法所使用的大型聚合窗，通過對聚合窗分析及大量實驗，發(fā)現通過固定核的位置可以得到9個特殊位置的聚合窗(圖2)，用它們替代傳統(tǒng)多窗算法的聚合窗，可大幅度減小算法計算量，提高了算法計算速度。

匹配代價的具體計算方法是，分別計算每對像素9個聚合窗的匹配代價，取最佳匹配代價作為左右視圖像素的匹配代價結果，并由此得到視差。為進一步提高本算法速度，將9個聚合窗分為3類:核位于最上層的聚合窗，稱之為第一類聚合窗(圖2a～圖2c);核位于中間的聚合窗，稱之為第二類聚合窗(圖2d～圖2f);核位于最下層的第三類聚合窗(圖2g～圖2i)，采用計算機緩存技術存儲中間計算結果，提高了匹配代價的計算效率。

圖2 特殊聚合窗示意圖Fig.2 Sketch maps of special aggregation window

以第二類聚合窗為例，匹配代價計算的主要過程如下:

1)先計算核位于中間聚合窗的SAD值，如圖3a所示。將該聚合窗分為3個區(qū)域，分別用白色、黑色及黑白相間像素點區(qū)分，白色和黑色區(qū)域分別覆蓋了另兩個聚合窗的相應顏色像素區(qū)域，黑白相間區(qū)域為3個聚合窗的公共區(qū)域，通過計算分別得到白色區(qū)域匹配代價Csad_left-common(x，y)、黑色區(qū)域匹配代價Csad_right-common(x，y)、黑白相間匹配代價Ccommon(x，y)，將其保存在內存中。該窗的SAD值為白色區(qū)域匹配代價、黑色區(qū)域匹配代價與黑白相間區(qū)域匹配代價之和。

2)計算核位于左側聚合窗SAD值，如圖3b所示。由于已知 Csad_right-common(x，y)和 Ccommon(x，y)，只需計算右邊新增四列像素的匹配代價，命名為Cnew_left(x，y)，如圖3b陰影部分所示，將3者相加即可得到該窗SAD值。

3)計算核位于右側聚合窗SAD值，如圖3c所示。計算方法與計算核位于左側聚合窗相類似，只需計算左邊新增四列像素的SAD值，命名為Cnew_right(x，y)，如圖3c陰影部分所示。

經過實驗證明，本算法將原始計算量減少了接近一半，提高了算法的效率。

改進的多窗算法計算公式如式(2)所示，其中，Ccenter(x，y)、Cleft(x，y)、Cright(x，y)分別代表同一類聚合窗的3個匹配代價。

圖3 改進算法示意圖Fig.3 Sketch maps of improved algorithm

1.3 視差選擇

本算法的視差選擇步驟采用WTA算法［1-2］(Winner Takes All，勝者為王算法)。在匹配過程中，每對像素點都可得到一個匹配代價數組，保存該對像素點在9個聚合窗下的匹配代價，由于SAD算法的特性，在這9個匹配代價中選擇最小的匹配代價作為該對像素點的匹配代價。由于左視圖中的一個像素點可能出現在右視圖的某個區(qū)域內(根據極線理論，處于同一條掃描線的一段線段中)，因此對于一個目標像素點，可能存在多個匹配像素對，將每對像素點的匹配代價保存在新數組中，數組的長度由像素對個數決定，對該數組再次進行比較，取最小匹配代價的像素點對作為正確匹配像素對，進而確定視差。WTA算法的計算公式如式(3)，N代表匹配像素的個數，d代表左右視圖像素點的匹配區(qū)域。

2 實驗結果與分析

為驗證本算法的有效性，采用由Tsukuba大學網站上提供的雙目立體視覺視差圖研究的圖源進行實驗，如圖4所示，其中4a和4b分別為左右視差圖，4c為標準視差圖，并將本算法與傳統(tǒng)的多窗算法［11］和大窗多窗算法［10］進行對比實驗，其結果分別如圖4d、4e、4f所示，從圖中可以看出本算法具有較高的匹配精度，對具有復雜紋理的圖像區(qū)域有較好的魯棒性，在圖像邊緣區(qū)域減小了噪聲對匹配精度的影響，并提高了算法的速度。

為了量化評估本算法的性能，本試驗采用平方根誤差算法［1］量化評估視差圖，平方根誤差算法計算公式如式(4)所示。

其中，dC(x，y)代表算法視差圖中位置為(x，y)處的像素灰度值，dT(x，y)代表標準視差圖中位置為(x，y)處的像素灰度值，N代表視差圖的像素總數。采用計算機CPU運算時間評估算法效率，所有實驗均在 Intel酷睿2雙核 CPU(主頻2.4 GHz)及2 G內存環(huán)境下進行。

傳統(tǒng)多窗視差圖算法、大窗多窗視差圖算法以及改進多窗視差圖算法的量化對比結果如表1所示，從表中可以看出本算法相對于傳統(tǒng)多窗視差圖算法具有更好的匹配精度，相對于大窗多窗算法具有更快的運算速度。經過大量試驗證明，本算法匹配精度高、效率高，能有效過濾圖像中背景所造成的誤匹配，對于背景復雜圖像具有較好的匹配結果，魯棒性好。

表1 試驗所用算法的運行參數Table 1 Parameters of the algorithm

圖4 試驗結果Fig.4 Results by test

3 結論

1)在傳統(tǒng)的多窗視差圖算法和大窗視差圖算法上進行改進，提出了一種基于多窗體的改進視差圖算法，通過邊緣提取和固定聚合窗的方式，提高了算法的匹配精度和效率。

2)在本算法的匹配代價計算過程中，采用了計算機緩存技術，將特殊聚合窗分為3類，通過保存中間計算結果優(yōu)化算法的計算量，進一步提高了算法的效率。

3)本算法相對于傳統(tǒng)的多窗體視差圖算法和大窗多窗視差圖算法具有更高的運算效率和匹配精度，對于復雜背景以及圖像噪聲具有較好的去除效果，可應用于背景復雜、精度要求較高的工業(yè)、計算機立體視覺領域。

［1］Scharstein D，Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms［J］.International Journal of Computer Vision，2002，46(1):7－42.

［2］Richard S.Computer Vision:Algorithms and Applications［M］.Springer，2001:1 －812.

［3］Klaus A，Sormann M，Karner K.Segment-based stereo matching using belief propagation and a selfadapting dissimilarity measure［C］. Proceeding ofInternationalConference on Pattern Recognition，2006，3:15－18.

［4］Hong L，Chen G.Segment-based stereo matching using graph cuts［C］.IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2004，1:74－81.

［5］Mattoccia S.A locally global approach to stereo correspondence［C］.IEEE 12th International Conference on Computer Vision Workshops，2009，10:1763－1770.

［6］Stefano L D，Marchionni M，Mattoccia S.A fast area-based stereo matching algorithm ［J］.Image and Vision Computing，2004，22(12):983－1005.

［7］Hirschmuller H，Innocent P R，Garibaldi J.Real time correlation based stereo vision with reduced border errors［J］.International Journal of Computer Vision，2001，47(1/2/3):229－246.

［8］Veksler O.Fast variable window for stereo correspondence using integral images［C］.Proceeding of IEEE Conference on Computer Vision and Pattern Recognition，2003，1:556－561.

［9］Kanade T，Okutomi M.A stereo matching algorithm with an adaptive window:theory and experiment［J］.IEEE Transactions Pattern Analysis and Machine Intelligence，1994，16(9):920 －932.

［10］Federico T，Stefano M，Luigi D S，et al.Classification and evaluation of cost aggregation methods for stereo correspondence［C］//IEEE Conferenceon ComputerVision and Pattern Recognition，2008:1 －8.

［11］Fusiello A，Roberto V.Efficient stereo with multiple windowing［C］//IEEE ConferenceOnComputerVisionandPattern Recognition，1997:858－863.

［12］劉維羅，桂娥楊，欣榮.一種快速魯棒區(qū)域匹配算法［J］.微計算機信息(測控自動化)，2009，25:184－191.

［13］王愛紅，王瓊華，李大海，等.立體顯示中立體深度與視差圖獲取的關系［J］.光學精密工程，2009，17:433－438.