Transcript
Page 1: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Mathematische Grundlagen der Video – Kompression

von

Christian Müller

„GIS und Multimedia“

Page 2: 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?

Page 3: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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?

Page 4: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 5: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 6: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 7: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 8: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 9: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 10: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

IStartbild ist das I – Frame

als Vollbild zum Einstieg

Page 11: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 12: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 13: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

I

Page 14: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

I

Page 15: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

I

Page 16: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

I

Page 17: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

PB

MPEG – Format

Veranschaulichung: Group of Pictures

BP

BB

I

Page 18: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

MPEG – Format

B – Frames werden vom Decoder nur dann entschlüsselt,

wenn er den nachfolgenden P – Frame kennt:

Bildein – / ausgabe

Page 19: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 20: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

MPEG – Format

Beispiel: Bildein – / ausgabe

B1I B2 P1 B3 B4 P2

Betrachtungsreihenfolge

Page 21: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

MPEG – Format

Beispiel: Bildein – / ausgabe

B1I B2 P1 B3 B4 P2

P1I B1 B2 P2 B3 B4

Betrachtungsreihenfolge

Übertragungsreihenfolge

Page 22: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 23: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von I – Frames

Das menschliche Auge ist für hohe Frequenzen weniger

empfindlich.

Discrete Cosinustransformation

I I

Page 24: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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?

Page 25: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 26: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von I – Frames

Beispiel: Discrete Cosinustransformation

Bild

I I

Page 27: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von I – Frames

Beispiel: Discrete Cosinustransformation

8x8 Pixelblock

I I

Page 28: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 29: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 30: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 31: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 32: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 33: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 34: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 35: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 36: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 37: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 38: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 39: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 40: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 41: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 42: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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.

Page 43: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 44: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von P – & B – Frames

Beispiel

P B

Page 45: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von P – & B – Frames

Beispiel

P B

Page 46: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von P – & B – Frames

Beispiel

P B

Page 47: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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.

Page 48: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von P – & B – Frames

Abtastverfahren

P B

Page 49: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Codierung von P – & B – Frames

Abtastverfahren

P B

Page 50: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

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

Page 51: Mathematische Grundlagen der Video – Kompression von Christian Müller GIS und Multimedia

Noch Fragen,

Kienzle?


Recommended