亢宇欣，諶貴輝，鄧 宇，張軍豪

多測度融合的立體匹配算法研究

亢宇欣，諶貴輝，鄧 宇，張軍豪

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

針對多測度融合的立體匹配算法的測度選擇問題，提出一種基于測度互補(bǔ)系數(shù)的測度選擇方法。通過該方法選擇多種測度進(jìn)行融合作為匹配代價(jià)，并使用改進(jìn)的半全局算法進(jìn)行代價(jià)聚合，實(shí)現(xiàn)多測度融合的立體匹配算法。首先定義互補(bǔ)系數(shù)，通過互補(bǔ)系數(shù)選擇多種相似性測度進(jìn)行融合作為匹配代價(jià)；然后，針對半全局代價(jià)聚合使用隨機(jī)初始化視差圖導(dǎo)致立體匹配效果較差的問題，使用基于SURF特征得到的視差作為初始視差進(jìn)行半全局代價(jià)聚合；最后計(jì)算視差并優(yōu)化視差得到最終視差圖。實(shí)驗(yàn)表明，使用該測度選擇方法可以選擇互補(bǔ)特征，結(jié)合改進(jìn)的半全局代價(jià)聚合方法可以提高立體匹配效果。

多測度融合；測度互補(bǔ)系數(shù)；半全局代價(jià)聚合；立體匹配

雙目視覺模擬人類視覺原理，實(shí)現(xiàn)從二維圖像獲取三維信息。立體匹配是指雙目視覺系統(tǒng)針對同一場景在不同角度拍攝到的2幅圖像，在搜索圖像中找到參考圖像對應(yīng)點(diǎn)的過程。立體匹配的效果決定雙目視覺所獲取三維信息的精確度，是雙目視覺的重要環(huán)節(jié)。

SCHARSTEIN等[1]將立體匹配算法進(jìn)行分類與評估，將其劃分為匹配代價(jià)計(jì)算、匹配代價(jià)聚合、初始視差計(jì)算與視差優(yōu)化4個(gè)相對獨(dú)立的模塊，此后關(guān)于立體匹配算法的研究大多沿用此框架。針對匹配代價(jià)計(jì)算，為解決單一相似性測度對圖像特征描述不完全，影響匹配精度的問題，文獻(xiàn)[2]提出融合圖像灰度信息，將灰度差絕對值之和(sum of absolute differences, SAD)、灰度差平方和(sum of squared differences, SSD)以及水平梯度分量作為匹配代價(jià)，在彩色圖像上取得更好的效果；陸軍等[3]設(shè)計(jì)了一種SAD與Census變換相融合的相似性測度算法，結(jié)合線性平滑項(xiàng)和動(dòng)態(tài)變搜索半徑，有效改善條紋誤匹配現(xiàn)象。靳太明等[4]提出一種融合顏色特征、Census特征、局部二值模型(local binary pattern, LBP)特征并考慮圖像多尺度信息的匹配算法，在多種復(fù)雜場景中提高了匹配精度。相比單一測度，多測度融合作為匹配代價(jià)具有更好的立體匹配效果，但多種測度的選擇還沒有較好的方法，多根據(jù)經(jīng)驗(yàn)和測度特性進(jìn)行選擇融合。針對此問題，本文通過定義測度互補(bǔ)系數(shù)并使用該系數(shù)進(jìn)行測度選擇，實(shí)驗(yàn)證明該方法可以選擇效果互補(bǔ)的多種測度。

