基于顏色與邊緣融合的非局部立體匹配算法

鄧 宇，諶貴輝，李忠兵，張軍豪，亢宇欣，夏旭洪

西南石油大學(xué) 電氣信息學(xué)院，成都 610500

1 引言

立體匹配技術(shù)作為雙目視覺(jué)系統(tǒng)中最關(guān)鍵的一個(gè)環(huán)節(jié)，主要解決如何將同一空間中的場(chǎng)景點(diǎn)在不同視角的投影圖像中的像素點(diǎn)一一對(duì)應(yīng)起來(lái)的問(wèn)題，其廣泛應(yīng)用于機(jī)器人導(dǎo)航[1]、目標(biāo)識(shí)別定位[2]、三維重建[3]、虛擬現(xiàn)實(shí)等領(lǐng)域。Scharstein 等[4]將稠密立體匹配算法分為四個(gè)步驟：（1）匹配代價(jià)計(jì)算；（2）代價(jià)聚合；（3）視差計(jì)算；（4）視差優(yōu)化。根據(jù)執(zhí)行步驟的不同分為了全局算法和局部算法，它們都部分或全部地包含以上步驟。全局算法[5-7]首先建立一個(gè)能量代價(jià)函數(shù)，然后通過(guò)最小化能量函數(shù)去求解視差。全局算法雖能獲得十分精確的視差，但計(jì)算量大。局部算法[8-9]則是在給定視差下通過(guò)一定的相似性度量準(zhǔn)則計(jì)算匹配代價(jià)，并在一個(gè)有限的支持窗口內(nèi)進(jìn)行聚合，采用勝者為王（Winner Takes All，WTA）策略求取初始視差，最后執(zhí)行視差優(yōu)化步驟。局部方法的核心在于代價(jià)聚合，大多數(shù)代價(jià)聚合方法都視為在代價(jià)體上的濾波。Yoon 等[10]將雙邊濾波引入到代價(jià)聚合中，創(chuàng)新性地提出了自適應(yīng)權(quán)重法。Rhemann等[11]利用引導(dǎo)濾波[12]進(jìn)行代價(jià)聚合。由于引導(dǎo)濾波的計(jì)算復(fù)雜度與濾波核大小無(wú)關(guān)，因此在實(shí)時(shí)系統(tǒng)中應(yīng)用廣泛。上述代價(jià)聚合方法都是在有限的支持窗口中進(jìn)行聚合，這會(huì)導(dǎo)致圖像中的像素不能正確地貢獻(xiàn)給其他所有像素而陷入局部最優(yōu)解。

Yang[13]首次提出了基于最小生成樹(shù)（Minimum Spanning Tree，MST）的非局部代價(jià)聚合算法，將聚合窗口擴(kuò)展到整個(gè)圖像，通過(guò)計(jì)算圖像的MST，可以快速完成代價(jià)聚合。學(xué)者們?cè)诖嘶A(chǔ)上又提出了許多改進(jìn)算法[14-18]，使得匹配效果進(jìn)一步改善。雖然文獻(xiàn)[13]中的算法在匹配精度和運(yùn)算效率上都取得了很好的效果，但還具有兩方面的缺陷：其一，采用的基于顏色-梯度的代價(jià)計(jì)算方法導(dǎo)致無(wú)紋理區(qū)域中像素的匹配代價(jià)近似為0，不能為代價(jià)聚合提供有效的貢獻(xiàn)。其二，只采用顏色信息構(gòu)造邊權(quán)函數(shù)，導(dǎo)致在顏色分布相似的圖像邊緣產(chǎn)生誤匹配。針對(duì)無(wú)紋理區(qū)域問(wèn)題，重新構(gòu)造了基于顏色-梯度的匹配代價(jià)函數(shù)，提高了無(wú)紋理區(qū)域像素對(duì)代價(jià)聚合的貢獻(xiàn)率；針對(duì)邊緣問(wèn)題，引入了顏色與邊緣融合的自適應(yīng)邊權(quán)函數(shù)，提高了算法在邊緣的匹配精度。算法的總體流程如圖1所示。

