Summary: Recently, continuous optimization methods have become quite popular since they can deal with a variety of non-smooth convex problems. They are inherently parallel and therefore well suited for GPU implementations. Most of the continuous optimization approaches have in common that they are very fast in the beginning, but tend to get very slow as the solution gets close to the optimum. We therefore propose to apply global relabeling steps to speed up the convergence close to the optimum. The resulting primal-dual algorithm with global relabeling is applied to graph cut problems as well as to Total Variation (TV) based image segmentation. Numerical results show that the global relabeling steps significantly speed up convergence of the segmentation algorithm.