基于視差范圍估計(jì)和改進(jìn)代價(jià)的半全局匹配

彭 妍, 郭君斌,*, 于傳強(qiáng), 李靜波

(1. 火箭軍工程大學(xué)導(dǎo)彈工程學(xué)院,陜西 西安 710025; 2. 中國(guó)人民解放軍96873部隊(duì),陜西 寶雞 721000)

0 引 言

立體匹配通過(guò)尋找左右圖像中的同名點(diǎn),計(jì)算視差,從而獲取物體的深度信息。近年來(lái),隨著立體匹配技術(shù)的發(fā)展,立體匹配已被廣泛應(yīng)用在三維重建、目標(biāo)檢測(cè)、自動(dòng)駕駛、虛擬現(xiàn)實(shí)等領(lǐng)域。Scharstein等人在總結(jié)之前的立體匹配方法后提出了立體匹配的常規(guī)基本框架。在該框架中,立體匹配被劃分為匹配代價(jià)計(jì)算、代價(jià)聚合、視差計(jì)算和視差優(yōu)化4個(gè)步驟。根據(jù)計(jì)算策略的不同,傳統(tǒng)立體匹配方法又可被分為局部、全局和半全局3類算法。其中,半全局匹配算法(semi-global matching, SGM)綜合考慮了速度和精度對(duì)匹配的影響,應(yīng)用最為廣泛。

視差范圍作為立體匹配中的一個(gè)重要概念,用來(lái)確定匹配點(diǎn)的候選范圍,卻沒(méi)有得到傳統(tǒng)SGM算法的重視。在實(shí)際場(chǎng)景中,立體圖像對(duì)的視差范圍通常不能預(yù)知,一般解決方法是人為地設(shè)定一個(gè)視差范圍,但是這種方法比較主觀,沒(méi)有理論依據(jù),得到的視差范圍往往并不準(zhǔn)確。若視差范圍過(guò)大,導(dǎo)致計(jì)算資源浪費(fèi);若視差范圍過(guò)小,容易導(dǎo)致視差計(jì)算錯(cuò)誤。因此有效的視差范圍估計(jì)在立體匹配中就顯得尤為重要。

匹配代價(jià)計(jì)算作為立體匹配的第一步,為后續(xù)優(yōu)化得到準(zhǔn)確的視差值提供了基礎(chǔ)。傳統(tǒng)SGM算法通常采用Census變換進(jìn)行代價(jià)計(jì)算,而傳統(tǒng)Census變換僅考慮圖像的亮度信息做Hamming距離計(jì)算匹配代價(jià),在圖像的重復(fù)紋理區(qū)域,計(jì)算結(jié)果具有模糊性,容易導(dǎo)致誤匹配,進(jìn)而影響視差計(jì)算精度。

針對(duì)視差范圍通常不能預(yù)知的問(wèn)題,毛苗等人提出了一種基于圖像細(xì)分的快速視差范圍估計(jì)算法;董本志等人在毛苗的基礎(chǔ)上,提出了一種基于前向搜索的圖像迭代細(xì)分方法來(lái)估計(jì)視差范圍,得到更精確的視差范圍;李海超等人利用特征點(diǎn)擬合空間平面,根據(jù)平面估計(jì)視差范圍,有效提高了匹配的速度和精度;Yang等人使用金字塔匹配策略計(jì)算不同金字塔圖像上每個(gè)像素的視差范圍。

針對(duì)傳統(tǒng)Census變換的問(wèn)題,Mei等人提出了將灰度差絕對(duì)值和Census變換結(jié)合,提高了弱紋理和重復(fù)紋理區(qū)域的匹配精度;閆利等人提出了將梯度與Census變換結(jié)合,提高了弱紋理區(qū)域的匹配結(jié)果;Zhu等人提出了將Census變換、顏色和梯度作為混合匹配代價(jià);Liu等人提出了將增強(qiáng)的圖像梯度和改進(jìn)的Census變換結(jié)合,對(duì)無(wú)紋理區(qū)域具有較好的魯棒性。

