基于MPI的高效半全局約束密集匹配方法

王歡歡，鄒崢嶸，張?jiān)粕?/p>

（中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長沙410083）

面對(duì)突然發(fā)生的自然災(zāi)害，快速準(zhǔn)確獲取災(zāi)害現(xiàn)場的災(zāi)區(qū)范圍、房屋倒塌、道路破壞等情況是災(zāi)害評(píng)估和救災(zāi)搶險(xiǎn)的關(guān)鍵。災(zāi)害現(xiàn)場的地形地物高效三維重建是快速獲取災(zāi)情信息的重要手段之一，也是正射影像糾正的先決條件。快速的正射影像獲取可以為決策者提供最直觀的第一手資料，從而提高災(zāi)害應(yīng)急響應(yīng)的效率［1］。無人機(jī)等低空遙感系統(tǒng)能快速獲取高分辨率和高重疊的低空影像［2］，因此在災(zāi)害應(yīng)急響應(yīng)中引起了廣泛的關(guān)注。從汶川地震到舟曲泥石流等自然災(zāi)害的應(yīng)急救災(zāi)工作中可以感受到，利用無人飛機(jī)等低空平臺(tái)獲取的低空影像正在成為救災(zāi)測繪應(yīng)急保障的重要手段。

面對(duì)災(zāi)情，時(shí)間就是生命。如何快速、高效地處理大量的低空影像獲取災(zāi)區(qū)信息尤為重要。影像密集匹配技術(shù)是三維重建的關(guān)鍵環(huán)節(jié)，也是極其耗時(shí)的環(huán)節(jié)。影像匹配算法大體上可以分為局部匹配算法和全局匹配算法。局部匹配算法較為簡單快速，但因?qū)υ肼暶舾小⑵ヅ浣Y(jié)果密度較低等難以滿足三維重建要求。全局匹配算法生成視差圖密集可靠，但卻需要付出高昂的計(jì)算代價(jià)，計(jì)算時(shí)間過長。Hirsch müller提出一種半全局約束立體匹配算法（SGM）［3］，通過在待匹配像素點(diǎn)多個(gè)方向上作動(dòng)態(tài)規(guī)劃來近似圖像二維全局優(yōu)化，確定視差圖。該算法能夠獲取理想的視差圖，且在計(jì)算時(shí)間上已經(jīng)有較大改善，但仍然不能很好滿足面對(duì)災(zāi)害的海量數(shù)據(jù)的應(yīng)急響應(yīng)的需求。采用并行計(jì)算，協(xié)同多臺(tái)處理器同時(shí)處理海量數(shù)據(jù)可以有效縮短計(jì)算時(shí)間提高效率［4］，因此本文提出采用 MPI（Message Passing Interface）進(jìn)行高效半全局約束密集匹配。

1 串行算法流程

圖1給出了本文的串行算法處理流程，主要分為數(shù)據(jù)輸入、自適應(yīng)立體像對(duì)選擇、核線糾正、密集匹配、空間前方交會(huì)、輸出三維點(diǎn)云等過程。

圖1 基于SGM密集匹配串行算法流程

1．1 自適應(yīng)立體像對(duì)選擇

基于自動(dòng)空三結(jié)果獲取的同名點(diǎn)，計(jì)算兩張影像之間的單應(yīng)性矩陣，求得影像與影像之間的重疊率。顧及重疊率和基高比，對(duì)于每一個(gè)區(qū)域主要選擇一個(gè)立體像對(duì)，在保證結(jié)果沒有空洞的基礎(chǔ)上，盡可能少的選擇立體像對(duì)，以達(dá)到減少冗余計(jì)算的目的。

1．2 半全局約束立體匹配算法（SGM）

1．2．1 匹配代價(jià)

匹配代價(jià)是衡量立體像對(duì)中左右影像上任意兩個(gè)像素點(diǎn)之間的相似程度，匹配代價(jià)越小，則匹配程度越高。參數(shù)變換匹配代價(jià)直接比較像點(diǎn)的灰度信息，計(jì)算相似性測度。本文采用絕對(duì)值差和（Su m of Absolute Differences，SAD）計(jì)算匹配代價(jià)。假設(shè)立體像對(duì)已校正，則對(duì)于左影像上任意一點(diǎn)P，其在右影像上的同名像點(diǎn)為P－d（其中d為視差），則

