×

Fuzzy constraint satisfaction problem for model-based image interpretation. (English) Zbl 1380.68370

Summary: 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.

MSC:

68T45 Machine vision and scene understanding

Software:

ToulBar2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atif, J.; Hudelot, C.; Fouquier, G.; Bloch, I.; Angelini, E. D., From generic knowledge to specific reasoning for medical image interpretation using graph based representations, (International Joint Conference on Artificial Intelligence IJCAI’07 (2007)), 224-229
[2] Benz, U.; Hofmann, P.; Willhauck, G.; Lingenfelder, I.; Heynen, M., Multi-resolution, object-oriented fuzzy analysis of remote sensing data for GIS-ready information, ISPRS J. Photogramm. Remote Sens., 58, 3-4, 239-258 (2004)
[3] Bistarelli, S.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G.; Fargier, H., Semiring-based CSPs and valued CSPs: frameworks, properties, and comparison, Constraints, 4, 3, 199-240 (1999) · Zbl 0946.68143
[4] Bloch, I., Fuzzy spatial relationships for image processing and interpretation: a review, Image Vis. Comput., 23, 89-110 (2005)
[5] Bloch, I.; Colliot, O.; Cesar, R., On the ternary spatial relation between, IEEE Trans. Syst. Man Cybern., Part B, Cybern., 36, 2, 312-327 (2006)
[6] Bloch, I.; Géraud, T.; Maître, H., Representation and fusion of heterogeneous fuzzy information in the 3D space for model-based structural recognition—application to 3D brain imaging, Artif. Intell., 148, 1-2, 141-175 (2003) · Zbl 1082.68789
[7] Chein, M.; Mugnier, M.-L., Graph-Based Knowledge Representation and Reasoning—Computational Foundations Conceptual Graphs, Advanced Information and Knowledge Processing (2008), Springer
[8] Ciucu, M.; Héas, P.; Datcu, M.; Tilton, J. C., Scale space exploration for mining image information content, (Mining Multimedia and Complex Data, KDD Workshop MDM/KDD 2002, PAKDD Workshop KDMCD 2002, Revised Papers (2002), Springer), 118-133
[9] Colliot, O.; Camara, O.; Bloch, I., Integration of fuzzy spatial relations in deformable models—application to brain MRI segmentation, Pattern Recognit., 39, 8, 1401-1414 (2006)
[10] Cooper, M.; Schiex, T., Arc consistency for soft constraints, Artif. Intell., 154, 1, 199-227 (2004) · Zbl 1085.68672
[11] Cooper, M. C., Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets Syst., 134, 3, 311-342 (2003) · Zbl 1031.90072
[12] Cooper, M. C.; de Givry, S.; Sánchez, M.; Schiex, T.; Zytnicki, M.; Werner, T., Soft arc consistency revisited, Artif. Intell., 174, 7, 449-478 (2010) · Zbl 1213.68580
[13] Crevier, D.; Lepage, R., Knowledge-based image understanding systems: a survey, Comput. Vis. Image Underst., 67, 2, 161-185 (1997)
[14] DeMenthon, D.; Megret, R., Spatio-temporal segmentation of video by hierarchical mean shift analysis, (Statistical Methods in Video Processing Workshop (2002))
[15] Deruyver, A.; Hodé, Y., Constraint satisfaction problem with bilevel constraint: application to interpretation of over-segmented images, Artif. Intell., 93, 1-2, 321-335 (1997) · Zbl 1017.68535
[16] Deruyver, A.; Hodé, Y.; Brun, L., Image interpretation with a conceptual graph: labeling over-segmented images and detection of unexpected objects, Artif. Intell., 173, 14, 1245-1265 (2009) · Zbl 1194.68238
[17] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty, Appl. Intell., 6, 4, 287-309 (1996) · Zbl 1028.91526
[18] Dubois, D.; Fargier, H.; Prade, H., Refinements of the maximin approach to decision-making in a fuzzy environment, Fuzzy Sets Syst., 81, 1, 103-122 (1996) · Zbl 0877.90002
[19] Dubois, D.; Fortemps, P., Computing improved optimal solutions to max-min flexible constraint satisfaction problems, Eur. J. Oper. Res., 118, 1, 95-126 (1999) · Zbl 0945.90087
[20] Fargier, H., Modèles et algorithmes pour l’aide à la décision (2006), Université Paul Sabatier: Université Paul Sabatier Toulouse, France, Habilitation à diriger des recherches
[21] Fouquier, G.; Atif, J.; Bloch, I., Sequential model-based segmentation and recognition of image structures driven by visual features and spatial relations, Comput. Vis. Image Underst., 116, 146-165 (2012)
[22] Goward, S.; Markham, B.; Dye, D.; Dulaney, W.; Yang, J., Normalized difference vegetation index measurements from the Advanced Very High Resolution Radiometer, Remote Sens. Environ., 35, 2-3, 257-277 (1991)
[23] Guo, D.; Xiong, H.; Atluri, V.; Adam, N., Object discovery in high-resolution remote sensing images: a semantic perspective, Knowl. Inf. Syst., 19, 2, 211-233 (2009)
[24] Guo, J.; Zhou, H.; Zhu, C., Cascaded classification of high resolution remote sensing images using multiple contexts, Inf. Sci., 221, 84-97 (2013)
[25] Hudelot, C.; Atif, J.; Bloch, I., Fuzzy spatial relation ontology for image interpretation, Fuzzy Sets Syst., 159, 15, 1929-1951 (2008)
[26] Hudelot, C.; Maillot, N.; Thonnat, M., Symbol grounding for semantic image interpretation: from image data to semantics, (Tenth IEEE International Conference on Computer Vision Workshops, 2005, ICCVW’05 (2005), China: China Beijing)
[27] Le Ber, F.; Lieber, J.; Napoli, A., Les systèmes à base de connaissances, (Akoka, J.; Comyn Wattiau, I., Encyclopédie de l’informatique et des systèmes d’information (2006), Vuibert), 1197-1208
[28] Lecoutre, C.; Roussel, O.; Dehani, D., WCSP Integration of soft neighborhood substitutability, (Milano, M., Principles and Practice of Constraint Programming. Principles and Practice of Constraint Programming, Lecture Notes in Computer Science (2012), Springer: Springer Berlin, Heidelberg), 406-421
[29] Liu, Y.; Zhanga, Y.; Gaoa Gnet, Y., A generalized network model and its applications in qualitative spatial reasoning, Inf. Sci., 178, 2163-2175 (2008) · Zbl 1136.68367
[30] McFeeters, S., The use of the Normalized Difference Water Index (NDWI) in the delineation of open water features, Int. J. Remote Sens., 17, 7, 1425-1432 (1996)
[31] Metzger, J.; Le Ber, F.; Napoli, A., Modeling and representing structures for analyzing spatial organization in agronomy, (de Moor, A.; Lex, W.; Ganter, B., Conceptual Structures for Knowledge Creation and Communication. Conceptual Structures for Knowledge Creation and Communication, 11th International Conference on Conceptual Structures, ICCS 2003, vol. 2746 (2003), Springer, Dresden, Germany), 215-228
[32] Möller, R.; Näth, T. H., Implementing probabilistic description logics: an application to image interpretation, (Cohn, A. G.; Hogg, D. C.; Möller, R.; Neumann, B., Logic and Probability for Scene Interpretation, Dagstuhl Seminar Proceedings (2008), Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Germany: Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Germany Dagstuhl, Germany), 1862-4405
[33] Myint, S. W.; Gober, P.; Brazel, A.; Grossman-Clarke, S.; Weng, Q., Per-pixel vs. object-based classification of urban land cover extraction using high spatial resolution imagery, Remote Sens. Environ., 115, 5, 1145-1161 (2011)
[34] Nempont, O.; Atif, J.; Bloch, I., A constraint propagation approach to structural model based image segmentation and recognition, Inf. Sci., 246, 1-27 (2013) · Zbl 1320.68203
[35] Papadopoulos, G. T.; Saathoff, C.; Escalante, H.; Mezaris, V.; Kompatsiaris, I.; Strintzis, M., A comparative study of object-level spatial context techniques for semantic image analysis, Comput. Vis. Image Underst., 115, 9, 1288-1307 (2011)
[36] Paris, S.; Durand, F., A topological approach to hierarchical segmentation using mean shift, (IEEE Conference on Computer Vision and Pattern Recognition. IEEE Conference on Computer Vision and Pattern Recognition, CVPR07 (2007)), 1-8
[37] Perchant, A.; Bloch, I., Fuzzy morphisms between graphs, Fuzzy Sets Syst., 128, 2, 149-168 (2002) · Zbl 1005.05041
[38] Rosenfeld, A.; Hummel, R.; Zucker, S., Scene labeling by relaxation operations, IEEE Trans. Syst. Man Cybern., 6, 6, 420-433 (1976) · Zbl 0335.68070
[39] Saathoff, C.; Staab, S., Exploiting spatial context in image region labelling using fuzzy constraint reasoning, (WIAMIS ’08: Proceedings of the 2008 Ninth International Workshop on Image Analysis for Multimedia Interactive Services. WIAMIS ’08: Proceedings of the 2008 Ninth International Workshop on Image Analysis for Multimedia Interactive Services, Washington, DC, USA (2008)), 16-19
[40] Sebari, I.; He, D.-C., Automatic fuzzy object-based analysis of VHSR images for urban objects extraction, ISPRS J. Photogramm. Remote Sens., 79, 171-184 (2013)
[41] Smeulders, A. W.; Worring, M.; Santini, S.; Gupta, A.; Jain, R., Content-based image retrieval at the end of the early years, IEEE Trans. Pattern Anal. Mach. Intell., 22, 12, 1349-1380 (2000)
[42] Sowa, J. F., Conceptual Structures: Information Processing in Mind and Machine (1984), Addison-Wesley · Zbl 0536.68077
[43] Sowmya, A.; Trinder, J., Modelling and representation issues in automated feature extraction from aerial and satellite images, ISPRS J. Photogramm. Remote Sens., 55, 1, 34-47 (2000)
[44] Vanegas, M.-C., Spatial relations and spatial reasoning for the interpretation of earth observation images using a structural model (2011), Ph.D. thesis, Télécom ParisTech
[45] Vanegas, M.-C.; Bloch, I.; Inglada, J., A fuzzy definition of the spatial relation “surround”—application to complex shapes, (EUSFLAT (2011, 2011)), 844-851
[46] Vanegas, M.-C.; Bloch, I.; Inglada, J., Alignment and parallelism for the description of high resolution remote sensing images, IEEE Trans. Geosci. Remote Sens., 51, 6, 3542-3557 (2013)
[47] Yuan, J.; Li, J.; Zhang, B., Exploiting spatial context constraints for automatic image region annotation, (Proceedings of the 15th International Conference on Multimedia (2007), ACM), 595-604
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.