融合邊緣特征的SAD立體匹配算法

張一飛,李新福,田學(xué)東

(河北大學(xué) 網(wǎng)絡(luò)空間安全與計算機(jī)學(xué)院,河北 保定 071000)

0 概述

立體匹配就是找出同一視點(diǎn)在左右視圖中的坐標(biāo)位置,從而計算得到視差圖的過程[1-2]。工業(yè)測量、無人駕駛、醫(yī)療診斷等領(lǐng)域都迫切需要立體匹配生成的3D信息來幫助計算機(jī)和機(jī)器人完成各項任務(wù)[3-5]。SAD算法是實時系統(tǒng)的典型算法,但其匹配精確度不高[6]。邊緣是圖像的重要特征,優(yōu)秀的邊緣提取結(jié)果可以提高匹配的精確度。

文獻(xiàn)[7]對SAD算法進(jìn)行改進(jìn),在其比較窗口上賦予不同的權(quán)值,并與Census算法相結(jié)合提出SAD-Census算法,該算法可較好地解決左右視圖存在亮度差異的問題,但其對弱紋理區(qū)域的匹配效果不好。文獻(xiàn)[8]在實驗中將深度邊緣和紋理邊緣進(jìn)行匹配,同時采用基于邊緣線段的方法來提高算法的魯棒性,該算法能準(zhǔn)確檢測到深度圖的邊緣失真并確定位置,但是對于層次復(fù)雜且顏色相近的物體,該算法的深度值準(zhǔn)確率下降。文獻(xiàn)[9]提出一種兩階段算法,第1個階段進(jìn)行特征提取和特征匹配,第2個階段圍繞特征區(qū)域的特殊鄰域的差異增長計算視差,該算法能夠較快較好地得到視差圖,但其對特征選取的依賴性太強(qiáng)。文獻(xiàn)[10]僅使用加減和乘法運(yùn)算,而無占用計算資源較多的矩陣運(yùn)算,提出遞歸邊緣保持性雙目立體匹配算法,該算法準(zhǔn)確率高但遞歸的使用導(dǎo)致計算量增大。

本文為了保留SAD算法實現(xiàn)簡單、實時性好等優(yōu)點(diǎn),同時提高匹配精度,提出將邊緣特征與SAD算法相融合的立體匹配算法Edge-Gray。

1 SAD算法與邊緣算子選取

1.1 SAD算法簡介

SAD算法通常在左右圖上分別創(chuàng)建一個W=[(2n+1)×(2n+1)]的窗口,n為正整數(shù),固定左(或右)圖窗口,滑動右(或左)圖窗口,每次滑動后記錄窗口上相同位置的差值和,直至滑動結(jié)束,差值和最小的點(diǎn)記為左右視圖的匹配點(diǎn)[6]。其中,n的取值越大,時間消耗越長。以Cones為例,實驗中窗口大小與時間的關(guān)系如圖1所示。

圖1 窗口大小與時間的關(guān)系

1.2 邊緣算子的選取

Roberts、Prewitt、Sobel、Canny等算子都是計算圖像邊緣的有效方法[11-13],各個算子都有自己的特點(diǎn)。Roberts算子邊緣定位較準(zhǔn),但對噪聲敏感。Prewitt算子能去掉部分偽邊緣并對噪聲具有平滑作用,但是對邊緣的定位不準(zhǔn)確。Sobel算子能很好地消除噪聲的影響[14-15],但主題與背景的區(qū)分不明確。Canny算子具有很好的信噪比和檢測精度,定位性能良好,其邊緣檢測的標(biāo)準(zhǔn)較為嚴(yán)格,是一個具有濾波、增強(qiáng)、檢測的多階段的優(yōu)化算子[16],但Canny算子相比其他3個算子計算過程更為復(fù)雜[17]。綜上所述,Canny算子檢測精度高,邊緣刻畫清晰。為了減少立體匹配中可能出現(xiàn)的錯誤匹配,本文選擇使用Canny算子來計算邊緣信息。