針對(duì)傳統(tǒng)SGM算法存在的不足,提出了一種基于視差范圍估計(jì)和改進(jìn)代價(jià)的半全局匹配算法。首先,采用二元穩(wěn)健恒定可擴(kuò)展關(guān)鍵點(diǎn)(binary robust invariant scalable keypoints,BRISK)、加速穩(wěn)健特征(speeded up robust feature,SURF)和方向描述符(oriented brief,ORB)算子同時(shí)提取圖像對(duì)的特征點(diǎn),對(duì)所有特征點(diǎn)統(tǒng)一采用SURF描述子計(jì)算特征向量,通過(guò)快速最近鄰搜索方法(fast library for approximate nearest neighbors,FLANN)進(jìn)行特征點(diǎn)匹配,利用立體匹配的約束條件篩選匹配點(diǎn),對(duì)篩選后的匹配點(diǎn)對(duì)計(jì)算視差值,估計(jì)圖像的視差范圍;然后,在估計(jì)好的視差范圍內(nèi),分別對(duì)圖像的亮度、梯度和邊緣信息進(jìn)行Census變換和Hamming距離計(jì)算,將三者的計(jì)算結(jié)果融合,構(gòu)建新的代價(jià)計(jì)算函數(shù)。與傳統(tǒng)SGM算法相比,所提算法不僅提高了視差計(jì)算效率,而且改善了重復(fù)紋理、弱紋理及邊緣區(qū)域的視差結(jié)果,提高了視差計(jì)算精度。

1 基于特征點(diǎn)的視差范圍估計(jì)

針對(duì)傳統(tǒng)SGM算法對(duì)視差范圍未知場(chǎng)景，通常人為確定一個(gè)視差范圍,造成計(jì)算資源浪費(fèi)的不足,提出了一種基于特征點(diǎn)的視差范圍估計(jì)方法。該方法的核心在于統(tǒng)計(jì)左右圖像中特征點(diǎn)對(duì)的有效視差來(lái)估計(jì)整個(gè)圖像的視差范圍,進(jìn)而達(dá)到快速、可靠估計(jì)視差范圍的目的。

1.1 特征點(diǎn)的提取和匹配

目前,常見(jiàn)的特征點(diǎn)算法有:尺度不變特征變換(scale-invariant feature transform,SIFT)、SURF、加速分割測(cè)試獲得特征(features from accelerated segment test,FAST)、BRISK以及ORB等。其中,SIFT是一種非常穩(wěn)定的局部特征,但本身計(jì)算過(guò)程過(guò)于復(fù)雜,實(shí)時(shí)性不高;SURF是SIFT的加速版,核心在于采用了Hessian矩陣和盒子濾波器等概念,比SIFT更快更具有魯棒性;FAST檢測(cè)速度快,可應(yīng)用在實(shí)時(shí)場(chǎng)景中,但容易受到噪聲的影響,魯棒性較差;BRISK檢測(cè)速度快,具有較好的魯棒性;ORB運(yùn)行時(shí)間遠(yuǎn)低于SIFT和SURF,可用于實(shí)時(shí)的特征檢測(cè)。

為了使特征點(diǎn)對(duì)的視差值能更全面地表征圖像的視差范圍,提高視差范圍估計(jì)的可靠性,需要盡可能多地提取圖像的特征點(diǎn)。因此,首先聯(lián)合幾種運(yùn)行速度較快且魯棒性較好的SURF、BRISK、ORB算子同時(shí)檢測(cè)圖像對(duì)的特征點(diǎn);然后對(duì)所有特征點(diǎn)統(tǒng)一采用魯棒性最好的SURF描述子計(jì)算特征向量;最后通過(guò)FLANN方法進(jìn)行特征點(diǎn)匹配,獲得初始的特征匹配結(jié)果。待匹配圖像對(duì)錐面如圖1所示,初始匹配結(jié)果如圖2所示,一共生成了4 995對(duì)匹配點(diǎn)對(duì),但存在大量明顯錯(cuò)誤的匹配點(diǎn)對(duì)。

圖1 立體圖像對(duì)錐面Fig.1 Stereoscopic image pair cones

圖2 初始匹配結(jié)果Fig.2 Initial match result

1.2 剔除錯(cuò)誤的匹配點(diǎn)對(duì)

為了減小錯(cuò)誤的匹配點(diǎn)對(duì)對(duì)視差范圍估計(jì)的影響,提高視差范圍估計(jì)的可靠性,利用立體匹配的約束條件對(duì)匹配點(diǎn)進(jìn)行篩選。常見(jiàn)的立體匹配約束準(zhǔn)則有以下幾點(diǎn)。

(1) 極線約束:將左右圖像的極線對(duì)齊,使得匹配點(diǎn)對(duì)在同一水平線上,匹配點(diǎn)對(duì)應(yīng)該具有相同的縱坐標(biāo)。

(2) 相似性約束:匹配點(diǎn)對(duì)應(yīng)該具有相似的灰度值和梯度值。

(3) 視差范圍約束:沿著極線方向搜索匹配點(diǎn)時(shí),搜索的范圍受到最大視差值的約束。