有關(guān)匹配代價(jià)聚合，門宇博等[5]提出一種自適應(yīng)多窗口方案，解決存在遮擋時(shí)的魯棒視差估計(jì)。常用的代價(jià)聚合算法還有雙邊濾波[6]和引導(dǎo)濾波[7]。此外，還有一種半全局代價(jià)聚合算法[8]，該算法的主要思想是通過求多方向一維最優(yōu)解來模擬全局最優(yōu)，相比于雙邊濾波和引導(dǎo)濾波，可以取得更好的代價(jià)聚合效果。但是半全局代價(jià)聚合使用隨機(jī)視差作為初始視差，影響算法的精度和效率。針對此問題，本文使用基于加速魯棒特征(speeded up robust features, SURF)[9]生成的視差作為初始視差進(jìn)行代價(jià)聚合，并通過WTA (winner take all)算法[10]獲取視差圖并經(jīng)過視差優(yōu)化獲得最終視差圖。實(shí)驗(yàn)表明，該立體匹配算法可以取得較好的匹配效果。

1 算法總體框架

針對單一相似性測度不能全面描述圖像局部特征的問題，使用多種相似性測度融合作為匹配代價(jià)；針對半全局算法使用隨機(jī)初始化視差在多尺度空間計(jì)算導(dǎo)致算法效率低的問題，由于SURF特征描述符具有高效、高匹配率的優(yōu)點(diǎn)，使用基于SURF特征提取的視差圖作為初始視差圖進(jìn)行半全局代價(jià)聚合，經(jīng)過視差計(jì)算、左右一致性檢驗(yàn)、可信度檢驗(yàn)等步驟得到最終視差圖。算法總體框架如圖1所示。其中，I，I為經(jīng)過校正的左右圖像；[，]為多測度融合的匹配代價(jià)；D為基于SURF特征匹配得到的視差圖；[,]為半全局代價(jià)聚合后的匹配代價(jià)；D為使用WTA算法計(jì)算得到的初始視差；為經(jīng)過視差優(yōu)化后輸出的最終視差圖。

圖1 算法流程圖

2 多種相似性測度的選擇

相似性測度描述的是圖像的相似程度，常見相似性測度有SAD、SSD、歸一化交叉相關(guān)(normalization cross correlation, NCC)[11]、梯度度量(gradient based measure, GBM)、Census[12]變換度量、LBP[13]度量和韋伯局部描述符(Weber’s local descriptor, WLD)[14]度量等。

不同相似性測度使用不同的圖像信息和圖像特征對圖像相似性進(jìn)行描述，各測度有各自的優(yōu)勢區(qū)域。例如SAD測度關(guān)注圖像灰度信息，以圖像灰度差別進(jìn)行相似度評價(jià)；GBM關(guān)注圖像梯度信息，以梯度差別進(jìn)行相似度評價(jià)。融合多種相似性測度可以更全面地描述圖像，進(jìn)而提高匹配精度，如圖2所示。圖2(a)中綠色標(biāo)記為SAD測度正確匹配點(diǎn)，紅色標(biāo)記為GBM，藍(lán)色標(biāo)記為2種測度均正確匹配的像素點(diǎn)；圖2(b)中綠色為SAD測度正確匹配點(diǎn)，紅色為SSD測度，藍(lán)色為2種測度均正確匹配的像素點(diǎn)。

可以看出，SAD與GBM重合程度較低，SAD與SSD重合程度非常高。SAD單獨(dú)作用時(shí)正確匹配率為44.38%，SAD分別與SSD和GBM測度融合后匹配正確率為44.51%和52.1%?？梢娭睾铣潭雀叩腟SD與SAD融合后對于匹配正確率的提升非常小，重合程度低的GBM與SAD測度融合后對于匹配正確率的提升較為明顯。本文提出一種基于優(yōu)勢作用區(qū)域互補(bǔ)程度的相似性測度選擇方法。

圖2 測度作用效果

2.1 測度互補(bǔ)系數(shù)

每種相似性測度有各自的特點(diǎn)和優(yōu)勢作用區(qū)域，設(shè)與S為使用和2種相似性測度單獨(dú)作用所得正確匹配點(diǎn)點(diǎn)集，定義測度互補(bǔ)系數(shù)為

