基于超像素的遥感图像并行分割算法∗

李 帅 韩俊岗 范 望 张恩泽

（1.西安邮电大学研究生学院 西安 710121）（2.西安电子科技大学研究生学院 西安 710126）

1 引言

卫星遥感技术的迅速发展，使得遥感图像的分辨率大幅度提高，从而显著推动了遥感技术在各个领域的应用。实地调查和人工解译方法对区域尺度的地物进行处理费时费力，因此，探索快速、高效的高分辨率影像数据处理与信息提取方法，已成为当前遥感研究领域的一个重要研究课题［1］。

在2003 年，Ren［2］等首先提出了超像素这个概念。Gould［3］，Fulkerson［4］，Yang［5］等利用超像素提取特征，直接做物体识别，在PASCAL VOC Challenge 取得了很好的名次。Mori［6］等则利用超像素做人体动作方面的检测，构造超像素的过程实际上是一种粗糙的图像分割。

国内外对于图像分割与研究已久，各种方法层出不穷。近年来随着研究的日益深入，一些新的效率较高的方法也不断出现。

对于图像分割技术来说，目前常用的方法主要有基于阈值的分割、聚类法、基于能量函数的分割、基于图论的分割和分水岭算法等分割方法［7］。

基于阈值的分割算法常常是通过设定不同的阈值，依据影像灰度值把像元分为不同灰度级的目标区域和背景区域，这种方法比较简单、计算量小，但当场景较为复杂时，算法性能较差。为提升阈值的自适应性，Otsu［8］提出最大类间方差法，该算法利用图像中的灰度直方图，以目标与背景之间的方差最大而动态地确定图像分割阈值，但该方法采用穷举法，计算速度较慢。

聚类分割算法中应用比较广泛的主要有谱聚类 方 法 和K-means 方 法，陈 作 炳［8］等 首 次 采 用K-means 方法对CT 数据进行分割处理，实现了轮廓提取，Bezdek［9］提出了FCM 算法，又称模糊C 均值，该方法通过引入样本到聚类中心的隶属度，确定样本所属区域，实现图像分割。聚类分割算法的优点是计算较为简单，但初始参数值对于分割的影响较大。

基于图论的分割算法是近年来应用较为广泛的图像分割方法之一。 主要方法有GC（Graph-Cut）［10］、NC（Normalized Cuts）［11］、RW（Random Walks）［12］、GS（Graph-Based Segmentation）［13］的分割算法。基于图割的分割算法的优点是分割精度较高，不足之处在于算法效率普遍较低。

分水岭算法［14］是目前在图像分割中广泛被应用的一种算法，其优点在于分割精度高，结果准确，但是其缺点也比较明显，在分割过程中，很容易出现过分割现象，且其算法效率较低。因此，为了提高遥感图像的识别能力，寻找一种精度高、速度快的分割算法是图像分割领域目前面临的重要问题［15］。

传统分割算法自身空间复杂度较高，需要将海量遥感图像数据一次性调入内存并进行分析与处理，不仅降低了分割的速度，甚至会使整个系统异常中断，进而严重限制了其实际应用。本文利用现如今计算机多核的优势，利用OpenMPI，提出了一种并行分割方案，使得分割时间有了提高，增大了其实际应用范围。

2 本文工作

本文提出一种快速精确且工程易实现的遥感图像并行分割方法，旨在解决传统串行分割的时间消耗多、占用空间大的问题。本文融合了假彩色图像生成、并行分割、区域异质性评价，边界合并处理，游程码压缩存储等技术，既保证了分割边缘的精度，又提高了分割速度，有利于算法的工程应用。其具体步骤如下。

步骤1:计算各波段的图像熵，选择信息量最大的四波段，预处理后合成假彩色图像；

步骤2:对假彩色图像进行带状分块；

步骤3:设定分割区域参数和终止条件，对分块后的子图像进行并行SLIC分割；

步骤4:建立分块边界的上下区域邻接关系图，设计区域合并准则，对区域进行合并，并更新区域标签；

