基于改進Census變換和多尺度空間的立體匹配算法*

劉建國 俞力 柳思健 王帥帥

(武漢理工大學(xué) 現(xiàn)代汽車零部件技術(shù)湖北省重點實驗室∥汽車零部件技術(shù)湖北省協(xié)同創(chuàng)新中心， 湖北 武漢 430070)

立體匹配是計算機視覺研究最為活躍的領(lǐng)域之一，作為雙目立體視覺的核心組成部分，其主要任務(wù)是找到真實環(huán)境中物體上的某一點在左右視圖上的對應(yīng)點.而真實世界中因為外界環(huán)境(如光照不均勻、遮擋、弱紋理、傾斜區(qū)域等)問題使得物體成像發(fā)生相應(yīng)的變化，從而給雙目匹配帶來挑戰(zhàn).Scharstein等[1]對立體匹配算法進行了總結(jié)分類，把匹配的過程分為4個步驟：匹配代價計算、匹配代價聚合、初始視差計算和視差優(yōu)化，并根據(jù)計算視差值方式的不同把立體匹配算法分為全局匹配算法[2- 3]和局部匹配算法[4- 7].全局匹配算法通過構(gòu)建全局約束，大多能夠獲取高質(zhì)量的視差圖，主要有動態(tài)規(guī)劃、置信傳播[2]、圖割法[3]，但是算法的時間復(fù)雜度高、計算效率低，是其明顯的弊端.局部匹配算法在尋找匹配點時僅考慮匹配點鄰域內(nèi)像素對匹配對的影響，通常運行速度快、執(zhí)行效率高，但是它對一些由于遮擋和弱紋理等造成的模糊比較敏感，易造成誤匹配，如何選擇合適的支持窗口和像素匹配代價的計算方法是個難點.

傳統(tǒng)的局部立體匹配代價計算方法主要有基于絕對差(AD)、平方差(SD)[1]、自適應(yīng)權(quán)重(AW)[4]以及自適應(yīng)匹配窗口的算法等幾種.近年來，相關(guān)研究學(xué)者提出許多新的匹配代價算法.Yoon等[4]提出一種變權(quán)重系數(shù)的成本聚類的方法，該權(quán)重系數(shù)根據(jù)像素間的顏色相似度和距離來計算得到，顏色越相近，空間距離越近，權(quán)重系數(shù)越大.Zhang等[5]提出基于交叉區(qū)域匹配窗口的匹配算法，利用顏色相似性和距離限制得到由多條相鄰的水平分割線或者豎直分割線組成的匹配窗口，該窗口是自適應(yīng)的，所以能很好地解決匹配中弱紋理的問題.Shen[6]提出基于梯度測量和非參數(shù)變換的方法：Rank和Census變換，該方法提高了匹配精度和魯棒性，但傳統(tǒng)Census變換依賴于中心像素灰度值的大小，對噪聲比較敏感，支持區(qū)域的選擇合理性也會影響匹配精度.Stentoumis等[7]對視差空間進行3D濾波，采用順序約束和唯一性約束來選擇3D濾波區(qū)域內(nèi)的像素點，以局部高斯函數(shù)為核函數(shù)，給選取的像素點分配適當(dāng)?shù)臋?quán)重系數(shù)，此方法考慮到了視差空間內(nèi)的3D信息，匹配正確率有所提高.

在代價聚合階段，傳統(tǒng)聚合算法的共同點是在輸入圖像為細尺度上進行聚合的，然而人類是在多尺度[8- 9]下產(chǎn)生的立體視覺效果，受到這種生物啟發(fā),在傳統(tǒng)的算法上采用多尺度聚合比細尺度聚合更為合理.

在視差計算階段，選擇使用局部算法中聚合代價最小的候選點作為最終匹配點，因為局部匹配算法更多地依靠匹配代價計算和代價聚合來保證視差圖的質(zhì)量，通常用“贏家通吃”(WTA)[10- 11]的算法，該方法雖然簡單、快速有效，但容易受噪聲等因素的影響而產(chǎn)生視差突變，使獲得的視差圖存在較多的誤匹配點和異常值.

