Accelerated implementation of level set based segmentation

Piggott, Marc J ; Vallotton, Pascal ; Taylor, John A ; Bednarz, Tomasz P

ANZIAM Journal, Tome 53 (2013), / Harvested from Australian Mathematical Society

Résumé

An Open Computing Language implementation of a level set solver for 2D and 3D image segmentation tasks is presented. An adaptive time stepping algorithm is implemented using an optimised parallel reduction kernel to compensate for a loss of algorithmic parallelisation. For a 2D data set (256x256) the execution is accelerated by a factor of 20 in the adaptive case and 100 in the non-adaptive case compared to a CPU implementation, facilitating real time interactive parameter tuning. For a 3D data set (384x397x41) the acceleration factors are 200 and 270 for the adaptive and non-adaptive cases, respectively. Though a single iteration of the adaptive method is slower compared to the non-adaptive scheme, it automatically enforces the Courant--Friedrichs--Lewy condition and reduces the number of user-tuned parameters while safely allowing larger time steps. Open Computing Language optimisations and techniques are discussed. References D. Adalsteinsson and J. A. Sethian. The fast construction of extension velocities in level set methods J. Comp. Phys. 148(1):2--22, 1999. doi:10.1006/jcph.1998.6090 J. F. Aujol and G. Aubert. Signed distance functions and viscosity solutions of discontinuous Hamilton--Jacobi equations Research Report, Inria, France 4507, 2002. K. N. Chaudhury and K. R.Ramakrishnan. Stability and convergence of the level set method in computer vision Patt. Rec. Lett. 28:884--893, 2007. doi:10.1016/j.patrec.2006.12.003 S. De Weerdt. Animal models: Towards a myeloma mouse Nature 480(7377):S38--S39, 2011. doi:10.1038/480S38a P. F. Felzenszwalb and D. P. Huttenlocher. Distance transforms of sampled functions Cornell Comp. Inf. Sci. TR2004-1963, 2004. J. Gomes and O. Faugeras. Reconciling distance functions and level sets J. Vis. Comm. Image Rep. 11:209--223, 2000. doi:10.1006/jvci.1999.0439 Khronos Group. The open standard for parallel programming of heterogeneous systems. http://www.khronos.org/opencl/, 17/10/2012. M. Harris et al. Optimizing parallel reduction in CUDA Proc. of ACM SIGMOD 21(13):104--110, 2007. D. Lee, I. Dinov, B. Dong, B. Gutman, I. Yanovsky and A. W. Toga. CUDA optimization strategies for compute---and memory---bound neuroimaging algorithms Comp. Meth. Prog. Biomed. 106:175--187, 2012. doi:10.1016/j.cmpb.2010.10.013 C. Li, C. Xu, C. Gui and M. D. Fox. Level set evolution without re-initialization: a new variational formulation IEEE Conf. Comp Vision and Pattern Recognition 1:430--436, 2005. doi:10.1109/CVPR.2005.213 A. E. Lefohn, J. M. Kniss, C. D. Hansen and R. T. Whitaker. A streaming narrow-band algorithm: interactive computation and visualization of level sets IEEE Trans. Vis Comp Graphics 10(4):422--433, 2004. doi:10.1109/TVCG.2004.2 R. Malladi, J. A. Sethian and B. C. Vermuri. Shape modeling with front propagation: a level set approach IEEE Trans. Patt. Analy. Mach. Int. 17(2):158--175, 1995. doi:10.1109/34.368173 S. Osher and N. Paragios. Geometric level set methods in imaging, vision, and graphics. Springer 2003. S. Osher and J. A. Sethian. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton--Jacobi formulations J. Comp. Phys. 79:12--49, 1988. doi:10.1016/0021-9991(88)90002-2 J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn and T. J. Purcell. A survey of general-purpose computation on graphics hardware Computer Graphics Forum 26(1):80--113, 2007. doi:10.1111/j.1467-8659.2007.01012.x J. A. Sethian. Level Set Methods and Fast Marching Methods Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge Monographs on Applied and Computational Mathematics (3), $2$nd Ed, 1999. J. Strain. Semi-Lagrangian methods for level set equations J. Comp. Phys 151(2):498--533, 1999. doi:10.1006/jcph.1999.6194 K. R. Varshney and A. S. Willsky. Classification using geometric level sets J. Machine Learning Research 11:491--516, 2010. http://dl.acm.org/citation.cfm?id=1756006.1756020

Détail

Publié le : 2013-01-01
DOI : https://doi.org/10.21914/anziamj.v54i0.6323