Fuzzy constraint satisfaction problem for model-based image interpretation

Scene interpretation guided by a generic model benefits from structural representations of objects and their spatial relationships. In this paper, we consider nested conceptual graphs for encoding objects and groups of objects, spatial relationships between objects or between groups of objects, along with the imprecision and uncertainty attached to the formal representations of such relationships. Scene interpretation is then formalized as a graph homomorphism problem for the identification of possibly multiple instances of the model in an image. We propose an extension of fuzzy constraint satisfaction problems (FCSP) to deal with complex objects. In particular, we extend FCSP arc-consistency checking to deal with groups of objects which can be related among them or have a spatial property such as being aligned. The instantiations of the model in the image are obtained by solving a FCSP. This framework is illustrated on the example of interpretation of Earth observation images. A method is proposed to find the instantiations of a nested conceptual graph, representing a generic model of the scene (such as harbor or airport) in an unlabeled image. Experimental results on high resolution satellite images show that the proposed approach successfully recognizes a given spatial configuration and is robust to image segmentation errors. The results demonstrate the interest of using complex spatial relations for the interpretation of images.