融合多特征表示和超像素優(yōu)化的雙目立體匹配

郭 倩，張福楊，孫農(nóng)亮

山東科技大學 電子通信與物理學院，山東 青島266590

1 引言

雙目立體匹配一直是計算機視覺領域的一個基本問題和研究熱點，其核心思想是在兩幅圖像之間建立對應關系，該技術可應用在3D 模型、機器人導航、三維場景重建、零件檢測以及基于圖像渲染等領域。20 世紀90年代以來，立體匹配研究出現(xiàn)了兩個方向，一種是偏重于實時性的局部特征法，另一種是偏重于算法準確性的全局匹配算法[1]。局部立體匹配通?？煞譃樗膫€步驟：代價計算、代價聚合、視差計算和視差精化[2]。全局立體匹配通過隨機生成視差粗略圖，最小化全局能量方程，得到最優(yōu)視差圖。采用的匹配技術主要有置信度傳播算法[3]、圖割算法[4]、動態(tài)規(guī)劃算法[5]、二次規(guī)劃算法[6]等。

全局立體匹配方法在應用中匹配精度高，但實際執(zhí)行效率卻很低，無法滿足實時性的要求[7]。局部立體匹配算法以像素點為中心構(gòu)建局部窗口，通過計算窗口內(nèi)的像素相似性求取初始匹配代價，具有計算速度快、易于實現(xiàn)的優(yōu)點。常用的像素相似性度量方法主要有：像素點灰度差（SAD）、歸一化交叉變換（NCC）、Rank 變換、Census變換[8]等，并通過在一定范圍內(nèi)代價聚合得到初始視差值。但是由于支持窗口的大小難以選擇，Zhang等人[9]將自適應支持窗口用于代價聚合過程，Mei等人[10]對文獻[9]進行改進，增大自適應窗口的約束條件，提高匹配精度。Lee 和Hong[11]通過對左右圖像分別求各自的自適應支持窗口進行AND 操作，得出最終的代價聚合支持窗口，對文獻[10]進一步改進。文獻[12-13]分別提出基于最小生成樹（MST）和分割樹（ST）的代價聚合方法，在匹配精度上取得了較好的效果。Kang等人[14]利用人眼視覺由粗到細的特征，將CTF 框架用于立體匹配，在視差精度上進一步得到了改進，速度上并沒有很大的提升。馬龍等人[15]利用強相似點檢測對雙目圖像進行立體匹配，提高了匹配速度，但是在缺乏紋理區(qū)域匹配精度不高。文獻[16]將超像素分割應用于立體匹配，并通過對超像素建立馬爾科夫場進行匹配代價聚集，視差效果得到了較好的改進，但是在缺乏紋理區(qū)域卻不能很好的匹配。

本文基于多特征信息進行代價計算，利用超像素分割將具有相似度高的像素聚合為超像素，并基于米字骨架自適應搜索方法計算聚合范圍。在視差精化步驟，采用左右一致性檢測檢測出錯誤匹配點，并對錯誤匹配點進行8個方向極線掃描優(yōu)化，利用超像素分割結(jié)果作為檢測視差結(jié)果是否正確的判斷條件，進一步修正了匹配中常見的毛刺現(xiàn)象。

2 改進算法描述

本文算法主要通過權重融合AD、Census、Edge信息代價計算；利用超像素分割SLIC算法生成超像素，并基于米字骨架對初始匹配代價進行代價聚合；利用Winner Take All 進行視差求取；最后利用本文提出的超像素優(yōu)化算法進行優(yōu)化，生成最終的視差圖。具體的算法流程圖如圖1所示。

圖1 本文算法流程圖

2.1 結(jié)合多特征表示的代價計算

局部立體匹配算法中，AD（Absolute Difference）算法不需要復雜的乘除法運算，因此運算速度快，但對噪聲和光照較敏感，算法精度隨信噪比增加和光照不均而下降[17]。Census算法對光照變化的適應性好，對由光照不均引起灰度變化有很好的修正作用[18]。在立體視覺匹配過程中，邊緣信息的處理比較復雜。由于邊緣位置視差具有很大的不連續(xù)性，在一幅圖像中體現(xiàn)場景特征最明顯的位置往往在圖像的邊緣位置上[19]，這同時也為研究提供了一個非常有意義的線索。因此，在AD、Census算法的基礎上，加入Edge圖像的邊緣信息，能夠增強立體匹配對邊緣的辨識度，減少在邊緣匹配錯誤的像素數(shù)量。

AD（絕對差）算法通過計算在同一位置左右目圖像的信息差異來得到匹配代價，像素(x,y)在視差為d 時的計算公式如下：

