基于互信息的半全局密集立體匹配算法

張桂濱，鞏丹超，王仁禮，王 一

1.山東科技大學(xué) 山東省基礎(chǔ)地理信息與數(shù)字化技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島，266590；2.西安測(cè)繪研究所，陜西 西安，710054；3.航天天繪科技有限公司，陜西 西安，710100

?

基于互信息的半全局密集立體匹配算法

張桂濱1,3，鞏丹超2，王仁禮1，王 一3

1.山東科技大學(xué) 山東省基礎(chǔ)地理信息與數(shù)字化技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 青島，266590；2.西安測(cè)繪研究所，陜西 西安，710054；3.航天天繪科技有限公司，陜西 西安，710100

鑒于密集匹配在三維重建中具有重要的作用，本文研究了一種基于互信息的半全局密集立體匹配算法。它利用立體像對(duì)對(duì)應(yīng)像素間的互信息作為匹配代價(jià)，通過(guò)16個(gè)方向的一維搜索近似全局匹配；并通過(guò)金字塔傳遞、動(dòng)態(tài)規(guī)劃、視差優(yōu)化等策略對(duì)立體像對(duì)進(jìn)行逐像素匹配，確定立體像對(duì)像素間的一一對(duì)應(yīng)關(guān)系。實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)紋理貧乏、有遮擋區(qū)域影像仍可以生成精確稠密的視差圖。

互信息；立體匹配；動(dòng)態(tài)規(guī)劃；視差圖

1 引 言

三維重建在醫(yī)學(xué)、虛擬現(xiàn)實(shí)、地質(zhì)學(xué)等很多方面都有重要的作用。通過(guò)匹配方法生成大量的密集匹配點(diǎn)是三維重建的關(guān)鍵技術(shù)之一。立體匹配是在不同視點(diǎn)的條件下，獲取同一場(chǎng)景的兩幅或多幅圖像，通過(guò)尋找同一空間景物在投影圖像中像素點(diǎn)的一一對(duì)應(yīng)關(guān)系，得到視差圖和深度信息，從而恢復(fù)場(chǎng)景的三維立體信息。針對(duì)立體匹配在視差不連續(xù)區(qū)域、遮擋區(qū)域以及弱紋理區(qū)域匹配難以獲得良好視差圖的問(wèn)題，很多研究學(xué)者展開(kāi)了研究。Dhond[1]采用三目約束的匹配算法，降低立體匹配的歧義性。Koschan[2]等對(duì)早期的遮擋和無(wú)紋理問(wèn)題及實(shí)時(shí)立體視覺(jué)的實(shí)現(xiàn)進(jìn)行了總結(jié)與探討。Scharstein[3]對(duì)兩幀圖像的稠密立體匹配算法進(jìn)行了性能測(cè)試、分析和比較。Yoon和Kweon[4]提出了基于顏色信息和距離信息的自適應(yīng)加權(quán)窗口的匹配算法。Rhemann等人[5]將具有邊緣保護(hù)的平滑濾波技術(shù)應(yīng)用到匹配算法中。

目前，根據(jù)匹配策略的不同，立體密集匹配算法大致可以分為局部?jī)?yōu)化的匹配算法和全局優(yōu)化的匹配算法兩類(lèi)。其中，局部?jī)?yōu)化的匹配算法對(duì)無(wú)紋理區(qū)域、視差不連續(xù)區(qū)域和遮擋區(qū)域敏感，匹配效果不理想[6]，生成的視差圖不連續(xù)、不緊密；全局優(yōu)化匹配算法通過(guò)比較立體像對(duì)所有像素點(diǎn)間的灰度相關(guān)性確定其對(duì)應(yīng)關(guān)系，生成稠密的視差圖，但計(jì)算量大、速度慢。因此，出現(xiàn)了動(dòng)態(tài)規(guī)劃立體匹配算法[7]、Birchfield和Tomasi的BT算法[8]等。然而，傳統(tǒng)的動(dòng)態(tài)規(guī)劃立體匹配算法[7]和BT算法[8]產(chǎn)生的視差圖存在條紋瑕疵，影響視差圖的質(zhì)量，進(jìn)而影響密集匹配的精度。本文研究的算法通過(guò)16個(gè)方向的一維搜索近似全局匹配方法，并采用金字塔傳遞、動(dòng)態(tài)規(guī)劃和視差優(yōu)化等策略，解決了視差圖不連續(xù)、不緊密和條紋瑕疵的問(wèn)題，相對(duì)于全局優(yōu)化的匹配算法在速度上也有一定的提高。

