遥感影像数据并行计算中数据分配策略研究

马伟锋，李　伟

(1.浙江科技学院 信息与电子工程学院，浙江 杭州 310023；2.浙江工业大学 浙江省可视媒体智能处理技术研究重点实验室，浙江 杭州 310023)

遥感影像数据并行计算中数据分配策略研究

马伟锋1,2，李伟2

(1.浙江科技学院 信息与电子工程学院，浙江 杭州 310023；2.浙江工业大学 浙江省可视媒体智能处理技术研究重点实验室，浙江 杭州 310023)

摘要：分布式并行计算技术的发展使得遥感影像的快速处理成为了可能，而数据分配策略是遥感影像数据并行计算的核心问题.针对不同的影像数据类型和计算算法，提出了基于计算优化的平均划分与非平均划分和基于效果增强的窗口划分与尺度划分四种数据分配策略模式，分析了不同模式适合的算法类型和应用场合，对基于计算优化的模式进行计算速度和效率的理论分析，并通过构建MPI并行计算环境进行实验测试和分析.实验结果符合理论分析预期，可以对遥感影像数据并行计算系统构建和算法设计提供有效的参考和评价.

关键词：遥感计算;并行计算;数据分配;遥感影像处理;分布式计算

随着空间技术的不断发展，人类获取空间数据的能力迅速增强，以遥感影像为代表的对地观察数据正成为空间信息应用的主要数据来源.遥感计算技术紧密依赖于计算机技术、通讯网络技术和智能处理技术的发展，如何从海量的遥感空间数据中快速、有效地提炼与应用目标直接相关的信息和知识，并服务于各行各业的分析与决策一直是遥感计算技术发展的瓶颈问题.近年来，分布式并行计算技术的发展为遥感计算问题提供了新的契机，尤其是基于数据并行的集群计算[1-2].

数据分配是基于数据并行的集群计算的关键问题.目前，国内外对遥感影像并行计算的环境、算法设计等方面研究较多，但对数据分配策略这一关键问题的研究较少，所能参考的文献和资料也寥寥无几.李国庆等[3]提出了6种分布式影像处理的数据分配模式，但这种模式的分类主要侧重于计算和操作角度，分别为整图模式、行序图、列序图、交叉序图、矩阵和特定型；黄国满等[4]对并行遥感影像信息并行处理中的数据划分问题也进行了比较深入的研究；沈占锋等[5-7]都对数据分配策略模式有过相应的研究；从计算环境角度，较大部分研究工作基于MPI的并行环境，也有基于网格计算、Hadoop框架以及赵伟彪等提出MPI向云计算迁移等相关研究及应用[8-14]；国外对基于消息传递机制的分布式并行遥感影像处理研究较早，也比较成熟，集中在并行处理环境、处理系统以及处理算法等方面[15-16].基于以上问题，在结合实践科研工作的基础上，提出了4类数据分配策略模式，分析了不同模式适合的算法类型和应用场合，对相关模式的计算性能进行理论分析并实验.

1数据并行计算原理

在并行计算模型中，基于消息传递机制的模型以其灵活、方便、高效被广泛的采用.基于该模型的遥感影像数据并行计算的工作过程为：首先有个核心计算机，将要被计算的原始遥感影像分成若干个数据块，并将这些数据块分配到不同的并行数据处理计算机上分别进行数据处理与计算，最后再将处理完毕的结果进行合并，完成数据并行计算的任务，如图1所示.

图1　数据并行计算原理Fig.1　Data parallel computing

从图1可以看出：整个数据并行计算的实质就是将数据分配给各个计算结点进行分别计算然后结果汇总的过程，其中图1显示的是一种平均分配策略，即将被处理的原始图像数据平均的划分成若干部分进行计算，这种方式适合那些信息均匀分布的遥感影像.但是对于遥感影像来说，分布在影像上的信息不可能全部都是匀质分布的，需要通过非均匀的、特殊的数据划分策略进行计算.因此根据不同遥感影像特点和计算算法来设计对应的数据划分策略，在数据量传输、通讯量、计算速度等方面将会获得比传统计算方法更好的效果.

2数据分配策略模式

目前，已经有部分专家学者对数据划分策略进行了研究，基本上确立的分配模式可以归纳为平均分配和非平均分配两类，但是这种分类比较粗糙.因此，根据信息在整个影像中的分布情况，算法的类型等方面，初步总结了四类数据划分的策略，如图2所示.