2 Edge-Gray算法

文獻(xiàn)[18]將立體匹配算法分為4步,即匹配代價計算、代價聚合、視差計算與優(yōu)化和視差后處理。本文在上述流程上做出了調(diào)整,如圖2所示。

圖2 本文立體匹配算法流程

2.1 預(yù)處理圖像

預(yù)處理部分就是將彩色圖像轉(zhuǎn)化為灰度圖像,灰度化后的圖像一個像素由24位轉(zhuǎn)化為8位,可減少后續(xù)處理中的內(nèi)存消耗。圖像灰度化過程所用到的公式如下:

IGray(i,j)=0.299R(i,j)+0.587G(i,j)+

0.114B(i,j)

(1)

其中,IGray為彩色圖像計算轉(zhuǎn)化為灰度圖像后的灰度值。(i,j)為當(dāng)前像素點(diǎn)在圖片中的橫縱坐標(biāo),R、G、B分別為24位真彩圖像的紅、綠、藍(lán)的色值[19]。

2.2 邊緣計算

本文采用Canny算子計算圖像邊緣信息,主要包括以下3個步驟:

1)使用高斯濾波器平滑圖像,濾除噪聲。

2)計算圖像中每個像素點(diǎn)的梯度強(qiáng)度和方向。

3)應(yīng)用非極大值抑制(Non-Maximum Suppression,NMS)消除邊緣檢測帶來的雜散響應(yīng)。

2.2.1 圖像平滑

高斯濾波的主要作用是去除噪聲。由于噪聲集中于高頻信號,很容易被識別為偽邊緣,因此應(yīng)用高斯模糊去除噪聲,可降低偽邊緣的識別。由于圖像邊緣信息也是高頻信號,因此高斯模糊的半徑選擇很重要,窗口半徑越大,對噪聲的敏感度越低[19]。高斯核的生成方法如下:

(2)

其中,G(i,j)為輸出結(jié)果,它是一個大小為(2k+1)×(2k+1)的方形矩陣,k為正整數(shù)。標(biāo)準(zhǔn)差σ取值一般為k的一半,即k/2。生成的高斯核如圖3所示,其歸一化后的結(jié)果如圖4所示。

圖3 k=2且σ=1時的高斯濾波核

圖4 歸一化后的高斯濾波核

將得到的高斯核與待處理的圖像進(jìn)行卷積運(yùn)算,計算公式如下:

(3)

其中,Q(m,n)為輸出結(jié)果,G(i,j)為高斯濾波核,F(m,n)為待處理圖像,(m,n)為當(dāng)前要處理的像素點(diǎn)的坐標(biāo)值。5×5的高斯核與待處理圖像卷積后的結(jié)果如圖5所示。

圖5 高斯濾波后的圖像

2.2.2 梯度強(qiáng)度和方向計算

本文采用Sobel算子來計算水平和垂直方向的差分。在計算后返回水平和垂直方向的一階導(dǎo)數(shù)值,由此便可以確定像素點(diǎn)的梯度Ggrad和角度θ。將水平方向記為X方向,將垂直方向記為Y方向,則X方向和Y方向的Sobel算子分別如圖6、圖7所示。

圖6 X方向的Sobel算子

圖7 Y方向的Sobel算子

分別將X和Y方向的Sobel算子與高斯濾波后的圖像進(jìn)行卷積運(yùn)算,得到兩組數(shù)據(jù)Gx與Gy。計算公式與式(2)類似,在此不再贅述。

在得到Gx和Gy后,就可以利用這兩組數(shù)據(jù)來計算梯度,計算公式如下:

Ggrad=|Gx|+|Gy|

(4)

同時,每個像素點(diǎn)對應(yīng)角θ也可以由Gx和Gy求出,計算公式如下:

θ=arctan(Gy/Gx)

(5)

