20.4 Formale Beschreibung multimedialer Anwendungen

Die Entwicklung interaktiver multimedialer Anwendungen (IMA) ist schwierig und teuer. Je größer und kompakter solche Projekte werden, desto unübersichtlicher und schwieriger gestalten sich die dabei entstehenden Probleme. Daher wird nach Möglichkeiten gesucht, das Verhalten von IMA's formal spezifizieren zu können. In den letzten Jahren wurden daher verschiedene Verfahren und Modelle entwickelt, die dieses Ziel verfolgen und sich dabei in zwei Klassen einteilen lassen. Auf der einen Seite stehen die prozessorientierten Modelle und auf der anderen Seite die spezifikationsorientierten Modelle.

Bei den prozessorientierten Modellen wird ein ganzer Prozeß in viele Teilprozesse aufgegliedert. Dann wird jeder Teilprozeß durch ein spezielles und leistungsstarkes Tool implementiert. Bei den spezifikationsorientierten Modellen wird hingegen angegeben, wann und wo ein Objekt erscheint und wann es gestartet und beendet wird. Hier sollen nun zwei Vertreter der zweiten Klasse näher betrachtet werden.

Dabei handelt es sich zum einen um das von Little und Ghafoor entwickelte Object Composition Petri Net und zum anderen um das von Milner entwickelte Calculus of Communcation Systems.

Ein weiteres Model, welches sich nicht in eines der beiden Klassifizierungen einordnen läßt, ist das Model der Statecharts. Dieses soll zunächst betrachtet werden, da es zur Modellierung eines Teilbereiches von IMA´s dient, nämlich dem Hypertext.

20.4.1 Statecharts

Statecharts stellen ein formales graphisches Model dar, um hierarchische Kompositionsstrukturen und die Browsing-Semantik von Hypertextdokumenten zu spezifizieren. Das Model unterstützt dabei 3 Forderungen:

Ein statechart besteht aus atomaren Zuständen (atomic states) und zusammengesetzten Zuständen (composed states). Zusammengesetzte Zustände entstehen durch die Verknüpfung von Unterzuständen (substates) durch AND- oder XOR-Verknüpfungen. Falls S einen Zustand darstellt, der aus einer XOR-Verknüpfung von verschiedenen Unterzuständen entsteht, dann bedeutet, daß man sich im Zustand S befindet, daß man sich in einem und nur in einem Unterzustand befinden kann. Falls S sich aus einer AND-Verknüpfung zusammensetzt, befindet man sich gleichzeitig in allen Unterzuständen.

**Abbildung:** XOR- und AND-Verknüpfung
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild1.PS} }\end{center}\end{figure}$

Transitionen können zwischen atomaren und zusammengesetzten Zuständen stattfinden (siehe Abbildung 20.17).

**Abbildung 20.17:** Transition
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild2.PS} }\end{center}\end{figure}$

Textuell wird dies beschrieben durch (S1,S2), wobei S1 und S2 atomar oder zusammengesetzt sein können.

Befindet sich das System im Zustand S1, würde der Trigger e1 das System vom Zustand S1 in den Zustand S2 überführen. Dabei würde die Transition die Ausgabe e2 erzeugen. Zustände können sich im externen oder internen Modus befinden. Nur wenn sich der Zustand in einem externen Modus befindet, kann er auf Trigger reagieren. Wird von einer Transition eine Ausgabe generiert, so bleibt der Zustand solange in einem internen Zustand bis diese Ausgabe komplett abgearbeitet wurde.

Statecharts ermöglichen die Modellierung von regierenden Systemen, die eventgesteuert oder getriggert sind, und die Effekte eines generierten Events geschehen gleichzeitig mit getriggerten Event.

20.4.1.1 Modellierung von Hypertext durch Statecharts

Anhand von zwei Beispielen soll die Modellierung erläutert werden. Abbildung 20.18 zeigt ein Statechart für das Öffnen und Schließen eines Fensters mit dem gleichen Button.