Census變換是一種局部非參數(shù)變換[20]，通過比較兩個像素的Census 編碼得到漢明距離作為匹配代價。Census 編碼以窗口中心像素(u,v)為基準，如果窗口中的一個像素(m,n)的灰度值比中心像素大，則將該位置的編碼置為0，否則置為1。Census 變換示意圖如圖2所示。

圖2 Census初始代價計算

經(jīng)過以上Census 變換得到的初始計算代價如下所示：

式中，Cl(x,y)，Cr(x-d,y)分別為匹配圖與參考圖中以(x,y)，(x-d,y)為中心的匹配窗經(jīng)過Census 變換之后的比特串，d 為視差值。

Canny 算子利用一階差分偏導計算圖像的邊緣特征，將圖像邊緣像素值置為255，非邊緣像素值為0，得到邊緣初始代價CEdge。由于邊緣特征具有特殊的作用，往往代表著深度不連續(xù)區(qū)域。因此在代價融合時，先將CCensus、CAD代價融合，然后將邊緣位置的代價替換為CEdge，增強了立體匹配在邊緣區(qū)域的辨識度。計算公式如下：

其中，λCensus、λAD、λEdge分別是CCensus、CAD、CEdge的變換影響參數(shù)，P(a,b)則采用以下方程計算：

P(a,b)的作用是將匹配代價歸一化，使代價值投影到[0，1]范圍，從而使不同代價計算方法得到的初始代價對最終代價的貢獻相同。由于P(CCensus,λCensus) 、P(CAD,λAD)取值范圍均為[0，1]，所以融合兩個初始代價時將兩種方法的初始代價相加并取平均，保證初始代價范圍仍然在[0，1]。

本文采用AD-Census 立體匹配[10]中的λCensus、λAD變換影響參數(shù)，λCensus取30.0，λAD取10.0。由于CEdge的值只有0 和255，所以以10 為間隔，選取0.01～100 作為λEdge的候選值，以標準立體匹配庫中的4幅圖像作為實驗對象，實驗結(jié)果如圖3所示。

圖3 不同λEdge 值對應的錯誤率

圖3 中的縱坐標表示匹配精確度，橫坐標表示λEdge值，從圖中可以看出，當λEdge值小于等于1時，立體匹配結(jié)果對應的錯誤率幾乎沒有變化，當λEdge值大于1 時，錯誤率明顯上升，尤其是Teddy 圖像，變化最為明顯。因此，在本文的實驗中，λEdge取值為1。

因此最終的初始匹配代價分為兩部分，當匹配區(qū)域處于邊緣時，匹配代價為CEdge，當匹配區(qū)域處于非邊緣時，匹配代價為CCensus、CAD的融合代價。

2.2 基于超像素自適應搜索區(qū)域的代價聚合

超像素分割方法是將具有相似紋理、顏色、亮度等特征的相鄰像素聚集成不規(guī)則像素塊，用來區(qū)分不同特征物體的技術，常用于目標識別、目標檢測[21]、深度信息恢復[22]等計算機視覺領域。對于立體匹配得到的深度信息，利用顏色相似區(qū)域有相同的視差的原理[16]，可以認為超像素體中的像素擁有相同的視差。簡單線性迭代聚類方法（Simple Linear Iterative Clustering，SLIC）相對于其他超像素分割算法具有計算復雜度低的優(yōu)勢[21]，因此在本文中，利用SLIC對圖像進行超像素分割處理。不同超像素分割范圍的圖像如圖4所示。

圖4 選取不同超像素數(shù)量Teddy的分割結(jié)果

通過圖4 可以發(fā)現(xiàn)，分割個數(shù)越多，對圖像分割越精確，在圖像邊緣位置分割越好，但是分割時間相對較長。在超像素個數(shù)少的分割圖像中，雖然分割時間較短，但由于圖像邊緣較多，因此會將多個深度不連續(xù)的邊緣包含在一個超像素體中。在超像素分割過程中，將每一個超像素體的中心點進行標記，并將此中心點的顏色定義為超像素體內(nèi)所有像素顏色的均值。

在進行代價聚合步驟時，本文汲取文獻[10]中提出的基于單個像素的自適應聚合范圍方法，并以此為基礎，提出基于超像素的自適應聚合范圍方法。該方法以每個超像素為中心，分別以超像素為單位進行條件約束下的自適應搜索。由于米字骨架需要搜索8個方向，因此搜索到的代價聚合范圍更加全面。聚合范圍搜索過程中用到的條件約束分別由顏色約束和距離約束組成，具體公式如下：

