Multimedia-Systeme: Übungsblatt 13

Übung: 31.01.03

Aufgabe 1: Kompressionsverfahren

1. Huffman-Kodierung

   Gegeben sei die Zeichenkette CADBBDCCBC. Kodieren Sie diese optimal nach dem Huffman-Verfahren. Geben Sie den vollständigen Kodierbaum an. Gehen Sie dabei davon aus, daß obige Zeichenkette einen repräsentativen Ausschnitt aus der insgesamt zu übertragenden Datenmenge darstellt.

2. Statische arithmetische Kodierung 

   Bei der arithmetischen Kodierung wird eine Nachricht als Gleitkommazahl aus dem Intervall [0; 1) kodiert. Dieses Intervall wird dabei in Teilintervalle unterteilt, die sukzessive wiederum zerlegt werden. Entwickeln Sie die beiden Formeln für die Berechnung der Unter- bzw. Obergrenze (U_n bzw. O_n) des Kodierungsintervalls bezüglich des n-ten Zeichens. Es gilt U₀=0 und O ₀=1.

   Beispiel: Sind die Zeichen a, b mit den Wahrscheinlichkeiten p(a)=0,4 und p(b)=0,6 gegeben, und es wird die Zeichenkette ab kodiert, so ergibt sich für das 1. Zeichen (a) das Kodierungsintervall [U₁; O₁) = [0; 0,4).

3. Berechnung zur statischen arithmetischen Kodierung 

   Kodieren Sie nun die Zeichenkette bca mittels statischer arithmetischer Kodierung. Die zugehörigen Wahrscheinlichkeiten p(.) sind p(a)=0,3, p(b)=0,3 und p(c)=0,4. Verwenden Sie für das Eintragen Ihrer Ergebnisse untenstehende Tabelle und wählen Sie ein geeignetes Endergebnis aus.
   

   Schritt	Zeichen	Kodierungsintervall
   0	-	[0; 1)
   1	b
   2	c
   3	a

Aufgabe 2: Kompression von Videosequenzen

1. Merkmale von MPEG-Video, H.261 und Motion-JPEG

   Betrachten Sie die Videosequenz $V$, die aus den Einzelbildern $F$₁, F ₂ , ..., F_n besteht. $V$ werde nun mittels der Videokodierungsverfahren MPEG-Video, H.261 und Motion-JPEG in die komprimierten Datenströme $V$_MPEG, $V$_H261 und $V$ _M-JPEG überführt.

   Vergleichen Sie die drei Verfahren unter folgenden Gesichtspunkten:

   1. Kompressionsrate, d. h. welches Verfahren erreicht die beste, welches die mittlere und welches die schlechteste Kompression,
   2. Wahlfreier Zugriff auf Einzelbilder, d. h. wie aufwendig ist es, aus den komprimierten Datenströmen beliebig positionierte Einzelbilder zu extrahieren.

   Begründen Sie Ihre Antworten!

   Hinweis: Unter Motion-JPEG versteht man eine Aneinanderreihung JPEG-komprimierter Einzelbilder.

2. Videokompression

   Die komprimierten Videoströme V_MPEG und V _M-JPEG werden über ein paketorientiertes Netzwerk übertragen. Der Videostrom V_MPEG wurde mit dem MPEG-Kompressionsverfahren, der Videostrom V_M-JPEG mittels Motion-JPEG kodiert. Ein Paket innerhalb der Übertragung besteht aus einem Teilbereich eines einzelnes Bildes (frame) des jeweiligen komprimierten Videos.

   Wie beeinträchtigen Paketverluste die Darstellung der verschiedenen Videoströme auf der Empfängerseite? Begründen Sie Ihre Antwort!

   Hinweis: Motion-JPEG bedeutet, daß die Einzelbilder des Videostromes unabhängig voneinander mittels des JPEG-Verfahrens komprimiert werden.

