Level Set Parallel Highly Accurate Evolution Based on GPU Cluster

Abstract

Abstract: We design and implement parallel level set evolution algorithm based on tensor product B-spline which improves accuracy and parallelism of level set evolution. Each step of evolution need compute B-spline coefficients. Furthermore, a parallel high approximation solver for diagonally dominant tridiagonal linear system based on exact LU decomposition is implemented, which is used to compute B-spline coefficients. Two step communications are used to remove communicating dependency, so as to communicate in parallel. As a result, it speeds up level set evolution efficiently.

Key words: B-spline, level set, hybrid parallelism, tridiagonal system

CLC Number:

TP391

YUAN Bin. Level Set Parallel Highly Accurate Evolution Based on GPU Cluster[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2016, 33(3): 253-265.

References

[1] NVIDIA.NVIDIA_CUDA_Programming_Guide[CP/OL].[2015-03-09]http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf.
[2] HOWISON M, BETHEL E W, CHILDS H. Hybrid parallelism for volume rendering on large-, multi-, and many-core systems[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(1):17-29.
[3] OSHER S, SETHIAN J. Fronts propagating with curvature dependent speed:Algorithms based on Hamilton-Jacobi formulation[J]. Journal of Computational Physics, 1988,79(1):12-49.
[4] ROSENFELD A. Edge and curve detection for visual scene anaIysis[J]. IEEE Transactions on Computers, 1971, 20(5):562-569.
[5] WITKIN A P. Scale-space filtering[C]//Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing 1984, Piscataway,NJ,USA:IEEE Press,1984:150-153.
[6] PERONA P, MALIK J. Scale space and edge detection using anisotropic diffusion[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(7):629-639.
[7] ALVAREZ L, LIONS P L MOREL J M. Image selective smoothing and edge detection by nonlinear diffusion.Ⅱ[J]. SIAM Journal on Numerical Analysis,1992,29(3):845-866.
[8] CASELLES V, KIMMEL R, SAPIRO G. Geodesic active contours[J]. International Journal of Computer Vision,1997,22(1):61-79.
[9] RUDIN L I, OSHER S, FATEMI E. Nonlinear total variation based noise removal algorithms[J]. Physica D Nonlinear Phenomena, 1992, 60(1/4):259-268.
[10] UNSER M, ALDROUBI A, EDEN M. On the asymptotic convergence of B-spline wavelets to Gabor functions[J]. IEEE Transactions on Information Theory,1992, 38(2):864-872.
[11] BRINKS R. On the convergence of derivatives of B-splines to derivatives of the Gaussian function[J]. Computational &Applied Mathematics,2008, 27(1):79-92.
[12] de BOOR C. On calculation with B-spline[J].Journal of Approximation Theory,1972,6(1):50-62.
[13] COX M G.The numerical evaluation of B-spline[J].IMA Journal of Applied Mathematics,1972,10(2):134-149.
[14] 施法中.计算机辅助几何设计与非均匀有理B样条[M].北京:北京航空航天大学出版社,1994.
[15] LARRIBA-Pey J L, NAVARRO J J, JORBA A, et al. Review of general and toeplitz vector bidiagonal solvers[J]. Parallel Computing, 1996, 22(8):1091-1126.
[16] 崔锦泰. 小波分析导论[M].程正兴,译.西安:西安交通大学出版, 1994.
[17] 何旭初,苏煜成,包雪松. 计算数学简明教程[M]. 北京:高等教育出版社, 1980.
[18] 莫则尧,袁国兴.消息传递并行编程环境[M].北京:科学出版社,2001.
[19] 袁斌.改进的均匀数据场GPU光线投射[J].中国图象图形学报,2011,16(7):1269-1275.