Parallel Image Segmentation with Level Set Methods

M. Jeon (Korea), M. Alexander, and N. Pizzi (Canada)


level set methods, image segmentation, additive operator splitting, parallelization, OpenMP


Most PDE-based image segmentation algorithms employ an explicit scheme to solve the system equations. However, an explicit scheme has a time step constraint and also when parallelized, data dependency is unavoidable at the bound ary of the region assigned to processors, which requires communication between neighboring processors to share the boundary information. Additive Operator Splitting is a semi-implicit scheme that effectively decomposes a multi dimensional system into a series of independent one dimen sional systems, each composed of multiple tridiagonal sys tems. Functional parallelism is made possible by this de composition and within each one dimensional processing step, data parallelism is achieved by solving the indepen dent tridiagonal systems, resulting in a nested parallelism. Thus, implementation of parallelism is straightforward, and the parallel program will be subject to less communication overhead than explicit schemes. In this paper, we employ the AOS scheme for a level set formulation of the segmen tation problem, and OpenMP on a shared memory machine for its parallelization. Test results show that parallelization with OpenMP on a shared memory system with 8 proces sors gives improved computational time with speedup of over 3 for 2-phase image segmentation.

Important Links:

Go Back