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

杜根遠　張火林　苗　放

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

?

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

杜根遠1張火林1苗放2

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

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

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

0　引　言

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

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

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

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

1　地球剖分模型(EMD)

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

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

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

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

2　MPI+OpenMP混合編程模式

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

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

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

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

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

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

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

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

3.1遙感影像剖分化處理

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

3.2構建模板并行計算模式

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

3.3形成算法并行處理模型

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

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

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

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

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

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

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

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

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

4　應用及效果

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

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

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

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

4.2算法具體應用

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

圖3　實驗流程

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

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

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

圖4　分割實驗結果

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

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

5　結　語

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

[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] 張雁,吳保國,王曉輝,等.基于網格環境的遙感圖像并行分類[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] 李德仁.論廣義空間信息網格和狹義空間信息網格[J].遙感學報,2005,9(5):513-520.[11] 宋樹華,程承旗,濮國梁,等.基于EMD的遙感影像數據組織模型[J].地理與地理信息科學,2013,29(3):21-25.

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

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

[14] 杜根遠,熊德蘭,張火林.基于剖分理論的遙感影像模板數據模型[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