通過以上步驟可以得到兩組數(shù)據(jù),即各個像素點(diǎn)的梯度值Ggrad和各個像素點(diǎn)的角度θ。

2.2.3 非極大值抑制

非極大值抑制是一種邊緣稀疏技術(shù),其作用在于“瘦邊”[11]。為保證圖像中給定的邊緣應(yīng)只被標(biāo)記一次,并且在可能的情況下,使圖像的噪聲不產(chǎn)生假的邊緣。

如圖8所示,將P點(diǎn)的周圍分為4個區(qū)域,分別標(biāo)有0、1、2和3。將0°到180°分別對應(yīng)到4個區(qū)域內(nèi)。

圖8 P點(diǎn)的八鄰域圖

應(yīng)用非極大值抑制將局部最大值之外的所有梯度值抑制為0,計算結(jié)果如圖9所示。

圖9 邊緣特征圖

以θ在[0°,45°)范圍內(nèi)為例,計算過程描述如下:

1)將當(dāng)前像素的梯度強(qiáng)度與沿正負(fù)梯度方向上的2個像素進(jìn)行比較,梯度方向的點(diǎn)的像素計算方法如式(6),可得F(p1)和F(p2)。

F(p1)=(1-tanθ)E+tanθ×NE

F(p2)=(1-tanθ)W+tanθ×SW

(6)

2)如果當(dāng)前像素的梯度強(qiáng)度大于另外2個像素的梯度強(qiáng)度,即F(p)>F(p1)且F(p)>F(p2),則當(dāng)前像素點(diǎn)保留為邊緣點(diǎn),否則該像素點(diǎn)將被抑制。

2.3 視差計算

SAD算法速度快、效率高、實時性好,可以較好地滿足大部分立體匹配系統(tǒng)的需求[5],但其匹配精度不高。為此,本文引入圖像邊緣特征來提高匹配結(jié)果的精確性。改進(jìn)SAD算法后,Edge-Gray算法的流程如圖10所示。

圖10 Edge-Gray算法流程

將預(yù)處理圖像得到的左右視圖的灰度圖和邊緣特征圖分別記為Lgray、Rgray和Ledge、Redge,Edge-Gray算法描述如下:

1)確定參考圖(以左圖為參考圖,則右圖為匹配圖),在參考圖對應(yīng)的灰度圖中構(gòu)建參考窗口,窗口大小的取值W=[(2n+1)×(2n+1)],n為正整數(shù)。計算不同窗口大小下,窗口中所有值的標(biāo)準(zhǔn)差,對應(yīng)標(biāo)準(zhǔn)差最大的W即為此次匹配的窗口大小。

2)在參考圖和匹配圖中構(gòu)建大小為W的窗口,分別計算窗口中心點(diǎn)與各個鄰域點(diǎn)的差值和,記作Sgray和Sedge。

3)若Sgray>Sedge則選Lgray和Rgray為匹配源圖,反之則選Ledge和Redge為匹配源圖。然后采用經(jīng)典的SAD算法計算出當(dāng)前點(diǎn)的視差值,計算公式如下:

(7)

其中,L(x,y)和R(x,y)代表左右圖像中(x,y)點(diǎn)的灰度值。用i和j遍歷匹配窗口中的每一個像素點(diǎn),每次計算d加1直到遍歷完W。當(dāng)CSAD最小時所得點(diǎn)即為匹配點(diǎn),d即為所求視差。

4)逐一取出參考圖中的每一個點(diǎn)進(jìn)行上述步驟,得到左圖的視差圖。

5)將左視圖作為匹配圖,右視圖作為參考圖,重復(fù)步驟2～步驟4得到右圖的視差圖。

2.4 視差后處理

視差后處理專為除去視差圖中的錯誤點(diǎn)而設(shè)計。該過程包含左右一致性檢測、奇異點(diǎn)填充和平滑濾波3個步驟。