Aufgabe 3: Quality of Service

1. Erläutern Sie den Begriff Delay-Jitter. Wodurch kann es zu Delay-Jitter in normalen Weitverkehrsnetzen wie dem Internet kommen?

2. Welches der beiden LAN-Typen Ethernet bzw. Token-Ring zeigt in bezug auf den Delay-Jitter ein zuverlässigeres Verhalten? Begründen Sie Ihre Antwort kurz!

3. Betrachten Sie ein Videoserversystem. Nennen Sie 3 weitere Dienstgütemerkmale der Netzwerkanbindung, die neben dem Delay-Jitter in einem solchen System eine Rolle spielen und erläutern Sie diese kurz.

Aufgabe 4: Betriebssystemunterstützung

1. Was versteht man unter Preemptive Scheduling, was unter Non-preemptive Scheduling?

2. Ein Video on Demand Server nutzt das Non-preemptive Scheduling. Seine Aufgabe ist es, gleichmäßig Videodaten an seine Empfänger zu senden. Innerhalb von 10ms kann der Server im Durchschnitt 100kByte Daten versenden. Ein Videostrom besteht aus durchschnittlich 2 MBit/s wobei das Senden eines Videostromes in jeweils einem Prozeß geschieht. Zum Umschalten zwischen zwei Prozessen werden jeweils 2ms benötigt. Wieviele Ströme kann der Server maximal parallel versenden?´
   Hinweis: Mindestens einmal pro Sekunde sollen die Daten jedes Videostroms gesendet werden.
   

Aufgabe 5: Inhaltsanalyse

1. Gegeben sei ein zweidimensionales, digitales Bild der Größe $N$x M mit 256 Graustufen. Geben Sie einen Algorithmus zur Berechnung des zugehörigen Histogramms an.

2. Beschreiben Sie eine Vorgehensweise zum Vergleich zweier Histogramme $H$₁ und $H$₂, und beurteilen Sie die Aussagekraft von Histogrammen in Bezug auf die histogrammbasierte Schnitterkennung in Videosequenzen.

3. Aufgrund der von Ihnen festgestellten Schwachpunkte, entschließen Sie sich in einem System zur automatischen Schnitterkennung in Videosequenzen statt Histogrammen sogenannte color coherence vectors (CCV) einzusetzen. Beschreibt der Vektor ₀, h₁, ..., h_n> ein Histogramm, wobei $h$_i die Anzahl der Bildpunkte mit Farbe/Grauwert $i$ angibt; so kann ein CCV über a₀,b₀),$($ a₁,b₁), ..., (a _n , b_n)> angegeben werden. Dabei gibt $$ a_i die Anzahl der Bildpunkte mit Farbe $i$ an, die zur Klasse $A$ gehören, und $$ b_i die Anzahl der Bildpunkte mit Farbe $i$, die der Klasse $B$ zugeordnet wurden.

   Zur Klassifizierung der einzelnen Bildpunkte verwenden Sie folgende Vorgehensweise: Ein Bildpunkt $p$ gehört genau dann zur Klasse A, wenn er zu einer Region mit mindestens $T$ gleichfarbigen Bildpunkten gehört. Ansonsten wird er der Klasse B zugeordnet.

   Beispiel: Nebenstehendes $6$ x 6 Bild ergibt mit $T\; =\; 10$ den color coherence vector a 0 = 15, b0 = 1), (a1 = 16, b1 = 1+3)>.

   Entwickeln Sie einen Algorithmus zur Berechnung des CCV unter Berücksichtigung obiger Klassifizierung. Gehen Sie dabei davon aus, daß Ihrem Algorithmus ein Einzelbild $I$ der Größe $N$x M und der Schwellwert $T$ als Parameter übergeben werden.

   Hinweis: Die Unterteilung eines Bildes in Regionen zusammenhängender Bildpunkte gleicher Farbe ist ein Segmentierungsproblem.