其中，IL（P），IR（P－d）為以點(diǎn)P為中心的窗口Np內(nèi)灰度均值。

1．2．2 匹配代價(jià)聚合

SGM算法利用匹配代價(jià)和動(dòng)態(tài)規(guī)劃的概念，以立體像對(duì)左影像中一條水平像素系列為基準(zhǔn)，向右影像中相同水平位置的像素系列進(jìn)行比對(duì)，再通過多個(gè)一維方向的動(dòng)態(tài)規(guī)劃影像匹配模擬二維影像的全局匹配最優(yōu)化［5］。為了顧及場景中的傾斜平面、深度斷裂和相似區(qū)域等，SGM算法在匹配代價(jià)聚合中引入平滑約束，其能量函數(shù)為

于是，可將立體匹配中視差圖D的確定轉(zhuǎn)換為求解式（2）全局最優(yōu)的過程。在二維圖像上的全局優(yōu)化已被證明是NP完全問題，通常采用一些全局優(yōu)化算法來近似求解，如圖割、置信度傳播等。SGM算法在待匹配像素P處沿著多個(gè)方向上作動(dòng)態(tài)規(guī)劃，采用多方向匹配代價(jià)聚合策略，實(shí)現(xiàn)二維聚合，一般選8個(gè)方向足夠，如圖2所示。由于在不同的搜索方向上，并不一定都滿足核線約束，則順序性約束一般難以滿足，相比于傳統(tǒng)的動(dòng)態(tài)規(guī)劃算法，SGM算法采用的優(yōu)化算法更類似于掃描線最優(yōu)算法。

對(duì)于像素P，在r方向的累積匹配代價(jià)定義為

式（3）中最后一項(xiàng)是為了防止累積匹配過大而減去一個(gè)固定值，對(duì)后續(xù)最優(yōu)路徑?jīng)]有影響。最后，將各個(gè)路徑上的匹配代價(jià)相加即為該點(diǎn)總的匹配代價(jià)，實(shí)現(xiàn)匹配代價(jià)聚合

其中S（p，d）為聚合匹配代價(jià)，Lr為路徑代價(jià)聚合。

圖2 匹配代價(jià)聚合

1．2．3 視差計(jì)算和優(yōu)化

計(jì)算所有像素點(diǎn)聚合匹配代價(jià)S（p，d）之后，一般采用勝者為王算法（WTA），即選取灰度相關(guān)性最大的匹配點(diǎn)作為代價(jià)比對(duì)的結(jié)果，生成左右影像的視差圖。然后對(duì)視差圖進(jìn)行中值濾波去除突變點(diǎn)。后續(xù)采用線性插值法填補(bǔ)視差圖空洞，進(jìn)行視差優(yōu)化，生成最終的視差圖。

2 基于MPI的并行集群平臺(tái)的搭建

2．1 并行計(jì)算

并行計(jì)算（Parallel Co mputing）是相對(duì)串行計(jì)算而言，指將一個(gè)任務(wù)分解為多個(gè)子任務(wù)，各處理器之間相互通訊、協(xié)同執(zhí)行，進(jìn)而加快求解速度和求解大規(guī)模問題。并行計(jì)算的主要目的是節(jié)省大型復(fù)雜問題或海量數(shù)據(jù)的處理時(shí)間［6］，整合“廉價(jià)”的計(jì)算資源組建并行計(jì)算系統(tǒng)克服單機(jī)計(jì)算性能瓶頸。根據(jù)并行粒度可以將并行計(jì)算分為粗粒度并行、中粒度并行和細(xì)粒度并行3種［7］。粗粒度并行是指對(duì)某個(gè)過程進(jìn)行整體并行，比如MPI。中粒度并行是指對(duì)計(jì)算過程中的某個(gè)循環(huán)過程進(jìn)行多核計(jì)算，比如Open MP。細(xì)粒度是指對(duì)計(jì)算進(jìn)行指令級(jí)加速，比如CUDA。MPI并行程序開發(fā)常用的模式有主從模式和對(duì)等模式。對(duì)等模式常用于共享式主存的并行計(jì)算平臺(tái)，分布式主存的并行計(jì)算平臺(tái)較多使用主從模式。主從模式中，主進(jìn)程負(fù)責(zé)輸入輸出數(shù)據(jù)、分配任務(wù)和回收從進(jìn)程的計(jì)算結(jié)果。從進(jìn)程負(fù)責(zé)完成主進(jìn)程分配的計(jì)算任務(wù)。