**Abbildung:** Öffnen und Schließen mit einem Button
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild3.PS} }\end{center}\end{figure}$

Der Status des Buttons Sb kann sich in den Unterzuständen SbcanOpenF2 oder SbcanCloseF2 befinden. SF2 kann sich in den Unterzuständen SF2closed oder Sbopened befinden. Zu Beginn befinde sich SDocument1 im Zustand [SbcanOpenF2, SF2closed]. Wird nun der Event bselect ausgelöst, wird der Event F2opened an SF2 geschickt und dort ausgeführt. Danach befindet SF2 dann im Zustand SF2opened befindet.

Ein weiteres Beispiel ist ein statechart für das Öffnen und Schließen eines Fensters mit zwei Buttons. Die Funktionsweise leitet sich ab aus dem Graphen (siehe Abbildung 20.19).

**Abbildung:** Öffnen und Schließen mit zwei Buttons
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild4.PS} }\end{center}\end{figure}$

20.4.2 Object Composition Petri Net (OCPN)

Das OCPN basiert auf den sogenannten Timed-Petri-Netzen und Zeitintervalle. Die Bedeutung der Zeitintervalle wird später erklärt. Zuerst sollen die Petri-Netze eingeführt werden.

20.4.2.1 Petri-Netze

Petri-Netze sind Modelle zur Beschreibung und Analyse von Abläufen mit nebenläufigen und nichtdeterministischen Vorgängen. Sie eignen sich zur Beschreibung von dynamischen Systemen mit einer festen Grundstruktur. Somit sind sie als Repräsentation von IMA's anwendbar, da IMA's eben diese Anforderungen erfüllen (abgesehen von den nicht-deterministischen Vorgängen)

Definitiom 1

Ein Tripel N=(S,T,F) heißt Netz oder Petri-Netz, falls gilt:

i) S= $\{s_{1},s_{2},\ldots,s_{n}\}$ und T= $\{t_{1},t_{2},...,t_{m}\}$ sind disjunkte Mengen

ii) F $\subseteq$ (SxT) $\cup$ (TxS) ist eine zweistellige Relation, die Flußrelation von N

Die Elemente aus S werden mit Stellen und die Elemente aus T mit Transitionen bezeichnet.

Eine Stelle entspricht einer Zwischenablage für Daten, eine Transition repräsentiert die Verarbeitung mit Daten. Ein Petri-Netz gibt eine feste Ablauf-Struktur wieder. Um dynamische Vorgänge darzustellen, werden Objekte auf die Stellen gelegt, die von den Transitionen weitergereicht werden. Dies führt zu den Marked-Petri-Netzen Nm = S,T,F,M. Hier werden durch eine Abbildung M : S $\longrightarrow$ I mit I=0,1,... jeder Stelle si im Netz Markierungen (token) zugewiesen.

Bein einfachen Petri-Netzen ist die Zeit zwischen der Ermöglichung des Schaltens und dem tatsächlichen Feuern nicht spezifiziert und nicht-deterministisch. Das Feuern einer Transition wird als augenblicklich und unverzögertes Ereignis vorausgesetzt.

Eine Weiterentwicklung der Marked-Petri-Netze stellt somit die Klasse der Timed-Petri-Netze dar, bei denen jeder Transition eine bestimmte Schaltdauer zugewiesen wird. Dadurch werden Prozesse aber durch Transitionen und nicht durch Stellen repräsentiert. Um eine kompaktere Darstellung zu bekommen, wedren in einer anderen Klasse die nichtnegativen Ausführungszeiten in die Stellen gelegt und es wird vorausgesetzt, daß Transitionen unverzögert schalten. Somit befindet sich das System zu jedem Zeitpunkt in einem eindeutig definierten Zustand. (token befinden sich zu jeder Zeit in den Stellen und niemals in den Transitionen).