文中提出一種改進的局部立體匹配算法對Census變換進行改進，采用一種增加變換窗口信息均值判斷和自適應(yīng)權(quán)重的計算方法，提高算法魯棒性；在代價聚合階段，將引導(dǎo)圖[12]聚合算法融入高斯金字塔構(gòu)中，并結(jié)合正則變換方法來加強層間一致性匹配代價運算，提高視差圖精度；最后，在視差處理中，采用多層次的視差優(yōu)化步驟，包括誤匹配點檢測、區(qū)域投票策略和亞像素增強[9,13].

1 算法描述

根據(jù)Scharstein等[1]對立體匹配算法的分類和評價，立體匹配算法通常包括以下步驟：代價計算、代價聚合、視差計算和視差優(yōu)化.文中算法也遵循該流程.

1.1 匹配代價計算

傳統(tǒng)的Census變換[14]是以像素p為中心選取一個矩形變換窗口W(p)，選取該中心像素的灰度值作為參考值，將矩形變換窗口內(nèi)各點像素q的灰度值分別與中心像素p的灰度值進行比較，并用0和1來表示其大小關(guān)系.Census變換的實質(zhì)就是將像素p與以其為中心的窗口映射成一個比特流，用該比特流作為中心像素點的Census變換碼.映射關(guān)系為

(1)

式中，I(p)、I(q)分別為像素點p、q的灰度值.由映射關(guān)系得到對應(yīng)的比特流，定義如下：

(2)

式中，符號?表示按位連接，Np表示p的領(lǐng)域.

如圖1所示，變換窗口大小為3×3，中心像素的灰度值為68，領(lǐng)域各像素的灰度值如圖1(a)所示，其Census變換后的比特串為10010100.

圖1 Census變換示意圖Fig.1 Schematic diagram of census transform

由圖1(a)可知，傳統(tǒng)的Census變換能夠在一定程度上改善圖像受到噪聲干擾時的立體匹配性能，但仍存在如下局限性：變換結(jié)果完全依賴于中心點的灰度值，一旦中心像素點受到外界因素的干擾，Census變換編碼結(jié)果會發(fā)生巨大變化，導(dǎo)致誤匹配，降低匹配精度；其次，變換窗口大小的選擇也將影響到算法的匹配精度，窗口選取過大會增加深度不連續(xù)區(qū)域的誤匹配率，且會增加算法的運行時間；窗口選取過小，則包含窗口內(nèi)領(lǐng)域像素的信息較少，使得匹配精度下降，噪點增多.

(3)

式中，Ta為設(shè)定的閾值.閾值的選取不宜選大，過大的閾值會影響匹配精度，所以選擇較小的閾值即可.根據(jù)對圖像相鄰點的分析及在不同閾值下的Census變化仿真選取的閾值區(qū)間為[15,20]，文中采用的閾值為17，則有

(4)

式中,Iz(p)是經(jīng)閾值判斷后變換窗口中心點的灰度值，圖2給出了改進Census變換的對比圖.

圖2 Census變換對比圖Fig.2 Comparison charts using different Census transform

通過對比可知,改進的Census變換能有效降低因外界干擾而引起的Census變換碼的變化.此外，采用自適應(yīng)權(quán)重的方法區(qū)別對待窗口的像素，根據(jù)相似性原則，窗口內(nèi)與待匹配像素顏色信息越接近的像素點分配越大的權(quán)重；如圖3(a)所示，當(dāng)窗口中心點處于深度連續(xù)區(qū)域時，由連續(xù)性假設(shè)可知，窗口內(nèi)其他點與中心點處于相似深度，顏色信息相近，即可認為是窗口內(nèi)的“有效點”.與之對應(yīng)的是當(dāng)窗口中心點處于深度不連續(xù)區(qū)域時，表示窗口內(nèi)的某些點與中心點處在不同深度，即顏色信息差異大，這些點被認為是“無效點”.所以當(dāng)某中心點變換窗口包含的“有效點”越多時，即可認為匹配精度越高，反之則越低.圖3(b)中的黑色部分表示的是誤匹配區(qū)域.

