于 英， 楊靖宇， 張永生， 薛 武

（1.信息工程大學(xué)測繪學(xué)院，河南鄭州450052； 2.中國人民解放軍61733部隊(duì)，河南鄭州 450052；3.江西省數(shù)字國土重點(diǎn)實(shí)驗(yàn)室，江西撫州 344000）

一種適應(yīng)無人機(jī)平臺的快速立體匹配方法

于 英1，3， 楊靖宇2， 張永生1， 薛 武1，3

（1.信息工程大學(xué)測繪學(xué)院，河南鄭州450052； 2.中國人民解放軍61733部隊(duì)，河南鄭州 450052；3.江西省數(shù)字國土重點(diǎn)實(shí)驗(yàn)室，江西撫州 344000）

設(shè)計(jì)了一種高質(zhì)量和快速的立體匹配方法，首先在粗分辨率的影像上獲取立體影像的重疊區(qū)域和初始視差值，而后采用互信息作為匹配測度并采用一種通過一維路徑聚合的全局優(yōu)化方法得到精確的視差值。匹配方法采用圖形處理器進(jìn)行了加速，得到了很好的加速比。實(shí)驗(yàn)結(jié)果表明了該匹配方法的正確性和高效率性。

計(jì)量學(xué)；無人機(jī)；立體匹配；互信息；半全局；圖形處理器并行

1 引 言

無人機(jī)低空攝影具有快速、靈活、低成本、高影像分辨率等特點(diǎn)，可在云下遙感的能力彌補(bǔ)了衛(wèi)星光學(xué)遙感和普通航空攝影經(jīng)常受云層遮擋獲取不到影像的缺陷，相應(yīng)的圖像處理技術(shù)也得到了廣泛的關(guān)注和重視。無人機(jī)圖像處理中核心的技術(shù)之一是影像的快速立體匹配技術(shù)，因此研究一種適合無人機(jī)平臺的快速立體匹配方法很有必要［1，2］。

本文研究的匹配方法要求可以生成稠密的視差圖，因此特指基于灰度的匹配算法?；诨叶鹊钠ヅ渌惴ㄓ挚煞譃榫植績?yōu)化算法和全局優(yōu)化算法。局部優(yōu)化算法是依據(jù)匹配測度，計(jì)算過程比較簡單，但匹配的可靠性比較差。而全局優(yōu)化算法則是通過選用一個全局能量函數(shù)，并最小化該函數(shù)來得到更為準(zhǔn)確的視差圖［3］。圖割法算法和信任傳播算法是目前公認(rèn)的效果最好的全局優(yōu)化算法，可以獲取高精度的稠密視差圖，但是這兩種算法的時(shí)間復(fù)雜度比較高，計(jì)算效率低［5～9］。德國宇航中心提出并采用的半全局匹配算法，不僅可以得到與圖割法、置信傳播法相媲美的處理結(jié)果，執(zhí)行效率遠(yuǎn)高于這些算法，且半全局匹配方法具有較高的邊緣保持性能［10］。全局匹配算法保證了匹配的穩(wěn)定性和匹配的精度，但匹配的速度就難以保證。多核CPU和多核圖形處理器（GPU：Graphic Processing Unit）的出現(xiàn)意味著并行系統(tǒng)已逐漸成為主流的處理器芯片，特別是GPU在處理能力和存儲器帶寬上相對CPU有明顯的優(yōu)勢，使得GPU-CPU協(xié)同處理架構(gòu)成為優(yōu)異的高速計(jì)算平臺［11］，本文的匹配算法將采用并行的處理方式提高匹配的實(shí)時(shí)性以適應(yīng)無人機(jī)平臺對匹配速度的要求。

2 匹配算法