步骤5:对全图的合并区域进行标签重组，采用游程码的方法压缩存储分割结果。

2.1 假彩色图像合成

1）计算各个波段的图像熵，选择熵值最大的四个波段，此处采用图像的一元灰度熵作为图像熵的衡量单位，计算公式如下:

式中，pi是某个灰度在该图像中出现的概率，可由灰度直方图获得。

2）对所选的四个波段分别统计其亮度直方图，进行阈值为2%的截断拉伸；

3）提取直方图累计概率位于2%和98%的亮度值，作为线性归一化的下、上限，对该范围内的所有像元归一化到［0，255］；

4）将图像从RGB空间变换到XYZ空间:

5）然后将图像从XYZ空间变换到ST空间:

式中:

6）最后将图像从ST 空间变换为HLC 空间，生成假彩色图像。

2.2 分块理论

遥感图像有着“数据可分”的优点，所以可以将遥感图像根据一定的规则进行分块，分解成一定数量并且相互独立的图像块，按照要求分配给多个线程，各线程独立读取分割图像块，进行处理并写入，直到结束。

分块机制是处理大内存遥感图像常用策略。在其大数据处理中，数据并行是最常见的处理模式，如图1和图2所示，此机制利用虚拟的网格将遥感图像分成若干块并分配到相互独立的子线程中。具体方法如下。

1）影像分块并编号

根据遥感图像及其投影获得影像的分块边界，将影像从上到下分成若干个大小相同的矩形子图像；若下边界的剩余部分不够平均分块的大小，则保留剩余块的大小。对分块后的影像，按照从上到下的顺序进行编号。

图1 影像分块过程图

2）分配子线程

每个子线程都有相同的划分方法，根据分块策略获得各自对应编号的子图像。假设有n 个线程，第i个线程要处理的子图像的编号就是i。

3）分块处理

子线程按照编号从小到大顺序处理各个图像，并把处理结果保存下来，像主线程发送完成消息，直到所有子图像处理完毕为止。

图2 智能分块器工作原理图

2.3 图像分割

1）设置SLIC 分割的参数，包括分割最小因子，预期种子点个数；

2）对SLIC分割算法进行OpenMP并行改造，应用并行编译指令#pragma omp parallel for 优化循环工作；

程序中最耗时的当属循环语句，OpenMP 对循环做了优化，编译指令#pragma omp parallel for就是循环优化的注释语句，当有其作用时，for 循环的工作就会被分配给一组线程进行执行，每个线程会承担一定任务，则程序由原来的串行模式转变为并行模式。

3）在Visual Studio编译器中，打开项目的“属性页”栏，展开“配置属性”，展开“C++”，将“语言”栏中“OpenMP 支持”选项改成“是”，并在源代码文件中加入头文件“omp.h”；

4）根据分块策略获得对应编号的子图像，每个子线程按照编号从小到大顺序处理各子图像，保存处理结果，向主线程发送完成消息，直到所有子图像处理完毕为止。

2.4 边界缝合算法

2.4.1 区域异质性

相邻区域的异质性，与两个区域的颜色特性和形状特性相关。所以计算方式为

Z 代表相邻区域的权值，w 表示光谱特性所占的权值，h(color)为光谱异质性公式，h(shape)为形状异质性公式，总的异质性是这两部分的加权。计算公式如下:

式中，σobj1和σobj2分别表示两个区域对象的方差，nobj1和nobj2为为两个区域对象的像素个数，nmerge表示合并后对象像素个数，σmerge表示合并后对象的方差。

式中，ωcmpct为紧凑度权值，取值0 到1 之间，为紧凑度异质性表示平滑异质性，l 表示区域边界长度，n 表示区域个数，b 表示区域最小外接矩形周长。

2.4.2 边界区域邻接图

边界区域邻接图描述分块后子图像分割结果的边界区域邻接关系，在图3 中，图3（a）表示两个相邻分块的边界处的区域标签，图3（b）表示图3（a）对应的边界区域邻接图。

