Multimedia-Systeme: Übungsblatt 13 (Musterlösung)

Ü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.

   Als Wahrscheinlichkeiten ergeben sich: A B C D 10% 30% 40% 20% Der vollständige Kodierbaum sieht demnach folgendermaßen aus: Daraus ergibt sich folgende Kodierung: 0 111 110 10 10 110 0 0 10 0.

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).

   es bezeichnen:         Un die untere Grenze des Kodierungsintervalls, On die obere Grenze des Kodierungsintervalls, Rn die Größe des Kodierungsintervalls, u(ch) die untere Grenze des ersten Kodierungsintervalls bezüglich des Eingabezeichens ch o(ch) die obere Grenze des ersten Kodierungsintervalls bezüglich des Eingabezeichens ch Damit gelten folgende Zusammenhänge: U0=0, O0=1, R0=1 Un=Un-1+Rn-1*u(ch) On=Un-1+Rn-1*o(ch) Rn=On-Un

   
   

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

   erste Kodieungsintervalle:  Zeichen a b c [u(ch); o(ch) ) [0; 0,3) [0,3; 0,6) [0,6; 1) Schritt Zeichen Kodierungsintervall 0 - [0; 1) U0=0 O0=1 1 b [0,3; 0,6) U1=0+1*0,3 O1 =0+1*0,6 2 c [0,48;0,6) U2=0,3+0,3*0,6 O 2=0,3+0,3*1 3 a [0,48; 0,516) U3=0,48+0,12*0 O 3=0,48+0,12*0,3 Auswahl eines Zeichens aus dem Intervall [0,48; 0,516), z.B. 0,5

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.

   Kompressionsrate: M-JPEG: M-JPEG ergibt im Vergleich die schlechteste Kompression, da hier auf die besonderen Eigenschaften von Videosequenzen keine Rücksicht genommen wird, d.h. die Tatsache, daß aufeinanderfolgende Bilder in der Regel nur minimal voneinander abweichen, wird nicht ausgenutzt. In der Terminologie des MPEG-Verfahrens ergibt M-JPEG als Ergebnis eine Folge von I-Frames. H.261: Im Gegensatz zum M-JPEG-Verfahren werden hier die Abhängigkeiten aufeinanderfolgender Bilder ausgenutzt; es gibt Intraframe- (DCT-basiert) und Interframe-Kodierung (DPCM-basiert). MPEG-Video: MPEG-Video ist flexibler als M-JPEG; insbesondere die Verwendung von bidirectionally predictive coded pictures (B-Frames) erlaubt hohe Kompressionsraten. Wahlfreier Zugriff auf Einzelbilder: M-JPEG: Da hier die einzelnen Frames unabhängig voneinander kodiert werden, ermöglicht ein M-JPEG-Datenstrom den einfachsten Zugriff auf Einzelbilder. H.261: Da bei der Kodierung Abhängigkeiten zwischen aufeinanderfolgenden Bildern ausgenutzt werden, muß der Dekodierung eines interframe-kodierten Bildes Fi die Dekodierung des bzw. der Frames vorausgehen, von denen Fi abhängig ist. MPEG-Video: Die Dekodierung eines B-Frames erfordert die Auflösung von Abhängigkeiten in beide Richtungen. Ist z.B. die komprimierte Bildfolge I0, B1, B 2, P3, B4, B5, I 6 gegeben, so erfordert die Dekodierung von B2 , daß zunächst I0, I6 und P 3 dekodiert werden. Bezüglich Kompression liefert MPEG-Video die besten, H.261 mittlere und M-JPEG die schlechtesten Ergebnisse. Bei wahlfreiem Zugriff auf Einzelbilder kehrt sich diese Reihenfolge gerade um.

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.

   Motion-JPEG: Paketverluste sind hier von geringer Bedeutung, da sie nur das jeweils aktuelle Bild betreffen. D.h. in diesem Fall ist ein Teilbereich des aktuellen Bildes nicht darstellbar. Da sich innerhalb einer Videosequenz von einem Bild zum anderen nur wenig ändert, kann dieser Paketverlust leicht kompensiert werden. MPEG: Hier erweisen sich die Abhängigkeiten zwischen den einzelnen Bildern als problematisch. Die Auswirkung eines Paketverlusts hängt davon ab, welchem Frametyp (I,P,B) dieses Paket zugeordnet ist. Der Verlust eines Teilbereichs innerhalb eines I-Frames wirkt auf die nachfolgenden Bilder aus (sofern diese nicht ebenfalls I-Frames sind). Es können daher ganze Teilsequenzen unbrauchbar werden. Wird ein P-Frame nicht vollständig übertragen, so wirkt sich das ebenfalls auf nachfolgende Bilder aus. Lediglich der Verlust von Teilen eines B-Frames ist unproblematisch.

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?

   Der Delay-Jitter gibt die Varianz der Verzögerung beim Versenden von Daten an. Die Verzögerung entspricht dabei der Zeit, die ein Paket benötigt, um von der Quelle zum Ziel zu gelangen. Gründe für Delay-Jitter in WANs sind: Best effort Netze bieten keine Ressourcenreservierung an Verbindungslose Protokolle können Pakete auf unterschiedlichen Wegen routen. Dadurch entstehen unterschiedliche Delays. Fehlersicherung durch go-Back-n: Verluste von Paketen werden nicht sofort bemerkt. Erst nach Ablauf eines time-outs werden verlorene Pakete erneut gesendet.

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!

   Token Ring ist in sofern zuerlässiger, daß zumindest ein maximale Wartezeit angegeben werden kann, bis eine Station sendeberechtigt ist. Beim Ethernet kann keine maximale Wartezeit angegeben werden. Bei hoher Auslastung des Netzes kann es zu vielen Kollissionen kommen, sodaß eine Station unter Umständen sehr lange warten muß, bis sie ein Paket senden darf.

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.

   Delay. Der Delay (Verzögerung) entspricht der Zeit, die ein Paket benötigt, um von der Quelle zum Ziel zu gelangen. Er wird zum einen durch die physikalische Übertragungszeit auf dem Medium zum anderen durch die Verarbeitungsgeschwindigekit und die Auslastung der Zwischenknoten (Router) verursacht. Beim Videoserver gibt der QoS-Parameter Delay die maximale Zeit an, die Zwischen dem Sendezeitpunkt und dem Empfangszeitpunkt vergehen darf und spielt i.d.R. in diesem Falle keine große Rolle. Loss-Rate. Die Loss-Rate gibt an, wieviele Pakete pro Zeitintervall verloren gehen. Die Loss-Rate wird durch physikalische Übertragungsfehler und durch Überlastung der Router (Verwerfen von Paketen) ausgelöst. Der QoS Parameter Loss-Rate gibt die maximale Anzahl von Paketen an, die eine Anwendung bereit ist, hinzunehmen. Es gibt drei Reaktionsmöglichkeiten auf Paketverluste: Ignorieren. Verlorene Pakete werden nicht erneut gesendet. Diese Methode ist typisch für Videoübertragungen, da kleine Bildfehler nicht wargenommen werden. Anzeigen. Die Netzwerkschicht informiert die Anwendung zumindest über Verluste. Korrigieren. Die Netzwerkschicht sorgt für eine sichere Übertragung. Verloren Pakete werden erneut gesendet. Dieses Verhalten ist beispielsweise notwendig bei Whiteboardoperationen. Throughput. Der Durchsatz gibt die maximale Langzeitdatenrate an. Er wird hauptsächlich durch die Leistungsfähigkeit der physikalischen Übertragungswege beeinflußt. Der QoS Paramter Throughput gibt an, welche Datenrate eine Anwendung benötigt. Bei unserem Videoserver wird die Anforderung hauptsächlich durch unsere mittlere Bildgröße (in Bytes) bestimmt. Der Parameter kann durch den Wert der maximalen Burstgröße noch verfeinert werden.