2．2 平臺(tái)搭建

MPI（Message Passing Interface）是消息傳遞型并行編程模型的一種標(biāo)準(zhǔn)的消息傳遞接口，主要服務(wù)于分布式主存的并行計(jì)算平臺(tái)。MPI實(shí)際是一個(gè)可由C／FORTRAN77／C＋＋／Fortran90等語言調(diào)用的函數(shù)庫，它遵循和其他庫函數(shù)一樣的調(diào)用規(guī)則。在并行編程開發(fā)中，作為消息傳遞型編程模型工具，MPI的主要作用是在并行計(jì)算節(jié)點(diǎn)間傳遞消息，協(xié)調(diào)各節(jié)點(diǎn)間的數(shù)據(jù)交換、同步、控制，協(xié)同完成并行任務(wù)。目前所有并行計(jì)算機(jī)都支持MPI，在網(wǎng)上可以免費(fèi)下載 MPI的實(shí)現(xiàn) MPICH。現(xiàn)在使用較為廣泛的MPICH2是于2004年9月發(fā)布。本文采用MPICH2（http：／／www．mpich．or g／）實(shí)現(xiàn)分布式主存并行計(jì)算平臺(tái)的搭建，結(jié)構(gòu)如圖3所示。并行計(jì)算平臺(tái)的具體組建步驟如下：

1）用百兆路由器和網(wǎng)線將4臺(tái)四核PC機(jī)組建為一個(gè)局域網(wǎng)，且將每臺(tái)計(jì)算機(jī)的用戶名和密碼統(tǒng)一。

2）在每臺(tái)計(jì)算機(jī)的同一個(gè)路徑下安裝MPICH2。

3）在每臺(tái)計(jì)算機(jī)上安裝好 MPI后，用wmpiregister．exe將每臺(tái)計(jì)算機(jī)用統(tǒng)一的用戶名和密碼進(jìn)行注冊。

4）使用wmpiconfig．exe在局域網(wǎng)中搜索主機(jī)，如果各主機(jī)上已安裝好MPI則均顯示為綠色。選擇應(yīng)用后即可。

5）將需要運(yùn)行的程序放在各主計(jì)算機(jī)主存的同一路徑下，用w mpiexec．exe運(yùn)行并行程序。

圖3 并行計(jì)算平臺(tái)結(jié)構(gòu)圖

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

3．1 試驗(yàn)數(shù)據(jù)

本文試驗(yàn)采用一組航空影像和一組無人機(jī)影像，具體的數(shù)據(jù)信息如表1所示，圖4和圖5給出了兩組影像中部分影像的示例圖。

表1 試驗(yàn)影像信息

圖4 航空影像

圖5 無人機(jī)影像

3．2 并行計(jì)算運(yùn)行時(shí)間

由圖1可知為保證任務(wù)的完整性和一致性，數(shù)據(jù)的輸入、輸出和自適應(yīng)立體像對(duì)的選擇必須在主進(jìn)程中完成。核線糾正、基于SGM的密集匹配和前方交會(huì)3個(gè)過程可以考慮采用并行計(jì)算。本文組建的計(jì)算平臺(tái)為分布式主存的并行計(jì)算平臺(tái)，在任務(wù)分配和結(jié)果回收過程中包含數(shù)據(jù)傳輸和傳輸?shù)却葐栴}。以上3個(gè)過程采用并行計(jì)算是否能夠節(jié)省時(shí)間需要比較該過程對(duì)應(yīng)的計(jì)算時(shí)間和數(shù)據(jù)傳輸時(shí)間。如果單個(gè)過程的計(jì)算時(shí)間大于接收主進(jìn)程分配信息和傳回結(jié)果的傳輸時(shí)間，則該過程并行可以達(dá)到加速的目的，縮短程序運(yùn)行時(shí)間。

