Chapitre 3

Modèles temporels pour les documents multimédia

[Table des matières]

1 Introduction

Dans le chapitre précédent, nous avons montré le rôle important du temps à travers son impact aussi bien sur l'architecture d'une application d'édition et de présentation multimédia, que dans un modèle de documents. Nous avons souligné en particulier que le problème de la synchronisation temporelle s'étend depuis le niveau spécification jusqu'aux autres niveaux liés à la présentation. Pour apporter des réponses adaptées à chacun de ces niveaux, il est nécessaire d'adopter une analyse descendante des différents problèmes. En effet, l'opération d'édition qui consiste à spécifier la synchronisation temporelle d'un document multimédia constitue le point de départ de son cycle de vie. Pour un auteur, ce cycle comprenant la création, la préparation, la correction et la publication est similaire à celui rencontré par un développeur dans le domaine du génie logiciel. La réutilisation maximale, la puissance des fonctions d'édition et la facilité de maintenance des documents et de leurs composants sont des qualités très recherchées. Un système d'édition doit en outre gérer une description précise et cohérente de l'information temporelle. Une telle description conditionne, en effet, la restitution correcte du document à l'utilisateur (étape de présentation).

Cependant, on peut constater que l'on dispose de peu d'expérience en matière de composition temporelle (domaine neuf du fait de la technologie) et, de fait, les travaux pour la spécification de documents multimédia sont encore peu nombreux. Ce facteur, conjugué à la grande richesse temporelle des éléments et de leur schéma de composition temporel, rend actuellement l'opération d'édition particulièrement complexe. La réduction de cette complexité passe par la définition d'un niveau d'abstraction suffisant pour rendre cette opération plus accessible.

C'est dans cette perspective qu'on se propose, dans ce chapitre, d'étudier les modèles temporels pour les documents multimédia.

Un modèle temporel pour l'édition et la présentation multimédia est composé de trois parties [PER 96]:

La première partie de ce chapitre est consacrée à la définition d'un scénario temporel, à la représentation de l'information temporelle de base et à la spécification de la synchronisation d'un document. Dans la deuxième partie, on aborde les techniques d'analyse et de synthèse des spécifications de scénarios. Cette analyse porte principalement sur le processus de composition temporelle, la vérification de la cohérence et la production automatique d'une représentation de plus bas niveau adaptée à la phase de présentation.

[Table des matières]

2 Scénarios temporels

Dans cette section, nous présentons la notion de scénario temporel, les différentes façons de les décrire, ainsi que les qualités attendues d'un modèle temporel adapté à l'édition de documents multimédia.

[Table des matières]

2.1 Définitions

Un scénario temporel définit comment les éléments d'un document s'enchaînent dans le temps. C'est en quelque sorte la projection du document sur la dimension temporelle.

À titre d'exemple, un document reproduisant un exposé est composé d'un ensemble de transparents qui sont enchaînés en séquence. Supposons que chaque transparent soit composé d'un texte, d'une image et d'un commentaire audio et que le temps de présentation du transparent soit égal à la durée du commentaire audio. Les trois entités sont donc reliées entre elles dans le temps (elles démarrent et finissent en même temps) et elles sont dépendantes du temps (le commentaire audio dure par exemple 2 minutes).

À tout scénario, peuvent correspondre une ou plusieurs traces d'exécution qui le respectent. Une trace d'exécution est définie de la façon suivante : c'est une suite de triplets (instant, ensemble d'observations, séquence d'actions). Chaque action correspond au démarrage d'un élément et une observation à une terminaison.

On peut distinguer deux types de scénarios temporels dans une présentation multimédia :

Image scenarios.gif
Fig 0. Exemple de scénario temporel indéterministe

Dans la figure Fig 0 , nous décrivons en langage naturel un exemple de scénario de type indéterministe. Dans cet exemple, une présentation est composée de cinq éléments multimédia dont les dépendances temporelles sont les suivantes : un élément de type texte (Titre) est présenté durant 40 secondes. Il est suivi d'une séquence Audio et d'une séquence Vidéo. Ces deux séquences démarrent simultanément. Lorsque les deux sont terminées, un élément Texte est présenté pendant 30 secondes suivi d'une Image. On suppose que les éléments Audio et Vidéo sont stockés sur un site distant et qu'il n'existe aucune connaissance a priori sur leur durée de présentation qui peut varier d'une exécution à l'autre. Chaque exécution du scénario conduit à une trace différente (voir Fig 0 ). Nous constatons donc qu'à partir d'une même description en langage naturel, les traces peuvent varier d'une présentation à l'autre.

De façon analogue à l'exemple présenté, une méthode de spécification d'un scénario doit être suffisamment générale pour couvrir l'ensemble de ses traces. Bien entendu, cette description doit s'appliquer aussi bien aux scénarios déterministes qu'aux scénarios indéterministes.

[Table des matières]

2.2 Niveau de représentation des scénarios

Un scénario peut être spécifié de deux façons. La première consiste à décrire un scénario à travers une trace particulière, c'est le principe des timelines. Cela revient à le considérer comme un ensemble d'instants indépendants qui se rapportent à un repère temporel unique (le début du document). Dans ce type de représentation, basé sur un temps absolu, les relations temporelles entre les événements sont implicites et l'ordre induit est total. L'analyse et la synthèse sont dans ce cas inutiles, et la représentation du document peut être exploitée telle quelle pour ordonnancer la présentation. En effet, il suffit simplement de déclencher les différents événements à leur date de début. Ce type de représentation ne permet pas de représenter des scénarios indéterministes. De plus, il n'est pas adapté à la nature incrémentale du processus d'édition. En effet, toute modification nécessite une reconsidération globale de la spécification, du fait de l'incapacité de ce type de représentation à expliciter les relations temporelles. Ce sont ces caractéristiques qui nous la font qualifier de représentation de bas niveau.

À l'opposé, la seconde façon consiste à décrire le scénario à partir d'une mise en relation des différents éléments qui le composent. Cette forme de temps relative, contrairement à la précédente, permet de rendre explicite toutes les dépendances temporelles du scénario et induit un ordre partiel entre ses différents instants. Cette représentation de haut niveau permet d'obtenir des structures temporelles abstraites plus facile à organiser et à mettre à jour. Cependant, ces qualités ne sont pas acquises sans contre-partie. La nature de la représentation du temps utilisée introduit dans les spécifications de scénarios des risques d'incohérences. De plus, pour effectuer la présentation, il est nécessaire de rapporter cette représentation au temps, d'où l'importance de fournir des mécanismes d'analyse et de synthèse pour ce type de représentation.

[Table des matières]

2.3 Critères d'évaluation d'un modèle temporel

Avant d'aborder plus en détail les modèles temporels, il convient de préciser d'abord les critères qui permettent d'évaluer un modèle donné. Dans notre étude, l'objectif attendu de la modèlisation est double. Il s'agit d'une part de faciliter l'opération d'édition d'un document et donc de satisfaire au mieux les exigences d'un auteur, et d'autre part de produire automatiquement une forme du document adaptée à la présentation. Un modèle donné doit répondre aux objectifs concernant la dimension temporelle des documents multimédia. Ils se résument ainsi : À travers les modèles temporels, on cherche ainsi à retrouver deux composants importants de l'édition multimédia : le premier est un langage temporel permettant l'expression de la synchronisation et le second est l'ensemble des méthodes pour son analyse et sa synthèse. Les critères introduits doivent être évalués au niveau du modèle pour juger si celui-ci est adapté à l'édition multimédia.

