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

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

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

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

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

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

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

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

1 引 言

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

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

2 匹配算法

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

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

2.2 匹配代價(jià)聚合

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

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

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

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

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

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

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

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

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

2.3 GPU并行處理

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

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

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

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

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

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ù)法和本文方法對(duì)上面的核線影像進(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像素，在左影像上選擇不同大小的多個(gè)待匹配的區(qū)域，統(tǒng)計(jì)相應(yīng)CPU與GPU處理時(shí)間（ms）和加速效率（表1）。

4 結(jié) 論

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

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

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

［2］ 胡堃.基于無(wú)人機(jī)遙感平臺(tái)的震后災(zāi)情監(jiān)測(cè)系統(tǒng)［J］.科學(xué)探索與知識(shí)創(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］.北京：中國(guó)水利水電出版社，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ù)字國(guó)土重點(diǎn)實(shí)驗(yàn)室開放基金（DLLJ201303）

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