其中，為調(diào)節(jié)系數(shù)；ρ為2種相似性測度作用下正確匹配點(diǎn)的相異點(diǎn)數(shù)與相同點(diǎn)數(shù)之比。顯然，該系數(shù)越大，表示2種相似性測度正確匹配的相異點(diǎn)越多，互補(bǔ)程度越高；反之互補(bǔ)程度越低，按照此系數(shù)進(jìn)行特征選擇，可以選出效果互補(bǔ)的測度。

2.2 基于測度互補(bǔ)系數(shù)的測度選擇

為驗(yàn)證測度互補(bǔ)系數(shù)對測度選擇效果的影響，使用Middlebury數(shù)據(jù)集，根據(jù)上述7種測度進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先計(jì)算各測度單獨(dú)作用所得匹配結(jié)果，如圖3所示。

選擇正確率最高的SAD測度作為第一個(gè)測度，依次計(jì)算其余測度與SAD測度的互補(bǔ)系數(shù)，并分別計(jì)算其余測度與SAD融合后的匹配效果與正確率，如圖4所示。

圖4中SAD+GBM測度融合后匹配效果最佳且互補(bǔ)系數(shù)最大，選擇其作為下一步初始測度。分別計(jì)算其余測度與SAD與GBM融合后的匹配效果及互補(bǔ)系數(shù)，循環(huán)上述步驟，直至融合所有測度，結(jié)果見表1。

測度SADSSDLBPNCCWLDCensusGBM 匹配效果 正確率(%)44.3843.8237.8035.5436.7231.7039.18

測度SAD+SSDSAD+LBPSAD+NCCSAD+WLDSAD+CensusSAD+GBM 匹配效果 互補(bǔ)系數(shù)0.0510.21460.1470.1950.2770.385 正確率(%)44.5146.4945.8346.3348.9652.10

表1 測度相關(guān)系數(shù)表

可以看出，每次進(jìn)行測度融合時(shí)，正確率最高的測度其互補(bǔ)系數(shù)也最大?；跍y度互補(bǔ)系數(shù)進(jìn)行測度選擇融合可以選出互補(bǔ)測度并取得更好的匹配效果。

3 半全局代價(jià)聚合

半全局算法是使用多方向一維動(dòng)態(tài)規(guī)劃近似二維動(dòng)態(tài)規(guī)劃求解能量函數(shù)最小值，以提高弱紋理、視差不連續(xù)和遮擋區(qū)域的匹配精度。

3.1 SGM算法

SGM使用動(dòng)態(tài)規(guī)劃優(yōu)化能量函數(shù)，求得能量函數(shù)最小時(shí)的視差，能量函數(shù)定義為

其中，()為視差圖的能量函數(shù)；(,D)為原始匹配代價(jià)；后2項(xiàng)為懲罰項(xiàng)，指當(dāng)前像素和其鄰域內(nèi)所有像素之間的約束。如果和的視差為1，那么懲罰1項(xiàng)；如果大于1，那么懲罰2項(xiàng)。

使用動(dòng)態(tài)規(guī)劃進(jìn)行能量函數(shù)最小化的求解是NP完全問題。在二維圖像上利用動(dòng)態(tài)規(guī)劃求解及其復(fù)雜，但如果只考慮某一行或某一列存在約束不足的問題，使用多方向一維動(dòng)態(tài)規(guī)劃可以兼顧求解準(zhǔn)確度和效率。首先構(gòu)建單一方向的狀態(tài)轉(zhuǎn)移方程

對多個(gè)方向使用掃描線優(yōu)化并對每個(gè)掃描線上的L(,)求和，得到圖像上點(diǎn)的代價(jià)聚合，即

3.2 基于SURF初始視差的SGM代價(jià)聚合

由于SGM算法需要一個(gè)初始化視差圖，原算法隨機(jī)初始化視差圖，并經(jīng)過多尺度的多次迭代求取最終視差圖。算法效果和速度受初始視差圖的影響，而基于SURF特征初始化視差圖，可提高算法精度和效率。

3.2.1 SURF特征描述符

