Abductive reasoning for image interpretation based on spatial concrete domains and description logics

Abductive reasoning for image interpretation based on spatial concrete domains and description logics

Yifan Yang Jamal Atif Isabelle Bloch 

LTCI, Télécom ParisTech, Université Paris-Saclay, Paris, France

Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, 75016 Paris, France

Corresponding Author Email: 
yifan.yang@telecom-paristech.fr; jamal.atif@dauphine.fr; isabelle.bloch@telecom-paristech.fr
30 April 2017
| Citation



Image interpretation aims not only at detecting and recognizing objects in a scene but also at deriving a semantic description considering contextual information in the whole scene. Image interpretation can be formalized as an abductive reasoning problem, i.e. an inference to the best explanation using a background knowledge. In this work, we present a framework using a tableau method for generating and selecting potential explanations of the given image when the background knowledge is encoded in description logics, and includes concepts describing objects and their spatial relations. The best explanation is selected according to a minimality criterion based on the satisfaction degree of spatial relations between the objects, computed in concrete domains.


image interpretation, abduction, description logics, semantic tableau, spatial relations, fuzzy representations, concrete domains

1. Introduction
2. Représentation des connaissances
3. Un nouvel algorithme d’abduction reposant sur les tableaux sémantiques
4. Critère de sélection d’hypothèses guidé par l’information de l’image
5. Exemples d’illustrations
6. Conclusion

Ce travail a été financé par l’ANR (projet LOGIMA).


Atif J., Hudelot C., Bloch I. (2014). Explanatory reasoning for image understanding using formal concept analysis and description logics. IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 44, no 5, p. 552–570.

Atif J., Hudelot C., Fouquier G., Bloch I., Angelini E. (2007). From Generic Knowledge to Specific Reasoning for Medical Image Interpretation using Graph-based Representations. In International Joint Conference on Artificial Intelligence IJCAI’07, p. 224-229. Hyderabad, India.

Baader F. (2003). Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles. In International Joint Conference on Artificial Intelligence IJCAI’03, vol. 3, p. 319–324.

Baader F., Calvanese D., McGuinness D. L., Nardi D., Patel-Schneider P. F. (2003). The description logic handbook: theory, implementation, and applications. Cambridge University Press.

Baader F., Hanschke P. (1991). A schema for integrating concrete domains into concept languages. In International Joint Conference on Artificial Intelligence IJCAI'91, p. 452–457.

Bienvenu M. (2008). Complexity of abduction in the EL family of lightweight description logics. In 11th International Conference on Principles of Knowledge Representation and Reasoning (KR08), p. 220-230.

Bloch I. (2005). Fuzzy spatial relationships for image processing and interpretation: a review. Image and Vision Computing, vol. 23, no 2, p. 89 - 110.

Chein M., Mugnier M.-L. (2008). Graph-based knowledge representation: computational foundations of conceptual graphs. Springer Science & Business Media.

Colucci S., Di Noia T., Di Sciascio E., Donini F. M., Mongiello M. (2004). A uniform tableauxbased approach to concept abduction and contraction in ALN. In 17th International Workshop on Description Logics (DL), vol. 104, p. 158–167.

Coradeschi S., Saffiotti A. (2000). Anchoring symbols to sensor data: preliminary report. In AAAI conference on Artificial Intelligence, p. 129–135.

Dubois D., Prade H. (1980). Fuzzy sets and systems: theory and applications. Academic Press.

Eiter T., Gottlob G. (1995). The complexity of logic-based abduction. Journal of the ACM (JACM), vol. 42, no 1, p. 3–42.

Elsenbroich C., Kutz O., Sattler U. (2006). A case for abductive reasoning over ontologies. In OWL: Experiences and Directions, vol. 216, p. 10–20.

Fouquier G., Atif J., Bloch I. (2012). Sequential model-based segmentation and recognition of image structures driven by visual features and spatial relations. Computer Vision and Image Understanding, vol. 116, no 1, p. 146–165.

Harnad S. (1990). The symbol grounding problem. Physica D: Nonlinear Phenomena, vol. 42, no 1-3, p. 335–346.

Hobbs J. R. (2004). Abduction in natural language understanding. Handbook of pragmatics, p. 724–741.

Horrocks I., Sattler U. (1999). A description logic with transitive and inverse roles and role hierarchies. Journal of Logic and Computation, vol. 9, no 3, p. 385–410.

Hudelot C., Atif J., Bloch I. (2008). Fuzzy spatial relation ontology for image interpretation. Fuzzy Sets and Systems, vol. 159, no 15, p. 1929–1951.

Klarman S., Endriss U., Schlobach S. (2011). ABox abduction in the description logic ALC. Journal of Automated Reasoning, vol. 46, no 1, p. 43–80.

Krizhevsky A., Sutskever I., Hinton G. E. (2012). Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, p. 1097–1105.

Nempont O., Atif J., Bloch I. (2013). A constraint propagation approach to structural model based image segmentation and recognition. Information Sciences, vol. 246, p. 1–27.

Neumann B., Möller R. (2008). On scene interpretation with description logics. Image and Vision Computing, vol. 26, no 1, p. 82–101.

Neuranat. (2006). http://rprcsgi.rprc.washington.edu/neronames/.

Peirce C. (1958). Collected papers of Charles Sanders Peirce, vol. I–VI edited by C. Hartshorne and P. Weiss, 1931–1935, vol. VII–VIII edited by A. W. Burks. Havard University Press, Cambridge MA.

Peraldi S. E., Kaya A., Melzer S., Möller R., Wessel M. (2007). Multimedia interpretation as abduction. In 20th International Workshop on Description Logics, p. 323–330.

Reiter R. (1987). A theory of diagnosis from first principles. Artificial Intelligence, vol. 32, no 1, p. 57–95.

Rosse C., Mejino Jr J. L. et al. (2003). A reference ontology for biomedical informatics: the foundational model of anatomy. Journal of biomedical informatics, vol. 36, no 6, p. 478–500.

Russell B. C., Torralba A., Murphy K. P., Freeman W. T. (2008). LabelMe: a database and web-based tool for image annotation. International Journal of Computer Vision, vol. 77, no 1-3, p. 157–173.

Shanahan M. (2005). Perception as abduction: Turning sensor data into meaningful representation. Cognitive Science, vol. 29, no 1, p. 103–134.

Smeulders A. W., Worring M., Santini S., Gupta A., Jain R. (2000). Content-based image retrieval at the end of the early years. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, no 12, p. 1349–1380.

Soomro K., Zamir A. R., Shah M. (2012). UCF101: A dataset of 101 human actions classes from videos in the wild. arXiv preprint arXiv:1212.0402.

Town C. (2006). Ontological inference for image and video analysis. Machine Vision and Applications, vol. 17, no 2, p. 94–115.

Vinyals O., Toshev A., Bengio S., Erhan D. (2015). Show and tell: A neural image caption generator. In IEEE Conference on Computer Vision and Pattern Recognition, p. 3156–3164.

Waxman S. G. (2000). Correlative Neuroanatomy (24e éd.). New York, McGraw-Hill.

Zhu S.-C., Mumford D. (2006). A stochastic grammar of images. Foundations and Trends ® in Computer Graphics and Vision, vol. 2, no 4, p. 259–362.