Multimedia-Systeme: Übungsblatt 11

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.

   - 1 101 110 00 00 110 0 0 10 0 0 111 110 10 10 110 0 0 10 0 0 011 010 10 10 010 0 1 10 0 1 100 110 10 10 110 0 0 10 0

2. Kompression von Videosequenzen

   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.

Aufgabe 2: Kommunikationsunterstützung

1. 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!

      - Ethernet Token-Ring

      
      

   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.

2. Multicasting

   1. PIM (Protocol Independent Mode) ist ein Multicast-Routing-Protokoll, das in zwei Modi betrieben wird. Welches sind die beiden Modi? Erklären Sie die Funktionsweise der beiden Modi. Gehen Sie auf die Vorteile des PIM gegenüber anderen Multicast-Routing-Protokollen ein.

   2. Erklären Sie in kurzen Worten, was man im Zusammenhang mit dem MBone unter dem Begriff ``Tunneling'' versteht.

Aufgabe 3: 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?

   - 21 37 44

   
   

Aufgabe 4: Multimedia-Datenspeicher

1. Nennen Sie vier klassische Disk Scheduling Methoden und erläutern Sie diese kurz.

2. Welche Schwachpunkte weisen diese Methoden hinsichtlich der Verarbeitung von Multimedia-Daten auf? Schlagen Sie ein Schema vor, welches die Probleme löst.

3. Betrachten Sie die Anforderungsreihenfolge für Blöcke einer Festplatte auf der nächsten Seite. Bearbeiten Sie diese Anforderungsreihenfolge unter Verwendung des Scan-EDF-Verfahrens mit modifizierten deadlines. Verwenden Sie zur Darstellung nebenstehendes Diagramm. Zur Berechnung der modifizierten deadlines wählen Sie eine geeignete Funktion aus und geben Sie diese an.

Geben Sie in der nachfolgenden Auswahlbox den Zustand des Schreib-/Lesekopfes nach Abarbeitung der zuletzt ausgeführten Anfrage an:

- 20 up 10 up 10 down

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 a0 = 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.

Abgabedaten:

Matrikelnummer: Password: