Belief propagation (BP) over Pairwise Markov random field (MRF) has been successfully applied to some computer vision problems. However, Conventional Pairwise MRF model is still insufficient to capture natural image statistical characteristics. To solve this problem, we proposed an adaptive MRF model for image segmentation problem. The proposed model adaptively model the local features according to local region information of the image and the local feature parameters will be efficiently estimated. Then we develop an efficient BP algorithm for image segmentation. The convergence region messages are passed among the local regions over the proposed model. Experimental results show that the proposed BP algorithm generates more accurate segmentation results, and also can efficiently restrain effect of image noise and texture mutation for segmentation.