A Spatial Algebra for Multimedia Document Adaptation Sébastien Laborie, Jérôme Euzenat and Nabil Layaı̈da Abstract— The multiplication of execution contexts for multi- Logo media documents requires the adaptation of document specifi- cations. This paper instantiates our previous semantic approach Photo for multimedia document adaptation to the spatial dimension of Text multimedia documents. Our goal is to find a qualitative spatial representation that computes, in a reasonable time, a set of Map adaptation solutions close to the initial document satisfying a profile. The quality of an adaptation can be regarded in two respects: expressiveness of adaptation solutions and computation Fig. 1. Multimedia document example (left) and spatial dimension (right). speed. In this context, we propose a new spatial representation sufficiently expressive to adapt multimedia documents faster. Index Terms— Semantic adaptation, qualitative reasoning. III. A DAPTATION OF A NEW SPATIAL REPRESENTATION I. I NTRODUCTION We present a new spatial representation called ABLR, A multimedia document may be played on different devices adapted to the multimedia adaptation task and illustrate it with with different capabilities: phones, PDAs, etc. These introduce the example of Fig. 1. different constraints on the presentation itself. For instance, display limitations can prevent overlapping regions from being A. A new spatial representation: ABLR displayed at the same time for visibility reasons. To satisfy these constraints, multimedia documents must Preserving the directionality property, i.e., orientation in be adapted, i.e., transformed into documents compatible with space, with a sufficient number of relations is our major goal. the target contexts before being played. Several kinds of Thus, we propose to group together some Allen relations adaptation are possible, such as local adaptation (adaptation of expressing the same directionality property. media objects individually) and global adaptation (adaptation Suppose two multimedia objects X and Y . On a horizontal of the document structure). This paper focuses on the latter. point of view, six relations can be identified to specify directive In [1], we have proposed a framework for adapting a qualitative information between them (idem for the vertical multimedia document based on the qualitative semantics of axis). These relations are presented in Fig. 2. The first line is the documents and constraints. This work has been applied to made of the 13 Allen relations, grouped together for preserving descriptions based on the Allen algebra [2]. the directionality property. For example, the relations before As far as the spatial dimension is concerned (§II), many and meets between X and Y specifies that X is on the left of qualitative representations can be used to describe documents. Y (if we consider the horizontal axis). Thus, we can deduce Some of them are very precise, e.g., the directional representa- 62 spatial relations. tion [3], but with a high adaptation computational cost. Others, like the RCC representation [4], can be used to quickly adapt X Y multimedia documents but lack expressiveness. In order to find X X X X X Y Y Y Y an adapted document that is acceptable both in computing X Y time and precision, we introduce a new algebra of relations Y X particularly useful in this context (§III). X X Y X X Y Y Y X Y II. M ULTIMEDIA DOCUMENT SPECIFICATION Y X left Y X overlaps−left Y X contains Y X inside Y X overlaps−right Y X right Y Multimedia documents are defined by their temporal, spa- (L) (OL ) (CX ) (IX) (OR ) (R) tial, logical and interactive dimensions. This paper focuses on X above Y X overlaps−above Y X contains Y X inside Y X overlaps−below Y X below Y (A) (OA ) (CY ) (I Y) (OB ) (B) the adaptation of multimedia documents along their spatial dimension. The organization of such a document over space is presented in Fig. 1. It features a multimedia presentation Fig. 2. The ABLR spatial representation. of an Art and Architecture Tour composed of different panels like a Logo, a Text area, a Photo and a Map. In Fig. 1, the Logo is on the left (L) and inside vertically Authors are with INRIA Rhône-Alpes, 655 Avenue de l’Europe 38334 Saint (Iy ) of the Text (Fig. 3, left). Hence, having the relation L Iy Ismier France (e-mail: firstname.lastname@inrialpes.fr) between Logo and Text. B. Semantic adaptation of the ABLR spatial representation distance between the initial and the adapted graphs is 3. Fig 5 In [1], a semantic approach for multimedia document adap- (left) presents an adapted execution of Fig. 3 (right). tation is defined. This approach interprets each document as 1e+006 A2D representation the set of its potential executions, i.e., related to the initial RCC representation ABLR representation 100000 document and a profile as the set of possible executions. In 10000 this context, “adapting” amounts to find the set of potential executions that are possible. When none is possible, the goal 1000 Mean Time [ms] of adaptation is to find executions as close as possible to 100 potential executions that satisfy the profile. We consider both 10 the multimedia document specifications and the profiles as 1 a set of relations holding between multimedia objects. The 0.1 potential and possible executions are ideally represented by relation graphs. Fig. 3 presents two relation graphs. 0.01 2 3 4 5 6 Nb objects {L I } y y{L I } Fig. 5. An adapted execution of Fig. 3, right (left) and experimental results Logo K / T ext Logo / T ext with a logarithmic scale (right). KK{OL A} s KK s KK ss K {O KK L A} s s KK ssss KK ssss {Ix A} KsKs {O O } {I KsKs s ss KKKKR A x A} s ss KKK{R KK OA } IV. E XPERIMENTAL RESULTS s s K KK s s KK s s  yss {OR Cy } %   yss {R Cy } %  We evaluate our spatial adaptation framework on SMIL P hoto / M ap P hoto / M ap {OL OA } {OL A} documents [5] with the non-overlapping constraint. We have compared experimentally three spatial representations, namely Fig. 3. Initial relation graph (left) and adapted relation graph (right). the directional one [3] (A2D), RCC [4] and ABLR. Our benchmark was composed of 50 SMIL documents with i ∈ The potential executions (left) include, in particular, the [2, 6] multimedia objects. Results are provided in Fig. 5 (right). execution of Fig.1. The possible executions correspond to the As we can see the RCC representation is the most efficient following profile: overlapping visible objects are impossible spatial representation for adapting multimedia documents. at a time. It may occur that some potential relations are not However, this one is not precise enough. Our spatial represen- possible (e.g., Text OR Cy Photo). In this context, adapting tation, which is a compromise between all the expressiveness consists of finding a set of relation graphs corresponding of the directional representation and the number of spatial to possible executions (i.e., respecting adaptation constraints) relations, provides much better results than the directional rep- at a minimal distance from the relation graph of potential resentation. Moreover, we also observe that for each adaptation executions (i.e., the initial document specification). the order of efficiency presented in Fig. 5 (right) is respected. Proximity between two relation graphs depends on the proximity between relations beared by the same edge in both V. C ONCLUSION graphs. This proximity relies on the conceptual neighborhood We have presented a way of applying our semantic adap- between these relations and is measured by the shortest path tation framework to the spatial dimension of multimedia distance in the corresponding conceptual neighborhood graph documents. A new spatial representation, called ABLR, has (Fig. 4 presents the one of ABLR). been introduced which ensures a compromise between expres- siveness and computation speed. Cx A This work is limited to the spatial dimension, while adapta- OL A Ix A OR A tion can take advantage of the other dimensions. We are cur- LA Ix OA RA rently working on the extension of both the generic solutions OL OA Cx OA OR OA provided by the framework and the SMIL instantiations. L OA Ix Cy Ix Iy R OA R EFERENCES L Cy L Iy OL Iy OL Cy Cx Cy OR Cy OR Iy R Iy R Cy [1] J. Euzenat, N. Layaı̈da, and V. Dias, “A semantic framework for multi- L OB Cx Iy R OB media document adaptation,” in Proc. of IJCAI’03. Morgan Kauffman, 2003, pp. 31–36. OL OB Cx OB OR OB [2] J. Allen, “Maintaining knowledge about temporal intervals,” Communi- cations of the ACM, vol. 26, no. 11, pp. 832–843, 1983. LB Ix OB RB [3] D. Papadias, T. Sellis, Y. Theodoridis, and M. J. Egenhofer, “Topological OL B Ix B OR B relations in the world of minimum bounding rectangles: a study with r-trees,” in SIGMOD’95: Proc. of the ACM SIGMOD international Cx B conference on Management of data. ACM Press, 1995, pp. 92–103. [4] D. A. Randell, Z. Cui, and A. Cohn, “A spatial logic based on regions Fig. 4. Conceptual neighborhood graph of the ABLR relations. and connection,” in KR’92. Principles of Knowledge Representation and Reasoning: Proc. of the Third International Conference, B. Nebel, C. Rich, and W. Swartout, Eds., San Mateo (CA), 1992, pp. 165–176. Fig. 3 (right) presents the adapted relation graph of Fig. 3 [5] Synchronized Multimedia Integration Language (SMIL 2.0) Specification, (left) with the non-overlapping adaptation constraint. The W3C, 2001. [Online]. Available: http://www.w3.org/TR/smil20/