綜合上述約束條件對(duì)匹配點(diǎn)進(jìn)行篩選,滿足條件保留,不滿足條件剔除。假設(shè)、分別是左右圖像中對(duì)應(yīng)的特征點(diǎn),總的約束條件為

(1)

式中:(·)、(·)分別表示特征點(diǎn)對(duì)應(yīng)的灰度值和梯度值;、分別表示特征點(diǎn)的橫縱坐標(biāo);、、分別表示匹配點(diǎn)對(duì)對(duì)于灰度值、梯度值和縱坐標(biāo)設(shè)定的允許波動(dòng)的截?cái)嘀?表示人為設(shè)定的視差最大值。

篩選后的匹配結(jié)果如圖3所示,此時(shí)還有1 053對(duì)匹配點(diǎn)對(duì),剔除了大量錯(cuò)誤的匹配點(diǎn)對(duì),匹配點(diǎn)對(duì)都保持在同一極線上。

圖3 篩選后的匹配結(jié)果Fig.3 Filtered matching results

1.3 視差范圍估計(jì)

根據(jù)篩選后的特征匹配結(jié)果計(jì)算視差,估計(jì)圖像的視差范圍。雖然通過(guò)約束條件剔除了大量的誤匹配點(diǎn),但匹配結(jié)果中仍存在異常值。多次實(shí)驗(yàn)結(jié)果表明,為了增強(qiáng)視差范圍估計(jì)的魯棒性,對(duì)匹配點(diǎn)對(duì)計(jì)算視差后,舍去其中的最大和最小視差值,選擇次最大和次最小視差值分別作為視差范圍的上下邊界。為了進(jìn)一步增強(qiáng)魯棒性,還應(yīng)對(duì)次最大和次最小視差值進(jìn)行一定補(bǔ)償,作為最終視差范圍的上下邊界。表1為錐面的視差估計(jì)范圍和真實(shí)范圍對(duì)比。

表1 視差范圍對(duì)比

2 改進(jìn)的代價(jià)計(jì)算

2.1 傳統(tǒng)的Census變換

傳統(tǒng)SGM算法通常采用Census變換進(jìn)行匹配代價(jià)計(jì)算。傳統(tǒng)Census變換將中心像素及其鄰域內(nèi)像素亮度的相對(duì)大小關(guān)系轉(zhuǎn)換為比特串,作為中心像素的Census變換值:

(2)

(3)

式中:?表示按位連接,選取中心像素(,)周?chē)笮椤恋拇翱?′=|2|,′=|2|;(·)表示圖像像素的亮度。

計(jì)算左右圖像Census變換值Cen和Cen的Hamming距離作為中心像素的初始匹配代價(jià):

(,,)=
Hm[Cen(,),Cen(-,)]

(4)

2.2改進(jìn)的代價(jià)計(jì)算

傳統(tǒng)Census變換進(jìn)行匹配代價(jià)計(jì)算時(shí)僅考慮了圖像的亮度信息,在重復(fù)紋理區(qū)域易導(dǎo)致誤匹配。弱紋理區(qū)域主要通過(guò)邊緣信息進(jìn)行匹配,匹配時(shí)過(guò)于依賴邊緣閾值,而且在復(fù)雜的背景環(huán)境下確定有效的邊緣閾值并不容易。為了提高重復(fù)紋理和弱紋理區(qū)域的匹配精度,分別對(duì)圖像的亮度、梯度和邊緣信息進(jìn)行Census變換和Hamming距離計(jì)算,將三者計(jì)算結(jié)果融合,構(gòu)建新的代價(jià)計(jì)算函數(shù)。

圖像的梯度是一個(gè)用來(lái)衡量圖像水平和垂直方向上灰度變化率的二維向量,即:

(5)

數(shù)字圖像本質(zhì)上是一個(gè)二維離散函數(shù),一般使用灰度差分近似對(duì)圖像求導(dǎo),則圖像在(,)處的水平和垂直方向的梯度值分別通過(guò)中值差分表示為

(6)

式中:(,)為圖像在(,)處的灰度值。

結(jié)合水平和垂直方向的梯度值,得到圖像的梯度信息:

(7)

圖像的邊緣是圖像中兩個(gè)區(qū)域的交接處,通常是局部亮度或結(jié)構(gòu)發(fā)生急劇變化的地方。Sobel是一種典型的邊緣檢測(cè)算子,一般利用水平和垂直方向上的兩個(gè)簡(jiǎn)單的3×3內(nèi)核,如圖4所示,與圖像進(jìn)行卷積操作得到圖像梯度的近似值,通過(guò)判斷梯度值與邊緣閾值的大小關(guān)系獲取圖像的邊緣信息。