具体步骤如下。

Step 1:扫描分割后的分块边界，确定边界区域的节点标签；

Step 2:根据分割边界的空间位置关系，建立边界处的节点关系；

Step 3:根据区域异质性的定义，计算节点区域的权值Z；

Step 4:边界区域邻接图建立完成。

2.4.3 边界合并处理步骤

根据分块边界处建立的邻接图，就可以根据合并准则进行边界区域的分割处理其具体步骤如下。

Step 1:根据分块处边界上区域和下区域空间位置关系，建立边界邻接图；

Step 2:按照从左到右的顺序依次遍历邻接图中上区域的节点；

Step 3:找出上区域节点相邻的下区域节点；

Step 4:判断下区域所有相邻边的权值是否在设置的区域异质性阈值范围内，如果在，将下区域的节点标签更新成上区域标签，并重新计算该标签区域的属性值。

Step 5:重复Step 2，3，4 步骤，直到所有的上区域节点处理完成，则结束。

图3 边界标签和区域邻接图

2.5 图像存储算法

1）对所有分块的边界进行区域合并后，对全图的标签进行连续化整理，使标签值从0 开始且连续；

2）将分割区域采用游程码的方式进行压缩存储；

3）如图4 所示，首先保存图像文件信息头、图像大小和分割区域个数，然后根据实际的分割结果，以游程码结构，保存每一行的分割区域标签。N1表示分割结果第一行不同游程码的个数，NM表示分割结果第M行不同游程码的个数。

图4 游程码存储图

3 实验结果与分析

3.1 实验环境

3.1.1 硬件环境

系统:Windows7

CPU:Intel（R）Core（TM）i3-4170 四核

主频:3.7GHz

内存:8G

3.1.2 软件环境

Visual Studio 2010软件

OpenMP支持

3.2 实验评价

并行计算效率常用的评价方法有很多种，如执行时间、加速比等。

3.2.1 执行时间

对于并行分割算法来说，其执行时间是衡量算法的性能指标之一，其主要包括2 个部分:并行执行时间和串行执行时间。并行执行时间是所有线程完成全部工作所消耗的时间。串行执行时间是程序串行执行的时间。

3.2.2 加速比

加速比是串行执行时间与并行执行时间的比值，它是评价并行分割算法最重要的指标。

3.3 实验方案

3.3.1 并行实验方案

为了检测并行分割算法的提速效果，本文设计了并行实验方案，具体内容如下。

1）实验数据

采用Landsat8 卫星图像作为原图像，将原图像进行裁剪，生成14 个不同尺寸的图像，具体见表2.3。

2）对实验用到的14 个影像数据进行数据分块；

3）采用串行的方式分别对14 个影像数据的分块子影像进行分割，每组分割数据统计20 次，然后去每组的平均值作为其对应串行时间；

4）对分割算法进行OpenMP 并行改造，然后将14 个硬性数据的分块数据交给多线程执行，每组进行10次实验，然后记录并行执行时间；

5）对获得的结果进行耗时评价。

3.3.2 边界合并算法实验方案

为了检测边界合并算法的有效性，本文设计了以下实验方案，具体内容如下。

1）实验数据具体见表1；

2）对所选三个实验影像，利用本章改进算法进行分割，不进行边界合并，记录实验结果；

3）对三个实验影像，利用本章算法进行分割，进行边界合并，记录实验结果；

4）对比实验结果并分析。

表1 边界合并算法实验数据参数列表

3.3.3 分割精度对比实验方案

为了验证本分割算法的有效性，本文设计了不同算法对比实验方案，具体内容如下:

1）实验数据具体见表2；

表2 分割精度对比实验数据参数列表

2）对所选四个实验影像，利用本章改进算法进行分割，记录实验结果；

3）对所选四个实验影像，利用易康软件的多尺度分割算法进行分割，记录实验结果；

4）对比实验结果并分析。

3.4 实验结果分析

3.4.1 并行实验结果分析