圖3 視差連續(xù)區(qū)域與不連續(xù)區(qū)域誤匹配分布示意圖

Fig.3 Mismatch distribution in depth continuous and discontinuous area

文中采用的自適應(yīng)權(quán)重的顏色相似性方法引入了顏色強度信息，即采用絕對灰度值的方法(AD)[15]，CAD(p,d)表示左圖中點(xp,yp)和右圖中點(xp-d,yp)的平均灰度差值，這里Ii(p)表示第i個RGB通道的灰度值，即：

(5)

C(p,d)即為改進的Census變換與AD方法相結(jié)合的函數(shù)，

(6)

(7)

圖4 中心點領(lǐng)域點的權(quán)值分配Fig.4 Distribution of weights in the center point domain

1.2 匹配代價聚合

成本聚合是局部匹配算法中重要的一步，其目的是借助一個匹配窗口對視差空間進行過濾，減小匹配的歧義性.實現(xiàn)方法是假設(shè)匹配窗口內(nèi)的點均有相似的視差值，把窗口內(nèi)的所有像素點按照一定的權(quán)重系數(shù)累加起來.Hosni等[16- 17]詳細介紹并評估了現(xiàn)有的代價聚合算法，指出大部分聚合算法的思想是試圖區(qū)分中心像素點與其領(lǐng)域內(nèi)相似的點和非相似的點，賦予相似的點更多的權(quán)重、非相似的點更少的權(quán)重.常用判斷兩點是否相似的標(biāo)準(zhǔn)有距離、顏色、測地距離及空間距離等，很多算法的匹配結(jié)果能夠和全局匹配算法相媲美.

但是，傳統(tǒng)的代價聚合算法往往是在細尺度下進行的，它們在處理高紋理區(qū)域時表現(xiàn)得非常好，而在弱紋理和近無紋理區(qū)域的效果不理想.為了進一步提升算法對更符合人類視覺系統(tǒng)的多尺度空間的自適應(yīng)性，采用尺度空間理論中的經(jīng)典表示——高斯金字塔結(jié)構(gòu)[18],通過連續(xù)采樣和亞抽樣得到高斯金字塔結(jié)構(gòu)，再在每個尺度空間上單獨計算匹配聚合代價值，并利用正則變換來加強層間一致性匹配代價運算,最后根據(jù)多尺度空間計算得到其最優(yōu)解.

對每個尺度下的圖像進行代價聚合算法，在對比了雙邊濾波器和基于高斯核的聚合算法之后，采取引導(dǎo)圖濾波算法，其優(yōu)勢在于：首先，其復(fù)雜度與圖像大小無關(guān)，與濾波窗口大小無關(guān)，能提高匹配效率；其次，引導(dǎo)圖濾波能夠梯度保持，所以即使在強度突變的位置顏色信息量較少，但只要能提供足夠的梯度信息，就能實現(xiàn)較好的跟隨效果.這樣就起到了一個很好的區(qū)分視差連續(xù)區(qū)域和視差不連續(xù)區(qū)域的作用，提高該區(qū)域的匹配精度.

先通過對圖像進行高斯下采樣，可以得到多副成對圖像，多尺度代價聚合模型下每層的代價聚合計算公式為

(8)

假設(shè)引導(dǎo)圖像I和濾波器輸出q之間存在一個局部的線性對應(yīng)關(guān)系.這里定義q是I在中心像素為k的窗口wk的線性變換，即：

qi=akIi+bk， ?i∈wk

(9)