圖1 算法總體流程圖

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

匹配代價(jià)計(jì)算是通過(guò)某種相似性度量準(zhǔn)則計(jì)算左右兩幅圖像對(duì)應(yīng)點(diǎn)之間的相似性。文獻(xiàn)[13]采用顏色強(qiáng)度和梯度的截?cái)嘟^對(duì)差作為匹配代價(jià)，即對(duì)應(yīng)于圖像中每一個(gè)像素點(diǎn)p在視差d下，有：

式中，I(p)和I′(p+d)分別表示參考圖像上中心像素和視差為d時(shí)該像素在目標(biāo)圖像上對(duì)應(yīng)像素的強(qiáng)度；α用以平衡顏色項(xiàng)和梯度項(xiàng)；τcol、τgrd為截?cái)嚅撝担?x表示圖像像素在x方向上的梯度。

由于無(wú)紋理區(qū)域像素的像素值分布均勻，采用上述匹配代價(jià)函數(shù)計(jì)算時(shí)，在該區(qū)域中像素的匹配代價(jià)值近似為0，在使用3.2節(jié)中非局部算法進(jìn)行聚合時(shí)，在樹(shù)結(jié)構(gòu)上傳遞的代價(jià)值也即為0，對(duì)其他像素基本無(wú)影響，這與紋理區(qū)域中像素相比，它們對(duì)代價(jià)聚合的貢獻(xiàn)率較低，且通過(guò)WTA策略為這些像素選擇視差時(shí)，會(huì)出現(xiàn)一對(duì)多的情況。故針對(duì)在無(wú)紋理區(qū)域出現(xiàn)誤匹配的問(wèn)題，重新構(gòu)造了基于顏色-梯度的代價(jià)計(jì)算函數(shù)，如下式：

通過(guò)上述變換將零匹配代價(jià)項(xiàng)轉(zhuǎn)換為正的匹配代價(jià)項(xiàng)（ln2），即通過(guò)適度提升無(wú)紋理區(qū)域像素的匹配代價(jià)來(lái)提高該區(qū)域像素對(duì)代價(jià)聚合的貢獻(xiàn)，從而增加像素的可區(qū)分性。在數(shù)學(xué)上可以證明提出的代價(jià)計(jì)算函數(shù)是單調(diào)遞增的，用x代替原算法中代價(jià)函數(shù)Cd(p) 的值，對(duì)應(yīng)的代價(jià)函數(shù)可表示為f(x)=x，那么可表示為h(x)=ln(1+ex)，兩代價(jià)函數(shù)的對(duì)比圖如圖2 所示。當(dāng)原匹配代價(jià)為0 時(shí)，式（1）、（2）的最大絕對(duì)差為ln2；而當(dāng)原匹配代價(jià)增加時(shí)，二者絕對(duì)差則大大減小，且無(wú)限逼近于0。因此提出的方法對(duì)紋理區(qū)域的影響很小，但能有效地處理無(wú)紋理區(qū)域。

圖2 匹配代價(jià)對(duì)比圖

如圖3所示，分別為采用兩種代價(jià)計(jì)算方法得到的未經(jīng)視差優(yōu)化的視差圖。圖中紅色區(qū)域表示在未遮擋區(qū)域中的誤匹配點(diǎn)。（b）、（e）是在原方法下的視差結(jié)果，（c）、（f）是在改進(jìn)方法下的視差結(jié)果。從圖中黃色方框表示的無(wú)紋理區(qū)域中可以看出，改進(jìn)后算法的紅色區(qū)域減小，說(shuō)明改進(jìn)后代價(jià)計(jì)算方法能明顯改善在無(wú)紋理區(qū)域中的匹配結(jié)果。

圖3 不同代價(jià)計(jì)算方法下的初始視差圖

3 代價(jià)聚合

