半分辨率半路徑數(shù)量的半全局匹配方法*

于　英　張永生　薛　武

(1.信息工程大學(xué),鄭州 450052；2.江西省數(shù)字國土重點實驗室,撫州 344000)

0　引言

基于半全局的影像逐像素密集匹配方法，因具有匹配精度高、物體邊緣匹配效果好、對圖像亮度差異適應(yīng)性良好以及同等匹配精度條件下匹配速度快等諸多優(yōu)點，得到了多方面的關(guān)注。該方法采用多個一維路徑聚合的優(yōu)化策略容易在FPGA和GPU 實現(xiàn)并行計算，可以大幅度的提高匹配的速度[1-3]。但在基于視覺驅(qū)動的導(dǎo)彈匹配導(dǎo)航、無人機動態(tài)準(zhǔn)實時測繪[4]等對實時性要求高的航空場合，特別需要指出的是無人機動態(tài)準(zhǔn)實時測繪得到的影像數(shù)量多并且影像分辨率高，對影像的匹配速度提出了極高的要求，半全局匹配的速度仍達不到要求。

半全局匹配算法原文作者指出為實現(xiàn)較好的匹配效果，代價聚集路徑的數(shù)量要為16個(最少8個)，但作者并沒有說明原因。顯然代價聚集路徑的數(shù)量的減少，可以顯著提高匹配的速度，但造成的匹配結(jié)果質(zhì)量的降低程度需要進行研究分析。文獻[2]嘗試采用4條路徑進行代價聚集，但沒有認真考慮由此帶來的匹配質(zhì)量降低問題。文獻[5]研究了半全局匹配聚集路徑數(shù)量衰減與匹配質(zhì)量損失的關(guān)系問題,但驗證數(shù)據(jù)均采用地面數(shù)據(jù)，驗證也不夠充分。本文的研究旨在以無人機高分辨率影像為數(shù)據(jù)基礎(chǔ)，系統(tǒng)性的研究路徑數(shù)量衰減對匹配質(zhì)量影響。鑒于原始影像的分辨率較高，更進一步研究了半全局匹配方法進行隔點匹配加速方法，這幾乎可以提高一倍的匹配速度。

1　半全局匹配原理

半全局優(yōu)化匹配算法的原理如式(1)所示：

(1)

式中，第一項表示所有像素點的匹配代價之和；第二項和第三項分別利用系數(shù)P1和P2對像素點p與其鄰域內(nèi)的像素點深度差存在的較小變化和較大變化兩種情況進行了懲罰，即平滑約束，顯然P1

附加平滑約束并通過能量函數(shù)最小化的方法是全局匹配的基本思想，半全局匹配方法實際使用時將二維圖像NP(Nondeterministic Polynomial)問題的完全解問題轉(zhuǎn)化為通過多個方向的一維平滑約束來近似一個二維平滑約束的方法，這極大的減少了計算量。圖1中的左圖為全局匹配的無向圖，右圖為半全局匹配的無向圖，實線為匹配路徑，線段間的節(jié)點為匹配路徑經(jīng)過的像素點，其中S為源點、T為終點。半全局匹配的路徑相比全局匹配的路徑要少得很多，因此得名。經(jīng)典的動態(tài)規(guī)劃算法只能沿著掃描行進行一維優(yōu)化，使得匹配結(jié)果產(chǎn)生拖尾效應(yīng)，在匹配算法中利用8個(或16個)方向上的一維平滑約束來近似擬合一個二維平滑約束。

圖1　全局匹配與半全局匹配的無向圖對比

半全局匹配算法在每一條路徑上依據(jù)動態(tài)規(guī)劃的思想按照式(2)和式(3)進行計算，式中的第一項表示對像素點p賦予深度d的匹配代價；第二項是當(dāng)前路徑上p的上一個點沿著p-r方向包含了懲罰系數(shù)的最小匹配代價，如圖2所示；第三項則對最優(yōu)路徑的產(chǎn)生沒有施加影響，加入這一項的目的僅僅是為了防止L過大超出計算機字節(jié)限制。