2 基于互信息的半全局立體匹配算法

本文研究算法基本流程如圖1：給定兩幅立體影像對(duì)，首先，采用金字塔傳遞的思想對(duì)待匹配的兩幅立體影像和初始視差圖進(jìn)行分層處理；其次，從金字塔影像的最頂層出發(fā)，將待匹配的兩幅相應(yīng)金字塔影像Ibs和Ims，根據(jù)初始視差圖Ds對(duì)像素點(diǎn)進(jìn)行互信息代價(jià)C(p,d)的遍歷計(jì)算；然后，選取16個(gè)方向路徑，并對(duì)每一像素點(diǎn)在每個(gè)方向路徑上運(yùn)用動(dòng)態(tài)規(guī)劃的思想進(jìn)行尋優(yōu)逼近，獲得最優(yōu)路徑代價(jià)Lr(p,d)；再將每一像素16個(gè)方向路徑代價(jià)Lr(p,d)進(jìn)行聚合得到聚合代價(jià)S(p,d)，選取最優(yōu)聚合代價(jià)對(duì)應(yīng)的視差d作為其最優(yōu)視差；最后，將視差傳遞到金字塔影像第二層，作為初始視差圖Ds繼續(xù)進(jìn)行上述過(guò)程，直到金字塔層遍歷完成為止，輸出最后的視差圖D。

圖1 算法流程圖

2.1 互信息匹配代價(jià)計(jì)算

假設(shè)基準(zhǔn)影像為Ib，待匹配影像為Im，基準(zhǔn)影像上像素點(diǎn)p的灰度值為Ibp，p在Im中的對(duì)應(yīng)像素點(diǎn)為q，像素灰度值為Imq。像素之間存在下述關(guān)系：q=ebm(p,d)，表示影像Ib中像素點(diǎn)p通過(guò)視差d映射到影像Im中的對(duì)應(yīng)像素點(diǎn)為q，則基于互信息的匹配代價(jià)CMI公式如下：

CMI(p,d)=miIbfD(Im)(Ibp,Imq)

(1)

其中，miIbfD(Im)(Ibp,Imq)為互信息，計(jì)算公式如下：

miI1I2(i,k)=hI1(i)+hI2(k)-hI1I2(i,k)

(2)

式中，hI1和hI2為兩幅影像像素點(diǎn)的獨(dú)立熵，hI1I2為兩幅影像對(duì)應(yīng)像素點(diǎn)的聯(lián)合熵。

對(duì)于比較好配準(zhǔn)的影像，一個(gè)影像的像素可以通過(guò)另一幅影像對(duì)應(yīng)像素很好地預(yù)測(cè)到。在立體匹配的過(guò)程中，一個(gè)影像需要根據(jù)視差圖D進(jìn)行映射來(lái)找到左右兩幅影像對(duì)應(yīng)的像素點(diǎn)，如I1=Ib和I2=fD(Im)，從而達(dá)到左右兩幅影像立體匹配的目的。兩幅影像對(duì)應(yīng)像素點(diǎn)的聯(lián)合熵hI1I2可以通過(guò)對(duì)應(yīng)灰度的聯(lián)合概率分布PI1I2計(jì)算得到。為了減少運(yùn)算量，先對(duì)其進(jìn)行一次二維高斯卷積(表示為?g(i,k))；取對(duì)數(shù)后，再對(duì)其進(jìn)行一次二維的卷積。本文算法中的卷積核取為5×5，由于0的對(duì)數(shù)沒(méi)有定義，我們把0元素的值用一個(gè)很小的數(shù)來(lái)替代，則計(jì)算公式如下：