Das Petri-Netz-Modell angereichert um die zwei Abbildungen D und R, die den Stellen zeitliche Ausprägungen und die für multimediale Ausgaben erforderlichen Resourcen zuordnen, führt dann zum Object Composition Petri Net (OCPN).

Definiton 2

OCPN ist definiert als C_ocpn = (S,T,F,D,R,M) mit

i) $S = \{s_{1},s_{2},\dots,s_{n}\}$ und $T = \{t_{1},t_{2},\dots,t_{m}\}$ disjunkt

ii) $F:\{S \times T\} \cup \{T \times S\} \longrightarrow I$ mit $I = \{1,2,\dots\}$

iii) $D:S \longrightarrow R$

iv) $R:S \longrightarrow \{r_{1},r_{2},\dots,r_{k}\}$

v) $M:S \longrightarrow J$ mit $J = \{0,1,2,\dots\}$

Es soll eine multimediale Slide-Show repräsentiert werden. Die Slide-Show besteht aus einer Sequenz von synchronisierten Audios und visuellen Elementen mit variierender Präsentationsdauer. Angenommen es seien n slides zu präsentieren und zu jedem slide gäbe es eine Sprachausgabe. In einem Zeit-Ressourven-Diagramm läßt sich die Präsentation repräsentieren als zwei Ströme die gleichzeitig abläufen, wie in Abbildung 20.20 gezeigt.

**Abbildung:** Timeline und Petrinetz-Repräsentation
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild5.PS} }\end{center}\end{figure}$

Die Zeit wird auf der horizontalen Achse aufgetragen. Die vertikale Achse spiegelt den Raum wider, die eine Anwendung während ihrer Ausführung einnimmt. Überträgt man dieses Diagramm in die eingeführte Petri-Netz-Syntax, ergibt sich der in der Abbildung unten aufgezeichnete Graph.

Es lassen sich auf diese Weise auch komplexere Synchronisationen mit dieser Technik repräsentieren. In Abbildung 20.21 wird ein Object A gezeigt, welches aus den Sub-Objekten D, E, F, G zusammengesetzt ist. Diese Objekte können z.B. stehen für Text(G), Sprache(F), und zwei sequentielle Bilder(D und E). Das zugehörige Petri-Netz ist ebenfalls dargestellt.

**Abbildung 20.21:** Komplexes Petrinetz
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild6.PS} }\end{center}\end{figure}$

20.4.2.2 Zeitintervalle

Eines der zentralen Themen bei der Moellierung von Zeit ist das Problem, wie ist die Zeit zu repräsentieren: unmittelbar oder mittelbar. Eine mittelbare Repräsentation stellen die Zeitintervalle dar.

Ein Zeitintervall ist charakterisiert durch eine Zeitdauer größer als 0 in einer beliebigen Menge von Einheiten, wie z.B. ,,eine Woche'' oder ,,100ms''. Die Zeitangabe ,,12.00 mittags'' steht aber nicht für ein Zeitintervall.

Defintion 3

Sei $[S,\leq ]$ eine partiell geordnete Menge und seien a,b zwei Elemente aus S mit $a \leq b$ .

Die Menge $\{ x \mid a \leq x \leq b\}$ heißt Intervall von S bezeichnet mit [a,b].

Gegeben seien zwei beliebige Intervalle, dann existieren 13 verschiedene Möglichkeiten diese in Relation zu setzen. Diese Relationen zeigen an, in welchen Beziehungen die Intervalle stehen. In Abbildung 20.22 werden nur 7 Relationen aufgeführt, da die Fehlenden die Inversen der abgebildeten darstellen.Als Beispiel ist die Relation after die inverse Relation zu before, oder äquivalent before^-1 ist die inverse zu before. Beachte: Die Relation equals hat keine inverse Relation!

Durch die Theorie der Petri-Netze un der Intervalle kommt man zu zwei grundlegenden Sätzen:

Satz 1

Gegeben seien zwei atomare Prozesse, spezifiziert durch zeitliche Intervalle,

dann existiert eine Petri-Netz-Repräsentation (OCPN) für deren zeitliche Beziehungen.