式中，ak、bk為窗口內(nèi)的恒定系數(shù).這個局部線性關(guān)系保證了輸出圖像q的邊緣與引導(dǎo)圖像I的邊緣保持一致，因為q=aI.利用引導(dǎo)圖濾波進行代價聚合的詳細過程見文獻[17]，這里直接給出引導(dǎo)圖濾波器的核函數(shù)，即：

(10)

(11)

其中，β為正則化因子，在不同尺度下，同一像素的代價一致，如果正則化因子越大，即說明同一像素不同尺度間的一致性約束越強，這會加強對弱紋理區(qū)域的視差估計，從而提高在弱紋理區(qū)域的匹配精度.

當(dāng)前正是我國扶貧工作的攻堅時期，扶貧模式也由粗放式調(diào)整為精準(zhǔn)式。在落實政策的過程中，鄉(xiāng)村旅游可作為精準(zhǔn)扶貧的媒介。

1.3 視差計算和優(yōu)化

在完成代價聚合步驟后，接下來選擇具有最低聚合費用的偏移值作為最終的視差值(即WTA:贏家通吃策略)[20]，獲得的初始視差值為

(12)

式中，Sd={dmin,…,dmax}為可能的所有視差值，C(p,d)為視差值為d時的匹配代價值.贏家通吃的方法快速有效，通過預(yù)保留聚合費用值可以很容易地獲得該檢測結(jié)果而不增加太多的計算量.

初始視差圖在遮擋區(qū)域和深度不連續(xù)區(qū)域會存在一些誤匹配點，所以需要進行視差優(yōu)化，即采用誤匹配點檢測、區(qū)域投票策略和亞像素增強[9,13]的方法來建立更完整的視差圖.這里定義在視差計算中得到左右圖的視差圖，分別用DL和DR表示，視差圖中每個點都稱為視差點.

誤匹配點檢測：采用左右一致性檢測的方法來檢測誤匹配視差點[9].通過比較左圖和右圖匹配對的視差點的視差值，把視差點分為遮擋點和非遮擋點，即

(13)

(14)

(15)

圖5 視差后處理的結(jié)果Fig.5 Results of disparity post-processing

2 實驗結(jié)果

2.1 匹配代價評估

在19幅Middlebury匹配圖中，改進的Census算法與傳統(tǒng)的Census變換算法對比結(jié)果如表1所示，主要對比了算法的平均匹配精度和時間效率，除了匹配代價算法不一樣外，其余所有步驟保持一致.

表1 傳統(tǒng)Census算法與改進Census算法的對比

Table 1 Comparison of traditional Census method and improved Census method

匹配代價算法誤碼率/%運行時間/sCT1)8.430.41ImCT2)8.020.63

1)CT表示Census變換方法，即原始的統(tǒng)計變換算法；2)ImCT表示文中改進的Census變換方法，即改進后的匹配代價算法

表2 無視差優(yōu)化的匹配算法對比

Table 2 Performance evaluations on algorithms without disparity refinement

匹配圖像誤碼率/%CT-GFCG-GFCT-STCG-STCT-NLCG-NL改進算法Tsukuba4.3174.2963.2333.1313.3253.2643.212Venus2.0371.2721.5741.4331.8261.6051.171Teddy8.7348.8758.2339.3777.8619.2667.962Cones4.7335.3674.8745.0565.0454.5214.642Aloe7.8967.8057.2138.7177.6946.2016.722Art12.44312.37213.05413.70613.62513.83712.231Baby15.6525.8547.6865.6739.1177.5055.511Baby23.7525.7637.1967.5576.7556.7343.551Books13.42610.87211.70312.31412.42514.9279.421Cloth12.8171.6460.9111.2241.5650.9721.803Cloth25.9456.9975.9345.9136.3064.9115.872Dolls7.1927.3337.8167.6458.3277.5747.141Lampshade115.08711.72410.46212.43513.35611.0039.871Flowerpots9.30110.91313.24513.10416.66618.83710.112Reindeer10.50410.4839.86212.82611.64514.0179.471Rock13.8344.6773.4723.9353.7634.0163.461Rock22.6723.7872.7433.2253.2463.0642.631Wood15.0034.6626.1246.78511.31710.7364.391Wood24.6053.0715.9274.6364.0543.4433.172平均誤碼率/%6.8436.7226.9047.2957.7877.7065.911