由于無人機(jī)上固定基線的立體相機(jī)的外方位元素精確已知，因此可以很容易地得到核線影像，這樣本文匹配算法輸入的影像均是核線影像。如圖1所示，本文匹配方法采用降采樣的方法生成粗分辨率的影像，在粗分辨率的影像上采用灰度相關(guān)匹配的方法計(jì)算影像的重疊度和初始視差值。后續(xù)的匹配只在重疊區(qū)域中進(jìn)行，這樣不僅使計(jì)算量成倍地較少，還有效地防止了圖像非重疊區(qū)域中的信息對算法的干擾，提高了算法的精度；在后面精確的同名點(diǎn)搜索的過程中，搜索范圍僅需要在初始視差值一定范圍內(nèi)進(jìn)行，可以提高匹配的效率。然后，在原始分辨率的影像上按行計(jì)算匹配代價(jià)計(jì)算并采用半全局匹配的方法在利用多個方向的一維平滑約束來近似一個二維平滑約束得到最優(yōu)的視差值，其中在匹配代價(jià)計(jì)算和匹配代價(jià)聚合采用了GPU并行計(jì)算進(jìn)行了加速。最后，進(jìn)行左右一致性檢查和中值濾波，確保匹配結(jié)果的唯一性和誤差的剔除。

圖1 本文匹配算法計(jì)算流程圖

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

2幅圖像的互信息可以定義為：

式中：H（A）和H（B）分別為圖像A和B的平均信息量，而H（A，B）則是它們的相關(guān)平均信息量。圖像A和B的平均信息量和相關(guān)平均信息量為：

式中：ρA（a）和ρB（b）分別為圖像A中具有灰度值a的概率密度函數(shù)和圖像B中具有灰度值b的概率密度函數(shù)；ρA，B（a，b）為圖像A和B的聯(lián)合概率密度函數(shù)，它們可以由2幅圖像A和B的聯(lián)合直方圖計(jì)算得到。

互信息并不直接依賴于灰度值來衡量不同圖像的一致程度，而是依賴于它們在每幅圖像中各自發(fā)生的概率和兩幅圖像組合產(chǎn)生的聯(lián)合發(fā)生概率.因此它對灰度改變或一對一的灰度變換不敏感，能同時(shí)處理積極的和消極的圖像灰度相互關(guān)系［3］。

2.2 匹配代價(jià)聚合

為由于防止噪聲引起的匹配代價(jià)計(jì)算誤差以及由此引起的深度污染擴(kuò)散，將引進(jìn)一個額外的約束加入到能量函數(shù)中：

式中：第1項(xiàng)表示所有像素點(diǎn)的匹配代價(jià)之和；第2項(xiàng)和第3項(xiàng)分別利用系數(shù)P1和P2對像素點(diǎn)p與其鄰域內(nèi)的像素點(diǎn)深度差存在的較小變化和較大變化2種情況進(jìn)行了懲罰，即平滑約束，顯然P1〈P2。T為判斷函數(shù)，當(dāng)且僅當(dāng)其參數(shù)為真時(shí)函數(shù)值為1，否則為0。

對于二維圖像，尋找式（3）的全局最小值已被證明是NP完全問題（Non-deterministic Polynomial：NP，多項(xiàng)式復(fù)雜程度的非確定性問題），而一維路徑上的能量最小化則可以使用動態(tài)規(guī)劃算法高效實(shí)現(xiàn)，但經(jīng)典的動態(tài)規(guī)劃算法只能沿著掃描行進(jìn)行一維優(yōu)化，使得匹配結(jié)果產(chǎn)生拖尾效應(yīng)，因此在匹配算法中利用8個（或16個）方向上的一維平滑約束來近似擬合一個二維平滑約束。

在每一條路徑L上依據(jù)動態(tài)規(guī)劃的思想按照后面式（4）、式（5）進(jìn)行計(jì)算，如圖2所示。

式（4）中的第1項(xiàng)表示對像素點(diǎn)p賦予深度d的匹配代價(jià)；第2項(xiàng)是當(dāng)前路徑上p的上一個點(diǎn)p-r包含了懲罰系數(shù)的最小匹配代價(jià)；第3項(xiàng)則對最優(yōu)路徑的產(chǎn)生沒有施加影響，加入這一項(xiàng)的目的僅僅是為了防止L過大，使得L≤Cmax＋P2。其中r為路徑；Cmax為最大匹配代價(jià)值；P2為視呈跳變懲罰值。

將各個方向上的匹配代價(jià)相加形成為總的匹配代價(jià)，如式（5）、圖3所示。

圖2 最小匹配代價(jià)路徑Lr（p，d）

圖3 8個方向上的匹配代價(jià)聚合