hI1I2(i,k)=log(PI1I2(i,k)?g(i,k))?g(i,k)

(3)

式(2)中，兩幅影像像素點(diǎn)的獨(dú)立熵hI1和hI2可以仿照聯(lián)合熵hI1I2的方法求出。

2.2 16個(gè)方向代價(jià)聚合函數(shù)

假設(shè)r代表16個(gè)方向的任一方向，則每一方向路徑的每一像素點(diǎn)p的路徑代價(jià)計(jì)算公式如下：

(4)

其中，Lr表示沿r方向搜索的路徑代價(jià)能量函數(shù)。C(p,d)作為數(shù)據(jù)項(xiàng)，是像素點(diǎn)p視差為d時(shí)的基于互信息的匹配代價(jià)，min()函數(shù)部分作為平滑項(xiàng)。Lr(p,d)為像素點(diǎn)p視差為d時(shí)沿r方向搜索的路徑代價(jià)。式(4)中增加了路徑前一像素點(diǎn)p-r在視差范圍內(nèi)的最小代價(jià)。當(dāng)視差范圍變化為1時(shí)加上一個(gè)P1，當(dāng)視差范圍變化大于1時(shí)加上一個(gè)P2，其中P1、P2為不連續(xù)的懲罰項(xiàng)，二者為常數(shù)且P1

(5)

聚合代價(jià)S(p,d)表示為每個(gè)像素點(diǎn)p的16個(gè)方向路徑代價(jià)Lr(p,d)的和。視差d的取值則可以通過(guò)將16個(gè)一維搜索路徑聚合代價(jià)求和最小來(lái)獲取，即d=dminS(p,d)。

圖2 視差空間示意圖

如圖2所示，一個(gè)三維的視差空間，xy平面為影像的二維平面，平面中的每一點(diǎn)代表像素坐標(biāo)，縱軸d表示視差范圍，r表示搜索路徑的方向。沿著縱軸d從上往下看，空間中的每一節(jié)點(diǎn)存儲(chǔ)視差值為d時(shí)左圖像與右圖像對(duì)應(yīng)的互信息匹配代價(jià)C(p,d)。xy平面中展示了像素點(diǎn)p(x,y)視差確定過(guò)程中16個(gè)簡(jiǎn)單的路徑方向，方向路徑可以任意選擇。網(wǎng)格切面展示了像素點(diǎn) 兩個(gè)方向路徑視差的搜索過(guò)程，從切面可以看出，這兩個(gè)路徑不是簡(jiǎn)單的直線路徑。0～9為隨意給出的一個(gè)視差搜索范圍，這里只畫(huà)出了像素點(diǎn)p(x,y)兩個(gè)方向視差確定過(guò)程的最優(yōu)路徑縱切面。當(dāng)像素點(diǎn)p(x,y)的16個(gè)方向路徑代價(jià)的聚合代價(jià)最小時(shí)，對(duì)應(yīng)的視差d即為最優(yōu)視差。

在代價(jià)計(jì)算的過(guò)程中，圖像中每個(gè)像素被訪問(wèn)16次，這16次是從不同的方向開(kāi)始，通過(guò)這16個(gè)方向的一維搜索近似全局匹配，使本文算法比傳統(tǒng)動(dòng)態(tài)規(guī)劃立體匹配算法[7]、Birchfield和Tomasi的BT算法[8]在生成視差圖的精度上有很大的優(yōu)勢(shì)，相比于全局匹配方法在速度上也有一定的優(yōu)勢(shì)。通常情況下，搜索方向越多，越接近于全局匹配方法；得到的視差圖精度越高，視差值越精確。本文研究算法單從16個(gè)方向出發(fā)，也可以達(dá)到很好的效果。

2.3 視差優(yōu)化