由于單個(gè)像素的匹配易受到噪聲影響，需利用鄰域像素的信息進(jìn)行代價(jià)聚合，以提高匹配的可靠性。對(duì)于傳統(tǒng)局部算法，中心像素僅能從鄰域有限的支持窗口內(nèi)獲得支持，而忽略了窗口外像素的影響。而非局部聚合算法利用樹(shù)結(jié)構(gòu)的特性，天然地建立全圖像素間的關(guān)系，聚合范圍不再受約束，并且聚合過(guò)程不需要迭代，只需要兩次遍歷樹(shù)結(jié)構(gòu)就能得到所有點(diǎn)的代價(jià)聚合值，大幅度降低了算法復(fù)雜度。

基于MST的非局部算法[13]中，將參考圖像I視為四連通無(wú)向圖，其中頂點(diǎn)集合V代表圖I中的所有像素，邊集合E是圖像I中所有四鄰域像素之間的邊，并通過(guò)一個(gè)加權(quán)函數(shù)將其映射到實(shí)數(shù)權(quán)值。若存在T為G的子圖且無(wú)閉環(huán)，并且T中的邊權(quán)值之和最小，則T為G的最小生成樹(shù)。文中采用Kruskal算法從G中貪心地選擇權(quán)值最小的邊來(lái)生成MST。

3.1 基于顏色與邊緣融合的邊權(quán)函數(shù)

在原算法中邊權(quán)函數(shù)定義為相鄰像素顏色強(qiáng)度的絕對(duì)差，即設(shè)s和r是一對(duì)相鄰像素，則權(quán)重定義如下：

由于該邊權(quán)函數(shù)只依賴于圖像的顏色信息，容易導(dǎo)致在圖像中具有顏色相似的邊緣區(qū)域造成誤匹配，因此提出了顏色與邊緣相融合的邊權(quán)函數(shù)。

（1）顏色加權(quán)函數(shù)

上述顏色權(quán)重只采用RGB三個(gè)通道中最大權(quán)重作為邊權(quán)值，而忽略了其他兩個(gè)通道的影響，因此提出了加權(quán)三通道聯(lián)合邊權(quán)作為最終的顏色權(quán)重，定義為：

通過(guò)融合三個(gè)通道的權(quán)重，增強(qiáng)了顏色加權(quán)函數(shù)的魯棒性，為后續(xù)構(gòu)造MST奠定了良好的基礎(chǔ)。

（2）邊緣加權(quán)函數(shù)

邊緣權(quán)重是通過(guò)邊緣提取后的二值圖像中計(jì)算得到的。邊緣檢測(cè)采用具有較強(qiáng)抗噪性能的自適應(yīng)閾值[19]的Canny算子。為了保證圖像邊緣信息的完整性，匹配圖像采用恒定時(shí)間的中值濾波[20]去除圖像噪聲。該濾波方法不僅能抑制噪聲，同時(shí)還能有效保護(hù)圖像的邊緣細(xì)節(jié)，且計(jì)算復(fù)雜度與濾波核大小無(wú)關(guān)。如圖4為分別采用5×5 的恒定時(shí)間中值濾波與均值濾波的效果對(duì)比圖，從圖中可以看出中值濾波在邊緣保持效果上更好，并采用結(jié)構(gòu)相似性（Structural Similarity，SSIM）進(jìn)行了客觀評(píng)價(jià)，SSIM（中值濾波）=0.85，SSIM（均值濾波）=0.82，其結(jié)果也表明中值濾波效果更好。

因?yàn)閳D像在邊緣提取后被二值化，所以在邊緣圖像中相鄰像素s、r的灰度值只包含兩種情況，即I(s),I(r)∈{0,1}。當(dāng)相鄰像素s、r為邊緣點(diǎn)或非邊緣點(diǎn)時(shí)，有或。因此相鄰像素s、r的邊緣權(quán)重定義為：

圖4 濾波效果對(duì)比

（3）融合邊權(quán)函數(shù)

利用上述顏色權(quán)重和邊緣權(quán)重進(jìn)行融合以解決在顏色相似的邊緣區(qū)域易產(chǎn)生誤匹配的問(wèn)題。根據(jù)經(jīng)驗(yàn)公式，融合后的邊權(quán)函數(shù)如下式：

式中，λ是調(diào)節(jié)顏色項(xiàng)和邊緣項(xiàng)比例的調(diào)節(jié)因子。

使用該融合后的邊權(quán)函數(shù)在邊緣區(qū)域時(shí)，采用邊緣和顏色信息共同計(jì)算邊權(quán)，而在其他區(qū)域時(shí)，則采用顏色信息計(jì)算邊權(quán)。對(duì)于不同區(qū)域的判定則與邊緣提取的準(zhǔn)確性息息相關(guān)。本文采用自適應(yīng)閾值的Canny 算子進(jìn)行邊緣檢測(cè)，由于噪聲等因素的干擾，會(huì)出現(xiàn)偽邊緣現(xiàn)象，造成有時(shí)判斷錯(cuò)誤。如圖5所示為邊緣檢測(cè)結(jié)果，在黃色方框表示的具有相似深度信息的高紋理區(qū)域出現(xiàn)了偽邊緣。在構(gòu)造樹(shù)結(jié)構(gòu)時(shí)，希望盡可能地保留具有相似深度的點(diǎn)之間的邊，最大可能地剔除跨深度的邊。因此，此處出現(xiàn)的偽邊緣會(huì)增大高紋理區(qū)域像素點(diǎn)間的邊權(quán)值，而降低該區(qū)域的代價(jià)聚合。

圖5 Canny邊緣檢測(cè)結(jié)果

對(duì)于偽邊緣現(xiàn)象，通常由于光照等外界因素導(dǎo)致噪聲點(diǎn)引入，或者圖像場(chǎng)景較為復(fù)雜，紋理信息比較豐富，都會(huì)不可避免地引入偽邊緣。但是圖像中的邊緣與場(chǎng)景的深度邊緣之間是一種包含與被包含的關(guān)系，因此與原算法只采用單一顏色信息構(gòu)造邊權(quán)重相較而言，邊緣信息的引入能夠在一定程度上改善具有顏色相似的深度邊緣區(qū)域的匹配效果。最后使用融合后的邊權(quán)函數(shù)去構(gòu)造MST，這里簡(jiǎn)稱新構(gòu)造的MST為MST-CE。

3.2 基于MST-CE的代價(jià)聚合

采用非局部代價(jià)聚合算法[13]在MST-CE上進(jìn)行代價(jià)聚合。設(shè)兩像素p、q之間的距離D(p,q)是MST-CE上沿最短路徑的邊權(quán)值之和。設(shè)Cd(p)表示像素p在視差d下的匹配代價(jià)，則非局部聚合代價(jià)表示為匹配代價(jià)的加權(quán)和：

其中，S(p,q)表示兩像素間的相似性，參數(shù)σ是用于調(diào)整兩像素之間相似性的常數(shù)。

對(duì)圖像中所有像素進(jìn)行代價(jià)聚合只需要通過(guò)兩次遍歷樹(shù)結(jié)構(gòu)就能有效地計(jì)算出來(lái)，聚合過(guò)程如圖6 所示。第一次遍歷（圖6（a）），從樹(shù)的葉節(jié)點(diǎn)到根節(jié)點(diǎn)。對(duì)于像素p，其代價(jià)值在訪問(wèn)完所有子節(jié)點(diǎn)才會(huì)被更新，即：

圖6 在MST-CE上的代價(jià)聚合

在MST-CE樹(shù)結(jié)構(gòu)上進(jìn)行代價(jià)聚合，得到聚合代價(jià)值后通過(guò)WTA策略求取視差。圖7為所提算法與基于MST算法的視差圖及局部放大對(duì)比。以真實(shí)視差圖為參照，所提算法相較于基于MST 的算法能夠更加有效地保護(hù)圖像邊緣，在深度不連續(xù)區(qū)域的匹配效果有較明顯的改善。

4 視差優(yōu)化

視差優(yōu)化采用文獻(xiàn)[13]中提出的非局部視差優(yōu)化算法。首先以左右圖像為參考圖像，依次運(yùn)行非局部代價(jià)聚合算法得到相應(yīng)的左右視差圖；然后采用左右一致性檢測(cè)，將所有像素劃分為穩(wěn)定像素和不穩(wěn)定像素；最后利用劃分的像素重新構(gòu)造匹配代價(jià)體，構(gòu)造如下：

式中，D(p)表示初始左視差圖。因此對(duì)于不穩(wěn)定像素在視差d上的代價(jià)被重置為0。再利用3.2節(jié)的非局部代價(jià)聚合算法將新的代價(jià)值在樹(shù)結(jié)構(gòu)上進(jìn)行聚合，將視差值從穩(wěn)定像素傳播到不穩(wěn)定像素。

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

為驗(yàn)證算法的有效性，在Middlebury[21]的19個(gè)數(shù)據(jù)集上對(duì)算法進(jìn)行了評(píng)估，包括4個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集和15個(gè)擴(kuò)展的數(shù)據(jù)集，其中誤差閾值均設(shè)為1.0。實(shí)驗(yàn)硬件平臺(tái)為配置2.8 GHz 主頻的CPU、8 GB 內(nèi)存的臺(tái)式電腦；軟件平臺(tái)為Visual Studio2015，編程語(yǔ)言為C++。

圖7 算法視差圖比較

本文算法的具體參數(shù)通過(guò)大量實(shí)驗(yàn)確定，具體如表1所示。其中標(biāo)準(zhǔn)數(shù)據(jù)集中參數(shù)λ設(shè)為0.6，參數(shù)σ設(shè)為0.1；擴(kuò)展數(shù)據(jù)集中參數(shù)λ設(shè)為0.2，參數(shù)σ設(shè)為0.04；對(duì)比算法保持與原文獻(xiàn)一致的參數(shù)。

表1 算法具體參數(shù)

5.1 代價(jià)計(jì)算性能測(cè)試

為驗(yàn)證改進(jìn)的代價(jià)計(jì)算方法的性能，在MST非局部算法框架下，將改進(jìn)的代價(jià)計(jì)算方法（Proposed）與原代價(jià)計(jì)算方法（Original）、基于截?cái)嗷叶炔罱^對(duì)值（Truncated Absolute Differences，TAD）、基于梯度（Grad）、基于Census的代價(jià)計(jì)算方法進(jìn)行對(duì)比。在Middlebury的19個(gè)數(shù)據(jù)集上進(jìn)行了測(cè)試，算法性能如表2 所示。從表中可知，改進(jìn)的代價(jià)計(jì)算方法與其他四種典型的代價(jià)計(jì)算方法相較而言，誤匹配率最低，且在運(yùn)行時(shí)間上相差無(wú)幾。

5.2 算法對(duì)比分析

為了驗(yàn)證算法的總體性能，將改進(jìn)后的算法與原算法[13]（MST）、基于引導(dǎo)濾波的算法（GF）[11]和基于分割樹(shù)的算法[14]（ST-1）進(jìn)行對(duì)比。算法的初始視差都是采用代價(jià)計(jì)算、代價(jià)聚合和WTA策略計(jì)算得到，不采用視差優(yōu)化技術(shù)。對(duì)于標(biāo)準(zhǔn)數(shù)據(jù)集，在三種不同區(qū)域進(jìn)行測(cè)試，即非遮擋區(qū)域（nonocc）、全部區(qū)域（all）、不連續(xù)區(qū)域（disc），其結(jié)果如表3 所示。對(duì)于深度不連續(xù)區(qū)域多分布在邊緣區(qū)域，因此“disc”一欄中的數(shù)據(jù)能夠表明算法在邊緣區(qū)域的匹配效果。從表3 可知，在“disc”一欄中改進(jìn)算法的誤匹配率均小于MST，與ST-1和GF相比也具有很大的優(yōu)勢(shì)。因此，在“disc”中的良好性能說(shuō)明了本文提出的融合邊權(quán)函數(shù)的必要性。