自適應(yīng)選擇立體像對(duì)后，分配的處理任務(wù)以立體像對(duì)為單位，因此在單機(jī)上對(duì)3個(gè)過程處理一個(gè)立體像對(duì)的時(shí)間進(jìn)行測試。測試數(shù)據(jù)傳輸時(shí)間以立體像對(duì)為單位，3個(gè)計(jì)算過程的所需時(shí)間如表2所示，表中時(shí)間均為隨機(jī)獲取的多個(gè)立體像對(duì)的平均時(shí)間。

表2 立體像對(duì)計(jì)算過程時(shí)間 s

采用本文自主搭建的并行平臺(tái)對(duì)核線糾正、基于SGM的密集匹配和前方交會(huì)3個(gè)計(jì)算過程的數(shù)據(jù)傳輸時(shí)間進(jìn)行測試。核線糾正需要接收主進(jìn)程的信息為立體像對(duì)信息和立體像對(duì)影像，生成的結(jié)果為核線影像。密集匹配過程需要輸入的信息為立體像對(duì)信息和核線影像信息，生成結(jié)果為視差圖。前方交會(huì)需要輸入的信息為立體像對(duì)信息和視差圖，生成結(jié)果為三維點(diǎn)云。各計(jì)算過程所需輸入信息和生成結(jié)果的傳輸時(shí)間如表3所示，表中時(shí)間均為傳輸多個(gè)立體像對(duì)信息的平均時(shí)間。

表3 信息傳輸時(shí)間 s

對(duì)比表2和表3可知，密集匹配和前方交會(huì)過程的計(jì)算時(shí)間遠(yuǎn)大于傳輸時(shí)間，因此將這兩個(gè)過程并行化可以明顯減少整個(gè)過程的處理時(shí)間。核線糾正的處理時(shí)間和信息傳輸時(shí)間基本相等，如果核線糾正過程采用并行方案，則整個(gè)過程并行流程如圖6（a）所示，如果采用串行方案則并行流程如圖6（b）所示。

以無人機(jī)影像的90個(gè)立體像對(duì)為例，在4臺(tái)計(jì)算機(jī)上各開辟1個(gè)進(jìn)程共4個(gè)進(jìn)程，其中1個(gè)設(shè)為主進(jìn)程，3個(gè)設(shè)為從進(jìn)程。如果核線糾正采用并行計(jì)算，如圖6（a）所示，預(yù)計(jì)耗時(shí)為主進(jìn)程輸入輸出數(shù)據(jù)、主進(jìn)程傳輸立體像對(duì)信息（包含原始影像）、接收三維點(diǎn)云的時(shí)間及從進(jìn)程并行計(jì)算所耗費(fèi)的時(shí)間之和；如果核線糾正采用串行計(jì)算，如圖6（b）所示，預(yù)計(jì)耗時(shí)為主進(jìn)程輸入輸出數(shù)據(jù)、主進(jìn)程的傳輸立體像對(duì)信息（包含核線影像）、接收三維點(diǎn)云及核線糾正的時(shí)間及從進(jìn)程并行計(jì)算所耗費(fèi)的時(shí)間之和。按照上述分析，采用本文自主組建的并行平臺(tái)進(jìn)行試驗(yàn)，核線糾正采用并行共耗時(shí)7 275 s，核線糾正采用串行共耗時(shí)7 455 s 因此，本文將核線糾正、密集匹配和前方交會(huì)3個(gè)過程均采用并行計(jì)算，具體并行計(jì)算流程如圖6（a）所示。

圖6 并行算法流程

3．3 試驗(yàn)結(jié)果與分析

采用自適應(yīng)選擇立體像對(duì)的方法，無人機(jī)影像共選擇立體像對(duì)258對(duì)，航空影像共選擇立體像對(duì)245對(duì)。并行計(jì)算時(shí)顧及計(jì)算機(jī)的運(yùn)算能力、內(nèi)存和傳輸時(shí)間，在每臺(tái)計(jì)算機(jī)上開辟3個(gè)進(jìn)程共12個(gè)進(jìn)程進(jìn)行計(jì)算，其中1個(gè)為控制進(jìn)程（主進(jìn)程），另外11個(gè)為計(jì)算進(jìn)程（從進(jìn)程）。表4給出了兩組數(shù)據(jù)的立體像對(duì)數(shù)目、整個(gè)測區(qū)的三維點(diǎn)數(shù)目、計(jì)算時(shí)間以及采用本文自主組建的并行計(jì)算平臺(tái)獲得加速比。無人機(jī)影像三維點(diǎn)云如圖7所示。兩組數(shù)據(jù)所覆蓋的整個(gè)測區(qū)的三維點(diǎn)云顯示結(jié)果如圖8和圖9所示。圖10和圖11給出了測區(qū)部分區(qū)域的三維點(diǎn)云和三維模型。

