Graphical models are probabilistic models defined in terms of graphs. The intuitive and compact graph representation and its ability to model complex probabilistic systems make graphical models a powerful modeling tool in various research areas. In this paper we introduce a graphical model framework for image segmentation based on the integration of Markov random fields (MRFs) and deformable models. A graphical model is constructed 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 region-contour 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. Finally, we generalize our method from 2D to 3D. Experimental results on both synthetic and real images, in both 2D and 3D, show that our new hybrid method outperforms both the MRF-based and the deformable model-based methods using onlyhomogeneous constraints.