Aufgabe 4: Betriebssystemunterstützung

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

   Preemptive Scheduling: Wenn ein Prozeß mit höherer Priorität eine Anforderung stellt, wird dem gerade aktuelen Prozeß die Ressource entzogen. Folge: Es entsteht ein erhöhter Aufwand für die Prozeßverwaltung und es gibt mehr Prozeßwechsel. Non-Preemptive Scheduling: Aktive Prozesse werden nicht unterbrochen; in manchen Fällen durch äußere Zwänge vorgegeben, z.B. für einen Prozeß, der vom Netz liest. Folge: Weniger Aufwand für Prozeßwechsel. Non preemptive Scheduling ist i.d.R. vorzuziehen, wenn die Ausführungszeiten kurz sind.

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.
   

   CPU-Output: o= 100kByte/10ms ==> o= 10 kByte/ms= 10.000 kByte/s benötigt werden 2MBit/s pro Strom 250kByte/s ==> Quantum q= 250kByte/10.000kByte/s= 0,025s Das Umschalten dauert s= 2ms n*(q+s)= 1s ==> n= |1/(q+s)|= 37 Es können also 37 Ströme gleichzeitig von einem Server bedient 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.

   Histogram H(256); // Histogramm fuer 256 Grauwerte Image I(N,M); // Bild der Groesse NxM for i = 0 to 256-1 do // Initialisierung H[i] = 0; for x = 0 to N-1 do // alle Pixel des Bildes abarbeiten for y = 0 to M-1 do H[I(x,y)] = H[I(x,y)] + 1; od od

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.

   Betrachtet man die beiden Histogramme als Vektoren, d.h. $H$1 = < h0 , h 1, ..., hn > und $H$ 2 = < k0, k1, ..., k n > , so kann man folgende Distanzmaße verwenden: $$L1 = SUMi=0n(hi-ki) L2 = SUMi=0n (hi -k i)2 Die Verwendung von Histogrammen für die Erkennung von Schnitten in Videosequenzen ist problematisch, da grundverschiedene Bilder das gleiche Histogramm aufweisen können; man betrachte zum Beispiel zwei Bilder: Bild 1 zeigt eine Wiese mit Mohnblumen und Bild 2 stellt einen großen, roten Sonnenschirm dar. In beiden Bildern sind demnach viele rote Bildpunkte vorhanden, ihre Verteilung über die Bildfläche ist jedoch völlig unterschiedlich.

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.

   calculateCCV (Image I, Threshold T) { colorCoherenceVector CCV; // Initialisierung CCV for i = 0 to numberOfColors-1 do // Anzahl der Farben wird // als gegeben angenommen CCV[i].alpha = 0; CCV[i].beta = 0; od Image visited(N,M); for x = 0 to N-1 do for y = 0 to M-1 do visited(x,y) = false; od od for all pixels p in I do if (visited(p) == false) then currentColor = I(p); numberOfPixels = regionGrowing (I,visited,p); if (numberOfPixels >= T) then CCV[currentColor].alpha += numberOfPixels; else CCV[currentColor].beta += numberOfPixels; fi fi od return CCV; } regionGrowing (Image I, VAR Image visited, Pixel p) { Queue queue; // fuer region growing wird hier statt // Rekursion eine queue verwendet currentColor = I(p); queue.put(p); // Startpixel eintragen visited(p) = true; numberOfPixels = 1; while (queue.empty() == false) do p = queue.get(); for each q in neighbourhood(p) do if ((visited(q) == false) and (I(q) == currentColor)) then visited(q) = true; queue.put(q); numberOfPixels++; fi od od return numberOfPixels; }