1. LES DOCUMENTS HYPERMEDIA SYNCHRONISES

Les termes multimédia et hypermédia sont devenus courants de nos jours. La puissance des ordinateurs personnels et les débits de communication actuels permettent d'imaginer l'échange de données sous des formes très évoluées. Cependant, malgré les possibilités offertes, les documents électroniques que l'on rencontre actuellement sur Internet possèdent une structure linéaire très proche des documents papiers (à l'exception de l'hyperlien qui permet de naviguer de manière très efficace). Il existe des outils pour la création de documents structurés au niveau logique (décomposition en parties, chapitres, sections...), au niveau spatial (placement d'objets multimédia à l'écran), mais pour l'instant très peu au niveau temporel (positionnement dans le temps d'objets multimédia).

A l'image des outils pour assister un auteur dans la structuration logique et spatiale d'un document, certains se sont intéressés à l'élaboration de logiciels pour faciliter la création de documents dynamiques, c'est-à-dire où les objets du document sont synchronisés dans le temps à partir de spécifications évoluées fournies par l'auteur. Cet aspect suscite de nombreux problèmes: comment distribuer les données sur un réseau afin d'obtenir un téléchargement optimal lors de la lecture du document ? comment synchroniser à bas niveau les flux de données afin d'éviter les dégradations de qualité ?... et enfin, comment synchroniser à un plus haut niveau les différents objets multimédia afin de garantir les spécifications de l'auteur du document ?

Ce mémoire se penche tout particulièrement sur la dernière question, la synchronisation inter-média, dont la problématique est tout à fait comparable à celle posée pour la création de documents où l'auteur spécifie une structure sous forme de paragraphes, d'images... justifiés, alignés à gauche, centrés dans la page... et un système logiciel se charge de positionner au mieux tous les éléments pour un rendu de la meilleure qualité possible, l'exemple le plus connu étant TeX (cf. [Knuth81]). Dans l'aspect temporel, les relations entre les objets sont plutôt du genre: l'objet A doit être présenté avant l'objet B, l'objet A démarre en même temps que l'objet B...

De nombreuses approches sont proposées pour la synchronisation inter-média, aussi bien au niveau de la formalisation même des relations temporelles entre les objets multimédia, que des méthodes permettant la synchronisation de ces objets lors de la présentation du document au spectateur. N'étant pas experts dans ce domaine, nous proposons un premier chapitre qui positionne simplement nos travaux par rapport à toutes les problématiques et les études déjà menées, renvoyant le lecteur à des documents plus complets sur l'aspect même de la synchronisation hypermédia.

Nous nous intéressons tout particulièrement aux problèmes de recherche opérationnelle, et plus précisément d'optimisation, que la synchronisation inter-média suscite. Pour notre étude, nous avons choisi une formalisation dite par intervalles, très courante, permettant de représenter les relations temporelles des objets multimédia d'un document. Dans le second chapitre nous proposons une représentation sous forme de graphe de cette formalisation, et discutons des limitations que nous apportons alors dans l'expression des relations temporelles. Nous montrons enfin que la synchronisation inter-média peut être modélisée par des problèmes de tension dans un graphe.

Un document multimédia est un document électronique composé de différents médias comme du texte, du son, de la vidéo, des images, des animations, des applets... Lorsqu'il est possible de naviguer entre différents documents multimédia, grâce au lien hypertexte, on parle de documents hypermédia. Par exemple, les pages HTML que l'on trouve sur Internet et la plupart des CD-ROMs éducatifs constituent des documents hypermédia. Il est vrai cependant que, malgré les évolutions technologiques qui nous permettent notamment le transfert et la décompression quasi en temps réel de données volumineuses comme la vidéo, il n'existe toujours pas de documents qui exploitent pleinement le mélange des différents médias.

Les objets multimédia variés qui constituent un document hypermédia sont certes structurés au niveau logique, i.e. le document est décomposé en parties, chapitres, sections, sous-sections...; et au niveau spatial, en permettant le contrôle du placement des différents objets à l'écran ou dans une page (e.g. [Layaida96b]). Mais au niveau temporel, très peu d'outils permettent d'organiser les objets multimédia. Bien qu'une page HTML contienne différents médias animés, ces derniers ne sont pas synchronisés entre eux et n'exploitent que de manière simpliste les capacités vidéo. Dans certains types de document comme les supports pédagogiques, il est intéressant de structurer les différents médias afin d'obtenir une présentation sophistiquée et extrêmement planifiée dans le temps, avec néanmoins une bonne interaction avec le spectateur.

Ces aspects temporels sont regroupés sous le terme de synchronisation hypermédia. Comme le souligne [Herman98], cette problématique soulève de nombreux problèmes à tous les niveaux du développement informatique: les technologies des réseaux, les techniques de compression des données, la synchronisation bas niveau des flux de médias (synchronisation d'une vidéo avec sa bande sonore)... Nous ne nous intéresserons ici qu'à la synchronisation entre objets multimédia à partir de spécifications fournies par l'auteur d'un document, synchronisation qualifiée d'inter-média. Dans la suite du mémoire, lorsque nous parlerons de synchronisation hypermédia, il sera sous-entendu ce type précis de synchronisation.

Pour concevoir un document hypermédia synchronisé, un auteur commence par collecter ou créer des données sous différentes formes (son, vidéo, texte, images...). Ces données peuvent provenir de différentes sources et n'ont, a priori, pas été conçues dans un but unique et précis de diffusion. Dans un second temps, l'auteur tente d'élaborer un scénario à partir des médias récoltés pour concevoir une présentation sophistiquée où le spectateur peut éventuellement intervenir, simplement pour ralentir, accélérer, stopper... la présentation, mais également pour déclencher des événements comme cliquer sur un bouton pour lancer une nouvelle séquence dans la présentation.

De nombreux travaux se sont penchés sur la manière de spécifier un scénario et les possibilités d'intervention du spectateur, et ont aboutis à plusieurs standards internationaux de multimédia: HyTime [Newcomb91], MHEG [Boudnik95], Premo [Herman98], SMIL [Bulterman98]... [Rousseau98] explique que les trois premiers standards cités considèrent plutôt la synchronisation bas niveau des flux multimédia. En revanche, SMIL (Synchronized Multimedia Integration Language), qui a été retenu comme standard par le WWW Consortium (cf. [W3CWeb1]) et qui devrait à terme être intégré dans les navigateurs Web, permet de spécifier des synchronisations entre objets multimédia plus sophistiquées.

Plusieurs outils ont également été élaborés pour fournir une assistance à l'auteur lors de la création d'un document hypermédia synchronisé, et pour assurer la synchronisation du document au moment de sa présentation: CMIFed [vanRossum93], Firefly [Buchanan93a], Isis [Kim95], Madeus [Layaida97], HyperProp [Soares00]... De la conception de ces outils sont issus différents types de modèle pour représenter les spécifications temporelles. Plusieurs travaux très complets discutent des possibilités de chacun: [Jourdan98], [Rousseau99], [Perez-Luque96]. Nous nous intéressons en particulier à l'outil HyperProp, l'un des objectifs de notre étude étant de proposer des méthodes de synchronisation adaptées à ce système.

Dans un premier temps, nous présentons les besoins des auteurs concernant l'aspect temporel des documents hypermédia et plus précisément les différentes relations temporelles entre les objets multimédia qu'ils souhaitent exprimer. Cela nous permet dans le second chapitre de proposer une modélisation sous forme de graphe qui tente de prendre en compte la plupart de ces besoins. Nous exposons ensuite les principaux problèmes de recherche opérationnelle et d'optimisation qui se posent alors, aussi bien au niveau de la conception même des documents hypermédia synchronisés qu'au niveau de la synchronisation de leur présentation. Finalement, nous discutons brièvement des diverses solutions apportées actuellement à ces problèmes.

Considérons un objet multimédia . On note l'événement, la date, de début de la présentation de et l'événement de fin de sa présentation. Une première approche pour définir un scénario consiste à affecter une date de début de présentation à chaque objet multimédia, la date de fin de présentation de chacun découlant de sa durée intrinsèque (pour une vidéo, un son...) ou d'une durée choisie par l'auteur pour les objets intemporels (une image, un texte...). Cette représentation est illustrée par la figure 1.1.

Figure 1.1: Représentation d'un scénario par lignes de temps.

Cette approche comptabilise plusieurs défauts. Tout d'abord, il est très délicat de modifier un tel scénario. Si l'on retire par exemple l'objet , il faut revoir la synchronisation de tout le document. En outre, à cause de problèmes sur le réseau, ou même d'objets multimédia dont on ne maîtrise pas la durée (e.g. une requête dans une base de données), il faut être capable d'exprimer une incertitude quant à la durée d'un objet ou sa date de début de présentation. Il a donc fallu proposer une approche qui corrige ces défauts. Elle est issue de plusieurs travaux synthétisés notamment dans [Jourdan99] qui recommande, pour un système de synchronisation hypermédia, les spécifications que nous présentons maintenant.

Il est important de fournir une certaine flexibilité que [Allen83] propose dans une approche descriptive des relations temporelles (totalement indépendamment de l'aspect synchronisation hypermédia à l'époque) entre les différents objets multimédia. Les figures 1.2 et 1.3 représentent les 13 relations qu'il a ainsi établies. Il y en a en fait 7 fondamentales: meets, before, starts, finishes, equals, during, overlaps. Les six autres (met-by, after, started-by, finished-by, contains, overlapped-by) sont simplement les relations inverses. Toutes ces relations, comme le montre la figure 1.2, expriment des contraintes entre les événements de début et de fin des différents médias. Par la suite, nous ferons référence à ces relations par le terme relations d'Allen.

Figure 1.2: Les 7 premières relations d'Allen.

Bien que décrivant déjà un grand nombre de possibilités, ces relations sont insuffisantes pour les besoins de création de documents hypermédia synchronisés, comme le soulignent notamment [Jourdan99] et [Layaida97]. Ils proposent de compléter ces relations avec l'opération de disjonction or. En particulier, la possibilité de structurer les objets multimédia sous forme de composites entraîne la nécessité d'exprimer une disjonction entre différentes contraintes (e.g. [Fargier98]).

Figure 1.3: Les 6 relations inverses d'Allen.

Prenons l'exemple de la figure 1.4. L'événement du composite est défini par , en d'autre termes coïncide avec la date la plus ancienne des objets qui composent . A l'inverse, la date est définie par . Dans notre exemple, cela s'exprime par des relations d'Allen combinées avec des disjonctions:

Figure 1.4: Un exemple de scénario avec un objet composite.

Pour permettre une expressivité plus grande, il est souhaitable de compléter les relations d'Allen par des informations quantitatives du genre: d'au moins 3 secondes, d'au plus 2 secondes, entre 2 et 3 secondes... Il est également nécessaire de fournir des intervalles de durées pour les objets multimédia, plutôt qu'une durée unique. Nous en expliquons maintenant les raisons, grâce à l'exemple simple illustré par la figure 1.5 (qui reprend le scénario par lignes de temps de la figure 1.1), où les flèches signifient que la fin de l'objet source coïncide avec le début de l'objet cible. La spécification textuelle équivalente à ce schéma est définie comme suit.

Les objets multimédia proviennent souvent de sources différentes, il n'y a donc aucune chance de pouvoir satisfaire les contraintes exprimées précédemment. Cela signifierait par exemple que la durée de ajoutée à celle de est égale à celle de . Nous appelons durée idéale la durée intrinsèque des objets s'ils en ont une (e.g. une vidéo ou un son), ou la durée que l'auteur a choisie s'ils n'en ont pas (e.g. un texte ou une image). En effet, l'auteur peut juger du temps nécessaire à la lecture d'un texte ou à l'assimilation des différents éléments d'une image en fonction du message qu'il tente de faire passer.

Figure 1.5: Un exemple de scénario avec les relations d'Allen.

Pour que les contraintes induites par les relations temporelles puissent être satisfaites, l'auteur doit accepter une certaine flexibilité sur la durée idéale des objets multimédia. Par exemple, pour une image dont la durée choisie était 10 secondes, il est tout à fait concevable que l'auteur accepte une durée effective entre 9 et 11 secondes. De la même manière, la durée d'un texte peut être définie dans un intervalle continu.

En revanche, pour une vidéo ou un son, il est plus délicat d'adapter la durée de manière continue. Cette durée est déterminée par le débit des données, en images par seconde pour la vidéo et en kilobits par seconde pour le son. Il est facile de s'apercevoir qu'un changement d'une seule unité dans le débit du média entraîne une modification de la durée de manière discrète. Pour ce type de média, la tolérance n'est donc pas un intervalle continu, mais un ensemble de valeurs discrètes. Néanmoins, il existe des techniques, détériorant plus ou moins la qualité du média, qui permettent d'ajuster de manière continue la durée de ces médias (cf. [Steinmetz90]). L'aspect discret n'intervient alors finalement que lorsque l'on propose plusieurs alternatives pour un objet multimédia. Par exemple, la bande son d'une narration peut exister en plusieurs versions de durées différentes.

Nous avons vu qu'il était nécessaire de pouvoir gérer les incertitudes. Il en existe deux types, celles sur les durées de certains objets multimédia, et celles sur les dates d'occurrence de certains événements. La première peut être liée tout simplement à un objet multimédia dont la durée ne peut pas être connue à l'avance, comme une requête dans une base de données ou l'exécution d'une applet. La seconde est typiquement une action d'un utilisateur, par exemple un clic sur un bouton qui va déclencher une nouvelle séquence d'objets multimédia dans la présentation.

Pour un formalisme qui tente d'exprimer les synchronisations hypermédia, il est important de dissocier les durées et les événements prévisibles de ceux qui sont indéterminés (e.g. [Fargier98]). [Layaida97] préconise en outre deux relations dites causales. Elles confrontent des événements prévisibles à d'autres imprévisibles.

Figure 1.6: Relations causales.

La première relation, , signifie que les objets multimédia et démarrent en même temps, et que le premier qui se termine arrête l'autre. En résumé, la durée de présentation de et est celle du plus petit, mais celle-ci n'est bien entendu pas connue à l'avance (les durées de et/ou de sont indéterminées). La seconde relation, , signifie que et démarrent en même temps, et que termine si ce dernier n'est pas déjà terminé. Là aussi, les durées de et/ou de sont indéterminées. La figure 1.6 illustre ces deux relations causales.

Comme nous l'avons déjà souligné, la synchronisation hypermédia suscite de nombreux problèmes de recherche opérationnelle. Ceux qui nous intéressent ici concernent la flexibilité offerte par les intervalles continus ou les ensembles discrets des durées tolérées pour les différents objets multimédia. Cette flexibilité offre un nombre important de possibilités de planification parmi lesquelles il faut choisir la meilleure. Avant de nous pencher sur ce problème d'optimisation, intéressons-nous tout d'abord à quelques problèmes de réalisabilité.

La problématique générale consiste, à partir de spécifications temporelles qui décrivent un scénario, à déterminer une planification, autrement dit une date pour chaque événement du scénario. Une planification sera réalisable si elle satisfait toutes les contraintes temporelles exprimées par l'auteur du scénario, i.e. les relations temporelles et les ensembles de tolérance. S'il existe au moins une planification réalisable pour un scénario, on dira que ses contraintes temporelles sont cohérentes. De la littérature, il resort trois questions importantes concernant la réalisabilité d'une planification.

• La première question qui se pose est de savoir si une planification réalisable existe. Si la réponse est positive, il s'agit d'en déterminer au moins une. Si la réponse est négative, il faut déterminer la ou les contraintes qui sont responsables de ce fait, afin que l'auteur corrige les spécifications de son scénario.

• La seconde question, d'ordre plus pratique, consiste à savoir quelles sont les durées minimales et maximales de présentation d'un scénario. Comme l'explique [Kim95], il est tout à fait appréciable, aussi bien pour l'auteur du document que pour un spectateur, de connaître la durée totale d'une présentation.

• La troisième question concerne plutôt la phase de conception du document. Il peut être intéressant pour l'auteur de connaître la durée minimale (ou maximale) qu'un objet multimédia peut prendre dans une planification réalisable. Cela permet de savoir si cet objet peut poser problème dans la synchronisation. En effet, son intervalle durée minimale/durée maximale comparé à son ensemble de tolérance permet de juger des contraintes qu'il subit. Cette information est également importante pour la présentation, un objet avec peu de différence entre ses durées minimale et maximale est critique, un simple retard sur un tel objet pourrait empêcher toute planification réalisable.

Le problème de la réalisabilité prend un aspect très différent dès qu'on introduit des événements ou des durées imprévisibles. Un intervalle de temps plus ou moins précis, dans lequel un événement (ou une durée) imprévisible sera constaté, est généralement connu. Il est donc possible tout de même de détecter certaines incohérences temporelles, en fonction de la date potentielle de l'événement. Il existe des cohérences plus ou moins fortes (cf. [Vidal97]).

• Cohérence forte: il existe une planification réalisable quelque soit l'occurrence des événements imprévisibles. Une planification peut donc être fixée à l'avance, on est sûr qu'elle pourra être réalisée.

• Cohérence faible: il existe toujours, pour chaque occurrence des événements imprévisibles, une planification réalisable. Il n'est pas possible de fixer à l'avance une planification réalisable.

• Cohérence dynamique: il existe une planification réalisable, qui peut être modifiée au moment de l'occurrence d'un événement imprévisible, pour donner une nouvelle planification réalisable. Une planification peut être fixée à l'avance, on est sûr que quoi qu'il arrive, il sera possible de réajuster cette planification.

La problématique peut sembler proche de celle posée en planification de projets ou de tâches (e.g. [Foldes93]). Cependant, la grande différence des problèmes de synchronisation inter-média est qu'aucun temps mort implicite (i.e. non spécifié par l'auteur) n'est autorisé. Les relations temporelles sont telles qu'il est interdit, comme dans l'exemple de la figure 1.5, de jouer plus court que suivi de .

Une fois que l'on sait qu'une planification est possible, la réelle question est de savoir quelle est la planification qui permet une présentation du document de la meilleure qualité. Les ensembles de tolérance offrent une certaine souplesse dans la planification et généralement il existe un grand nombre de solutions réalisables.

Cela soulève le problème de pouvoir quantifier la qualité d'une planification. Cette discussion est encore ouverte à l'heure actuelle. En effet, certains proposent simplement d'attribuer un coût à chaque objet, proportionnel à la déformation (i.e. la différence entre sa durée idéale et sa durée planifiée), e.g. [Buchanan93b] et [Kim95]. Mais cette approche entraîne des inégalités, un objet très contraint peut se retrouver très déformé alors que d'autres très peu. Au lieu d'avoir des coûts proportionnels, des coûts quadratiques sont proposés, e.g. [Kim95]. Enfin, pour des difficultés pratiques à déformer des objets multimédia, certains auteurs préfèrent exprimer la qualité d'un document par un minimum d'objets déformés, sans distinction entre une légère ou une forte déformation, e.g. [Medina04]. Nous discutons plus en détail de cet aspect au chapitre 2 après avoir présenté une modélisation sous forme de graphe des relations temporelles et des ensembles de tolérance introduits ici.

Dans un objectif d'optimisation, une grande différence est faite entre des intervalles de tolérance continus et des ensembles discrets, puisque de manière générale il est plus facile d'optimiser dans un espace continu que dans un espace discret. Deux planifications "proches" dans le domaine continu auront des qualités similaires, alors que dans le domaine discret deux planifications quasiment identiques pourront avoir des qualités très différentes.

Ces problèmes de synchronisation se posent à différentes étapes du cycle de vie d'un document hypermédia (cf. figure 1.7). En effet, il est souhaitable tout d'abord d'assister l'auteur dans la conception des documents, cette phase est appelée l'édition. Lors de l'élaboration du scénario, c'est-à-dire au moment d'énoncer les relations temporelles et de fixer les ensembles de tolérance des durées des objets, il faut vérifier en temps réel que l'auteur ne produit pas un système de contraintes irréalisable, et donc vérifier la cohérence d'un scénario.

Figure 1.7: Cycle de vie d'un document hypermédia.

Il est également important d'essayer d'indiquer la ou les contraintes qui entraînent l'incohérence du scénario. Le problème de réalisabilité devient alors un peu plus délicat à traiter, il faut non seulement trouver une solution réalisable si elle existe, mais déterminer aussi les raisons pour lesquelles éventuellement elle n'existe pas. En outre, il a été expliqué précédemment que certains événements ou durées peuvent être imprévisibles. Cet aspect doit être pris en compte dès la phase de planification du document (e.g. [Vidal97]) et les différents niveaux de cohérence (forte, faible ou dynamique) ou d'incohérence établis.

La création du scénario d'un document est un processus incrémental: l'auteur crée un premier scénario et doit être sûr de suite qu'il est cohérent, il le prévisualise, revient au scénario, ajoute/supprime une relation... Il est donc nécessaire à la fois de vérifier en temps réel la cohérence du document, mais également de pouvoir en peu de temps fournir une planification optimale (ou presque) pour une prévisualisation. L'auteur refusera en effet d'attendre plusieurs secondes pour prévisualiser le résultat de son travail.

Il est également nécessaire, afin de ne pas déstabiliser l'auteur et de toujours lui permettre une approche incrémentale, de garantir une certaine robustesse dans la solution trouvée. Autrement dit, si l'auteur effectue un changement simple dans les relations temporelles ou les ensembles de tolérance, il ne faut pas que la nouvelle solution soit totalement différente de l'ancienne.

Une fois les relations et les ensembles spécifiés par l'auteur, il est possible de prendre plus de temps, dans la phase appelée formatage, pour déterminer la planification de meilleure qualité pour le document. Cette phase peut être lancée à chaque prévisualisation si elle est suffisamment rapide. Ensuite, vient la phase de présentation où la planification est respectée tant qu'il n'apparaît pas de problème, tel qu'un retard sur le réseau au cours du téléchargement d'un média. En cas d'anomalie, il faut alors être capable de réajuster en temps réel la planification, et là encore de disposer d'une méthode efficace pour réagir instantanément.

Il est très délicat de discuter des méthodes qui permettent de déterminer une planification réalisable et/ou optimale, et encore moins de les comparer, puisqu'elles dépendent très fortement de la modélisation choisie, et donc des restrictions d'expressivité induites, pour exprimer les relations temporelles. Nous en proposons néanmoins un rapide aperçu.

La détection de la cohérence d'un scénario et la détermination d'une planification est un problème simple lorsqu'il s'agit uniquement d'intervalles de tolérance continus sans aucun événement ou durée imprévisible. [Song99] propose par exemple une modélisation sous forme de graphe très proche de la nôtre (cf. chapitre 3), les contraintes temporelles d'un scénario se traduisent alors en conditions d'inexistence de certains cycles sur le graphe équivalent, des cycles de longueur négative plus précisément. Le problème peut alors être ramené simplement à un problème de plus court chemin dont de nombreux algorithmes polynômiaux existent. Cette approche est tout à fait adaptée au processus incrémental de la phase d'édition puisque très efficace.

Détecter la cohérence d'un scénario et déterminer une planification avec des événements imprévisibles devient plus délicat. Les solutions proposées reposent sur des systèmes d'énumération exhaustive des possibilités (e.g. RT-LOTOS [Courtiat96b], [Santos99], [Sampaio00a]), ou utilisent une simulation à événements discrets pour tester différentes planifications (réseaux de Petri [Little90]). Ces méthodes sont tout à fait adaptées à cet aspect imprévisible, mais à cause de la combinatoire explicite qu'elle gèrent, elle deviennent tout de même assez vite difficiles à manipuler. Dans le cas où l'aspect imprévisible est écarté, elles deviennent inefficaces faces à la méthode présentée précédemment. En revanche, elles offrent des réponses aux questions concernant la cohérence forte, faible ou dynamique du document.

Toutes ces approches ne peuvent pas être employées en temps réel pour maintenir la cohérence d'un scénario. Pour cela, [Layaida02] propose un algorithme glouton qui tente au cours du temps, face aux événements imprévus tels que des retards dans le téléchargement des objets multimédia, ou des interactions du spectateur, de garantir une planification réalisable, ou tout du moins de s'en rapprocher. L'approche considère des temps morts entre certains points d'articulation du scénario afin de permettre une flexibilité supplémentaire dans la planification du scénario et essaie de les réduire, jusqu'à ce qu'ils soient nuls si possible.

A notre connaissance, il n'existe pas d'approche qui tente de déterminer une planification réalisable, ni même de vérifier la cohérence d'un scénario pour des ensembles de tolérance discrets. Une approche utilisant la programmation par contrainte semble tout à fait adaptée pour manipuler ces ensembles discrets.

Les approches énoncées précédemment ne gèrent pas la qualité des planifications. La solution actuellement employée consiste à modéliser les contraintes temporelles sous forme de contraintes linéaires et de s'assurer que la fonction qui évalue la qualité d'une planification est linéaire. Il est alors possible de résoudre le problème par la programmation linéaire (e.g. [Buchanan93b] et [Kim95]). Mais il est impossible dans ce cas de considérer une mesure de la qualité différente d'une fonction linéaire, alors que [Kim95] explique qu'il serait intéressant de manipuler des fonctions quadratiques pour introduire une équité dans les déformations des objets multimédia.

La problématique suscitée par des événements et des durées imprévisibles est néanmoins légèrement abordée dans ces travaux, simplement en découpant le scénario sur des points d'articulation induits par les données indéterministes. Par la programmation linéaire, les portions du scénario sont ensuite optimisées, les dates trouvées pour les événements prévisibles étant relatives à celles des événements imprévisibles.

Une approche combinant l'un des modèles linéaires précédents avec une technique de Branch & Bound permet d'optimiser la qualité d'une planification mesurée par le nombre d'objets touchés par une déformation (cf. [Medina04]). Cette méthode peut être envisagée pour la phase de formatage, mais ne peut pas être employée pour un usage temps réel.

La programmation linéaire est efficace sur des documents de taille raisonnable (quelques centaines d'événements), et par conséquent est adaptée à la phase de formatage ou de prévisualisation. En revanche, une utilisation temps réel n'est pas possible en l'état. Il n'est pas concevable d'optimiser plusieurs fois le scénario pendant la diffusion du document, mais les contraintes linéaires pourraient être modifiées en temps réel et l'optimisation recommencée à partir de la solution existante. En résumé, aucune solution ne permet à notre connaissance un réajustement en temps réel de la planification optimale d'un scénario.

De cette présentation, il resort que des méthodes variées permettent de répondre à certains des problèmes liés à la synchronisation inter-média. Mais chacune se concentre sur un aspect du problème et est peu adaptée aux autres: la cohérence ou la qualité, l'imprévisible ou le prévisible, le temps réel ou le formatage. L'objectif de notre étude est une investigation des possibilités offertes par une modélisation des contraintes temporelles et des ensembles de tolérance par l'outil de graphe possédant une théorie importante, en espérant couvrir plusieurs aspects de la problématique.

Nous proposons au cours des chapitres des méthodes permettant la détection de la cohérence d'un scénario, la recherche d'une planification réalisable, optimale, avec les principales mesures de qualité énoncées ici. L'efficacité des méthodes et leur approche permettent d'envisager une utilisation en temps réel, aussi bien pour la cohérence que pour la qualité de la planification. Cependant, nous excluons de notre étude les ensembles de tolérance discrets (comme toutes les approches présentées précédemment) et nous ne prenons pas en considération les événements imprévisibles, pour lesquels l'approche générale que nous proposons n'est pas adaptée.

Le chapitre suivant propose l'introduction de quelques notions nécessaires sur les graphes, avant de poursuivre la discussion sur la synchronisation hypermédia par la proposition d'une modélisation sous forme de graphe temporel des spécifications d'un scénario, et l'explication des limitations qu'elle impose sur les relations temporelles ainsi représentables.