一种基于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