1 背景

图像连通域标记算法是从一幅栅格图像（通常为二值图像）中，将互相邻接（4邻接或8邻接）的具有非背景值的像素集合提取出来，为不同的连通域填入数字标记，并且统计连通域的数目。通过对栅格图像中进行连通域标记，可用于静态地分析各连通域斑块的分布，或动态地分析这些斑块随时间的集聚或离散，是图像处理非常基础的算法。目前常用的连通域标记算法有1）扫描法（二次扫描法、单向反复扫描法等）、2）线标记法、3）区域增长法。二次扫描法由于简单通用而被广泛使用！

图1 连通域标记示意图

随着所要处理的数据量越来越大，使用传统的串行计算技术的连通域标记算法运行时间过长，难以满足实际应用的效率需求。随着并行计算技术的发展，利用不同的编程模型，许多数据密集型的计算任务可以被同时分配给单机多核或多机多处理器进行并行处理，从而有可能大幅度缩减计算时间。目前在集群计算领域广泛使用MPI来进行并行化，在单机领域广泛使用OpenMP进行化，本文针对基于等价对的二值图像连通域标记算法的进行了并行化设计，利用不同的并行编程模型分别实现了不同的并行算法，并通过实验对利用不同并行编程模型所实现的连通域标记算法进行了性能对比分析。

2 二次扫描串行算法思想

顾名思义，二次扫描串行算法步骤包含两部分。

2.1 第一次扫描

a）标记

b）等价关系建立

2.2 第二次扫描

利用并查集链表进行标记更新。

3 并行化策略

3.1 数据划分并行策略

二次扫描的串行算法中，非直接相邻的各像元数据之间是无关的，将图像分割为数据块后，对于各个数据块之间的主体运算也是独立无关的，可并行性较高，因此可通过对图像进行分块来加快计算时间、提高计算效率。

3.2 并行算法步骤

a）各个进程分别使用串行算法计算

b）各个进程将各块的标记值唯一化

c）生成等价对数组

d）主进程生成全局并查集链表

将1到n-1进程中比较获得的等价对数组统一发送给0进程，0进程生成并查集链表。

e）广播全局并查集链表，各进程更改标记值

主进程广播全局并查集链表，各进程接收后更新标记值。

4 程序实现

并行算法详细流程图。

MPI版本和OpenMP版本的并行算法。

5 测试准备

5.1 实验目的

a）正确性；

b）效率：测试不同连通域数目的数据、不同机器环境（单机和集群）、不同并行编程模型（MPI和OpenMP）对二次扫描并行算法效率的影响。

5.2 测试环境

a）单节点

CPU：两颗Intel(R) Quad Core E5645 Xeon(R) CPU，共12核；

内存：80GB ；操作系统：Linux CentOS 64位。

b）高性能集群（4个计算节点，1个存储节点）

CPU：两颗Intel(R) Quad Core E5645 Xeon(R) CPU，共12核；

内存：32GB；操作系统：Linux CentOS 64位；

节点间文件系统：Network File System （NFS）。

c）测试数据

两个相同数据量（ 18640×22260 ）的二值栅格图像，一个连通域为3个（简单图），一个连通域为10433个（复杂图）

6 效率测试结果

6.1 结果1：复杂图和简单图的运行时间

6.2 为什么复杂图计算时间更长？

6.3 结果2：单节点环境下，复杂图和简单图的加速比

6.4 问题1：为什么会出现超线性加速比？

原因：并查集链表的影响。

连通域标记算法很多时间用于对并查集链表进行大量查询和插入操作。

6.5 问题2：为什么复杂图比简单图加速比高？

6.6 结果3：集群环境下，复杂图和简单图的加速比

6.7 问题：为什么进程数超过12时，复杂图加速比不再上升，而简单图加速比继续上升？

6.8 结果4：OpenMP版本与MPI版本的比较？

6.9问题：为什么MPI 1个进程比OpenMP 1个线程更高效？

6.10 OpenMP开辟线程的开销？

6.11 OpenMP编译制导语句会影响编译结果？

OpenMP编译制导语句会影响编译结果，这也可以解释单线程OpenMP程序比串行程序慢这一现象。

参考文献

连通域标记算法的并行化研究，马益杭、占利军、谢传节、秦承志，《地理与地理信息科学》