式中，sp 為當前超像素的中心位置，sp1為以sp 為出發(fā)點向右搜索的不同的超像素中心點（以向右搜索為例）。dn_sup為搜索的步長；τ1、τ2為設置的顏色約束閾值；L1、L2為空間距離約束閾值；Dc(sp1,sp)為超像素sp1、sp 的顏色差，Ds(sp1,sp)為超像素sp1、sp 的空間距離差。

約束條件（6）對超像素sp 和搜索到的超像素sp1，以及sp1和搜索到sp1之前的一個超像素sp1+(dn_sup,0)進行顏色約束，該約束條件的作用是防止搜索范圍超出邊界。約束條件（7）為對超像素sp1和sp 進行距離約束，用一個較大的值L1在無紋理和缺乏紋理區(qū)域聚集到更多的代價值。當在滿足條件（6）和（7）的情況下搜索范圍仍然很大時，為了節(jié)省搜索時間和保留搜索點的局部特征，定義公式（8），即當搜索距離超過L2(L2＜L1)時，對超過L2的超像素實行更嚴格的顏色約束，使sp1與sp 的顏色差小于τ2(τ2＜τ1)。具體搜索示意圖如圖5所示。

圖5 超像素基于米字骨架自適應搜索示意圖

在圖5 中，第一行兩幅圖為中心搜索超像素圖，第二行兩幅圖為在約束條件（6）和（7）下的基于米字骨架的搜索區(qū)域圖，第三行兩幅圖為加上約束條件（8）的搜索區(qū)域圖。從A 組圖中可以看出，在加上約束條件（8）后，搜索區(qū)域明顯減小，避免了在缺乏紋理和無紋理區(qū)域過多地聚合代價信息。在保留了該超像素的局部特征信息的同時，減小了在視差匹配時的誤差。而在B組圖中加上約束條件（8）后搜索區(qū)域沒有發(fā)生變化，說明該約束條件在缺乏特征區(qū)域效果明顯，而在特征較為明顯區(qū)域約束性不強。

由于超像素單元中包含的像素個數(shù)較多，若在聚合時將搜索到的超像素代價值進行簡單地累加，則失去了每個中心超像素的特征性。因此對于自適應搜索到的超像素，將其代價乘以權值exp(-i)（i 表示按照極線方向搜索到的第i 個超像素），以保留超像素的特征，在一定程度上提高匹配的精確度。代價聚合公式如下所示：

2.3 超像素視差優(yōu)化

視差計算采用WTA（Winner Take All）策略求出粗略視差值，并利用左右一致性檢查得出錯誤匹配視差。在視差優(yōu)化步驟，本文分為兩步：

（1）極線修正。先對初始視差圖進行左右一致性檢測。對于經(jīng)過左右一致性檢測得出的異常值（非遮擋點），通過搜索該異常值周圍16 個方向的有效像素點，找出最具有相似特征的像素點，并將找到的正確匹配的像素點的視差值賦值給該異常點。若該異常值是遮擋點，則將其填充為周圍16 個像素中視差值最低的視差值，對其進行視差修正。

式中，rx,ry,(rx,ry∈[-2,2])分別表示相對于中心點(x,y)的周圍16 個方向的像素搜索，Dis(x+rx,y+ry)為該像素點周圍搜索到的16個有效的視差值；Dis(x,y)代表搜索到的16個方向中顏色差異最小的像素點的視差值。

（2）超像素修正。計算每個超像素中由第一步修正后得到的視差，并將超像素中的每個像素的視差值映射到對應的直方圖上。其具體步驟如下：

圖6 超像素映射直方圖

①計算視差圖像每個超像素內(nèi)的像素視差值，并將其投影到直方圖中，其對應的直方圖形式如圖6 所示。本文將Tsukuba等4幅經(jīng)過極線修正的視差圖像進行統(tǒng)計，計算視差圖每個超像素中對應的不同視差值，并統(tǒng)計不同視差值的像素個數(shù)，將其以折線圖（如圖7）的形式呈現(xiàn)出來。從折線圖中可以看出，超像素中不同視差值分別為1、2、3、4個。其中不同視差值個數(shù)為1的最多，說明大部分像素正確匹配；不同視差值個數(shù)為2的大約占27%；個數(shù)為3 的大約占14%；個數(shù)為4 的最少，比例不到5%。因此，個數(shù)為1 的超像素為正確匹配，如圖6（a）所示，不進行后續(xù)的優(yōu)化；視差值個數(shù)為2、3、4的超像素分別進行以下2、3、4步優(yōu)化。