SURF是對尺度不變特征變換(scale invariant feature transform, SIFT)的優(yōu)化，是一種魯棒的局部特征點(diǎn)描述算法，具有尺度縮放、旋轉(zhuǎn)和仿射不變性。SURF特征提取與匹配[9]主要包括以下步驟：

(1) 構(gòu)建Hessian矩陣，生成所有的興趣點(diǎn)；

(2) 構(gòu)建尺度空間；

(3) 特征點(diǎn)定位；

(4) 特征點(diǎn)主方向分配；

(5) 生成特征點(diǎn)描述符；

(6) 基于歐式距離最小化的特征匹配。

3.2.2 基于SURF特征的視差

對左、右2圖提取的特征點(diǎn)，以SURF特征描述符歐式距離最小為標(biāo)準(zhǔn)進(jìn)行特征點(diǎn)匹配，進(jìn)而求取稀疏視差。使用區(qū)域生產(chǎn)算法獲得稠密視差，并以此為初始視差圖進(jìn)行SGM代價(jià)聚合。

3.3 基于SURF的SGM算法實(shí)驗(yàn)

為測試算法效果，設(shè)計(jì)如下實(shí)驗(yàn)。首先按照3.2.1節(jié)步驟對左、右2圖進(jìn)行SURF特征提取與匹配，如圖5所示。生成關(guān)鍵點(diǎn)如圖6所示。

對每個(gè)關(guān)鍵點(diǎn)計(jì)算Harr小波特征的主方向，并以其為基準(zhǔn)方向計(jì)算每個(gè)特征點(diǎn)的SURF描述符，根據(jù)歐式距離最小進(jìn)行特征點(diǎn)匹配，得到圖7匹配結(jié)果。

使用對應(yīng)點(diǎn)橫坐標(biāo)差計(jì)算視差，得到稀疏視差圖，使用區(qū)域生長算法獲得稠密視差，如圖8所示。

以該視差圖作為初始視差圖的半全局立體匹配，并與原立體匹配算法進(jìn)行對比。原算法進(jìn)行多次下采樣，通過多輪迭代，對每輪迭代的結(jié)果進(jìn)行上采樣作為下一輪迭代的初始視差。基于SURF特征的半全局算法只在原尺度進(jìn)行計(jì)算，統(tǒng)計(jì)2種算法在所有數(shù)據(jù)集上每輪迭代的平均誤匹配率和平均運(yùn)行時(shí)間。實(shí)驗(yàn)用計(jì)算機(jī)CPU主頻3.4 GHz，內(nèi)存8 GB，使用Python語言編程，使用Middlebury數(shù)據(jù)集中Cones、Teddy、Tsukuba和Venus數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表2和表3。

圖5 關(guān)鍵點(diǎn)求取過程

圖6 關(guān)鍵點(diǎn)標(biāo)記

圖7 SURF特征匹配

圖8 區(qū)域生長稠密視差圖

由表2和表3可以看出，原算法經(jīng)過5輪迭代后的誤匹配率為6.87%，而改進(jìn)后的算法只需2輪迭代誤匹配率穩(wěn)定在6.79%；原算法總運(yùn)行時(shí)間為137 ms，改進(jìn)算法所用時(shí)間為125 ms。綜上，基于SURF特征的SGM算法在算法誤匹配率和算法效率方面有一定改善。

表2 SGM算法效果

表3 SURF-SGM算法效果

4 算法實(shí)驗(yàn)與分析

選擇SAD、GBM、Census和WLD4種測度融合作為匹配代價(jià)，匹配代價(jià)如式(7)所示。使用改進(jìn)的半全局算法進(jìn)行代價(jià)聚合，利用WTA算法計(jì)算初始視差，經(jīng)過左右一致性檢驗(yàn)、可信度檢驗(yàn)得到最終視差，按照圖1的算法流程進(jìn)行實(shí)驗(yàn)。使用Middlebury數(shù)據(jù)集作為算法測試數(shù)據(jù)集，計(jì)算機(jī)CPU主頻3.4 GHz、8 G內(nèi)存，使用Python編程。

