Parallel image segmentation with level set methods

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 boundary 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 multidimensional system into a series of independent one dimensional systems, each composed of multiple tridiagonal systems. Functional parallelism is made possible by this decomposition and within each one dimensional processing step, data parallelism is achieved by solving the independent 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 segmentation 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 processors gives improved computational time with speedup of over 3 for 2-phase image segmentation.