This paper proposes a new framework for image segmentation based on the integration of MRFs and deformable models using graphical models. We first construct a graphical model to represent the relationship of the observed image pixels, the true region labels and the underlying object contour. We then formulate the problem of image segmentation as the one of joint regioncontour inference and learning in the graphical model. The graphical model representation allows us to use an approximate structured variational inference technique to solve this otherwise intractable joint inference problem. Using this technique, the MAP solution to the original model is obtained by finding the MAP solutions of two simpler models, an extended MRF model and a probabilistic deformable model, iteratively and incrementally. In the extended MRF model, the true region labels are estimated using the BP algorithm in a band area around the estimated contour from the probabilistic deformable model, and the result in turn guides the probabilistic deformable model to an improved estimation of the contour. Experimental results show that our new hybrid method outperforms both the MRF-based and the deformable model-based methods.