非參數(shù)變換和改進動態(tài)規(guī)劃的立體匹配算法

門宇博，馬 寧，，張國印，李 香，門朝光，孫鵬飛

(1.哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院，150001哈爾濱;2.哈爾濱師范大學(xué)計算機科學(xué)與信息工程學(xué)院，150001哈爾濱)

立體匹配作為計算機視覺領(lǐng)域中的熱點研究內(nèi)容，在機器人自主導(dǎo)航、物體識別與跟蹤、工業(yè)控制與檢測、地理信息系統(tǒng)、生物醫(yī)學(xué)成像及虛擬現(xiàn)實等領(lǐng)域有著廣泛的應(yīng)用［1-3］.Scharstein 等［4］把立體匹配過程概括為匹配代價計算、匹配代價集成、初始視差計算和視差優(yōu)化.根據(jù)匹配基元的不同，立體匹配算法可以分為基于區(qū)域的匹配算法［5］，基于特征的匹配算法［6］和基于相位信息的匹配算法［7］.在基于區(qū)域的算法中，Zabih 等［8］提出的傳統(tǒng)Census算法，利用像素間的大小關(guān)系作為相似性測度，解決了因相機在拍攝過程中受到光照等外部條件影響而產(chǎn)生的參考圖像與目標(biāo)圖像之間的灰度差異所造成的匹配效果降低的問題.但傳統(tǒng)Census的相似性測度由變換窗口的中心像素的灰度值決定，不能完整的描述矩形變換窗口內(nèi)的信息，匹配精度不高，并且在中心點像素發(fā)生畸變的情況下會出現(xiàn)誤匹配.

本文提出一種基于非參數(shù)變換和改進動態(tài)規(guī)劃的立體匹配算法，考慮到相鄰像素間的視差約束，利用改進的Census算法計算匹配代價，增加區(qū)域內(nèi)像素點與鄰域像素均值的比較，將區(qū)域內(nèi)全部像素均值代替了中心點像素，有效地解決了中心點像素的畸變問題，在代價集成中利用全局的改進動態(tài)規(guī)劃方法，大幅提高算法精度.此算法具有較高的匹配精度與魯棒性，在視差優(yōu)化中處理圖像的非紋理區(qū)、深度不連續(xù)處和遮擋處，最終獲得稠密視差圖，得到較好的匹配效果.

1 初始視差圖計算

1.1 稀疏Census非參數(shù)變換的初始匹配代價計算

Census變換的思想是以待匹配像素點為中心取一個矩形區(qū)域，把待匹配像素點灰度值與其鄰域的像素灰度值進行對比生成匹配模板，對該模板進行非參數(shù)變換獲得比特串作為匹配基元，最后利用Hamming距離完成立體匹配［9］.但是由于Census變換匹配法是一種局部算法，沒有考慮相鄰像素間的視差約束，視差結(jié)果的平滑約束受到影響，所以本文提出的基于稀疏Census非參數(shù)變換法作為初始代價的計算方法.并且傳統(tǒng)的Census變換的相似性測度只依賴于變換窗口的中心像素的灰度值，不能完整的描述矩形變換窗口內(nèi)的信息，本文算法將鄰域像素灰度的平均值作為另一個約束條件，用矩形窗口內(nèi)所有像素點灰度均值代替中心點的灰度值，并且每隔一行以及一列選擇一個像素點與兩個均值做比對，獲得兩位二進制碼構(gòu)成的比特串作為新的匹配基元.改進后的Census變換可以更完整地描述所選取支持區(qū)域的像素信息，清晰地區(qū)分出兩個矩陣窗口圖像的不同，同時提高了算法的執(zhí)行效率，解決了由于中心點因噪聲問題發(fā)生畸變所帶來的誤匹配.

稀疏Census非參數(shù)變換的原理如圖1所示，圖1(a)為稀疏Census非參數(shù)變換的模板，其中陰影部分為參加變換的像素，圖1(b)為傳統(tǒng)Census非參數(shù)變換的模板.對圖像Ⅰ中的像素(u，v)進行稀疏Census非參數(shù)變換，首先以像素(u，v)為中心選取一個矩形變換窗口W，其窗口尺寸為n×m，計算窗口內(nèi)全部像素點的均值，計算公式為

式中:Ⅰ(i，j)為像素(i，j)的灰度值;n':=?n/2」，m':=?m/2」.以此均值代替中心像素.計算窗口內(nèi)鄰域像素的均值為

將矩形變換窗口內(nèi)每隔一行以及一列的鄰域像素灰度值Ⅰ(u+i，v+j)與窗口內(nèi)鄰域像素點的均值和窗口內(nèi)全部像素點灰度均值進行比較，可獲得一組bit字符串.稀疏Census變換表示為

