GPU implementations of a relaxation scheme for image partitioning: GLSL versus CUDA

The GPU programmability opens a new perspective for algorithms that have not been studied and used for real applications on commodity state-of-the-art hardware due to their computational expenses. In this paper, we present three implementations of a partitioning algorithm for multi-channel images, which extends an original algorithm for singlechannel images presented in the early 1990's. The segmentation algorithm is based on the information theory concept of minimum description length, which leads to the formulation of an energy functional. The optimal solution is obtained by minimizing the functional. The minimization approach follows a graduated non-convexity approach, which leads to a fully explicit scheme. As the scheme is applied to all pixels of the image simultaneously, it is naturally parallelizable. Besides the optimized sequential implementation in C++ we developed a GLSL version of the algorithm using vertex and fragment shaders as well as a CUDA version usi ng global memory, shared memory, and texture memory. We compare the performance of the implementations, discuss the implementation details, and show that suitability of this algorithm for GPU allows it to become a comparable alternative to the modern partitioning algorithm (multi-label Graph-Cuts).