圖7 超像素內(nèi)不同的視差值個數(shù)

②若超像素中的不同視差值為2，如圖6（b）所示，則搜索該超像素內(nèi)匹配正確的視差值，若全部為正確匹配，則不對其進行優(yōu)化；若超像素內(nèi)正確匹配的視差值為dc，則將該超像素內(nèi)的視差值更改為dc；若超像素內(nèi)沒有正確匹配的視差值，則對該超像素周圍像素進行搜索，找到顏色差最小的正確匹配的像素視差值ds，并將該超像素內(nèi)的像素視差值更改為ds。

③若超像素中的不同視差值為3，如圖6（c）所示，先搜索超像素內(nèi)正確匹配的視差值，若全部正確匹配，則不對該超像素視差值進行處理；若有正確匹配的像素視差值，則對超像素內(nèi)沒有正確匹配的像素視差值進行更新，更新準則為：若未匹配像素視差值與匹配像素視差值顏色差小于λcolor，則對像素視差值進行更新，否則標記該像素為誤匹配，進行下一次更新.

④若超像素中的不同視差值為4，先搜索超像素內(nèi)正確匹配的視差值，若全部正確匹配，則不對該超像素視差值進行處理，否則進行與第③步相同的步驟進行視差更新。

2.4 算法偽代碼

基于上文對本文算法各步驟的詳細描述，給出以下算法偽代碼。其中Ileft、Iright分別表示輸入左右目圖像，N 表示超像素個數(shù)，min Dis、max Dis 分別表示最小最大視差，d 表示視差取值，DleftDright表示視差圖。

輸入：左右圖像、超像素個數(shù)、最小最大視差。

1. Ileft和Iright進行SLIC超像素分割

2. for d in min Dis to max Dis，do

3. Ileft和Iright計算AD、Census、Edge代價

4. # parallel compute {

5. for 每個超像素in Ileft和Iright，do

6. 基于米字骨架計算聚合范圍

7. 基于聚合范圍代價聚合

end}

end

8. WTA求出DleftDright

9. for DleftDright，do

10. LRC左右一致性檢測

11. if 錯誤點為非遮擋點

填充具有相似特征的像素對應的視差

12. else

填充周圍16個像素中視差值最低的視差值

13. LRC左右一致性檢測

14. for每個超像素in DleftDright，do

15. 利用直方圖統(tǒng)計不同視差值個數(shù)

16. 根據(jù)不同視差值個數(shù)的情況進行不同步驟的優(yōu)化操作

end

end

輸出：最終的視差圖DleftDright。

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

本文算法在Windows平臺下采用C++語言在Visual Studio 2015 環(huán)境下進行開發(fā)實現(xiàn)，硬件條件為Intel Core i7-4790 CPU，頻率為3.6 GHz，實驗平臺為Visual Studio2015 和OpenCV3.2.0。檢驗算法性能的圖像來源于Middlebury 網(wǎng)站提供的數(shù)據(jù)集[23]，先選取4 組圖像對初始視差進行求取。本文算法采用超像素個數(shù)為3 200，其他的參數(shù)設置如下：

3.1 初始視差結(jié)果求取與分析

如圖8 為對Tsukuba、Venus、Teddy、Cones 這4 幅圖求取的初始視差結(jié)果，Census算法在低紋理區(qū)域出現(xiàn)了大面積匹配錯誤的現(xiàn)象，如Tsukuba的燈罩區(qū)域；AD算法在邊緣部分較Census算法表現(xiàn)較好，例如Teddy的桌子邊緣區(qū)域，但在紋理豐富區(qū)域，例如Cones 的木板區(qū)域，以及Teddy 的背景區(qū)域，卻沒能達到正確匹配的效果。而本文的方法結(jié)合兩種方法的優(yōu)點，無論是在低紋理區(qū)域還是在邊緣區(qū)域，都能夠得到較精準的視差。

3.2 視差結(jié)果與分析

如圖9為各算法分別對Tsukuba、Venus、Teddy、Cones這4 幅圖求取的視差結(jié)果。其中圖9（a）、（b）分別是基準圖像及標準視差圖；圖9（c）、（d）、（e）、（f）分別是ADCensus算法[25]、FA算法[26]、ASW算法[27]、GMM-MST[28]算法得出的立體匹配結(jié)果；圖9（g）為利用本文算法得出的立體匹配結(jié)果。

圖8 經(jīng)過代價計算的初始視差圖

