基于CUDA的二值图像连通域快速标记算法改进研究

摘要

二值图像连通域标记是指将二值图像中通过给定规则相互连接的像素附上同样的标记，而相互不连接的像素附上不同标记的处理过程。二值图像连通域标记在机器人视觉，人脸识别等相关领域有着重要的应用。二值图像连通域快速标记算法是在CPU(Central Processing Unit)上进行一次光栅扫描标记后采用集合合并方式处理等价类的一种算法，该算法在以CPU为处理核心的算法中是效率最高和最具鲁棒性的算法。但是与其他现有标记算法相比该算法的效率和性能提升幅度比较有限。本文以并行处理为出发点，设计和实现了一种并行的二值图像连通域标记算法来提高二值图像连通域标记问题的处理效率。
　　GPU(Graphic Processing Unit)是显卡的“心脏”，由于现代计算机对图像处理要求越来越高，特别是计算机系统对于2D和3D图像的实时处理主要依赖于GPU的图像处理能力。当前可编程GPU具有卓越的计算功率和非常高的存储器带宽，可以被认为是一种高度并行化、多线程和多核的处理器。CUDA(Compute Unified Device Architecture)是NVIDIA公司提出的一种新的实现GPU通用计算的软硬件架构。通过CUDA架构编程人员可方便的使用类似C语言的代码启动大量的GPU线程实现并行工作。本文所设计的算法以CUDA架构为基础，并以CUDA C为编程语言，实现二值图像连通域标记问题的并行处理。
　　通过二值图像连通域标记问题的可并行化分析，设计出了一种完全基于GPU内核多线程并行运行的二值图像连通域标记算法。该算法的输入为PBM(Portable Bitmap Image)格式二值图像文件，经过I/O(Input/Output)初始化后将二值图像文件格式化为由4个特定位置像素为一最小连接体，以最小连接体为元素的矩阵描述原始图像。通过对图像描述矩阵进行初次标记，一次和反推标记和循环等价标记三个完全并行步骤后实现了对二值图像连通域标记问题的处理。该算法最终输出为对应的标记值矩阵和连通域数目。
　　在算法设计基础上编程实现了二值图像连通域并行标记算法，并以CUDA代码的优化措施为参考对应用程序进行了优化。对应用程序进行了实验验证和效率分析，得出了算法的加速比和鲁棒性数据。最终实验结果显示本研究所设计的算法相对于二值图像连通域快速标记算法具有明显的效率优势。该算法能够在任何具有支持CUDA的GPU的计算设备上运行，具有较高的经济性和可实现性。算法的设计达到了研究的预期目标。

目录

摘要

1 绪论

1．1 研究的目的及意义

1．2 国内外研究发展状况

1．3 本文的主要工作及内容安排

2 二值图像连通域标记原理及相关并行计算技术

2．1 二值图像连通域标记

2．1．1 PBM图像

2．1．2 二值图像的表示

2．1．3 四连接体和八连接体

2．1．4 二值图像连通域标记

2．2 二值图像连通域快速标记算法的分析

2．2．1 二值图像连通域标记一般算法

2．2．2 二值图像连通域快速标记算法

2．2．3 算法效率及瓶颈分析

2．3 相关并行计算技术

2．3．1 并行计算机

2．3．2 集群计算技术

2．3．3 GPU通用计算

2．3．4 并行计算技术对比分析

2．4 本章小结

3 并行标记算法设计

3．1 现代GPU的并行计算能力

3．2 二值图像连通域标记问题的可并行化分析

3．2．1 同一连通域中像素具有共同“顶点”

3．2．2 单像素和四像素标记一致

3．3 二值图像连通域并行标记算法的设计

3．3．1 图像预处理

3．3．2 首次标记

3．3．3 一次和反推标记

3．3．4 循环等价标记

3．3．5 后续处理

3．4 本章小结

4 基于CUDA的并行标记算法实现

4．1 CUDA编程模型与接口

4．1．1 内核

4．1．2 线程层次

4．1．3 存储器层次

4．1．4 异构编程

4．1．5 编程接口

4．2 CUDA架构的硬件实现

4．2．1 SIMT

4．2．2 硬件多线程

4．3 并行标记算法的实现

4．3．1 主机端实现

4．3．2 设备端实现

4．4 本章小结

5 并行标记算法优化及实验分析

5．1 并行标记算法优化

5．1．1 算法优化措施与应用

5．2 算法标记实验分析

5．2．1 算法正确性测试

5．2．2 算法效率测试分析基于GT520M GPU

5．2．3 算法效率测试分析基于Tesla K20 GPU

5．3 非并行算法与并行算法效率对比

5．4 算法稳定性分析

5．5 本章小结

6 全文总结与展望

6．1 全文工作总结

6．2 未来工作展望

致谢

参考文献

攻读学位期间发表的学术论文目录

声明