通過實(shí)驗(yàn)確定參數(shù)，首先使用上述4種測度單獨(dú)進(jìn)行匹配，并不斷變換測度對應(yīng)參數(shù)，以誤匹配率最小時(shí)的參數(shù)對應(yīng)測度的參數(shù)，求得各測度參數(shù)為：λ=32，T=17，T=0.013，T=0.010，T=0.024。然后進(jìn)行融合測度權(quán)重實(shí)驗(yàn)，設(shè)所有測度權(quán)重之和為1，在此約束條件下不斷調(diào)整各測度權(quán)重，以誤匹配率最小時(shí)的權(quán)重作為最終權(quán)重，求得各測度權(quán)重為：1=0.110，2=0.730，3=0.126，4=0.034。

為驗(yàn)證算法性能，與當(dāng)前效果較好的SGM、Segment Support算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖9所示。

原圖Segment SupportSGM本文算法真實(shí)視差圖 Cones Teddy Tsukusa Venus

由圖9可以看出，與SGM[15]、Segment Support算法[16]相比，本文算法在紋理區(qū)域、視差不連續(xù)區(qū)域和遮擋區(qū)域表現(xiàn)出更好的效果。如Cones數(shù)據(jù)中方框標(biāo)記位置為視差不連續(xù)區(qū)域，本文算法在該區(qū)域得到更加平滑的視差；Teddy數(shù)據(jù)中方框標(biāo)記位置為紋理區(qū)域和遮擋區(qū)域，本文算法紋理區(qū)域視差平滑、遮擋區(qū)域視差輪廓更為清晰。同樣地，本文算法在Tsukusa與Venus數(shù)據(jù)中紋理區(qū)域、視差不連續(xù)區(qū)域也有更好的效果。各算法在Middlebury數(shù)據(jù)集上不同區(qū)域測試結(jié)果見表4~7。

由表4~7可以看出，與另2種算法相比，本文算法在多種圖像區(qū)域匹配效果更佳。另SGM、Segment Support及本文算法的平均誤匹配率分別為6.87%，6.58%，4.56%，本文的立體匹配效果較好。

表4 Cones數(shù)據(jù)上算法效果

表5 Teddy數(shù)據(jù)上算法效果

表6 Tsukuba數(shù)據(jù)上算法效果

表7 Venus數(shù)據(jù)上算法效果

5 結(jié) 論

針對立體匹配算法匹配代價(jià)計(jì)算與代價(jià)聚合步驟，本文提出一種相似性測度選擇方法，使用該方法選擇相似性測度融合作為匹配代價(jià)，實(shí)現(xiàn)對圖像區(qū)域更全面地描述。使用基于SURF特征生成的視差圖作為初始視差進(jìn)行半全局代價(jià)聚合。經(jīng)過實(shí)驗(yàn)驗(yàn)證，與當(dāng)前較為經(jīng)典的SGM與Segment Support算法相比，本文算法在紋理區(qū)域、遮擋區(qū)域與視差不連續(xù)區(qū)域有更好的匹配效果。

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

[2] TOLT G, KALAYKOV I. Measures based on fuzzy similarity for stereo matching of color images [J]. Soft Computing, 2006, 10(12): 1117-1126.

[3] 陸軍, 方瑩, 張鑫. 融合AD與Census變換的動(dòng)態(tài)規(guī)劃立體匹配與遮擋處理[J]. 北京理工大學(xué)學(xué)報(bào), 2015, 35(12): 1274-1279.

[4] 靳太明, 曾婧, 張翔. 基于多特征融合的多尺度立體匹配算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(A2): 139-142.