1)下標(biāo)代表7種算法在每一幅測試圖的排名.

表3 視差優(yōu)化后的匹配算法及計算時間對比

Table 3 Running time of Middlebury stereo pairs by stereo algorithms with disparity refinement

匹配算法非遮擋區(qū)域誤碼率/%全部區(qū)域誤碼率/%計算時間/sCT-GF6.4513.827.02CG-GF6.1312.878.05CT-ST6.4214.254.69CG-ST6.2713.205.68CT-NL7.2015.325.02CG-NL6.8114.065.31改進算法4.5111.877.22

從表1中可以看出ImCT提升了匹配精度且未增加太多時間.

2.2 無視差優(yōu)化評估

執(zhí)行所有的算法及采用贏家通吃策略來計算初始視差值，表2比較了改進算法與其它幾種算法的結(jié)果，視差圖的像素閾值誤差為1.0%，表中可以看到改進算法在11/19幅匹配對中排名第1、19幅匹配對的平均誤碼率在表2最后1排，相比其他算法，改進算法的平均誤碼率最低，即匹配精度更優(yōu).

2.3 視差優(yōu)化評估

算法經(jīng)過視差優(yōu)化后的評估結(jié)果及運算時間如表3所示.算法因考慮到窗口內(nèi)均值像素點計算和多尺度空間，所以計算時間會增加，但因采用引導(dǎo)圖濾波算法及尺度空間個數(shù)，選取了一合適的值，故在提高匹配精度的同時并未增加太大的時間復(fù)雜度.圖6具體給出了Venus、Baby1、Rock1的視差圖，其中在非遮擋區(qū)域的誤匹配點用紅色點標(biāo)記出來.

圖6 7種算法得到的視差優(yōu)化圖Venus、Baby1、Rock1

Fig.6 Disparity refinement maps of Venus，Baby1 and Rock1 obtained by the seven algorithms

3 結(jié)語

文中通過分析傳統(tǒng)Census匹配算法的缺陷，提出一種基于變換窗口信息均值判斷和自適應(yīng)權(quán)重的Census變換方法，提高了在視差不連續(xù)區(qū)域的匹配精度.在代價聚合階段引入多尺度空間的概念，采用高斯金字塔結(jié)構(gòu)，將引導(dǎo)圖濾波算法融合到該結(jié)構(gòu)中，并添加正則化項來加強層間一致性匹配代價運算，充分提高在弱紋理區(qū)域的匹配精度.在視差選擇階段，采用一系列優(yōu)化方法(如誤匹配點檢測、區(qū)域投票策略和亞像素增強等)來提高最后的視差圖精度.實驗結(jié)果表明，文中算法的匹配精度優(yōu)于當(dāng)前部分優(yōu)秀的局部算法，時間復(fù)雜度相對長一些.目前算法主要在CPU上實現(xiàn)，今后的研究將圍繞如何使算法并行化而展開，從而達到實時性的效果.

參考文獻：

[1] SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms [J].International Journal of Computer Vision,2002,47(1):7- 42.

[2] BESSE F,ROTHER C,FITZGIBBON A,et al.PMBP:PatchMatch belief propagation for correspondence field estimation [J].International Journal of Computer Vision,2014,110(1):2- 13.

[3] LIANG Q,YANG Y,LIU B.Stereo matching algorithm based on ground control points using graph cut [C]∥2014 7th International Congress on Image and Signal Processing(CISP).Dalian:IEEE,2015:503- 508.