圖4 Sobel算子Fig.4 Sobel operator

得到圖像的亮度、梯度和邊緣信息后,引入估計(jì)好的視差范圍,分別對(duì)它們進(jìn)行Census變換、Hamming距離計(jì)算,則像素點(diǎn)(,)在視差下,基于圖像邊緣和基于圖像梯度的匹配代價(jià)分別表示為

(8)

(9)

式中:(·)、(·)分別表示圖像的邊緣值和梯度值;Cen(·)、Cen(·)分別表示基于邊緣和基于梯度的Census變換值,(·)、(·)分別表示基于邊緣和基于梯度的匹配代價(jià);[,]為事先估計(jì)好的視差范圍。

將分別基于圖像邊緣、亮度和梯度的匹配代價(jià)融合,構(gòu)建新的代價(jià)計(jì)算函數(shù):

∈[,]

(10)

對(duì)于重復(fù)紋理區(qū)域,改進(jìn)的代價(jià)計(jì)算在Census變換的基礎(chǔ)上,綜合考慮了鄰域內(nèi)圖像的亮度、梯度和邊緣信息對(duì)匹配的影響;對(duì)于弱紋理區(qū)域,改進(jìn)的代價(jià)計(jì)算對(duì)邊緣信息進(jìn)行Census變換,匹配時(shí)將不再關(guān)注于邊緣的具體取值,而在于鄰域內(nèi)邊緣的相對(duì)大小關(guān)系,削弱了邊緣閾值對(duì)于匹配的影響,進(jìn)而有效地改善了重復(fù)紋理以及弱紋理區(qū)域的匹配效果。

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

將經(jīng)過(guò)立體校正的圖像對(duì)作為本文算法的輸入,首先利用基于特征點(diǎn)的視差范圍估計(jì)方法估計(jì)出圖像的視差范圍,然后將估計(jì)的視差范圍引入傳統(tǒng)SGM算法中,依次進(jìn)行改進(jìn)的代價(jià)計(jì)算、代價(jià)聚合、視差計(jì)算及視差優(yōu)化。傳統(tǒng)SGM算法和本文算法的流程圖對(duì)比如圖5所示。

本文采用Middlebury立體匹配測(cè)評(píng)網(wǎng)站提供的4幅標(biāo)準(zhǔn)圖像對(duì)筑波、金星、泰迪、錐面進(jìn)行實(shí)驗(yàn),涉及實(shí)驗(yàn)參數(shù)的設(shè)置如表2所示。實(shí)驗(yàn)環(huán)境在CPU為Intel core i5 1.80 GHz, 操作系統(tǒng)為Windows 10的個(gè)人電腦上的Visual Studio 2019下,配合圖像處理開(kāi)源庫(kù)OpenCV 3.2.0。

圖5 不同算法的流程圖Fig.5 Diagram of different methods

表2 實(shí)驗(yàn)參數(shù)設(shè)置

為了驗(yàn)證所提算法的性能,選取了傳統(tǒng)SGM算法進(jìn)行實(shí)驗(yàn)對(duì)比,如圖6所示,從左到右依次為圖像對(duì)的左圖、真實(shí)視差圖以及傳統(tǒng)算法和所提算法生成的視差圖。首先對(duì)傳統(tǒng)SGM算法和所提算法進(jìn)行定性分析。本文用白色方框框出了視差圖的部分區(qū)域,如圖6(c)和圖6(d)所示。相比傳統(tǒng)算法,對(duì)于筑波和金星,本文算法在白色方框區(qū)域上的物體邊緣更清晰,輪廓曲線更平滑,更接近真實(shí)視差圖,說(shuō)明所提算法有效改善了深度不連續(xù)區(qū)域的匹配效果;對(duì)于具有復(fù)雜場(chǎng)景的泰迪,所提算法在白色方框區(qū)域上視差計(jì)算結(jié)果更為精確,說(shuō)明所提算法有效改善了邊緣遮擋區(qū)域的視差精度;對(duì)于同樣具有復(fù)雜背景的錐面,在具有重復(fù)紋理的三角圓錐區(qū)域,所提算法也成功匹配出了各個(gè)圓錐,說(shuō)明所提算法有效改善了弱紋理及重復(fù)紋理區(qū)域的視差精度。然后對(duì)傳統(tǒng)SGM算法與本文算法進(jìn)行了定量分析。從3個(gè)區(qū)域非遮擋區(qū)域(non)、所有區(qū)域(all)以及深度不連續(xù)區(qū)域(disc)分別來(lái)驗(yàn)證算法的魯棒性。將算法生成的視差圖與真實(shí)視差圖進(jìn)行比較,相差結(jié)果大于誤差閾值(本文設(shè)定閾值為1)的像素被視為誤匹配。這兩種算法在測(cè)試圖像對(duì)上的誤匹配率如表3所示,運(yùn)行時(shí)間如表4所列,實(shí)驗(yàn)結(jié)果表明,本文算法在這4幅圖像對(duì)上所有區(qū)域的誤匹配率均低于傳統(tǒng)算法,平均誤匹配率為7.65%,相比傳統(tǒng)算法降低了6.38%,在提高整體匹配精度的同時(shí),本文算法還將每幅圖像對(duì)的計(jì)算時(shí)間縮短了95%以上,匹配時(shí)間均不超過(guò)2 s,實(shí)現(xiàn)了快速的立體匹配。

