Automatic interpretation of images is of great interest. The goal is to compute a symbolic description of aspects or contents of the image. This can be seen as a general problem of pattern recognition (Ballard and Brown, 1982). A way of solving it involves labeling a set of objects such that specific constraints are satisfied. Labeling uses different kinds of constraint models (Mohr and Masini, 1988; Niemann et al., 1990; Pelillo and Refice, 1994; Rosenfeld et al., 1976). The present authors focus on knowledge representation based on semantic graphs. In this context, they consider control algorithms based on arc consistency. Mohr and Henderson (1986) presented an algorithm for arc consistency and showed that it is optimal in time complexity. This algorithm has been applied with success to a semantic graph for understanding images (Belaid and Belaid, 1992; and Benmouffek et al., 1991). However, this method only works if any two distinct regions are labeled differently. When a dataset concerns sursegmented objects without previous knowledge about this sursegmentation, this condition is missing. The present paper presents a new algorithm for arc consistency working on such data, for example, "true" three dimensional images. The analysis of this kind of information is encountered in medical imagery. The case of NMR imaging of the brain is mentioned in particular.