分布式并行遥感图像处理中的数据划分

文/王玉坤

信息时代背景下，各种复杂性的应用技术被广泛应用。其中数据处理的海量性是大规模复杂应用系统的特点之一。其中该系统应用最为常见的领域是在地球科学分析上。主要目的是遥感监测重大自然灾害，以便可以在决策系统的参考下，制定对策加以解决。数学分析模型在遥感和地理信息系统中的应用将遇到不断膨胀的大型空间数据库。在此背景下，原来传统顺序处理模式已经不能满足当前形势发展的需求，难以满足数据运算要求。针对目前的情况需要加强对分布式并行遥感图像处理中数据划分的研究。以便在实现处理技术高效运行的基础上，降低原有成本。

1 遥感数字图像处理关键技术特点分析

遥感数字图像处理技术在地球科学分析领域被广泛应用。作为地球科学分析领域中关键性技术之一，具有内在并行性的特点。提高实时处理海量数组图像系统的实用化需要建立集群分布式并行的微机、工作站图像处理系统。其中以下是对该技术特征分析。首先，较大的计算量。遥感数字图像处理技术具有计算量大的特点。再者，相同的计算形式。除了边界之外，任何数据点上的计算形式是相同的。都是将原有一个区域分成许多个区域。这样的区域划分可以将问题转变成许多个小规模的区域，形成小区域子问题。最后，局部的变量间相互作用。我们可以对其按照以下的方式进行理解，在计算所有数据点时，可以利用小距离内邻近点值。大计算量可以满足该技术的客观需求。相同计算形式的特点和局部变量间相互作用的特点可以满足并行处理的要求。以上特点共同满足分布式并行处理的要求。其中共享存储系统和消息传递系统是分布式系统的两种形式。消息传递系统可以在对消息传递仔细设计下，提高传递效率，但是此种形式的传递系统编程不简单，难度较高。共享存储系统经过精心设计，它的消息传递效率与消息传递系统存在一定相似性，但是该种系统在编程上较为简单。因此共享存储系统在遥感图像处理领域市场更广。分布式共享系统存储系统中。系统完成数据之间的传递。将处理节点间的通讯尽可能减小是提高并行分布计算执行效率的前提。而要想实现对通讯量的控制，需要利用遥感图像数据进行恰当的划分。以下是笔者对共享存储系统中并行遥感图像处理技术的分析。

表1：按条带划分和按矩形块划分的净通讯量之比

图1：三种划分方式下的净通讯量(以k=4为例)

2 并行遥感图像处理和数据划分分类

2.1 并行遥感图像处理分类

域处理和点处理是图像处理常见的分类方式。但是在笔者看来，此种分类方式存在一定的不合理性。可分为点处理、线处理和域处理。其中输入元素中单纯涉及一个像素的一类图像处理称为点处理。集中在一行或者一列的一类图像处理中的输入元素为线处理。集中在一列上的线处理称为竖直线处理。输入元素集中在一行上的线处理称为水平线处理。输入元素分布在一个矩形区域内的一类图像处理称为域处理。针对以上内容，我们可以得出域处理包括线处理的内容，线处理是域处理中的个例。但是我们在域处理中分出线处理的原因是，一线处理自身带有的特殊性，方便数据划分分析。二图像处理中线处理应用较为常见，我们可以将域处理划分为线处理，采用行、列两个方向的线处理模式。此中转换可并行化这类算法。

图2：数据按结果图像平均划分

2.2 数据划分分类

水平条带、竖直条带、矩形块、不规则划分是图像数据划分四种主要形式。实际中使用最少的为不规则划分。而使用较为常见的为水平条带、竖直条带、矩形块划分。竖直线处理和水平线处理是线处理的两种情况，因此在数据划分时也需要分类划分。域处理中不管采用以上四种划分方式中的任何一种，都会涉及到远程数据调用问题，因此划分方法的选择需要根据并行计算支撑环境来定。

3 分析域处理数据划分的通讯量

3.1 通讯域和数据通讯量分析

数据通讯量是选择数据划分的方式依据。笔者看来净通讯量和实际通讯量是数据通讯量进一步细化的两种分类方式。并行运算实际需要的数据通讯量为净通讯量。并行运算过程中并行计算支撑环境实际传送的数据量称为实际通讯量。而连带通讯量是指净通讯量与实际通讯量之差。而人们通常说的通讯量可以包含以上的任何一种。数据传送的分布范围称为通讯域，实际通讯域和净通讯域是通讯域进一步划分的形式表现。

3.2 点处理、线处理和域处理数据划分净通讯量分析