為了避免生成的視差圖包含錯(cuò)誤的點(diǎn)位，需要對(duì)視差圖剔除錯(cuò)誤的視差點(diǎn)。本文采取的視差優(yōu)化方法是左右一致性檢查方法，具體過(guò)程如下：首先以左圖為基準(zhǔn)影像，右圖為待匹配影像，用本文的匹配算法生成視差圖Db；然后以右圖為基準(zhǔn)影像，左圖為待匹配影像進(jìn)行同樣的步驟，得到視差圖Dm；再根據(jù)左右一致性約束的要求，如以左圖像為基準(zhǔn)圖像進(jìn)行匹配，左圖像中的某個(gè)點(diǎn)對(duì)應(yīng)的匹配點(diǎn)是右圖像中的一個(gè)點(diǎn)，那么當(dāng)以右圖像為基準(zhǔn)圖像進(jìn)行匹配時(shí)，右圖像中的這個(gè)點(diǎn)對(duì)應(yīng)的匹配點(diǎn)也應(yīng)該是左圖像中的那個(gè)點(diǎn)。根據(jù)這一要求，將Db中的每一點(diǎn)的視差與它對(duì)應(yīng)的Dm中的視差進(jìn)行比較， 如果它們差值的絕對(duì)值小于等于1，我們就賦予Dbp的值；否則，視為無(wú)效的值Dinv。具體公式如下：

(6)

其中，q=ebm(p,Dbp)表示基準(zhǔn)影像Ib中像素點(diǎn)p通過(guò)視差Dbp映射到待匹配影像Im中對(duì)應(yīng)的像素點(diǎn)q。通過(guò)公式(6)進(jìn)行點(diǎn)對(duì)點(diǎn)的檢查，能剔除大部分誤匹配的點(diǎn)，使生成的視差圖更加精確。由于將誤匹配的點(diǎn)賦予無(wú)效值，因此生成的視差圖可能會(huì)有很多的空洞，這些空洞即為錯(cuò)誤的匹配點(diǎn)。本文通過(guò)內(nèi)插的方法填充空洞，使生成的視差圖連續(xù)緊密。

3 實(shí)驗(yàn)結(jié)果與分析

圖3 Tsukuba(左)和Sawtooth(右)

如圖3所示，Middlebury大學(xué)數(shù)據(jù)庫(kù)中提供的Tsukuba(視差范圍設(shè)為16個(gè)像素)和Sawtooth(視差范圍設(shè)為20個(gè)像素)兩組近景攝影測(cè)量立體像對(duì)數(shù)據(jù)，大小分別為384×288像素和434×380像素。其中Tsukuba圖像紋理豐富，存在遮擋現(xiàn)象，如人物雕像后面及臺(tái)燈下面大部分黑色陰影區(qū)域即為遮擋區(qū)域；Sawtooth圖像紋理貧乏，大部分地方為弱紋理區(qū)域。為了驗(yàn)證本文算法在遮擋區(qū)域和紋理貧乏區(qū)域密集匹配的適應(yīng)性以及準(zhǔn)確率，現(xiàn)分別采用SAD+DP(傳統(tǒng)的基于灰度差的絕對(duì)值和的動(dòng)態(tài)規(guī)劃方法)、BT+DP(Birchfield和Tomasi[6]提出的BT算法)和本文算法對(duì)兩組數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)。

對(duì)于密集匹配結(jié)果的準(zhǔn)確率，可以根據(jù)Scharstein[3]文獻(xiàn)中的錯(cuò)誤匹配率公式，通過(guò)將真實(shí)視差圖與三種算法得到的視差圖進(jìn)行計(jì)算，得到錯(cuò)誤匹配率，計(jì)算公式如下：

(7)

其中，N是像素總數(shù)，δd是判斷視差對(duì)錯(cuò)的閾值，通常經(jīng)驗(yàn)值為1.0，dC(x,y)為相應(yīng)算法得到的視差圖中像素點(diǎn)(x,y)處對(duì)應(yīng)的視差值，dT(x,y)為數(shù)據(jù)庫(kù)中提供的真實(shí)視差圖中像素點(diǎn)(x,y)處對(duì)應(yīng)的視差值。兩組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果如圖4和表1所示。

