于　英　張永生　薛　武

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

0　引言

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

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

1　半全局匹配原理

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

(1)

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

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

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

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

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

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

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

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

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

圖7　隔點(diǎn)匹配中路徑代價值臨近拷貝示意圖

3　半分辨率匹配策略及實(shí)驗(yàn)

圖8　隔點(diǎn)匹配效果圖

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

4　結(jié)論

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

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

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

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

[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].計(jì)量學(xué)報(bào)，2005,26(3)

[4]張永生.現(xiàn)場直播式地理空間信息服務(wù)的構(gòu)思與體系[J].測繪學(xué)報(bào).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