表4 并行計(jì)算加速比

圖7 無人機(jī)影像三維點(diǎn)云

圖8 航空影像三維點(diǎn)云

圖9 無人機(jī)影像部分三維點(diǎn)云及對(duì)應(yīng)的三維模型

圖10 航空影像部分三維點(diǎn)云及對(duì)應(yīng)的三維模型

由表4和圖7～圖10可以看出，本文的自適應(yīng)選擇立體像對(duì)的方法在減少立體像對(duì)的基礎(chǔ)上保證了整個(gè)區(qū)域內(nèi)不出現(xiàn)空洞，能夠有效地減少冗余計(jì)算，縮短計(jì)算時(shí)間，獲取測區(qū)內(nèi)較好的三維點(diǎn)云。密集匹配算法能夠得到效果良好的視差圖，對(duì)三維重建的前方交會(huì)過程提供足夠的同名點(diǎn)。本文提出的基于MPI的高效半全局約束密集匹配方法效果明顯，串行計(jì)算處理一個(gè)立體像對(duì)平均用時(shí)分別為0．98 min和3．42 min，而采用本文提出的方法處理一對(duì)立體像對(duì)平均用時(shí)僅為0．17 min和0．48 min，大幅度提高了處理效率。對(duì)于主從模式的并行程序，如果忽略傳輸時(shí)間，理想加速比應(yīng)等于從進(jìn)程數(shù)。但是實(shí)際運(yùn)行過程中協(xié)調(diào)和信息傳輸占用了一定的時(shí)間，傳輸所占整體運(yùn)行時(shí)間比例越大加速比越小。航空影像傳輸時(shí)間占運(yùn)行時(shí)間比例大于無人機(jī)影像，因此加速比小于無人機(jī)影像的加速比。

4 結(jié)束語

試驗(yàn)結(jié)果表明，基于MPI的高效半全局約束密集匹配方法能夠?qū)崿F(xiàn)大范圍的低空影像密集匹配，有效提高大范圍低空影像的密集匹配效率，生成無縫的地形產(chǎn)品。從而縮短數(shù)字高程模型生成周期，為自然災(zāi)害應(yīng)急響應(yīng)提供及時(shí)的攝影測量產(chǎn)品。基于MPI搭建的并行計(jì)算平臺(tái)使用的是廉價(jià)易得的計(jì)算機(jī)和軟件，能有效降低應(yīng)急測繪處理成本。

［1］ 張祖勛，柯濤，郭大海，等．?dāng)?shù)字?jǐn)z影測量網(wǎng)格在汶川大地震中的快速響應(yīng)［J］．中國工程科學(xué)，2002，11（6）：54－62．

［2］ 李隆方，張著豪，鄧曉麗，等．基于無人機(jī)影像的三維模型構(gòu)建技術(shù)［J］．測繪工程，2013，22（4）：85－89．

［3］ HIRSCH MüLLER H．Stereo Processing by Semi－Global Matching and Mutual Infor mation ［J］．IEEE Transactions on Patter n Analysis and Machine Intelli－gence，2008，30（2）：328－341．

［4］ 張劍清，柯濤，孫明偉．基于集群計(jì)算機(jī)的海量航空數(shù)碼影像并行 處理［J］．計(jì)算機(jī)工程與應(yīng) 用，2008，44（13）：12－15．

［5］ 熊登亮，陳舫益．采用無人機(jī)影像生成高原山區(qū)高精度DEM的一種方法［J］．測繪與空間地理信息，2014，37（1）：127－128．

［6］ 劉航冶，張永生，鄧雪清．集群環(huán)境下的影像并行匹配算法［J］．測繪科學(xué)技術(shù)學(xué)報(bào)，2010，27（3）：205－208．

［7］ 李宏寬，楊曉冬，鄒珍軍．基于MPI并行的遙感影像系統(tǒng)級(jí)幾何校正快速處理技術(shù)研究［J］．河南工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2011，23（1）：49－52．