在通過匹配代價(jià)聚合更新S（p，d）得到所有像點(diǎn)對的匹配代價(jià)后，視差圖的確定就是一個簡單的選擇過程：基準(zhǔn)圖像上的每個像點(diǎn)p的視差dp＝min［S（p，d）］，即對應(yīng)的總匹配代價(jià)最小的視差值；而參考圖像Im中的每個像素點(diǎn)q對應(yīng)的視差dm＝min［S（emb（q，d），d］。通過比較Db和Dm（Db和Dm分別為判斷遮擋和錯誤匹配的依據(jù)），即進(jìn)行一致性檢查，式（7）。若二者差別在閾值之內(nèi)，則認(rèn)為匹配正確；否則若兩者差別過大則不接受算法輸出結(jié)果，并將該點(diǎn)標(biāo)識為誤匹配點(diǎn)Dinv。綜上所述，匹配算法通過對視差值的不同變化施以相應(yīng)的懲罰系數(shù)保證了平滑性約束，通過8或16個方向的一維路徑動態(tài)規(guī)劃來擬合二維平滑約束使得結(jié)果更加可靠，對噪聲表現(xiàn)出一定的魯棒性［10］。

2.3 GPU并行處理

在全局優(yōu)化匹配算法的匹配代價(jià)立方體生成過程中，每個立方體元素的計(jì)算過程完全獨(dú)立，具有很高的并行性，且每一層的視差空間圖像的生成又存在著大量的局部性重復(fù)訪問，為提高GPU的計(jì)算效率，需要對影像進(jìn)行紋理存儲器優(yōu)化和共享存儲器優(yōu)化。

而在匹配代價(jià)的聚合過程中，每個像素的計(jì)算過程不再是相互獨(dú)立的，而是需要利用當(dāng)前路徑上前一像點(diǎn)的匹配代價(jià)，這使得傳統(tǒng)的按照對圖像矩陣進(jìn)行分塊的模式不再適用，而應(yīng)該按照掃描行（或列）對匹配代價(jià)立方體進(jìn)行分塊。如圖4所示，在計(jì)算從上到下3個方向的Lr（p，d）時(shí)，圖像的每一行被分割為N＝Iw／Ap段，每一段由一個包含Ap×Rd個線程的線程塊來進(jìn)行計(jì)算，Iw為掃描寬度，Ap為計(jì)算過程中每個線程要循環(huán)執(zhí)行Ll（掃描行數(shù)）次來掃描整幅圖像。

圖4 匹配代價(jià)聚合的GPU并行化

此外為進(jìn)一步加快處理速度，在一次掃描過程中，同時(shí)計(jì)算多個方向的匹配代價(jià)聚合，如圖5所示僅需要掃描兩遍（從上而下和從下而上）即可對多個方向的匹配代價(jià)進(jìn)行聚合。同時(shí)匹配代價(jià)立方體的中間計(jì)算子塊被直接寫入到全局存儲空間，并在共享存儲空間內(nèi)的保留其副本數(shù)據(jù)，避免在下一行聚合過程中需要這些數(shù)據(jù)時(shí)，再從訪問緩慢的全局存儲空間讀取數(shù)據(jù)。

在通過匹配代價(jià)聚合更新S（p，d）后，就可以簡單的最小值選擇來生成視差圖。

3 實(shí) 驗(yàn)

圖5 匹配代價(jià)聚合的快速掃描方法

為驗(yàn)證本文匹配算法的正確性，本文以UCD航空數(shù)字相機(jī)獲取的湖北寶應(yīng)地區(qū)的大重疊度面陣影像進(jìn)行實(shí)驗(yàn)，如圖6所示，影像大小為3000× 3000像素，像素大小為9.0μm，焦距為101.4000 mm。

匹配質(zhì)量實(shí)驗(yàn)：分別采用匹配窗口大小為5× 5的相關(guān)系數(shù)法和本文方法對上面的核線影像進(jìn)行了匹配，匹配結(jié)果如圖7所示，可以看出本文方法得到的匹配視差圖的質(zhì)量明顯高于相關(guān)系數(shù)法。

圖6 本文所用核線影像

圖7 匹配結(jié)果視差圖

GPU匹配速度實(shí)驗(yàn)：實(shí)驗(yàn)中采用的GPU為NVIDIA Quadro Fx580顯卡，CPU為Inter（R）Core--（TM）i5 2.8GHz×4核，系統(tǒng)內(nèi)存為4GB。分別設(shè)置左右視差的搜索范圍為128、256像素，在左影像上選擇不同大小的多個待匹配的區(qū)域，統(tǒng)計(jì)相應(yīng)CPU與GPU處理時(shí)間（ms）和加速效率（表1）。