(2)

Lr(p0,d)=c(p0,d)

(3)

圖2　p-r方向包含了懲罰系數(shù)的最小匹配代價

然后，將各個方向上(通常為8個方向)的匹配代價相加形成為總的匹配代價，如公式(4)，在最大視差值范圍內(nèi)求取S(p,d)的最小值對應(yīng)的視差值dbest即為匹配的結(jié)果。

(4)

2　路徑優(yōu)化整合及實驗

圖3　8路徑方向表示聚集示意圖

圖4　半全局單方向匹配結(jié)果

圖5　兩方向匹配結(jié)果

圖6為4個路徑方向(半路徑)與8個路徑方向(全路徑)的匹配結(jié)果圖，兩組匹配結(jié)果幾乎并無差異，因此選用4個路徑方向進行半全局匹配已經(jīng)可以滿足需求，即只采用ScanA就可以得到良好的匹配結(jié)果與匹配速度，此外在匹配執(zhí)行過程中只需要存儲兩行的代價計算結(jié)果，極大減少內(nèi)存的使用量。

圖6　半路徑與全路徑匹配結(jié)果

圖7　隔點匹配中路徑代價值臨近拷貝示意圖

3　半分辨率匹配策略及實驗

圖8　隔點匹配效果圖

通過分析半全局的匹配結(jié)果，發(fā)現(xiàn)在圖像中一個物體內(nèi)部相鄰元素的視差值基本上是不變的，也就是說可以采用隔點匹配的方法提高計算速度和內(nèi)存資源。如圖7所示，本文將半全局匹配方法僅作用在偶數(shù)像素上，對于奇數(shù)像素采用最簡單的代價值拷貝的方式。在匹配路徑數(shù)量上選擇了4條路徑，因為2條路徑和8條路徑與此并無特別之處。從圖8的匹配結(jié)果可見，不進行拷貝方式的隔點匹配得到的視差圖比較稀疏，而隔點匹配并拷貝的方式得到的視差圖效果與圖6中半路徑的匹配結(jié)果基本一致。

4　結(jié)論

本文以高分辨率無人機影像為數(shù)據(jù)基礎(chǔ)，研究了半全局匹配與路徑的關(guān)系問題和半分辨率匹配的問題，研究結(jié)果表明：

1)兩條路徑的半全局匹配可以較好的克服單路徑匹配的條紋效應(yīng)和微移動效應(yīng)，對匹配精度要求不高的可以使用。

2)半路徑(4條路徑)的匹配與全路徑(8條路徑)的匹配結(jié)果相當(dāng)，但匹配速度得到了提高并且內(nèi)存使用量極大減少。

3)半分辨率匹配的方式即隔點匹配臨近拷貝的方式得到了匹配結(jié)果與半路徑的匹配結(jié)果基本一致，但計算量幾乎減少了一半，極大提高了匹配的速度。

[1]S.K.Gehrig，F(xiàn).Eberli，and T.Meyer.A real-time low-power stereo vision engine using semi-global matching.Proc.IEEE Int.Conf.on Computer Vision (ICCV)，5815:134-143，2009

[2]I.Ernst and H.Hirschmuller.Mutual information based semi-global stereo matching on the gpu[C].In ISVC ’08: Proceedings of the 4th International Symposium on Advances in Visual Computing，pages： 228-239，2008

[3]胡亮,段發(fā)階,丁克勤,葉聲華.基于線陣CCD鋼板表面缺陷在線檢測系統(tǒng)的研究[J].計量學(xué)報，2005,26(3)

[4]張永生.現(xiàn)場直播式地理空間信息服務(wù)的構(gòu)思與體系[J].測繪學(xué)報.2012,40(1)

[5]Hermann S，Morales S，Klette R.Half-resolution semi-global stereo matching[C].Intelligent Vehicles Symposium (IV)，IEEE，2011: 201-206

[6]Y.Ohta，T.Kanade.Stereo by two-level dynamic programming[C].Proc.Int.Joint Conf.Articial Intelligence 2 (1985)：1120-1126