图2　数据分配策略模式Fig.2　Data distribution strategy

从图2中可以看出：数据分配策略分为平均划分、非平均划分、窗口划分和尺度划分4种模式.其中根据信息量在整个遥感图像中分布的情况不同，提出了平均划分的数据分配策略和非平均划分的数据分配策略，主要目的是为了探讨快速计算的优化问题.同时，为了在图像快速处理的基础上得到更好的处理效果，根据图像处理算法的不同，提出了基于窗口的数据分配模式和基于尺度划分的数据分配模式.

2.1平均划分模式

目前最普遍采用的方法就是数据平均分配策略，也是较为容易的一种实现方法.该方法适合对信息量分布比较均匀的遥感图像.这种分配方式下，所适用的图像算法应具有在计算时对像素间的关联距离不大这一特点，如图2(a)所示.在该方法的指导下，提出了若干种具体的分配方式，如按块状进行划分，按行条状进行划分以及按列条状进行划分等等.

2.2非平均划分模式

非均匀划分模式比较复杂，需要在分配前粗略的计算划分的边界，所适合的图像处理算法与平均划分模式一样，但面向的遥感图像与均匀划分不同，是信息量分布不均衡的遥感图像，即在遥感图像上我们感兴趣的信息所占整个图像的比例较小，集中在一个较小的区域内，如图2(b)所示.假如系统想要在某一遥感影像数据中获取相关水域中的船体信息，但影像并非整个包含水域信息，可能其中绝大部分是陆地信息，水域信息只占据了一部分，所占区域非常小.而由于我们希望获取的船体的信息，一般位于水域信息中，因此在对船体进行信息提取时，就没有必要对陆地区域进行计算，只需对影像的水域信息进行处理.这样系统就可以进行预处理获取两个区域间的边界，明确需要计算的部分.在有效区域占比不高的情况下，边界统计会增加开销，但可以大大减少后期复杂度较高的遥感计算算法的开销，非常有益.

2.3重叠划分模式

上述两种划分模式主要针对的是在计算时像素间的关联不大，关联距离较小的图像处理算法.然后，在各类图像处理算法中，像素间无关联计算的情况几乎很少，有的甚至关联距离很大，例如基于窗口和模板的图像处理算法.因此，为了在获得快速图像处理的同时，获取较好的处理效果，在数据划分的时候要充分考虑像素间关联问题，即划分数据需要一定的重叠，如图2(c)所示.

这种数据划分模式其实就是在图2(a，b)模式的基础上考虑边界的数据重叠问题，控制重叠区域的大小是其中的关键点，也是难点.假如重叠区域大小控制的较差，非但不会提升遥感影像计算的效率，反而将增加计算的通信量，加剧遥感影像计算的系统开销.根据以往经验，一般建议冗余总体窗口宽度的1/10到1/20像素数据.

2.4尺度划分模式

地理空间本身具有尺度的依赖性.为获取更好结果，对于部分遥感影像不能只采用某一个分辨率进行计算，而是需要有尺度依赖性，选取同一影像的多个分辨率进行处理，最后将结果进行综合、合并.比如多尺度、多分辨率算法，可以按照需求，在主节点进行预处理建立多个尺度的影像数据，在子节点对不同尺度的影像数据进行计算，获取不同分辨率下的特征数据，最后对相关数据进行融合，提升图象处理效果.图2(d)是采用多尺度的数据分配策略.

3性能分析

上述4种模式，重叠划分和尺度划分主要是针对图像处理效果的，而均匀划分和非均匀划分主要针对快速计算的优化，因此分析了后2种划分模式的计算速度和效率问题.

假设有个并行计算环境，其网络传输速率为V(忽略其他通信环节的额外开销，如高速网络的传播时延，各个计算结点的IO影响等等)，每个结点的软硬件配置一样.所要处理的遥感影像数据量为D(假设处理完后的结果数据量也是D)，那么在并行计算环境中执行单一发送或接收的网络传输时间开销为Tn=D/V.影像处理算法为完全并行化，在单机运行时所需要的时间为Ts每单位影像数据(Ts跟处理算法复杂度有关系，越复杂时间越大)，进行并行计算机所需要的总时间为Tp.为方便期间，采用数据平均分配策略，对运行时间Tp和加速比Sp进行理论分析和实验测试.

3.1理论分析

3.1.1平均分配策略