表1根據(jù)Middlebury Stereo Evaluation對求出的視差結(jié)果進行測試，給出了立體圖像對求得的視差圖在非遮擋區(qū)域（noncc）、視差不連續(xù)區(qū)域（disc）、所有區(qū)域（all）在錯誤閾值為1.0 時的匹配錯誤率，可以看出本文除了Tsukuba 匹配效果不是很好，在另外3 張圖中相對于另外4 種方法都減少了立體匹配的錯誤率。其中ASW 以及GMM-MST 算法在Tsukuba 匹配上分別優(yōu)于本文算法0.55、0.61 個百分點，本文算法比AD-Census、FA 算法分別降低了0.75、0.31 個百分點。在Venus 上，本文算法相對于4 種算法中表現(xiàn)最好的GMM-MST 算法，錯誤率降低了0.05 個百分點。在Cones 上，本文算法較AD-Census算法錯誤率降低了1.41個百分點，相對于ASW 算法降低了3.41 個百分點。本文算法在Teddy上表現(xiàn)最好，匹配精度明顯增加，相對于AD-Census、FA算法分別降低了6.2、4.6個百分點。

3.3 算法性能分析

在初始代價計算步驟，本文通過計算AD、Census、Edge得到初始代價，令N 為圖像像素個數(shù)，L 為視差取值范圍，則匹配代價計算步驟的時間復雜度為O(NL)。通過SLIC 算法對圖像進行超像素分割，時間復雜度只與像素的數(shù)量線性相關，為O(NL)。在代價聚合步驟，本文算法可在保證視差結(jié)果不變的情況下，利用OpenMP對聚合范圍求取步驟和初始代價聚合步驟并行加速，加快程序運行速度。若超像素個數(shù)為M ，則聚合步驟在不利用并行加速的條件下時間復雜度為O(ML)。通過超像素對視差進行優(yōu)化，若只計算最差情況下即所有超像素都需要進行修正的情況下，時間復雜度為O(ML)。因此本文算法運行速度跟圖像的大小和分割的超像素的個數(shù)成正比，圖像過大或分割的超像素個數(shù)過多，會使運行速度變慢。

圖9 不同算法得到的視差圖

表1 閾值為1.0時不同算法的錯誤匹配率%

本文對大小為450×375的圖像進行處理，在加上并行運算的條件下，運行時間為230 ms。表2為本文算法與GMM-MST 算法、FA 算法、文獻[15]的運行時間對比。GMM-MST 算法由于在求解GMM 模型時需要將圖像分割為多個區(qū)域并需要多次迭代求解，因此所需時間相對于其他三種算法較長。本文算法在平均運行時間上較FA算法和文獻[15]算法要短，并且與文獻[15]基于強相似點算法相比較，本文算法在匹配結(jié)果精度上更高。

表2 運行時間對比ms

為了驗證本文算法在不同圖像上的適應性，對Middlebury標準測試平臺[23]提供的標準圖Aloe、Baby、Bowling進行了測試，視差搜索范圍分別為[0，60]，[0，52]，[0，67]。圖10（a）為標準測試圖，圖（b）為標準視差圖，圖（c）為本文算法得到的視差結(jié)果。通過與標準視差圖作對比，本文算法在重復紋理區(qū)域以及缺乏紋理區(qū)域得到了很好的匹配效果。利用本文算法得到的aloe立體匹配結(jié)果圖，在前景顏色與背景顏色極為相似的地方，由于在圖像分割過程中出現(xiàn)誤分割，匹配效果不是很好，是下一步需要改進的地方。

圖10 本文算法測試結(jié)果

4 結(jié)論

本文提出一種融合邊緣信息的多特征融合代價計算方法和結(jié)合超像素的代價聚合、視差優(yōu)化立體匹配方法。通過在代價計算步驟中加入邊緣信息代價，提高了在深度不連續(xù)區(qū)域的辨識度，進而增加了立體匹配的精確度。通過結(jié)合SLIC 超像素分割，在代價聚合步驟中利用米字骨架自適應搜索超像素，得出聚合范圍，并且分割得到的超像素可用來對誤匹配視差進行優(yōu)化，提高匹配精度。

實驗結(jié)果表明，本文算法能有效處理缺乏紋理和重復紋理區(qū)域的深度信息，并且在深度不連續(xù)區(qū)域得到了有效的匹配，但在前景顏色與背景顏色較為相近的區(qū)域，由于容易引起錯誤分割，導致在此區(qū)域匹配效果不是很好，是下一步算法需要改進的地方。由于本文算法在代價聚合步驟可以進行有效的并行運算，因此，通過GPU 并行編程技術實現(xiàn)本文算法是下一步的工作方向。