A semantic framework for multimedia document adaptation

1 Introduction

The multiplication of execution contexts for multimedia doc­ uments requires the adaptation of document specifications to the particularities of the contexts. Adaptation is not very pre­ cisely defined and it is currently specified through program­ ming. We propose a semantic approach to multimedia docu­ ments (§2). It does not deal with the semantics of document content, but with that of their composition. The approach allows the definition of adaptation in very general semantic terms independent from the multimedia objects (§3). We then investigate the temporal dimension of multimedia documents specified qualitatively (§4) and propose metrics for finding the "best" adaptations. We discuss then the limitations of current multimedia specifications that prohibit a better adap­ tation (§5).

We first introduce the characteristics of multimedia docu­ ments(§ 1.1) and adaptation(§ 1.2).

1.1 Multimedia documents

A multimedia document is a digital document composed of objects of different nature: text, sound, image, animation, etc. These objects and their compositions are called multime­ dia objects. Multimedia documents are traditionally analysed following four dimensions [Layalda, 1997]:

• logical (organisation into chapters, shots, etc.),
• spatial (graphic layout),
• hypermedia (relations between documents and docu­ ment fragments),
• temporal (temporal ordering of the multimedia objects).

These dimensions are not totally independent and require a combined processing.

This paper primarily focuses on the adaptation of multime­ dia documents along their temporal dimension. In a temporal multimedia document, the presentation of the multimedia ob­ jects is scheduled over time. Such a document is presented in Figure 1. Time is displayed on the horizontal axis. The example presented is the introduction of a slideshow made of different panels composed of graphic objects that can be presented simultaneously. The first panel displays the title, authors and outline of the speech; each of these objects are represented by a segment whose begin and end points corre­ spond to the beginning and ending of their presentation on screen.

The Title object starts at second 0 and ends at second 5, while the Author object starts at second 2 and ends at sec­ ond 5. Between seconds 5 and 8 the Outline object is pre­ sented. etc. Such a description is exact and quantitative since it defines exactly the beginning and ending instants of each multimedia object. This information is sufficient for playing the document: to one exact quantitative representation corre­ sponds only one possible execution of the document (within a fixed temporal reference).

Specifying a multimedia document in an exact manner is like writing a paper directly in PostScript instead of using lbT}3X. Multimedia documents are not often specified in an exact way because it is more convenient for the author to leave the interpretation of the specification to the machine as soon as the will of the author is clearly expressed. The author can concentrate on the creative part of is or her work instead of characterising the exact position of each object.

