In medical applications, segmentation has become an ever more important task. One of the competitive schemes to perform such segmentation is by means of pixel classifica-tion. Simple pixel-based classification schemes can be im-proved by incorporating contextual label information. Var-ious methods have been proposed to this end, e.g., iterative contextual pixel classification, iterated conditional modes, and other approaches related to Markov random fields. A problem of these methods, however, is their computational complexity, especially when dealing with high-resolution images in which relatively long range interactions may play a role. We propose a new method based on Kriging that makes it possible to include such long range interactions, while keeping the computations manageable when dealing with large medical images. 1.