對(duì)于所有圖像對(duì),特征點(diǎn)對(duì)數(shù)量與處理時(shí)間如表5所示,基于特征點(diǎn)估計(jì)的視差范圍和真實(shí)范圍對(duì)比如表6所示,雖然估計(jì)的視差范圍與真實(shí)范圍還是存在一定的偏差,但正是由于本文通過(guò)特征點(diǎn)檢測(cè)的方式縮小視差的搜索范圍,提高算法的計(jì)算效率,而且特征處理時(shí)間僅占據(jù)整個(gè)算法運(yùn)行時(shí)間的20%左右,從而將算法的運(yùn)行時(shí)間縮短了95%以上,保證了快速的立體匹配。此外,本文還采用了綜合考慮圖像的亮度、邊緣和梯度信息的Census變換計(jì)算匹配代價(jià),從圖6可以看出在重復(fù)紋理、弱紋理及邊緣區(qū)域的視差結(jié)果均得到了顯著改善,在保證計(jì)算效率的同時(shí)本文又進(jìn)一步提升了視差精度,實(shí)驗(yàn)數(shù)據(jù)也驗(yàn)證了本文匹配代價(jià)的有效性,由表3可以看出相比傳統(tǒng)算法,本文方法在non、all以及disc區(qū)域的視差精度均有不同程度的提升。

圖6 不同算法生成的視差圖Fig.6 Disparity maps generated by different algorithms

表3 兩種算法的誤匹配率

表4 不同算法的運(yùn)行時(shí)間

為了進(jìn)一步客觀分析所提算法的性能,還選取了Middlebury網(wǎng)站上一些實(shí)時(shí)及接近實(shí)時(shí)的立體匹配算法進(jìn)行比較,不同算法的誤匹配率如表7所示。對(duì)于筑波和金星這樣視差范圍較小的簡(jiǎn)單圖像對(duì),所提算法的誤匹配率接近表中的最優(yōu)算法,側(cè)面反映了所提算法在簡(jiǎn)單紋理圖像中具有較好的視差估計(jì)能力。對(duì)于泰迪和錐面這樣視差范圍較大的具有復(fù)雜場(chǎng)景的圖像對(duì),本文算法的平均誤匹配率由小到大分別位于第二和第一,且在泰迪上僅比第一低0.1%,匹配精度較高,這說(shuō)明視差范圍越大、圖像的場(chǎng)景越復(fù)雜,所提算法的性能也越強(qiáng)。除此之外,所提算法在所有圖像對(duì)上的平均誤匹配率為7.65%,在上述算法中最低,說(shuō)明本文方法具有較強(qiáng)的魯棒性,受場(chǎng)景紋理的影響較小,能較好的適用于各種不同的場(chǎng)景。綜合立體匹配的速度和精度考慮,本文算法具有很高的實(shí)際應(yīng)用價(jià)值。

表5 不同圖像的特征點(diǎn)對(duì)數(shù)量與處理時(shí)間

表6 視差范圍

表7 不同算法的誤匹配率

4 結(jié) 論

本文改進(jìn)了傳統(tǒng)SGM算法,提出了一種基于特征點(diǎn)的視差范圍估計(jì)方法,提高了視差計(jì)算效率;構(gòu)建了新的代價(jià)計(jì)算函數(shù),改善了重復(fù)紋理、弱紋理及邊緣區(qū)域的匹配效果。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)SGM算法相比,本文算法的平均誤匹配率降低了6.37%,計(jì)算時(shí)間縮短了95%以上,與其他實(shí)時(shí)性及近實(shí)時(shí)算法相比,本文算法具有較強(qiáng)的魯棒性,能較好地適用于各種不同場(chǎng)景。