HACID M Mohand-Saïd

M Ladjel

Yahia Chabane

Keywords: ontological queries, relaxation reasoning, semantic medical image retrieval, polyp ontology

Je tiens à remercier mon directeur de thèse Mr. Farouk TOUMANI de m'avoir accepté et pour son suivi, ses orientations et ses précieux conseils, et qui a su me faire profiter de sa grande expérience. Je remercie mon encadrant Mr. Christophe REY pour son aide et sa disponibilité. Je remercie Mme. Hélène JAUDOIN, d'avoir acceptée de faire partie

Textual data are very limited for information representation. Therefore, multimedia technology, mainly images, are increasingly used. Works in this research area are multiple [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF][START_REF] Christopher | Introduction to Information Retrieval[END_REF] and the problems are various [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF][START_REF] Mohammed Lamine Kherfi | Image retrieval from the world wide web: Issues, techniques, and systems[END_REF][START_REF] Meghini | A model of multimedia information retrieval[END_REF]. Image databases now represent very large volume of information but they are unfortunately poorly exploited. Querying and managing image databases is becoming a big challenge in computer science world. To effectively manage and use these image databases, an image retrieval system is required. This is why it has become a very important area for a long time. An image retrieval system manages access to several images, the images are represented and indexed according to the used approach and compared using various approaches to generated queries using specific techniques. In summary, an image retrieval system manages the image representation, the query construction and the selection of images.

In the medical domain, images are increasingly produced in large quantities. These images are stored for long durations, the hospitals must keep an images database measured in tera bytes. Images are becoming increasingly important and necessary for some medical practices such as diagnoses, report writing and teaching. Management and access to these images become capital but also complex. Important decisions are taken based on these images like for example, the gastroenterology [START_REF] Chabane | Medical data management in the SYSEO project[END_REF][START_REF] Chabane | Semantic gastroenterological images annotation and retrieval -reasoning with a polyp ontology[END_REF], where physicians, by exploiting past experiences try to retrieve images of previously treated cases similar to the present treated case to decide whether they remove a type of tumor called a polyp or not.

Medical images are commonly targeted by image retrieval systems and the medical domain is one of the main application cited by Content Based Image Retrieval (CBIR) systems [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF][START_REF] Arnold | Content-based image retrieval at the end of the early years[END_REF], but the most current access to medical images [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF] is based on the patient's ID and other characteristics present in a DICOM (Digital Imaging and COmmunications in Medicine) file. DICOM [START_REF]Dicom, digital imaging and communications in medicine[END_REF] is a standard for the exchange of medical images, information about patients and other information (concerning the examination for example) which are stored with the image in the same file. These files are stored and managed by systems called PACS (Picture Archiving and Communication System).

The SYSEO project is one of the projects supported by the ANR 1 in the framework of the technologies for the health and the autonomy (TecSan) program. It deals mainly with problems of data management domain, medical images domain and human computer interaction domain. This project aims at addressing several challenges underlying the production, the storage, the retrieval, the sharing and the manipulation of medical images. It introduces a software solution to improve the quality of gastroenterology examination by comparing the images taken during the examination with the old images of the patient and proposes a collaborative platform for mutual assistance between physicians. This software solution is also used for the images archiving, the teaching and the patient monitoring.

The medical practices and the particularity of the gastroenterology domain is one of the challenges of the SYSEO project. Images, for example, are acquired, interpreted and operated directly by the physician in real time. The chain of the process proposed by SYSEO, must respect the constraints of the gastroenterology domain and the examinations, like the real time constraint and the confidentiality of the patients data, to preserve the very limited duration of an examination and the number of treated patients per day and protect the patients data. This work investigates one of the challenges of SYSEO project, which is semantic image retrieval. Indeed, we propose to physicians an effective and flexible semantic gastroenterological images annotation and retrieval system based on a new polyp ontology system. This system is mainly used for teaching, research and diagnoses. The problems of ontology construction, image annotation using an ontology, reasoning on an ontology are scrutinized and a description logics approach based is proposed. Description logics [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] are used as formalism to construct the polyp ontology, represent images and for reasoning about knowledge. A polyp ontology is constructed which will be used by an image retrieval system. This ontology is the knowledge base of the system, it is used to define the representation of an image and the important elements of gastroenterology as standard classifications of polyps and for reasoning about all these definitions. Semantic medical image retrieval generally uses medical ontologies. The purpose of medical ontologies is to provide a common vocabulary with formal definitions. These 1 Agence Nationale de la Recherche. http://www.agence-nationale-recherche.fr/ definitions can be used to represent images and medical assessments. It helps to standardize the interpretation of medical images for better treatment. The challenges of these approaches are: the tradeoff between the expressivity of image representations and reasoning performance in terms of relevance and computation time, adapted interfaces to medical domain and conditions of the examinations and the construction of ontology (reuse ? adapt ? create ? ...) and its maintenance for approaches based on ontologies.

The context of medical domain and medical practices is very complicated and special, there is a gap between the theoretical approaches and the implemented systems. Several powerful techniques in other domains have not been tested. For example, the non utilisation of user feedback [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF] justified by their absence due to the medical practices and the very limited time. Another example is the lack of investment in interfaces adapted to the working conditions [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF]. The evaluation techniques and benchmarks are also lacking in the medical domain, although in 2004 a medical image retrieval task was added to ImageCLEF which is a part of the Cross Language Evaluation Forum (CLEF) [4].

Main contributions

In this thesis, two main problems are investigated: a semantic gastroenterological image retrieval and a relaxed answers for ontological queries. The main contributions of the work are structured as follows:

1. WRelaxation A new approach is proposed for computing relaxed answers of ontological queries based on a notion of an edit distance of a given individual w.r.t. a given query. Such a distance is computed by counting the number of elementary operations needed to be applied to an ABox in order to make a given individual a correct answer to a given query. The considered elementary operations are added to or removed from an ABox, assertions of the form of an atomic concept (or its negation) and/or atomic roles. The main goal is to increase the number of concepts instances according to some defined criteria. In particular, we investigate:

• WRelaxation by considering separately the individuals: The general idea is to determine the minimum knowledge to add to or to remove from an ABox so that a given individual can be considered as an instance of a given concept. Such a quantity of knowledge is defined by counting the elementary operations performed over the Abox.

The individuals are integrated into the instances of a concept one by one.

• WRelaxation by considering a set of individuals: After having presented the limits of the integration of individuals one by one, we redefine the WRelaxation by taking into account the interaction between the elementary operations which allow to integrate each individual. The objective is to form a single consistent ABox which allows for the integration of a set of individuals in the relaxation of a given concept.

• Algorithms for decision problems: we explore a decision problem related to deciding the existence of W operations needed to make a given individual a instance of a given concept C, and we reduce these problems to known problems of checking the consistency of an ABox w.r.t. a T Box.

• Algorithms for optimisation problems: we study some optimisation problems, related to the computation of the minimal distance W, needed to make a given individual a instance of a given concept C, and related to computation of relaxed answers by considering a set of individuals, in the case of the three WRelaxation. We propose three algorithms inspired from tableau algorithm to solve some optimisation problems, related to the computation of the minimal distance W.

• Application of WRelaxation: we present the utilisation of WRelaxation with a medical images ontology to improve the semantic images retrieval and to enrich and/or to correct an existing images annotations database.

Semantic gastroenterological image retrieval

We propose and implement a semantic gastroenterological images annotation and retrieval system based on a new polyp ontology to help physicians, to decide whether they remove a polyp or not. The system includes:

• Ontology: It represents the knowledge base of the system, and it is used to define the representation of an image and the important elements of gastroenterology as standard classifications of polyps and for reasoning about all these definitions (WRelaxation, classification, instance retrieval, etc.).

We use description logics as formalism to define the polyp ontology. The knowledge collected about polyps is used for diagnosing cancer which is based 1.3. Organization of the thesis on the analysis of polyps present in an organ. The principle is to clearly identify the type and the state of the polyp by retrieving its standard classes used in gastroenterology.

• Annotation: An annotation (or query) of an image is manually generated using an interactive interface. We use semantic information to describe the content of the image, i.e., concepts, individuals or roles of the polyp ontology.

• Reasoning: we have implemented in our system three types of reasoning: a standard reasoning which is the instance retrieval and two other reasonings, a local subsumees retrieval and a local subsumers retrieval which are a slight modifications of the standard subsumption reasoning. These reasonings allow us to make a classification and an image retrieval.

Organization of the thesis

This thesis is organized as follows:

Chapter 2 This chapter presents the foundations of description logics, which include the syntax, two assumption semantics, the reasoning and the monotony property.

Chapter 3 This chapter introduces the two main techniques of image retrieval, the different facets of image retrieval, then the medical image retrieval and an overview of a semantic image retrieval using description logics, and finally, the proposed approach of semantic gastroenterological images retrieval based on a new polyp ontology.

Chapter 4 We highlight our main contribution in this chapter, which is a new reasoning for computing relaxed answers of ontological queries. We start by presenting the motivations and the general idea of our reasoning. Then, the definition of our reasoning and its implementation in the medical domain. Finally, we compare our reasoning with other approaches.

Chapter 5 In this chapter, a decision and optimization problems for WRelaxation are described, algorithms to solve these problems are proposed.

Chapter 6 This chapter is the conclusion of the thesis, we synthesizes and summarizes the major perspectives of this work.

Chapter 2

Foundations of Description Logics

Introduction

Description logics (DL) are a knowledge representation and reasoning formalism [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] heavily used in semantic web area. DL form the basic of Web Ontology language (OWL) [START_REF] Owl | the web ontology language[END_REF], one of the main standards in semantic technologies. When modelling knowledge using DL, we define sets of elements and relations between these elements. The elements are called individuals, the sets of elements are concepts, and the sets of pairs of elements are roles.

