Image labeling is a process of recognizing each segmented region properly exploiting the properties of the regions and the spatial relationsships between regions. In some sense, image labeling is an optimization process of indexing regions using the constraints as to the scene knowledge. In this paper, we further investigate a method of efficiently labeling images using the Markov Random Field (MRF). MRF model is defined on the region adjacency graph and the labeling is then optimally determined using the simulated annealing. To endow the adaptability to the MRF-based image labeling, we have proposed a parameter estimation technique based on error backpropagation. We analyze the proposed method through experiments using the real natural scene images.