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

西南石油大學 電氣信息學院，成都 610500

1 引言

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

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

圖1 算法總體流程圖

2 匹配代價計算

匹配代價計算是通過某種相似性度量準則計算左右兩幅圖像對應點之間的相似性。文獻[13]采用顏色強度和梯度的截斷絕對差作為匹配代價，即對應于圖像中每一個像素點p在視差d下，有：

式中，I(p)和I′(p+d)分別表示參考圖像上中心像素和視差為d時該像素在目標圖像上對應像素的強度；α用以平衡顏色項和梯度項；τcol、τgrd為截斷閾值；?x表示圖像像素在x方向上的梯度。

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

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

圖2 匹配代價對比圖

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

圖3 不同代價計算方法下的初始視差圖

3 代價聚合

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

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

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

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

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

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

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

通過融合三個通道的權重，增強了顏色加權函數(shù)的魯棒性，為后續(xù)構造MST奠定了良好的基礎。

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

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

因為圖像在邊緣提取后被二值化，所以在邊緣圖像中相鄰像素s、r的灰度值只包含兩種情況，即I(s),I(r)∈{0,1}。當相鄰像素s、r為邊緣點或非邊緣點時，有或。因此相鄰像素s、r的邊緣權重定義為：

圖4 濾波效果對比

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

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

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

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

圖5 Canny邊緣檢測結果

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

3.2 基于MST-CE的代價聚合

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

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

對圖像中所有像素進行代價聚合只需要通過兩次遍歷樹結構就能有效地計算出來，聚合過程如圖6 所示。第一次遍歷（圖6（a）），從樹的葉節(jié)點到根節(jié)點。對于像素p，其代價值在訪問完所有子節(jié)點才會被更新，即：

圖6 在MST-CE上的代價聚合

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

4 視差優(yōu)化

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

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

5 實驗結果與分析

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

圖7 算法視差圖比較

本文算法的具體參數(shù)通過大量實驗確定，具體如表1所示。其中標準數(shù)據(jù)集中參數(shù)λ設為0.6，參數(shù)σ設為0.1；擴展數(shù)據(jù)集中參數(shù)λ設為0.2，參數(shù)σ設為0.04；對比算法保持與原文獻一致的參數(shù)。

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

5.1 代價計算性能測試

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

5.2 算法對比分析

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

表2 代價計算方法性能測試結果

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

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

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

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

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

圖9 標準數(shù)據(jù)集視差優(yōu)化后結果

6 結束語

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