Dans ce chapitre nous présentons une vue globale du système multimédia Madeus que nous avons contribué à réaliser et que nous avons utilisé comme plate-forme pour l'expérimentation des services de présentation proposés dans ce mémoire. L'objectif ici est de donner les informations nécessaires à la présentation de notre travail qui constitue la partie présentation du système Madeus. Ainsi, ce chapitre constitue une synthèse de la thèse de Nabil Layaïda [Layaïda 97] et des travaux qui ont suivi (voir les papiers sur Madeus [Layaïda 96a] [Layaïda 96b] [Jourdan 97] [Jourdan 98b] [Sabry 97] [Sabry 98]).
Dans ce chapitre, nous donnons en section 2 une présentation générale du système Madeus. Nous en décrivons les principes généraux, le modèle de document, l'architecture globale et l'interface utilisateur. Dans la section 3, nous décrivons le format pivot ainsi que le format interne des documents Madeus. Dans la section 4, nous présentons le système d'édition et les fonctions de ses différents composants. Finalement, dans la section 5, nous donnons une introduction au système de présentation. Nous en décrivons seulement l'architecture, les fonctions faisant l'objet des chapitres suivants.
Madeus est un système d'édition et de présentation de documents multimédia interactifs. Il prend en compte les trois types d'organisation des documents multimédia identifiés en section II.2.2 du chapitre II : logique, temporelle et spatiale, ainsi que l'aspect hypermédia identifié en section II.3.2 du chapitre II. Le principe de Madeus consiste à fournir aux auteurs de documents multimédia :
Un document Madeus est défini comme un ensemble d'objets de base organisés selon une structure hiérarchique. La structure hiérarchique introduit la notion d'un objet composite qui permet de regrouper sous un même objet en ensemble d'objets de base ou composites. Le modèle de temps attaché aux objets est décrit dans la section 2.2.1 ci-dessous. Les compositions temporelle et spatiale des objets, exprimées sous forme de contraintes (voir section II.2.5.2), sont présentées dans la section 2.2.2.
Dans la classification du comportement temporel des objets média de base introduite dans la section II.2.1, nous avons fait la distinction entre les objets média de base de type discret, continu et indéterministe. Dans notre modèle de document, tous ces types d'objets ainsi que les délais et les objets composites peuvent être représentés par une abstraction à base d'intervalles.
Tout intervalle I est caractérisé par une information temporelle sous forme d'intervalle de durée [lI, uI], où lI et uI sont respectivement des valeurs positives spécifiant les bornes inférieure et supérieure pour la durée de l'objet correspondant.
Ce modèle d'intervalle permet à l'auteur de spécifier la durée d'un objet média selon les formes suivantes :
En outre, une autre caractéristique est attachée aux intervalles représentant les objets média. Un intervalle peut être de deux types :
Il faut noter qu'un objet composite est incontrôlable si au moins un de ses descendants est incontrôlable, parce que la durée d'un objet composite est calculée en fonction de la durée de ses descendants. L'objet incontrôlable participe donc par une valeur incontrôlable dans la durée de ses ancêtres. Par contre, un objet composite est contrôlable si tous ses descendants sont contrôlables.
Nous avons présenté dans chapitre II le besoin de spécifier la synchronisation inter-objet pour la présentation multimédia ainsi que les principales classes d'approches de spécification. Madeus se situe dans les approches à base de contraintes. Dans la suite, nous présentons les deux types principaux de contraintes : les relations temporelles (qualitatives, quantitatives et causales) et les relations spatiales.
Les relations temporelles
Relations qualitatives et quantitatives
Madeus propose une extension à l'ensemble des relations temporelles proposées par Allen [Allen 83] afin de tenir compte de l'aspect quantitatif des durées des objets et des paramètres temporels associés aux relations. La Fig 1 montre l'ensemble des relations temporelles quantitatives entre intervalles avec les paramètres temporels et les contraintes numériques associées. La notation dur(I) représente la durée de l'intervalle I.
Fig 1. Les relations temporelles qualitatives et quantitatives
Relations causales
Madeus possède également un ensemble de relations temporelles causales qui permettent d'exprimer des effets de causalité entre les différents instants du document. La Fig 2 montre les opérateurs supportés dans Madeus. Les flèches verticales de la figure signifient que l'occurrence d'un instant source provoque l'occurrence de l'instant cible. La durée de la construction résultant de chaque type de relation est exprimée sous forme d'un intervalle en fonction des intervalles de durée des objets opérandes A et B.
Fig 2. Les relations temporelles causales
Les relations causales dans Madeus ont la sémantique suivante :
En fonction de la durée de A et B, chacune des relations Parmaster, Parmin et Parmax peut avoir deux représentations graphiques (cf. figure Fig 2 ).
Les relations spatiales
Les relations spatiales que nous adoptons décrivent l'alignement d'objets média sur l'écran dans les deux dimensions : horizontale et verticale [Carcone 97]. Les relations représentent les types de placement suivants : centrage (Center_v et Center_h), alignement (Left_align, Right_align, Top_align et Bottom_align), espacement (Left_spacing, Right_spacing, Top_spacing et Bottom_spacing) et décalage (Left_indent, Right_indent, Top_indent et Bottom_indent).
L'architecture générale de Madeus est illustrée dans la Fig 3 . Le système se compose de deux parties principales : le système d'édition et le système de présentation. Le système d'édition, présenté dans la section 4, gère la création et la manipulation d'une représentation pivot de documents Madeus dont le format est présenté dans la section 3.2. Le format pivot est un format de stockage qui peut être échangé entre des différents sites et plates-formes en assurant une portabilité de haut niveau. Les documents sont représentés au sein du système Madeus selon un format interne sur lequel les différentes opérations d'édition et de présentation sont effectuées. De ce fait, ce format interne, décrit en section 3.3, est considéré comme le lien entre le système d'édition et le système de présentation. Le système de présentation, présenté dans la section 5 et développé dans les chapitres IV et V, s'occupe d'ordonner (Machine d'exécution multimédia) et de manipuler les activités de la présentation (Gestionnaire de présentation) en fonction du scénario spécifié par le format interne et des commandes données par l'utilisateur. Une interface utilisateur est fournie pour effectuer les opérations d'édition (flèche 1) et pour contrôler le cours de la présentation (flèches 2 et 3).
Fig 3. Architecture de Madeus
L'interface d'édition et de présentation de Madeus (voir la Fig 4 ) est construite au-dessus de la boîte à outils graphique de OSF/Motif [Motif 92]. À travers cette interface, l'utilisateur peut charger un document, le modifier, interagir avec ses objets ou contrôler sa progression temporelle. Il peut aussi agir sur les paramètres de sortie du document comme la taille de la fenêtre, sa partie visible (à travers les barres de défilement) ou encore contrôler le volume audio global de la présentation.
Fig 4. Interface utilisateur de l'éditeur Madeus
Un document Madeus peut être visualisé selon deux formats dans deux fenêtres différentes : le document composé (ou en cours de composition) est affiché et exécuté dans la fenêtre « principale » tandis que sa forme pivot (textuelle) est affichée dans la fenêtre « source ». À la fenêtre principale sont associées deux palettes d'édition : la palette d'opérateurs temporels et la palette d'opérateurs spatiaux.
La fenêtre principale est composée de quatre parties (numérotées sur la Fig 4 ) qui offrent des fonctions d'édition et de présentation :
L'utilisateur peut agir directement sur la zone principale (3) tant pour effectuer des opérations d'édition que pour des actions de présentation. Par exemple, il peut sélectionner des objets pour les composer spatialement, temporellement ou les détruire. Lors de l'exécution, l'utilisateur perçoit à travers cette zone l'évolution de la présentation et peut interagir directement au moyen de la souris. Cette interaction permet l'activation d'objets comme les boutons, les hyperliens ou tout objet média susceptible de réagir à ce type de manipulation (en particulier les programmes applets et les plugins).
Le système Madeus manipule des documents décrits selon un format pivot qui est un format déclaratif sous forme d'un marquage descriptif. Cette description couvre l'organisation logique, temporelle, spatiale et hypermédia des documents. Le système Madeus interprète le format pivot en un format interne sur lequel les différentes opérations d'édition et de présentation sont effectuées.
Afin de faciliter la compréhension des rôles des formats utilisés, nous allons d'abord donner un exemple d'un document multimédia. Cet exemple met en valeur les possibilités principales du système Madeus. Puis, nous décrivons le format pivot et le format interne de Madeus, principalement à travers cet exemple.
Supposons que l'on souhaite construire un document multimédia Bande-Annonce qui présente l'histoire et quelques extraits d'un film (voir la Fig 5 ). Le document comporte un objet texte Titre qui présente le titre du film, une Musique de fond, une sous-scène Résumé, un objet texte Générique et une image Lien-Extrait qui représente une ancre d'hyperlien interne vers la sous-scène Extraits. La sous-scène Résumé contient deux sous-scènes : Histoire qui contient l'objet Texte, l'objet Audio et l'objet Image donnant une idée brève sur l'histoire du film, et la sous-scène Extraits qui contient trois sous-scènes E1, E2 et E3. Chacune de ces sous-scènes représente un extrait du film se composant d'une vidéo avec une audio.
Fig 5. Structure logique du document multimédia Bande-Annonce
Fig 6. Scénario temporel du document Bande-Annonce
Le scénario temporel que l'on veut construire (représenté sous forme d'une ligne de temps dans la Fig 6 ) consiste à commencer la présentation du Titre au même instant que la Musique et le Générique. La Musique joue pendant une durée de 65 secondes pendant laquelle l'image Lien-Extrait est activable. Le Générique est présenté pendant 20 secondes et 7 secondes après sa terminaison, un résumé du film démarre. L'objet Résumé commence par présenter un résumé de l'histoire du film sous la forme d'un texte en parallèle avec une audio et une image pendant une durée de 35 secondes. La sous-scène Histoire peut être interrompue par le bouton Bouton. La terminaison de l'objet Histoire a aussi pour effet de rendre ce bouton inactif. Sept secondes après la terminaison de l'objet Histoire, une succession d'extraits du film commence à jouer.
Le marquage descriptif des éléments est le principe de base du format pivot de Madeus, de façon similaire aux principes de structuration des documents statiques (cf. SGML [Goldfarb 90]). Des marques (ou balises) sont associées à chacun des éléments. Les marques sont utilisées pour typer, délimiter et identifier les éléments d'un document et pour leur associer des attributs.
La syntaxe du format pivot est fondée sur le langage de marquage XML (eXtensible Markup Language) [W3C 98a]. XML a été retenu car c'est le standard défini par le W3C (World Wide Wec Consortium) à partir de SGML : il est simple de lecture et d'écriture et permet de décrire selon un format déclaratif l'organisation d'informations structurées. Dans XML, la structure logique générique est décrite dans une DTD (Document Type Definition) qui spécifie la grammaire d'une classe de documents sous la forme d'un ensemble de types d'éléments et d'attributs, et des règles qui permettent de les assembler.
Nous décrivons ci-dessous les principales définitions de types d'éléments et d'attributs de la DTD de Madeus qui a fait l'objet du rapport [Villard 98]. La DTD complète est donnée en annexe A.
Le format pivot de Madeus permet de décrire l'organisation logique ainsi que les organisations temporelle, spatiale et hyperlien [Layaïda 97] :
Au niveau le plus haut, un document Madeus est caractérisé par un ensemble d'attributs comme son nom et sa version. Son contenu est soit un objet de base, soit un objet composite. Ainsi, un document multimédia Madeus se spécifie de la façon suivante :
<!ELEMENT Madeus (%objects; | Composite)>Dans les sections suivantes, nous détaillons les composants principaux de cette syntaxe en les illustrant avec des parties de l'exemple Bande-Annonce dont la structure complète est donnée en annexe B.
Pour chaque type d'objet de base, un type d'élément avec les attributs correspondants est défini. Il existe cinq types de base actuellement supportés dans l'application Madeus :
Ainsi, l'entité %objet se spécifie de la
façon suivante :
<!ENTITY % objects "(Text | Image | Video | Audio |
External)">
Un objet de base est caractérisé par un ensemble de propriétés communes à tous les objets, comme par exemple le nom de l'objet, noté Name, qui doit être unique au sein du composite, et la source, noté Source, de l'objet qui sert à désigner le chemin d'accès soit localement soit à distance. La source contient une extension qui correspond à un type MIME pour identifier le format de codage de l'objet. Ces propriétés incluent aussi les propriétés spécifiques à l'objet, comme la fonte (Font) lorsque l'objet est de type Text, ou encore le volume sonore (Volume) pour un objet de type Audio. Ces propriétés sont spécifiées grâce aux attributs XML regroupés ci-dessous sous forme d'entités XML. Ils sont décrits en section 3.2.4.
<!ENTITY % global_properties
"Name CDATA #REQUIRED
Source CDATA #IMPLIED
Value CDATA #IMPLIED
BackGround CDATA #IMPLIED
Duration CDATA #IMPLIED">
<!ENTITY % position_properties
"Left CDATA #IMPLIED
Top CDATA #IMPLIED">
<!ENTITY % size_properties
"Width CDATA #IMPLIED
Height CDATA #IMPLIED">
<!ENTITY % link_properties
"Href CDATA #IMPLIED
Inclusion CDATA #IMPLIED">
Par exemple, pour le type de base Image on a :
<!ENTITY % image_properties "%position_properties; %size_properties;"> <!ELEMENT Image EMPTY> <!ATTLIST Image %global_properties; %image_properties;>
La déclaration de l'objet Image dans notre exemple de document est donnée dans la Fig 7 :
<Image Name = "Image"
Source
= "affiche.jpg"
Duration
= "10 35 100"
Left =
"20"
Top =
"40" />
Fig 7. L'objet de base Image
Un composite est caractérisé par un ensemble de propriétés (nom, position, etc.).
Le contenu inclut les propriétés par défaut pour tous les descendants du composite. Comme un composite peut contenir tout type d'objet, il peut définir une valeur par défaut sur l'union de toutes les propriétés des objets.Ensuite, les fils du composite sont spécifiés : ce sont soit des objets de base, soit des composites. Enfin, les relations entre les objets déclarés dans le composite sont spécifiées (voir la section 3.2.5).
Ainsi, un objet composite se spécifie de la façon suivante :
<!ELEMENT Composite (Default? , (%objects; | Composite)+, Relations?)>
<!ATTLIST Composite %global_properties; %position_properties;>
<!ELEMENT Default EMPTY>
<!ATTLIST Default %all_properties;>
Par exemple, la Fig 8 montre la spécification de
l'objet composite Histoire. Il se compose de trois objets
(Audio, Image et Text) avec des relations
temporelles exprimant le scénario de la Fig 6 :
les trois objets commencent et finissent en même temps. De même,
la partie marquée <Spatial> définit les
relations spatiales entre l'image et le texte. Les deux objets doivent
être alignés par la haut et le texte est à une distance de
10 points à droite de l'image.
<Composite Name = "Histoire"
FontFamily = "times"
FontSize = "14"
FontStyle = "bold" >
<Audio Name = "Audio"
Source = "histoire.au"
Duration = "30 35 40" />
<Image Name = "Image"
Source = "affiche.jpg"
Duration = "10 35 100"
Left = "20"
Top = "40" />
<Text Name = "Text"
Source = "histoire.html"
FontSize = "16"
Width = "100" />
<Relations>
<Temporal>
<Equals Interval1 = "Audio"
Interval2 = "Image" />
<Equals Interval1 = "Image"
Interval2 = "Text" />
</Temporal>
<Spatial>
<Top_align Interval1 = "Image"
Interval2 = "Text" />
<Right_spacing Interval1 = "Image"
Interval2 = "Text"
distance = "10" />
</Spatial>
</Relations>
</Composite>
Chaque objet, de base ou composite, possède un ensemble d'attributs qui définissent ses comportements (temporel, spatial et hyperlien). Avant de les décrire, nous présentons les caractéristiques générales attachées aux attributs.
Caractéristiques des attributs
Trois caractéristiques peuvent être identifiées pour les attributs définis dans Madeus :
Les attributs temporels
Pour chaque objet de base ou composite, il existe trois attributs temporels à partir desquels le scénario temporel est construit :
Les attributs spatiaux
Pour chaque objet visible de base ou composite, il existe quatre attributs spatiaux à partir desquels le placement spatial est effectué :
Les liens hypermédia
Dans un document Madeus, nous pouvons spécifier trois types fondamentaux de liens hypermédia en utilisant les deux attributs Href et Inclusion :
<Image Name = "Lien-Extrait"
...
Href = "Extraits"
... />
<Image Name = "toto"
...
Href = "~/doc/Presentation.Madeus"
... />
La spécification suivante spécifie un lien vers l'objet Exemple1 dans le document Presentation.Madeus :
<Image Name = "toto"
...
Href = "~/doc/Presentation.Madeus#Exemple1"
... />
Href = null). Ce type
de lien réalise la fonction du bouton d'interaction. Dans ce cas,
l'activation du lien aboutit à la terminaison de l'objet
considéré comme l'ancre source. Par exemple, l'objet
Bouton est défini comme une ancre source d'un lien vide :
<Image Name = "Bouton"
...
Href = "NULL" />
<Image Name = "Grenoble"
...
Inclusion = "~/video/paysage.mpg"
... />
L'ancre destination d'un lien d'inclusion joue le rôle d'une annotation pour l'ancre source, c'est-à-dire elle peut donner plus d'explication sur l'objet représentant l'ancre source. Dans l'exemple ci-dessus, l'objet Grenoble est une image de la ville de Grenoble. Il est l'ancre source d'un lien d'inclusion dont l'ancre destination est une vidéo qui donne plus d'information sur les paysages qu'on peut trouver à Grenoble.
Nous avons défini deux types de relations, temporel et spatial, qui spécifient respectivement la dimension temporelle et la dimension spatiale d'un document multimédia :
<!ELEMENT Relations ((Temporal, Spatial?) |
(Temporal?, Spatial))>
Un objet composite peut avoir soit un ensemble de relations temporelles suivi, de façon facultative, par un ensemble de relations spatiales, soit uniquement un ensemble de relations spatiales. Dans la suite, nous présentons ces relations en donnant des exemples de leur spécification.
Les relations temporelles
Nous pouvons distinguer deux types de relations temporelles de base :
<Starts Interval1 = "Titre"
Interval2 = "Musique" />
Un autre exemple est la relation parmin entre l'objet Bouton et l'objet Histoire est spécifiée comme suit :
<Parmin Interval1 = "Bouton"
Interval2 = "Histoire" />
<Before Interval1 = "Histoire"
Interval2 = "Extraits"
delay = "7" />
Les relations spatiales
Madeus permet non seulement la spécification absolue de placement au moyen des attributs spatiaux Top et Left, mais aussi le placement relatif des objets l'un par rapport à l'autre au moyen d'un ensemble de relations spatiales (voir section 2.2.2). Les relations spatiales entre l'objet Image et l'objet Text sont spécifiées comme suit :
<Top_align Interval1 = "Image"
Interval2 = "Text" />
<Right_spacing Interval1 = "Image"
Interval2 = "Text"
distance = "10" />
L'interprétation de ces relations est réalisée par le gestionnaire de contraintes spatiales, décrit en section 4.4, qui calcule les positions pour tous les objets en fonction des relations spatiales spécifiées. Les relations spatiales sont prioritaires par rapport aux positions absolues définies par les attributs Top et Left.
Dans Madeus, la structure temporelle d'un document est maintenue à deux niveaux :
L'approche adoptée dans Madeus repose donc principalement sur une mise en correspondance entre une représentation de haut niveau à base d'intervalles et une gestion interne de plus bas niveau fondée sur les instants. L'objectif est de ramener la représentation temporelle à base d'intervalles à une représentation temporelle à base d'instants qui permet des traitements efficaces de la synchronisation.
Dans cette section, nous présentons les deux structures (arbre abstrait et hypergraphe), en détaillant plus particulièrement la structure d'hypergraphe et la fonction de chaque composant de cette structure, puisque c'est à partir de cette structure que nous avons construit notre système de présentation.
L'arbre abstrait est une interprétation directe du format pivot. Ainsi, l'arbre abstrait est défini par un ensemble d'objets média de base ou composites où :
Fig 9. Arbre abstrait de l'exemple
À partir de l'arbre abstrait et des relations à base d'intervalles, nous définissons, pour chaque objet composite d'un document, un graphe de contraintes G = (I, A, E) à base d'instants, de la façon suivante :
Deux instants abstraits de début et de fin sont attachés aux objets composites du document, afin de délimiter leur contenu dans le temps. Ceci permet de définir pour chaque objet composite c un sous-graphe de contraintes Gc = (Ic, Ac, Ec) qui est construit de la même façon que celui du document lui-même. Ainsi, nous pouvons ramener le traitement temporel pour tout un document à celui d'un seul niveau de la hiérarchie logique. Le graphe obtenu est orienté et acyclique (Directed Acyclic Graph : DAG) (voir la condition de cohérence qualitative présentée dans la section 4.3.1). À chaque niveau de la hiérarchie logique, le graphe de contraintes correspondant possède un seul sommet début (l'instant début de l'objet englobant) et un seul sommet fin (l'instant de fin de l'objet englobant). La hiérarchie des graphes représentant un document multimédia est appelée un hypergraphe de contraintes.
Fig 10. L'hypergraphe de l'exemple Bande-Annonce
La Fig 10 illustre l'hypergraphe correspondant à l'exemple présenté dans la section 3.1 et dont l'arbre abstrait est représenté en Fig 9 .
Une relation temporelle est interprétée dans l'hypergraphe soit par l'ajout d'un intervalle de délai (noté par delta dans la Fig 10 ) entre sommets comme le délai delta1 entre la fin de Générique et le début de Résumé, soit par la fusion de sommets comme ceux de début et de fin des objets V1 et A1. La construction d'hypergraphe est détaillée en section 4.2.
Dans la Fig 10 , la hiérarchie est représentée par des flèches verticales entre l'arc de l'objet composite et le sous-graphe qui représente l'organisation temporelle de ses descendants.
Chaque arc est étiqueté par les bornes inférieure et supérieure de l'intervalle de durée. Dans cet hypergraphe, les intervalles de durée sont notés de trois façons différentes en fonction de spécification utilisée par l'auteur (voir section 2.2.1) :
Les durées ayant des bornes infinies seront restreintes par le gestionnaire de contraintes en appliquant les algorithmes de la vérification de la cohérence et les algorithmes du formatage temporel (voir section 4.3).
Chaînes temporelles
L'hypergraphe G étant à base d'instants, il offre de façon directe une vue supplémentaire du document sous forme d'un ensemble de chaînes temporelles. Ces chaînes sont définies de la façon suivante :
Définition : Une chaîne temporelle est une séquence d'arcs contigus Seq={a1,... , an} du graphe G telle que chaque arc aj, 2 <= j <= n-1, n'est relié qu'à un seul arc prédécesseur et à un seul arc successeur. Le résultat est un seul arc Ch=[a1, an]x qui représente une chaîne et qui est étiqueté par un intervalle ayant les caractéristiques suivantes :
On peut ainsi définir un graphe de chaînes noté GCh, obtenu à partir du graphe G en remplaçant la suite des arcs composant une chaîne Ch par l'arc Ch dans GCh. Ainsi, la Fig 11 montre l'hypergraphe de chaînes de notre exemple. Par exemple, la séquence d'objets Seq = {Générique, delta1, Résumé} (voir la Fig 10 ) constitue la chaîne Ch6 dont l'intervalle est égal à [27, +inf] (voir la Fig 11 ).
L'intérêt de cette structuration en chaînes dans Madeus est principalement lié à deux considérations. Elle permet d'améliorer les performances des opérations de mise à jour du document, car la plupart des traitements portent sur des chaînes et non pas directement sur des intervalles, en particulier, en ce qui concerne la vérification de la cohérence des relations temporelles spécifiées. Par ailleurs, les chaînes peuvent être mises à profit pour gérer l'indéterminisme pendant l'édition et pendant la présentation puisqu'elles constituent les branches parallèles du scénario (voir la section IV.4.4).
Fig 11. Hypergraphe de chaînes de l'exemple
Le système d'édition offre un ensemble de fonctions permettant de construire ou de modifier de façon interactive un document multimédia. Il permet aussi le chargement en mémoire d'un document ainsi que son stockage sur disque en fin de session d'édition. Dans cette section, nous présentons brièvement le système d'édition de Madeus qui est plus précisément détaillé dans la thèse de Nabil Layaïda [Layaïda 97].
Nous pouvons considérer que le processus d'édition d'un document est une combinaison des quatre fonctions suivantes :
Le gestionnaire d'édition s'occupe de l'interprétation du format pivot des documents multimédia et de la génération de l'hypergraphe de contraintes (format interne) correspondant, autrement dit, il traduit les relations à base d'intervalle en relations à base d'instants. Il se charge également de faire la transformation dans le sens inverse, c'est-à-dire il traduit le format interne en format pivot afin de le sauvegarder sur le disque.
Le gestionnaire d'édition reçoit les commandes à effectuer via l'interface utilisateur. Il réalise les fonctions d'édition en manipulant l'hypergraphe de contraintes comme suit :
Fig 12. Ajout de relations
Fig 13. Suppression d'une relation
Notre approche pour gérer la structure temporelle d'un document est fondée sur les contraintes et leur propagation lors de l'ajout, de la suppression et de la modification de contraintes. L'avantage principal de cette approche est qu'elle permet à l'auteur de spécifier facilement et de façon naturelle un scénario temporel. Par contre, son désavantage est la possibilité d'introduire une incohérence lors de l'ajout d'une nouvelle relation temporelle. Il est donc nécessaire de vérifier la cohérence du document après l'ajout de chaque relation. Il a été prouvé que les algorithmes de vérification de cohérence des relations à base d'intervalles ont une complexité polynômiale [Vilain 86] induisant des délais de traitement trop longs pour un environnement interactif.
C'est pourquoi nous avons tiré parti du format interne à base d'instants des documents Madeus pour mettre en oeuvre des algorithmes de vérification de cohérence avec une complexité linéaire [Layaïda 97]. Ces algorithmes, sont des adaptations des travaux de [Chleq 95]. La description ci-dessous en constitue une synthèse.
Dans la suite de cette section, nous présentons brièvement les solutions mises en oeuvre dans Madeus pour la vérification des trois types de cohérence suivants :
Cohérence qualitative
La première phase de vérification qui est réalisée lors de l'insertion d'une relation temporelle est celle qui correspond au cas de la Fig 14 . Dans cet exemple, la traduction de la relation d'intervalle en relations d'instants sur la structure du graphe a pour effet l'introduction d'un cycle. Ce cycle est formé par les intervalles A, B et l'intervalle correspondant au délai t de la relation C overlaps(t) A.
Fig 14. Exemple d'incohérence qualitative
Pour chaque relation d'intervalle introduite dans le document, la vérification de la cohérence qualitative consiste donc à vérifier que l'insertion de délais ainsi que la fusion des sommets qu'elle entraîne sur le graphe, n'introduisent pas de cycles.
Cohérence quantitative
La deuxième phase de vérification lors de l'insertion d'une relation temporelle est celle qui correspond au cas de la Fig 15 . Dans cet exemple, les objets A, B et C ont respectivement des durées égales à 30, 20 et 20 secondes. L'ajout de la relation C overlaps B est qualitativement cohérente mais elle est quantitativement incohérente parce que la durée de l'objet C ne permet pas la réalisation de la relation ajoutée.
L'ajout d'une relation cause l'insertion de nouvelles chaînes et/ou la modification de chaînes existantes. C'est cette liste de chaînes insérées et modifiées qui est passée à l'algorithme de vérification quantitative présenté dans [Layaïda 97]. L'algorithme que nous utilisons dans Madeus est fondé sur une version incrémentale [Chleq 95] de l'algorithme DPC (Directional Path Consistency) [Meiri 92].
Fig 15. Exemple d'incohérence quantitative
La mise en oeuvre de l'algorithme peut restreindre l'intervalle de durée associé aux objets média comme montré dans la Fig 16 qui représente l'hypergraphe de notre exemple après l'application de l'algorithme de la vérification de la cohérence quantitative. En effet, pour deux chaînes en parallèle, leurs bornes de durée peuvent être restreintes à l'intervalle de durée commun entre les deux chaînes, c'est-à-dire l'intersection entre les deux intervalles. Par exemple, pour les objets X [lx,ux] et Y [ly,uy], l'intervalle résultant de l'intersection est égal à [max (lx,ly), min (ux,uy)]. Prenons l'exemple de la Fig 10 et de la Fig 16 : l'intervalle équivalent aux trois objets (Audio, Image et Texte) en parallèle est égal à [30, 45], restreignant ainsi les intervalles des objets Image et Texte.
L'intervalle de durée d'un objet composite dépend de l'organisation temporelle de ses fils. L'intervalle est calculé en appliquant une version de l'algorithme du plus court chemin (all pairs shortest paths) qui permet de calculer le graphe minimal de contraintes en tenant compte de l'ordre temporel de sommets [Layaïda 97]. Un graphe de contraintes est dit minimal lorsque les valeurs des intervalles de durée sont restreintes aux seules valeurs appartenant à au moins une solution pour le scénario. Par exemple, à l'objet composite Bande-Annonce est attribué l'intervalle de durée [139, 199] calculé par l'algorithme du plus court chemin entre le sommet de début et le sommet de fin de son sous-graphe.
Fig 16. L'hypergraphe après la vérification quantitative
Cohérence indéterministe
La spécification temporelle présentée jusqu'ici traite le problème de cohérence pour les instants dont l'occurrence à l'exécution est entièrement sous le contrôle du système de présentation (les dates de présentation des différents objets média sont modélisées par des intervalles contrôlables). Le principe de vérification quantitative utilisé s'appuie sur la propagation de contraintes qui réduit la durée de ces intervalles afin de garantir l'existence d'une solution. Or pour les objets modélisés par des intervalles incontrôlables, les intervalles correspondants ne peuvent pas être modifiés car ils dépendent de facteurs externes au système de contraintes (interaction de l'utilisateur, exécution de programmes, délais variables dus aux accès réseau, etc).
Dans la section IV.4.4, nous présentons de façon détaillée les techniques utilisées pour traiter l'indéterminisme d'un scénario multimédia.
Le formatage temporel, par analogie avec le formatage spatial, consiste à affecter des valeurs aux différents intervalles du graphe. Cette opération n'est nécessaire que lorsque l'utilisateur lance la présentation du document. Le formatage temporel est appliqué à partir d'un hypergraphe minimal de contraintes (voir la Fig 16 ), puisque ce dernier contient les seules valeurs de durée susceptibles de figurer dans la solution finale.
Fig 17. L'hypergraphe après le formatage temporel
Dans Madeus, l'opération de formatage temporel consiste à appliquer un algorithme qui tient compte des valeurs préférables de durée d'objets, à deux phases pour calculer deux solutions pour un document (à partir du début du graphe puis à partir de sa fin). On peut ainsi mieux répartir les contraintes qui pèsent sur les différentes chaînes et éviter que certains objets média ne subissent des déviations trop importantes par rapport à leurs valeurs préférables. Nous n'allons pas détailler l'algorithme ici, puisque il est bien décrit dans la thèse [Layaïda 97]. La Fig 17 illustre le résultat du formatage temporel sur l'hypergraphe de notre exemple. Nous pouvons voir que l'algorithme a réussi à calculer des durées pour les objets média et des dates pour les instants de début et de fin d'objets.
Les relations spatiales sont traduites dans un système de contraintes géré par le résolveur DeltaBlue [Sannella 93]. Il maintient une solution pour le placement d'objets de façon incrémentale en fonction des actions de l'auteur : l'ajout ou le retrait de relations et le déplacement d'objets.
Pour pallier certaines limitations du résolveur DeltaBlue en ce qui concerne le maintien des contraintes cycliques, nous avons défini un module spécifique pour le traitement des relations redondantes, lesquelles introduisent des cycles dans le système de contraintes [Carcone 97].
Le gestionnaire de contraintes spatiales de Madeus est composé de trois modules : le module de traitement des relations, le module de gestion des relations redondantes et le module de maintien de solution DeltaBlue (Fig 18 ).
Fig 18. Le gestionnaire de contraintes spatiales
Une des limitations de ce gestionnaire spatial est qu'il ne prend pas en compte les relations sur les dimensions des objets, qui peuvent introduire des cycles en présence d'autres relations. C'est le cas par exemple d'une relation portant sur la largeur de deux objets avec une relation portant sur le bord droit de ces mêmes objets. Par contre, son avantage réside dans sa simplicité pour la spécification des relations spatiales et dans la rapidité de calcul d'une solution pour le placement des objets, ce qui procure un meilleur suivi visuel des déplacements.
Le système de présentation offre un ensemble de fonctions permettant de jouer le document multimédia à partir d'un hypergraphe cohérent et formaté. Dans le reste de cette thèse, nous nous concentrons sur l'explication du fonctionnement des composants du système de présentation Madeus. Dans cette section, nous présentons brièvement les fonctions de présentation qui seront détaillées dans les chapitres qui suivent.
Dans Madeus, le processus de présentation d'un document réalise les fonctions que nous avons identifiées dans le chapitre II, c'est-à-dire :
Les différents modules qui réalisent les fonctions de présentation définies ci-dessus sont organisés comme décrit dans la figure Fig 19 . Cela correspond à la décomposition suivante des boîtes « Machine d'exécution multimédia » et « Gestionnaire de présentation » de la Fig 3 :
Fig 19. Architecture détaillée du système de présentation Madeus
Dans ce chapitre, nous avons présenté le système d'édition et de présentation de documents multimédia Madeus. En particulier, nous avons présenté l'architecture générale de Madeus. Ensuite, nous avons détaillé le format pivot de document Madeus qui nous permet l'expression de l'organisation logique, spatiale, temporelle et hypermédia. Étant défini en XML, le format pivot offre un mode déclaratif de spécification des contraintes qui supprime tout besoin de programmation.
Nous avons présenté également le format interne d'un document Madeus qui est une interprétation directe du format pivot sous forme d'un graphe hiérarchique acyclique (hypergraphe). Il représente le lien entre le système d'édition et le système de présentation car les deux systèmes utilisent ce format pour effectuer leurs fonctions.
Nous avons présenté le système d'édition et les fonctions de chacun de ses composants. En particulier, nous avons vu que le format interne facilite la réalisation de l'édition incrémentale car il permet de vérifier la cohérence des contraintes après chaque modification élémentaire du document avec une complexité linéaire.
Nous avons enfin donné brièvement une idée du système de présentation, de ses fonctions et de son architecture. Le système de présentation fera l'objet des chapitres suivants dans lesquels nous allons montrer le rôle important qui joue le format interne décrit dans ce chapitre. En effet, par la vue globale du document qu'il offre, l'hypergraphe aide à effectuer les fonctions de synchronisation entre tous les objets faisant partie du document. Cette vue globale va également servir à compenser la désynchronisation due aux objets incontrôlables.