假设采用的并行计算结点数为n，那么每个结点所要处理的影像数据为D/n，到达或接收每个结点的一次网络传输时间为(D/n)/V.理论上每个结点进行计算的时间为DTs/n，并行计算的总时间包括原始影像数据发送的网络传输时间，单个结点运算时间和处理结果接收的网络传输时间，其表达式为

(1)

从式(1)可以看出：在该数据分配策略下，影响运行总时间Tp的因素包括网络传输速率、影像数据量、影像数据处理算法的复杂度(即单机运算时间)和并行计算的节点数等.在一定的并行计算环境下，网络传输速率一定，影像处理算法一定时，运行总时间Tp与影像数据量成正比，与并行结点数成反比；同时，对于同一影像数据量和同一并行结点数时，运行总时间Tp与网络传输速率成反比，与影像处理算法的复杂度成正比，其中当网络传输速率较高，网络传输时间远小于影像处理算法的单机处理时间，网络传输时间可以忽略，平均分配策略所需总时间Tp主要取决影像处理算法的复杂度.

数据平均分配策略下，带有网络开销的并行加速比公式为

(2)

从式(2)可以看出：在该数据分配策略下，影响并行加速比的因素包括网络传输速率、影像数据处理算法的复杂度(即单机运算时间)和并行计算的节点数.在并行计算环境的网络传输速度和处理算法一定的情况下，加速比随着结点个数增加程现增加的关系，网络传输时间与单机运行时间Ts之比越小，加速比增加快，效率较高.

3.1.2非平均分配策略

假设采用的并行计算结点数为n，数据分发前的预处理每单位影像算法时间为Tm，预处理后影像数据量为Da，那么每个结点所要处理的数据为Da/n，到达或接收每个结点的一次网络传输时间为(Da/n)/V，理论上每个结点进行计算的时间为DaTs/n，因此并行计算的总时间包括影像数据预处理时间，影像数据发送的网络传输时间，单个结点运算时间和处理结果接收的网络传输时间，其表达式为

(3)

从式(2)可以看出：在该数据分配策略下，影响运行总时间Tp的因素包括原始影像数据量、影像预处理算法的复杂度、预处理后影像数据量、网络传输速率、影像处理算法复杂度和并行计算结点数等.在一定的并行计算环境下，网络传输速率和并行计算节点数一定，当影像数据量和影像处理算法复杂度一定时，预处理算法复杂度越小，预测处理后的影像数据量越小，那么运行总时间Tp就越小.

非平均分配策略下，带有预处理和网络开销的并行加速比Sp公式为

(4)

从式(4)可以看出：与式(2)相比，在网络传输速率V和算法复杂度Ts一定的情况下，非平均分配的加速比主要取决于Tm/Ts，Da/D和n三个关键因素，当预处理时间Tm越小，预处理后的数据Da越小，计算节点n越大，那么整个加速比越好.

3.2实验测试

数据平均分配的计算环节是子节点并行计算，而非平均数据分配的计算有两个阶段：主节点预处理和子节点并行计算.假设非平均分配中预处理减少的数据量计算时间正好抵消预处理计算时间，那么子节点并行计算就是影响数据平均分配和非平均数据分配计算速度与效率的关键.实验构造了MPI并行计算环境，在考虑网络开销情况下，对子节点并行计算速度与效率进行了实验测试.实验选用经典的共生矩阵特征提取算法，对Brodatz纹理图像进行了角二度、熵、同质区、非相似性等进行计算及聚类.表1是对不同大小的图像在不同节点数上的网络时延、计算时间、加速比和系统效率的对比.

表1　共生矩阵特征并行计算结果

图3　计算时间对比Fig.3　The comparison of computing time

图4　加速比对比Fig.4　The comparison of speedup

实验结果基本符合理论分析，在考虑网络开销下，系统的加速比较好.当被计算的遥感数据的传输时间与计算算法的复杂度之比越小，系统的运行效率就越高，加速比也越好.当非平均分配中预处理计算时间小于预处理减少的数据量计算时间，那么非平均分配模式的计算速度将进一步提高.因此，系统对于计算复杂度高、所需运行时间较长的遥感影像处理算法非常适合.

4结论

