Post on 05-Apr-2015
transcript
Mathematische Grundlagen der Video – Kompression
von
Christian Müller
„GIS und Multimedia“
Allgemeines
Einsatz von Videos im geodätischen Arbeitsbereich: Städtebauliche Planung
• Zeigen von Ist – Zuständen• Photorealistische Visualisierung geplanter Bauobjekte• Virtuelle Realität
Routenplanung• Wege als Videos zeigen
Lehre• Aufnahme von Vorlesungen und Vorträgen• Animationen
Was hat das Thema mit dem Studium zu tun?
Allgemeines
Ein Film besteht aus einer Reihe von aufeinanderfolgenden Bildern
Jedes Bild für sich kann man als Bitmap – Vollbild betrachten
Problem: große Datenmenge
Woraus besteht ein Film?
Allgemeines
PAL – Standard: 720 x 576 Pixel = 414.720 Pixel
414.720 Pixel x 3 (RGB Werte pro Pixel) = 1.244.160 Byte
1.244.160 Byte x 25 Bilder/s = 31.104.000 Byte
1 Sekunde Film = 30 MByte
Rechenbeispiel
90 Minuten Film = 156 GByte
Allgemeines
Man unterscheidet: Verlustfreie Kompression:
Nach der Dekompression kann das ursprüngliche Signal wieder vollständig hergestellt werden
Verlustbehaftete Kompression: Das Signal wird nur annähernd wiederhergestellt
Datenkompression
Verfahren, um die Anzahl der Bits eines Signals herabzu – zusetzen
MPEG – Format
MPEG 1• Findet Anwendung bei sog. VideoCD• VHS ähnliche Qualität
MPEG 2• Kompatibel zu MPEG 1• Anwendung in der DVD – Technologie und im digitalen
Fernsehen (Premiere World) MPEG 4
• DivX, Echtzeitkommunikation, Mobile Multimedia UMTS
MPEG – Familie
MPEG – Format
Viele Informationen bleiben gleich, z.B.: der Hintergrund
Idee: überflüssige Informationen nicht mehrmals speichern
redundante Informationen auslassen
Unterschied zwischen zwei Bilder wird gespeichert
Bild um die Unterschiede zum vorhergehenden Bild ergänzen
Vergleichen von Bildern
MPEG – Format
Es werden drei verschiedene Bildtypen benutzt: I – Frame (intra – frame): Ein komplettes Vollbild, welches
alle Informationen enthält
P – Frame (predictet – frame): Einzelbild, welches lediglich die Differenz zum vorhergegangenem Bild enthält
B – Frame (bidirctional – frame): werden ausgehend von einem vorhergehenden und nachfolgenden Bild berechnet
Verschiedene Bildtypen
MPEG – Format
jede GOP enthält eine I – Frame als erstes Bild
dazu mehrere P – Frames
die B – Frames werden aus früheren und späteren P – und I – Frames abgeleitet
Verschiedene Bildtypen
Ein MPEG – Datenstrom besteht in erster Linie aus einer Sequenz von groups-of-pictures (GOP).
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
IStartbild ist das I – Frame
als Vollbild zum Einstieg
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
IStartbild ist das I – Frame
als Vollbild zum Einstieg
Zwischenbilder aus vorherigen
I – und P – Frames
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
IStartbild ist das I – Frame
als Vollbild zum Einstieg
Zwischenbilder aus vorherigen
I – und P – Frames
Zwischenbilder aus vorigen
und folgenden I – und P - Frames
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
I
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
I
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
I
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
I
PB
MPEG – Format
Veranschaulichung: Group of Pictures
BP
BB
I
MPEG – Format
B – Frames werden vom Decoder nur dann entschlüsselt,
wenn er den nachfolgenden P – Frame kennt:
Bildein – / ausgabe
MPEG – Format
B – Frames werden vom Decoder nur dann entschlüsselt,
wenn er den nachfolgenden P – Frame kennt:
Bilder werden in einer anderen Reihenfolge abgespeichert, als man sie hinterher zu sehen bekommt
Bildein – / ausgabe
MPEG – Format
Beispiel: Bildein – / ausgabe
B1I B2 P1 B3 B4 P2
Betrachtungsreihenfolge
MPEG – Format
Beispiel: Bildein – / ausgabe
B1I B2 P1 B3 B4 P2
P1I B1 B2 P2 B3 B4
Betrachtungsreihenfolge
Übertragungsreihenfolge
Codierung von I – Frames
Bild wird in 8x8 große Pixelblöcke aufgetrennt Blöcke werden einzeln bearbeitet Jeder Block durchläuft die DCT Umwandlung bis auf Rundungsfehler verlustfrei Verwandt mit der Fouriertransformation
Discrete Cosinustransformation
I I
Umwandlung räumlicher Information und Helligkeitswerte in
eine Frequenzdarstellung
Codierung von I – Frames
Das menschliche Auge ist für hohe Frequenzen weniger
empfindlich.
Discrete Cosinustransformation
I I
Codierung von I – Frames
Das menschliche Auge ist für hohe Frequenzen weniger
empfindlich.
je nach gewünschtem Kompressionsfaktor Vernachlässigung dieser Anteile
Discrete Cosinustransformation
I I
Wie geschieht dieses Weglassen von Hochfrequenzanteilen?
Codierung von I – Frames
sogenannter Quantisierer sorgt für die Verringerung der DCT – Koeffizienten
Koeffizienten nahe Null werden gleich Null gesetzt
Dieser ganze Vorgang wird Quantisierung genannt.
Quantisierung
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
Bild
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
8x8 Pixelblock
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
ursprüngliche Werte
103 101 102 105
34 56 109 107
30 28 105 106
101 104 106 103
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
103 101 102 105
34 56 109 107
30 28 105 106
101 104 106 103
ursprüngliche Werte
Transformierung
DCT – Koeffizienten
1
0
1
0 2
)12(cos
2
)12(cos),(
)()(2),(
N
x
N
y N
vy
N
uxyxf
N
vCuCvuF
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
103 101 102 105
34 56 109 107
30 28 105 106
101 104 106 103
ursprüngliche Werte
1
0
1
0 2
)12(cos
2
)12(cos),(
)()(2),(
N
x
N
y N
vy
N
uxyxf
N
vCuCvuF
I I
Farbwerte des Pixel der x-ten Matrixzeile und y-ten Matrixspalte
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
DCT – Koeffizienten
1
0
1
0 2
)12(cos
2
)12(cos),(
)()(2),(
N
x
N
y N
vy
N
uxyxf
N
vCuCvuF
I I
Transformierte Werte in der u – ten Zeile und v – ten Spalte
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
103 101 102 105
34 56 109 107
30 28 105 106
101 104 106 103
ursprüngliche Werte
405 0,2 -0,2 1,3
30 -0,4 0,7 -3,2
-0,8 -0,5 -0,3 -0,6
-2,0 2,2 -0,5 -1,6
Transformierung
DCT – Koeffizienten
I I
Codierung von I – Frames
Beispiel: Discrete Cosinustransformation
103 101 102 105
34 56 109 107
30 28 105 106
101 104 106 103
ursprüngliche Werte
405 0,2 -0,2 1,3
30 -0,4 0,7 -3,2
-0,8 -0,5 -0,3 -0,6
-2,0 2,2 -0,5 -1,6
Transformierung
DCT – Koeffizienten
DC – Komponente bzw. Gleichanteil f = 0
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0,2 -0,2 1,3
30 -0,4 0,7 -3,2
-0,8 -0,5 -0,3 -0,6
-2,0 2,2 -0,5 -1,6
DCT – Koeffizienten
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0,2 -0,2 1,3
30 -0,4 0,7 -3,2
-0,8 -0,5 -0,3 -0,6
-2,0 2,2 -0,5 -1,6
DCT – Koeffizienten
405 0 0 1
30 0 0 3
0 0 0 0
-2 2 0 0
Quantisierung
Ergebnismatrix
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 0 1
30 0 0 3
0 0 0 0
-2 2 0 0
Ergebnismatrix
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 0 1
30 0 0 3
0 0 0 0
-2 2 0 0
Ergebnismatrix
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 0 1
30 0 0 3
0 0 0 0
-2 2 0 0
Ergebnismatrix
Zickzack
405
0
30
0
0
0
1
0
0
-2
2
0
-3
0
0
0
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 30 0 0 0 1 0 0 -2 2 0 -3 0 0 0
Wertefolge nach Zickzack – Auslesung
405 1 30 3 1 2 -2 2 1 -3 3Lauflängen –
Codierung
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 30 0 0 0 1 0 0 -2 2 0 -3 0 0 0
Wertefolge nach Zickzack – Auslesung
1 3 2 31
405 1 30 3 1 2 -2 2 1 -3 3Lauflängen –
Codierung
I I
Codierung von I – Frames
Beispiel: Quantisierung und Kompression
405 0 30 0 0 0 1 0 0 -2 2 0 -3 0 0 0
Wertefolge nach Zickzack – Auslesung
1 3 2 31
405 1 30 3 1 2 -2 2 1 -3 3Lauflängen –
Codierung
I I
Codierung von P – & B – Frames
Motion Compensation
Idee: Bildteile werden gesucht, die sich von Frame zu Frame
nur verschieben, wie z.B.: sich bewegende Objekte
An diese Bilder wird dann ein Bewegungsvektor weitergegeben
P B
Die Voraussage von P – und B – Frames geschieht mit dersog. „Motion Compensation“, d.h. bewegungskompensiert.
Codierung von P – & B – Frames
Einteilung jedes Bildes in Makroblöcke aus 16x16 Pixeln
makroblockweise Abtastung, in welche Richtung sich der Inhalt eines Blocks verschiebt
Blöcke werden gemäß des Vektors verschoben und auf das Restbild addiert
Aufteilung in Makroblöcke
P B
Codierung von P – & B – Frames
Beispiel
P B
Codierung von P – & B – Frames
Beispiel
P B
Codierung von P – & B – Frames
Beispiel
P B
Codierung von P – & B – Frames
Werden allerdings keine übereinstimmenden Vektoren
gefunden, wird dieses Bild als I – Frame mittels DCT codiert.
I – Frame oder P – / B – Frame
P B
Strebt die Differenz zwischen zwei Makroblöcken gegen Null,
so wird hier der Bewegungsvektor berechnet und die Motion
Compensation benutzt, um ein P – bzw. B – Frame zu
codieren.
Codierung von P – & B – Frames
Abtastverfahren
P B
Codierung von P – & B – Frames
Abtastverfahren
P B
Schluss
Vergleich von Kompressionsraten
DCT + Motion Compensation: Datenrate 4 MBit/s
Zum Vergleich: unkomprimierter Film mit 30 MByte/s
Kompression von 60:1
ohne starken Verlust möglich: 100:1
Noch Fragen,
Kienzle?