Fork me on GitHub

A Work-Efficient GPU Algorithm for Level Set Segmentation

Mike Roberts

Jeff Packer

Mario Costa Sousa

Joseph Ross Mitchell

University of Calgary

High Performance Graphics 2010

Figure: The progression of our algorithm while segmenting the white and grey matter in a 2563 magnetic resonance image (MRI) of a human head with a signal-to-noise ratio of 11. Our algorithm interactively computes this segmentation in 7 seconds - 14x faster than previous GPU algorithms with no reduction in accuracy.

Code | Data | Paper | Slides | Poster | WMV | MOV

Abstract: We present a novel GPU level set segmentation algorithm that is both work-efficient and step-efficient. Our algorithm: (1) has linear work-complexity and logarithmic step-complexity, both of which depend only on the size of the active computational domain and do not depend on the size of the level set field; (2) 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; (3) tracks the active computational domain at the granularity of individual level set field elements instead of tiles without performance penalty; and (4) employs a novel parallel method for removing duplicate elements from unsorted data streams in a constant number of steps. We apply our algorithm to 3D medical images and we demonstrate that in typical clinical scenarios, 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.

    author    = {Mike Roberts AND Jeff Packer AND Mario Costa Sousa AND Joseph Ross Mitchell},
    title     = {A Work-Efficient {GPU} Algorithm for Level Set Segmentation},
    booktitle = {High Performance Graphics (HPG '10)},
    year      = {2010}

Acknowledgements: We thank the anonymous reviewers for their valuable comments and suggestions. This research was supported by the iCORE/Calgary Scientific Inc. Industrial Research Chair in Medical Imaging Informatics, Alberta Innovates - Health Solutions, the Alberta Heritage Foundation for Medical Research Endowment Fund, the iCORE/Foundation CMG Industrial Research Chair in Scalable Reservoir Visualization, and the Discovery Grants Program from the Natural Sciences and Engineering Research Council of Canada.