式中運算符?為位連接運算，輔助函數(shù)ξ定義為

基于稀疏Census非參數(shù)變換的初始代價計算采用Hamming距離的方法，Hamming距離表示兩個比特串之間在相同位置上不同比特數(shù)的數(shù)目總和，相同的位數(shù)越多，Hamming距離越短，匹配代價越小，兩個像素點越相似.初始代價計算為C(u，v，d)=Hamming(Tr(u，v)，Tt(u+d，v)).式中Tr(u，v)、Tt(u，v)分別為參考圖像和目標(biāo)圖像的像素(u，v)對應(yīng)的稀疏Census變換bit字符串.至此基于稀疏Census變換的初始代價計算完畢，將C(u，v，d)保存在視差空間圖 DSI中，作為下一步動態(tài)規(guī)劃算法的輸入數(shù)據(jù).

圖1 稀疏Census非參數(shù)變換示意

1.2 行列雙向約束動態(tài)規(guī)劃的匹配代價集成

由于空間場景的復(fù)雜性以及局部算法的局限性，立體匹配需要借助全局優(yōu)化技術(shù)獲得滿足平滑約束的視差圖.動態(tài)規(guī)劃算法是一種對掃描線進行約束的全局優(yōu)化算法.該類算法匹配準(zhǔn)確率較高，可以獲得較高精度的稠密視差圖［10］.但是傳統(tǒng)的動態(tài)規(guī)劃立體匹配算法缺乏對掃描線列方向上的視差連續(xù)性的融合，每一條掃描線被單獨處理，缺少了對掃描線之間的約束限制，使得生成的視差圖上帶有明顯的“條紋效應(yīng)”.本文采用基于行列雙向約束的動態(tài)規(guī)劃方法，在已求得的初始匹配代價的基礎(chǔ)上，分別在掃描線行方向上和掃描線列方向上進行全局優(yōu)化以獲得平滑的視差圖.首先構(gòu)造全局能量代價函數(shù)為

式中:Edata(u，v，d)為對應(yīng)像素點(u，v)與(u+d，v)之間的初始匹配代價，即已求得的C(u，v，d);Esmooth-h(u，v，d)為掃描線行方向上的平滑約束項，用來約束掃描線行方向上相鄰像素點之間的不連續(xù)性;Esmooth-v(u，v，d)為掃描線列方向上的平滑約束項，用來約束掃描線列方向上相鄰像素點之間的不連續(xù)性;Eocclude(u，v，d)為遮擋懲罰項，用來對遮擋像素點進行懲罰.

依據(jù)該能量函數(shù)分別在掃描線行方向上和掃描線列方向上進行全局優(yōu)化.由于在掃描線行方向上暫不考慮列方向平滑性約束，行方向能量函數(shù)Eh(u，v，d)可簡化為由數(shù)據(jù)項Edata(u，v，d)，掃描線行方向上的平滑約束項Esmooth-h(u，v，d)以及遮擋懲罰項Eocclude(u，v，d)組成.

利用動態(tài)規(guī)劃算法對行方向上每一條掃描線內(nèi)對應(yīng)像素點之間的匹配代價值進行求解:

根據(jù)掃描線行方向上得到的線內(nèi)能量函數(shù)，對列方向進行動態(tài)規(guī)劃優(yōu)化.列方向能量函數(shù)Ev(u，v，d)即為全局能量代價函數(shù)，可由數(shù)據(jù)項Edata(u，v，d)，掃描線列方向上的視差平滑約束項Esmooth-v(u，v，d)和掃描線行方向上的優(yōu)化結(jié)果Eh(u，v，d)組成.

利用動態(tài)規(guī)劃算法對全局能量代價函數(shù)進行全局優(yōu)化為

將獲得的匹配代價和初始視差結(jié)果存儲于緩存中，作為后續(xù)步驟的輸入數(shù)據(jù).

2 視差圖優(yōu)化

2.1 圖像可信性與紋理性檢測

雖然利用行列雙向約束的動態(tài)規(guī)劃算法可以增加匹配的可信度，但是由于大面積的弱紋理區(qū)域所導(dǎo)致的誤匹配仍然存在.針對非可信與非紋理的圖像區(qū)域，本文提出用于判別圖像的紋理性和可信性的方法.

像素(u，v)的可信性利用最優(yōu)與次優(yōu)匹配代價獲得

式中:Δ(u，v)為像素(u，v)最優(yōu)與次優(yōu)匹配之差;maxcost為最優(yōu)匹配代價值.

像素(u，v)的紋理性通過尺寸為n×m的矩形方差濾波函數(shù)來判斷為

非可信像素與非紋理像素通過兩個閾值τ1和τ2來判斷，只有滿足下式的像素才可以直接賦值為初始視差值.而不滿足下式的像素點則利用視差面擬合計算相應(yīng)的視差，來代替該像素點的初始視差為

2.2 圖像分割與視差平面擬合

對非可信像素與非紋理像素利用分割與平面擬合的方法獲取最終視差.擬合的像素包括非可信與非紋理兩類，利用mean-shift算法［11］對參考圖像進行區(qū)域分割.mean-shift算法利用概率分布的梯度尋找分布峰值的穩(wěn)定性高的非參數(shù)估計方法，將圖像聚類得到一系列互不交叉的區(qū)域.

對于每個圖像分塊，可使用平面方程描述其視差值.將分塊內(nèi)的視差d(x，y)視作關(guān)于像素位置(x，y)的函數(shù)為

式中:x、y分別為像素(x，y)的坐標(biāo);d為該像素對應(yīng)視差值;(a，b，c)為視差平面的參數(shù)，可以用最小二乘法求解平面參數(shù).

式中:矩陣A的第i行元素為［xi，yi，1］;B向量的第i個元素為d(xi，yi).式(2)可以展開為

式中m為分割區(qū)域中的像素點個數(shù).本文利用奇異值分解(SVD)求解該表達式.

式中(ATA)-為ATA的Moore-Penrose逆矩陣，可由SVD求得.

3 算法流程

綜上所述，本文算法流程如圖2所示.

關(guān)鍵步驟歸納如下:

1)采用稀疏Census變換算法對參考圖像和目標(biāo)圖像進行局部匹配處理，獲取初始匹配代價;

2)利用行列雙向約束的動態(tài)規(guī)劃算法對初始匹配代價進行全局優(yōu)化獲取初始視差，其中懲罰系數(shù)普遍采用λdisc=20，λocc=15來進行試驗;

3)對參考圖像逐像素點進行可信性和紋理性檢測，確定非可信像素與非紋理像素位置.對于非可信像素的檢測，由于圖像平面的質(zhì)量很大程度上取決于用于擬合的數(shù)據(jù)，所以選取τ1=200這種高可信度的閾值.對于非紋理像素的檢測，為了綜合提高算法可行性與準(zhǔn)確度，在不失準(zhǔn)確性與運算速度的同時能夠檢測出弱紋理區(qū)，選取τ2=20;

4)按照紋理性對參考圖像進行二值化分割，同時利用mean-shift算法對參考圖像進行灰度區(qū)域分割;

5)利用奇異值分解計算分割面參數(shù)，將非可信像素與非紋理像素的視差值用視差平面擬合的結(jié)果替換;

6)將計算結(jié)果合并為最終的稠密視差圖.

圖2 算法流程

4 實驗分析

為了驗證本文算法的有效性與正確性，本文利用VC++編程實現(xiàn)了所提算法.實驗對象采用Middlebury大學(xué)立體視覺數(shù)據(jù)庫中提供的4組標(biāo)準(zhǔn)立體圖像［4］:包括 Tsukuba、Teddy、Venus 和Cones圖像，尺寸分別為384像素 ×288像素、434像素×383像素、450像素 ×375像素和450像素×375像素，圖像均已進行了極線校正，視差只存在于同掃描線方向，視差搜索范圍的最大值分別是16、20、60和60像素，通過對上述圖像分別進行測試驗證本文算法的匹配效果.圖3給出了本文算法的實驗結(jié)果.

同時為了更好地評測本文算法的立體匹配結(jié)果，本文實現(xiàn)了另外兩種文中涉及到的算法，一種算法是經(jīng)典的動態(tài)規(guī)劃立體匹配算法(DP算法)［4］，另一種算法是 Humenberger 等［12］提出的改進Census非參數(shù)變換立體匹配算法，該方法是目前非參數(shù)變換類型的算法中效果較好的一種 (簡稱RTCensus算法).

圖3 本文算法的立體匹配實驗結(jié)果

圖4給出了3種算法的實驗結(jié)果圖.可以看出，DP算法生成的視差圖平滑性較好，物體邊緣較清晰，但視差結(jié)果中存在著明顯的條紋狀效應(yīng)，導(dǎo)致了錯誤視差向相鄰像素傳遞;RTCensus算法生成的視差圖在紋理豐富區(qū)域效果較好，但在物體邊界處(遮擋或不連續(xù)區(qū)域)，產(chǎn)生邊界模糊現(xiàn)象，在弱紋理區(qū)域同樣存在錯誤匹配;本文算法得到的視差結(jié)果優(yōu)于DP算法和RTCensus算法的實驗結(jié)果，由于同時考慮了行列雙方向上的視差不連續(xù)性，明顯消除了條紋狀效應(yīng)，且利用分割與平面擬合技術(shù)，在弱紋理區(qū)域、遮擋區(qū)域和視差不連續(xù)區(qū)域得到的匹配效果更加理想.另外，本文算法的初始代價計算利用了Census變換，使得算法具有一定的抑制噪聲能力.