For description logics, a domain of interest is defined by: an extentional part, which is a set of individuals organized in/by an intentional part, which is a set of concepts and roles. A concept is a category of individuals. The concepts can be defined using We present in this chapter the syntax and semantics of a very expressive DL, namely the ALCHOQ(¬) language (see the section 2.6 for DL languages) [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. A language L 1 is more expressive than another language L 2 if all knowledge bases of L 2 can be defined in L 1 and there exist a knowledge base of L 1 that cannot be defined in L 2 [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. There is a trade-off between expressiveness of a language and the complexity of reasoning in this language. Reaching a good compromise between the expressiveness of the language and reasoning about language has always been a challenge for knowledge representation languages [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF].

Introductory example

Let a DL based knowledge base KB = (T , A) represented in SerieA and the concept SerieA is subsumed by the concept F ootballChampionship then the individual serieA_2014 is also instance of the concept F ootballChampionship. Note also that the two instances of a role are generally individuals but the second may not be an individual. We can use concrete domains, which include integers, real, etc. For the axiom "winU ef aChLeagueCup(acM ilan, 1994)", 1994 is not an individual but an integer.

We have illustrated in this example that the knowledge of a domain can be defined and represented by a set of concepts, of roles and of individuals. Now, we present in detail the components of a description logic system. A description logic system is defined by the knowledge base together with reasoning algorithms (exploitation of the knowledge base). The knowledge base (TBox and ABox) is defined using a language which includes constructors, axioms and used semantics. Reasoning algorithms are techniques for knowledge exploitation of a knowledge base to deduce (infer) implicit knowledge.

Syntax

The syntax of a description logic language includes the definition of role constructors, of concept constructors and the definition of role axioms, of concept axioms and of individual axioms. The sets of concept names, of role names and of individual names are respectively denoted N C , N R and N I . We now present the syntax of different parts of the ALCHOQ(¬) language which is used in the next chapter.

TBox

The T Box of a knowledge base contains all concepts and roles, their definitions and their axioms. The concepts (or roles) are defined using other concepts (roles) and concepts (or roles) constructors. Some concepts (or roles) have not a formal definitions, they are called atomic or primitive concepts (or roles). An atomic concept (or role) is intuitive, it is defined by the set of individuals which it represents and is used to formally define other concepts.

The ALCHOQ(¬) T Box defines one role constructor which is the role complement.

Let R be a description role. S = ¬R is a new role defined using the role complement.

Let A be an atomic concept, C and D two concept descriptions, R a role, i 1 , ..., i n individuals and n an integer. Concept descriptions in ALCHOQ(¬) are formed using the concept constructors of Table 2.2. The first two constructors are interesting for the reasonings, they respectively define the most general concept of the terminology and the empty concept. The third constructor defines a concept that cannot be defined using other concepts or roles. The other constructors use operators, concepts and roles to define concepts. The semantics of these constructors is given in the section 2.4.

The ALCHOQ(¬) T Box defines two concept axioms and two role axioms: • The role equality axiom and the role inclusion axiom. We can define by the role inclusion axiom a role hierarchy. Let R and S be two role descriptions. R S is a role inclusion axiom. For this axiom, S is a more general role than R. All R couples are also S couples. The role equality axiom defines equivalence relations between roles. R ≡ S defines equivalence relation between R and S. All R couples are also S couples and all S couples are also R couples.

ABox

The ABox of a knowledge base contains all assertional axioms (individual axioms). Let C be a concept description, R be a role description, i and j be two individuals. The individual axioms of ALCHOQ(¬) are listed in Table 2.3. The first and second axioms are used respectively to define the instances of a concept and the instances of a role.

The two following axioms are used to define the individuals non-instance of a concept and the individuals non-instance of a role. The last two axioms define the equality and the non-equality between individuals, which are very useful for reasoning on the concepts defined with operators like qualified restrictions, value restriction etc.

Individual axioms Name

C(i) Concept assertion R(i, j) Role assertion ¬C(i) Negated concept assertion ¬R(i, j) Negated role assertion i = j Individuals equality i = j Individuals difference

Table 2.3: Individual axioms of ALCHOQ(¬)

We define below some functions that are used throughout this thesis:

• Conc: returns all concepts of a given T Box.

• Ind: returns all individuals of a given ABox.

• InsR: returns all instances of a given concept, i.e.,

InsR(C, KB) = { a ∈ Ind(A) | KB |= C(a)}

DL Languages

A description logic language is defined by the set of its role axioms, concept axioms, individual axioms and the set of its concept constructors and role constructors. The basic DL language is AL [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]. A concept description of AL can be an atomic concept, a top concept, a bottom concept, a negation of atomic concept, an intersection of two concept descriptions. A concept description [START_REF] Hacid | Dynamic discovery of e-services. In 18èmes Journées Bases de Données Avancées[END_REF] could also be formed using a value restriction or a limited existential quantification. All roles of AL are atomic. AL can be extended by adding concept or role constructors. Generally, each extension is assigned a letter or a symbol. For concept constructors, the letters/symbols are written after the starting AL, for role constructors, the letters/symbols are written between parentheses at the end of the language name. For example, ALCHOQ(¬) is an extension of AL by adding the concept complement (C), the role hierarchy (H), the nominals (O), the qualified number restrictions(Q) and the role complement.

A description logic complexity navigator is proposed in [START_REF] Zolin | Description logic complexity navigator[END_REF]. DL languages are formed by selecting a set of constructors and axioms. The name of the formed language is also given.

Among the most popular DL languages, we cite the DL-Lite family [START_REF] Calvanese | Dl-lite: Tractable description logics for ontologies[END_REF][START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The dl-lite family[END_REF]. The DL-Lite family is a hierarchy of DL languages. It captures the main notions of both ontologies and conceptual modeling formalisms used in databases and software engineering. The core language of this family is DL-Lite core . Its syntax is the basic syntax of the whole family, all other languages are derived from this language (extension of the set of constructors or/and the set of axioms).

Let A be an atomic concept, P be an atomic role, P -be the inverse of the atomic role P , C be a general concept, E be a general role and B be a basic concept, that is an atomic or a concept of the form ∃R, where R is a basic role, that is an atomic role or the inverse of an atomic role.

Concepts and roles of DL-Lite core language are formed according the following syntax [START_REF] Calvanese | Dl-lite: Tractable description logics for ontologies[END_REF]: The DL-Lite R extends DL-Lite core with the role inclusion axiom of the form: R E (R is a basic role and E is a general role). DL-Lite R is a strict subset of OWL Lite [START_REF] Owl | the web ontology language[END_REF].

B -→ A | ∃R R-→ P | P - C -→ B | ¬B E-→ R | ¬R The DL-Lite core T Box
The DL-Lite F extends DL-Lite core with the ability of specifying functionality on roles or on their inverses, of the form: (funct R) where R is a basic role. DL-Lite F can be seen as an extension of the ontology language RDFS [START_REF]Rdf, the resource description framework[END_REF].

Let L be a DL language, we denote by L-concept a concept expressed using L. Similarly, we denote by L-TBox (L-ABox) a TBox (an ABox) which all of these axioms are expressed using L, and by L-KB a knowledge base KB = (T , A) if T is a L-T and A is a L-A.

Semantics

The semantics of a DL is given in terms of interpretations, where an interpretation I is defined by [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• an interpretation domain Δ I which defines the elements of the domain which are represented by the knowledge base.

• an interpretation function . I which assigns to every element (concept, role or individual) of the knowledge base an element of the interpretation domain Δ I :

assigning for every individual name a ∈ N I an element a I ∈ Δ I from the interpretation domain.

assigning for every concept name A ∈ N C a set of elements A I ⊆ Δ I from the interpretation domain.

assigning for every role name r ∈ N R a set of ordered pairs of elements r I ⊆ Δ I × Δ I from the interpretation domain.

The interpretation function is extended to ALCHOQ(¬) concept description by the inductive definitions of Table 2.4 [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF].

Concept constructors Semantics

⊥ ⊥ I = ∅ I = Δ I A A I ⊆ Δ I ¬C (¬C) I = Δ I \ C I C D (C D) I = C I ∩ D I C D (C D) I = C I ∪ D I ∃R.C (∃R.C) I = {x ∈ Δ I | ∃y : (x, y) ∈ R I ∧ y ∈ C I } ∀R.C (∀R.C) I = {x ∈ Δ I | ∀y, (x, y) ∈ R I → y ∈ C I } nR.C ( nR.C) I = {x ∈ Δ I | Card({y ∈ C I | (x, y) ∈ R I }) n} nR.C ( nR.C) I = {x ∈ Δ I | Card({y ∈ C I | (x, y) ∈ R I }) n} one-of (i 1 , ..., i n ) one-of (i 1 , ..., i n ) I = {i I 1 , ..., i I n } Table 2.4: Semantics of ALCHOQ(¬)
The semantics of the other components is given in terms of satisfiability. An interpretation I satisfies a [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• concept inclusion axiom C D iff C I ⊆ D I • concept equality axiom C ≡ D iff C I = D I • role inclusion axiom R S iff R I ⊆ S I • role equality axiom R ≡ S iff R I = S I • concept assertion axiom C(a) iff a I ∈ C I • role assertion axiom R(a, b) iff (a I , b I ) ∈ R I
• T Box T iff it satisfies every axiom of T .

• ABox A iff it satisfies every assertion of A.

• ABox A with respect to a T Box T iff in addition to satisfying A, it satisfies T .

• knowledge base KB = (T , A) iff it satisfies both T and A. The entailment in DL aims at making explicit the implicit knowledge. Two semantics are defined for the entailment in the context of description logics, the open world assumption (OWA) [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] and the closed world assumption (CWA) [START_REF] Drew | Non-monotonic logic I[END_REF][START_REF] Antoniou | Nonmonotonic reasoning[END_REF][START_REF] Gries | Generalized closed world reasoning in description logics with extended domain closure[END_REF]. OWA and CWA are two standard assumptions upon which entailments in a DL system may be based.

If
The difference is that for the CWA, any knowledge which cannot be entailed is false, but for OWA, any knowledge which cannot be entailed may be true. For the same knowledge base, we can entail different knowledge depending on which assumption is made.

Open World Assumption Semantics

Open world assumption is a widely used semantic in the context of description logics. An

ABox

Closed World Assumption Semantics

Closed world assumption semantics is illustrated by the databases theory [START_REF] Minker | On indefinite databases and the closed world assumption[END_REF][START_REF] Abiteboul | Foundations of Databases[END_REF]. Knowledge must be explicitly represented or inferred. Anything that is not inferred is considered false.

Classical entailment model [START_REF] Gries | Generalized closed world reasoning in description logics with extended domain closure[END_REF] To tackle this problem, the generalized closed world assumption (GCWA) is proposed in [START_REF] Gries | Generalized closed world reasoning in description logics with extended domain closure[END_REF]. GCWA is a generalization of CWA which ensures the consistency of a knowledge base.

Let KB = (T , A) be a consistent DL based knowledge base and let AS be the set of all assertions of the form A(a) or R(a, b) with A an atomic concept and R an atomic In this thesis, we use the context of the Open World Assumption (OWA) and the Generalized Closed World Assumption (GCWA) approaches.

Reasoning Tasks

Reasoning means making explicit the implicit knowledge that is logically inferred from the knowledge contained in a T Box and an ABox. The four properties are related to one another. If the language allows, a property can be reduced to another. Generally, the reasoning algorithms are implemented for one property and derived for the other properties.

Reasoning Tasks for Concepts

For two concepts C and D, if the language provides the intersection operator " " and contains the unsatisfiable concept "⊥", we have the following reduction to subsumption [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• C is unsatisfiable ⇔ C ⊥.
• C and D are equivalent ⇔ C D and D C.

• C and D are disjoint ⇔ C D ⊥.
The reduction to unsatisfiability is possible if the language provides the intersection operator and the negation operators; for two concepts C and D, we have [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• C is subsumed by D ⇔ C ¬D is unsatisfiable.
• C and D are equivalent ⇔ both (C ¬D) and (¬C D) are unsatisfiable.

• C and D are disjoint ⇔ C D is unsatisfiable.

Reasoning Tasks for ABoxes

Reasoning tasks for ABoxes are about individuals which are the extensional part of the knowledge base. The main ABox properties which are sources of inferences are [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]: The modelization of a domain is performed manually by humans, it is important to check the consistency of this modelization. Indeed, the description of a domain should not be contradictory. This verification is carried out by testing the consistency of the ABox.

• Consistency: An ABox A is consistent w.r
An inconsistent ABox entails a false knowledge, which will make the system useless.

A reasoning problem for concepts can be reduced to a reasoning problem for ABoxes.

For example, the concept satisfiability problem can be reduced to an ABox consistency problem, we have [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• C is satisf iable if f A ∪ {C(a)} is consistent.
The concept instantiation and the role instantiation are an instance checking problem which is based on an ABox inference. It is the check whether an assertion α is entailed by an ABox A w.r.t. a T Box T i.e. A |= T α.

We can reduce this problem if the language allows, to the consistency problem for ABox.

We have [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]:

• A |= C(a) if f A ∪ {¬C(a)} is inconsistent.
We now present two reasoning approaches for ABoxes. The first reasoning is the instance retrieval which is based on instance checking. The second reasoning is a relaxation reasoning which aims at relaxing a logical inference.

Instance Retrieval

Let KB = (T Box, ABox) be a description logic based knowledge base. The instance retrieval problem [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF][START_REF] Baader | The instance problem and the most specific concept in the description logic EL w.r.t. terminological cycles with descriptive semantics[END_REF][START_REF] Horrocks | Reasoning with individuals for the description logic SHIQ[END_REF][START_REF] Horrocks | The instance store: DL reasoning with large numbers of individuals[END_REF] consists in finding all individuals names i of ABox that are instances of a given concept C (i.e., testing whether KB |= C(i), for i ∈ ABox).

A trivial instance retrieval algorithm, for a concept C, checks for every individual i of the ABox, if the knowledge base entails the assertion C(i). Optimization techniques, tools and techniques from database and logic programming are also used for this problem [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Hustadt | Reasoning in description logics by a reduction to disjunctive datalog[END_REF][START_REF] Gottlob | Ontological queries: Rewriting and optimization[END_REF][START_REF] Motik | A comparison of reasoning techniques for querying large description logic aboxes[END_REF].

Variants of instance retrieval

Variants of instance retrieval [START_REF] Ecke | Answering instance queries relaxed by concept similarity[END_REF][START_REF] Schaerf | Tractable reasoning via approximation[END_REF][START_REF] Stuckenschmidt | Partial matchmaking using approximate subsumption[END_REF] are reasonings which have the same kinds of inputs and outputs of a classical instance retrieval. The difference is that the inference process is modified.

Variants approaches are generally motivated by two main reasons:

• To improve the performance of reasoning or eliminate a constructor or axioms: an example of these approaches is the transformation of descriptions expressed in an expressive language into descriptions expressed in a less expressive language [START_REF] Pan | Approximating OWL-DL ontologies[END_REF][START_REF] Brandt | Approximation and difference in description logics[END_REF][START_REF] Pan | Completeness guaranteed approximations for OWL-DL query answering[END_REF][START_REF] Yuan Ren | Soundness preserving approximation for tbox reasoning[END_REF][START_REF] Yuan Ren | Towards soundness preserving approximation for abox reasoning of OWL2[END_REF]. These approaches are called generally approximation.

• To expand query answers: the goal here is to find sound answers of a given query and also other answers close to the sound answers w.r.t. some constraints or measures [START_REF] Ecke | Answering instance queries relaxed by concept similarity[END_REF][START_REF] Schaerf | Tractable reasoning via approximation[END_REF][START_REF] Stuckenschmidt | Partial matchmaking using approximate subsumption[END_REF][START_REF] Stuckenschmidt | Approximate subsumption for complex description logics[END_REF]. These approaches are generally called relaxations.

The DL Family

The DL family are the different DL languages. We presented in Section 2.3 some DL languages defined by the set of constructors and axioms they allow. Other extensions have been investigated such as the use of concrete domains, the temporal DL, the fuzzy DL, the probabilistic DL, the non-monotonic DL, etc.

According to the monotony property, the DL languages can be classified into two main families: monotonic DL and non-monotonic DL. We use both families in this thesis.

Monotonic DL

Reasoning in a knowledge representation formalism is monotonic [START_REF] Grimm | Semantic Matchmaking with Nonmonotonic Description Logics, volume 1 of Studies on the Semantic Web[END_REF] iff, for two knowl- A Description Logic is monotonic if reasoning in this logic is monotonic.

Description logics with classical semantics (OWA) are monotonic and with CWA are nonmonotonic [START_REF] Knorr | Local closed world reasoning with description logics under the well-founded semantics[END_REF][START_REF] Grimm | Matching semantic service descriptions with local closed-world reasoning[END_REF][START_REF] Grimm | Semantic Matchmaking with Nonmonotonic Description Logics, volume 1 of Studies on the Semantic Web[END_REF].

Example 2 Let KB = (T , A) be the knowledge base of Reasoning in the context of OWA approach is monotonic.

Non-monotonic DL

Non-monotonic description logics languages are languages where a reasoning could infer a knowledge which can be revised. The introduction of new knowledge can invalidate old inferred knowledge. These logics are useful for modeling systems where the response is necessary even though the information are incomplete.

Database theory was one of the earliest area on which the formalization of nonmonotonic descriptions logic has been inspired, in particular with the closed world assumption. We use in this thesis the non-monotonic description logics in the context of the closed world assumption. For description logics, reasoning in the context of closed world assumption is non monotonic.

Example 3 Let KB = (T , A) be the knowledge base of Table 2.1. We have KB |= gcwa ¬Man(f ederer) but KB∪{P erson(f ederer)} |= gcwa ¬Man(f ederer)

Reasoning in the context of GCWA approach is non monotonic.

Conclusion

In this chapter, we introduced the fundamental notions of description logics as our main contribution is based on it. Description logics structure the world in hierarchy and create relations between the objects of this world.

Among the fundamental notions introduced, the semantics of the closed world in description logics is presented. This semantic is not standard but it is well suited to the medical application domain and thus our work.

A description logics language is defined by its syntax (constructors and axioms) and its semantics. The choice of a language is guided by a need for expression but must comply with the constraints of decidability and complexity of the reasoning used for the language.

The more the language is expressive, the more the reasoning is difficult. We have chosen to present in this chapter the syntax and the semantics of ALCHOQ(¬) language as it will be used in the next chapter. ALCHOQ(¬) is a very expressive language but decidable in the case of standard reasoning. We have chosen to define with precision a medical knowledge.

We will see in the next chapter the first step of our work, which is to use the description logics to represent the medical knowledge and images of the gastro-enterology and to develop a semantic gastroenterological images annotation and retrieval system.

Chapter 3

A Description Logic Based Approach

For Semantic Image Retrieval

Introduction

Textual data are very limited for information representation. Therefore, multimedia technology, mainly images, are increasingly used. Image databases now represent large volume of information. Querying image databases is becoming a big challenge in computer science world.

To effectively manage and use these image databases, an image retrieval system is required. This is why it is a very active area since a long time. An image retrieval system manages access to several images, the images are represented and indexed according to the used approach and compared using various approaches to generated queries using specific techniques. In summary, an image retrieval system manage the image representation, the query construction and the selection of images.

The goal of this chapter is to give an overview of the image retrieval problem and propose a semantic gastroenterological images retrieval based on a new polyp ontology.

For this purpose, this chapter is structured as follows: we start by the presentation of the two major image retrieval techniques proposed in the literature, then the facets of an image retrieval which are: query modalities, image annotation and image similarity.

Afterwards, we present after the outline of the semantic image retrieval based on description logics and the medical images retrieval. Finally, we present the proposed approach including: the construction of an ontology, generation of image annotations and reasoning mechanisms, before concluding.

Image retrieval

Image retrieval techniques

The first image retrieval systems were based on a textual description of the image (keywords associated to images) [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF][START_REF] Rui | Image retrieval: Current techniques, promising directions, and open issues[END_REF][START_REF] Del | Visual information retrieval[END_REF], keywords are external source of information manually attached to images. The indexing process based on keywords is time consuming since it is manual, tricky, because the quality of the retrieval system depends largely on the relevance of the terms assigned to images and not standardized because the source of these keywords is generally not unique and depends on the person who associates keywords to images. In addition, a short list of keywords cannot completely cover the often rich semantics carried by an image.

The second generation of image retrieval systems are based on content. The content based approach aims to directly extract information from the image itself to be able to classify it, this comes as an alternative to the textual approach but semantic problems related to the automatic processing of images are quickly noted. Techniques for solving these problems have been proposed in the literature [START_REF] Luo | A bayesian network-based framework for semantic image understanding[END_REF][START_REF] Ghoshal | Hidden markov models for automatic annotation and content-based retrieval of images and video[END_REF][START_REF] Wang | Adaptive tree similarity learning for image retrieval[END_REF][START_REF] Shah | Semantic image retrieval based on probabilistic latent semantic analysis[END_REF][START_REF] Zhang | FAST: toward more effective and efficient image retrieval[END_REF][START_REF] Cheng | A semantic learning for content-based image retrieval using analytical hierarchy process[END_REF][START_REF] Eakins | Towards intelligent image retrieval[END_REF].

We can classify the images retrieval approaches into two main currents: the current of content based image retrieval and the current of semantic image retrieval based on a knowledge representation formalism.

Content-based image retrieval

The principles of content based image retrieval (CBIR) approaches are to answer two questions [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF]: how to mathematically describe an image ? and how to measure the similarity based on the abstract description ? These approaches usually apply statistics and machine learning techniques.

To describe images, most CBIR systems use characteristics automatically extracted from images such as color, texture and shape. These characteristics are used in different processes, such as similarity computation, model building, or even annotations.

One of the most known issues of content based approaches [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF] is the gap between the extracted characteristics from the images to describe it which are low-level characteristics (description), and the human description of the image (image semantic) which is of highlevel. In other words, the gap between the image description built automatically, and the human interpretation of the image. Indeed, the human uses more information and characteristics than the automated processes to interpret the image. [START_REF] Liu | A survey of contentbased image retrieval with high-level semantics[END_REF]. They study and describe the different methods proposed which are classified in five major categories [START_REF] Liu | A survey of contentbased image retrieval with high-level semantics[END_REF]:

Liu et al. talk about this problem in

• Using an ontology: to define high level objects and better interpret the extracted characteristics of low level.

• Using a machine learning methods: to predict from an input measure the value of an outcome measure of a process or describe the organization of the input measure.

• Using a user feedback: to try to learn the user's intentions to better understand their needs using an online processing.

• Generating a semantic template: to support high level image retrieval by using a templates to represent concepts calculated from a collection of reference images.

• Using a web context: for the web image retrieval. It consists to the utilisation of informations that can be structured as the url or HTML pages to improve the semantics of images.

Semantic-based image retrieval

In classical image retrieval approaches, images are described with a set of keywords [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF],

[77], [START_REF] Del | Visual information retrieval[END_REF]. The quality of this process depends largely on the relevance of these keywords, the keywords used in the user query, and the adequacy between them. Generally, this process performs a simple syntactical comparison between annotation keywords and user query keywords, and if the user does not use the same keywords, he may not get what he is looking for. Among the problems of these approaches is that the keywords may not cover the rich semantics carried by the image.

Semantic image retrieval approaches use generally a formalism of knowledge representation such as description logics or semantic networks [START_REF] Meghini | A model of multimedia information retrieval[END_REF]. The goal is to find a model of image representation. This representation haves to be easily comparable and characterize the image in the best way. Semantic retrieval is based on the meaning of keywords (concept in this case), not its syntax. The comparison between concepts (generally referred to reasoning) is based on more advanced techniques than those of syntactic retrieval. It takes into account also the interaction between different concepts of the query to improve relevance compared to a syntactical retrieval.

Wang et al. [START_REF] Wang | Does ontology help in image retrieval?: a comparison between keyword, text ontology and multi-modality ontology approaches[END_REF] propose a comparison between ontology based image retrieval approaches and keywords based image retrieval approaches. The keywords based image retrieval is simple and easy to apply with an acceptable precision, and the ontology based image retrieval improves precision but requires a complete description of images.

Facets of image retrieval

To design an image retrieval system, we need to answer three key questions: how to built the query ? How do we represent an image ? And how to match between the query and the image representation (description) ?

These three questions are highly linked to each other and are considered as the three foundations of an image retrieval system. In the next sections of our document, we will have a brief overview of the possible answers to the above questions. The first and third questions concern the query modalities and the similarity computing respectively.

We are interested in this work to a semantic based retrieval, question two is treated in a semantic based techniques view, which usually represent the image by annotations.

Other approaches, particularly in the case of CBIR systems use other techniques will not be mentioned here.

Query modalities

An important factor in an image retrieval system is the query modality. This modality define the query language supported by the system in terms of expressivity of generated user query. The most known query modalities of image retrieval system are [START_REF] Datta | Image retrieval: Ideas, influences, and trends of the new age[END_REF]:

• Keywords: this modality is the most used. The query is presented in the form of keywords. The set of authorized keywords is not limited in general like the image retrieval systems on the web, but can be predefined, which will limit the expressivity of queries.

• Free-Text: for this modality, the user tries to define his need by sentences. These sentences are constructed freely, it may be questions, stories or other expressions.

• Image: like its name indicate, the introduced query by the user is an image and the system returns all images similar to the user image. This modality is very suitable for CBIR systems.

• Graphics: this modality is based on a graphical representation of the query, the user defines graphically his needs by drawing an image. The image can also be automatically generated by computer.

• Composite: it consists of a combination of the other modalities. In general, the user can choose a modality for define his query or define a parts of his query by using several modalities. The combination of modalities is interesting in the case of an interactive querying, the user can each time give more details about his query by changing the modality.

It is important to make the difference between an image retrieval technique based on keywords and query modality based on keywords. Query modalities are used as an input to the query construction process, which provides after, a query to the image retrieval process, regardless of the used technique.

In general, the query construction process is not necessary for syntactic retrieval techniques based on keywords, the set of keywords introduced by the user are used without pretreatment. By cons, it is very important for semantic image retrieval techniques to give some semantics to the query.

Images annotation

Image annotation is an image description process that facilitates access to images. It is mainly used by semantic based image retrieval techniques but can be also used by syntactic techniques. The difference is that the semantic techniques use a knowledge representation formalism to define an annotation, and a knowledge base to enrich and to better interpret the annotations.

To describe an image, we can associate to it several types of information. This informations are [START_REF] Del | Visual information retrieval[END_REF][START_REF] Hanbury | A survey of methods for image annotation[END_REF]:

• content-independent meta-data: this information does not describe the content of images. They describe the context as the author of the image, the used camera, the image resolution, etc.;

• visual content meta-data: this information describes the visual content of images.

It can be divided into two types:

content-dependent meta-data: describes the low level characteristics of images.

It is generally information that can be automatically extracted such as color, shape, texture, etc.;

content-descriptive meta-data: describes the semantic of images content. This information represents the possible interpretations that a man can give to images.

The most used image annotation approaches are [START_REF] Hanbury | A survey of methods for image annotation[END_REF]:

1. Free text descriptions: free text is used to describe the image, the annotation is not formulated and its structure is not predefined. It is easy to make but difficult to exploit for obtaining an efficient system.

2. Keywords: a set of keywords freely chosen or selected from a predefined set of keywords is used to describe the image. These keywords can be used for the entire image or a segment of the image. The most difficult task for systems using this type of annotation is the definition of the query modality which is not necessarily the keywords modality. It must be use in some cases a process that transforms the output of the query modality to a set of keywords.

3. Based on ontologies: an ontology is used to define the structure of the annotation and enrich its interpretation to improve the comparisons. The ontology concepts are used to annotate the images in general. The main problems of approaches using this type of annotation are: the formalization of the annotation, the definition of a query modality exploiting the knowledge of the ontology and the comparison process between a query and an annotation.

The first classification annotation approaches are based on the domain and structure of the annotation. We can also classify approaches depending on the generation process of the annotation. The generation can be manual, automatic or semi-automatic:

1. Manual: it is recommended for small images databases and usually for delicate applications which require maximum of accuracy such as medical imaging systems.

Its advantage is that it is performed by human, therefore more accurate and very well suited for semantic techniques. Its limits is that it is very expensive and not possible to use for very large image databases.

2. Automatic: automatic annotation is the only solution in the case of very large image databases. It is generally used for CBIR systems and can also uses an ontology as proposed in [START_REF] Srikanth | Exploiting ontologies for automatic image annotation[END_REF]. Its advantage is that no human intervention is required and can be performed in the background but its limits is the lack of precision often and the difficulty of use in the case of a semantic technique.

3.

Semi-automatic: it consists to the use of both types of previous annotations. The manual annotation can be used to review the automatic annotations or to complete them.

Images similarity

The similarity computing is a process used to retrieve the set of images answers. It defines an affinity relationship that can be quantified or not between a query and a image. The query is generated using the output of the query modality, it may be another image, text or a combination of both. The similarity computing also allows generally the ranking of images answers even if other approaches use other parameters in addition to do the ranking [START_REF] Trevisiol | Image ranking based on user browsing behavior[END_REF][START_REF] Xu | Efficient manifold ranking for image retrieval[END_REF].

The similarity can be syntactic, semantic or hybrid. Syntactic similarity is based on a numerical comparison between the representations of the visual aspects of the images and the query. The result of this comparison is numerical and allows the ranking of the answers. By cons, semantic similarity is based on the comparison between the interpretation of the representations of visual aspects of images and the interpretation of the query, it generally uses a knowledge representation formalism and a knowledge base.

This knowledge base is used to better interpret the representations of the images and the query for a better comparison. The result of the comparison is generally not numeric but boolean and does not allow necessarily the ranking of images answers. The hybrid similarity uses a combination of syntactic and semantic similarities. It uses the knowledge base to enrich and for a better comparison, and numeric computation for the ranking.

Syntactic similarity:

The general principle of syntactic similarity is the computing of numerical distances between the query and a potential answers. The distance is defined according to the used model, it may be for example one or a set of values, numerically calculated using the representation of the query and the representation of a potential answer. The selection of answers is based on the values of distance, for example, by defining a distance threshold or the selection of N first answers after the ranking. We can distinguish two main approaches for computing the syntactic similarity:

Visual signature using: These approaches are mainly used in CBIR systems. The principle is to mathematically formulate the characteristics called signatures. This signatures are extracted from the images for using a techniques of distance computing to find one or a set of values representing the similarity.

Information retrieval models: The principle is simple, it consist to use text in form of keywords, tags, paragraphs or other forms to index images. The idea is to transform the image retrieval to an information retrieval to use techniques and models of information retrieval.

Semantic similarity:

The similarity in this case is not a distance to compute usually but a process of comparing an elements of a given language. A knowledge representation formalism is used to formally define an annotation image and a query. This formalism has a well-defined semantics for interpreting the annotations and queries.

The management of interpretation is called reasoning. The reasoning is used to compare an annotation and a query. The comparison is usually logical and based on set theory, it can use a standard or non-standard reasoning.

Standard reasoning: These are classical standardized reasoning which belong to the standard definition of the language. These reasoning are generally mastered, necessary for the best exploitation of language and include on its technical tools such as the tool which allows to reasoning called reasoner. They are also the basis for defining other reasoning called non standard.

Non-standard reasoning: They consist to a non classical reasoning using numerical computing or probability theory often. They are often defined for specific applications and not available on technical tools such as reasoners. These reasoning are generally based on standard reasoning but can also use non-standard semantics.

Semantic image retrieval using DL

Description logics are increasingly used for formalized a knowledge area. They allow to well structure a domain, to define these elements and associate a well defined interpretation to each element. They also offer a set of reasonings to manipulate knowledge of the domain. These features are useful for image retrieval.

Description logics are mainly used in image retrieval to annotate images and to compare image annotations, i.e. retrieve images. Formally, it consists to define the syntax and semantics of an annotation, and define a reasoning to retrieve images. We must answer two main questions: what language to use and how to define an annotation image? and what reasoning to use ? The two issues are closely linked in the famous compromise between expressiveness and complexity.

Among the works in the domain, we can cite the work of Sciascio et al. [START_REF] Di Sciascio | Structured knowledge representation for image retrieval[END_REF] which propose a semantic indexing approach based on description logics for image retrieval.

They use description logics and propose a formal language to structure the representation of an image and reduce the gap between low levels characteristics obtained by a vision algorithm and the complex structure of objects. They define syntactically an image by using concepts and roles. The composition of concepts and roles represent regions, simple shapes, complex shapes and geometric transformations. Each image is defined by all of its regions which are connected parts of uniform color. A region is recognized as a form if there exist a geometric transformation that transform this form to this region. Geometric transformations describe the relative positions of the elements. The authors associate a semantic to their language for the interpretation of the definition of each image and propose two main reasonings to manage these interpretations. The recognition (classification) to decide if a form is recognized in an image and the subsumption to decide if a form is contained in another form. Other reasonings are defined using these two reasonings.

An experience of the utilisation of an ontology is proposed by Optitz et al. in [START_REF] Opitz | Using ontologies for medical image retrieval -an experiment[END_REF].

An OWL EL ontology is used to annotate images and an instance retrieval reasoning is used to retrieve images. The paper shows that with a standard utilisation of semantic techniques, the image retrieval is improved. They identified before the experiment three main points that the utilisation of an ontology must improve compared to a keywords based techniques and they confirmed these points after the experiment.

The improvement of the recall 1 by a better management of synonyms. Indeed, for a keywords based retrieval, relevant images will not be retrieved if they are not annotated by the same vocabulary as the query, the utilisation of synonyms can degrade the value of the recall. With an ontology, the domain is formally defined, the image retrieval is based on the interpretation of keywords. The recall is improved because the synonyms have the same interpretation.

The precision 2 is improved also. A keyword depends on the context where it is used, a query can be misinterpreted when the interpretation is based on the syntax. Irrelevant images will be retrieved therefore a deterioration of the value of the precision but with the utilisation of an ontology, the query has a unique interpretation, the context is integrated in the query definition and the precision is improved.

The improvement of the construction of query. Indeed, with an interpreted language formally, the user can build more precise, well defined and expressive queries even with the used language which is not very expressive.

In the medical domain also, Hu et al. [START_REF] Hu | Ontologybased medical image annotation with description logics[END_REF] propose a system to formally annotating medical images based on the description logic to aid in the diagnosis of breast cancer.

This system is based on a domain ontology of breast cancer images. Their ontology is a multi levels model: graphic descriptors, images subjects and other medical terms. A 1 recall [START_REF] Christopher | Introduction to Information Retrieval[END_REF] is the number of relevant images returned divided by the number of all relevant images 2 precision [START_REF] Christopher | Introduction to Information Retrieval[END_REF] is the number of relevant images returned divided by the number of images returned last work can be cited is the work of Meghini et al. [START_REF] Meghini | A model of multimedia information retrieval[END_REF] which propose a framework based on fuzzy description logics to integrate the multidimensional aspects of multimedia information retrieval.

Medical image retrieval

Medical images are commonly targeted by image retrieval systems and medical domain is one of the main application cited by the CBIR systems [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF][START_REF] Arnold | Content-based image retrieval at the end of the early years[END_REF], but the most current access to medical images [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF] are based on the patient's ID and other characteristics present in a DICOM file. DICOM (Digital Imaging and COmmunications in Medicine) [START_REF]Dicom, digital imaging and communications in medicine[END_REF] is a standard definition of medical images, informations of patients and other informations (concerning the examination for example) are stored with the image in the same file.

These files are stored and managed by systems called PACS (Picture Archiving and Communication System).

Medical image retrieval systems are mainly used for teaching, research and diagnoses.

For teaching, image retrieval can be used to illustrate a course, get acquainted with commonly cases and compare them. The images are used for the formation of physicians and also specialists. They are also used in research, for example, to analyse phenomena or propose a classification. The diagnosis aid is the most common, the most important but most difficult utilisation of medical image retrieval systems. The images are used mainly to compare cases and reuse other previously treated cases. To get an efficient utilisation of the system for the diagnosis, the interface should be very fast to use because the time factor is very important in the medical domain and rich to allow the user to create very precise queries. The answer of the system should be fast also and very relevant because the error can be fatal in this domain.

The various image retrieval techniques are used in the medical domain but with modifications. The CBIR systems for example are widely used but not with the same characteristics extracted from the image. The utilisation of color is not very suitable, several images do not contain colors and conditions of examinations such as coloring influence on color. Consequently, texture and shape are gaining importance and are much used.

Semantic medical image retrieval generally use medical ontologies. The purpose of medical ontologies is to provide a common vocabulary with formal definitions. These definitions can be used to represent images and medical assessments. It helps to standardize the interpretation of medical images for better treatment. We can distinguish two main approaches to developing medical ontologies [START_REF] Hu | Lewis, and Nigel Shadbolt. Reflections on a medical ontology[END_REF]: general utilisation ones that are independent of the application and others pointed for a particular application utilisation.

UMLS Metathesaurus, SNOMED, MeSH and GALEN are examples of medical ontologies

for a general utilisation.

The challenges of these approaches are: the tradeoff between the expressivity of image representations and reasoning performance in terms of relevance and computation time, adapted interfaces to medical domain and conditions of the examinations and the construction of ontology (reuse ? adapt ? create ? ...) and its maintenance for approaches based on ontologies.

The context of the medical domain and medical practices are very complicated and special, there is a gap between the theoretical approaches and the implemented systems.

Several powerful techniques in other domain have not been tested, such as for example the non utilisation of user feedback [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF] justified by his absence caused by the medical practices and the very limited time. Another example is the lack of investment in interfaces adapted to the working conditions [START_REF] Müller | A review of content-based image retrieval systems in medical applications -clinical benefits and future directions[END_REF]. The evaluation techniques and benchmarks are also lacking in the medical domain, although in 2004 a medical image retrieval tasks is added to ImageCLEF which is a part of the Cross Language Evaluation Forum (CLEF) [4]. In [START_REF] Müller | Evaluation axes for medical image retrieval systems: the imageclef experience[END_REF], The authors investigate the various interesting axes for medical image retrieval system evaluation.

For more information on medical practices and mainly propose a diagnosis aid for physicians, we propose and implement in this thesis a completed semantic gastroenterological image retrieval system [START_REF] Chabane | Medical data management in the SYSEO project[END_REF][START_REF] Chabane | Semantic gastroenterological images annotation and retrieval -reasoning with a polyp ontology[END_REF]. We built a polyp ontology based on standard classifications used in gastroenterology, propose a graphical interface to generate semantic queries and implement reasonings based on a slight extension of a standard reasonings used in description logic. We now present in detail all these parts.

Semantic gastroenterological image retrieval

In the medical domain, images are increasingly produced in large quantities. They are becoming increasingly important and necessary for some medical practices such as diagnosis, report writing and teaching. Management and access to this images become capital but also complex. Important decisions are based on these images. Like for the gastroenterology, where physicians for exploiting past experiences try to retrieve images of previously treated cases, similar to the treated case to decide whether they remove a type of tumor called a polyp or not. These polyps can develop a cancer. The decision to remove a polyp or not is sometimes very complex because it can be very dangerous for the patient's health but can also generate unjustified costs. The error can be fatal in this domain and the time is very valuable, these physicians need an image retrieval system allowing to quickly, intuitively and efficiently generate queries and quickly retrieve very relevant images.

To help physicians, we propose in this work a semantic gastroenterological images annotation and retrieval system based on a new polyp ontology. We investigate the problems of ontology construction, image annotation using an ontology and semantic image retrieval. We proceed by constructing a polyp ontology which will be used by an image retrieval system. This ontology is the knowledge base of the system, it is used to define the representation of an image and the important elements of gastroenterology as standard classifications of polyps and for reasoning about all these definitions.

We use description logics as formalism to construct the polyp ontology, represent images and for reasoning about knowledge. The choice of description logics is justified by a set of criteria which can be summarized as:

• They allow to structure the world in hierarchy and create relationships between the objects of this world, which is well suited to medical domain for the formal definition of classifications, illnesses, symptoms, ... etc.

• They offer a wide range of languages with a variety of operators and a controlled reasonings but with a tradeoff between the language expressivity and the reasonings performances. We can always restrict the language expressivity to facilitate reasoning.

• A wide variety of technical tools as reasoners are complimentary. Experiments and development of systems are becoming less expensive and faster.

• Description logics are widely used for many years, we can reuse many results.

• Need to use an ontology to formalize medical knowledge, and separate the knowledge part from the processing part for a better exploitation, re-use, evolution and sharing of medical knowledge, knowing that the renowned language for the development of ontology, Ontology Web Language (OWL) [START_REF] Owl | the web ontology language[END_REF], which is standardized by the W3C, is based on description logics.

As we have seen previously, description logics enable to describe a domain by individuals, concepts and relationships. For our domain, we represent images by individuals which are instance of a concept image, images annotations by concepts descriptions and other medical terms by concepts. We present the polyp ontology and the conception details in section 3.3.1.

The main utilisation of the system is the semantic image retrieval, but it can also be used for other purposes such as teaching. It can be useful in the following cases:

• as an help for annotation: during a surgery, when he takes a photo, a surgeon may want to describe it even basically; in this context he can give his observations (color, shapes, ...) to the system which will display corresponding reference images (those described by a annotation semantically linked with the same observations), helping him annotating his image with the suited (and standard) concepts.

• as an help for a diagnosis: after having annotated the taken image, the surgeon may have to decide whether he removes or not the polyp. Then he can once again be helped by the system that would classify the image, according to its annotation, into various classifications (related to medical acts, pathologies, procedures,...). He can also be displayed images of the same kind of polyps that have been previously removed.

• as an help during medical education: learning a polyp classification can be eased by a system that is able to quickly relate a set of observations to the possible polyp classes it corresponds, and also to give the polyp classes that are not related to the observations by focusing on what is contradictory between the observation and the polyp description.

We distinguish three possible scenarios of utilisation: S1 semantic images retrieval: given an image annotation concept, the problem is to retrieve all images which can be annotated with this concept, in other words, they check all properties of this annotation. A property of an annotation is a part of its definition which represent an aspect of the annotated image, for example, the shape of the polyp or its color. This scenario is used to retrieve similar images and to help physicians in the diagnosis by the utilisation of images of previously treated cases.

S2 exact classes retrieval: given an image annotation concept, and a standard gastroenterological classification concept, the problem is to retrieve all subclasses of this annotation and are also subclass of the standard classification. This scenario can be used for the formation of physicians to different standard classifications.

S3 relaxed classes retrieval: given an image annotation concept, and a standard gastroenterological classification concept, the problem is to relax this annotation to retrieve these superclasses, which are also subclass of the standard classification.

This scenario can be used as an help to the annotation or diagnosis.

From these three scenarios, we can create other interesting scenarios by combining these scenarios. For example, we can compare the standard classifications and find links between these classifications by the relaxed classes retrieval of images of a given annotation. This result is given by the sequence of scenarios S1 S3. We can also illustrate by images the definition and the different classes of a standard classification by the sequence of scenarios S1 S2. This combination is used for the formation of physicians.

The rest of the chapter is organized as follows. We present our choice of language, conception and formalization to construct the polyp ontology. Then, we explain how formally define and construct annotations or queries using the ontology and how to reason with this ontology and what reasoning used to answer queries. We present afterwards the prototype, some technical aspects and execution examples. We discuss at the end of our problems and choice compared to other approaches.

Ontology

Ontologies are designed to capture a shared knowledge and to solve the semantic heterogeneity between domains. Before the construction of an ontology, we must identify the important terms of the domain. These terms are represented by concepts, individuals and roles. We work about a domain of polyps, our ontology is an ontology of polyps and Polyp concept is the main concept of the ontology. Gastroenterological images are represented by individuals, instance of the Image concept. This Image concept represents a diagnostic, a site, a measurement or an observation. Observable concepts are atomic concepts, they are defined by the enumeration of their individual instance. For example, the Color concept is defined by a set of eight individuals:

Color ≡ {white, blue, yellow, black, orange, pink, red, green}.

Part of the core hierarchy of the ontology is presented in Figure 3.1. This hierarchy is composed by five main parts: a part to describe the observable concepts, another part to describe some organs of the human anatomy, a part to describe the measurable concepts, Roles are also organized in a hierarchy and use the same name of concepts to support the automatic processing of image annotation definitions.

The observable concepts part includes the concepts describing the observations of the physicians. These observations mainly concern the polyps, it consist of color, shape and texture. Some of these concepts are defined by listing their individual instance.

The human anatomy part represents some organs that may contain polyps. The representation is simple, each organ is an individual. We still have not found links between these organs and other concepts and roles of ontology.

The measurable concepts part defined measures concerning polyps obtained by medical equipment. We use roles on concrete domain in this part. The polyp ontology is used mainly for diagnosing cancer which is based on the analysis of polyps present in an organ. The principle is to clearly identify the type and state of the polyp by retrieving its standard classes used in gastroenterology. Formally speaking, it is consist to make a classification. We have integrated in the ontology the three most known standard classifications and widely used in gastroenterology. Namely, the Paris classification [START_REF] Paris | The paris endoscopic classification of superficial neoplastic lesions: esophagus, stomach, and colon: November 30 to december 1, 2002[END_REF] that describes polyp shapes, the Pit-Pattern classification [START_REF] Kudo | Colorectal tumours and pit pattern[END_REF] that describes polyp surfaces and the Vienna classification [START_REF] Schlemper | The vienna classification of gastrointestinal epithelial neoplasia[END_REF] that describes pathological states associated to polyps. Each standard classification is represented by a hierarchy of concepts, the concept root is the name of the classification and the concepts children represent the classes of the classification. Each concept of the classification is defined using other concepts and roles. We have also integrated some concepts related to the domain of gastroenterology from the MST3.0 [5] that lists many gastroenterological concepts related to anatomy, observations and medical acts.

We use the ALCHOQ(¬) language for the construction of the ontology. ALCHOQ(¬) language is very expressive but decidable in the case of standard reasoning. The choice of ALCHOQ(¬) language is justified by a need for constructors concepts and roles and reasonings performance to define medical classifications, describe the medical context and annotate medical images. Indeed, we need to define atomic concepts to generate more knowledge and be more specific about the description of a polyp. We remind that the main objective of using the ontology is to find the standard classes of the polyp. We chose ALCHOQ(¬) to try to accurately define the standard gastroenterological classifications of polyps. For performance, our ontology is small and we use very simple adaptations of standard reasonings, the times answers are very reasonable, we did not have performance issues even though the language is very expressive. Statistically speaking, the ontology gathers 58 defined concepts, 23 roles and 188 individuals, among them 100 images and 88 various individuals (names or gastroenterological organs, colors, textures). These data are linked through 58 subsumption relations, 40 disjoint concepts axioms and about 200 individuals assertions. It is contained into a 476 KBytes files. This is a quite small ontology since it is still in its infancy.

Annotation

The annotation of images in our system is achieved manually by experts saw the importance of the made decision after an images retrieval. We use high levels information to describe the content of the image. Automatic extraction of low-level information is not used for the same reason that we have just mentioned and the information do not describe the image are also not used in the first version because we have not integrate information describing patients, context and physicians in the ontology and the query. We want to first test the first version of our system to see if the inclusion of such information contribute to improve the relevance of our results.

The used information for the annotation are concepts, individuals or roles of the polyp ontology described above, we use a knowledge base for the annotation, the text is not free.

Note that, the process of generating annotations and the process of generating queries are based on the same principle with a slight difference. The query generation process is more general than the annotation generation process. It allows the construction of concept descriptions of other object and the construction of image concept descriptions like the annotation generation process. In addition to that, the annotation is performed by specialists but the interrogation can be performed by any user.

An annotation (or query) of an image is manually generated using an interactive interface. This interface represents graphically the polyp ontology and allows to navigate on concepts, roles and individuals of the ontology. According to his observation (or need for other users), the physician select most appropriate concepts, roles and individuals to generate an annotation (or query) of an image. The annotation generation process is fast and simple to use for satisfying the requirements of physicians. Other more complex interfaces are proposed in the literature including other information, such as the work of Xu et al. [START_REF] Xu | Image search by concept map[END_REF] which propose a new query interface by integrating the spatial distribution of concepts in the image. They propose a model for converting a concept map to a visual instance map, and a evaluation scheme for comparing the visual instance map with images. This system is not suitable for medical domain because images in general have the same spatial structure.

Formally, an annotation (or a query) of an image is a concept description A in conjunctive form defined as following: The annotation generation process is illustrated in figure 3.2. The user selects "stomach", "orange" and "haemorrhagic" from the ontology. It consists of three individuals from which we define using the concept constructor oneOF [START_REF] Hacid | Dynamic discovery of e-services. In 18èmes Journées Bases de Données Avancées[END_REF] three concepts: "oneOF(stomach)", "oneOF(orange)" and "oneOF(haemorrhaic)". The subsumers (belonging to the annotation concept definition) of these concepts will be determined in order to select the most appropriate roles for each concept. The subsumers are the concepts:

Location (subsumer of oneOF(stomach)) and Observation (subsumer of oneOF(orange) and oneOF(haemorrhaic)). These subsumers allow to select from the definition Image concept the roles: location and observation (which will be used twice) to find the roles which to be used to define the annotation. Roles used to define the annotation satisfy two conditions: they are subsumed by the selected roles before, and their domain are the selected concepts from the interface (or defined from a selection) or subsumers of these concepts. The roles location, color and mucous are found. We use all these results for define the user annotation as shown in the figure .   5ROH VHOHFWLRQ

2QWRORJ\ GLVSOD\ D Ł ѩUHSUHVHQWV ѩ FRORU ^RUDQJH` ӹ ѩ PXFRXV ^KDHPRUUKDJLF` ӹ ѩ ORFDWLRQ ^VWRPDFK` $ Ł ѩUHSUHVHQWV ӹ L , ѩGLDJQRVLV L 'LDJQRVLV L ӹ ӹ M -ѩORFDWLRQ M /RFDWLRQ M ӹ ӹ N . ѩPHDVXUH N 0HDVXUH N ӹ ӹ O / ѩREVHUYDWLRQ

Reasoning

We represented a given image by an individual. This individual belongs to a general concept Image representing all the existing images. All images are associated with an image annotation. An image annotation is a concept description. The image associated with this annotation is an element of the interpretation. This description describes the contents and characteristics of the image. We want to find to find the annotation that best characterizes the image.

The correspondence between a query and a set of images is semantically computed in our system, the similarity is semantics. It is determined by reasoning. The reasoning is the logical management of knowledge to infer other knowledge.

We have implemented in our system three types of reasoning: a standard reasoning which is the instance retrieval and two other reasonings, a local subsumees retrieval and a local subsumers retrieval which are a slight modifications of a standard reasoning which is subsumption. Table 3.1 shows the inputs, outputs and the utilisation of each implemented reasoning.

We use the instance retrieval to find an images results of a query, which can be used as an example of diagnosis when it is a previously treated cases or for the formation of new The tools which implement reasonings in description logic are called reasoners. Several reasonings implementing the standard reasonings are proposed as FaCT++ [2], Pellet [START_REF] Pellet | the pellet owl2 reasoner[END_REF],

RacerPro [START_REF]Racerpro, the racerpro owl/rdf reasoner[END_REF] Hermit and [3]. We use Hermit for the implementation of our reasonings, it is one of the most effective reasoner up to our knowledge. It is based on the hypertableau algorithm [START_REF] Motik | Hypertableau reasoning for description logics[END_REF] and most other reasoners are based on the tableau algorithm [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF].

Prototype and experiments

The architecture of our application is presented in Figure 3.3. To implement the system we use the MVC model which is composed by three layers: the data layer to manage the data (images, ontology), the controller layer to manage the processing (query construction, reasoning) and the view layer to manage the interface and user interaction (query modality, answer display). The application is mainly composed by three modules: interface module, annotation module and reasoning module.

We use different technologies for the development of our application. Struts 2 framework for the implementation of the MVC pattern, Java Server Pages to create the interface, OWL API for the management of the ontology, HermiT reasoner [3] for the reasoning about the ontology and Prefuse [START_REF] Heer | prefuse: a toolkit for interactive information visualization[END_REF] to create the interface of images annotation and query generation.

For the first scenario (semantic images retrieval), reasoning extend the images indexation. An image is indexed by an annotation concept but also by all concepts that can be inferred by the annotation concept. For example, if the query is the P arisIII class, In the second scenario (exact classes retrieval), reasoning is used for classification.

The annotation concepts used to infer other concepts and information to find the class (standard classification) of the polyp. For example, a concept with a f lat depressed form, through submucosa state, papillary surface and m4 depth will infer other information as depth is superf icial, it is a lesion, this may cause cancer, it is a polyp and from all that, it will deduct it belongs to the P arisII c class.

In the third scenario (relaxed classes retrieval), reasoning is used to find relaxed classes or classification (standard). The annotation concepts are used to infer other concepts and information in order to approach a class or classification. For example, if I ask to classify surfaces, after inference, the system returns the Pit Pattern classification and his hierarchy.

Let's see now an execution example. By browsing the ontology as represented in figure 3.1, the user may select the concepts Lesion and totallyF lat (which in fact is an invididual). By selecting these concepts like keywords, the user expresses that he's looking for images where man can see some lesion that is totally flat. From these keywords, the prototype may built two semantic queries: the first will be built as the most general concept linking both Lesion and totallyF lat, and the second as the most general concept linking both Lesion and totallyF lat and being a subconcept of Image: Query ≡ Lesion ∀observation.oneOf {totallyF lat} is the first query which can be as-sociated to a classification name (e.g. Vienna) so as the system can run retrieval of local subsumees and instance retrieval reasonings.

Query ≡ ∃represents.( Lesion ∀observation.oneOf {totallyF lat}) is the second query for which the system can retrieve all corresponding images (images that describe a totally flat lesion with other extra properties). On our current ontology, with a hundred of randomly generated images, the second query with instance retrieval reasoning shows that 11 images correspond to these criteria, and the first query, with retrieval of local subsumees and retrieval of local subsumers reasonings, shows that these criteria are present in the class Paris II B of the Paris classification, and in no other classification.

Semantic retrieval has brought more flexibility and precision. With ontology, the annotation vocabulary is unified. With a formal definition of concepts and reasoning techniques, the indexation of images is extended and the accuracy is improved. The quality of the image retrieval system depends directly on the quality of the image annotation and the quality of the query construction which depend on the expressivity of the used language, which is selected according to the compromise expressivity / performance. We propose a quick and simple method for the images annotation. The problem with this method is that the accuracy is low in some cases, if the doctor fails to well define the form of a polyp, for example.

Conclusion

We investigate in this first part of the thesis, how to implement an annotation, a semantic image retrieval and a classification system adapted to gastroenterologists. The proposed solution is based on a polyp ontology, a slight adaptation of the standard reasonings in description logic and a semi-automatic construction of queries and image annotation.

Semantic retrieval has brought more flexibility and precision for image retrieval. With ontology, the vocabulary used for annotation is unified. With concepts structure and reasoning, indexing is extended, and with relationships between concepts and queries the annotation accuracy is improved which affects the result. The quality results depends directly on the quality of annotation and the quality of query generation. The quality of annotation and query depends on the used language expressivity, which is selected according to the compromise expressivity/decidability. We proposed a simple method for rapid annotation by graphic selection of concepts. The problem of this method is that the accuracy is low in some cases, if the physician fails to well defined the shape of a polyp for example. Our goal is to develop a complete semantic system then define an interesting problem and detailing it.

It is clear that the system is still in its infancy, we randomly generate the images for the first tests, practice validation is required. Performance is acceptable but the ontology is to evolve by specialists and the interface of image annotation construction too. We were interested in the second part of the thesis to improve reasoning. Two main issues motivated our approach:

• Ranking: some physicians do not detail their queries, the number of retrieved images is great and naturally the instance retrieval do not distinguish between instances of a given concept. How to present images is a problem, we must rank the results by relevance.

• Relax the query: in the opposite of the first problem other physicians are very greedy and construct queries with many properties. With a standard instance retrieval, the set of retrieved images is empty. We must relax the query by sacrificing some properties to have a non-empty result.

We propose a new relaxed instances retrieval reasoning to solve both problems. The advantage of our approach is that for a given result the sacrificed properties are not the same for every individual.

We investigate in the second part of the thesis a new approach for computing relaxed answers of ontological queries based on a notion of an edit distance of a given individual w.r.t. a given query. Such a distance is computed by counting the number of elementary operations needed to be applied to an ABox in order to make a given individual a correct answer to a given query. The considered elementary operations are adding to or removing from an ABox, assertions of the form of an atomic concept (or its negation) and/or atomic roles.

Introduction

We proposed in the previous chapter a semantic system for querying, annotation and retrieval of medical images based on description logics. We will now work on the reasonings for improving the images retrieval research part of the system. If only one model of KB is not model of C(a), it is sufficient to infer that a is not an instance of C. When a is not instance of C two cases are possible: no model of KB is a model of C(a) or some models of KB are not models of C(a). For some applications, the models of KB which are not models of C(a) result from a poor modelization or a lack of knowledge. A slight modification of knowledge base might be sufficient for a to become instance of C without having a large effect on the other knowledge. For our application for example, physicians can forget to annotate a color c 1 of a polyp for an image i 1 , an instance retrieval with the criterion c 1 on the color cannot find the image i 1 even if all the other criteria are satisfied, but an update of the knowledge base by adding the assertion forgotten by the physicians regarding the color of the polyp allows to retrieve i 1 . This observation motivates our work, which consist to create a more flexible reasoning than instance retrieval. This flexibility allows to retrieve more instances of a concept, which is necessary for a very specific concept when the application needs a large number of answers.

It is difficult to formally define what is the flexibility for an instance retrieval reasoning, but the main idea is to increase the number of concepts instances according to defined criteria. Classical approaches for relaxed instance retrieval work mainly at the terminological level [START_REF] Stuckenschmidt | Partial matchmaking using approximate subsumption[END_REF][START_REF] Stuckenschmidt | Approximate subsumption for complex description logics[END_REF][START_REF] Brandt | Approximation and difference in description logics[END_REF][START_REF] Yuan Ren | Soundness preserving approximation for tbox reasoning[END_REF][START_REF] Pan | Approximating OWL-DL ontologies[END_REF][START_REF] Botoeva | Expressive approximations in DL-Lite ontologies[END_REF], such approaches compute in general the subsumants concept without the exploitation of the ABox. For these approaches, the result of the relaxation of a concept is the set of instances of another concept, but the instances of a concept do not convey necessarily the same knowledge. In our approach, we propose to deal separately with each instance.

The TBox and the Abox are complementary, the TBox defines the domain organization and the ABox defines the individuals of this domain. The combination of these two types of knowledge is necessary to define an interesting flexibility for the instance retrieval.

The exploitation of ABox knowledge allows for example to have an information on the distribution of individuals on the structure of the domain. We propose in this chapter a new reasoning mechanism to compute relaxed answers of ontological queries which work at the ABox level. This new mechanism is based on a notion of an edit distance of a given individual w.r.t. a given query. Such a distance is computed by counting the number of elementary operations that need to be applied to an ABox in order to make a given individual a correct answer to a given query. The considered elementary operations are add to or remove from an ABox, assertions on atomic concept, on a negation of atomic concept or on atomic role. This reasoning is investigated in the context of the Open World Assumption (OWA) and the Generalized Closed World Assumption (GCWA) approaches.

The main motivation of our work comes from the application proposed in the previous chapter where the constructed knowledge bases include incomplete and/or incorrect human annotations.

Using WRelaxation with a medical images ontology

The main motivation of our approach comes from our application of semantic retrieval of medical images that we have presented in the previous chapter. We remember that the large part of the assertions are used for the images annotation. Three main scenarios are justified, in a first step the utilisation of the relaxation of the answers, and in a second step, the insertion and deletion of assertions:

• Answers need and limited time: the query of physicians are in general very detailed when they use the images retrieval for a decision analysis. It is important to find an answer in this case, given the importance of the decision to take. Note that, physicians have a very limited time, the time of interrogation system must be minimal, they cannot rewrite a query to make it less detailed, a result must be returned for each query.

• Incomplete annotations: as we have already said, the physicians have a very limited time, they quickly pass the images annotation step, the annotation is not very well detailed and they can forget a very important characteristics. The knowledge base becomes incomplete, assertions used for the images annotation are missing in the ABox, adding these assertions improve the precision and makes the knowledge base complete.

• Incorrect annotations: like any manual annotation, two physicians can annotate differently an image, they may not agree on the classification of the polyp for example. The context may also influence the annotation, and induce to an incorrect annotation. The ABox will contain not valid assertions which can be detected if the knowledge base becomes inconsistent but can also not generate an inconsistent knowledge base. The deletion of these assertions becomes necessary to not retrieve the images annotated with these assertions by a wrong queries.

The standard utilisation of the WRelaxation with a medical images ontology is the improvement of the semantic images retrieval, by the introduction of a distance computed between a query and a potential answer. This distance allows the parameterization of the precision. The WRelaxation is used as an image retrieval reasoning without the update of the annotations or with the update of the annotations after the validation of an expert.

The WRelaxation can also be used to enrich and/or to correct an existing images annotations database. For example, a physicians can perform queries for which the result is mastered (medical classifications for example), to validate the insertion or deletion of annotations of images that are at a distance greater than zero from the query, but who should check the query.

The WRelaxation is interesting for the parameterization of the precision and for the evolution of the ABox, but the medical ontologies are in general large and built using a very expressive languages. The WRelaxation is a very costly reasoning, using it for medical ontologies is still a challenge.

Motivation and main ideas

Consider the knowledge base KB = (T , A) of Table 4.1 which is a part of our polyp ontology seen in the previous chapter. The ABox A stores observations about endoscopic images of a physician while the T Box T defines some associated medical concepts. A polyp may be described by several features, such as shape, color, classification (e.g., Paris is a polyp classification). Given such a knowledge base, one may be interested, for example, on computing the instances of the concept Image or of the concepts Query 1 and Query 2 of the knowledge base KB. In our example, there are three individuals in the ABox A, namely image 1 , image 2 and image 3 , which are instances of the concept Image (can be inferred from histology(image 1 , h 1 ), class(image 2 , p 2 ) and color(image 3 , clear) respectively) while the concepts Query 1 and Query 2 do not have any instance in A. Table 4.1: A knowledge base KB = (T , A) of a medical images system.

Query 1 and Query 2 may represent user queries and, in this case, the instance retrieval problem can be viewed as a query answering problem (i.e., the problem of computing the answers of a given query Q). In this chapter, we are interested by the problem of computing relaxed answers to a given query. To achieve this task, we propose a new reasoning mechanism, called WRelaxation, which is more flexible than the classical instance retrieval mechanism. In particular, we relax the constraints that must be satisfied by a given individual in order to be considered as an instance of a given concept. For this purpose, we define a notion of a distance of a given individual w.r.t. a given query using elementary operations performed over the ABox.

More precisely, we consider the following elementary operations over an ABox: add to and remove from, an assertion on atomic concept, a negation of an atomic concept or an atomic role. Back to the example, by adding P aris1(p 1 ), the individual image 1 becomes relaxed answer of Query 1 . Hence, image 1 is a relaxed answer to the query Query 1 with a distance equal to 1 (i.e., only one elementary operation is needed). On the other side, adding P aris1(p 2 ) to the ABox makes the knowledge base inconsistent.

Therefore, image 2 does not belong to any relaxation of Query 1 computed only by adding new assertions to the ABox.

We investigate WRelaxation both in the context of the Open World Assumption (OWA) and the Generalized Closed World Assumption (GCWA) approaches. OWA is a widely used approach in the context of description logics while the use of GCWA is motivated by our application context. The considered polyp images retrieval application provides assistance to surgeons to decide whether or not polyp must be removed. An inadequate decision in this context may generate unjustified costs or be dangerous for the patient's health. Therefore, accurate annotation of images is essential. GCWA turned out to be an interesting approach to support validation of image annotation by young physicians and forces expert physicians to be very precise in their annotations.

Note that, in the next part of the thesis, we use the term atomic assertions to denote assertions on atomic concept, a negation of an atomic concept or an atomic role.

A new relaxation based on the ABox

As explained before, the general idea behind WRelaxation is to determine the minimum knowledge to add to or to remove from an ABox so that a given individual can be considered as an instance of a given concept. Such a quantity of knowledge is defined by counting the elementary operations performed over the ABox. We consider the following elementary operations over an ABox: add to or remove from an atomic assertions. We define below three types of WRelaxation based on the type of authorized elementary operations:

• The W + Relaxation that allows only insertion of new assertions.

• The W -Relaxation that allows only deletion of assertions.

• The WRelaxation which is more general and allows both insertion and deletion of assertions.

Note that, in the context of the GCWA, the elementary operations are performed before the computation of the generalized closed world assumption set.

Assertions on atomic concept, on a negation of atomic concept or on atomic role are used because they represent the minimal knowledge to add to or to remove from an ABox.

For an acyclic terminology, concepts definitions can be unfolded into descriptions made with atomic concepts. In this case, adding a non atomic concept assertion is equivalent for these languages to adding a set of atomic assertions. Therefore we need to normalize the computing of the number of adding or removing assertions which represents the distance of the relaxation reasoning.

In our notation, 'W' denotes the number of actions (insertion or deletions) performed.

When W = 0, the WRelaxation coincides with the instance retrieval problem.

WRelaxation by considering separately the individuals

We define in this first part the WRelaxation and explain how an individual is integrated into the instances of a concept and then we discuss the limits of considering separately the individuals.

W + Relaxation: relaxation by adding assertions

This relaxation computes the minimum set of assertions to be added to an ABox so that a given individual becomes relaxed answer of a given concept. Let KB = (T , A) be a consistent knowledge base, C be a concept and W be an integer. We define the function

InsR + W (C,
InsR + W (C, KB) = {a ∈ Ind(A) | ∃A such that: i. A ⊆ A ii. A \ A is a set of atomic assertions such that | A \ A | W iii. KB = (T , A ) is consistent iv. a ∈ InsR(C, KB ) }
Note that, the function InsR + W (C, KB) and all the relaxation functions that we will define can be used with a third parameter representing the context used,

InsR + W (C,
Then, a ∈ InsR + W (C, KB, OW A) ⇒ a ∈ InsR + W (C, KB, GCW A).
Example 4 Let a DL knowledge base KB = (T , A). In the case of an OWA :

T C ≡ (A B) ∀R.P D ≡ B Q E ≡ 1R F ≡ = 2R.P ∃R.∃S.A G ≡ A ∃R.(B Q) H ≡ A ( 3R.B) (∃R.(B Q)) I ≡ ¬A B 1R K ≡ ∀S.G 3R A A(a), ¬A(b), B(f ), ¬B(c), D(c), F (f ), G(d), Q(f ), R(a, b), R(b, d), R(b, f ), R(
The individual "a" is not an instance of "G", but if we add the "R(a, f )" assertion, then "a" will be instance of "G". Hence, a ∈ InsR + 1 (G, KB, OW A), i.e., "a" is a relaxed answer of "G" with distance 1.

The individuals "a" and "c" cannot be relaxed answers of "I" (i.e., a / ∈ InsR + W (I, KB, OW A) ∀W) because the assertions "¬A(a)" and "B(c)" cannot be added, since there will had an inconsistency with "A(a)" and "¬B(c)", knowing that I ¬A B

The individual "d" cannot be relaxed answer of "I" because the concepts "G" and "I" are disjoint.

No individuals can be relaxed answer of "K" because we assume the open world. We cannot guarantee that for a given individual all his "S" role assertions are with an individuals of "G" and that the number of relations is less than or equal to 3 without explicit declaration. The assertions ∀S.G(a) and 3R(a) cannot be constructed from atomic assertions.

In the case of OWA, assertions using some constructors such as "∀" and " n" cannot be constructed from atomic assertions.

In the case of a GCWA : If we add "R(a, f )" assertion in this case, "a" will be relaxed answer of "G" and of "H",

with distance 1.
Hence, "a" is from one operation to the instances of "G" and the instances of "H", there-

fore a ∈ InsR + 1 (G, KB, GCW A) ∩ InsR + 1 (H, KB, GCW A).
The individual "b" will be relaxed answer of "K" if we add the assertion "R(a, f )".

Example 4 illustrates one possible case of the difference between W + Relaxation in the GCWA and in the OWA. We can note that for some concepts the W + Relaxation does not exist in the OWA but exists in the GCWA, concepts built by "∀" constructor for example. We can also note that the number of added assertions in the GCWA is less than or equal to the number of added assertions in the OWA.

W -Relaxation: relaxation by deleting assertions

In this type of relaxation, we are interested by the minimum set of assertions to be deleted from an ABox so that a given individual become relaxed answer of a given concept. Let KB = (T , A) be a consistent knowledge base, C be a concept and let W be an integer.

We define InsR - W (C, KB) as a function which returns the instances of a concept C w.r.t. a knowledge base KB obtained by deleting at most W assertions from the ABox.

Definition 4.4.4 InsR - W (C, KB) = {a ∈ Ind(A) | ∃A such that: i. A ⊆ A ii. A \ A is a set of atomic assertions such that | A \ A | W iii. a ∈ InsR(C, KB ) | KB = (T , A ) }
Note that, W -Relaxation of KB is the knowledge base KB W-obtained by deleting atomic assertions.

The following lemma shows that, in the case of monotonic DLs, W -Relaxation does not extend the set of instances of a concept.

In the case of a OWA :

The relaxation is not possible in this case (see the lemma 4.4.5).

In the case of a GCWA : If we delete the assertion "R(b, d)" or "R(b, f )", "b" will be relaxed answer of "F ".

The individual "b" cannot become relaxed answer of "G" and of "H" because we have ¬A(b) and G H A.

WRelaxation: relaxation by adding/deleting assertions

This type of relaxation deals with the minimum set of assertions to be added to and/or deleted from the ABox so that a given individual become relaxed answer of a given concept. Let KB = (T , A) be a consistent knowledge base, C be a concept and let W be an integer. We define InsR W (C, KB) as a function that return the instances of a concept C w.r.t. a knowledge base KB obtained by adding and/or deleting at most W assertions.

Definition 4.4.6 InsR W (C, KB) = {a ∈ Ind(A) | ∃A such that: i. (A \ A) ∪ (A \ A ) is a set of atomic assertions such that | (A \ A) ∪ (A \ A ) | W ii. KB = (T , A ) is consistent iii. a ∈ InsR(C, KB ) }
Note that, WRelaxation of KB is the knowledge base KB W obtained from KB by adding and/or deleting atomic assertions. Example 6 Let us consider the knowledge base of the example 4.

In the case of a OWA :

The individual "b" will be relaxed answer of "G" if we delete the assertion "¬A(b)" and we add the assertion "A(b)", therefore b ∈ InsR 2 (G, KB, OW A).

In the case of a GCWA :

The individual "f " will be relaxed answer of "K" if we delete the assertion "¬A(b)" and we add the assertion "A(b)", therefore f ∈ InsR 2 (K, KB, GCW A).

If we add "A(e)" assertion and we delete "R(e, b)", "R(e, c)" or "R(e, d)" assertions, "e" will be relaxed answer of "H", therefore e ∈ InsR 2 (H, KB, GCW A).

(T , A) |= C(a) and (T , A) |= C(b)

Let A 1 = A ∪ {A(b), ¬A(a)} and A 2 = A ∪ {A(a), ¬A(b)} (T , A 1 ) |= C(a) and (T , A 2 ) |= C(b). Hence, a ∈ InsR + 2 (C, KB, OW A) and b ∈ InsR + 2 (C, KB, OW A) but it is not possible to build A 3 such that (T , A 3 ) |= C(a) ∧ C(b) and {a, b} ∈ InsR + 2 (C, KB, OW A).
In the Example 8 below, the generation of a unique ABox such that the individuals a and b become relaxed answers of D is possible while however the number of added assertions for b is not minimal.

WRelaxation by considering a set of individuals

We have defined in the first part of the chapter how each individual is integrated in the relaxation of a concept by the application of elementary operations. The elementary operations which allow to integrate all individuals of the relaxation must be consistent between them and keep the consistency of the knowledge base. From a practical point of view, it is not interesting to identify a set of individuals who may not belong to the same consistent knowledge base.

We redefine now the three types of relaxations to take into account the interaction between the elementary operations which allow to integrate each individual. The objective is to built a single consistent ABox which allows to integrate a set of individuals in the relaxation of a given concept.

W + Relaxation: relaxation by adding assertions

Let KB = (T , A) be a consistent knowledge base, C be a concept, and W and N be two integers. We define RxdIR + W (C, KB) as an extension of the W + Relaxation function to take into consideration the interactions between the relaxation of several individuals.

Definition 4.4.8

The set RxdIR + W (C, KB) of relaxed answers of C is defined as follows:

RxdIR + W (C, KB) = {a ∈ Ind(A) | (T , A ) |= C(a)} Such ∃A which satisfies: i. A ⊆ A ii. A \ A is a set of atomic assertions iii. KB = (T , A ) is consistent iv. Dist + (C, KB, A ) W
where Dist + (C, KB, A ) is a distance defined between two ABoxes over the same TBox. Such a distance is application dependent and could be calculated in different ways:

• Global distance, defined at a global level, i.e. it is calculated at the ABox level, as the total number of added assertions (i.e., equal to | A \ A |). This distance is useful when the goal is to minimize the overall amount of knowledge added to an ABox.

• Local distance, defined at a local level, i.e. calculated at the individuals level. Let -Average distance: calculated as the average number of added assertions such that the individuals become relaxed answers of C. It is equal to

average(indDist(a)) ∀a ∈ ( RxdIR + W (C, KB) \ InsR(C, KB) ).
This distance is used when the goal is to minimize the average added knowledge for each individuals.

-Maximal distance: calculated as the largest number of added assertions such that the individuals become relaxed answers of C. It is equal to

maximal(indDist(a)) ∀a ∈ ( RxdIR + W (C, KB) \ InsR(C, KB) ).
This distance is used when the goal is to fix a maximal distance beyond which an individual cannot be considered as a relevant answer to a given query.

It is worth noting that, a W + Relaxation for individual focuses on the relation between an individual and a concept. In the case of an W + Relaxation of a set of individuals, the focus is on the relation between a set of individuals and a concept.

W -Relaxation: relaxation by deleting assertions

Let KB = (T , A) be a consistent knowledge base, C a concept and let W and N be two integers. We define RxdIR - W (C, KB) as the function that extends W -Relaxation to take into consideration the interactions between the relaxation of several individuals. Definition 4.4.9

The set RxdIR - W (C, KB) of relaxed answers of C is defined as follows:

RxdIR - W (C, KB) = {a ∈ Ind(A) | (T , A ) |= C(a)} Such ∃A which satisfies: i. A ⊆ A ii. A \ A is a set of atomic assertions iii. Dist -(C, KB, A ) W
where Dist -(C, KB, A ) is a distance between two ABoxes over a same TBox. As previously, such a distance is application dependent and can be calculated in different ways as discussed for the case of Dist + (C, KB, A ) (Section 4.4.2.1).

WRelaxation: relaxation by adding/deleting assertions

Let KB = (T , A) be a consistent knowledge base, C be a concept, and let W and N be two integers. We define RxdIR W (C, KB) as an extension of WRelaxation to take into consideration the interactions between the relaxation of several individuals.

Definition 4.4.10

The set RxdIR W (C, KB) of relaxed answers of C is defined as follows:

RxdIR W (C, KB) = {a ∈ Ind(A) | (T , A ) |= C(a)} Such ∃A which satisfies: i. (A \ A) ∪ (A \ A ) is a set of atomic assertions ii. KB = (T , A ) is consistent iii. Dist(C, KB, A ) W
where Dist(C, KB, A ) is a distance between two ABoxes over the same TBox. It can be calculated as in the case of Dist + (C, KB, A ) (Section 4.4.2.1) by taking into consideration the addition and deletion of assertions.

Comparison w.r.t. existing reasonings

We investigated in this chapter a new approach for computing relaxed answers of ontological queries. The proposed approach concern several aspects of description logic reasoning as the instance retrieval, the approximation, the relaxation reasoning and the dynamic aspects of the ABox. In the following subsection, we review related work.

ABox abduction

Contrary to the deduction, the abduction [START_REF] Walton | Abductive reasoning[END_REF] is interested in finding the causes of a set of facts. The abduction problem is defined for description logics for the TBox [START_REF] Colucci | Concept abduction and contraction in description logics[END_REF][START_REF] Halland | Tbox abduction in ALC using a DL tableau[END_REF] and also for the ABox [START_REF] Du | Towards practical abox abduction in large OWL DL ontologies[END_REF][START_REF] Klarman | Abox abduction in the description logic ALC[END_REF]. It consists for the TBox (resp. ABox) to identify the set of TBox axioms (resp. ABox assertions) need to be added to a DL knowledge base to allow a TBox axioms (resp. ABox assertions) to be entailed. We are interested in this work to the abduction problem defined for the ABox, because it is similar to one of the problems that we are trying to address in this thesis, i.e. the problem of adding assertions to an ABox to entail other assertions. We can refer to the definition proposed in [START_REF] Klarman | Abox abduction in the description logic ALC[END_REF] for the ABox abduction: The three criteria, consistency, relevance and minimality are often used to limit the number of possible solutions to a ABox abduction problem which is in general infinite.

The choice of these criteria is widely adopted in the literature [START_REF] Klarman | Abox abduction in the description logic ALC[END_REF][START_REF] Aliseda-Llera | Seeking Explanations: Abduction in Logic[END_REF][START_REF] Paul | Approaches to abductive reasoning: an overview[END_REF]. This choice is justified by:

• The consistency: for the practical problems, a solution is interesting if it is consistent with the knowledge base. It must not contradict the knowledge already acquired which is in general non-editable.

• The relevance: the ABox abduction problem is to identify the assertions A to add to a knowledge base for that other assertions Φ are entailed. An obvious solution to this problem is to add Φ to the knowledge base but this solution trivializes the problem instead of really solving it because it is independent of the knowledge base used.

• The minimality: this criterion consist on adding the minimum of necessary assertions to the knowledge base in order to resolve the problem, without adding unnecessary information to the knowledge base. It is necessary to minimize the change of the overall structure of the knowledge base to do not generate unnecessary knowledge or even false.

Klarman et al. [START_REF] Klarman | Abox abduction in the description logic ALC[END_REF] introduce a formal computational framework for ABox abduction in the DL ALC. They propose two novel reasoning for solving this problem. The two introduced reasoning are variants of resolution and tableaux algorithms for the first-order logic. The general idea is to transform the inputs of an abduction problem (KB, Φ) into first order logic and try to construct a refutation proof for KB Φ by proving that KB ∪ ¬Φ ⊥. Model-theoretic and proof-theoretic aspects of abductive reasoning are the basis for resolution. For model-theoretic, the resolution can be considered as to try to find a formula that is unsatisfiable in all models of the knowledge base in which the adductive query is not satisfied (eliminate all non interesting models). For proof-theoretic and for a goal-oriented strategy for example, the resolution use a back chaining to try to derive from the abductive query intermediate results that are connected and so on.

For an ABox abduction, the goal is to identify a set of assertions to be added to an ABox so that a given set of assertions known in advance becomes entailed by the knowledge base, i.e., the input is an assertions set and the output is also an assertions set.

For relaxations that we proposed, the goal is also to identify a set of assertions to be added to (in the case of W + Relaxation), to be removed from (in the case of W -Relaxation)

or to be added to and to be removed from (in the case of WRelaxation) an ABox, the output is an assertions set but the input is not an assertions set, because the set of individuals which may be relaxed is not known (the number of possible combination is exponential). Let C and a an input of a W + Relaxation problem, respectively a concept and an individual, we have that the problem of existence of W for a W + Relaxation and the problem of finding W for a W + Relaxation can be reduced in polynomial time to an ABox abduction problem as following:

• Φ = C(a).
• Find a consistent and minimal Abox abduction solution A.

• Compute W, the number of all atomic assertions.

Note that, this reduction is only possible if the used language allows to transform the assertions of the Abox into atomic assertions.

Other reasonings

Instance retrieval reasoning

The instance retrieval is a standard reasoning for retrieving the instances of a concept.

It consists in finding all individuals names i of the ABox that are instances of a given concept C. It is a costly reasoning for some applications, when the ABox represents a database with a large number of individuals.

The instance retrieval problem is investigated since the first description logics systems [START_REF] Bhushan | Semantic web reasoners and languages[END_REF], the first algorithms reduce [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF][START_REF] Bhushan | Semantic web reasoners and languages[END_REF] the problem to a satisfiability problem but the complexity of the problem resulted in the proposition of several optimization techniques [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF][START_REF] Bhushan | Semantic web reasoners and languages[END_REF]. The reduction of the problem to the datalog programs to exploit the techniques of the theory of databases is also proposed in recent approaches [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Motik | A comparison of reasoning techniques for querying large description logic aboxes[END_REF][START_REF] Hustadt | Reducing shiq-description logic to disjunctive datalog programs[END_REF]. an ABox satisfiability problem. The limits of this approach is that it is very costly, it consists to resolve |ABox| problems of ABox satisfiability.

Optimization techniques

The reduction of an instance retrieval problem to satisfiability problems requires the definition of a satisfiability problem for each individual. This can be very costly for expressive languages. A range of optimization techniques are defined [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] to improve performance. In general, the principle of these techniques is aimed at reducing the size of the search space which is often very large.

This search space is represented in general by a tree, which allows to reusing a few search techniques for a tree.

There are several techniques for satisfiability optimizations, we can cite [START_REF]The Description Logic Handbook: Theory, Implementation, and Applications[END_REF]: the semantic branching search, the local simplification, the dependency directed backtracking, the heuristic guided search and the caching satisfiability 4.5.2.1.3 Reduction to Datalog problems The general interest of the reduction to Datalog approaches [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Motik | A comparison of reasoning techniques for querying large description logic aboxes[END_REF][START_REF] Hustadt | Reducing shiq-description logic to disjunctive datalog programs[END_REF] is to reduce the expressivity gap between the database query language and the description logics as ontology language, to transfer the techniques, evidences and concepts of the database theory to description logics theory. The general principle of these approaches is that the ABox can be considered as an extensional database and the TBox as a set of integrity constraints or a functional dependencies.

Calì et al. [START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF][START_REF] Calì | A general datalog-based framework for tractable query answering over ontologies[END_REF] introduce a family of expressive extension of datalog to reduce the gap between the semantic web and the databases. They defined a special class of tuplegenerating dependency (TGD) so that the boolean conjunctive queries are decidable and of polynomial complexity in general. They have also defined another class of TGD, a negative constraints and equality generating dependencies to define two extensions of Datalog: Datalog 0 ± and Datalog 1 ± . Motik and Sattler [START_REF] Motik | A comparison of reasoning techniques for querying large description logic aboxes[END_REF] developed an algorithm for reducing a DL knowledge base to a disjunctive datalog program and compared a reasoning approaches for querying large description logic Aboxes. They concluded that the translation to datalog is interesting when the TBox is simple and the ABox is large. The authors proved that their extension is strictly more expressive than a few languages of the DL-Lite family and proposed translation functions which are used to rewrite LD-Lite systems in their datalog extension.

In [START_REF] Hustadt | Reducing shiq-description logic to disjunctive datalog programs[END_REF], Hustadt et al. translated a slight restriction of description logic SHIQ (SHIQ -) to disjunctive datalog programs to reuse optimization techniques from deductive databases for resolving the problem of consistency of Aboxes, instance checking and query answering.

Approximation

A description logic system is defined in general by the definition of three components: the language, the knowledge base and the reasoning. An approximation approach may be defined for one or several components. Groot et al. [START_REF] Groot | Approximating description logic classification for semantic web reasoning[END_REF] defined three types of approximations approaches depending on the used component:

• Language Weakening: It consists in a rewriting of the knowledge base in a less expressive language by the elimination of a constructor or an axiom. By reducing the expressivity, the reasoning becomes less costly.

• Knowledge Compilation: It is a pre-processing performed on the knowledge base before the reasoning. It can be the normalization of the knowledge base or the insertion of entailed knowledge to avoid recalculating it each time.

• Approximate Deduction: It consists on the approximation of the logical inference to make it more flexible. In general, the approximed inferences are sound but incomplete, or complete but unsound.

Approximation approaches are generally motivated by three main goals: improving the performance of reasoning, eliminating a constructor or axioms or expanding query answers. We are interested in this work on the expansion query answering approximation.

Performance improvements

The performance improvements approaches [START_REF] Brandt | Approximation and difference in description logics[END_REF][START_REF] Yuan Ren | Soundness preserving approximation for tbox reasoning[END_REF][START_REF] Yuan Ren | Towards soundness preserving approximation for abox reasoning of OWL2[END_REF][START_REF] Pan | Approximating OWL-DL ontologies[END_REF][START_REF] Botoeva | Expressive approximations in DL-Lite ontologies[END_REF] approximate generally the syntax of a language by the elimination of constructors and axioms for translate the language into another less expressive language. They are used in general to improve the performance of a system, make decidable undecidable problems or restrict the language used in a system. The authors of [START_REF] Brandt | Approximation and difference in description logics[END_REF] defined the approximation of a concept as its rewriting in another logic less expressive in optimizing the subsumption between this rewriting and the original concept. They investigated the mapping of ALC to ALE and demonstrate that this mapping always exists. They defined the upper approximation as the minimal subsuming concept and also introduce a syntactic difference operator to calculate the accuracy of the approximation. The main objective of this work is to improve the performance of reasoning despite that the departure language is not very expressive. More precisely, the result of the approximation of a concept C is given by the instances of all his subsumers D that satisfy C E D ⇒ D ≡ E. This result does not necessarily extend the instance set of the concept. The subsumption constraint is very restrictive and the approximation of the concept in this case may be equivalent to the instance retrieval mechanism. The proposed approach does not explore solutions beyond the first subsumers, while this is possible in our case by increasing the value of the parameter W.

In [START_REF] Yuan Ren | Soundness preserving approximation for tbox reasoning[END_REF][START_REF] Yuan Ren | Towards soundness preserving approximation for abox reasoning of OWL2[END_REF] the authors proposed an approximation approach for the instance retrieval that preserves the soundness of the result for performing ABox reasoning. The approximation and the reasoning can be performed in PTime. The principle of approximation is to transform an expressive ontology language (DL RO) to a less expressive ontology language (DL EL ++ ) and a complement table to maintain the complementary relations between concept names.

In this work, the approximation is for the completeness of the result. The result is a subset of the interpretation of the concept. The authors aim is to improve the performance of reasoning which can be performed in PTime.

The co-authors of [START_REF] Pan | Approximating OWL-DL ontologies[END_REF] proposed an approximation of OWL-DL language to DL-Lite language and of [START_REF] Botoeva | Expressive approximations in DL-Lite ontologies[END_REF] from OWL 2 to DL-LiteA. Ecke et al. [START_REF] Ecke | Answering instance queries relaxed by concept similarity[END_REF] proposed a new algorithm for relaxed instances query answering. This algorithm use a concept similarity measures to relax the classical instance retrieval reasoning but it is independent of the chosen concept similarity measures approach. The general principle of the algorithm is very simple, to relax instances of a concept C they compute instances of all concepts D i such as the similarity value of the pair (C, D i ) is greater than the degree of relaxation. The proposed approach can be used with any similarity measure but the quality of relaxed instances depends on the quality of the used similarity measure. The authors discuss also two major aspects of the relaxed instance query answering: the maximum degree of relaxation and taking into account the choice of the part of the query that can be relaxed.

In [START_REF] Stuckenschmidt | Partial matchmaking using approximate subsumption[END_REF][START_REF] Stuckenschmidt | Approximate subsumption for complex description logics[END_REF] and C. The advantage of the approach is that it does not depend on any language. Its limits are the low accuracy of the results which depends on the selected sub vocabulary and the incoherence of results in some cases.

ABox revision/update/erasure

These approaches investigate the dynamic aspect of a knowledge base. The dynamic aspects of a knowledge related to our work are those which concern the Abox, therefore, we present only the ABoxes work. These work concerns two main problems:

• ABox update and erasure problem: the update/erasure of a knowledge base is an old problem in logic and in database [START_REF] Winslett | A model-theoretic approach to updating logical databases[END_REF][START_REF] Fagin | Updating logical databases[END_REF][START_REF] Winslett | A framework for comparison of update semantics[END_REF]. For the ABox, the problem is the definition of transformation occurred on the knowledge base after adding and/or deleting assertions.

• ABox revision problem: the evolution or the revision of knowledge is a manual procedure. Its integration in the knowledge based systems is necessary for some A revision operator [START_REF] Chang | An abox revision algorithm for the description logic el_bot[END_REF]:

• must preserve the consistency of knowledge bases;

• must entail the new information and preserve the protected part;

• should not change the original knowledge base if there is no conflict;

• should be independent of the syntactical forms of knowledge bases;

• should guarantee a minimal change.

The result of the revision of a DL knowledge base KB must be independent of the syntax of KB. It can be carried out by two operations: adding and/or deleting knowledge.

For both cases, the result must be a consistent knowledge base KB [START_REF] Lenzerini | On the evolution of the instance level of dl-lite knowledge bases[END_REF]. Two main approaches to define the distances between KB and KB are distinguished by the definition of minimal change [START_REF] Lenzerini | On the evolution of the instance level of dl-lite knowledge bases[END_REF][START_REF] Chang | An abox revision algorithm for the description logic el_bot[END_REF]:

• Model based approaches: the result of a revision operator is defined by a set of models. The semantics of minimal change is the distance between the model of the new knowledge base and the model of the initial knowledge base. They are independent of the syntax of the knowledge base but only works for limited forms of LD-Lite family. One of these basic problems is to characterize the necessary language to capture the results of all models.

• Formula based approaches: the result is defined in terms of formulas. They can be used for more expressive DL as SHOIN but depend on the syntax of the knowledge base. The semantics of minimal change is reflected in the minimality of formulas which will be changed. One of these basic problems is that the formula is not unique in general.

The set of models corresponding to the update/erasure of a knowledge base K may not be expressible in the language of KB [START_REF] Liu | Updating description logic aboxes[END_REF]. De Giacomo et al. [START_REF] De | On the approximation of instance level update and erasure in description logics[END_REF] investigate this problem and define the sound approximation and the maximal approximation of a terminology to introduce the maximal approximation of an ABox update/erasure to characterize the ABoxes which capture the better the update. They prove that this maximal approximation is unique and present a polynomial algorithm to calculate it for DL-Lite F .

In [START_REF] Lenzerini | On the evolution of the instance level of dl-lite knowledge bases[END_REF], the authors investigated the problem of ABox update/erasure for the knowledge base which verify that the new knowledge base can be expressed in the same language as the initial knowledge base. They propose an algorithm to calculate a knowledge base after an insertion of assertions and another algorithm to calculate a knowledge base after a deletion of assertions for DL-Lite A .

Gao et al. [START_REF] Gao | A new operator for abox revision in dl-lite[END_REF] proposed an operator for the DL-Lite ABox revision. This operator deletes an assertion of each minimal inconsistent sub set from the initial ABox A up to found the revised ABox A .

We have presented in this section different approaches which investigate in the dynamic aspect of Aboxes. We have presented how to integrate a new knowledge with maintaining the consistency of the knowledge base and how to characterize a knowledge base after adding and/or deleting assertions. These aspects are interesting and related to our work. We also add and delete assertions to integrate new knowledge but the problem changes, the sets of assertions to add and/or delete are initially unknown and the new knowledge to integrate is unknown also. The definition of the interpretation update changes also.

Conclusion

In this chapter, we investigated a new approach to relax answers of ontological queries that take into consideration the knowledge in an ABox. The main idea is to determine the minimum knowledge to add to or delete from the ABox so that a relaxed answer become an exact answer. The benefit of such an approach lies in the exploitation of the knowledge that is hidden in the data (in addition to the terminology) in order to compute relaxed answers and the parameterization of the relaxation.

The WRelaxation and its principle can be used in many applications. Naturally, as an instance retrieval reasoning or for the evolution of an ABox, but also for other applications less obvious as the computing of membership degree of an individual i in a concept C. This value could used to compute a distance between concepts or individuals.

The distance between two individuals can be defined as the number of common concept an role assertions or the minimum or maximum number of different concept an role assertions. The distance between two concepts can be defined as the average distance between all individuals of the two concepts or the minimum or maximum distance between two individuals of the two concepts or by another distance methods. These distances can be used for indexation or to investigate problems based on a similarity matching for semantic retrieval.

In our work, we used assertions of atomic concepts (or its negation) and roles. It will be interesting to extend our approach to assertions of defined concepts and roles and propose to normalize the computation of the distance in this context. This will extend the covered language constructed from adding/deletion assertions especially in the case of OWA for some constructors such as "∀" and " n".

We will explore in the next chapter a decision and optimization problems. The WRelaxation is a very costly reasoning, we investigate these problems with the ELU (¬) ⊥ language and we present after, the challenges for more expressive languages.

Introduction

We proposed in the previous chapter a new relaxation reasoning for instance retrieval.

The novelty is that the reasoning is based on the ABox instead of the TBox used by classical approaches.

Many problems related to WRelaxation are worth to explore, such as computing the set of relaxed answers for a given ontological query, computing the minimal distance W for a given individual w.r.t. a query Q or the existence of relaxed answers for a given query.

We present in this chapter the results concerning some interesting decision problems and related optimization problems w.r.t. WRelaxation in the context of the OWA and the GCWA. All the problems related to WRelaxation are studied by considering the language of Table 5.1. We use this language because all types of assertions in this language can be constructed using atomic assertions.

Concept constructors Name

Optimisation Problems

We study in this section three optimisation problems, related to computation of the minimal distance W, needed to make a given individual a instance of a given concept C w.r.t. the two semantics considered in this thesis.

Computing minimal W for W + Relaxation

We are interested in this section in the problem of computing the minimal distance W in the context of W + Relaxation. This problem can be stated formally as follows: Second, we proceed in two steps: construction of the minimal atomic assertions sets and computation of the minimal distance W + . These two steps are detailed below.

Step The proof of the lemma is given on the appendix.

→ rule condition S contains (D 1 D 2 )(x) action M AAS(KB, C, a) = M AAS(KB, C, a) ∪ ({S ∪ {D 1 (x)} \ {(D 1 D 2 )(x)}}) ∪ ({S ∪ {D 2 (x)} \ {(D 1 D 2 )(x)}}) \ {S} → ∃ rule condition S contains (∃R.D)(x) action M AAS(KB, C, a) = MAAS(KB, C, a) ∪ ({S ∪ {R(x, z), D(z)} \ {(∃R.D)(x)}}) ∪ y∈ind(A) ({S ∪ {R(x, y), D(y)} \ {(∃R.D)(x)}}) \ {S} such that z / ∈ ind(A) is an individual. → rule condition S contains (D 1 D 2 )(x) action S = S ∪ {D 1 (x), D 2 (x)} \ {(D 1 D 2 )(x)}
The M AAS computed by Algorithm 1, is used in the second step described below, to compute the minimal distance W + .

Step 2: Computation of the Minimal distance W +

To compute the minimal distance W + , we proceed in two steps: first, we remove from the M AAS computed by Algorithm 1 the sets which are inconsistent with the knowledge base. The obtained set noted M AAS + is computed as follows:

M AAS + (KB, C, a) = {S ∈ M AAS(KB, C, a) | KB ∪ S |= ⊥}.
Each element of M AAS + represents a candidate set of atomic assertions that can be added to KB to make the individual a instance of C. However, some elements of M AAS + contain redundancy, that is to say they include atomic assertions which can be deduced from the knowledge base. Therefore, these sets are not minimal w.r. Finally, the redundant elements of S 1 is removed. We obtain a candidate solution labelled with S 3 = {B(a), R(a, a)} .

The leaf nodes are candidate solutions. The optimal solutions are given by the filled leave node.

Computing minimal W for W -Relaxation

We consider now the problem of computation the minimal W in the context of W -Relaxation. This problem can be stated formally as follows: As in the previous case, to solve this problem, we propose to transform the assertion C(a) to a set of atomic assertions to identify the atomic assertions which are inconsistent with KB, i.e., the atomic assertions to delete. The transformation can generate several candidate sets. The solution is hence to identify the set defining the minimal number of atomic assertions to delete.

We proceed in two steps: construction of the minimal atomic assertions sets and computation of the minimal distance W -.

Step 1: Construction of the Minimal Atomic Assertions Sets (M AAS)

The M AAS(KB, C, a) is computed as previously (Algorithm 1). It is used in the second step described below to identify the set of atomic assertions which are inconsistent KB and compute the minimal distance W -.

Step Finally, candidate solutions are identified. S 1 is a solution but S 2 is not a solution.

The leaf nodes are candidate solutions. The optimal solution are given by the filled leave node.

Computing minimal W for WRelaxation

We consider now the general problem of computing the minimal W in the context of WRelaxation. This problem can be stated formally as follows: As in the previous case, we propose to transform the assertion C(a) into a set of atomic assertions to identify the atomic assertions which cannot be deduced from KB and the atomic assertions which are inconsistent with KB, i.e., the atomic assertions to add and the atomic assertions to remove. The transformation can generate several candidate sets. The solution is hence to identify the set defining the minimal number of atomic assertions to add and to remove.

We proceed in two steps: construction of the minimal atomic assertions sets and computation of the minimal distance W.

Step 1: Construction of the Minimal Atomic Assertions Sets (M AAS)

The M AAS(KB, C, a) is computed as previously (Algorithm 1). It is used in the second step described below to identify the set of atomic assertions which are not deduced from KB and the set of atomic assertions which are inconsistent with KB.

Step The leaf nodes are candidate solutions. The optimal solution are given by the filled leaves nodes.

Complexity

The following lemma gives the complexity of ComputW(C, KB, a). The SAT problem is to decide if there are some assignments to variables of E such that E is true [START_REF] Gu | Algorithms for the satisfiability (SAT) problem: A survey[END_REF].

The SAT problem can be reduced to the ExistW(C, KB, a) problem as follows:

• Each literal "p" is represented by an atomic concept "A p ".

• The boolean formula is transformed into a concept C by replacing each literal "p" by "A p ", each literal "¬p" by "¬A p ", " ∧ " by " " and " ∨ " by " ".

• We start with an empty ABox and we seek if an individual i belongs to a WRelaxation of C.

• The SAT problem will be solved if W exists.

Hence, ExistW(C, KB, a) is at least as hard to SAT and ComputW(C, KB, a) is NPhard (if a decision problem is NP-complete, then the optimization problem is NP-hard).

Example 13 Let a SAT problem P 1 : let a propositional formula E ⇔ (p ∨ ¬q) ∧ (¬p ∨ ¬q) ∧ (p ∨ q), decide if there is an assignement to p and q such that E is true. 2 (C, KB). So, there exists an assignment p = true and q = false such that E is true.

Optimisation problems related to WRelaxation of set of individuals

We study in this section two optimisation problems, related to computation of relaxed answers by considering a set of individuals w.r.t. the two semantics considered in the thesis. We consider first, the problem in the case of W + Relaxation.

Conclusion

In this section, we have defined some of the WRelaxation problems. These problems are: decision problems related to deciding the existence of W needed to make a given individual a instance of a given concept C, and optimisation problems, related to computation of the minimal distance W, needed to make a given individual a instance of a given concept C, and related to computation of relaxed answers by considering a set of individuals, in the case of the three WRelaxation.

• WRelaxation by integrating individuals one by one: The general idea is to determine the minimum knowledge to add to or to remove from an ABox so that a given individual can be considered as an instance of a given concept. Such a quantity of knowledge is defined by counting the elementary operations performed over the Abox. The individuals are integrated into the instances of a concept one by one.

• WRelaxation by integrating a set of individuals: After having presented the limits of the integration of individuals one by one, we redefine the WRelaxation by taking into account the interaction between the elementary operations which allow to integrate each individual. The objective is to form a single consistent ABox which allows for the integration of a set of individuals in the relaxation of a given concept.

• Algorithms for decision problems: we explore a decision problems related to deciding the existence of W needed to make a given individual a instance of a given concept C, and we reduce these problems to known problems of checking the consistency of an ABox w.r.t. a T Box.

• Algorithms for optimisation problems: we study some optimisation problems, related to computation of the minimal distance W, needed to make a given individual a instance of a given concept C, and related to computation of relaxed answers by considering a set of individuals, in the case of the three WRelaxation. We propose three algorithms inspired from tableau algorithm to solve some optimisation problems, related to computation of the minimal distance W.

• Application of WRelaxation: we present the utilisation of WRelaxation with a medical images ontology to improve the semantic images retrieval and to enrich and/or to correct an existing images annotations database.

Future Work

We want to study two extension of our reasoning: to support relaxation constraints and also the generalization of approach to non elementary operations.

Distance extension:

The distance between an individual and a query is computed by counting the number of elementary operations needed to be applied to an ABox in order to make the individual instance of the query. We defined the elementary operations as the adding to or the removing from an ABox, of atomic assertions.

For the open world assumption, the types of assertions which can be constructed with these operations are limited. The assertion ∀R.A(a) for example, cannot be constructed using atomic assertions. It becomes necessary to extend the elementary operations to be able to construct other types of assertions for expressive languages.

Constraints extension:

The main objective of our reasoning is to make flexible, the instance retrieval reasoning for increasing the set of answers. This flexibility is implemented by the adding to or the removing from an ABox of atomic assertions.

Which is not practical when answers must have some properties.

Consider the following example, let a query Q ≡ P olyp ∃color.{red} ∃shape.{flat}, to retrieve the red polyps with flat shape. If we want to relax the query, it is clear that a physician who wants to decide whether he remove a polyp or not seeks to have of polyps as results. It is not interesting to retrieve for example, a red car with a flat shape but rather red polyps or polyps with a flat shape.

We add the notion of prohibited operations to our definition of relaxation. An insertion or a deletion assertion operation is prohibited if it cannot be used to relax an individual.

RésuméL 1 Introduction 1 . 1

 111 'interrogation efficace d'images en utilisant un système de recherche d'image est un problème qui a attiré l'attention de la communauté de recherche depuis une longue période. Dans le domaine médical, les images sont de plus en plus produites en grandes quantités en raison de leur intérêt croissant pour de nombreuses pratiques médicales comme le diagnostic, la rédaction de rapports et l'enseignement. Cette thèse propose un système d'annotation et recherche sémantique d'images gastroentérologiques basé sur une nouvelle ontologie des polypes qui peut être utilisée pour aider les médecins à décider comment traiter un polype. La solution proposée utilise une ontologie de polype et se base sur une adaptation des raisonnements standard des logiques de description pour permettre une construction semi-automatique de requêtes et d'annotation d'images. Une deuxième contribution de ce travail consiste dans la proposition d'une nouvelle approche pour le calcul de réponses relaxées des requêtes ontologiques basée sur une notion de distance entre un individu donné et une requête donnée. Cette distance est calculée en comptant le nombre d'opérations élémentaires à appliquer à une ABox afin de rendre un individu donné x, une réponse correcte à une requête. Ces opérations élémentaires sont l'ajout à ou la suppression d'une ABox, d'assertions sur des concepts atomiques (ou leur négation) et/ou des rôles atomiques. La thèse propose plusieurs sémantiques formelles pour la relaxation de requêtes et étudie les problèmes de décision et d'optimisation sous-jacents. Mots-clés : Requêtes ontologiques, raisonnement de relaxation, recherche sémantique d'images médicales, ontologie de polype. Chapter Context of the study and the statement of the problem

  other concepts and roles and are structured as a hierarchy by axioms. Binary relations between individuals are defined by roles. An axiom represent a relation between two components of the knowledge base. The axioms are generally subset relations between concepts, subset relations between roles, the membership of individuals to concepts and the membership of pairs of individuals to roles. A description logic based knowledge base KB is a pair (T Box T , ABox A). T is the set of concepts, roles, concept axioms and role axioms of the knowledge base, A is the set of individuals and individual axioms of the knowledge base.

  concept instances and assertions of roles for the definition of role instances. What follows is a more detailed view of the syntax and meaning of some definitions: "P erson ≡ Man W oman": is a definition of the concept P erson. " ≡ " is a concept axiom called equivalence. It is used to indicate an equivalence between a concept in its right and another concept in its left. Generally the concept in its right is a concept name (named concept) and the concept in its left is a concept description built from concepts (and / or roles), and concepts (and / or roles) constructors. " " is a concept constructor called disjunction. It is used to build a new concept from two concepts. The new concept is the union of the two sets of individuals of the two concepts. In the definition of the second concept Athlete ≡ P erson ∃ play.Sport, the concept constructor " ", called conjunction, is used. It allows the construction of a new concept with two concepts. The new concept is the intersection of the two sets of individuals of the two concepts. "∃" is a concept constructor using a role R and a concept C. All individuals of this new concept are connected by the role R to at least one individual of the concept C. Therefore, the concept Athlete is a set of individuals of type P erson which are connected by the role play to at least one individual of type Sport, In other words, athletes are people who practice at least one sport. Note that the concept constructor "∃" may not use a concept. In this case, the individuals of the built concept need just to have a link with any other individual. Note also that the concept C may not be a concept name. For the definition of the concept SoccerP layer for example, the concept is built directly and represents a single individual. The concept constructor "{}" uses a set of individuals to create the concept representing them. "∀" is a concept constructor using also a role R and a concept C. All individuals of a concept built with the constructor "∀" are connected by the role R only to individuals of the concept C. Individuals of the concept "∀ engage.SoccerP layer" are connected by the role engage only to individuals of the concept SoccerP layer. In the example, the football teams are defined by the concept F ootballT eam, it must use at least a ball and engage only football players. By this definition, a football team does not have a coach or a president. Other concepts constructors, " ", " " and " = " (with a role R and sometimes a concept C) use constraints on the role cardinality to build a concept. These constraints are on the number of relations that an individual must have with other individuals. For example, the individuals of the concept " 4 participant.Athlete" must have at least four relations using the role participant with individuals of the concept Athlete. For " = 1 play.T eamSport", the individuals of this concept must have exactly one relations using the role play with individuals of the concept T eamSport. A concept axiom is used in the example. It is the subsumption axiom " " which is used to define a subsumption relation between two concepts C and D. "SerieA F ootballChampionship" means that all individuals of SerieA are also individuals of F ootballChampionship. The individual axioms are defined in the ABox. The axiom "C(a)" defines the membership of an individual a to a concept C (we say that a is an instance of C) and another axiom "R(a, b)" defines the membership of two individuals a and b to a role R (we say that the pair (a, b) is an instance of R). In the example, the individual bolt is an instance of the concept Athlete and the individual f ederer is connected to the individual tennis by the role play. Note that other individual axioms can be deduced when combining the ABox and the T Box. For example, as the individual serieA_2014 is an instance of the concept

  descriptions. C D is a concept inclusion axiom. For this axiom, D is a more general concept than C. All instances of C are also instances of D. The concept equality axiom defines equivalence relations between concepts. C ≡ D defines equivalence relation between C and D. All instances of C are also instances of D and all instances of D are also instances of C.

  defines a set of concept inclusion axioms of the form: B C (B is a basic concept and C is a general concept) and the DL-Lite core ABox is formed by a finite set of membership assertions on atomic concepts and on atomic roles, of the form: A(a) or P (a, b).

Example 1

 1 Let KB = (T , A) be the following knowledge base. T = {C ≡ A B} and A = {C(a)}. CW A(KB) = {¬A(a), ¬B(a)}. KB is inconsistent. We have KB |= cwa C(a), KB |= cwa ¬A(a) and KB |= cwa ¬B(a) therefore KB |= cwa ¬C(a). KB entails C(a) and C ≡ A B then KB entails A(a) or KB entails B(a) certainly, but as the case is non-deterministic, we can have three possible cases of entailment: • KB |= cwa A(a) and KB |= cwa B(a) • KB |= cwa ¬A(a) and KB |= cwa B(a) • KB |= cwa A(a) and KB |= cwa ¬B(a) Therefore, at least one of the two assertions A(a) and B(a) must be entailed, but none of these two assertions cannot be entailed from the KB and ¬A(a) and ¬B(a) are added to KB what makes KB + inconsistent.

  e. C I = D I . • Disjointness: Two concepts C and D are disjoint w.r.t. a knowledge base KB if for every model I of KB the intersection of the interpretation of C in I and the interpretation of D in I is empty i.e. C I ∩ D I = ∅.

  edge bases KB = (T , A) and KB = (T , A ) with KB ⊂ KB ((T ⊆ T , A ⊂ A ) or (T ⊂ T , A ⊆ A ) for DL) we have: for any axiom α, KB |= α implies KB |= α. It is nonmonotonic otherwise.

Figure 3 . 1 :

 31 Figure 3.1: Part of the core hierarchy of the polyp ontology. Snapshot taken in Protégé 4.3[10] with the OntoGraf plug-in.

  The image description part is composed by a concept of an image definition, concepts of an image annotation definition subsumed by the image concept and individuals image of previously treated cases, instance of image annotation concepts.The diagnosis part contains the concepts defining a cancer diagnosis as polyps states, standard classifications used in gastroenterology ... etc.

A

  ≡ ∃represents.( I i=0 (∃diagnosis i .Diagnosis i ) J j=0 (∃location j .Location j ) K k=0 (∃measure k .M easure k ) L l=0 (∃observation l .Observation l ) ∃length.F loat ∃width.F loat) Such as: Diagnosis i , Location j , M easure k , Observation l are concepts descriptions and ∀(i, j, k, l): Diagnosis i Diagnosis Location j Location M easure k M easure Observation l Observation diagnosis i , location j , measure k , observation l are roles names and ∀(i, j, k, l): diagnosis i diagnosis location j location measure k measure observation l observation

  specialists. It is a ABox description logic reasoning and formally, it's consist to find from an ABox all individuals i which are instance of a concept C. The concept C represent in our system the user query. It is generated graphically as seen previously. Individuals i are image references, they are instances of one or more annotation concepts.The retrieval of local subsumees is used to find all the subclasses of the query and are also subclass of a standard classification used in gastroenterology. This result can be used to better understand and analyze the definitions of the standard classifications used in gastroenterology. Formally, we find all the concepts C subsumed by the query A and a standard classification concept D, i.e. subsumed by the conjunction of the two concepts A and D. This is a T Box reasoning. The concepts C share all the properties defined in the query and in the standard classification, knowing that these concepts may have other properties that are not expressed in the query.The last implemented reasoning is the retrieval of local subsumers used to find the classes of standard classifications used in gastroenterology which are superclasses of the query. It is also a T Box reasoning. We need to find all concepts C subsumed by a standard classification concept D and which subsume a query A. These concepts C are a classes used in gastroenterology, they share all properties defined in the classification concept D and part or all of the properties defined in the query. The query A is relaxed by the deletion of some of these properties until obtaining a standard class.

Figure 3 . 3 :

 33 Figure 3.3: Application architecture

  The instance retrieval reasoning determines the individuals of the ABox which are instances of a concept C w.r.t. a knowledge base KB. If an individual a is an instance of a concept C w.r.t. a knowledge base KB, all models of KB are also models of C(a).

  KB) which returns the instances of a given concept C w.r.t. a knowledge base obtained by adding at most W assertions to the ABox A. Definition 4.4.1

  KB, OW A) for the OWA and InsR + W (C, KB, GCW A) for the GCWA. We use the function without the third parameter to indicate that the two contexts are taken into account. Note also that, a W + Relaxation of KB is the knowledge base KB W+ obtained by adding to the ABox of KB, at most W atomic assertions. Consider now the case of monotonic DLs. The following property is straightforward from the definition of monotonicity. Lemma 4.4.2 Let KB be a monotonic description logic based knowledge base and let I be an interpretation of KB. Then, ∀I, I |= KB W+ ⇒ I |= KB. Hence, in the case of monotonic DLs, W + Relaxation decreases the number of models of a given knowledge base. Regarding the relation between OWA and GCWA, we exhibit the following first result.Corollary 4.4.3 Let KB be a knowledge base and let C and a be respectively a concept and an individual.

  e, b), R(e, c), R(e, d), R(e, f ), S(a, d), S(b, a), S(f, b)

Lemma 4 . 4 . 5

 445 Let KB be a monotonic description logic based knowledge base. Then, ∀C ∈ Conc(T ), ∀W > 0, InsR - W (C, KB) ⊆ InsR(C, KB). Hence, W -Relaxation is unless in the case of monotonic DL.Example 5 Let the knowledge base of the example 4.

Corollary 4 . 4 . 7

 447 Let KB be a knowledge base and let C be a concept and a an individual. Then, a ∈ InsR W (C, KB, OW A) ⇒ a ∈ InsR W (C, KB, GCW A).

  The previous definitions are provided on the perspective of a single individual. In the case of a relaxation of a set of individuals, possible interactions between the assertions required by distinct individuals are not considered in the definition. An example of such interactions is given in Example 7. Two consistent ABoxes (respectively, A 1 and A 2 ) could be generated to enable respectively the individuals a or b to become an instance of C. However, it is not possible to generate a unique ABox where both a and b are instances of C. Example 7 Let KB = (T , A) be the following knowledge base using the OWA. T = {C ≡ = 1R.A ¬A} and A = {R(a, b), R(b, a)}.

Example 8

 8 Consider the previous knowledge base augmented with the following concept: D ≡ C (B 1 B 2 B 3 ). Here, we need two assertions A(b) and ¬A(a) so that a become relaxed answer of D and also two assertions A(a) and ¬A(b) so that b become relaxed answer of D. But we need five assertions R(a, b), R(b, a), A(b), ¬A(a), B 1 (b), B 2 (b) and B 3 (b) so that a and b become together relaxed answers of D.

  indDist(a) = minimal(| assAdd |) with assAdd ⊆ A \ A and a ∈ InsR(C, (T , A ∪ assAdd)), we give two examples of local distances:

Definition 4 . 5 . 1 (

 451 ABox abduction problem) Let L K and L Q be DLs, KB = (T , A) a knowledge base in L K and Φ a set of ABox assertions in L Q , denoted as the abductive query. We call the tuple (KB, Φ) an ABox abduction problem iff KB Φ and KB ∪Φ ⊥. Definition 4.5.2 (ABox abduction solution) Let L S be a DL and A a set of ABox assertions in L S . A is a (plain) solution to abductive problem (KB, Φ) iff KB ∪ A Φ. It is consistent iff KB ∪ A ⊥, relevant iff A Φ or minimal iff there is no solution B to (KB, Φ) that is minimal with respect to A. B is minimal with respect to A iff there exists a renaming ρ : N I (B) → N I (A), where N I (B) and N I (A) are the sets of individual names from A and B that do not occur in KB, such that A ρB, but for every renaming : N I (A) → N I (B) it holds that B A.

4. 5 . 2 . 1 . 1

 5211 Reduction to satisfiability problems A trivial solution to the problem of the instance retrieval of a concept is to check for each individual in the ABox if it is instance of the concept. It consists to translate an instance retrieval problem to a set of instance checking problems. Then each instance checking problem is transformed to

4. 5 . 2 . 2 . 2

 5222 Query answering expansion It consist in general on the definition of a new non-standard semantic or on a new operator of logical inference. These approaches are used to make flexible the instance retrieval reasoning. They increase in general the number of instances of concepts.

  the author introduces two non-standard interpretations to define the approximation of concepts subsumption. They describe the degree of similarity in terms of the used sub vocabulary. The two non-standard interpretations are equivalent to the standard interpretation in a subset S of the concept set. The first non-standard interpretation is a lower interpretation. It interprets the concepts that do not belong to S by ∅, i.e. for a lower interpretation I, (A I ∪ ¬A I ) = ∅ if A / ∈ S. This interpretation reduces the satisfiability of formulas (add non existing clash). The problem of subsumption is complete but not sound. The second non-standard interpretation is an upper interpretation. It interprets the concepts that do not belong to S by Δ I , i.e. for a upper interpretation I, (A I ∩ ¬A I ) = Δ I if A / ∈ S. This interpretation increases the satisfiability of formulas. The problem of subsumption is sound but not complete. The aim of this work is to propose a new subsumption axiom more flexible than conventional subsumption axiom. This flexibility is configurable and depends on the selected subset of concepts. This work can be used to approximate concepts by defining a new flexible equivalence axiom. This equivalence axiom between two concepts C and D is equivalent to the subsumption defined by the authors between C and D and between D

  applications. Abox revision problem maintain the consistency of the ABox and integrate a new knowledge. Liu et al. [57] use an update U which is a simple consistent ABox to define the update of a interpretation with U : Definition 4.5.3 (Interpretation Update) Let U be an update and I, I interpretations such that Δ I = Δ I . Then I is the result of updating I with U , I U , if for all concept names C and roles names r:C I = (C I ∪ {a I | C(a) ∈ U}) \ {a I | ¬C(a) ∈ U} r I = (r I ∪ {(a I , b I ) | r(a, b) ∈ U}) \ {(a I , b I ) | ¬r(a, b) ∈ U} Definition 4.5.4 (ABox Update) Let A be an ABox and U an update. An ABox A is the result of updating A with U if M (A ) = {I U | I ∈ M (A)}De Giacomo et al.[START_REF] De | On the approximation of instance level update and erasure in description logics[END_REF] use the same principle and define also the erasure of an interpretation. We resume its definition and we use the same format of the first definition for having: Definition 4.5.5 (Interpretation Erasure) Let U be an update and I, I interpretations such that Δ I = Δ I . Then I is the result of erasing I with U, I U , if for all concept names C and roles names r: C I = (C I ∪ {a I | ¬C(a) ∈ U}) \ {a I | C(a) ∈ U} r I = (r I ∪ {(a I , b I ) | ¬r(a, b) ∈ U}) \ {(a I , b I ) | r(a, b) ∈ U} Definition 4.5.6 (ABox Erasure) Let A be an ABox and U an update and M (A) the set of all models of the ABox A. An ABox A is the result of erasing A with U if M (A ) = {I U | I ∈ M (A)} We can also define a standard ABox revision problem by: Definition 4.5.7 (ABox revision problem) Let L K and L Q be DLs, KB = (T , A) a knowledge base in L K and A an ABox in L Q . We call the tuple (KB, A ) an ABox revision problem iff A is consistent w.r.t. T . Definition 4.5.8 (ABox revision solution) Let L S be a DL and A an ABox in L S . A is a solution to revision problem (KB, A ) iff KB = (T , A ) is consistent and KB A .

Problem 5 . 3 . 1 (

 531 ComputW + (C, KB, a)) Let KB = (T , A) be a knowledge base and let C be a concept and a be an individual. The problem ComputW + (C, KB, a) is the problem of computing minimal W such that a ∈ InsR + W (C, KB). To solve ComputW + (C, KB, a) problem, we propose to transform the assertion C(a) to a set of atomic assertions to identify the atomic assertions which are not entailed by KB, i.e., the atomic assertions to add. The transformation can generate several sets of atomic assertions. The solution is hence to identify the set defining the minimal number of atomic assertions to add. First, the knowledge base is unfolded. This task consists in recursively replacing all nonatomic concept name C (resp. non atomic assertion C(a)) defined in T (resp. A) by C ≡ D with D (resp. D(x)).

1 :Algorithm 1 :begin 2 M 3 while a rule of

 1123 Construction of the Minimal Atomic Assertions Sets (M AAS)In this step, we construct the minimum sets of atomic assertions representing the possible decomposition of C(a). Algorithm 1 computes these sets. It consists mainly in the application of the transformation rules of Table5.2 to decompose assertions. The first rule allows to detect entailments and the other three rules allow to eliminate the operators , ∃ and respectively. Algorithm 1 takes as input an assertion C(a) and produces as output the possible sets required to make a instance of C. Computing Minimal Atomic Assertions Sets M AAS. Input: C: a concept, a: an individual, KB = (T , A): a knowledge base Output: M AAS(KB, C, a): sets of atomic assertions 1 AAS(KB, C, a) ← {C(a)};

7 return

 7 M AAS(KB, C, a) ; Inference rule → |= rule condition (D E)(x) ∈ A and E(x) ∈ S and D not contains "∃" and (S ∪ {¬D(x)} \ {E(x)}) / ∈ M AAS(KB, C, a) action M AAS(KB, C, a) = M AAS(KB, C, a) ∪ {S ∪ {¬D(x)} \ {E(x)}} Decomposition rules

Example 9

 9 Let KB = (T , A) be the following knowledge base. T = {C ≡ (A B) ¬B} and A = {}. The application to C(a) of the "→ rule" and the "→ rule" respectively enables to generate the two following sets: set 1 = {A(a), B(a)} and set 2 = {¬B(a)}. Hence, we have M AAS(KB, C, a) = {set 1 , set 2 }. One of the sets set 1 or set 2 is required to make a instance of C, The following lemma ensures the correctness of Algorithm 1. Lemma 5.3.2 Let KB = (T , A) be a knowledge base and let C be a concept and a be an individual. Then, we have KB |= C(a) ⇔ ∃S ∈ MAAS(KB, C, a) | KB |= S.

  t. the number of atomic assertions required to make a instance of C. So, we define the function Res + , that enables to remove redundant elements from a set S as follows: ∀S ∈ M AAS + (KB, C, a), Res + (KB, S) = {P ∈ S | KB |= P }. As a consequence, the function Res + enables to transform any set elements of M AAS + to a minimal set of atomic assertions that can be added to KB to make a instance of C. The cardinality of each set Res + (KB, S), for S ∈ M AAS + (KB, C, a), provides a distance W + for the W + Relaxation of an individual a w.r.t. a concept C. Hence, a minimal distance W + can be computed for these sets as stated by the following lemma: Lemma 5.3.3 Let KB = (T , A) be a knowledge base, C be a concept and a be an individual. The smallest W | a ∈ InsR + W (C, KB) is equal to Min(| Res + (KB, S) |), ∀S ∈ M AAS + (KB, C, a). Example 10 Let a DL knowledge base KB = (T , A) of Table 5.3. We illustrate the different steps of the proposed approach to compute minimal W such that a ∈ InsR + W (C, KB) in the context of OWA. T C ≡ E F D ≡ A B E ≡ D ∃R.(A B) F ≡ ∃S.B A A {a, c} ¬A {b} ¬B {b, c} R {(a, b), (c, a)} B F {a} Table 5.3: Example of knowledge base.

Figure 5 . 1 :

 51 Figure 5.1: Example of computing minimal W for W + Relaxation

Problem 5 . 3 . 4 (

 534 ComputW -(C, KB, a)) Let KB = (T , A) be a knowledge base and let C be a concept and a be an individual. The problem ComputW -(C, KB, a) is the problem of computing minimal W such that a ∈ InsR - W (C, KB).

2 :

 2 Computation of the Minimal distance W -To compute the minimal distance W -, we proceed in two steps: first we define the function Res ⊥ , that enables to identify each atomic assertion of a set S which is inconsistent with the ABox A as follows:∀S ∈ M AAS(KB, C, a), Res ⊥ (KB, S) = {P ∈ A | ¬P ∈ S and S is consistent w.r.t. T }.Each set Res ⊥ (KB, S) represents a candidate set of atomic assertions that can be removed from KB to make the individual a instance of C. However, the removal of this set must make a instance of C, to become a solution.So, we define the function Res- |= , that enables to identify the elements S of M AAS(KB, C, a), such that the removal of Res ⊥ (KB, S) from the ABox make a instance of C as follows: ∀S ∈ M AAS(KB, C, a), Res - |= (KB, C, a) = {Res ⊥ (KB, S) | KB \ Res ⊥ (KB, S) |= C(a)}. As a consequence, the function Res - |= enables to identify from any set elements of M AAS a minimal set of atomic assertions that can be removed from KB to make a instance of C. The cardinality of each set Res - |= (KB, C, a), for S ∈ M AAS(KB, C, a), provides the distance W -for the W -Relaxation of an individual a w.r.t. a concept C. Hence, a minimal distance W -can be computed from these sets as stated by the following lemma: Lemma 5.3.5 Let KB = (T , A) be a knowledge base, C be a concept and a be an individual. The smallest W | a ∈ InsR - W (C, KB) is equal to Min(| Res - |= (KB, C, a) |). Example 11 Let the DL knowledge base KB of Example 10 and a concept G ≡ ∃R.¬A (A B). We illustrate the different steps of the proposed approach to compute minimal W such that c ∈ InsR - W (G, KB) in the context of GCWA. Figure 5.2 shows the computation of the minimal distance W in the context of W -Relaxation. We start with the root of the tree labelled with the assertion G(c). Some edges correspond to the application of the transformation rules while other edges correspond to the computation of Res ⊥ and Res - |= . For example, let the node labelled with {∃R.¬A(c), (A B)(c)} and apply the "→ ∃ rule" to obtain four children nodes labelled respectively with R(c, a), ¬A(a), (A B)(c), R(c, b), ¬A(b), (A B)(c), R(c, c), ¬A(c), (A B)(c) and R(c, x1), ¬A(x1), (A B)(c). The two nodes N 1 and N 2 labelled respectively with S 1 = {R(c, a), ¬A(a), A(c)} and S 2 = {R(c, a), ¬A(a), B(c)} are labelled with elements of M AAS(KB, G, c). Then, we identify atomic assertions of each element of M AAS(KB, G, c), which is inconsistent with KB. S 1 = {A(a)} for S 1 and S 2 = {A(a), ¬B(c)} for S 2 .

Figure 5 . 2 :

 52 Figure 5.2: Example of computing minimal W for W -Relaxation

2 :

 2 Computation of the Minimal distance W To compute the minimal distance W, we proceed in two steps: first we define the same function Res ⊥ of the previous problem. Now, each set Res ⊥ (KB, S) represents a candidate set of atomic assertions that can be removed from KB. It remains now to compute the set of atomic assertions to be added. So, we define the function Res |= , that enables to identify for each element S ∈ M AAS(KB, C, a), the set of atomic assertions which are not deduced from KB as follows: ∀S ∈ M AAS(KB, C, a), Res |= (KB, S) = {P ∈ S | KB \ Res ⊥ (KB, S) |= P } As a consequence, the functions Res |= and Res ⊥ enable us to identify from any set elements of M AAS a minimal set of atomic assertions that can be respectively added to and removed from KB to make a instance of C. The cardinality of each set (Res |= (KB, S)∪Res ⊥ (KB, S)), with S ∈ M AAS(KB, C, a) provides the distance W for the WRelaxation of an individual a w.r.t. a concept C. Hence, a minimal distance W can be computed for these sets as stated by the following lemma: Lemma 5.3.7 Let KB = (T , A) be a knowledge base, C be a concept and a be an individual. The smallest W | a ∈ InsR W (C, KB) is equal to Min(| Res |= (KB, S) ∪ Res ⊥ (KB, S) |), ∀S ∈ M AAS(KB, C, a). Example 12 Let us consider the DL knowledge base KB of Example 10 and a concept G ≡ ∃R.¬A (A B). We illustrate the different steps of the proposed approach to compute minimal W such that c ∈ InsR W (G, KB) in the context of OWA.

Figure 5 .Figure 5 . 3 :

 553 Figure 5.3 shows the computation of the minimal distance W in the context of

Lemma 5 . 3 . 8

 538 The problem ComputW(C, KB, a) is NP-hard.Proof of this lemma is given by the reduction of the boolean satisfiability problem (SAT) explained below.Reduction of SAT problem to ExistW(C, KB, a) problemLet a boolean formula E, defined with propositional variables, constants (true or false), and ∧, ∨, ¬ operators.

P 1

 1 can be reduced to an ExistW(C, KB, a) problem P 2 as follows : P 2 : p and q are represented by atomic concepts A and B respectively, KB = (T , A), T = {A, B, C}, A = ∅, Ind(A) = {a}, C ≡ (A ¬B) (¬A ¬B) (A B). The problem is to decide if ∃W such that a ∈ InsR + W (C, KB). For A = A∪{A(a), ¬B(a)}, a is instance of C therefore ∃W = 2 and a ∈ InsR +

Problem 5 . 4 . 1 (

 541 RlxComputW + (C, KB)) Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem RlxComputW + (C, KB) is the problem of computing RxdIR + W (C, KB), the set of relaxed instances of the concept C, by adding atomic assertions, with a distance W.The lemma below enables to use the algorithm of computing W for a W + Relaxation to construct a solution. The constructed solutions (element of M AAS + ) for each individual can be combined w.r.t. criteria used by a given distance function.Lemma 5.4.2 Let L be the language of Table 5.1 and let KB = (T , A) be a L-knowledge base, C be a L-concept definition, a, b be individuals of the ABoxA and let W 1 , W 2 , W 3 be integers. Then, a ∈ InsR + W 1 (C, KB), b ∈ InsR + W 2 (C, KB) ⇒ ∃W 3 such as {a, b} ⊆ RxdIR + W 3 (C, KB).We consider now, the optimisation problem in the general case of WRelaxation: Problem 5.4.3 (RlxComputW(C, KB)) Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem RlxComputW(C, KB) is the problem of computing RxdIR W (C, KB), the set of relaxed instances of the concept C, by adding and removing atomic assertions, with a distance W. relaxation instances of the concept C by adding and removing assertions with a distance W, RxdIR W (C, KB). The lemma below enables to use the algorithm of computing W for a WRelaxation to construct a solution. Lemma 5.4.4 Let L be the language of Table 5.1 and let KB = (T , A) be a L-knowledge base, C be a L-concept definition, a, b be individuals of the ABox A and let W 1 , W 2 , W 3 be integers. Then, a ∈ InsR W 1 (C, KB), b ∈ InsR W 2 (C, KB) ⇒ ∃W 3 such as {a, b} ⊆ RxdIR W 3 (C, KB).

Problem A. 2 . 2 (

 22 ExistW -(C, KB)) : Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer.The problem ExistW -(C, KB) is the problem of deciding whether InsR - W (C, KB, GCW A) is not empty. Problem A.2.3 (ExistW(C, KB)) : Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem ExistW(C, KB) is the problem of deciding whether InsR W (C, KB) is not empty. Problem A.2.4 (NoEmptyW + (C, KB)) Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem NoEmptyW + (C, KB) is the problem of deciding whether there exists an integer W such that RxdIR + W (C, KB) is not empty. Problem A.2.5 (NoEmptyW -(C, KB)) Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem NoEmptyW -(C, KB) is the problem of deciding whether there exists an integer W such that RxdIR - W (C, KB, GCW A) is not empty. Problem A.2.6 (NoEmptyW(C, KB)) Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem NoEmptyW(C, KB) is the problem of deciding whether there exists an integer W such that RxdIR W (C, KB) is not empty.A.2.1 Optimisation problemsProblem A.2.7 (RlxNoEmptyW + (C, KB)) : Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem RlxNoEmptyW + (C, KB) is the problem of computing minimal W for that the relaxation instances of the concept C by adding assertions RxdIR + W (C, KB) is not empty. Problem A.2.8 (RlxNoEmptyW -(C, KB)) : Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem RlxNoEmptyW -(C, KB) is the problem of computing minimal W for that the relaxation instances of the concept C by removing assertions RxdIR + W (C, KB, GCW A) is not empty. Problem A.2.9 (RlxNoEmptyW(C, KB)) : Let KB = (T , A) be a knowledge base and let C be a concept and W be an integer. The problem RlxNoEmptyW(C, KB) is the problem of computing minimal W for that the relaxation instances of the concept C by adding and removing assertions RxdIR + W (C, KB) is not empty.

  Contents 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 2.2 Introductory example . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.1 TBox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.2 ABox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.3 DL Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 Open World Assumption Semantics . . . . . . . . . . . . . . . . . . . 16 2.4.2 Closed World Assumption Semantics . . . . . . . . . . . . . . . . . . 16 2.5 Reasoning Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5.1 Reasoning Tasks for Concepts . . . . . . . . . . . . . . . . . . . . . . 18 2.5.2 Reasoning Tasks for ABoxes . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 The DL Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6.1 Monotonic DL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.6.2 Non-monotonic DL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Table 2

 2

	.1. It describes briefly

T is the T Box. It contains definitions of concepts, of roles, of concept axioms and of role axioms. A is the ABox. It contains assertions of concepts for the definition of

Table 2 .

 2

1: Example of DL based knowledge base.

Table 2 . 2

 22

: Concept constructors of ALCHOQ(¬)

• The concept equality axiom and the concept inclusion axiom. We can define by the concept inclusion axiom a concept hierarchy. Let C and D be two concept

  an interpretation I satisfies an axiom ax or a knowledge base KB, then it is a model of ax noted I |= ax or of KB noted I |= KB. A knowledge base KB is satisfiable iff a model M such that M |= KB exists.

represents many different interpretations. The absence of information in an ABox

	only indicates lack of knowledge. A knowledge not belonging to the knowledge base can
	be true or false. Only, a part of the knowledge of the world is represented.
	The entailment in the context of OWA is defined by [15]:
	Definition 2.4.1 A knowledge base KB = (T , A) entails an axiom α (written KB |= α)
	iff for every model M of KB, M |= α (i.e., M |= KB implies M |= α).

  role and a, b two individuals. Let P K be the set of all positive clauses constructed from

	AS. A positive clause in this case is a disjunction of assertions A(a) and R(a, b). The
	generalized closed world assumption set of KB, annotated GCW A(KB), is defined as
	follows: GCW A(KB) = {¬p | p ∈ AS, ∀K ∈ P K, KB |= p, and if KB |= (p ∨ K) then
	KB |= K}. The entailment in the context of GCWA is defined by [37]:
	Definition 2.4.3 A knowledge base KB = (T , A) entails an assertion α considering
	generalized closed world assumption (written KB |= gcwa α) iff KB * |= α, with KB * =
	KB ∪ GCW A(KB).
	Back to the introductory example (section 2.2): {¬Man(acM ilan), ¬W oman(acM ilan),
	¬winCup(acM ilan, van), ¬winCup(acM ilan, bolt), ¬winCup(acM ilan, f ootball),
	¬winCup(acM ilan, lopez), ¬winCup(acM ilan, torres), ¬winCup(acM ilan, f ederer),
	¬winCup(acM ilan, tennis),	¬winCup(acM ilan, elshaarawy),
	¬winCup(acM ilan, rugby),	¬winCup(acM ilan, acM ilan),
	¬winCup(acM ilan, serieA 2 014), } ⊂ GCW A(KB)
	Hence, KB |= gcwa (¬SoccerP layer ∀winCup.U ef aChLeagueCup)(acM ilan)

  KB D or KB |= C D) if for every model I of KB the interpretation of C in I is a subset of the instances of D i.e. C I ⊆ D I .

	Another example is the subsumption problem. The problem is to try to retrieve a sub-
	sumption property between two concepts. A concept C is subsumed by a concept D if
	for every model of KB the instance of C is a subset of the instance of D. If a concept C
	is subsumed by a concept D, the knowledge 'for all instances i of C, i is an instance of
	D is logically inferred.
	Let a knowledge base KB. Some properties of concepts are [15]:
	• Satisfiability: A concept C is satisfiable w.r.t. a knowledge base KB if there exist
	a model I of KB such that the interpretation of C in I is nonempty i.e. C I = ∅.
	• Subsumption: A concept C is subsumed by a concept D (denoted C D) w.r.t.
	a knowledge base KB (denoted C
	Concepts are the intentional part of the knowledge base. They allow to regroup individ-
	uals, to structure and organize a domain. The properties of concepts and the relations
	between concepts are source of logical inferences.
	For example, testing the satisfiability of a concept; a concept C is satisfiable w.r.t. a
	knowledge base KB if there exist an interpretation that is a model of KB such that C
	denotes a nonempty set in this interpretation. When a concept C is unsatisfiable, the
	knowledge: for all individuals i of the ABox, i is not a instance of C becomes explicit
	(logically inferred) by this property.

• Equivalence: Two concepts C and D are equivalent w.r.t. a knowledge base KB if for every model I of KB the interpretation of C in I is equal to the interpretation of D in I i.

Table 2

 2

	.1.

Table 3 .

 3

	8VHU VHOHFWHG FRQFHSWV
		ƐƚŽŵĂĐŚ
			2EWDLQHG DQQRWDWLRQ TXHU\
		ŽƌĂŶŐĞ
		ŚĂĞŵŽƌƌĂŐŚŝĐ
			$QQRWDWLRQ TXHU\
	RUDQJH	KDHPRUUKDJLF	VWRPDFK	FRQVWUXFWLRQ
			FRORU ӷ	REVHUYDWLRQ
			^RUDQJH` ӷ	2EVHUYDWLRQ
			PXFRXV ӷ	REVHUYDWLRQ
			^KDHPRUUKDJLF`ӷ	2EVHUYDWLRQ
			ORFDWLRQ ӷ	ORFDWLRQ
			^VWRPDFK`ӷ	/RFDWLRQ
		,PDJH GHILQLWLRQ
			8VHG NQRZOHGJH
		Figure 3.2: Annotation/query construction
	The annotation generation process dependent and uses the definition of the Image
	concept. The same principle is used to generate other types of queries, the classes of
	polyps for example. The proposed interface is well suited to generate other types of
	queries and easily extensible for other needs.
	Note that, the image annotation is generated by selecting concepts and individuals
	of the ontology. Roles and relationships between concepts and between individuals are
	generated automatically which restricts the expressivity of the query language. It is
	interesting to improve the query modality to allow the construction of other types of
	queries.

O 2EVHUYDWLRQ O ӹ ѩOHQJWK)ORDW ӹѩZLGWK)ORDW 1: Implemented reasonings.

  , h 2 , h 3 , h 4 , h 5 , h 6 , h 7 , h 8 }

		T
	Image ≡ ∃represent.((∃diagnosis.Diagnosis) (∃location.Location)
		(∃measure.M easure) (∃observation.Observation))
	Lesion ≡ ∃growOn.M ucosa ∃state.{lesionnel}
	P olyp ≡ Lesion ∃depth.Superf icial ∀mayImply.Cancer
	P arisI ≡ P olyp ∃shape.{raised}
	P arisII ≡ P olyp ∃shape.F lat
	P arisIII ≡ P olyp ∃shape.{ulcerated}
	LesionShape ≡ {ulcerated, raised} F lat
	Histology ≡ {h 1 Color ≡ {yellow, pink, red, black, brown, clear}
	P arisI P arisIII ≡ ⊥
	Lesion	Diagnosis
	Histology	Diagnosis
	Color	Observation
	class	diagnosis
	color	observation
	histology	diagnosis
	Query 1 ≡ ∃represent.(∃class.P aris1	1 class.T hing)
	Query

2 ≡ ∃represent.(∃color.{pink, red} ∃class.P aris3 ∃histology.{h 6 }) A P aris2(p 1 ), P aris2(p 2 ), P aris3(p 2 ), class(image 1 , p 1 ), class(image 2 , p 2 ) color(image 1 , clear), color(image 2 , red), color(image 3 , clear), histology(image 1 , h 1 )

Table 5 .

 5 We consider first, the following existence problem in the case of W + Relaxation: Theorem 5.2.2 Let L be the language of Table5.1, let KB = (T , A) be a L-knowledge base and C be a L-concept definition. Let a be an individual of the ABox A. Then:∃W such as a ∈ InsR + W (C, KB) ⇔ A ∪ {C(a)} is consistent w.r.t. T .We consider now, the existence problem in the general case of WRelaxation:

	1: Used concept constructors

The theorem below provides a full characterization of the ExistW + (C, KB, a) problem in both OWA and GCWA. Problem 5.2.3 (ExistW(C, KB, a)) Let KB = (T , A) be a knowledge base and let C be a concept and a be an individual of the ABox A. The problem ExistW(C, KB, a) is the problem of deciding whether there exists an integer W such that a ∈ InsR W (C, KB). We give below a full characterization of the problem ExistW(C, KB, a) in both OWA and GCWA. Theorem 5.2.4 Let L be the language of Table 5.1, let KB = (T , A) be a L-knowledge base and C be a L-concept definition. Let a be an individual of the ABox A and let A the set of all atomic assertions of A. Then: ∃W such as a ∈ InsR W (C, KB) ⇔ (A \ A ) ∪ {C(a)} is consistent w.r.t. T . The proof of the theorem is given in the appendix. Theorem 5.2.4 reduces also ExistW(C, KB, a) to a known problem of checking the consistency of an ABox w.r.t. a T Box.

Table 5

 5

.2 can be applied to a set S ∈ M AAS(KB, C, a) do 4 Apply an inference rule ; 5 if no inference rule can be applied then 6 Apply a decomposition rule ;

Table 5 . 2

 52

: Transformation rules of M AAS computing algorithm.

Acknowledgements

Conclusions and Future Work

In this thesis, two main problems are investigated: a semantic gastroenterological image retrieval and a relaxed answers for ontological queries.

We proposed and implemented a semantic gastroenterological images annotation and retrieval system based on a new polyp ontology to help physicians, to decide whether they remove a polyp or not. The system includes:

• Ontology: we use description logics as formalism to define the polyp ontology. The knowledge collected about polyps is used for diagnosing cancer which is based on the analysis of polyps present in an organ. The principle is to clearly identify the type and the state of the polyp by retrieving its standard classes used in gastroenterology.

• Annotation: An annotation (or query) of an image is manually generated using an interactive interface. We use semantic information to describe the content of the image, i.e., concepts, individuals or roles of the polyp ontology.

• Reasoning: we have implemented three types of reasoning: a standard reasoning which is the instance retrieval and two other reasonings, a local subsumees retrieval and a local subsumers retrieval which are a slight modifications of the standard subsumption reasoning.

We proposed also a new approach for computing relaxed answers of ontological queries based on a notion of an edit distance of a given individual w.r.t. a given query. Such a distance is computed by counting the number of elementary operations needed to be applied to an ABox in order to make a given individual a correct answer to a given query.

The considered elementary operations are added to or removed from an ABox, assertions of the form of an atomic concept (or its negation) and/or atomic roles. The main goal is to increase the number of concepts instances according to some defined criteria. In particular, we investigate:

• KB W+ is consistent.

is consistent w.r.t. T .

Therfore : ∃W such as a ∈ InsR + W (C, KB) ⇒ A ∪ {C(a)} is consistent w.r.t. T .

For A ∪ {C(a)} is consistent w.r.t. T ⇒ ∃W such that a ∈ InsR + W (C, KB) Let L be the language supporting the concepts constructors of Table 5.1 and let C be a L-concept definition and an individual a. We can transform the assertion C(a) into an equivalent set of assertions on atomic concepts, on negation of atomic concepts and on atomic roles. This set may not be unique.

The transformation of the assertion C(a) is a finished set, let S be one of the decomposition sets :

• S contains only assertions on atomic concepts, on negation of atomic concepts and on atomic roles.

• A ∪ S is consistent w.r.t. T .

• (T , A ∪ S) |= C(a).

There exists then at least one set that satisfies the constraints of the W + Relaxation.

A.1.2 Proof of Theorem 5.2.4

For ∃W such as

• KB W is consistent. • S ∪ A contains only assertions on atomic concepts, on negation of atomic concepts and on atomic roles.

• (A \ A ) ∪ S is consistent w.r.t. T .

• (T , (A \ A ) ∪ S) |= C(a).

There exists then at least one set that satisfies the constraints of the WRelaxation.

Therefore : → rule: We must prove that KB |= C(a)

We define a canonical interpretation I A such that:

1. Δ I A of I A consists of all the individual names occurring in A.

∀C, C I