Accelerated implementation of level set based segmentation


  • Marc J Piggott CSIRO Mathematics, Informatics and Statistics, North Ryde NSW 2113.
  • Pascal Vallotton CSIRO Mathematics, Informatics and Statistics, North Ryde NSW 2113.
  • John A Taylor CSIRO Mathematics, Informatics and Statistics, Acton ACT 2601.
  • Tomasz P Bednarz CSIRO Mathematics, Informatics and Statistics, North Ryde NSW 2113.



level set method, OpenCL, GPU, segmentation, upwinding, adaptive timestepping


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., 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.





Proceedings Computational Techniques and Applications Conference