[Table des matières]

3 Représentation de l'information temporelle multimédia

Dans le chapitre précédent, nous avons clairement identifié deux phases de traitement d'un document multimédia : son édition et sa présentation. Dans ces deux phases la dimension temporelle apparaît au coeur du problème et nécessite donc une étude plus approfondie.

De la même façon que les dimensions logique [HYT 92][ISO 92] et spatiale [ROI 94] des documents ont été modélisées, nous proposons dans cette section un modèle temporel permettant de caractériser les présentations multimédia ainsi que le processus de leur mise en relations dans un document : la composition temporelle.

[Table des matières]

3.1 Modélisation de l'information temporelle de base

Avant d'aborder les méthodes de spécification d'un scénario, nous commençons par la définition des entités de base qui le composent. En particulier, nous caractérisons le comportement temporel de chaque élément indépendamment d'un scénario donné. Cette étape nous permet de modéliser les différents éléments multimédia de façon homogène et indépendante de leur contenu et de leur type (audio, vidéo, texte, etc.), on parle alors d'unités temporelles.

Tout élément multimédia peut être manipulé à travers trois informations temporelles essentielles :

L'une de ces trois informations est redondante. En effet, il est possible de calculer l'une en fonction des deux autres. Mais le choix des informations retenues fait partie du langage et donc du modèle, car la mise en relation des éléments se fait à partir de ces informations.

Il existe deux façons de représenter le déroulement d'un scénario : à travers les changements qui surviennent (la terminaison de la vidéo correspond au démarrage de l'audio) ou au contraire en reliant globalement les activités entre elles (la séquence audio est présenté pendant la séquence vidéo). Ceci débouche sur deux types de représentations :

  1. Une représentation fondée sur les instants. Dans ce cas, un élément multimédia, qu'il soit logique ou de base, est décrit dans un scénario par un instant de début et un instant de finnote1, comme dans Firefly [BUC 93] et Maestro [DRA 93].
  2. Une représentation fondée sur les intervalles. Un élément multimédia est considéré comme une entité temporelle de base décrite par sa durée comme dans OCPN [LIT 93] et Cmifed [BUL 95].
Dans les représentations multimédia fondées sur les intervalles, les unités temporelles de base peuvent être classées en trois catégories en fonctions des caractéristiques attachées à leurs durées :
Image donnees.gif
Fig 1. Les unités temporelles de base

Domaine de validité d'un intervalle

Les unités de présentation à base d'intervalles peuvent être modélisées par un ensemble décrivant leur valeurs possibles de durée ; on parle de leur domaine de validité ou de leurs bornes. Le domaine de validité d'une unité de présentation peut être défini par un triplet de valeurs [min, nom, max] :

Le comportement temporel de l'ensemble des éléments multimédia peut être représenté par ces domaines de validité. Si on se restreint à la manipulation des éléments à travers ces domaines, il devient possible d'abstraire leur contenu au sein du modèle et de rendre homogène leur représentation et leurs traitements. Les contraintes liées à la perception humaine de la synchronisation se traduisent alors simplement par un choix adapté de ces trois valeurs.
Image fenetre.gif
Fig 2. Domaine de validité d'un intervalle temporel

On peut noter qu'il existe des différences dans le sens attaché à ces bornes en fonction des catégories introduites plus haut (continus, discrètes, indéterministes) [ERF 93]. Ces différences peuvent se traduire par l'amoindrissement du sens de l'une des valeurs du triplet. C'est le cas des unités temporelles de type continu où le domaine de validité correspond à une notion de flexibilité temporelle inhérente à certains éléments multimédia. Par exemple, pour un élément de type animation représenté par les bornes [20, -, 30] secondes, l'auteur peut choisir à sa guise la valeur qui lui convient dans cette plage car il s'agit de contraintes temporelles synthétiques. Pour les éléments discrets comme le texte, cette flexibilité est infinie (bornes ]0, -,infty]), et se distingue comme le cas de l'animation par l'absence de valeur optimale. Le domaine de validité constitue donc un paramètre d'édition puisqu'il est sujet à un choix d'une part pour la définition des valeurs admissibles et d'autre part pour la valeur définitive retenue pour un scénario donné. Dans certains cas comme pour la vidéo et l'audio, le domaine de validité peut être lié à une notion de solution préférable mesurée en fonction de l'écartement par rapport à la valeur nominale (qui correspond aux contraintes naturelles). Par exemple, pour un élément de type audio modélisé [23, 25, 27], une durée de 26 sera jugée plus souhaitable que la valeur maximale de 27, bien que cette dernière reste acceptable. Intuitivement, ce dernier type d'éléments introduit plus de contraintes puisque le choix des valeurs de validité est généralement plus restreint que dans les exemples de l'animation et du texte.

La mise en relation d'éléments est la seconde source de contraintes. Par exemple dans un scénario dans lequel une animation est présentée en même temps qu'un élément audio, les domaines de validité doivent être combinés pour retenir celui qui convient le mieux.

[Table des matières]

3.2 Expression des relations temporelles

Les relations temporelles permettent de décrire la façon dont les éléments multimédia doivent être combinés temporellement pour produire le scénario d'un document. Les relations temporelles servent à la fois comme entrée de la partie analyse d'un modèle et comme une mémoire des intentions de l'auteur. Cette représentation permet de définir l'état courant d'un document sur lequel s'appliquent les différentes opérations de composition.

Afin de définir un jeu de relations ou d'opérateurs temporels permettant la construction d'un document, nous étudions dans cette section trois aspects importants liés à ces relations temporelles qui peuvent intervenir pour décrire un scénario :

Étant donnée l'existence de deux modes de représentation des unités temporelles (les instants et les intervalles), il en résulte deux classes de relations temporelles. Les relations temporelles fondées sur les instants et les relations fondées sur les intervalles.

Dans ces deux types de relations, les scénarios sont représentés à partir d'un ensemble B de relations temporelles dites primitives. Ces relations sont exclusives et permettent d'exprimer comment les unités temporelles d'un document (les éléments) se situent les unes par rapport aux autres.

[Table des matières]

3.2.1 Relations à base d'instants

Dans les relations à base d'instants (algèbre d'instantsnote2 notée PA : Point Algebra), les unités temporelles considérées dans les relations sont les instants de début et de fin des éléments. Étant donnés deux instants dans un scénario, trois relations peuvent exister entre eux. Un instant peut en précéder un autre (<), lui succéder (>) ou lui être égal (=). L'ensemble des relations primitives de l'algèbre d'instant est noté B = { <, >, = }.

Dans certains cas, les relations entre certains instants d'un scénario peuvent être connues de façon moins précise. Dans l'opération d'édition, il existe deux sources à ce genre d'imprécision :

Afin d'illustrer le premier type de situations, supposons que la seule relation que nous connaissions entre deux instants e1 et e2 est que e1 ne peut avoir lieu après e2. Cela signifie que e1 a lieu avant ou en même temps que e2. Cette relation est notée e1< e2 wedge e1 = e2 ou encore e1 {<, = } e2.