表2 代價(jià)計(jì)算方法性能測(cè)試結(jié)果

表3 不同算法在標(biāo)準(zhǔn)數(shù)據(jù)集上不同區(qū)域的匹配誤差（未經(jīng)視差后處理） %

為進(jìn)一步驗(yàn)證算法性能，在15 個(gè)擴(kuò)展數(shù)據(jù)集上進(jìn)行了測(cè)試，其結(jié)果如表4所示。在這19個(gè)數(shù)據(jù)集上改進(jìn)算法在10 個(gè)數(shù)據(jù)集上取得了最低誤差，且平均誤匹配率最小。為了在視覺(jué)上進(jìn)行更加直觀的比較，圖8給出了其中3幅圖像未經(jīng)視差優(yōu)化的視差圖（從上到下依次為原圖、真實(shí)視差圖、GF視差圖、ST-1視差圖、MST視差圖、本文視差圖），用紅色表示在未遮擋區(qū)域中的誤匹配像素。從圖中可以看出，改進(jìn)后算法的紅色區(qū)域明顯減小，在圖中黃色方框表示的邊緣區(qū)域上改進(jìn)后算法的匹配效果相比其他三種算法也更加理想。但是由于算法在代價(jià)計(jì)算中采用的顏色與梯度兩種測(cè)度對(duì)噪聲都比較敏感，且在邊緣檢測(cè)中出現(xiàn)了偽邊緣，致使邊權(quán)重的構(gòu)建不是十分準(zhǔn)確，從而導(dǎo)致了算法在某些紋理較為豐富的圖像上的改善效果并不是十分明顯。

表4 不同算法在非遮擋區(qū)域中的匹配誤差 %

圖8 未經(jīng)視差優(yōu)化的視差圖

最后采用文獻(xiàn)[13]中的視差優(yōu)化算法對(duì)初始視差進(jìn)行優(yōu)化。如圖9 為MST 算法和MST-CE 算法在標(biāo)準(zhǔn)數(shù)據(jù)集上視差優(yōu)化后的視差結(jié)果，在這4 個(gè)數(shù)據(jù)集上，平均誤匹配率從5.48%下降到了5.34%。

圖9 標(biāo)準(zhǔn)數(shù)據(jù)集視差優(yōu)化后結(jié)果

6 結(jié)束語(yǔ)

本文對(duì)基于MST 非局部算法進(jìn)行了兩方面的改進(jìn)。針對(duì)原算法在無(wú)紋理區(qū)域像素的匹配代價(jià)對(duì)代價(jià)聚合貢獻(xiàn)率低的問(wèn)題，重新構(gòu)造了基于顏色-梯度的匹配代價(jià)函數(shù)，有效改善了在無(wú)紋理區(qū)域的匹配效果。針對(duì)邊權(quán)函數(shù)的構(gòu)造只采用單一的顏色信息，導(dǎo)致了在顏色相似的圖像邊緣出現(xiàn)錯(cuò)誤匹配，提出了顏色與邊緣融合的自適應(yīng)邊權(quán)函數(shù)。在Middlebury 19個(gè)數(shù)據(jù)集上的評(píng)估表明，算法有效地提高了在無(wú)紋理以及邊緣區(qū)域的匹配精度。但是由于算法在代價(jià)計(jì)算中選擇的測(cè)度對(duì)噪聲較為敏感，以及邊緣檢測(cè)中出現(xiàn)了偽邊緣，導(dǎo)致算法對(duì)一些紋理較豐富的圖像的改善效果并不是十分明顯。今后將針對(duì)代價(jià)計(jì)算進(jìn)行進(jìn)一步的研究，測(cè)試更多測(cè)度并進(jìn)行融合；針對(duì)邊緣檢測(cè)將進(jìn)行進(jìn)一步約束，提高檢測(cè)的準(zhǔn)確性，從而提高算法的匹配精度。