Non-exact specifications can be achieved by expressing the qualitative relations between multimedia objects. There are several languages for specifying multimedia documents with different ways of expressing the temporal dimension: SMIL [W3C, 1998] expresses the positioning of multimedia ob­ jects with parallel and sequence operators on intervals; Magic [Dalal et at., 1996] and Madeus [Laya"ida, 1997] use a restric­ tion of the Allen algebra of temporal intervals.

The document of Figure 1 can be expressed qualitatively. For instance, the Authors object starts after and finishes with the Title object; the Authors object meets the Outline object. From such a specification, the multimedia presentation sys­ tem (or the Player) computes a plan (called "scenario") that can be executed. This function is called temporal formatting.

1.2 Adapting multimedia documents

A server delivers a multimedia document to be played by a client. Clients and servers can be different machines with different capabilities. Different contexts of multimedia pre­ sentations introduce different constraints on the presentation itself. For instance, bandwidth limitations between the client and the server can result in preventing the client from playing two bandwidth-demanding videos at the same time. Display limitations can produce similar constraints. Other constraints may also be introduced by user preferences, content protec­ tion or terminal capabilities. The constraints imposed by a client are called a profile.

Profiles can be expressed in terms of a restriction of the language used for specifying target documents or in terms of additional constraints imposed on the objects. For instance, if the device features only a screen with limited capabilities, it can be impossible to display two images simultaneously on the same screen.

For satisfying these constraints, multimedia documents must be adapted before being played. From the profile and the source document, the adaptation must provide a document satisfying the constraints expressed in the profile. Qualitative specifications are central to this process as they enable more efficient adaptation by providing more flexibility. This adap­ tation is usually performed by a program transforming the document [Villard, 200 I; Lemlouma and Laya"ida, 2001].

For the purpose of characterising the adaptation process, we introduce a semantics of multimedia documents and illus­ trate it on the temporal dimension (§2). The semantic defi­ nition of adaptation (§3) leads to distinguish refining adapta­ tion (in which the models of the adapted document are mod­ els of the source documents) from transgressive adaptation (in which the models are as close as possible to those of the source document). Section 4 illustrates the notion of close­ ness for the temporal dimension. The limits of our approach are then presented (§5).

2 A semantic approach to multimedia documents

We describe the specification of multimedia documents (§2. 1) before defining their semantics (§2.2) used finally for defining adaptation (§3).

2.1 Specifications

We assume that the qualitative specifications of multimedia documents use the temporal interval algebra [Allen, 1983] for representing the temporal relationships between multime­ dia objects. So, the temporal extent of the multimedia ob­ jects will be a temporal interval I whose beginning and end­ ing time are identified by I - and I+. The specification will relate each pair of multimedia objects by a subset of the set A13 of temporal relations (presented in Table 1).

Definition 1 (Specification). A specification s = ( 0 , C) of a document is made of a set of objects 0 and a set of constraints C between these objects (i.e., a relation between several ob­ jects). The set of all specifications will be noted S.

Example 1 (Temporal specifications).

In the remainder, the constraints will be considered as bi­ nary. The temporal specification can then be represented as a relation graph [van Beek, 1992]. This representation will be used for describing models.

Definition 2 (Relation graph). A specifications = (0, C) can be represented as a complete direct labelled graph 9s = (N, E, .\) such that the elements of 0 are in bijection with those of N and ,\ : E --+ 2A 13 is a total function from the arcs to temporal relations such that for each x r y E C, .\((x,y))~r.

Definition 3 (Resolved relation graph). A relation graph is resolved iff all the labels are singletons.

2.2 Semantics of a specification

The specification of a multimedia document is interpreted as the set of its potential executions. A model of a multimedia document (in the sense of model theory) is an execution of the document satisfying the specification.

Definition 4 (Interpretation). An interpretation of a specifi­ cation is a pair (I, D) such that D is the domain of interpre­ tation and I is a function from 0 to D and from C to D x D (i.e., such that a constraint applied to two elements of the do­ main of interpretation is either true of false).

Example 2 (Temporal interpretation). In order to interpret the temporal aspects of multimedia documents, we consider the interpretations such that the objects in 0 are interpreted as intervals of the positive real numbers and the constraints are interpreted as the corresponding relations in the temporal interval algebra. For instance, A can be interpreted as the interval [10 20[, B as [12 30[ and C as [10 30[, o is true if its first argument begins before the second one and ends during it, { b m o} is true if its first argument begins before the second one and ends before the end of the second one.

A model is defined in the usual way:

Definition 5 (Model). A model of a specification (0, C) is an interpretation (I, D) such that for each o r o' E C, (I ( o) ,I( o')) E I ( r) is true. The set of models of a specifica­ tion 8 is noted Ms.

Example 3 (Temporal model). The interpretation presented in Example 2 is a model of 8 1 but not of 82 .

In the following, we will always consider that there exists at least one model of the source specification (which is thus consistent).

These models correspond faithfully to the execution of the multimedia documents. However, the formatter will consider executions as equal if they only differ by a translation factor and the adaptation will consider two executions as equal if they only differ in duration, preserving topology and order­ ing. We introduce qualitative representations of models as abstractions of models.

Definition 6 (Qualitative representation of a model). The qualitative representation of a model (I, D) of a specifica­ tion ( 0, C) is a complete direct labelled graph (N, E, >.) such that the elements of 0 are in bijection with those of N and >. : E -+ 2A' 3 is a total function from the arcs to temporal relations such that for each I(x) r I(y ), >.( (x, y)) = r.

Since the Allen relations are exclusive and exhaustive, qualitative representations of a model correspond to resolved relation graphs.

Example4. q! 2 =({A, B , C}, {A{o}B, C{8}A, C{m}B}) is a qualitative representation of one of the three models of 82.

3 Semantics of adaptation

The adaptation of a multimedia document is constrained by the profile. The profile defines constraints that must be satis­ fied by the document to be played.

3.1 Adaptation constraints

Definition 7 (Adaptation constraint). An adaptation con­ straint a determines a set of possible executions Ma. The set of adaptation constraints will be noted A.

The example above introduced a constraint prohibiting more than one image to be displayed at once on a screen. This can be expressed by a MSO constraint.

Example 5 (Maximum Simultaneous Objects). The con­ straint MSOr(n) (Maximum Simultaneous Objects) is a global constraint prohibiting the display of more than n ob­ jects belonging to the set T simultaneously. It thus determines the set of interpretations (I, D) of a specification 8 = (0, C), suchthat\li E IR,I{o E T;I(o)- ~ i ~ I(o)+}l ~ n. In the remainder, MSO will be used instead of MSOo.

A profile pis a set of such constraints. It determines a class of qualitative models (those who satisfy the constraints). The role of adaptation is thus to determine if there exist models of the initial specification belonging to that class. Otherwise, it is convenient to alter the specification by finding, among the set of models satisfying the profile, those that are "semanti­ cally closer" to the source specification.

Definition 8 (Classification of adaptation). Three types of adaptation can be identified in function of the value of Ms n Mv (inducing three different constraints on the model selection function o:):

Compliant specification M s n M P = M s: the source doc­ ument satisfies the adaptation constraints (all models of Ms satisfy the adaptation constraints, so o: is identity).

Refining adaptation 0 C Ms n Mv C M.: there exists some models of 8 satisfying the adaptation constraints (o:(Ms) = M s n Mv)·

Transgressive adaptation Ms n Mp = 0: no model of 8 satisfies the adaptation constraints (o: will then select some models of Mp closest to those of the specification 8).

If the constraints of the profile can be expressed as a for­ mula of the specification language, the two first cases are characterised by the consistency of 8 Up. The MSOr(l) con­ straint can be expressed by the relation graph in which all the labels of arcs connecting two nodes in T are subsets of {b m mi bi}. Filtering it can be efficiently performed.

3.2 Problems

One of the benefits of the approach is to be able to clearly pro­ vide criteria that an adaptation function T must meet. These criteria are expressed here as a set of problems.

The first one is that the adapted specification must satisfy the adaptation constraints.

Problem (soundness). Mr(s) ~ Mv: do the models of the adapted specification satisfy the adaptation constraints?

Moreover, if there exists a possible execution of the doc­ ument satisfying the adaptation constraints, this execution must be preserved in the adapted specification.

Problem (refining-completeness). if Ms n Mp =I 0 then Mr(s) 2 Ms n Mp In such a case, the adaptation should not authorise models that were not models of the source specification.

Unfortunately, no guarantee is given that the languages used for expressing the specifications and the adaptation con­ straints allow the expression of a specification satisfying these requirements.

Problem (representability). \Is E S;Vp ~A, Does r(s) E Sexist such that Mr(s) = Ms n Mp.

Moreover, one constraint that should be achieved by a se­ mantic approach is that the result of adaptation must not de­ pend on the syntactic form of the specification.

Taking the semantic approach to multimedia document adaptation allows the characterisation of adaptation in a very general way depending only on model theoretic considera­ tions. In particular, these definitions are totally independent from the language used for expressing documents and profiles as well as the multimedia object and constraint types.

This characterisation clearly emphasises the constraints that a refining adaptation must meet and that can be over­ looked when programming the transformation.

Transgressive adaptation is more difficult to characterise and this is considered in the next section.

4 Transgressive adaptation in the temporal dimension

The goal of transgressive adaptation is to find a specification r(s) as close as possible to the source specifications. Seman­ tically, this amounts to find the specifications whose models are the closest possible to those of the source specification. Figure 3 shows the set of models satisfying MS0(1). A dis­ tance 6. must be defined between two sets of models in order to find which models to select.

Problem (compactness). if Ms n Mp = 0 then

Example 6. For the specification s1 = ( {A, B}, {A { o} B}) and the constraint of displaying only one graphic object at once (MS0(1)), adaptation must be transgressive. The 13 possible models correspond to the 13 possible Allen rela­ tions. Among these models, only those built from before ( {b} ), meets ( {m} ), met by ( { mi}) and after ( {bi}) satisfy the adaptation property MSO(l). These possible combinations are presented in Figure 3.

Applying a semantic approach to transgressive adaptation can be compared to the use of the semantic approach for knowledge base revision [Dalal, 1988]. This will be the first step taken here. But we will show that the simple distance used for comparing models is not sufficient for adapting mul­ timedia documents. Measures depending on the kind of mul­ timedia objects are required.

The usual way to compute the distance between sets of models is function of a distance d between two models and a method of aggregation F .

Definition 9 (Distance between sets of models).

Various methods exist for aggregating distances (e.g., sin­ gle linkage, full linkage, Hausdorf distance). The single link­ age (i.e., the distance between two sets of models is the small­ est distance between a pair of elements of both sets) seems better for semantics because the designer of the specification always has a privileged model in mind.

The second element is the distance d that is considered hereafter 1 ·

4.1 Distance on the qualitative models

The first distance that comes to mind consists of counting the relations between two objects that differ between models. It is comparable to the Hamming distance (i.e., the cardinal of the symmetric difference between two sets) counting the propositional atoms that do not have the same truth-value in propositional logic [Dalal, 1988]. Because qualitative models correspond to resolved relation graphs, the distance is easily computed by counting the labels which differ between each pair of objects. The distance is defined on graphs (and more precisely on their labelling functions) .

Definition 10 (Distance between resolved relation graphs).

Example 7. Concerning s1 , the four models are all at the same distance from the model of the source specification be­ cause they all differ by two relations (the one between A and Band its converse).

In order to find more precise results that discriminate be­ tween the four models of the example, the relations between intervals can be transcribed into relations between their begin and end points and the same sort of distance can be used.

4.2 Point-based distance on the qualitative models

The relations of the interval algebra can be represented by relations of the instant algebra between the endpoints of the intervals. For instance, the meet relation (m) will be repre­ sented by 1(m) = (<, <, =, <). The distance between two intervals based on their endpoints will be the number of posi­ tions in the 4-uple that differ.

1 The metrics presented satisfy all the properties of distances [Monjardet, 1981]. This is not discussed due to space constraints.

Definition 11 (Distance between interval relations based on endpoints).

The distance between models is the sum of the distance between each interval relation.

Definition 12 (Distance between models based on end­ points).

Example 8. Table 2 exhibits the relations on endpoints pre­ served by each of the four models of s1 satisfying the adap­ tation constraint with regard to the model of the source spec­ ification. This distance discriminates better the models for

adapting situation s1 . Two models (before and meets) are clearly preferred over the others (met by and after). But in­ tuitively, it seems that meet is a better solution because it reduces the distance between the two objects which where previously overlapping. We show that it is possible to find a distance conforming to this intuition.

4.3 Conceptual distance in the interval algebra

The problem with the former distance is that it does not take into account the topological structure of temporal relations (i.e., it only counts differing relations on endpoints or inter­ vals without consideration for a proximity between the dis­ agreeing relations) . To take this proximity into account, we take advantage of the notion of conceptual neighbourhood [Freksa, 1996] and the shortest path distance in its graph (see Figure 4).

Conceptual neighbourhood attempts at capturing the prox­ imity between qualitative relations by observing the effects of transforming the related objects.

Definition 13 (Conceptual neighbourhood). The concep­ tual neighbourhood relation is a binary relation Nf between elements of a set of relations r such that Nf (r, r') iff the continuous transformation X of a situation involving two in­ dividuals x andy can transform r(x, y) into r'(x, y) without transiting by a third relation.

The conceptual neighbourhood relation for the transforma­ tion that moves one endpoint without affecting the others is given in Figure 4.

A distance between relations can be directly computed from the graph.

Definition 14 (Conceptual distance). The conceptual dis­ tance 6' between two relations is the length of the shortest path between rand r' in the graph of Nf.

Then the distance between models can be expressed by summing up the conceptual distances between the relation­ ships used in both models.

Definition 15 (Conceptual distance between models).

Example 9. Concerning s1 , the models satisfying the adapta­ tion constraint MSO(l) are at different conceptual distances from the source specification: before is at a distance of 2, meet is at a distance of 1, met by is at a distance of 5 and after is at a distance of 6. So the closest solution to serializing the overlap relation is meet. This corresponds to the intuition.

5 Limitations

Extending the presented work to the spatial dimension does not look very difficult. The logical dimension is even eas­ ier because it provides a very structured organisation of the document that, we conjecture, can yield direct adaptation. So the proposed approach is able to cope with adaptation in each dimension of the document.

Real difficulties arise when hypermedia and temporal and spatial dimensions are considered together. As a matter of fact, the presence of hypermedia links which, when triggered by the users, jump to other parts of the presentation, introduce non-determinism in the interpretation of documents [Dalal et al. , 1996; Fargier et al., 1998]. This non determinism does not easily fit with the conceptual neighbourhood approach which favours continuity.

A further analysis shows that the temporal information contained in specifications is not sufficient for a good adapta­ tion. For instance, considering two panels composed of two pictures each (AB and then CD, like in Figure 1) and the MSO(l) constraint, the closest models linearizing the presen­ tation are ABCD and ABDC with a conceptual distance of 18. However, if both panels aim at comparing two objects 01 (right) and 02 (left) on the basis of two features (one by panel), preserving the parallelism (which suggests the com­ parison) imposes the choice of ABCD. The absence of in­ formation about the comparison is missing from the speci­ fication resulting in lower quality adaptation. Some authors [Rutledge et al., 2000] have proposed to use rhetorical struc­ tures [Mann and Thompson, 1987] in order to choose a better presentation at the formatting stage. This could be useful for the adaptation stage as well.

6 Related work

The most related work is that of [Dalal et al., 1996], which describes the generation of multimedia presentations through the negotiation of the temporal constraints. Like the work presented here, the temporal specifications are expressed by Allen relations. The approach differs because we consider an existing specification to be adapted where the authors gen­ erate schedules and preferences among them on the fly. So there is no alteration of already existing constraints based on the semantic characterisation, but a satisfiability check and negotiation of constraints when inconsistency is detected.

The transgressive adaptation can be compared with there­ vision in knowledge bases [Gardenfors, 1992]: the addition of a new (adaptation) constraint leads to inconsistency. It is necessary to find a new specification satisfying this con­ straint and not too different from the source specification. One difference is that adaptation constraints are not always formulas of the specification language. Having several con­ straints raises problems similar to incremental revision: since the constraints are not provided in a sequence but in a set, it is important that the adaptation does not depend on some order of presentation constraints. Although transgressive adapta­ tion is neither revision (it does not correspond to some change in our knowledge) nor update (it cannot be compared to the acquisition of a new information), more generic techniques developed for revision could be used in the context of multi­ media adaptation.

7 Conclusion

This paper applied a semantic approach to multimedia docu­ ments and their adaptation. This allows for a precise defini­ tion of what is expected from the adaptation of these doc­ uments and the comparison of the results given by hand­ made transformation with what was expected. It proposes a model-based distinction between compliant documents, refin­ ing adaptation and transgressive adaptation. This framework has been applied to the temporal dimension of the documents providing measures for sharply discriminating the possible transgressive adaptations.

As discussed above, there remains more work to be carried out for covering all the aspects of multimedia documents and for deepening the specification of documents and adaptation constraint so that the adaptation produces quality results.