一種基于MPI和OpenMP的剖分遙感影像并行分割方法

杜根遠　張火林　苗　放

1(許昌學院國際教育學院　河南 許昌 461000)2(成都理工大學地球物理學院　四川 成都 610059)

?

一種基于MPI和OpenMP的剖分遙感影像并行分割方法

杜根遠1張火林1苗放2

1(許昌學院國際教育學院河南 許昌 461000)2(成都理工大學地球物理學院四川 成都 610059)

隨著遙感數(shù)據(jù)量的快速增長，組織效率和處理速率成為其快捷應用的瓶頸，地球剖分理論和高性能計算為該問題解決提供了一種可能途徑?；谏鲜鏊悸?，設計一種基于MPI和OpenMP的剖分遙感影像并行分割方法。該方法在地球剖分組織理論的研究基礎上，針對遙感影像數(shù)據(jù)進行剖分化處理，依據(jù)應用需求確定剖分層級，形成有利于并行處理的影像數(shù)據(jù)剖分面片集合；在MPI集群計算和OpenMP多核任務處理環(huán)境下，對上述剖分面片集進行相應操作的并行化處理，最后把處理后的面片整合為所需要的結果數(shù)據(jù)。通過一個遙感影像數(shù)據(jù)K-Means分割的例子對上述方法進行驗證。結果表明，該方法能在分割結果保持一致的情況下，有效提高遙感影像的組織效率和處理速度，達到了一定的加速比，實用性較強。

遙感影像地球剖分理論剖分面片MPIOpenMP

0　引　言

目前，全球天地一體化的高分辨率對地觀測體系已經(jīng)初步形成，利用該體系進行環(huán)境保護、災害監(jiān)測、資源開發(fā)、軍事偵察等諸多軍事及民用領域應用成為了新的手段[1]。高分辨率衛(wèi)星遙感是對地觀測體系的重要組成部分，呈現(xiàn)出高空間分辨率、高光譜分辨率、高時間分辨率和多平臺、多傳感器、多角度的發(fā)展趨勢。隨著航空航天技術的發(fā)展和遙感器件性能的改進，利用遙感產(chǎn)生的空間數(shù)據(jù)體量日益龐大。與此同時，遙感數(shù)據(jù)的應用領域也在不斷地深化和拓展。然而，人們對空間數(shù)據(jù)的解析和利用程度卻遠遠低于數(shù)據(jù)獲取的速度。如何對遙感數(shù)據(jù)進行高效的組織、管理和快捷的信息提取成為當前研究的一個熱點，地球剖分組織理論和并行計算是解決上述問題的有效途徑。

經(jīng)過幾十年的發(fā)展，遙感影像處理技術日趨成熟，已經(jīng)取得了一大批理論和算法成果[1]。以并行數(shù)據(jù)處理為基礎的高性能計算技術是目前遙感影像高效處理所采用的主要方法，也是提高影像處理速度和效率的最有效方法之一[2-5]。文獻[2]提出了一種基于網(wǎng)格環(huán)境的遙感影像并行分類模型，并設計了網(wǎng)格服務及任務調度的算法流程；文獻[3]針對遠海遙感影像目標物數(shù)量相對較少的特點，提出了對影像進行并行處理的集群體系任務分配算法模型；文獻[4]提出了一種面向統(tǒng)一遙感圖像處理的多粒度并行模型，并給出了模型的四層接口，描述了模型接口、定義、并行任務調度和容錯機制等；文獻[5]提出一種有效的、可擴展的并行點對稱的遙感影像像素分類并行算法，并給出了用于計算基于距離的點對稱的加速策略。與此同時，高性能集群、專用硬件設備GPU、MIC等在遙感影像高性能處理領域得到廣泛應用[6,7]。

