author = {Aline Deruyver and Yann Hod{'e} and Luc Brun}, title = {Image interpretation with a conceptual graph: Labeling over-segmented images and detection of unexpected objects}, journal = {Artif. Intell.}, volume = {173}, number = {14}, year = {2009}, pages = {1245-1265}, ee = {http://dx.doi.org/10.1016/j.artint.2009.05.003}, bibsource = {DBLP, http://dblp.uni-trier.de}, theme="nonhierarchique", abstract={The labeling of the regions of a segmented image according to a semantic representation (ontology) is usually associated with the notion of understanding. The high combinatorial aspect of this problem can be reduced with local checking of constraints between the elements of the ontology. In the classical definition of Finite Domain Constraint Satisfaction Problem, it is assumed that the matching problem between regions and labels is bijective. Unfortunately, in image interpretation the matching problem is often non-univocal. Indeed, images are often over-segmented: one object is made up of several regions. This non-univocal matching between data and a conceptual graph was not possible until a decisive step was accomplished by the introduction of arc consistency with bilevel constraint (FDCSPBC). However, this extension is only adequate for a matching corresponding to surjective functions. In medical image analysis, the case of non-functional relations is often encountered, for example, when an unexpected object like a tumor appears. In this case, the data cannot be mapped to the conceptual graph, with a classical approach. In this paper we propose an extension of the FDCSPBC to solve the constraint satisfaction problem for non-functional relations.}