In this paper, we show how Markovian strategies used to solve well-known segmentation problems such as motion estimation, motion detection, motion segmentation, stereovision, and color segmentation can be significantly accelerated when implemented on programmable graphics hardware. More precisely, we expose how the parallel abilities of a standard graphics processing unit usually devoted to image synthesis can be used to infer the labels of a segmentation map. The problems we address are stated in the sense of the maximum a posteriori with an energy-based or probabilistic formulation, depending on the application. In every case, the label field is inferred with an optimization algorithm such as iterated conditional mode (ICM) or simulated annealing. In the case of probabilistic segmentation, mixture parameters are estimated with the K-means and the iterative conditional estimation (ICE) procedure. For both the optimization and the parameter estimation algorithms, the graphics processor unit's (GPU's) fragment processor is used to update in parallel every labels of the segmentation map, while rendering passes and graphics textures are used to simulate optimization iterations. The hardware results obtained with a mid-end graphics card, show that these Markovian applications can be accelerated by a factor of 4 to 200 without requiring any advanced skills in hardware programming.