Sébastien Laborie
email: sebastien.laborie@irit.fr

Jérôme Euzenat
email: jerome.euzenat@inrialpes.fr

Nabil Layaïda
email: nabil.layaida@inrialpes.fr

Semantic Multimedia Document Adaptation with Functional Annotations

The diversity of presentation contexts for multimedia documents requires the adaptation of document specifications. In an earlier work, we have proposed a semantic adaptation framework for multimedia documents. This framework captures the semantics of the document composition and transforms the relations between multimedia objects according to adaptation constraints. In this paper, we show that relying on document composition alone for adaptation restricts the set of relevant candidate solutions and may even divert the adaptation from the authors intent. Hence, we propose to introduce functional annotations to guide the adaptation process. Theses annotations allow to refine the role of multimedia objects in the document. We show that SMIL documents could embed functional annotations encoded in RDF. These multimedia documents are then adapted thanks to an interactive adaptation tool.

Introduction

Ideally, a multimedia document is authored once but can be played on different devices with different capabilities: phones, PDAs, desktop computers, set-top boxes, etc. These devices introduce different constraints on the presentation itself. For instance, CPU or display limitations (e.g., mobile phones) may prevent multimedia objects from being displayed correctly. Other constraints may also be introduced by user preferences, content protection issues or terminal capabilities [START_REF] Klyne | Composite Capability/Preference Profiles (CC/PP): Structure and vocabularies 1.0. Recommendation, W3C[END_REF]. The set of constraints related to a client is called a profile.

To satisfy profiles, multimedia documents must be adapted, i.e., transformed into documents compatible with target contexts before being played. We need to distinguish two types of adaptation: local adaptation (adaptation of multimedia objects individually) and global adaptation (adaptation of the document structure). This paper focuses on the latter.

In [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF], a framework for adapting multimedia documents based on the qualitative semantics of the documents and constraints was proposed. This approach transforms the relations between multimedia objects and ensures two main properties: [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] all constraints specified in a target client profile are satisfied and (2) the computed adapted document is as close as possible to the initial document. We have shown, e.g., in [START_REF] Laborie | Spatio-temporal proximities for multimedia document adaptation[END_REF][START_REF] Laborie | An incremental framework for adapting the hypermedia structure of multimedia documents[END_REF], that this framework can adapt the spatiotemporal and the hypermedia dimensions of standard multimedia documents such as SMIL documents [START_REF] Bulterman | Synchronized Multimedia Integration Language (SMIL 2.1)[END_REF].

However, this adaptation framework only deals with the initial document composition, i.e., explicit relations between multimedia objects specified by authors. In this paper, we show that relying only on this information for adapting documents is unsatisfactory because it leads to a limited form of adaptation. Hence, we propose to guide adaptation with functional annotations, i.e., annotations related to multimedia objects which express a function in the document, such as a title, a legend. Consequently, additional implicit relations between multimedia objects can be identified and these could enrich the adaptation process for producing new adapted solutions close to the initial document composition and the author intent.

Furthermore, we show that SMIL documents could embed functional annotations encoded in RDF [START_REF] Manola | RDF primer. Recommendation[END_REF]. From such multimedia documents, our interactive adaptation prototype provides relevant adaptations.

In Section 2, we present a general adaptation scheme. In Section 3, we define functional annotations and show how to integrate them into the document specification. In Section 4, we adapt a multimedia document example and compare adaptation results with and without functional annotations. We show that with these annotations, adaptation is more flexible. Finally, in Section 5, we adapt SMIL documents with functional annotations encoded in RDF.

In order to execute a multimedia document on different devices with different profiles, a fair amount of research has been conducted on multimedia document adaptation. We propose to group all techniques into three categories 1 :

• Specification of alternatives: During a multimedia document edition, an author may specify different versions based on some target profiles, e.g., thanks to the switch tag of SMIL [START_REF] Bulterman | Synchronized Multimedia Integration Language (SMIL 2.1)[END_REF]. However, when editing a document, it is cumbersome to specify all possible versions for every existing profiles.

• Using transformation rules: Inside an adaptation system, a set of transformations is defined a priori (e.g., speech to text, parallel to sequential) and stored into a repository. From a multimedia document and a target device profile, some transformations are selected by the system and applied on the document. [START_REF] Lemlouma | The negotiation of multimedia content services in heterogeneous environments[END_REF] and [START_REF] Asadi | Knowledge-based and semantic adaptation of multimedia content[END_REF] are two examples of such a system.

• Multimedia document generation: Other approaches for multimedia document adaptation are based on specialized specifications for generating documents, such as [START_REF] Geurts | Application-specific constraints for multimedia presentation generation[END_REF] and [START_REF] Boll | MM4U -a framework for creating personalized multimedia content[END_REF]. However, this requires the content to be initially described with these specifications instead of adapting existing documents.