L'ensemble des relations composées ou disjonctives, noté 2B, représente des disjonctions des relations primitives. Puisqu'il existe 3 relations primitives, il en résulte 23 = 8 relations composées qui forment les parties de B. Dans la suite, chacune de ces relations sera notée par un symbole particulier. Par exemple, au lieu de noter e1 {<, =} e2, nous utiliserons e1 <= e2. Les relations composées à base d'instants sont : bot, <=, <, =, >, >=, =/=, ?, où la relation ? représente une disjonction contenant l'ensemble des relations primitives et bot l'ensemble vide des relationsnote3.

De façon intuitive les relations primitives <, >, = sont utiles pour la composition multimédia car elles interviennent dans la construction des scénarios multimédia les plus simples. En est-il de même pour toutes les formes disjonctives {<=, >=, =/=, ?} ? Afin de répondre à cette question, nous devons d'abord tenir compte des caractéristiques temporelles d'une présentation multimédia. Dans le chapitre précédent, nous avons montré que de légères fluctuations sur l'instant de début des éléments et sur leur durée (domaine de validité) sont tolérées. Par exemple, la présentation d'un élément audio une milli seconde plus tard ou plus tôt que sa date prévue n'affecte en rien la qualité de la présentation. Ceci signifie qu'il n'y a pas de différence perceptible si on spécifie entre deux instants e1 et e2 la relation e1 < e2 ou e1 <= e2. De façon similaire la relation =/= se démarque de la relation ? sur un seul instant du temps. Les quatre relations d'instants : { <, =, >, ? } sont donc les seules qui sont utiles pour la spécification de scénarios multimédia [WAH 94][MIN 96].

[Table des matières]

3.2.2 Relations à base d'intervalles

Dans les relations à base d'intervalles (algèbre d'intervalles notée IA : Interval Algebra), les relations possibles entre deux éléments multimédia se réduisent à toutes les combinaisons de positionnement possibles de deux intervalles sur une droite orientée. Le modèle le plus général, proposé par J.F. Allen [ALL 83], dresse la liste exhaustive de toutes ces relations. La liste des combinaisons possibles entre éléments multimédia comporte 13 relations consistant en 7 relations de base (cf. Fig 3 ) et de leurs relations inverses, l'égalité étant elle-même son inverse. Ces treize relations se répartissent en deux classes, celle des relations de séquentialité et celle des relations introduisant le parallélisme de présentation. Dans l'avant-dernière colonne du tableau, nous présentons la traduction de chaque relation sous la forme d'une suite de relations à base d'instants. Les variables x et y représentent des intervalles et les notations x- et x+ correspondent respectivement aux instants de début et de fin de l'intervalle x.
Relation Symbole Inverse Relation à base d'instants équivalente au symbole Classe
x before y b bi x- < x+ < y- < y+ Seq
x meets y m mi x- < x+ = y- < y+ Seq
x overlaps y o oi x- < y-< x+ < y+ Par
y finishes x f fi x- < y-< x+ = y+ Par
y during x d di x- < y- < y+< x+ Par
x starts y s si x- = y-< x+ < y+ Par
x equals y e ei x- = y- < x+ = y+ Par
Fig 3. Les relations à base d'intervalles

De façon analogue aux relations à base d'instants, il existe 213 = 8192 relations composées. Par exemple, si l'auteur d'un scénario veut décrire que deux intervalles A et B sont disposés séquentiellement dans le temps, la relation qui les lie correspond à la forme disjonctive suivante : A {b, bi, m, mi } B. Cette relation consiste simplement à éliminer les relations de classe parallèle.

Afin de mesurer l'apport de l'algèbre d'intervalles au multimédia, nous commençons d'abord par la comparer avec l'algèbre d'instants. Le tableau de la Fig 3 indique que chaque relation primitive à base d'intervalles est équivalente à plusieurs relations d'instants. Il est alors légitime de se demander s'il en est de même pour les relations composées ou disjonctives à base d'intervalles. Auquel cas, ces deux représentations seraient équivalentes [VAN 90]. Le tableau de la figure Fig 4 donne un résumé du nombre de relations disjonctives de IA qui peuvent être générées à partir d'un sous-ensemble des relations composées de PA.
Relations à base d'instants de PA Nombre de disjonctions de IA pouvant être générées 
<, =, > 13
<, =, >, ? 29
<=, <, =, >, >=, ? 82
<=, <, =, >, >=, ?, =/= 187

Fig 4. Relations disjonctives de IA engendrées par les relations de PA

La dernière ligne montre que seules 187 relations sont exprimables à partir des relations à base d'instants : c'est l'algèbre d'intervalles restreinte qu'on notera RIA (Restricted Interval Algebra). Ce fait témoigne de la plus grande richesse des relations de IA par rapport à celle de PA. Sur les 8192-187 = 8004 relations non exprimables moyennant PA, il existe plusieurs relations qui peuvent être utiles dans un scénario multimédia. En particulier, la relation A {b, bi, m, mi} B qui dénote l'exclusion mutuelle entre deux intervalles. Cette relation peut être utilisée pour traduire l'impossibilité de présenter A et B en même temps. Par exemple, si ces derniers nécessitent la même ressource matérielle (carte de décompression, haut-parleur, etc.).

Notons que les relations d'instants jugées utiles pour le multimédia dans PA engendrent uniquement 29 relations d'IA (deuxième ligne du tableau Fig 4 ). Plusieurs auteurs [MIN 96][WAH 94][SEN 96] les retiennent d'ailleurs comme une référence pour mesurer l'expressivité d'un langage de synchronisation temporelle multimédianote4.

[Table des matières]

3.2.3 Choix entre algèbres d'intervalles et d'instants

Dans le cadre des systèmes d'édition de documents multimédia, plusieurs arguments plaident en faveur d'une spécification des documents multimédia à base d'intervalles : En revanche, la représentation à base d'instants fournit un très bon support d'exécution pour la présentation. En effet, on peut considérer que l'état du système de présentation ne change pas de façon continue dans le temps mais évolue lors de l'apparition d'événements discrets (on parle de Système Dynamique à Événements Discrets (SDED) [SEN 96]). Dans ce cas, la représentation d'un scénario à base d'instants permet de manipuler une structure interne de type graphe, qui peut être exploitée comme une description des tâches à ordonnancer lors de la présentation.

[Table des matières]

3.3 Expression des relations et langage temporel multimédia

Après avoir présenté et analysé la nature des relations temporelles, nous nous proposons dans cette section d'étudier la capacité des deux langages temporels à modéliser un scénario multimédia. Cela revient à poser la question : est-ce que la sémantique attachée à ces relations est suffisante pour traduire tous les schémas de synchronisation multimédia ?

Afin de répondre à cette question, il est nécessaire d'analyser les différents besoins qui apparaissent lorsqu'on cherche à spécifier un scénario multimédia. Notre analyse nous a conduit à séparer trois types de besoins :

