. In this work we present a new Markov Random Field model for image binary segmentation that computes the probability that each pixel belongs to a given class. We show that if a real valued field is computed, instead of a binary one as in graph cuts based methods, then the resultant cost function has noticeable computational and performance advantages. The proposed energy function can be efficiently minimized with standard fast linear order algorithms as Conjugate Gradient or multigrid Gauss-Seidel schemes. More- over, our formulation accepts a good initial guess (starting point) and avoids to construct from scratch the new solution accelerating the computational process. Then we naturally implement computationally efficient multigrid algorithms. For applications with limited computational time, a good partial solution can be obtained by stopping the iterations even if the global optimum is not yet reached. We performed a meticulous comparison (with state of the art methods: Graph Cut, Random Walker and GMMF) for the interactive im- age segmentation (based on trimaps). We compare the algorithms using cross–validation procedures and a simplex decent algorithm for learning the parameter set.