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

王歡歡，鄒崢嶸，張云生

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

面對突然發(fā)生的自然災(zāi)害，快速準(zhǔn)確獲取災(zāi)害現(xiàn)場的災(zāi)區(qū)范圍、房屋倒塌、道路破壞等情況是災(zāi)害評估和救災(zāi)搶險的關(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ī)等低空平臺獲取的低空影像正在成為救災(zāi)測繪應(yīng)急保障的重要手段。

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

1 串行算法流程

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

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

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

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

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

1．2．1 匹配代價

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

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

1．2．2 匹配代價聚合

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

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

對于像素P，在r方向的累積匹配代價定義為

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

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

圖2 匹配代價聚合

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

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

2 基于MPI的并行集群平臺的搭建

2．1 并行計算

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

2．2 平臺搭建

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

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

2）在每臺計算機(jī)的同一個路徑下安裝MPICH2。

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

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

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

圖3 并行計算平臺結(jié)構(gòu)圖

3 實驗結(jié)果及分析

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

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

表1 試驗影像信息

圖4 航空影像

圖5 無人機(jī)影像

3．2 并行計算運行時間

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

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

表2 立體像對計算過程時間 s

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

表3 信息傳輸時間 s

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

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

圖6 并行算法流程

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

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

表4 并行計算加速比

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

圖8 航空影像三維點云

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

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

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

4 結(jié)束語

試驗結(jié)果表明，基于MPI的高效半全局約束密集匹配方法能夠?qū)崿F(xiàn)大范圍的低空影像密集匹配，有效提高大范圍低空影像的密集匹配效率，生成無縫的地形產(chǎn)品。從而縮短數(shù)字高程模型生成周期，為自然災(zāi)害應(yīng)急響應(yīng)提供及時的攝影測量產(chǎn)品。基于MPI搭建的并行計算平臺使用的是廉價易得的計算機(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ī)的海量航空數(shù)碼影像并行 處理［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é)報，2010，27（3）：205－208．

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