GPU-based morphological reconstruction system

doi:10.11772/j.issn.1001-9081.2018122549

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (7): 2008-2013.DOI: 10.11772/j.issn.1001-9081.2018122549

• Advanced computing • Previous Articles Next Articles

GPU-based morphological reconstruction system

HE Xi1,2, WU Yantao1, DI Zhenwei1, CHEN Jia1

1. College of Data Science and Software Engineering, Wuzhou University, Wuzhou Guangxi 543002, China;
2. Guangxi Colleges and Universities Key Laboratory of Professional Software Technology(Wuzhou University), Wuzhou Guangxi 543002, China

Received:2018-12-26 Revised:2019-03-06 Online:2019-03-29 Published:2019-07-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61562074).

基于图形处理器的形态学重建系统

何希^1,2, 吴炎桃¹, 邸臻炜¹, 陈佳¹

1. 梧州学院大数据与软件工程学院, 广西梧州 543002;
2. 广西高校行业软件技术重点实验室(梧州学院), 广西梧州 543002

通讯作者: 陈佳
作者简介:何希(1978-),男,广西梧州人,讲师,博士,主要研究方向:并行计算、分布式计算、数据可视化;吴炎桃(1978-),女,广西苍梧人,讲师,主要研究方向:软件工程;邸臻炜(1980-),女,广西梧州人,讲师,硕士,主要研究方向:数据可视化、虚拟现实;陈佳(1982-),女,重庆人,副教授,主要研究方向:图像处理、机器学习。
基金资助:
国家自然科学基金资助项目（61562074）。

Abstract

Abstract:

Morphological reconstruction is a fundamental and critical operation in medical image processing, in which dilation operations are repeatedly carried out on the marker image based on the characteristics of mask image, until no change occurs on the pixels of the marker image. Concerning the problem that traditional CPU-based morphological reconstruction system has low computational efficiency, using Graphics Processing Unit (GPU) to quicken the morphological reconstruction was proposed. Firstly, a GPU-friendly data structure:parallel heap cluster was proposed. Then, based on the parallel heap cluster, a GPU-based morphological reconstruction system was designed and implemented. The experimental results show that compared with traditional CPU-based morphological reconstruction system, the proposed GPU-based morphological reconstruction system can achieve speedup ratio over 20 times. The proposed system demonstrates how to efficiently port complex data structure-based software system onto GPU.

Key words: Graphics Processing Unit (GPU), morphological reconstruction, parallel computing, parallel heap, parallel data structure

摘要：

形态学重建是医学图像处理中非常基础和重要的操作。它根据掩膜图像的特征对标记图像反复进行膨胀操作，直到标记图像中的像素值不再变化为止。对于传统基于中央处理器（CPU）的形态学重建系统计算效率不高的问题，提出了使用图形处理器（GPU）来加速形态学重建。首先，设计了适合GPU处理的数据结构：并行堆集群；然后，基于并行堆集群，设计和实现了一套基于GPU的形态学重建系统。实验结果表明，相比传统基于CPU的形态学重建系统，基于GPU的形态学重建系统可以获取超过20倍的加速比。基于GPU的形态学重建系统展示了如何把基于复杂数据结构的软件系统高效地移植到GPU上。

关键词: 图形处理器, 形态学重建, 并行计算, 并行堆, 并行数据结构

CLC Number:

TP302.1

HE Xi, WU Yantao, DI Zhenwei, CHEN Jia. GPU-based morphological reconstruction system[J]. Journal of Computer Applications, 2019, 39(7): 2008-2013.

何希, 吴炎桃, 邸臻炜, 陈佳. 基于图形处理器的形态学重建系统[J]. 计算机应用, 2019, 39(7): 2008-2013.

References