**Abbildung:** Intervalle und zugehörige Petrinetze
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild7.PS} }\end{center}\end{figure}$

Satz 2

Ein willkürlich komplexes Prozeß-Model bestehend aus Zeitintervallen läßt sich mit Hilfe

von Petri-Netzen durch Auswahl paarweiser, zeitlicher Beziehung zwischen zwei

Prozeßeinheiten konstruieren.

20.4.2.3 Resümee

Einige Probleme werden durch dieses Model nicht unterstützt. Als Beispiel soll hier erwähnt werden, daß mit dem OCPN-Model keine Interaktionen modelliert werden können. So läßt sich z.B. das Stoppen eines Videos durch den Anwender mit Hilfe der Petri-Netze nicht beschreiben. Ebenso läßt sich die reverse Darstellung eines Objektes, wie z.B. das Rückwärts-Abspielen eines Videos nicht beschreiben.

In erster Linie ist dieses Model also hilfreich bei der Komposition und Synchronisation von multimedialen Aufgaben.

Zum Abschluß soll hier ein etwas größeres Beispiel gezeigt werden, für eine Repräsentation einer Seite aus einer multimedialen Anwendung (siehe auch Abbildung 20.23).

**Abbildung 20.23:** Anwendungsbeispiel
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild8.PS} }\end{center}\end{figure}$

20.4.3 Calculus of Communication Systems (CCS)

CCS ist ein Kalkül zur Beschreibung eines Systems von Repräsentanten, die synchron und asynchron über Nachrichtenaustausch miteinander kommunizieren. Ein durch CCS beschriebenes System läßt sich vergleichen mit einem Netzwerk, in dem einzelne Knoten über Kanten Nachrichten untereinander austauschen.

In CCS besitzt jedes Objekt Schnittstellen bzgl. Eingang und Ausgang. Die Eingänge werden mit a? und die Ausgänge mit a! bezeichnet. Falls ein Objekt A einen Eingang a? und einen Ausgang b! besitzt, dann lautet seine Bezeichnung A=a?.b!.A. Diese Bezeichnung bedeutet, daß das Objekt seine Präsentation beginnt, sobald eine Nachricht an seinem Eingang a? eintrifft. Wenn es seine Präsentation abgeschlossen hat, schickt es eine Nachricht über seinen Ausgang b! an das nachfolgende Objekt.

In Abbildung 20.24 werden drei CCS-Ausdrücke gezeigt. Im ersten werden zwei Objekte A und B seriell synchronisiert. Objekt B beginnt seine Präsentation, nachdem Objekt A seine Präsentation beendet hat.

**Abbildung 20.24:** Serielle Synchronisation
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild9.PS} }\end{center}\end{figure}$

In Abbildung 20.25 sind zwei Objekte A und B gezeigt, die ihre Präsentation synchron starten und beenden.

**Abbildung 20.25:** Synchroner Start und Ende
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild10.PS} }\end{center}\end{figure}$

In Abbildung 20.26 wird eine Synchronisationsstruktur wiedergegeben, die bei Videos mit gleichzeitiger Sprachausgabe verwendet wird, zur Lippensynchronisation. Dabei präsentiert das Videoobjekt einen Videofilm, der einige Bilder lang ohne Ton ausgegeben wird. Wenn er einen bestimmten Punkt erreicht hat, wird das Objekt A mit der parallelen Sprachausgabe gestartet. Die gleichen Bedingungen gelten für die Objekte B und C.

**Abbildung 20.26:** Lippensynchronisation bei einem Video mit 3 Audios
$\begin{figure} \begin{center} {\protect\centering \epsfxsize=7cm \epsfbox{./zeichnungen/formale.bild11.PS} }\end{center}\end{figure}$

Video=s?.PlayVideo PlayVideo=s1!.Video1 PlayVideo1=s2!.Video2 PlayVideo2=s3!.Video3 PlayVideo3=e!.Video