Apart from the existing adaptation mechanisms, there are several languages or formats for specifying multimedia documents that have to be adapted, such as SMIL [START_REF] Bulterman | Synchronized Multimedia Integration Language (SMIL 2.1)[END_REF], Madeus [START_REF] Jourdan | Madeus, an authoring environment for interactive multimedia documents[END_REF] and XHTML [START_REF] Pemberton | XHTML TM 1.0 the extensible hypertext markup language[END_REF]. Making the adaptation format-dependent requires an adaptation strategy for every single format. Instead, we propose an abstraction layer which allows to hide the format specific syntax and details, and capture the essence of a given document with respect to its main dimensions. We call this document abstraction a multimedia document specification and presents in Figure 1 a generic adaptation scheme for such representation.

Definition 1 (Multimedia document specification) A multimedia document specification s = O, C is made of a set of multimedia objects O and a set of relations (or constraints) C between these objects.

In the remainder, the set O will contain at least two multimedia objects and the relations of C will be considered as binary. As illustrated in Figure 1, from an initial multimedia document we identify all its involved objects (i.e., texts, images, audios, videos, hypermedia links) and all relations between them. These relations may come from the document composition ( a ) and functional annotations ( b ). The latter will be defined in Section 3. 1 Other adaptation categories have been proposed, e.g., in [START_REF] Lei | Context-based media adaptation in pervasive computing[END_REF]. Thereafter, the multimedia document specification is adapted according to target profiles. For that purpose, forbidden relations deduced from target profiles are transformed into valid ones. In the remainder, we will use the adaptation framework presented in [START_REF] Euzenat | A semantic framework for multimedia document adaptation[END_REF] because it considers multimedia document specification and provides adapted documents which are as close as possible from the initial document.

Finally, an adapted document satisfying the adapted specification is instantiated. This one could be encoded as the initial multimedia document description language or another one.

The advantages of such adaptation scheme presented in Figure 1 are twofold. First, it permits to reuse the same adaptation strategy for different formats. Second, the abstract representation provides more flexibility for adaptation since the relations between multimedia objects can be described qualitatively.

In the following, we show that functional annotations enrich the adaptation process for producing new adapted solutions close to the initial document composition and the author intent.

Enhanced Multimedia Document Specifications with Functional Annotations

A multimedia document specification is composed of relations holding between objects (cf., Definition 1). Functional annotations may complete these relations, they are annotations related to objects which express a function in the document. We identified two categories of functional annotations: one concerns media individually and the other one concerns groups of objects.

The former expresses a specific role of a media involved in a multimedia presentation. For instance, one media might be a title, a menu, a logo or an advertisement. Some multimedia description standards, e.g., the multimedia description schemes of MPEG-7 [START_REF] Mpeg Mds Group | Text of ISO/IEC 15938-5 FDIS Information Technology -Multimedia Content Description Interface -Part 5 Multimedia Description Schemes[END_REF], allow to specify such roles.

The latter expresses semantic relationships between a group of objects and describes how several objects relate in a narrative or story. For instance, these semantic relationships may describe relations that draw upon typical pragmatic relations such as an object being the agent, patient, cause, goal of other objects. The rhetorical structure theory [START_REF] Mann | Rhetorical Structure Theory: Towards a functional theory of text organisation[END_REF] offers some possible semantic relationships between objects. These have been used, e.g., in [START_REF] Rutledge | Generating presentation constraints from rhetorical structure[END_REF], for generating multimedia presentations.

During a multimedia document edition, objects are usually placed according to these functional annotations. For example, a title may stay on top of a slide, a legend may stay around the object it describes. From particular functional annotations, [START_REF] Little | Dynamic generation of intelligent multimedia presentations through semantic inferencing[END_REF] and [START_REF] Gaillard | Intentions based authoring process from audiovisual resources[END_REF] identify mappings to qualitative spatio-temporal relations. Consequently, from a multimedia document specification the set of relations could contain both explicit spatio-temporal relations made by an author and implicit spatio-temporal relations deduced from functional annotations. In the following, we show how to embed functional annotation information into a multimedia document specification. Suppose the multimedia presentation example illustrated in Figure 2. This one is composed of four objects: two texts T 1 and T 2 , one video V and an image I.

T 1 (title) V T 2 (I&V legend) I T 1 V T 2 I t(s)
x y 0 10 20

Figure 2. A multimedia presentation example.

The multimedia document specification corresponding to this example may be represented with a relation graph where each node refers to an object of the presentation and each edge is labeled by some spatio-temporal relations. Figure 3 presents three relation graphs related to the multimedia document example of Figure 2.