但是，由于缺乏有效的數(shù)據(jù)組織機制，多源異構的影像數(shù)據(jù)要實現(xiàn)動態(tài)、高效關聯(lián)比較困難。此外，遙感影像并行處理算法需要采取合理的策略進行粒度分割，以充分發(fā)揮集群的計算能力；且遙感影像并行算法的實際運行效率往往達不到理想的加速比，嚴重依賴于集群的硬件配置情況，不具有通用性。如何科學高效地對空間數(shù)據(jù)進行組織，合理設計并行算法模型，充分利用集群CPU、GPU及MIC的計算能力對其進行優(yōu)化，不僅對編程者而言是難點，同時也給空間數(shù)據(jù)應用帶來了困難。

針對上述問題，基于地球剖分組織理論，設計了一種基于MPI和OpenMP混合編程模式下的遙感影像并行分割方法。該方法首先對遙感影像數(shù)據(jù)進行剖分化處理，形成有利于并行處理的影像數(shù)據(jù)剖分面片集合；在MPI集群計算和OpenMP多核任務處理環(huán)境下，對上述剖分面片集進行相應操作的并行化處理，最后把處理后的面片整合為所需要的結果數(shù)據(jù)。通過一個實例對上述方法進行了驗證，結果表明，該方法能有效提高遙感影像的組織效率和處理速度，加速效果較為明顯。

1　地球剖分模型(EMD)

地球剖分組織理論是研究如何對地理空間位置進行劃分的方法，它依據(jù)剖分組織框架，把地球表面劃分為離散分布、大小相似、無縫無疊的剖分面片。相比平面數(shù)據(jù)模型，具有全球空間數(shù)據(jù)統(tǒng)一組織、存儲、提取、分析、平面-球面一體化表達、數(shù)據(jù)整合匯聚迅速等優(yōu)勢。剖分模型是地球剖分組織理論研究的核心問題，該模型研究對地球表面進行多級劃分的方式和方法以及得到剖分面片形狀、編碼、結構、如何組織等問題。幾種常見的剖分模型包括QTM模型[8](Quaternary Triangular Mesh)、STQIE模型[9](Spherical Triangle Quadtree based on Icosahedron and ERLRP)、SIMG模型[10](Spatial Information Multi-Grid)等。剖分模型中的剖分面片構成一個相互關聯(lián)的地球剖分遙感影像體系框架，剖分面片層級之間以及同層不同面片之間大多采用四叉樹和剖分編碼來進行組織。但部分剖分模型存在剖分面片變形、計算復雜等一系列問題，不能有效滿足宏觀空間剖分數(shù)據(jù)高性能處理的需求[3]。

北京大學973課題組基于上述研究基礎，設計并驗證了EMD剖分模型的整套方案[11,12]。其主要思想是地球表面行劃分為中低緯度區(qū)域和高緯度區(qū)域，對不同的部分采用不同的剖分方法。在該方案中，采用基于地圖分幅的“等經(jīng)緯度格網(wǎng)”方法對中低緯度區(qū)域進行剖分；采用“正多面體”以三角形進行剖分的方法對高緯度區(qū)域進行剖分，從而實現(xiàn)地球空間多種數(shù)據(jù)的統(tǒng)一組織和高效管理[11,12]。

剖分面片是地球表面經(jīng)剖分模型劃分出來的分割單元，具有多尺度、多等級、小變形、離散、規(guī)則等特點。每一個剖分面片均有唯一的編碼標識、層級結構和明確的地理空間位置、范圍等信息。

剖分面片模板包含剖分面片的基本結構和內容，其本身既為經(jīng)處理后的高分辨率遙感影像，同時也包含與該面片相關聯(lián)的其他空間特征數(shù)據(jù)，是與面片相對應的數(shù)據(jù)樣本。一個剖分面片可對應多種剖分面片模板，根據(jù)數(shù)據(jù)處理和應用需求的不同，每一種模板可對應于一個具體的處理算法[13,14]。

2　MPI+OpenMP混合編程模式

目前有兩種主要的并行系統(tǒng)：分布式內存系統(tǒng)和共享內存系統(tǒng)。在分布式內存系統(tǒng)中，每個核都擁有自己的私有內存，核之間的通信是顯式的，需要使用類似于在網(wǎng)絡中發(fā)送消息的機制；在共享內存系統(tǒng)中，原則上每個核能訪問每個內存區(qū)域。