数据并行计算是遥感影像快速、高效计算的重要方向，而数据分配则是遥感影像数据并行计算的核心问题.文章提出了遥感影像数据并行计算中的四类数据分配策略模式，分析了不同模式适合的算法类型和应用场合，对基于计算优化的模式进行计算速度和效率的理论分析，并通过构建MPI并行计算环境，对平均分配和非平均分配的子节点并行计算环节进行实验测试和分析.结果表明：相关的分配策略合理可行，可以对遥感影像数据并行计算算法的设计提供有效的参考和评价.当然，随着计算体系的发展，将进一步研究新的遥感计算模型以及非平均分配的应用场景和算法，对基于效果增强的窗口划分与尺度划分的算法进行归类和实验.

参考文献：

[1]张哲.基于海量遥感数据的集群并行处理技术研究与应用[D].开封：河南大学，2012.

[2]LIANG Fan, LU Xiaoyi.Accelerating iterative big data computing through MPI[J].Journal of computer science and technology,2015,30(2):283-294.

[3]李国庆，刘定生.遥感图象处理的并行计算模式研究[J].中国图形图像学报,2003,8(z1):901-905.

[4]黄国满，郭建峰.分布式并行遥感图像处理中的数据划分[J].遥感信息,2001(2):9-12.

[5]沈占锋，骆剑承，陈秋晓,等.高分辨率遥感影像并行处理数据分配策略研究[J].哈尔滨工业大学学报,2006,38(11):1968-1971.

[6]李德仁，李军.分布式遥感图像处理中的若干关键技术[J].遥感学报,1999,24(1):15-19.

[7]GREGORY A. NEWMAN. A review of high-performance computational strategies for modeling and imaging of electromagnetic induction data[J]. Surveys in geophysics,2014,35(1):85-100.

[8]FOX G. Message passing: from parallel computing to the grid[J]. Computing in science and engineering,2002,4(5):70-73.

[9]马伟锋，岑岗，李君，等.高性能遥感图像处理与空间信息网格建模[J].计算机工程.2006,32(5):283-284.

[10]郭淑琴，薛益赵，徐步汇.一种基于Hadoop的分布式地图匹配算法[J].浙江工业大学学报,2015,43(3):332-335.

[11]杨建锋，孟利民.视频监控系统中实时流媒体传输控制方法的设计[J].浙江工业大学学报,2012,40(4):454-457.

[12]张剑华，张自然等.基于结构显著性的医学图像质量评价[J].浙江工业大学学报,2015,43(6):636-641.

[13]李帆，何洪林，任小丽等.基于MapReduce的空间敏感性分析并行算法设计[J].地球信息科学学报,2014(6):874-881.

[14]赵伟彪.MPI并行空间算法在云计算平台上的迁移技术研究[D].成都：电子科技大学,2014.

[15]BROWNE P A , WILSON S. A simple method for integrating a complex model into an ensemble data assimilation system using MPI[J]. Environmental modelling & software,2015,68(6):122-128.

[16]DOBOSZ R, HURLEY R, MCCONNELL S. A hybrid openMP-MPI parallelization of structure software[J]. International journal of computer applications,2015,118(11):1-9.

(责任编辑：刘岩)

Research on data distribution strategy in parallel computing of remote sensing image

MA Weifeng1,2, LI Wei2

(1.School of Information and Electronic Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, China;2.Key Laboratory of Visual Media Intelligent Process Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The development of distributed and parallel computing technology enables rapid processing of remote sensing image possible, and data distribution strategy is the core issue in remote sensing image parallel computing. This paper analyzes the current remote sensing parallel computing and data distribution methods. Base on the current status of research work, four data distribution strategy modes are proposed such as evenly division, non-evenly division, window-based division and scale division based on calculation optimization. Moreover, the paper discusses that the four distribution strategy modes would adapt to different types of algorithms and applications. The computing speed and efficiency are analyzed theoretically for the four modes based on calculation optimization. Finally, through building MPI parallel computing environment, the four data distribution strategies are tested and analyzed The experimental results correspond to the expected theoretical analysis results. It will be useful for system construction and algorithm design of the remote sensing image parallel computing.

Keywords:remote sensing computing; parallel computing; data distribution; remote sensing image processing; distributed computing

收稿日期：2016-01-18

基金项目：浙江省可视媒体智能处理技术研究重点实验室开放基金资助项目(2012007)

作者简介：马伟锋(1979-)，男，浙江绍兴人，讲师，研究方向为分布式地学计算、智能计算及移动互联网应用等，E-mail:mawf@zust.edu.cn.

中图分类号：TP31

文献标志码：A

文章编号：1006-4303(2016)03-0270-05