In this example, the Allen algebra [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] (cf., Table 1) is used to describe spatio-temporal relations. More precisely, each spatio-temporal relation forms a triple (r x , r y , r t ) such that r x , r y and r t are Allen's relations which correspond respectively to projections over the x, y and t axis. From functional annotations, additional implicit spatiotemporal relations are identified in Figure 3(b). For example, T 1 is a title and should stay on top of the other objects and played simultaneously (e.g., T 1 {(si, b, f i)}I), T 2 is the legend of I and V , and should stay around them (e.g., T 2 {(mi, e, e)}I). It may happen that no functional annotations are provided, e.g., between I and V .

T 1 {(di,b,si)} / / {(di,b,f i)} ) ) S S
{(di,b,f i)} V {(b,e,o)} u u k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k {(s,b,o)} T 2 {(f,b,e)}
/ / I (a) Explicit relations from the document composition of Figure 2. Table 1. The thirteen Allen's relation.

T 1 {(si,b,si)} / / {(si,b,f i)} ) ) S S
{(f i,b,f i)} V {(m,e,o)} u u k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k {(e,
To maintain complete information in Figure 3(b), we compute the transitive closure of spatio-temporal relations.

For example, V {(m, e, o)}T 2 and T 2 {(mi, e, e)}I implies V {(e, e, o)}I. For visibility reasons, we only illustrate in Figure 3(b) one spatio-temporal relation in each set which differs from those of Figure 3(a).

Figure 3(c) corresponds to the global multimedia document specification of Figure 2. It combines the explicit and implicit information provided respectively by Figure 3(a) and Figure 3(b). In the next section, the relation graph illustrated in Figure 3(c) will be adapted in order to show the benefits of using functional annotations.

Adaptation of Multimedia Document Specifications

We want to execute the multimedia presentation example illustrated in Figure 2 on a mobile phone. However, its profile indicates that it is impossible to play more than three multimedia objects concurrently. The multimedia presentation presented in Figure 2 does not comply with this target profile because from t = 10s to t = 20s four objects are executed simultaneously. We thus have to adapt the document, i.e., transform forbidden relations into valid ones and compute an adapted document as close as possible to the initial document and author intent.

In this context, adapting consists of finding a set of relation graphs satisfying the profile at a minimal distance from the initial document specification. We consider that the proximity between two relation graphs depends on the proximity between relations borne by the same edge in both graphs. This proximity relies on the conceptual neighborhood between these relations and is measured by the shortest path distance in the corresponding conceptual neighborhood graph (Figure 4, [START_REF] Freksa | Temporal reasoning based on semi-intervals[END_REF]

). bi k mi k oi k d d si k d d f k d d di k e k d k d d fi k d d s k d d o k m k b k Figure 4. A conceptual neighborhood graph.
Thus, a distance d between relation graphs is obtained by summing up all the conceptual distances δ between relationships used in both graphs (cf., Definition 2).

Definition 2 Let G and G be two relation graphs with a set of nodes N and a labeling function λ (resp., λ ) which returns a set of relations between two nodes. d(G, G ) = Σ n1,n2∈N Min r∈λ( n1,n2 ),r ∈λ ( n1,n2 ) δ(r x , r x ) + δ(r y , r y ) + δ(r t , r t ). 4) and the one between T 2 and I changes from e to f i (δ(e, f i) = 1 in Figure 4).

T 1 {(di,b,si)} / / {(di,b,f i)} ) ) S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S {(di,b,f i)} V {(b,e,o)} u u k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k {(s,b,m)} T 2 {(f,b,f i)}
/ / I (a) Adaptation of the relation graph illustrated in Figure 3(a) without considering functional annotations. Figure 6 presents two adapted executions of the adapted relation graphs presented in Figure 5. Figure 6(a) presents an execution without considering functional annotations. This execution satisfies the mobile phone profile and is close to the initial document.