圖4 真實(shí)視差圖及各算法生成的視差圖

表1 各算法錯(cuò)誤率及效率統(tǒng)計(jì)表

數(shù)據(jù)算法SAD+DP算法BT+DP算法本文算法錯(cuò)誤率%用時(shí)s錯(cuò)誤率%用時(shí)s錯(cuò)誤率%用時(shí)sTsukuba6．583．1406．513．0472．863．437Sawtooth5．203．7344．413．8292．494．234

圖4為真實(shí)視差圖與各算法生成視差圖的結(jié)果。圖中分別展示了Tsukuba和Sawtooth兩組近景攝影測(cè)量立體像對(duì)數(shù)據(jù)在SAD+DP算法、BT+DP算法和本文算法下生成的視差圖。將各算法對(duì)Tsukuba和Sawtooth兩組數(shù)據(jù)生成的視差圖與真實(shí)視差圖對(duì)比可以看出，對(duì)于Tsukuba數(shù)據(jù)中人物雕像后面及臺(tái)燈下面大部分黑色陰影區(qū)域(遮擋區(qū)域)和Sawtooth數(shù)據(jù)中的紋理貧乏區(qū)域，如圖3所示，本文算法都能生成連續(xù)、緊密的視差圖。雖然對(duì)Tsukuba數(shù)據(jù)中的遮擋區(qū)域和Sawtooth數(shù)據(jù)中的紋理貧乏區(qū)域采用SAD+DP算法和BT+DP算法也能生成視差圖，但是SAD+DP算法與BT+DP算法生成的視差圖會(huì)產(chǎn)生條紋瑕疵和空洞瑕疵，這勢(shì)必會(huì)影響視差圖的精度，而在本文的算法下生成的視差圖不會(huì)產(chǎn)生條紋瑕疵和空洞瑕疵，視差圖連續(xù)、緊密與真實(shí)視差圖最為接近，這也表明本文算法生成的視差圖精度最高。所以對(duì)于存在遮擋區(qū)域和紋理貧乏的影像，本文算法較SAD+DP算法和BT+DP算法具有更好的適應(yīng)性。

表1為算法錯(cuò)誤率及效率統(tǒng)計(jì)表，由表1可以看出，本文算法在Tsukuba和Sawtooth兩組數(shù)據(jù)的匹配錯(cuò)誤率上明顯比SAD+DP算法和BT+DP算法低，說(shuō)明本文算法的匹配結(jié)果最好，精度最高。這也間接驗(yàn)證了本文算法生成的視差圖與真實(shí)視差圖最為接近這一結(jié)論。在匹配算法的效率上，本文算法的效率稍微低于其它兩種算法，這是因?yàn)楸疚乃惴ㄊ窃?6個(gè)方向的約束條件下實(shí)現(xiàn)的，約束條件的增加使本文算法的效率略有降低，但匹配精度卻有很大提高。

由圖4和表1實(shí)驗(yàn)結(jié)果可知，本文算法效率雖略有降低，但是相比SAD+DP算法和BT+DP算法，其在精度上卻具有很大的優(yōu)勢(shì)，可以在密集匹配中發(fā)揮更好的作用。

圖5 衛(wèi)星立體像對(duì)數(shù)據(jù)(左)及視差圖(右)