根据并行实验方案，结果见表3，串行执行时间与并行执行时间的对比折线图见图5，加速比折线图见图6。

通过实验分析可以得到以下结论:

1）从图5 可以看出，对于SLIC 分割算法，串行执行时间与并行执行时间相似，与遥感图像大小近似成线性关系。

2）由于程序执行中，存在数据读取和存入时间，还有SLIC算法存在大量不可进行OpenMP并行改造的循环语句，所以在图6 中，加速比一直维持在1.9 上下波动，在四核CPU 下，没有完全发挥OpenMP 在多核下的加速作用，所得的加速比低于理想情况下的加速比。

表3 串行与并行时间对比表

图5 串行与并行时间对比图

图6 加速比与其平均值对比图

3.4.2 边界合并算法实验结果分析

以下展示了三个不同影像的分割结果数据边界合并处的局部放大图，图7（a）为Landsat8遥感图像未进行边界处理的分割结果图，图7（b）为Landsat8 遥感图像进行边界合并处理的分割结果图；图8（a）为SPOT5 遥感图像未进行边界处理的分割结果图，图8（b）为SPOT5 遥感图像进行边界合并处理的分割结果图；图9（a）为SPOT6 遥感图像未进行边界处理的分割结果图，图9（b）为SPOT6 遥感图像进行边界合并处理的分割结果图。

图7 Landsat8遥感图像分割结果对比图

图8 SPOT5遥感图像分割结果对比图

图9 SPOT6遥感图像分割结果对比图

从图7、图8 和图9 中，在进行合并处理前，存在很明显的分界线，进行合并处理后，已经消除了图（a）中存在的分界线，由于合并前，合并后采用相同的分割方法和相同的分割参数，所以选择的分割区域不存在太多的区别，由此，该实验实现了边界合并算法的正确性和有效性的验证。

3.4.3 分割精度对比实验结果分析

以下展示了四个不同遥感图像使用不同分割算法的分割结果局部放大图，图10（a）为Landsat8遥感图像使用易康多尺度分割结果图，图10（b）为Landsat8 遥感图像使用改进算法分割结果图；图11a 为SPOT5 遥感图像使用易康多尺度分割结果图，图11（b）为SPOT5 遥感图像使用改进算法分割结果图；图12（a）为SPOT6 遥感图像使用易康多尺度分割结果图，图12（b）为SPOT6 遥感图像使用改进算法分割结果图。图13（a）为GF1遥感图像使用易康多尺度分割结果图，图13（b）为GF1 遥感图像使用改进算法分割结果图。

图10 Landsat8遥感图像不同算法分割结果对比图

图11 SPOT5遥感图像不同算法分割结果对比图

图12 SPOT6遥感图像不同算法分割结果对比图

图13 GF1遥感图像不同算法分割结果对比图

根据不同分割算法的实验结果，对其计算对应的错分率和区域数比，其具体如表4。

从图10、图11、图12 和图13 中可以很明显地看出，同一影像，使用本章分割算法得到的实验结果图，能够找到正确的边缘，然而，使用易康自带的多尺度分割算法得到的实验结果图，都存在欠分割的情况，不能找到正确的边缘。图13 中显示GF1影像的分割局部放大图，使用多尺度分割，对图中右下角深绿色岛屿目标的分割边缘明显不正确。表4 统计了不同算法的错分率和区域数比，很显然，本章改进分割算法在保持区域数比与多尺度分割算法一致的前提下，错分率更低，分割更准确。以上验证了基于超像素的遥感图像并行分割算法的有效性。

表4 不同算法分割结果评价指标统计表

4 结语

本文引入了遥感图像并行的思想，在SLIC 分割算法的基础上，做了相应的改进，利用遥感图像数据可分的特征，提出遥感图像数据分块理论和基于区域邻接图的边界合并算法，设计出基于超像素的遥感图像并行分割算法；最后，根据并行实验方案和边界合并算法实验，验证了本算法在遥感图像分割领域的正确性和有效性。