MPI用于分布式內存系統(tǒng)的編程，一個MPI系統(tǒng)通常由一組庫、頭文件和相應環(huán)境構成，其并行程序通過調用庫中函數(shù)完成消息傳遞，在編譯時與庫進行鏈接。常用的MPI系統(tǒng)是MPICH。

OpenMP用于共享內存系統(tǒng)的編程，是對C語言相對更高層次的擴展，容易將很多程序并行化，主要針對細粒度的循環(huán)級并行，可使用Fork-Join的并行執(zhí)行模式。

石化智造，需要集聚一大批專業(yè)人才、高端人才，這是團隊研發(fā)持續(xù)不斷的基礎，錢鋒團隊引進了一批“高潛能”人才，培育出了一支“高品質”的研發(fā)團隊。

為了結合分布式內存結構和共享式內存結構的優(yōu)勢，業(yè)界提出采用MPI+OpenMP的分布式/共享內存的混合編程模式。該模式下，計算結點內部和之間采用二級并行，計算結點內部利用OpenMP方式并行，計算結點之間采用MPI方式并行。實踐證明，該模式能較好地提升并行系統(tǒng)的性能[15]。

3　剖分遙感影像并行處理方法

遙感影像經(jīng)剖分模型進行剖分化處理，形成不同層級的剖分面片集合；對剖分面片進行特征提取并快速生成剖分面片模板，建立剖分面片模板數(shù)據(jù)庫；針對具體應用如分割算法進行并行化分析，實現(xiàn)算法并行處理模型；設計相應并行類，形成處理算法的并行化類庫，最終實現(xiàn)遙感影像的快速并行處理。其并行化處理流程如圖1所示。

圖1　剖分面片模板處理算法的并行化流程

3.1遙感影像剖分化處理

針對特定應用需求的熱點區(qū)域、分辨率的遙感影像，根據(jù)應用需求，按照EMD剖分流程生成該遙感影像所對應級別的剖分面片，提取剖分面片單元的模板化特征形成面片模板，進行入庫操作。如果檢索該面片模板不存在則直接入庫，否則根據(jù)該遙感影像特征進行相似度對比，確定閾值，當對比結果小于閾值則不更新該面片對應的模板，否則入庫并更新該面片模板。模板庫按照“數(shù)據(jù)節(jié)點編號/衛(wèi)星類型/面片層級/目標模板數(shù)據(jù)”方式組織面片模板數(shù)據(jù)。

3.2構建模板并行計算模式

剖分面片模板作為剖分面片并行計算的基本單元，剖分面片的模板創(chuàng)建應當依據(jù)一定的應用需求。需要對特定區(qū)域的數(shù)據(jù)進行處理時，可直接提取相應的模板用于剖分化并行計算，從而實現(xiàn)數(shù)據(jù)的高效處理，縮短應用準備時間。剖分面片模板并行計算模式源于剖分數(shù)據(jù)組織模型的支持。在面片層面，計算節(jié)點采用分布式存儲體系結構，通過MPI實現(xiàn)計算節(jié)點(剖分面片)之間的并發(fā)數(shù)據(jù)處理，從而實現(xiàn)粗粒度數(shù)據(jù)并行；在計算節(jié)點(剖分面片)內部，可根據(jù)數(shù)據(jù)特點或具體算法利用OpenMP進行細粒度數(shù)據(jù)并行。

3.3形成算法并行處理模型

首先對算法并行性分析。對于特定遙感圖像處理算法，利用并行化分析工具Intel VTune找出該算法的計算熱點，通過計算依賴、數(shù)據(jù)依賴分析，考察計算熱點的可并行性；分析模板相關的處理算法及其可并行的代碼步占整個算法總運算步的百分比。依據(jù)算法并行化特征可分為全局可并行算法、局部可并行算法、不可并行算法三類。根據(jù)分類，提取三種不同的處理模型：全局并行處理模型、局部并行處理模型、串行算法處理模型。其次生成算法并行處理模型。根據(jù)熱點計算特點，實現(xiàn)在MPI與OpenMP混合并行計算框架下計算任務的多粒度分解模式與節(jié)點間數(shù)據(jù)交換策略，得到算法的并行處理模型。在MPI與OpenMP混合并行計算框架下，MPI處于頂層，主要負責計算節(jié)點間的通信；OpenMP處于底層，負責單機內多核心并行處理。