T 1 {(si,b,si)} / / {(si,b,f i)} ) ) S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S {(f i,b,f i)} V {(m,e,o)} u u k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k {(e,
However, the solution proposed is not suitable because at t = 20s (i.e., when V disappears and I appears) spatial information is not well presented. This is due to the explicit relations illustrated in Figure 3(a) which are too restrictive because it strictly interprets the document composition constraints and does not reflects functional annotations.

Figure 6(b) presents an execution when taking into account functional annotations, especially their implicit spatio-temporal relations. This execution satisfies the profile and is as close as possible to the initial document composition and the author intent. Furthermore, thanks to the flexibility added by these annotations the previous display problem did not appear in this adapted solution.

Implementation

This adaptation framework has been implemented in an interactive adaptation prototype. Its architecture is based on Figure 1 and uses the Adaptation algorithm (cf., Algorithm 1) to compute adapted solutions.

The user of our system may edit a SMIL document containing functional annotations encoded in RDF [START_REF] Manola | RDF primer. Recommendation[END_REF]. The SMIL Metainformation module [START_REF] Bulterman | Synchronized Multimedia Integration Language (SMIL 2.1)[END_REF] is used to specify such annotations in RDF. Figure 7 presents such a multimedia document, this one corresponds to the presentation illustrated in Figure 2.

From such document, explicit and implicit relations relative to the initial document specification, and possible relations satisfying the target device profile are encoded into two matrix I i,j and P i,j . Before the call to Adaptation(I i,j , P i,j ), we sort each label of the matrix P i,j according to the distance δ (cf., Section 4) from each label of the matrix I i,j . Thereafter, Algorithm 1 computes consistent relation graphs with help from the pathConsistency function defined in [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. The closest relation graphs from the initial document specification are selected in S. When Algorithm 1 stops, S contains adapted relation graph solutions.

Of course, our implementation could adapt multimedia documents on the client side or on the server side without any GUI. Our interactive prototype is useful for guiding an author during a multimedia document edition under constraints.

Algorithm 1: Adaptation

Input: A matrix I i,j corresponding to the initial multimedia document specification and a matrix P i,j corresponding to possible relations. Data: S is a set of adapted relation graphs; M in is a current minimum computed distance (initialized with a high value). pathConsistency(P ); if P does not contain an empty relation then Choose an unprocessed label P i,j and split P i,j into r l = r 1 , . Actually, one may specify some constraints (i.e., a profile) inside our prototype and if an author creates a forbidden relation between two objects the system provides other possible configurations close to the initial invalid one which satisfy the given profile. Hence, a user can be assisted, for instance, during the edition of a mobile multimedia document.

Conclusion

We have defined an adaptation framework which uses functional annotations in order to guide adaptation and make it more flexible. This adaptation approach is generic, i.e., it may adapt several document dimensions and may be applied to any multimedia description language. In order to validate the framework, we have implemented a prototype which adapts SMIL documents containing functional annotations encoded in RDF.

In the future, we plan to identify automatically, from the document composition, functional annotations (e.g., using emergent semantics as proposed in [START_REF] Scherp | Emergent semantics in personalized multimedia content[END_REF]) and select particular privileged adapted solutions, thus refining our adaptation approach.

Figure 1 .

 1 Figure 1. A generic multimedia document adaptation scheme.

Figure 3 (

 3 Figure3(a) presents the explicit spatio-temporal relations related to the document composition of Figure2. From functional annotations, additional implicit spatiotemporal relations are identified in Figure3(b). For example, T 1 is a title and should stay on top of the other objects and played simultaneously (e.g., T 1 {(si, b, f i)}I), T 2 is the legend of I and V , and should stay around them (e.g., T 2 {(mi, e, e)}I). It may happen that no functional annotations are provided, e.g., between I and V .

2 {

 2 e,o)} T (mi,e,e)} / / I (b) Implicit relations from the functional annotations of Figure 2.

T 1 { 2 {

 12 (di,b,si),(si,b,si)} / / {(di,b,f i),(si,b,f i)} ,b,f i),(f i,b,f i)} V {(b,e,o),(m,e,o)} u u k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k {(s,b,o),(e,e,o)} T (f,b,e),(mi,e,e)} / / I (c) The multimedia document specification of Figure 2 with explicit and implicit relations.

Figure 3 .

 3 Figure 3. Multimedia document specifications represented with relation graphs.

Figure 5

 5 Figure 5 presents two adapted relation graphs satisfying the mobile phone profile. The former (Figure 5(a)) considers only the explicit relations presented in Figure 3(a) which were extracted from Figure 2. The latter (Figure 5(b)) considers the explicit and implicit relations presented in Figure 3(c). Their distance from their corresponding initial specification are both d = 2 because the temporal relation r t between V and I changes from o to m (δ(o, m) = 1 in Figure4) and the one between T 2 and I changes from e to f i (δ(e, f i) = 1 in Figure4).

2 {

 2 e,m)} T (mi,e,f i)} / / I (b) Adaptation of the relation graph illustrated in Figure 3(c) which considers explicit and implicit relations.

Figure 5 .

 5 Figure 5. Adapted relation graphs which satisfy the mobile phone profile.

  An execution corresponding to Figure 5(a).

  An execution corresponding to Figure 5(b).

Figure 6 .

 6 Figure 6. Executions corresponding to the relation graphs presented in Figure 5.

Figure 7 .

 7 Figure 7. The SMIL code of Figure 2 with functional annotations encoded in RDF.