圖4 基于標(biāo)準(zhǔn)立體圖像的3種算法比較實驗結(jié)果

表1給出了3種參加比對實驗的算法在錯誤匹配率方面的量化實驗結(jié)果.表1為Nonocc(非遮擋)區(qū)域的錯誤匹配率;All(包括遮擋區(qū)域在內(nèi)的整體)區(qū)域的錯誤匹配率;Disc(視差不連續(xù))區(qū)域的錯誤匹配率.由表1給出的量化結(jié)果顯示，本文提出的算法在非遮擋區(qū)域、整體區(qū)域和視差不連續(xù)區(qū)域的錯誤匹配率都明顯低于DP算法和 RTCensus算法，取得了較高的匹配精度.

表1 本文算法與DP算法、RTCensus算法的量化實驗結(jié)果比較

根據(jù)上述實驗結(jié)果可知，本文算法有效解決了立體影像的匹配問題，算法匹配正確率較高，尤其在弱紋理區(qū)域、遮擋區(qū)域和視差不連續(xù)區(qū)域具有良好的穩(wěn)定性.

5 結(jié)語

本文提出一種基于非參數(shù)變換和改進動態(tài)規(guī)劃的立體匹配算法，采用稀疏Census變換計算初始局部匹配代價，構(gòu)造基于行列雙向的全局能量函數(shù)，并利用改進動態(tài)規(guī)劃算法求解初始視差，對非紋理與非可信區(qū)域的像素，通過視差平面擬合代替初始視差結(jié)果.算法最大限度地利用了圖像紋理信息以及掃描線相鄰像素點間的平滑信息，有效克服了弱紋理區(qū)域、遮擋區(qū)域和視差不連續(xù)區(qū)域?qū)σ暡罱Y(jié)果的影響.實驗結(jié)果表明，該算法在匹配效果和匹配精度方面均優(yōu)于傳統(tǒng)的動態(tài)規(guī)劃立體匹配算法和魯棒性較好的基于Census非參數(shù)變換立體匹配算法，降低了錯誤匹配率，可以獲得匹配準(zhǔn)確率較高的稠密視差圖，得到較好的匹配效果.

［1］BROWN M Z，BURSCHKA D，HAGER G D.Advances in computational stereo［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence， 2003，25(8):993-1008.

［2］HUMENBERGER M，ENGELKE T，KUBINGER W.A census-based stereo vision algorithm using modified semi-global matching and plane fitting to improve matching quality［C］//Proceeding of the 2010 IEEE Computer Society Conference on Computer Vision and PatternRecognition Workshops(CVPRW).San Francisco，CA:IEEE，2010:77-84.

［3］ KUMAR S，KUMAR S，SUKAVANAM N，et al.Human visualsystem and segment-based disparity estimation ［J］. AEU-International Journal of Electronics and Communications，2013，67(5):372-381.

［4］SCHARSTEIN D，SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms［J］.International Journal of Computer Vision，2002，47(1/3):7-42.

［5］ RHEMANN C，HOSNI A，BLEYER M，et al.Fast cost-volume filtering forvisualcorrespondence and beyond［C］//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition(CVPR).Washington， DC:IEEE ComputerSociety， 2011:3017-3024.

［6］ NIERADKA G，BUTKIEWICZ B S.Features stereo matching based on Fuzzy logic［C］//Proceedings of the Joint 2009 InternationalFuzzy SystemsAssociation World Congress and 2009 European Society of Fuzzy Logic and Technology Conference.Lisbon，Portudal，2009:1188-1193.

［7］ULUSOY I，HANCOCK E R.A statistical approach to sparse multi-scale phase-based stereo［J］. Pattern Recognition，2007，40(9):2504-2520.

［8］ ZABIH R， WOODFILL J. Non-parametricLocal Transforms for Computing Visual Correspondence［M］.Springer，Berlin-Heidelberg:Computer Vision—ECCV'94，1994:151-158.

［9］FIFE W S，ARCHIBALD J K.Improved census transforms for resource-optimized stereo vision ［J］. IEEE Transactions on Circuits and Systems for Video Technology，2013，23(1):60-73.

［10］TORR P H S，CRIMINISI A.Dense stereo using pivoted dynamic programming［J］.Image and Vision Computing，2004，22(10):795-806.

［11］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(5):603-619.

［12］HUMENBERGER M，ZINNER C，WEBER M，et al.A fast stereo matching algorithm suitable for embedded real-time systems［J］.Computer Vision and Image Understanding，2010，114(11):1180-1202.