Hidden Markov random fields appear naturally in problems such as image segmentation where an unknown class assignment has to be estimated from the observations for each pixel. Choosing the probabilistic model that best accounts for the observed data is an important first step for the quality of the subsequent estimation and analysis. A commonly used selection criterion is the Bayesian Information Criterion (BIC) of \citeN{schwarz} but for hidden Markov random fields, its exact computation is not tractable due to the dependence structure induced by the Markov model. We propose approximations of BIC based on the mean field principle of statistical physics. The mean field theory provides approximations of Markov random fields by systems of independent variables leading to tractable computations. Using this principle, we first derive a class of criteria by approximating the Markov distribution in the usual BIC expression as a penalized likelihood. We then rewrite BIC in terms of normalizing constants (partition functions) instead of Markov distributions, which enables us to use finer mean field approximations and derive other criteria using optimal lower bounds for the normalizing constants. To illustrate the performance of our partition function-based approximation of BIC as a model selection criterion, we focus on the preliminary issue of choosing the number of classes before the segmentation task. Experiments on simulated and real data point out our criterion as promising: it takes spatial information into account through the Markov model and improves the results obtained with BIC for independent mixture models.