En ce qui concerne les informations causales, il est nécessaire dans certains cas de pouvoir exprimer des scénarios dans lesquels l'occurrence d'un instant de fin d'un élément provoque l'arrêt d'un autre, même si ce dernier n'a pas restitué tout son contenu à l'utilisateur. Pour le cas d'une représentation à base d'intervalles, nous avons identifié trois relations pertinentes de ce type : À titre d'exemple, dans un scénario composé d'une séquence vidéo et d'une séquence musicale, si l'auteur souhaite que ces deux éléments se terminent en même temps même s'ils ont des durées différentes, il lui suffit d'introduire la relation Parmin(audio, vidéo). Cette relation ne peut être exprimée ni par l'algèbre d'instants, ni par l'algèbre d'intervalles. Si ces algèbres permettent de construire des scénarios non interactifs, les relations causales permettent d'intégrer une certaine forme d'interactivité. Par exemple, si l'auteur souhaite décrire un scénario où l'activation d'un bouton permet l'interruption d'une vidéo, il lui suffit d'introduire la relation suivante : Parmaster(Boutonm, vidéo).

[Table des matières]

4 Analyse et synthèse de scénarios temporels

Les problèmes liés à la représentation et à la composition d'éléments multimédia ressemblent, sur beaucoup d'aspects, à des problèmes rencontrés dans d'autres domaines de l'informatique. Parmi ces domaines, les plus proches du multimédia et plus particulièrement de l'édition de documents, concernent la représentation et la gestion des connaissances temporelles [MEI 92], l'ordonnancement de tâches [MAC 85] et la planification [VID 95b]. Parmi ces travaux, l'algèbre d'intervalles d'Allen [ALL 83] et l'algèbre d'instants proposée par Kautz [KAU 91] ont beaucoup marqué la recherche en multimédia, en particulier en ce qui concerne l'expression des relations temporelles, comme nous l'avons présenté dans la section 3.2. En revanche, les travaux portant sur la synthèse et l'analyse des scénarios temporels, qui sont au coeur du processus d'édition, restent de nos jours encore très peu abordés. Pourtant beaucoup de travaux, dont ceux d'Allen [ALL 91] et Kautz [KAU 91], ont largement étudié ces deux aspects dans le cadre des systèmes temporels à base de contraintes. Dans la suite de ce chapitre, nous montrons qu'ils constituent un cadre pertinent pour aborder l'édition de documents multimédia.

Dans cette section, nous étudions les fondements théoriques des modèles temporels basés sur les contraintes. Cette étude, qui constitue l'originalité de notre démarche, place le problème de l'édition multimédia comme un cas particulier appartenant à une classe de problèmes plus généraux appelés CSP (Constraint Satisfaction Problem).

[Table des matières]

4.1 Introduction aux CSP

Dans le domaine des CSP, la notion de contrainte désigne un énoncé déclaratif exprimant une mise en relation entre les données d'un problème. Une contrainte constitue donc un élément de représentation de la connaissance relative à un problème. Un système de gestion de contraintes est l'outil qui permet d'une part d'exprimer dans un formalisme déclaratif les contraintes qui décrivent un problème, et qui fournit d'autre part des algorithmes d'analyse et de synthèse capables de déterminer sa cohérence et de le résoudre s'il admet une solution. L'approche fondée sur les contraintes allie donc expression du problème (aspect langage) et techniques algorithmiques de résolution (gestion des contraintes). Justement, ces deux éléments correspondent parfaitement aux besoins d'édition que nous visons.

Un CSP est défini par la donnée d'un ensemble de variables, chacune associée à un domaine de valeurs, et par la donnée d'un ensemble de contraintes liant ces variables. Une contrainte est généralement décrite par l'ensemble de combinaisons de valeurs qui la satisfont. Une solution d'un CSP est une instantiation de ces variables qui satisfait simultanément toutes les contraintes d'un problème. Nous nous intéressons par la suite uniquement aux CSP binaires, c'est-à-dire ne manipulant que des contraintes entre deux variables.

Formellement, un problème de satisfaction de contraintes binaires P = (X, D, C, R) est défini par :

Une solution sigma d'un tel CSP est définie par : sigma = {x1 in D1, ...,xn in Dn} / forall Ci,j in C, (xi, xj) in Ri,j

Un CSP est cohérent si et seulement si il existe au moins une solution qui le satisfait.

On peut associer à tout CSP binaire un réseau où les sommets sont les variables et les arcs représentent les contraintes étiquetés par les domaines des variables. On qualifie de minimal un tel réseau lorsque les domaines des variables sont restreints aux seules valeurs appartenant à au moins une solution.