[4] YOON K J,KWEON I S.Adaptive support-weight approach for correspondence search [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(4):650- 656.

[5] ZHANG K,LU J,LAFRUIT G.Cross-based local stereo matching using orthogonal integral images [J].IEEE Transactions on Circuits & Systems for Video Technology,2009,19(7):1073- 1079.

[6] SHEN Y.Efficient normalized cross correlation calculation method for stereo vision based robot navigation [J].Frontiers of Computer Science,2011,5(2):227- 235.

[7] STENTOUMIS C,GRAMMATIKOPOULOS L,KALISPERAKIS I,et al.On accurate dense stereo-matching using a local adaptive multi-cost approach [J].Isprs Journal of Photogrammetry & Remote Sensing,2014,91(91):29- 49.

[8] SHEN S.Accurate multiple view 3D reconstruction using patch-based stereo for large-scale scenes [J].IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society,2013,22(5):1901- 1914.

[9] MEI X,SUN X,ZHOU M,et al.On building an accurate stereo matching system on graphics hardware [C]∥Proceeding of IEEE International Conference on Computer Vision Workshops.Barcelona:IEEE,2011:467- 474.

[10] ZHANG D.The algorithm of WTA stereo matching based on the human detection method [J].Electronic Test,2013(5):66- 68.

[11] XIAO J,XIA L,LIN L,et al.A segment-based stereo matching method with ground control points [C]∥Proceeding of International Conference on Environmental Science and Information Application Technology.Wuhan:IEEE,2010:306- 309.

[12] HE K,SUN J,TANG X.Guided image filtering [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2013,35(6):1397- 1409.

[13] TIWARI K C,ARORA M K,SINGH D.Subpixel target enhancement in hyperspectral images [J].Proceedings of the International Society for Optical Engineering,2011,63(1):63- 68.

[14] STEIN F.Efficient computation of optical flow using the census transform [J].Lecture Notes in Computer Science,2004,3175:79- 86.

[15] CHAMBON S,CROUZIL A.Similarity measures for image matching despite occlusions in stereo vision [J].Pattern Recognition,2011,44(9):2063- 2075.

[16] HOSNI A,BLEYER M,GELAUTZ M.Secrets of adaptive support weight techniques for local stereo matching [J].Computer Vision & Image Understanding,2013,117(6):620- 632.

[17] MIN D,LU J,DO M N.A revisit to cost aggregation in stereo matching:How far can we reduce its computational redundancy [C]∥Proceeding of IEEE International Conference on Computer Vision.Barcelona:IEEE,2011:1567- 1574.

[18] ZHANG K,FANG Y,MIN D,et al.Cross-scale cost aggregation for stereo matching [C]∥Proceeding of IEEE Conference on Computer Vision and Pattern Recognition.Columbus:IEEE,2014:1590- 1597.

[19] 祝世平,李政.基于改進梯度和自適應(yīng)窗口的立體匹配算法 [J].光學(xué)學(xué)報,2015,35(1):115- 123.

ZHU Shi-ping,LI Zheng.A stereo matching algorithm using improved gradient and adaptive window [J].Acta Optica Sinica,2015,35(1):115- 123.

[20] CHANG X,ZHOU Z,WANG L,et al.Real-time accurate stereo matching using modified two-pass aggregation and winner-take-all guided dynamic programming [C]∥Proceeding of International Conference on 3d Imaging,Mode-ling,Processing,Visualization and Transmission.Hangzhou:IEEE,2011:73- 79.

[21] MEI X,SUN X,DONG W,et al.Segment-tree based cost aggregation for stereo matching [C]∥Proceeding of IEEE International Conference on Acoustics,Speech and Signal Processing.Portland:IEEE,2013:313- 320.

[22] YANG Q.A non-local cost aggregation method for stereo matching [C]∥Proceeding of IEEE Conference on Computer Vision and Pattern Recognition.Providence:IEEE,2012:1402- 1409.