圖5(左)為一組衛(wèi)星立體像對(duì)數(shù)據(jù)，數(shù)據(jù)中存在紋理貧乏的平原地區(qū)和有遮擋現(xiàn)象的山地地區(qū)。如圖5(左)立體像對(duì)數(shù)據(jù)中的左下角部分大多數(shù)為平原地區(qū)，紋理貧乏，右上角部分大多數(shù)為山地地區(qū)，遮擋現(xiàn)象明顯。該部分利用衛(wèi)星遙感數(shù)據(jù)來(lái)驗(yàn)證本文算法的可行性，并通過(guò)目視的方法對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行主觀的評(píng)價(jià)。采用本文算法對(duì)圖5(左)的衛(wèi)星立體像對(duì)數(shù)據(jù)進(jìn)行密集匹配，得到的視差圖結(jié)果如圖5(右)所示。由圖5(右)視差圖結(jié)果可以看出，在紋理貧乏的平原地區(qū)或者有遮擋現(xiàn)象的山地地區(qū)，本文算法仍然具有不錯(cuò)的匹配結(jié)果，仍能夠生成連續(xù)緊密的視差圖，進(jìn)一步證明了本文算法對(duì)于紋理貧乏、有遮擋區(qū)域影像的匹配具有一定的適應(yīng)性。

4 結(jié) 論

本文研究了一種基于互信息的半全局密集立體匹配算法，并利用Middlebury大學(xué)數(shù)據(jù)庫(kù)中的影像數(shù)據(jù)對(duì)本文算法與動(dòng)態(tài)規(guī)劃立體匹配算法[7]、Birchfield和Tomasi的BT算法[8]進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文算法對(duì)紋理貧乏、有遮擋區(qū)域影像的匹配具有一定的適應(yīng)性，并有效解決了視差圖的條紋和空洞瑕疵，生成的視差圖更加精確稠密；最后利用實(shí)際衛(wèi)星遙感影像數(shù)據(jù)對(duì)本文算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果進(jìn)一步驗(yàn)證了本文算法對(duì)弱紋理、有遮擋區(qū)域影像匹配的可行性結(jié)論，充分表明本文算法在密集匹配中具有一定的應(yīng)用價(jià)值。

[1]Dhond U R, Aggarwal J K. Structure from stereo-a review[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1989, 19(6): 1489-1510.

[2]Koschan A. What is new in computational stereo since 1989: A survey on current stereo papers[M]. TechnischeUniversitat Berlin, Fachbereich 20, Informatik, 1993.

[3]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.

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

[5]RHEMANN C, H0SNI A, BLEYER M, et al. Fast cost-volume filtering for visual correspondence and beyond [C]. IEEE Conference on Computer Vision and Pattern Recognition, 2011.

[6]白明，莊嚴(yán)，王偉． 雙目立體匹配算法的研究與進(jìn)展[J]．控制與決策，2008，23( 7) : 721-729．

[7]VEKSLER O．Stereo correspondence by dynamic programming on a tree[C]. Proceedings of IEEE Computer Society Conf on Computer Vision and Pattern Recognition,San Die-go，USA，2005．

[8]Birchield S,Tomasi C. Depth discontinuities by pixel-to-pixel stereo[C]. Proceedings of the Sixth IEEE International Conference on Computer Vision, 1988.

[9]H. Hirschmuller. Accurate and efficient stereo processing by semi-global matching and mutual information[C]. in IEEE Conference on Computer Vision and Pattern Recognition, San Diego, USA,2005.

Semi-Global Dense Stereo Matching Algorithm Based on Mutual Information

Zhang Guibin1,3, Gong Danchao2, Wang Renli1, Wang Yi3

1.Shandong Provincial Key Laboratory of Geomatics and Digital Technology, Shandong University of Science and Technology, Qingdao 266590,China 2.Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, China 3.Aerors Inc., Xi’an 710100,China

As the dense matching plays an important role in 3D reconstruction, the paper studies a semi-global dense stereo matching algorithm based on the mutual information. It uses the mutual information of corresponding pixels between the stereo pairs as matching cost, and does approximate global matching through one dimensional search of sixteen directions and determine the corresponding relation between the pixels of the stereo pairs through the pixelwise matching supported by pyramid passing, dynamic programming and disparity refining strategies. The experiment results show that the algorithm can still generate precise and dense disparity image which has poor texture and occlusion area image.

mutual information；stereo matching；dynamic programming；disparity Image

2015-01-27。

張桂濱(1988—)，男，碩士研究生，主要從事遙感技術(shù)與應(yīng)用以及圖像處理方面的研究。

P231

A