Dans le domaine du multimédia, les mérites que nous attribuons à une approche fondée sur les contraintes peuvent être résumés ainsi :

  1. Elle permet une description formelle de la synchronisation temporelle des documents multimédia.
  2. Elle permet une expression déclarative de la synchronisation temporelle. Ce type d'expression rend possible la construction de langages de synchronisation plus faciles à utiliser que les langages impératifs comme les scripts.
  3. Elle permet à l'auteur d'un document de se focaliser sur l'édition d'un document (la formulation de ce qu'il veut obtenir) sans se préoccuper de la façon dont il va l'obtenir (la résolution ou le formatage).
Dans cette section, nous établissons le lien qui existe entre le problème de synchronisation d'un document multimédia et les systèmes de contraintes CSP. Nous commençons d'abord par un rappel des principales définitions relatives à la théorie des CSP. Ces définitions nous seront utiles lorsque nous aborderons les techniques de vérification de la cohérence d'un scénario et de recherche de solutions qui sont présentées dans les sections 4.3 et 4.4.

[Table des matières]

4.2 TCSP : les CSP temporels

La synchronisation temporelle multimédia peut être abordée dans le cadre d'une classe particulière des CSP désignée par TCSP (Temporal Constraints Satisfaction Problem). Dans cette classe, les variables modélisent des instants ou des intervalles temporels de durée, et les relations leurs placements relatifs à travers le temps. Il existe deux grandes familles de techniques permettant de gérer les contraintes temporelles : En réalité, ces deux types de représentation sont nécessaires dans les systèmes multimédia, car dans un processus d'édition, l'auteur peut vouloir exprimer des relations de synchronisation sous forme symbolique, mais leurs conséquences dans le scénario peuvent se traduire sous forme de contraintes numériques. Ces mêmes contraintes peuvent à leur tour limiter les relations symboliques que l'auteur peut vouloir ajouter. Ceci explique la difficulté du problème de synchronisation des documents multimédia qui combine ces deux types de représentation.

[Table des matières]

4.3 Gestion symbolique des relations temporelles

La gestion symbolique des contraintes temporelles, introduit par Allen, s'appuie sur l'organisation des relations sous forme d'un graphe temporel. Les sommets sont des symboles qui représentent des intervalles, et les arcs sont des relations temporelles disjonctives d'IA (voir section 3.2.2).

La gestion symbolique des relations (analyse et synthèse) consiste à appliquer un mécanisme qui s'apparente à une activité de déduction. Ces déductions aboutissent au retrait de certaines disjonctions des relations du graphe, ce qui revient à les préciser. C'est cette caractéristique qui nous fait donner le nom de symbolique à ce type de système, par opposition aux systèmes numériques dont la gestion porte sur des contraintes numériques (domaines de validité des intervalles).

Pour les deux types de relations à base d'instants où d'intervalles, nous nous intéressons aux deux aspects suivants :

Nous allons d'abord présenter ces deux types de langage permettant l'expression des contraintes temporelles. En particulier, nous décrivons les mécanismes de composition qui leur sont associés ainsi que les avantages ou les inconvénients de gérer un document multimédia en adoptant l'une ou l'autre des deux méthodes.

[Table des matières]

4.3.1 Loi de composition temporelle

Dans les deux algèbres d'instants et d'intervalles, chaque relation de 2B (l'ensemble des relations composées) est inversible et son inverse est une relation de 2B ; par exemple, x before y est l'inverse de y before x dans l'algèbre d'intervalles. Pour chaque relation x R y de l'ensemble 2B entre deux éléments temporels x et y, on définit la relation inverse notée y R-1 x.

Pour permettre de combiner des connaissances temporelles exprimées par de telles relations, deux opérations sont définies sur les éléments de l'ensemble 2B :

On définit également une loi de composition interne @, associative, non commutative d'élément absorbant ? Son élément neutre est l'égalité (= dans PA et equals dans IA). Si R1 et R2 sont deux relations de 2B, nous obtenons une nouvelle relation R3(x, z) = R1(x, y) @ R2(y, z) qui fait aussi partie de 2B. Cette loi permet d'inférer, à partir de la relation R1(x, y) et R2 (y, z) la relation R1 @ R2(x, z).

Les trois opérations, @, intersect et union sont deux à deux distributives. Qu'il s'agisse d'instants ou d'intervalles { 2B, union, @ } est une structure d'algèbre. C'est pour cette raison qu'on parle d'algèbre d'instants ou d'algèbre d'intervalles.

[Table des matières]

4.3.2 Composition dans l'algèbre d'instants

La loi de composition @ s'applique de la façon suivante dans PA. Par exemple, si nous avons trois instants temporels x, y et z avec les relations x < y et y = z, on déduit la nouvelle relation x < z (voir le tableau de la Fig 5 ).
@ < = >
< < < ?
= < = >
> ? > >
Fig 5. Loi de composition de PA pour les relations primitives

En utilisant la distributivité de @, le même tableau peut être utilisé pour les relations de 2B. Par exemple, à partir des deux relations : x {<, =} y et y {<, =} z, on déduit :

x [ {<, =} @ {<, =} ] z = x [ (<@<) union (<@=) union (=@<) union (=@=) ] z

= x [ < union < union < union = ] z

= x [{<, =}] z

Ainsi, si l'auteur d'un document veut exprimer un scénario temporel multimédia moyennant l'algèbre d'instants, il construit une base d'instants temporels qui correspondent aux différents événements du scénario. Ensuite, il les relie temporellement en spécifiant des relations entre eux.

Par exemple, supposons que dans l'exemple de déduction ci-dessus, l'événement x corresponde au début d'une vidéo, y au début d'un élément audio et z au début d'un élément texte. Nous avons montré à travers l'exemple précédent qu'une application de la loi de composition entre les relations interdit d'introduire la relation x > z, au risque de rendre le scénario incohérent.

[Table des matières]

4.3.3 Composition avec l'algèbre d'intervalles

Pour faire de la vérification de cohérence, Allen suggère [ALL 83] l'utilisation des lois de composition appliquées aux intervalles afin d'exprimer un scénario temporel et de raisonner à son propos. L'expression d'une relation de synchronisation qui lie un élément temporel à un autre est alors simplement traduite sous forme de relation symbolique entre les deux éléments.
Image exemple41.gif
Fig 6. Graphe de contraintes de l'exemple 1

Exemple 1 : Soient trois éléments multimédia x, y et z. Supposons que l'auteur d'un scénario veut exprimer les contraintes temporelles suivantes (voir Fig 6 ) :

Comme pour l'algèbre de points, le pouvoir de déduction du système d'Allen repose sur l'établissement d'une table de transitivité 7x 7 (voir Fig 7 ) entre les relations primitives, permettant de calculer R3 dans la formule :

x R1 y @ y R2 z Rightarrow x R3 z

En général, la relation R3 est disjonctive, car la connaissance de R1 et de R2 ne donne pas toujours assez d'information pour que R3 soit suffisamment précise.

Lorsque R1 et R2 sont elles-mêmes disjonctives, l'algorithme de calcul de R3 est très simple :

  1. Décomposer R1 et R2 en une disjonction de relations élémentaires.
  2. Développer tous les termes en appliquant la distributivité de intersect par rapport à union. On obtient ainsi des clauses qui sont des paires conjonctives.
  3. Calculer grâce à la table de la Fig 7 le résultat de chaque paire conjonctive.
  4. Les conjonctions ayant disparu, composer les clauses disjonctives en une seule relation composée.
R1 @ R2
b
m
s
f
d
o
e
b
b
b
b
b
b,m,s,d,o
b
e
m
b
b
m
b,m,s,d,o
s,d,o
b
b
s
b
b
s
d
d
b,m,o
m
f
b
m
d
f
d
s,d,o
s
d
b
b
d
d
d
b,m,s,d,o
f
o
b
b
o
s,d,o
s,d,o
b,m,o
d
e
b
m
s
f
d
o
o
Fig 7. Loi de composition d'IA

L'algorithme proposé par Allen permet la détection d'incohérences temporelles. Son principe est le suivant : à partir de la table de transitivité ci-dessus, on calcule toutes les relations induites et on les confronte aux relations existantes, ceci permet d'obtenir des relations déduites, plus précises. L'algorithme propage ces relations par application d'une autre transitivité et ainsi de suite jusqu'au repos.

Ce principe s'applique pour les deux types de relations, d'instants ou d'intervalles. Dans les deux cas, le problème est représenté sous forme d'un graphe (S, R) où S={Xi,...,Xj} est l'ensemble des variables et Ri,j est l'ensemble des contraintes entre les variables X i et Xj. L'algorithme nécessite un graphe complet : les arcs entre variables qui ne sont liées initialement par aucune relation sont étiquetées par la relation ?


Initialisation : Pour i, j in [1, n], i =/= j :

Q <== {i, j} Q est la pile des relations en cours de propagation

Propagation : Tant que Q =/= emptyset

1) {i, j} <== dépiler(Q) On considère un arc

2) Pour k in [1, n], k =/= i, j

- On calcule l'influence de l'arc courant sur les autres arcs R'ik<== ( Rij @ Rjk ) intersect Rik R'kj<== ( Rki @ Rij ) intersect Rkj

- Si R'ik ou R'kj = bot Alors STOP nous avons détecté une incohérence

- Si la nouvelle relation diffère de l'ancienne, il faut la propager Si R'ik =/= Rik Alors empiler {i, k} dans Q; Rik <== R'ik Si R'kj =/= Rkj Alors empiler {j, k} dans Q; Rkj <== R'kj


Cet algorithme permet de préciser de plus en plus le graphe en éliminant des disjonctions. Étant donné que le nombre de relations et la taille du graphe sont finis, et que ce graphe est borné inférieurement par le graphe minimal, l'algorithme s'arrête toujours : soit parce qu'il n'y a plus de relations apportant une information nouvelle, soit parce qu'une relation composée devient vide, auquel cas on a détecté l'incohérence du scénario.