矩形面积一定时，周长最短的为正方形。当k设为处理机数时，k (k≥ 4,且 k的平方根为整数)，m为待处理图像的长和宽。其中(2×n+1)×(2×n+1)为域处理范围。假设n、k比m小(n×k×2

图1中净通讯域为阴影部分，水平条带和竖直条带是划分的主要方式。净通讯量一样，但是按照矩形块划分形成的净通讯量是非常小的。采用条带划分n×m×(k-1)×2像素为净通讯量。n×m×(sqrt(k)-1)×2×2像素则是按矩形块划分成的净通讯量。经过以上净通讯量的划分比较，可以确定两者之间的净通讯量之比为(k-1)/((sqrt(k)-1)×2)。此外我们要想对按条带划分和按矩形块划分的净通讯量进行更加清楚的比较，可以采用图表的方式。见表1。

通过上述图表可以看出，在处理机数不断增加的基础上，净通讯量之比越来越高，这说明按矩形块划分优于按条带划分。消息传递系统中，程序员可以对消息传递函数进行严格控制的基础下，将消息传递函数刚好传送到所需的远程数据。因此矩形快划分方式可以优先采用。而针对复杂性的分布式共享存储系统，由于此种系统情况的复杂性，需要将实际通讯量考虑进去。

3.3 点处理、线处理和域处理实际通讯量分析

为了将应用程序员编程的难度降低，在分布式共享存储系统中，应用程序不控制远程数据传送，二是字DSM系统下完成。数据预送技术是DSM系统常采用的方式，数据传送按照页面为单位。此种情况下，实际通讯量就会远远大于净通讯量。

当P为页面大小时，为了更好的方便计算，可以化简P到以前的像素单位，其他条件一样。之后我们在对点处理、线处理和域处理三种划分方式实际通讯量进行分析。图1中连带通讯域为短线条和实心矩形块，他们划分方式为竖直条带划分，此时实际通讯量是最大的。

3.3.1 实际通讯量最大的按竖直条带划分图1b所示，将第一条带和第二条带之间远程数据调用情况进行比较分析，其他各条之间大致相同。其中最佳情况为条带的宽度大于p,实心矩形块的宽度为(p-n)。此时0为短线条长度，实际通讯量要大于或等于(n+p）×(m-1))×(k-1)×2像素。

3.3.2 实际通讯量最小的按水平条带划分

图1a所示，(p-1)像素是连带通讯域在最坏的情况，此时实际通讯量应小于或等于(n×m+(p-1))×(k-1)×2像 素。(n+ p× (m - 1) ) /(n× m+ ( p - 1) )为上述两者比值。当将一景m=10000的三波段点交叉影像为案例，设4K 字节为系统传递的页面大小n = 2,p = 4096 /3≈ 1365。此时按竖直条带划分和按水平条带划分的实际通讯量的比值比638大。同理将k=4，按矩形块划分和按水平条带划分的实际通讯量的比值比567大。由此可见水平条带划分方式是分布式共享存储系统,域处理的数据划分最先佳采用的方式。

4 进一步数据划分分析

以上平均分配的数据划分在图像增强等卷积运算中是合理的。但是将其放在图像的几何纠正等带有图像旋转的运算不太适应。如图2所示，将原始图像旋转一个角度。数据在结果图像下平均分配，此时结果图像空白地方较大，但是空白处的计算量较小。因此第二台、第三台处理机要比第一台和最后一台处理机小大的多，伴随不断增加的旋转角度，差异性也不断增大。差别达到最大的时刻为旋转角度达到45度。此时第一台和最后一台处理机运算的非空白区域只有第二台和第三台处理机的三分之一。

此时差异对系统效率会有影响，因此需要针重新调整分配任务，实现动态负载平衡。实现方法如下：原图像四个角点在结果图像上的位置按照直接法求出。此时会得到原图像在结果图像上的大致分布范围的四边形。各个处理机上平均分配这些像元。此种方法的特点是可以实现任务分配的平衡性。当原图像周边地形起伏较大的情况下，此时原图像与图2中的四边形存在较大差异，需要进一步细致划分。此时可以在求得原图像边界上每个点所在的结果图像上位置时采用直接法，以此作为再次划分依据。

5 结语

综上所述，对数据通信量进行有效控制是提高遥感图像数据并行分布处理执行效率的关键。其中将三种划分方式分成点处理、线处理和域处理三类可以将并行图像处理的数据划分分析变得更加清晰。将数据通讯量进一步划分为实际通讯量和净通信量，此时数据划分最佳方式得出。分布式共享存储系统中，可以不使用到远程数据，因此可以在点处理、线处理和域处理三种处理方式中任选其中的一种。水平处理需要采用水平条带划分，竖直线处理需要采用竖直线条带划分；其中按水平条带划分方式是域处理的数据划分优先选择的划分方式，此种数据划分方式可以将实际通讯量减少。再者，有些图像几何纠正等带有图像旋转运算问题的，不适合采用数据平均分配方式。此时需要采取非平均分配时的数据划分方法。以上就是笔者针对分布式并行遥感图像处理中数据划分问题进行的详细介绍。