全局并行處理模型主要針對具有天然并行性、計算量較大、與影像信息統(tǒng)計密切相關的處理算法，這類算法數(shù)據(jù)及運算依賴性較弱，計算任務易于分解，并行效果好。處理流程為：集群主節(jié)點接受參數(shù)，完成初始化功能，利用MPI消息庫，將計算熱點區(qū)域分解到各個計算節(jié)點；各計算節(jié)點獲取計算任務，利用OpenMP實現(xiàn)節(jié)點內的并行計算；最后將計算結果聚合至主節(jié)點。主節(jié)點動態(tài)控制計算節(jié)點的計算負載。

串行算法處理模型主要針對計算熱點區(qū)域依賴性較強、并行性較差的處理算法。其處理流程為：集群主節(jié)點進行計算任務的分配，利用MPI將計算任務分配至存放對應面片模板的計算節(jié)點，實現(xiàn)任務的本地計算，從而節(jié)省數(shù)據(jù)傳輸所帶來的額外開銷。

3.4算法并行化類庫頂層設計

針對具體處理算法和并行化模型，運用面向對象軟件開發(fā)技術，設計相應的并行類。將該算法并行化模型中處理步驟抽象為并行類的方法成員，利用MPI與OpenMP對該并行類的方法進行并行化實現(xiàn)，在此基礎上形成剖分面片模板處理算法的并行化類庫。

根據(jù)并行處理模型設計三個接口IFullParallelProcessing、ISectionParallelProcessing、INearbyProcessing。該接口定義面向剖分面片模板處理算法的并行化流程，并把流程中每一個步驟抽象為接口中的方法。

為處理算法并行類實現(xiàn)一個共同的父接口，即抽象工廠IRemoting-ImgProcessingFactory，該工廠定義三個方法createFullParallelProcessing()、createSectionParallel-Processing()、createNearbyProcessing()。RemotingImgProcessingFactory實現(xiàn)抽象工廠接口，負責生成遙感圖像處理算法具體的并行化類。

3.5生成處理算法并行化類庫

確定該處理算法所必需的計算參數(shù)，包括算法的輸入輸出、對應的面片模板編號、圖像像素大小等。將其映射為相應并行算法類的數(shù)據(jù)成員，編寫相應的構造方法實現(xiàn)該類的初始化；選定該處理算法的并行化處理模型，實現(xiàn)相應的接口，逐一實現(xiàn)接口所定義的并行化步驟，即完成該算法的并行類；將常見的處理算法按上述方法進行并行化，構建常見處理算法的并行化類庫。用戶要進行特定的遙感處理，只需導入該類庫，生成該并行算法框架類的具體實例，調用類中實現(xiàn)的方法即可實現(xiàn)該處理的快速并行化。這些算法均在MPI+OpenMP混合并行計算框架下實現(xiàn)。

4　應用及效果

4.1基于K-means的混合聚類并行分割算法

基于上述思想，設計了集群環(huán)境下的基于K-means的混合型圖像并行分割算法。該算法采用MPI并行框架，主線程讀取影像數(shù)據(jù)，根據(jù)計算節(jié)點數(shù)目，進行任務分解。由于圖像數(shù)據(jù)按行存放，可根據(jù)行數(shù)及計算節(jié)點個數(shù)進行分塊，將影像數(shù)據(jù)均勻分解成若干子圖，將各子圖數(shù)據(jù)及聚類中心傳輸?shù)礁鱾€節(jié)點計算進程。進程間的通信由MPI的消息傳遞函數(shù)完成。各計算進程各自執(zhí)行并行的K-means聚類算法，其主要方法為：void KmeansParallel :: kmeans_run (vector > &datas, vector & indexer, vector &labels)。K-means聚類算法主要時間耗費在于計算各像素與聚類中心的距離。該算法利用OpenMP的#Pragma omp parallel for編譯指導指令，將計算任務并行分解到計算節(jié)點的多個核心。計算進程將各自聚類結果傳回給主進程，主進程進行層次聚類算法，從而完成各聚類的合并。層次聚類計算各子聚類的距離，該距離定義為兩子聚類間節(jié)點的平均距離，當該距離小于某一閾值時進行子聚類的合并，該閾值通過實驗確定最佳值。