L'application de cet algorithme à l'exemple 1 aboutit à la suppression de trois relations incohérentes (voir les relations barrées de la Fig 8 ). Cette méthode d'analyse a été proposée pour les documents multimédia par Kshirasagar [KSH 94].

Image exemple42.gif
Fig 8. Graphe minimal et scénario cohérent pour l'exemple 1

[Table des matières]

4.3.4 Discussion

L'approche proposée par Allen [ALL 83] constitue le principal travail accompli dans le cadre de la résolution d'un TCSP symbolique. Cet algorithme, polynômial, n'est malheureusement pas complet. En effet, Vilain et Kautz [VIL 86] ont montré que l'algorithme d'Allen pouvait ne pas détecter certaines incohérences et que le problème d'existence d'une solution dans IA est NP-complet. Ce qui signifie que, pour rechercher une solution, il faut utiliser des méthodes de recherche exhaustives. Ces techniques, même appliquées à des problèmes de petite taille, restent pour le cas des systèmes multimédia coûteuses car elles sont de complexité exponentielle.

En conclusion, si le modèle proposé par Allen permet une représentation plus riche que la représentation à base d'instants, c'est au prix de l'incomplétude et d'un accroissement important de la complexité algorithmique.

[Table des matières]

4.4 Gestion numérique des relations temporelles

Contrairement à l'approche symbolique, les systèmes numériques manipulent explicitement des nombresnote5, ce qui leur permet de couvrir l'aspect métrique du temps. Le modèle précédent représente et traite le temps uniquement à travers une représentation symbolique (traitement qualitatif). Cette représentation bien que très utile pour l'édition ne prend pas en compte des informations numériques. En particulier, dans la construction d'un scénario, on peut être intéressé par les trois opérations suivantes : [Table des matières]

4.4.1 Réseaux de contraintes numériques TCSP et STP

Les contraintes temporelles liées aux domaines de validité et aux relations temporelles symboliques peuvent s'exprimer sous forme de différences bornées entre dates d'instants. En partant de cette constatation, Dechter et Meiri [DEC 91] proposent de représenter les problèmes temporels sous forme de TCSP numériques.

Un TCSP numérique est défini par un ensemble de variables X1, .., Xn représentant des instants ayant des valeurs de dates dans aleph, et un ensemble de contraintes binaires. Une contrainte Ci,j entre les variables Xi et Xj, est une disjonction de différences bornées du type :

a1i,j <= Xi -Xj <= b1i,j wedge ... wedge ani,j <= Xi -Xj <= bni,j

Par conséquent, une contrainte Ci,j définit un ensemble d'intervalles de validité {I1i,j, ..., In i,j} où Ik i,j = [aki,j, bki,j ]. Un élément multimédia peut donc être modélisé dans ce formalisme par une union de domaines de validité. En fait, le seul cas de TCSP qui peut être résolu en temps polynômial est celui d'un TCSP ne comportant qu'un intervalle par arc (le problème STP : Simple Temporal Problem). Cela correspond à la modélisation de chaque élément multimédia par un seul domaine de validité. Pour cette raison, nous allons nous restreindre dans la suite de cette étude aux cas des STP.

Le problème de satisfaction de contraintes se présente dans les STP par un graphe conjonctif de différences bornées. Dans ce type de graphe, chaque arc reliant deux instants temporels i et j est étiqueté par des bornes [aij , bij] et indique la présence d'une contrainte de distance entre i et j :

aij <= Xi -Xj <= bij

Cette contrainte peut aussi être décrite par une paire d'inégalités :

Xi -Xj <= bij

et Xi -Xj <= -aij

Chaque contrainte Cj, i d'un sommet j à un sommet i peut être retrouvée à partir de Ci, j : Cj, i = [-bij , -aij], en général une seule de ces contraintes est représentée dans le graphe. De plus, un instant particulier, défini par le sommet 0 et la variable X0 est ajouté au graphe pour représenter le début du scénario. Toutes les valeurs Xi sont définies par rapport à X0 et chaque contrainte C0, i représente la contrainte de distance par rapport au début du scénario, on notera cette contrainte Ci et on considère pour des raison de simplicité que X0 = 0.

En conséquence, la résolution d'un problème STP revient à la résolution d'un problème décrit par ensemble d'inéquations linéaires sur les variables X0, ..., Xn.

[Table des matières]

4.4.2 Systèmes utilisant la programmation linéaire

Le problème de résolution d'un système linéaire d'inégalités est bien connu dans le domaine de la recherche opérationnelle. Il peut en effet être résolu en temps exponentiel moyennant l'algorithme du simplex [DAN 62] ou par l'algorithme de Khachiyan [KHA 79]. L'algorithme du simplex optimise n'importe quelle fonction linéaire sur un domaine exprimé au moyen de contraintes linéaires. Dans le problème d'analyse d'un scénario, il n'y a a priori pas de fonction à optimiser. On cherche seulement à définir les domaines de validité des éléments multimédia pour le scénario en construction. Par contre, pour le formatage on peut toujours considérer qu'une solution qui s'écarte le moins possible des valeurs optimales des éléments est celle qu'il faut rechercher en priorité. Dans ce cas, il est possible de définir une fonction coût, à minimiser, qui permet de guider le choix de la solution. S'il n'existe pas de solution, l'ensemble de contraintes est incohérent. De plus, on a toujours "sous la main" une solution totalement explicitée, mais les domaines des variables eux ne sont pas explicites. Par conséquent, l'auteur ne sait pas dans quelle mesure les valeurs des variables dans la solution exhibée sont modifiables tout en restant une solution au problème.

Ce genre de méthodes permet d'utiliser toute la puissance de représentation de l'algèbre linéaire. Un point révélateur est que les contraintes sont rarement présentées du point de vue d'un graphe temporel. De plus, on ne peut pas vraiment considérer le simplex comme une méthode d'analyse de scénarios, dans la mesure où l'algorithme ne fait qu'exhiber une solution. Dans le cas d'incohérence, l'algorithme rejette en bloc l'ensemble des contraintes, ce qui empêche l'auteur de localiser avec précision la source de l'incohérence.

Quant à la complexité de cette méthode, elle est fortement alourdie par le coût théoriquement exponentiel de l'algorithme du simplex, qu'il faut faire fonctionner chaque fois que l'on ajoute une contrainte (il n'est pas incrémental). C'est cette solution qui a été adoptée dans les deux seuls systèmes multimédia ayant implanté un module de recherche automatique de solution ou formateur temporel multimédia : Firefly [BUC 93] et plus récemment Isis [KIM 95].

[Table des matières]

4.4.3 Systèmes basés sur les réseaux de contraintes

Nous avons vu que non seulement les relations temporelles s'expriment de façon linéaire, mais aussi que les intervalles de validité peuvent être représentés de la même façon (inégalités sur la distance entre instants de début et fin). Les approches reposant sur les réseaux de contraintes partent du constat que les STP admettent des solutions plus efficaces que celles présentées dans la section précédente : les inéquations représentant les contraintes temporelles sont structurées sous forme d'un graphe auquel une algorithmique de graphe peut être appliquée.