4 結(jié) 論

針對無人機(jī)立體測繪的實(shí)際需求，設(shè)計(jì)了一種高效的立體影像匹配方法，實(shí)驗(yàn)結(jié)果表明該匹配方法在匹配質(zhì)量和匹配速度上均取得了滿意的結(jié)果。實(shí)現(xiàn)了2張像片的全局并行快速的匹配，后續(xù)將會研究實(shí)現(xiàn)序列圖像的快速匹配方法（多視匹配），以更好地適應(yīng)無人機(jī)大批量影像數(shù)據(jù)快速處理的需求。

表1 CPU與GPU處理時(shí)間及加速比

［1］ 吳正鵬.無人機(jī)載雙相機(jī)低空遙感系統(tǒng)應(yīng)用初探［J］.城市勘測，2011，（1）：76－80.

［2］ 胡堃.基于無人機(jī)遙感平臺的震后災(zāi)情監(jiān)測系統(tǒng)［J］.科學(xué)探索與知識創(chuàng)新，2009，（1）：100－101.

［3］ 王珺.計(jì)算機(jī)立體視覺算法研究與實(shí)現(xiàn)［D］.大連：大連理工大學(xué)，2009.

［4］ 周文暉.一種魯棒的基于互信息的實(shí)時(shí)立體匹配算法［J］.遙感技術(shù)學(xué)報(bào)，2006，19（4）：1243－1249.

［5］ Boykow Y，Veksler O，Zabih R.Fastapproximate energy minimization via graph cuts［J］.IEEETransactionson PatternAnalysisandMachineIntelligence，2001，23（11）：1222－1239.

［6］ Sun J，Zheng N N，Shum H Y.Stereo matching using belief propagation［J］.IEEETranscationsonPattern AnalysisandMachineIntelligence，2003，25：787－800.

［7］ Felzenszwalb P F，Huttenlocher D P.Efficient Belief Propagation for Early Vision［J］.InternationalJournalof ComputerVision，2006.

［8］ Forstmann S，Ohya J，Kanou Y，etal.Real-time stereo by using dynamic programming［C］／／Proc of CVPR Workshop on Real-time 3D Sensors and Their Use，2004.

［9］ Gong M L，Yang Y H.Fast stereo matching using reliability-based dynamic programming and consistency constraints［J］.ProcedingsoftheNithIEEEInternational ConferenceonComputerVision，2003，（1）：610－617.

［10］ Egnal G.Mutual information as a stereo correspondence measure［R］.Comp and Inf Science，U of Pennsylvania，2000.

［11］ 張舒，褶艷利.GPU高性能運(yùn)算之CUDA［M］.北京：中國水利水電出版社，2009.

A Quick Stereo Matching Algorithm for Helicopter Platform

YU Ying1，3， YANG Jing-yu2， ZHANG Yong-sheng3， XUEWu1，3
（1.Institute of Surveying and Mapping，Information Engineering University，Zhengzhou，Henan 450052，China；
2.Troops 61733，The Chinese People's Liberation Army，Zhengzhou，Henan 450052，China；
3.Jiangxi Province Key Lab for Digital Land，F(xiàn)uzhou，Jiangxi344000，China）

A stereo matching algorithm which is good matching quality and quick is designed.Firstly，an initial disparity and overlap based on coarse-resolution images is got.Then amutual information is used asmatching-measure and through one dimension path aggregation the accurate disparity will be got.Thematching algorithm uses GPU to accelerate the process，and a good acceleration ratio will be achieved.Finally，the experiment prove it right and efficient.

Metrology；Helicopter；Stereo matching；Mutual information；Semi-global；Graphic processing unit parallel

TB96

A

1000-1158（2014）02-0143-04

10．3969／j．issn．1000-1158．2014．02．10

2012-03-05；

2012-08-13

江西省數(shù)字國土重點(diǎn)實(shí)驗(yàn)室開放基金（DLLJ201303）

于英（1985－），男，河南鄭州人，信息工程大學(xué)在讀博士研究生，主要研究方向?yàn)榛谝苿悠脚_的視頻圖像快速處理方法。yuying5559104＠163.com