This paper presents an MAP-MRF (i.e. maximum a posteriori - Markov random field) based image segmentation method to achieve stable performance without knowing the true segment number in advance. Specifically, we firstly assign the segment number a value greater than or equal to the ground truth. Subsequently, cluster centroid of each segment in observation space is initialized randomly so that each pixel can be assigned the Euclidean distance-based membership. Then, a 2-D MRF is constructed on the regular pixel lattice of the interesting image. Under MAP-MRF framework, the image segmentation can be regarded as a labeling problem with the label configuration determined by the segment label of membership winner on each site. We therefore propose an iterative algorithm by optimizing the objective function to fade out the over-segmentation, through which an optimal segmentation is achieved. Finally, an unsupervised lip segmentation scheme based on the proposed method is presented. Experiment shows its outstanding performance.