“A work-efficient GPU algorithm for level set segmentation” by Roberts, Sousa and Mitchell

  • ©Mike Roberts, Mario Costa Sousa, and Joseph Ross Mitchell



Entry Number: 53


    A work-efficient GPU algorithm for level set segmentation



    We present a novel GPU level set segmentation algorithm that is both work-efficient and step-efficient. Our algorithm has O(log n) step-complexity, in contrast to previous GPU algorithms [Lefohn et al. 2004; Jeong et al. 2009] which have O(n) step-complexity. Moreover our algorithm limits the active computational domain to the minimal set of changing elements by examining both the temporal and spatial derivatives of the level set field. We apply our algorithm to 3D medical images (Figure 1) and demonstrate that our algorithm reduces the total number of processed level set field elements by 16x and is 14x faster than previous GPU algorithms with no reduction in segmentation accuracy.


    Harris, M., Sengupta, S., and Owens, J. D. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3, H. Nguyen, Ed. Addison Wesley, Aug.Google Scholar
    Jeong, W.-K., Beyer, J., Hadwiger, M., Vazquez, A., Pfister, H., and Whitaker, R. T. 2009. Scalable and interactive segmentation and visualization of neural processes in EM datasets. IEEE Trans. Vis. Comp. Graphics 15, 6. Google ScholarDigital Library
    Lefohn, A. E., Kniss, J. M., Hansen, C. D., and Whitaker, R. T. 2004. A streaming narrow-band algorithm: Interactive computation and visualization of level sets. IEEE Trans. Vis. Comp. Graphics 10, 4.

ACM Digital Library Publication:

Overview Page: