熊邦書，程 駿

(無(wú)損檢測(cè)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(南昌航空大學(xué))，南昌330063)

0 引言

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

1 算法描述

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

1.1 邊緣提取

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

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

1.2 匹配代價(jià)計(jì)算

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

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

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

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

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

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

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

以第二類聚合窗為例，匹配代價(jià)計(jì)算的主要過(guò)程如下:

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

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

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

經(jīng)過(guò)實(shí)驗(yàn)證明，本算法將原始計(jì)算量減少了接近一半，提高了算法的效率。

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

圖3 改進(jìn)算法示意圖Fig.3 Sketch maps of improved algorithm

1.3 視差選擇

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表1 試驗(yàn)所用算法的運(yùn)行參數(shù)Table 1 Parameters of the algorithm

圖4 試驗(yàn)結(jié)果Fig.4 Results by test

3 結(jié)論

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

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

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

［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］.微計(jì)算機(jī)信息(測(cè)控自動(dòng)化)，2009，25:184－191.

［13］王愛(ài)紅，王瓊?cè)A，李大海，等.立體顯示中立體深度與視差圖獲取的關(guān)系［J］.光學(xué)精密工程，2009，17:433－438.