[5] 門宇博, 張國印, 門朝光, 等. 像素?cái)U(kuò)展自適應(yīng)窗口立體匹配算法[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 2018, 39(3): 547-553.

[6] 宋時(shí)德, 李淼, 張健, 等. 面向以多視角立體匹配獲取的植株三維點(diǎn)云的去噪方法[J]. 計(jì)算機(jī)應(yīng)用, 2017, 37(S2): 141-145.

[7] 閆利, 王芮, 劉華, 等. 基于改進(jìn)代價(jià)計(jì)算和自適應(yīng)引導(dǎo)濾波的立體匹配[J]. 光學(xué)學(xué)報(bào), 2018,38(11): 257-267.

[8] 呂倪祺, 宋廣華, 楊波威. 特征融合的雙目半全局匹配算法及其并行加速實(shí)現(xiàn)[J]. 中國圖象圖形學(xué)報(bào), 2018, 23(6): 874-886.

[9] 馮亦東, 孫躍. 基于SURF特征提取和FLANN搜索的圖像匹配算法[J]. 圖學(xué)學(xué)報(bào), 2015, 36(4): 650-654.

[10] 王玉鋒, 王宏偉, 吳晨, 等. 基于共同視域的自監(jiān)督立體匹配算法[J]. 光學(xué)學(xué)報(bào), 2019, 39(2): 287-296.

[11] 宋毅, 崔平遠(yuǎn), 居鶴華. 一種圖像匹配中SSD和NCC算法的改進(jìn)[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 42(2): 42-44.

[12] 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]//2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Workshops. Washington, DC: IEEE Computer Society, 2010: 77-84.

[13] 胡敏, 余子璽, 王曉華, 等. G-LBP和方差投影交叉熵的人臉識別[J]. 圖學(xué)學(xué)報(bào), 2017, 38(1): 82-89.

[14] CHEN J, SHAN S G, HE C, et al. WLD: A robust local image descriptor [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(9): 1705-1720.

[15] HIRSCHMULLER H. Accurate and efficient stereo processing by semi-global matching and mutual information [C]//2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Washington, DC: IEEE Computer Society, 2015: 807-814.

[16] TOMBARI F, MATTOCCIA S, DI STEFANO L. Segmentation-based adaptive support for accurate stereo correspondence [M]//Advances in Image and Video Technology. Heidelberg: Springer, 2007: 427-438.

Research on Stereo Matching Algorithms Based on Multi-Measure Fusion

KANG Yu-xin, CHEN Gui-hui, DENG Yu, ZHANG Jun-hao

(School of Electrical Engineering and Information, Southwest Petroleum University, Chengdu Sichuan 610500, China)

Aiming at the measure selection problem of stereo matching algorithm based on multi-measure fusion, a measure selection method based on measure complementarity coefficient is proposed. Using this method, the present study fuses multiple measures as the matching cost, and adopts the improved semi-global algorithm for cost aggregation to realize the stereo matching algorithm of multi-measures fusion. Firstly, the complementary coefficients are defined, and a variety of similarity measures are fused by the complementary coefficients as matching costs. Then, in attempt to solve the problem of poor stereo matching effect caused by semi-global cost aggregation using randomly initialized disparity map, we carried out the semi-global cost aggregation taking disparity based on SURF features as initial disparity. Finally, the disparities are calculated and optimized to obtain the final disparity map. The experimental results show that the complementary features can be selected by using the measure selection method, and the stereo matching effect can be improved by combining the improved semi-global cost aggregation method.

multi-measure fusion; measure complementarity coefficient; semi-global cost aggregation; stereo matching

TP 391

10.11996/JG.j.2095-302X.2019040711

A

2095-302X(2019)04-0711-07

2019-02-01；

定稿日期：2019-03-21

四川省科技計(jì)劃項(xiàng)目(2016GZ0107)；四川省教育廳重點(diǎn)項(xiàng)目(16ZA0065)；南充市市?？萍紤?zhàn)略合作項(xiàng)目(NC17SY4001)

亢宇欣(1993-)，男，河北廊坊人，碩士研究生。主要研究方向?yàn)橛?jì)算機(jī)視覺、人工智能。E-mail：284260916@qq.com