Image segmentation is fundamentally a discrete problem. It consists in finding a partition of the image domain such that the pixels in each element of the partition exhibit some kind of similarity. Very often, the partitions are obtained via integer optimization, which is NP-hard, apart from a few exceptions. We sidestep the discrete nature of image segmentation by formulating the problem in the Bayesian framework and introducing a set of hidden real-valued random fields informative with respect to the probability of the partitions. Armed with this model, and assuming a supervised scenario, the original discrete optimization is converted into a convex problem, which is solved efficiently using the SALSA solver. In the semi-supervised scenario, we are lead to a nonconvex problem which is addressed with alternating optimization. The effectiveness of the proposed methodology is illustrated in simulated and real segmentation problems.