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

doi:10.19678/j.issn.1000-3428.0058298

摘要/Abstract

摘要： 针对传统种子填充算法无法充分利用多核处理器性能以及需要人工指定种子的不足，提出基于动态连接和并查集的并行随机种子反向填充算法。将填充任务分为随机种子生成、并行填充、连通区域识别、并行合并与反转步骤，并采用C++和CUDA-C语言分别实现各步骤的CPU和GPU版本。在此基础上，从众多参数组合中选择能发挥硬件最佳性能的参数。实验结果表明，相比传统反向填充算法，并行随机种子反向填充算法能充分利用多核、异构处理器的多线程并行能力，在处理6种不同分辨率的单张和批量图像时获得了平均3.84倍和4.43倍的加速比，其中在处理8 KB高分辨图像时，最高取得6.05倍和7.09倍的加速比。

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

Abstract: 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.

Key words: region filling, seed filling, high-resolution image, multithreading, Union-Find algorithm, conversely filling algorithm

中图分类号:

TP391

曹建立, 陈志奎, 王宇新, 郭禾. 高分辨图像区域填充的并行计算方法[J]. 计算机工程, 2021, 47(9): 217-226,234.

CAO Jianli, CHEN Zhikui, WANG Yuxin, GUO He. Parallel Computing Method of Region Filling for High-Resolution Images[J]. Computer Engineering, 2021, 47(9): 217-226,234.

http://www.ecice06.com/CN/Y2021/V47/I9/217

图/表 18

20210917192114

20210917192118

20210917192122

20210917192125

20210917192129

20210917192132

20210917192136

20210917192140

20210917192144

20210917192149

20210917192153

20210917192201

20210917192206

20210917192211

20210917192216

20210917192221

20210917192225

20210917192229

参考文献