Formellement, à chaque problème STP est associé un graphe étiqueté orienté appelé graphe de distance :


Définition 1 : Un graphe de distance temporelle Gd = (V, Ed) est défini par un ensemble de sommets 0, .., n représentant des variables V = {X0, ..., Xn} et un ensemble d'arcs Ed, où chaque arc Xi ==> Xj relie deux sommets distincts Xi et Xj du graphe. Chaque arc est étiqueté par une valeur entière. Si [ai,j,bi,j] est l'intervalle de validité associé à la distance entre Xi et Xj, alors l'arc Xi ==> Xj est étiqueté par bi,j et l'arc Xj ==> Xi est étiqueté par -ai,j.


Chaque chemin d'un sommet i à un sommet j dans le graphe Gd, i = i0, ..., ik = j, introduit la contrainte temporelle suivante sur la distance Xj - Xi :
Xi -Xj <=Sj = 1kaij-1, ij

S'il existe plus d'un chemin de i à j, alors il est facile de vérifier que l'intersection de toutes les contraintes de chemins donne :

Xj - Xi <= dij

Où dij représente la durée du plus court chemin entre i et j. En se basant sur cette observation, la condition fondamentale suivante pour la cohérence d'un problème STP peut être établie :


Théorème : (Shostak [SHO 81], Liao et Wong [LIA 93], Leiserson et Saxe [LEI 93]) Un STP est cohérent si et seulement si son graphe de distance Gd ne contient pas de cycle négatifs.


Preuve : Supposons qu'il existe un chemin négatif C formé des sommets i1, i2, ..., ik=i1. La somme des inégalités le long du chemin C donne :

Xi1 - Xi1 < 0, qui ne peut évidemment pas être satisfaite.

Dans l'autre sens de l'équivalence, s'il n'existe aucun cycle négatif dans Gd, alors le plus court chemin entre chaque paire de sommets est bien défini. Pour chaque paire de sommets i et j, le plus court chemins satisfait d0j <= aij + d0i ; d'où,

d0j - d0i <= aij

Donc le tuple (d01 , ... , d0n) est une solution du STP.

Corrolaire : Soit Gd le graphe de distance d'un STP cohérent. Il existe aux moins deux scénarios cohérents qui sont :

S1 = (d01 , ... , d0n) et S2 = (-d10 , ... , -dn0)

Ces deux scénarios représentent une instantiation des variables à leur date d'occurrence au plus tôt et au plus tard respectivement.

Deux problèmes STP sont dits équivalents s'ils représentant le même ensemble de solutions, et un STP est dit minimal s'il n'existe aucun STP équivalent dont les contraintes soient plus restrictives.

Algorithmes utilisant les graphes

Le graphe de distance d'un STP peut être construit en appliquant l'algorithme du plus court chemin (all pairs shortest paths) de Floyd-Warshal [PAP 82]. Cet algorithme peut être considéré comme un algorithme de relaxation : à chaque pas la valeur d'un arc est mise à jour d'un montant qui dépend uniquement de celles des arcs adjacents.


Algorithme du plus court chemin

1. Pour i := 1 à n faire dii <== 0

2. Pour i, j := 1 à n faire dij <== aij

3. Pour k := 1 à n faire

4. Pour i, j := 1 à n faire

5. dij <== min {dij, dik + dkj }


Fig 9. Algorithme all pairs shortest paths

L'algorithme s'exécute en O(n3) et détecte les cycles négatifs simplement en examinant le signe des éléments diagonaux dii.

Considérons l'exemple de la Fig 10 , puisqu'il n'y a pas de cycle négatif, le STP correspondant est cohérent. Les plus courts chemins dij sont présentés dans le tableau suivant :
Image GrapheDistance.gif
0 1 2 3 4
0 0 20 50 30 70
1 -10 0 40 20 60
2 -40 -30 0 -10 30
3 -20 -10 20 0 50
4 -60 -50 -20 -40 0
 

Fig 10. Longueur des chemins les plus courts de l'exemple

L'algorithme de Floyd-Warshal constitue ainsi un algorithme polynômial pour déterminer la cohérence du STP et le calcul des domaines de validité minimaux et donc le graphe minimal. Une fois que ce graphe est disponible, l'instantiation d'une solution ou le formatage temporel peut prendre O(n2), car chaque instantiation d'une valeur doit être conforme aux instantiations précédentes et ne sera plus modifiée ultérieurement (cf. section 4.4.4).

Algorithmes manipulant explicitement les domaines de validité

Cette classe d'algorithmes est très proche d'une formalisation du type étiquetage cohérent du graphe introduit par Allen (sans que leurs concepteurs n'en fassent mention toutefois). Les variables sont les arcs du graphe qui représentent les domaines de validité des intervalles contrairement au cas d'Allen où elles représentaient des relations et à l'algorithme de Floyd-Warshal où les étiquettes représentaient des entiers relatifs. En réalité, il existe toute une famille d'algorithmes de ce type développés dans le cadre des systèmes à base de contraintes [MEI 92] [VID 95b]. Dans cette étude, nous allons seulement en présenter un, appelé PC-2 [MAC 85], qui est représentatif de cette classe d'algorithmes et qui permet d'illustrer leur principe de fonctionnement.


Algorithme PC-2 ( Macworth [MAC 85])

1. Initialisation

2. Q <== Graphe initial

3. Propagation

4. Tant que Q =/= emptyset Faire

5. 1) extraire un élément de {i, j} <== Q

6. 2) Pour k = 1 à n, k =/= i, j Faire

7. D'ik <== Dij @ Djk + Dik

8. D'kj <== Dki @ Dij + Dkj

9. - Si D'ik ou D'kj = bot Alors Stop : une incohérence a été détectée

10. - Si D'ik =/= Dik Alors empiler {i, k} dans Q ; Dik <== D'ik

11. - Si D'kj =/= Dkj Alors empiler {j, k} dans Q ; Dkj <== D'kj


Fig 11. L'algorithme PC-2

Dans PC-2, la vérification de la cohérence du graphe se fait en même temps que le calcul du graphe minimal. Le graphe minimal est obtenu en appliquant des opérations algébriques sur les domaines de validité. Ces opérations permettent à chaque étape d'éliminer les valeurs impossibles d'un domaine de validité. Soient deux domaines de validité : D1 = [d1min, d1max] et D2 = [d2min, d2max]. On définit les deux opérations suivantes :

À l'échelle du graphe tout entier, une modification d'un domaine de validité peut donc en entraîner une autre. On propage donc ces modifications jusqu'à ce que le réseau soit au repos, ou que l'on détecte une incohérence.

La complexité de l'algorithme PC-2 est cubique O(n3). PC-2 possède une propriété intéressante qui consiste à réexaminer le graphe localement d'abord. En effet, il arrive souvent que l'insertion d'un élément ou d'une relation n'affecte qu'une portion limitée du graphe, auquel cas, il n'est pas utile de le remettre en cause dans sa totalité (voir les lignes 10-11 de l'algorithme qui permettent d'anticiper dans ces cas l'arrêt de l'algorithme), contrairement à l'algorithme de Floyd-Warshal où chaque modification nécessite de reconsidérer tout le graphe.

[Table des matières]