在左右視圖中,存在某些區(qū)域在其中一幅圖中可見,而在另一幅圖中被遮擋,視差圖中的錯誤點(diǎn)主要來源于圖片中的遮擋區(qū)域,這些區(qū)域往往會造成深度圖的不連續(xù)。左右一致性檢測所采用的公式如下:

DL(x,y)=DR(x-DL(x,y),y)

(8)

其中,DL和DR分別為左右視圖的視差圖,(x,y)為當(dāng)前點(diǎn)的坐標(biāo),不能滿足式(8)的點(diǎn)為奇異點(diǎn)。以奇異點(diǎn)為中心,向左右搜尋距離最近的非遮擋點(diǎn)中較小的值來填充。

在平滑濾波過程中,本文采用中值濾波[20]的方法對像素點(diǎn)進(jìn)行檢測與恢復(fù)。具體操作為取出中心點(diǎn)周圍8鄰域或24鄰域的灰度值,將這些深度值排序,取排序后中間位置的值為當(dāng)前像素點(diǎn)的深度值。

3 實驗結(jié)果與分析

本文實驗參數(shù)如下:操作系統(tǒng)為64位Windows10專業(yè)版,CPU為Intel(R)Core(TM)i7-6700,CPU主頻為3.40 GHz(3 408 MHz),內(nèi)存8 GB,顯卡AMD Radeon(TM) R5 340X(2 048 MB)。

將本文所得的實驗結(jié)果圖與理想視差計算所得深度圖進(jìn)行比較,將同一位置的像素值作差,超出閾值的點(diǎn)記為誤匹配點(diǎn),遍歷所有點(diǎn)即可得到實驗的誤匹配率。所得的實驗結(jié)果如圖11所示。

圖11 3種算法的匹配結(jié)果對比

圖11(a)～圖11(c)分別為傳統(tǒng)SAD算法(記為Gray)、單純使用邊緣增強(qiáng)圖(記為Edge)和本文算法(記為Edge-Gray)的匹配結(jié)果。可以看出,Edge算法在紋理較多的區(qū)域的匹配結(jié)果要優(yōu)于Gray算法,但在紋理較弱、純色區(qū)域較多的區(qū)域,Gray算法要優(yōu)于Edge算法。總體而言,本文算法雖然在弱紋理的純色區(qū)域提升效果不明顯,但在邊緣較多、紋理較豐富的區(qū)域有較好的匹配結(jié)果。具體數(shù)據(jù)如表1和表2所示。

表1 4種算法的誤匹配率對比

表2 4種算法的時間消耗對比

由表1和表2可知,本文提出的融合邊緣特征的SAD立體匹配算法精確度較好,該算法既能提高傳統(tǒng)算法在邊緣豐富區(qū)域的匹配精確度,又改善了該算法在純色和邊緣較少的區(qū)域匹配精度較低的特點(diǎn)。同時,從時間上看,本文算法與傳統(tǒng)SAD算法的時間消耗相近,具有較好的實時性。

4 結(jié)束語

本文對傳統(tǒng)的SAD算法進(jìn)行改進(jìn),提出一種融合邊緣特征的立體匹配算法。通過預(yù)處理得到邊緣特征圖,根據(jù)匹配窗口中像素點(diǎn)的標(biāo)準(zhǔn)差對自適應(yīng)窗口大小進(jìn)行處理。在匹配過程中,不同于傳統(tǒng)的立體匹配算法只利用灰度圖進(jìn)行匹配,而是融合了邊緣特征圖和灰度圖。實驗結(jié)果表明,與傳統(tǒng)SAD算法相比,該算法的耗時與其相近,但誤匹配率普遍降低,對于邊緣較多的Cones效果最為明顯,該算法的誤匹配率可降低10.52%。然而,在弱紋理和純色區(qū)域較多的部分,本文算法的匹配準(zhǔn)確率不高,針對該問題進(jìn)行改進(jìn)將是下一步的研究方向。