算法的具體流程如圖2所示。

圖2　基于K-means的混合并行分割算法流程圖

4.2算法具體應用

通過一個遙感影像分割的例子對上述思路進行驗證。首先對影像數(shù)據(jù)進行分級剖分處理，形成剖分面片集合；依據(jù)具體應用選取相應級別的剖分面片，利用上述算法進行并行化分割處理，最終實現(xiàn)遙感影像的快速并行處理，如圖3所示。

圖3　實驗流程

研究數(shù)據(jù)來源于2013年9月9日Landsat8衛(wèi)星的操作陸地成像儀所拍衛(wèi)星影像，影像區(qū)域為哈薩克斯坦遠東地區(qū)，空間分辨率大于8米。依據(jù)EMD模型對其進行剖分處理，形成面片集，依據(jù)應用需求對面片進行并行處理，處理后的剖分面片可根據(jù)需要可進行縫合、拼接；選取實驗區(qū)域第7級剖分面片，其緯差5′，經(jīng)差7′30″，對應于1∶5萬比例尺的地圖；根據(jù)實驗需要，選取實驗影像區(qū)域大小1667×1666像素。

實驗中使用4臺計算節(jié)點，每個計算節(jié)點CPU選用為Intel i5-4590 3.3 GHz四核處理器，內存選用Kingston DDR3 2666 8 GB。軟件環(huán)境采用Windows 7操作系統(tǒng)，開發(fā)工具為Visual Studio 2010，并行環(huán)境為MPICH2，多線程庫采用OpenMP。影像分割算法采用K-means聚類算法，針對遙感影像所在區(qū)域地物地貌進行目視判讀，確定算法聚類中心數(shù)K值為4。

依據(jù)文中所述方法對K-means算法進行并行化實現(xiàn)，其算法思想不再贅述。算法串行及并行分割后的影像效果如圖4所示。(a)為影像原圖，(b)為串行K-means分割效果，(c)為并行K-means分割效果，其分割效果接近。當聚類中心數(shù)K值選取為4時，得到的分割效果較好，K值選取為其他值時分割效果不理想。

圖4　分割實驗結果

選擇十次不同的初始聚類中心，對上述剖分遙感影像面片單元進行十次串、并行K-means算法測試，其時間消耗對比如表1所示，本文所述的并行方法在時間上有明顯的優(yōu)勢。由于聚類中心選擇的隨機性導致每次算法運行時間有差異，但從平均情況來看，并行算法的加速比達到2.947左右，從表中數(shù)據(jù)可以看出，加速比相對穩(wěn)定，加速效果較為理想。

表1　K-means算法串行及并行運行比較

5　結　語

本文提出了一種在MPI和OpenMP混合編程模式下的遙感影像并行分割方法。從實驗可以看出，本文方法既利用了地球剖分理論在遙感數(shù)據(jù)組織上的優(yōu)勢，又彌補了OpenMP在分布式并行的缺陷和MPI在細粒度上的不足。從實驗結果可以看出，執(zhí)行效率相對串行方法有較大的提高，有良好的加速比。本文所提出的方法能夠有效地提高空間數(shù)據(jù)的組織和存儲效率，縮短空間數(shù)據(jù)應用的時間，增強空間數(shù)據(jù)更新和解譯能力，為進一步研究遙感影像的高性能計算提供借鑒，具有一定的示范意義。