4.4.4 Décomposabilité d'un STP

A partir de la discussion précédente, nous avons établi que la spécification d'un scénario peut se ramener au maintien de la structure d'un graphe. Ce graphe est une représentation plus explicite, puisqu'il ne retient que les domaines de validité susceptibles de figurer dans une solution.

Étant donné un graphe cohérent, la présentation du scénario correspondant nécessite le choix d'une solution spécifique parmi celles qui sont possibles : c'est l'opération de synthèse ou formatage. Les problèmes STP possèdent une propriété importante permettant la recherche efficace d'une solution : la décomposabilité. Un réseau de contraintes STP est dit décomposable si chaque instantiation d'une valeur de durée pour un élément n'est jamais remise en cause lors du choix des valeurs des durées des autres éléments du scénario.

Le théorème proposé par Meiri établit que tout réseau de contraintes STP est décomposable. C'est un résultat fondamental sur lequel repose notre mise en oeuvre.


Théorème de décomposabilitié (Meiri [MEI 92]) : Tout problème STP est décomposable par rapport aux contraintes décrites par son graphe minimal de distance.


Preuve : Il suffit de montrer qu'une instantiation quelconque d'un sous-ensemble S de k variables qui représentent des dates d'instants (1 <= k < n) et qui satisfait tous les plus courts chemins appliqués à S est extensible à n'importe quelle autre variable. On procède par induction sur midSmid= k.

Pour midSmid=1, S consiste à instancier une variable unique Xi = xi. Pour n'importe quelle variable Xj, nous devons montrer qu'il est possible de trouver une valeur Xj = v qui satisfait les contraintes du plus court chemin entre ces deux variables. La valeur v doit satisfaire :

-dji <= v - xi <= dij (1)

Puisque tous les cycles du graphe de distance sont non-négatifs, nous avons :

dji + dij >= 0

Donc, il existe au moins une valeur v qui satisfait (1)

Pour midSmid = k, supposons que le théorème est vrai pour midSmid= k-1, et montrons qu'il reste vrai pour midSmid= k : soit S = {X1, ..., Xk} et soit {Xi = xi | 1 <= i <= k } des instantiations qui satisfont les contraintes des plus courts chemins entre les variables de S. Soit Xk+1not in S. Nous devons trouver une valeur Xk+1= v qui satisfait les contraintes des plus courts chemins entre Xk+1 et toutes les variables de S. La valeur v doit donc satisfaire :

v - xi <= di, k+1

xi - v <= d k+1, i

Pour =1, ..., k ou encore

v <= min{ xi+ di, k+1 | 1 <= i <= k },

v >= max{ xi+ dk+1, i | 1 <= i <= k },

Supposons que le minimum est atteint à i0 et le maximum à j0. En conséquence, v doit satisfaire :

xj0 - d k+1, j0 <= v <= xi0 + d i0, k+1 (2)

Puisque xi0 et xj0 satisfont les contraintes du plus court chemin, nous avons :

xj0 - xi0 <= d i0, j0

xj0 - d k+1, j0 <= v <= xi0 + d i0, k+1

Ceci ,avec di0, j0 <= d i0, k+1 + d k+1, j0 donne :

xj0 - d k+1, j0 <= xi0 + d i0, k+1

Donc, il existe bien une valeur v qui satisfait les conditions de (2)

L'importance de la propriété de décomposabilité pour le multimédia est double :

Ce résultat peut avoir des implications importantes sur l'organisation d'une application de présentation multimédia. En effet, un STP étant décomposable, l'opération de formatage (en particulier la politique adoptée pour réaliser le formatage) peut être effectuée aussi bien à l'édition que pendant l'exécution de la présentation (formatage dynamique). Cette possibilité est particulièrement intéressante pour des systèmes qui permettent de produire dynamiquement des parties de scénarios [DAL 96].

[Table des matières]

4.5 Synthèse des techniques multimédia existantes

À la différence des systèmes présentés dans le chapitre précédent où il s'agissait de décrire les caractéristiques fonctionnelles des outils d'édition, nous évaluons dans cette section les modèles temporels qui sont proposés pour les documents multimédia. Cette évaluation est basée sur un ensemble de critères introduits dans les sections précédentes comme la représentation de l'unité temporelle de base, le type de relations temporelles utilisées, leur sémantique (qualitative, quantitative, causale) et la structure des scénario considérés. À ces critères, nous ajoutons les suivants, qui sont à prendre en compte aussi bien dans la phase d'édition que dans la phase de présentation :
Modèle temporel Timeline Höpner & AHM OCPN Firefly & Isis
Technique de représentation Axe de temps absolu Expressions de parcours Réseau de Pétri Réseau de points
Représentation de l'unité temporelle de base instant intervalle intervalle instant
Expression des relations Implicite (datation) Séquence & Parmin & Parmax 13 IA 3 PA
Sémantique des relations quantitative causale qualitative qualitative quantitative
Structure du scénario Non Arbre Arbre Graphe
Analyse : Cohérence Domaines valides -note6 - Non - Non Oui Oui Non
Synthèse (formatage) - - Non Simplex
Performances - - - Très faibles
Incrémentalité Oui Oui Non Non
Indéterminisme vs Flexibilité Non Non Non Non
Fig 12. Évaluation des principaux modèles de synchronisation multimédia

Les modèles proposés n'abordent, comme le montre le tableau de la Fig 12 , qu'une partie des problèmes posés. La complexité de conception d'un système d'édition multimédia complet apparaît clairement dans la diversité des aspects mis en avant. En particulier, les méthodes de construction d'un document, de vérification de la cohérence et de formatage temporel s'adaptent peu à un processus interactif d'édition.

[Table des matières]

5 Conclusion

Dans ce chapitre, nous avons présenté les principaux aspects liés à la modélisation des documents multimédia. En partant d'une modélisation des éléments par des intervalles de validité et d'une étude des relations multimédia, nous avons montré que le problème de spécification d'un scénario multimédia peut se ramener à un système de contraintes de type STP. Les STP qui reposent sur l'algèbre d'instants ou, ce qui revient au même, sur l'algèbre d'intervalles restreinte, semblent être le meilleur compromis entre efficacité et pouvoir de représentation.

L'approche fondée sur les contraintes est attrayante sur plus d'un aspect. En effet, elle apporte des techniques de vérification de la cohérence et d'analyse d'un scénario adaptées pour le traitement de l'aspect qualitatif et quantitatif du temps. Le formatage (ou la recherche de solution) se trouve aussi simplifié grâce à la propriété de décomposabilité. Il reste cependant plusieurs questions en suspend qui ne sont pas abordées et que nous allons tenter de compléter dans la suite. Ces questions concernent principalement :

Notes :

(1)

On parle aussi d'événements dans certains systèmes.
(2)

Nous reviendrons dans la section 4 sur la justification de ce terme d'algèbre.
(3)

Cette relation traduit l'impossibilité de relier temporellement deux instants : l'incohérence.
(4)

Nous renvoyons le lecteur à ces travaux pour une étude plus détaillée de ces 29 relations.
(5)

Dans notre cas, on s'intéresse uniquement à des nombres entiers
(6)

«-» désigne une information non précisée ou non considérée dans le modèle.