We outline DL-Media, an ontology mediated multimedia information retrieval system, which combines logic-based retrieval with multimedia featurebased similarity retrieval. An ontology layer is used to define (in terms of a fuzzy DLR-Lite like description logic) the relevant abstract concepts and relations of the application domain, while a content-based multimedia retrieval system is used for feature-based retrieval. We will illustrate its logical model, its architecture, its representation and query language and the preliminary experiments we conducted.
The DL-MEDIA architecture has two basic components: the DL-based ontology component and the (feature-based) multimedia retrieval component (see Figure 1).
The DL-component supports both the definition of the ontology and query
answering. In particular, it provides a logical query and representation language, which is an
extension of the DL language DLR-Lite [
The (feature-based) multimedia retrieval component, supports the retrieval of text
and images based on low-level feature indexing. Specifically, we rely on our MIR
system MILOS 1. MILOS (Multimedia Content Management System) is a general purpose
software component that supports the storage and content-based retrieval of any
multimedia documents whose descriptions are provided by using arbitrary metadata models
represented in XML. MILOS is flexible in the management of documents containing
different types of data and content descriptions; it is efficient and scalable in the
storage and content-based retrieval of these documents [
The query answering procedure is as follows: a user submits a conceptual query (a conjunctive query) to the the DL-component. The DL-component will then use the
ontology to reformulate the initial query into one or several queries to be submitted to MILOS (that acts as a Web Service), which then provides back the top-k answers for each of the issued queries. The ranked lists will then be merged into one final top-k result list and displayed to the user. 3
For computational reasons the particular logic DL-MEDIA adopts is based on an
extension of the DLR-Lite [
DL-MEDIA syntax. DL-MEDIA supports concrete domains with specific predicates
on it. The concrete predicates that DL-MEDIA allows are not only relational predicates
such as ([i] ≤ 1500) (e.g. the value of the i-th column is less or equal than 1500), but
also similarity predicates such as ([i] simT xt !logic, image, retrieval!), which given
a piece of text x appearing in the i-th column of a tuple returns the system’s degree (in
[
Formally, a concrete domain in DL-MEDIA is a pair #ΔD, ΦD$, where ΔD is an
interpretation domain and ΦD is the set of domain predicates d with a predefined arity n
and an interpretation dD: ΔDn → [
DL-MEDIA allows to specify the ontology by relying on axioms. Consider an alphabet of n-ary relation symbols (denoted R) and an alphabet of unary relations, called atomic concepts (and denoted A). A DL-MEDIA ontology O consists of a set of axioms. An axiom is of the form
Rl1 ! . . . ! Rlm " Rr , where m ≥ 1, all Rli and Rr have the same arity and where each Rli is a so-called lefthand relation and Rr is a right-hand relation. They have the following syntax (h ≥ 1): Rr −→ A | ∃[i1, . . . , ik]R Rl −→ A | ∃[i1, . . . , ik]R | ∃[i1, . . . , ik]R.(Cond1 ! . . . ! Condh) Cond −→ ([i] ≤ v) | ([i] < v) | ([i] ≥ v) | ([i] > v) | ([i] = v) | ([i] (= v) |
([i] simT xt !k1, . . . , kn!) | ([i] simImg U RN ) where A is an atomic concept, R is an n-ary relation with 1 ≤ i1, i2, . . . , ik ≤ n, 1 ≤ i ≤ n and v is a value of the concrete interpretation domain of the appropriate type.
Informally, ∃[i1, . . . , ik]R is the projection of the relation R on the columns i1, . . . , ik (the order of the indexes matters). Hence, ∃[i1, . . . , ik]R has arity k.
On the other hand, ∃[i1, . . . , ik]R.(Cond1 ( . . . ( Condl) further restricts the projection ∃[i1, . . . , ik]R according to the conditions specified in Condi. For instance, ([i] ≤ v) specifies that the values of the i-th column have to be less or equal than the value v. So, e.g. suppose we have a relation Person(firstname, lastname, age, email, sex) then
∃[
Concerning queries, a DL-MEDIA query consists of a conjunctive query of the form q(x) ← R1(z1) ∧ . . . ∧ Rl(zl) , where q is an n-ary predicate, every Ri is an ni-ary predicate, x is a vector of variables, and every zi is a vector of constants, or variables. We call q(x) its head and R1(z1) ∧ . . . , ∧Rl(zl) its body. Ri(zi) may also be a concrete unary predicate of the form (z ≤ v), (z < v), (z ≥ v), (z > v), (z = v), (z *= v), (z simT xt !k1, . . . , kn!), (z simI mg U RN ), 2 http://en.wikipedia.org/wiki/Uniform_Resource_Name where z is a variable, v is a value of the appropriate concrete domain, ki is a keyword and U RN is an URN. Example queries are: q(x) ← Sunrise On Sea(x)
// find objects about a sunrise on the sea q(x) ← CreatorName(x, y) ∧ (y =! paolo!) ∧ Title(x, z), (z simTxt !tour!)
// find images made by Paolo whose title is about ’tour’ q(x) ← ImageDescr(x, y) ∧ (y simImg urn2)
// find images similar to a given image identified by urn2 q(x) ← ImageObject(x) ∧ isAbout(x, y1) ∧ Car(y1) ∧ isAbout(x, y2) ∧ Racing(y2) // find image objects about cars racing We note that a query may also be written as
q(x) ← ∃yφ(x, y) , where φ(x, y) is R1(z1) ∧ . . . ∧ Rl(zl) and no variable in y occurs in x and viceversa. Here, x are the so-called distinguished variables, while y are the so-called non distinguished variables, which are existentially quantified.
For a query atom q, we will write #q(c), s$ to denote that the tuple c is instance of the query atom q to degree at least s.
DL-MEDIA semantics. From a semantics point of view, DL-MEDIA is based on
mathematical fuzzy logic [
Given a concrete domain #ΔD, ΦD$, an interpretation I = #Δ, ·I $ consists of a fixed
infinite domain Δ, containing ΔD, and an interpretation function ·I that maps
– every atom A to a function AI : Δ → [
We also assume to have one object for each constant, denoting exactly that object. In other words, we have standard names, and we do not distinguish between the alphabet of constants and the objects in Δ. Furthermore, we assume that the relations have a typed signature and the interpretations have to agree on the relation’s type. For instance, the second argument of the Title relation (see axiom 2) is of type String and any interpretation function requires that the second argument of TitleI is of type String. To the easy of presentation, we omit the formalization of this aspect and leave it at the intuitive level.
In the following, we use c to denote an n-tuple of constants, and c[i1, ..., ik] to denote
the i1, . . . , ik-th components of c. For instance, (a, b, c, d)[
Concerning concrete comparison predicates, the interpretation function ·I has to satisfy ([i] ≤ v)I(c!) = 1 if 0 otherwise c![i] ≤ v and similarly for the other comparison constructs, ([i] < v), ([i] ≥ v), ([i] > v) and ([i] = v) | ([i] *= v).
Concerning the concrete similarity predicates, the interpretation function ·I has to
satisfy
([i] simT xt !k1, . . . , kn!)I(c!) = simT xtD(c![i],! k1, . . . , kn!) ∈ [
Concerning axioms, as in an interpretation each Rli(c) has a degree of truth, we
have to specify how to combine them to determine the degree of truth of the conjunction
Rl1 ( . . . ( Rlm. Usually, in fuzzy logic one uses a so-called T-norm ⊗ to combine the
truth of “conjunctive” expressions 3 (see [
In DL-MEDIA, to be compliant with the underlying MILOS system, the T-norm is fixed to be Go¨del conjunction.
The interpretation function ·I has to satisfy: for all c ∈ Δk and n-ary relation R: (∃[i1, . . . , ik]R)I(c) = supc!∈Δn, c![i1,...,ik]=c RI(c!) (∃[i1, . . . , ik]R.(Cond1 ! . . . ! Condl))I(c) =
supc!∈Δn, c![i1,...,ik]=c min(RI (c!), Cond1I(c!), . . . , CondlI(c!)) Some explanation is in place. Consider (∃[i1, . . . , ik]R). Informally, from a classical semantics point of view, (∃[i1, . . . , ik]R) is the projection of the relation R over the columns i1, . . . , ik and, thus, corresponds to the set of tuples
{c | ∃c! ∈ R s.t. c![i1, . . . , ik] = c} .
Note that for a fixed tuple c there may be several tuples c! ∈ R such that c![i1, . . . , ik] = c. Now, if we switch to fuzzy logic, for a fixed tuple c and interpretation I, each of the previous mentioned c! is instance of R to a degree RI (c!). It is usual practice in mathematical fuzzy logic to consider the supremum among these degrees (the existential is interpreted as supremum), which motivates the expression supc!∈Δn, c![i1,...,ik]=c RI (c!). The argument is similar for the ∃[i1, . . . , ik]R.(Cond1 ( . . . ( Condl) construct except that we consider also the additional conditions as conjuncts.
Now given an interpretation I, the notion of I is a model of (satisfies) an axiom τ , denoted I |= τ , is defined as follows:
I |= Rl1 ! . . . ! Rlm " Rr iff for all c ∈ Δn, min(Rl1I (c), . . . , RllI(c)) ≤ RrI (c) , 3 Given truth degrees x and y, the conjunction of x and y is x ⊗ y. ⊗ has to be symmetric, associative, monotone in its arguments and such that x ⊗ 1 = x. where we assume that the arity of Rr and all Rli is n. An interpretation I is a model of (satisfies) an ontology O iff it satisfies each element in it.
Concerning queries, an interpretation I is a model of (satisfies) a query q the form q(x) ← ∃yφ(x, y), denoted I |= q, iff for all c ∈ Δn: qI (c) ≥
sup c!∈Δ×···×Δ φI (c, c!) , where φI (c, c!) is obtained from φ(c, c!) by replacing every Ri by RI , and Go¨del i conjunction is used to combine all the truth degrees RI (c!!) in φI (c, c!). Furthermore, i we say that an interpretation I is a model of (satisfies) #q(c), s$, denoted I |= #q(c), s$, iff qI (c) ≥ s.
We say O entails q(c) to degree s, denoted O |= #q(c), s$, iff each model I of O is a model of #q(c), s$. The greatest lower bound of q(c) relative to O is
glb(O, q(c)) = sup{s | O |= -q(c), s.} .
As now each answer to a query has a degree of truth, the basic inference problem that is of interest in DL-MEDIA is the top-k retrieval problem, formulated as follows. Given O and a query with head q(x), retrieve k tuples #c, s$ that instantiate the query predicate q with maximal degree, and rank them in decreasing order relative to the degree s, denoted ansk(O, q) = Topk{#c, s$ | s = glb(O, q(c))} .
From a query answering point of view, the DL-MEDIA system extends the
DL-Lite/DLRLite reasoning method [
DL-MEDIA at work A prototype of the DL-MEDIA system has been implemented. The main interface is shown in Fig. 3.
In the upper pane, the currently loaded ontology component O is shown. Below it and to the right, the current query is shown (“find images about sunrises on the sea”, we also do not report here the concrete syntax of the DL-MEDIA DL).
So far, in DL-MEDIA, given a query, it will be transformed, using the ontology, into several queries (according to the query reformulation step described above) and then the conjunctive queries are transformed into appropriate queries (this component is called wrapper) in order to be submitted to the underlying database and multimedia engine. To support the query rewriting phase, DL-MEDIA allows also to write schema mapping rules, which map e.g. a relation name R into the concrete name of a XML tag (see Fig. 4) and excerpt of the metadata format is shown in Fig. 5.
For instance, the execution of the query shown in Fig. 3 produces the ranked list of images shown in Fig. 6.
Related to each image, we may also access to its metadata, which is in our case an excerpt of MPEG-7 (the data can be edited by the user as well). We may also select an image of the result pane and further refine the query to retrieve images similar to the selected one. 5
We conducted an experiment with the DL-MEDIA system. We considered an image set of around 560.000 images together with their MPEG-7 metadata. The data have been provided by Flickr 4 as a courtesy and for experimental purposes only. In MILOS we have indexed the images’ low-level features as well as their associated XML metadata. We built an ontology with 356 concept definitions, 12 relations. Totally, we have 746 DL-MEDIA axioms. We built 10 queries to be submitted to the system and measured for each of them 1. the precision at 10, i.e. the percentage of relevant images within the top-10 results. 2. the number of queries generated after the reformulation process (qr!ef ); 3. the number of reformulated queries after redundancy elimination (qref ); 4. the time of the reformulation process (tref ); 5. the number of queries effectively submitted to MILOS (qMILOS ); 6. the query answering time of MILOS for each submitted query (tMILOS ); 7. the time of merging process using the DTA (tDT A);
8. the time needed to visualize the images in the user interface (tImg ); 9. the total time from the submission of the initial query to the visualization of the final result (ttot).
The results are shown in Table 1 below (time is measured in seconds). Let’s comment some points. The number of queries generated after query reformulation varies significantly and depends both on the structure of the ontology and the concepts involved in the original query. For instance, a query about African animals formulated as q8(x) ← Animal(x) ∧ Af rica(x) will be reformulated into several queries involving the sub-concepts of both Animal and Africa, which in our case is quite large. Also interesting is that, e.g. for query 8, we may remove more than 100 queries from r(q8, O) by a simple query subsumption test check. Besides the possibility to have large query reformulation sets, the query reformulation time is quite low (less than 0.5 seconds). Also negligible is the time spent by the DTA merging algorithm. The MILOS response time is quite reasonable once we submit one query only (the answer is provided within some seconds). Clearly, as we submit the queries sequentially to the MILOS system, the total time sums up. Of course, an improvement may be expected once we submit the queries to MILOS in parallel. This part is under development as a joint activity with the MILOS development group.
Also note that the effective number of queries qMILOS may not coincide with qref =, as we do not submit queries to MILOS which involve abstract concepts only, as they do not have a translation into a MILOS query (for instance, the query q8, which despite belonging to the set of reformulated queries r(q8, O) is not submitted, while the reformulated query q81 (x) ← T ag(x, animal) ∧ T ag(x, af rica) is). Also, if we have already retrieved 10 images with score 1.0, we stop the MILOS query submission phase.
From a qualitative point of view of the retrieved images, the precision is satisfactory, though more extensive experiments are needed to assess the effectiveness of the DLMEDIA system. Worth noting is query 9
q9(x) ← Europe(x) ∧ Af rica(x) in which we considered as relevant one image only, which dealt with a postcard sent from Johannesburg (South Africa) to Norwich (UK). 6
In this work, we have outlined the DL-MEDIA system, i.e. an ontology mediated multimedia retrieval system. Main features (so far) of DL-MEDIA are that: (i) it uses an extension of DLR-Lite like language as query and ontology representation language; (ii) it supports feature-based queries, semantic-based queries and their combination; and (iii) is promisingly scalable.
There are several points, which we are further investigating: – so far, we consider all reformulated queries as equally relevant in response to information need. However, it seems reasonable to assume that the more specific the reformulated query becomes the less relevant its answers may be; – multithreading of reformulated queries; – from a language point of view, we would like to extend it by using rules on top of axioms and adding more concrete predicates.
Currently we are investigating how to scale both to a DL-component with 103 concepts and to a MIR component indexing 106 images.