Gauss-Markov random fields have been successfully used as texture models in a host of applications,ranging from synthesis,feature extraction,classification and segmentation to query by image content and information retrieval in large image databases. An issue that deserves special consideration is the selection of the neighbourhood order (model complexity),which should faithfully reject the Markovianity of spatial interactions. Estimating the parameters for the wrong model will not capture the essential statistical properties of the texture in question: a lower order model will not be informative enough,while a higher order will clutter the description with superfluous information,fitting the noise rather than the data. We give a full Bayesian solution for estimating the model complexity,using an appropriate set of prior probabilities on the parameters. The closed-form decision criterion is derived by employing a Gaussian approximation of the posterior probability around the mode. The validity and benets of this approach are demonstrated on two important problems arising in machine vision: texture replication and image classification.