[1] Lee C A,Gasster S D,Plaza A,et al.Recent developments in high performance computing for remote sensing:A review[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2011,4(3):508-527.

[2] 張雁,吳保國,王曉輝,等.基于網(wǎng)格環(huán)境的遙感圖像并行分類[J].計算機應用與軟件,2015,32(2):194-197,219.

[3] 曾志,劉仁義,李先濤,等.一種基于分塊的遙感影像并行處理機制[J].浙江大學學報:理學版,2012,39(2):225-230.

[4] Guo W, Zhu X,Hu T,et al.A Multi-granularity Parallel Model for Unified Remote Sensing Image Processing WebServices[J].Transactions in GIS,2012,16(6):845-866.

[5] Maulik U,Sarkar A.Efficient parallel algorithm for pixel classification in remote sensing imagery[J].Geoinformatica,2012,16(2):391-407.

[6] 袁濤,馬艷,劉定生.GPU在遙感圖像處理中的應用綜述[J].遙感信息,2012,27(6):110-117.

[7] Liu Y,Chen B,Yu H,et al.Applying GPU and POSIX thread technologies in massive remote sensing image data processing[C]//2011 IEEE 19th International Conference on Geoinformatics,2011:1-6.

[8] Dutton G.A hierarchical coordinate system for geoprocessing and cartography:working through the scales[M]//Lecture Notes in Earth Sciences,vol.79.Berlin: Springer-Verlag,1999.

[9] 袁文,莊大方,袁武,等.基于等角比例投影的球面三角四叉樹剖分模型[J].遙感學報,2009,13(1):103-111.

[10] 李德仁.論廣義空間信息網(wǎng)格和狹義空間信息網(wǎng)格[J].遙感學報,2005,9(5):513-520.[11] 宋樹華,程承旗,濮國梁,等.基于EMD的遙感影像數(shù)據(jù)組織模型[J].地理與地理信息科學,2013,29(3):21-25.

[12] 關麗,呂雪鋒.面向空間數(shù)據(jù)組織的地理空間剖分框架性質分析[J].北京大學學報:自然科學版,2012,48(1):123-132.

[13] 程承旗,任伏虎,濮國梁,等.空間信息剖分組織導論[M].北京: 科學出版社,2012.

[14] 杜根遠,熊德蘭,張火林.基于剖分理論的遙感影像模板數(shù)據(jù)模型[J].計算機應用,2014,34(4):1165-1168,1181.

[15] Hudik M,Hodon M.Modeling,optimization and performance prediction of parallel algorithms[C]//IEEE Symposium on Computers and Communication,2014:1-7.

A PARALLEL SEGMENTATION METHOD OF PARTITIONED REMOTE SENSING IMAGE BASED ON MPI AND OPENMP

Du Genyuan1Zhang Huolin1Miao Fang2

1(International School of Education,Xuchang University,Xuchang 461000,Henan,China)2(CollegeofGeophysics,ChengduUniversityofTechnology,Chengdu610059,Sichuan,China)

With the rapid growth of remote sensing data, organisational efficiency and processing speed become the bottlenecks of its fast applications, but earth partition theory and high-performance computing technology offer a possible solution. Guided by this idea, the researchers designed an MPI-and-OpenMP-based parallel segmentation method for partitioned remote sensing images. On the basis of earth partition organisation theory study, the method conducts partition process aimed at remote sensing image data and determines the partition layer according to the application requirements, and forms the partitioning facets set of image data conducive to parallel processing; Under the context of MPI cluster computing and OpenMP multi-core tasks processing, the researchers carried out the parallel processing of corresponding operation on above mentioned partitioning facets set, and finally integrated the processed facets into required result data. The above method has been verified by an example of K-means segmentation of remote sensing image data. Experimental result indicated that under the condition of keeping the conformity of segmentation results, this method could effectively raise the organisational efficiency and processing speed of remote sensing image, reached certain speedup and had strong practicality.

Remote sensing imageEarth partition theoryPartition facetMPIOpenMP

2015-03-30。國家自然科學基金項目(U1304403)；河南省科技攻關計劃項目(132102210398)；河南省基礎與前沿技術研究計劃項目(132300410349)。杜根遠，副教授，主研領域：空間信息技術，高性能地學計算。張火林，講師。苗放，教授。

TP751

A

10.3969/j.issn.1000-386x.2016.09.043