高分辨图像区域填充的并行计算方法  

Parallel Computing Method of Region Filling for High-Resolution Images

作　　者：曹建立 陈志奎[1] 王宇新[2] 郭禾[1] CAO Jianli;CHEN Zhikui;WANG Yuxin;GUO He(School of Software Technology,Dalian University of Technology,Dalian,Liaoning 116620,China;School of Computer Science and Technology,Dalian University of Technology,Dalian,Liaoning 116024,China)

机构地区：[1]大连理工大学软件学院,辽宁大连116620 [2]大连理工大学计算机科学与技术学院,辽宁大连116024

出　　处：《计算机工程》2021年第9期217-226,234,共11页Computer Engineering

基　　金：国家自然科学基金(61672123);中央高校基本科研业务费专项资金(DUT20LAB136)。

摘　　要：针对传统种子填充算法无法充分利用多核处理器性能以及需要人工指定种子的不足,提出基于动态连接和并查集的并行随机种子反向填充算法。将填充任务分为随机种子生成、并行填充、连通区域识别、并行合并与反转步骤,并采用C++和CUDA-C语言分别实现各步骤的CPU和GPU版本。在此基础上,从众多参数组合中选择能发挥硬件最佳性能的参数。实验结果表明,相比传统反向填充算法,并行随机种子反向填充算法能充分利用多核、异构处理器的多线程并行能力,在处理6种不同分辨率的单张和批量图像时获得了平均3.84倍和4.43倍的加速比,其中在处理8KB高分辨图像时,最高取得6.05倍和7.09倍的加速比。The traditional seed filling algorithms usually fail to make full use of the performance of a multi-core processor,and require manual intervention to specify seeds.To address the problem,a parallel random seed filling algorithm based on dynamic connection and Union-Find sets is designed.The algorithm divides the filling task into four stages:random seed generation,parallel filling,connected region recognition,and parallel union and reverse.C++and CUDA-C are used to implement each stage on CPU and GPU.On this basis,the optimal parameter configuration is chosen from various parameter configurations to maximize the hardware performance.The experimental results show that compared with the traditional reverse filling algorithm,the proposed algorithm can make full use of the multithreading performance of multi-core and heterogeneous processors.When processing six kinds of images of different resolutions,the proposed algorithm provides an average speedup of 3.84 times for single image processing and 4.43 times for batch image processing.Additionally,it provides a speedup of 6.05 times and 7.09 times for the processing of high-resolution images of 8KB.

关 键 词：区域填充 种子填充 高分辨图像 多线程 并查集算法 反向填充算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]