[1] PAVLIDIS T.Filling algorithms for raster graphics[J].Computer Graphics and Image Processing, 1979, 10(2):126-141.
[2] PAVLIDIS T.Algorithms for graphics and image processing[M].Berlin, Germany:Springer, 1982.
[3] BURTSEV S V, KUZMIN Y P.An efficient flood-filling algorithm[J].Computers & Graphics, 1993, 17(5):549-561.
[4] Rogers David F.Procedural elements for computer graphics[M].2nd ed.New York, USA:McGraw-Hill Companies, 1998.
[5] FREEMAN H.On the encoding of arbitrary geometric configurations[J].IRE Transactions on Electronic Computers, 1961, 10(2):260-268.
[6] CAI Z G.Restoration of binary images using contour direction chain codes description[J].Computer Vision Graphics and Image Processing, 1988, 41(1):101-106.
[7] LIU Y, HU W X, HAN L Z.A fast filling algorithm for image restoration based on contour parity[J].Computers, Materials & Continua, 2020, 63(1):509-519.
[8] TSAI Y H, CHUNG K L.Region-filling algorithm on bincode-based contour and its implementation[J].Computers & Graphics, 2000, 24(4):529-537.
[9] 巨志勇, 陈优广.一种新的基于链码的填充算法[J].计算机工程, 2007, 33(17):211-212. JU Z Y, CHEN Y G.New filling algorithm based on chain code[J].computer engineering, 2007, 33(17):211-212.(in Chinese)
[10] LI X, HUANG L.New region filling algorithm based on chain codes description[C]//Proceedings of the 3rd International Congress on Image and Signal Processing.Yantai, China:IEEE Press, 2010:2806-2809.
[11] KAUFMAN A, COHEN D, YAGEL R.Volume graphics[J].Computer, 1993, 26(7):51-64.
[12] FENG L, SOON S H.An effective 3D seed fill algorithm[J].Computers & Graphics, 1998, 22(5):641-644.
[13] 薛斌党, 薛文芳, 姜志国.三维种子填充算法的改进[J].计算机辅助设计与图形学学报, 2006, 18(10):1553-1556. XUE B D, XUE W F, JIANG Z G.Improvement of 3D seed filling algorithm[J].Journal of Computer-Aided Design and Computer Graphics, 2006, 18(10):1553-1556.(in Chinese)
[14] YU W W, HE F, XI P.A rapid 3D seed-filling algorithm based on scan slice[J].Computers & Graphics, 2010, 34(4):449-459.
[15] SARPATE G K, GURU S K.Image inpainting on satellite image using texture synthesis & region filling algorithm[C]//Proceedings of 2014 International Conference on Advances in Communication and Computing Technologies.Washington D.C., USA:IEEE Press, 2014:1-5.
[16] ABDULADHEM A A, HUSSEIN A H.Real-time lane markings recognition based on seed-fill algorithm[C]//Proceedings of ICICT'19.New York, USA:ACM Press, 2019:190-195.
[17] 刘海峰, 张超, 罗江, 等.一种二值图像船舶目标区域快速自动化填充算法[C]//第四届中国指挥控制大会论文集.北京:电子工业出版社, 2016:647-650. LIU H F, ZHANG C, LUO J, et al.A binary image boat region fast and auto filling algorithm[C]//Proceedings of the 4th China conference on command and control.Beijing, China:Publishing House of Electronics Industry, 2016:647-650.(in Chinese)
[18] MA Y, SUN H, YE P, et al.Mobile robot multi-resolution full coverage path planning algorithm[C]//Proceedings of the 5th International Conference on Systems and Informatics.Nanjing, China:IEEE Press, 2018:120-125.
[19] 汪俊, 廖敦明, 赵建华, 等.基于种子填充算法的热节快速显示在三维铸造工艺CAD中的应用[J].铸造, 2015, 64(1):25-28. WANG J, LIAO D M, ZHAO J H, et al.Application of the seed filling algorithm to the rapid display of hot spot by 3D casting process software[J].Foundry, 2015, 64(1):25-28.(in Chinese)
[20] 陈卓, 廖敦明, 陈涛.基于扫描线的铸造气相域种子填充算法改进[J].特种铸造及有色合金, 2020, 40(1):42-46. CHEN Z, LIAO D M, CHEN T.Improvement to seed filling algorithm in casting gas phase based on scanning line[J].Special-cast and Non-ferrous Alloys, 2020, 40(1):42-46.(in Chinese)
[21] 许苗村, 蒋先刚, 李林.细小器官分割的可回溯三维种子填充新算法[J].华东交通大学学报, 2010, 27(2):71-73. XU M C, JIANG X G, LI L.A new algorithm of backtrack 3D seed filling for mini-organ segmentation[J].Journal of East China Jiaotong University, 2010, 27(2):71-73.(in Chinese)
[22] 柳朝阳.对区域填充扫描线算法的改进[J].计算机工程, 1994(S1):469-472. LIU C Y.Improvement of scan line algorithm for region filling[J].Computer Engineering, 1994(S1):469-472.(in Chinese)
[23] 任继成, 刘慎权.区域填充扫描线算法的改进[J].计算机辅助设计与图形学学报, 1998(6):2-7. REN J C, LIU S Q.Improvement of area filling scanline algorithm[J].Journal of Computer-Aided Design and Computer Graphics, 1998(6):2-7.(in Chinese)
[24] 余腊生, 沈德耀.扫描线种子填充算法的改进[J].计算机工程, 2003(10):70-72. YU L S, SHEN D Y.A refinement of the scan line seed fill algorithm[J].Computer Engineering, 2003(10):70-72.(in Chinese)
[25] VUČKOVIĆ V, ARIZANOVIĆ B, BLOND S L.Generalized N-way iterative scanline fill algorithm for real-time applications[J].Journal of Real-Time Image Processing, 2019, 16(6):2213-2231.
[26] VUČKOVIĆ V, ARIZANOVIĆ B, BLOND S L.Ultra-fast basic geometrical transformations on linear image data structure[J].Expert Systems with Applications, 2018, 91:322-346.
[27] 柳稼航, 方涛, 杨建峰.适用于任意复杂区域的全自动填充方法[J].计算机工程, 2008, 34(4):238-240. LIU J H, FANG T, YANG J F.Fully automatic area-filling method for any complicated area[J].Computer Engineering, 2008, 34(4):238-240.(in Chinese)
[28] GALLER B A, FISHER M J.An improved equivalence algorithm[J].Communications of the ACM, 1964, 7(5):301-303.
[29] NVIDIA N, GENERATION N, COMPUTE C.Whitepaper-NVIDIA's next generation CUDA compute architecture[J].ReVision, 2009, 23(6):1-22.

选择文件类型/文献管理软件名称

选择包含的内容