[1] VINCENT L. Morphological grayscale reconstruction in image analysis:applications and efficient algorithms[J]. IEEE Transactions on Image Processing, 1993, 2(2):176-201.
[2] ROBINSON K, WHELAN P F. Efficient morphological reconstruction:a downhill filter[J]. Pattern Recognition Letters, 2004, 25(15):1759-1767.
[3] ZHOU K, HOU Q, WANG R, et al. Real-time KD-tree construction on graphics hardware[J]. ACM Transactions on Graphics, 2008, 27(5):Article No. 126.
[4] HOU Q, XIN S, ZHOU K, et al. Memory-scalable GPU spatial hierarchy construction[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(4):466-474.
[5] 吴哲锋,赵福凯,刘新国.图形处理器上的表面积启发式构建KD树并行方法:中国,CN201110241419.2[P].2011-08-22.(WU Z F, ZHAO F K, LIU X G. An surface-based heuristic algorithm for constructing KD-tree on GPUs:China, CN201110241419.2[P].2011-08-22.)
[6] BENSON D, DAVIS J. Octree textures[J]. ACM Transactions on Graphics, 2002, 21(3):785-790.
[7] ZIEGLER G, DIMITROV R, THEOBALT C, et al. Real-time quadtree analysis using HistoPyramids[C]//Proceedings of the SPIE 2007 Real-time Image Processing. Bellingham, WA:SPIE, 2007:64960L.
[8] AJMERA P, GORADIA R, CHANDRAN S, et al. Fast, parallel, GPU-based space filling curves and octrees[C]//Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games. New York:ACM, 2008:10.
[9] CASTRO R, LEWINER T, LOPES H, et al. Statistical optimization of octree searches[J]. Computer Graphics Forum, 2010, 27(6):1557-1566.
[10] SUN X, ZHOU K, STOLLNITZ E, et al. Interactive relighting of dynamic refractive objects[J]. ACM Transactions on Graphics, 2008, 27(3):Article No. 35.
[11] LEFEBVRE S, HORNUS S, NEYRET F. Octree textures on the GPU[J]. GPU Gems, 2005, 2:595-613.
[12] ZHOU K, GONG M, HUANG X, et al. Data-parallel octrees for surface reconstruction[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(5):669-681.
[13] GRAHN H, LAVESSON N, LAPAJNE M H, et al. CudaRF:a CUDA implementation of random forests[C]//Proceedings of the 2011 IEEE/ACS International Conference on Computer Systems and Applications. Piscataway, NJ:IEEE, 2011:95-101.
[14] SHARP T. Implementing decision trees and forests on a GPU[C]//Proceedings of the 10th European Conference on Computer Vision. Berlin:Springer, 2008:595-608.
[15] LAUTERBACH C, GARLAND M, SENGUPTA S, et al. Fast BVH construction on GPUs[J]. Computer Graphics Forum, 2009, 28(2):375-384.
[16] 李怀明,邓仰东.基于图形处理器的高性能跳表(Skiplist)数据结构[J].微电子学与计算机,2014,31(12):1-5.(LI H M, DENG Y D. High performance Skiplist for GPU computing[J]. Microelectronics and Computer, 2014, 31(12):1-5.)
[17] ALCANTARA D, SHARF A, ABBASINEJAD F, et al. Real-time parallel hashing on the GPU[J]. ACM Transactions on Graphics, 2009, 28(5):Article No. 154.
[18] FREDMAN M L, KOMLOS J, SZEMEREDI E. Storing a sparse table with O(1) worst case access time[J]. Journal of the ACM, 1984, 31(3):538-544.
[19] PAGH R, RODLER F F. Cuckoo hashing[J]. Journal of Algorithms, 2004, 51(2):122-144.
[20] MA L, CHAMBERLAIN R D, BUHLER J D, et al. Bloom filter performance on graphics engines[C]//Proceedings of the 2011 International Conference on Parallel Processing. Piscataway, NJ:IEEE, 2011:522-531.
[21] AMOSSEN R R, PAGH R. A new data layout for set intersection on GPUs[C]//Proceedings of the 2011 Parallel and Distributed Processing Symposium. Piscataway, NJ:IEEE, 2011:698-708.
[22] LUO L, WONG M, HWU W. An effective GPU implementation of breadth first search[C]//Proceedings of the 2010 Design Automation Conference. New York:ACM, 2010:52-55.
[23] VINEET V, HARISH P, PATIDAR S, et al. Fast minimum spanning tree for large graphs on the GPU[C]//Proceedings of the 2009 Conference on High Performance Graphics. New York:ACM, 2009:167-171.
[24] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to Algorithms[M]. Cambridge, MA:MIT Press, 2009:151-153.
[25] VUILLEMIN J. A data structure for manipulating priority queues[J]. Communications of the ACM, 1978, 21(4):309-315.
[26] FREDMAN M L, TARJAN R E. Fibonacci heaps and their uses in improved network optimization algorithms[J]. Journal of the ACM, 1987, 34(3):596-615.
[27] BRODAL G S. Priority queues on parallel machines[J]. Parallel Computing, 1999, 25(8):987-1011.
[28] NAGESHWARA R, KUMAR V. Concurrent access of priority queues[J]. IEEE Transactions on Computers, 1988, 37(12):1657-1665.
[29] He X, AGARWAL D, PRASAD S K. Design and implementation of a parallel priority queue on many-core architectures[C]//Proceedings of the 2012 International Conference on High Performance Computing. Piscataway, NJ:IEEE, 2012:1-10.
[30] SATISH N, HARRIS M, GARLAND M. Designing efficient sorting algorithms for many-core GPUS[C]//Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing. Piscataway, NJ:IEEE, 2009:1-10.
[31] CEDERMAN D, TSIGAS P. A practical quicksort algorithm for graphics processors[C]//Proceedings of the 2008 European Symposium on Algorithms. Berlin:Springer, 2008:246-258.
[32] GOVINDARAJU N, GRAY J, KUMAR R, et al. GPUTerasort:high performance graphics co-processor sorting for large database management[C]//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2006:325-336.
[33] GREB A, ZACHMANN G. GPU-ABiSort:optimal parallel sorting on stream architectures[C]//Proceedings of the 2006 International Parallel and Distributed Processing Symposium. Piscataway, NJ:IEEE, 2006:Article No. 45.
[34] DAVIDSON A, TARJAN D, GARLAND M, et al. Efficient parallel merge sort for fixed and variable length keys[C]//Proceedings of the 2012 Innovative Parallel Computing. Piscataway, NJ:IEEE, 2012:1-9.

GPU-based morphological reconstruction system

基于图形处理器的形态学重建系统

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	XIE Wenbo, WEI Yongzhuang, LIU Zhenghong. Parallel implementation and analysis of SKINNY encryption algorithm using CUDA [J]. Journal of Computer Applications, 2021, 41(4): 1136-1141.
[2]	YANG Xianfeng, GUI Hongjun, FU Chunchang. F-X domain predictive filtering parallel algorithm based on compute unified device architecture [J]. Journal of Computer Applications, 2021, 41(2): 486-491.
[3]	Fan PING, Xiaochun TANG, Yanyu PAN, Zhanhuai LI. Scheduling strategy of irregular tasks on graphics processing unit cluster [J]. Journal of Computer Applications, 2021, 41(11): 3295-3301.
[4]	Zhiyang ZENG, Yan CHEN, Ke WANG. Design and implementation of parallel genetic algorithm for cutting stock of circular parts [J]. Journal of Computer Applications, 2020, 40(2): 392-397.
[5]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[6]	SHA Zongxuan, XUE Fei, ZHU Jie. Scheduling strategy of cloud robots based on parallel reinforcement learning [J]. Journal of Computer Applications, 2019, 39(2): 501-508.
[7]	WU Xuchen, PIAO Chunhui, JIANG Xuehong. Siting model of electric taxi charging station based on GPU parallel computing [J]. Journal of Computer Applications, 2019, 39(10): 3071-3078.
[8]	WANG Peng, ZHOU Yan. MPI big data processing for high performance applications [J]. Journal of Computer Applications, 2018, 38(12): 3496-3499.
[9]	HAN Litao, LIU Hailong, KONG Qiaoli, YANG Fanlin. Parallel algorithm for hillshading under multi-core computing environment [J]. Journal of Computer Applications, 2017, 37(7): 1911-1915.
[10]	JIAO Jiafeng, LI Yun. Review of typical machine learning platforms for big data [J]. Journal of Computer Applications, 2017, 37(11): 3039-3047.
[11]	JI Lina, CHEN Qingkui, CHEN Yuanjing, ZHAO Deyu, FANG Yuling, ZHAO Yongtao. Real-time crowd counting method from video stream based on GPU [J]. Journal of Computer Applications, 2017, 37(1): 145-152.
[12]	XUE Jun, DUAN Fajie, JIANG Jiajia, LI Yanchao, YUAN Jianfu, WANG Xianquan. Parallel cyclic redundancy check Verilog program generating method based on Matlab [J]. Journal of Computer Applications, 2016, 36(9): 2503-2507.
[13]	XING Shuning, LIU Fang'ai, ZHAO Xiaohui. Parallel high utility pattern mining algorithm based on cluster partition [J]. Journal of Computer Applications, 2016, 36(8): 2202-2206.
[14]	GUAN Yaqin, ZHAO Xuesheng, WANG Pengfei, LI Dapeng. Parallel algorithm for massive point cloud simplification based on slicing principle [J]. Journal of Computer Applications, 2016, 36(7): 1793-1796.
[15]	ZHAO Mingchao, CHEN Zhibin, WEN Youwei. Parallel computation for image denoising via total variation dual model on GPU [J]. Journal of Computer Applications, 2016, 36(5): 1228-1231.