1

Backfrieder-Hagenberg

Image CompressionVorlesung FH-Hagenberg

SE::MED

Backfrieder-Hagenberg

Kompression

DecoderEncoder

Beseitigung der unnötigen Daten ... Redundanz

2

Backfrieder-Hagenberg

Inhalte

• Redundanz• Channel Encoding• Error-Free Compression

– Hufmann Coding– Runlength Coding

• Lossy Compression– Transform Coding

Backfrieder-Hagenberg

Redundanz• Daten <=> Information• Kompressionsrate= n1/n2

– n1, n2 Anzahl der Info-Träger• Relative Redundanz

– RD=1-(1/CR)• n1=n2 RD=0, n2<<n1 : RD => 1• Redundanz: coding, interpixel,

psychovisulal

3

Backfrieder-Hagenberg

Coding-Redundanzr p( r ) Code 1 l ( r ) Code 2 l ( r )

1 0,19 000 3 11 22 0,25 001 3 01 23 0,21 010 3 10 24 0,16 011 3 001 35 0,08 100 3 0001 46 0,06 101 3 00001 57 0,03 110 3 000001 68 0,02 111 3 000000 6

∑ ⋅=r

rprlL )()( L=2,7bit

Backfrieder-Hagenberg

Interpixel-Redundanz

• Threshold•Run-length•1024x343•~12.000 runs/ 11 bit•CR=2.63

4

Backfrieder-Hagenberg

Psychovisuelle Redundanz

(a) 256, (b) 16 gleichverteilt, (c ) 16 quantisiertGraustufen

Backfrieder-Hagenberg

Literatur

• http://datacompression.info/• comp.compression FAQ (part2) • University of Western Australia algorithms course

– http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/huffman.html

• http://compression.graphicon.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf

5

Backfrieder-Hagenberg

Informationstheorie• I(E)=log(1/p(E))=-log(p(E))

Selbstinformation• Durchschnittliche Selbstinfo =

Entropie))(log()()(

1∑=

−=J

jjj apapzH

Backfrieder-Hagenberg

Kompression-Codierung

Einem Quell-Alphabet wird durch den Codierer ein Ziel-Alphabet zugeordnet. q(i,j) gibt die Wahrscheinlichkeit an, daßdem Element a(i) der Code b(j) zugeordnet wird.

6

Backfrieder-Hagenberg

Huffman: Source Reduction

• Häufigkeit der Quellsymbole wird ermittelt• zwei Symbole mit niedrigster Wahrscheinlichkeit

werde zusammengefaßt• Reduktion auf zwei Gruppen

Backfrieder-Hagenberg

Huffman: Codierung

• Oberstes Level: Zuweisung der Symbole 0,1• Aufspaltung der zusammengesetzen Gruppe• Resulierender Code:

– eindeutig, instant, minimale Redundanz (optimal)

7

Backfrieder-Hagenberg

Decodierung

• Baum wird von oben nach unten durchlaufen

• Dekodiertes Symbol am Ende eines Zweiges

• Symbole eindeutig• Codelänge

unterschiedlich für Symbole

Backfrieder-Hagenberg

Run-length Coding• Verfahren für Fax• Zeilenweise Verarbeitung• Codierung (Grauwert, Anzahl)• Binär: Längen von weiß und schwarz

8

Backfrieder-Hagenberg

Bitplane-Coding

Bits 7-4 Bits 3-0

Backfrieder-Hagenberg

Bitplane Decomposition & Coding

• Decomposition eines Grauwertes mit m-Bit/Pixel

• Codierung mit exklusiv oder (XOR), gineuer code

• zB. 127={0111 1111}a={0100 0000}g

00

22

11 222 aaa m

mm

m +⋅⋅⋅++ −−

−−

1

11

+

−−

⊕==

iii

mm

aagag

9

Backfrieder-Hagenberg

Transformations Coding

• Einteilung in Sub-Images (8x8)• Transformation• Quantisierung• Code-Generierung

Backfrieder-Hagenberg

Transformation: Motivation

10

Backfrieder-Hagenberg

Transformations-Methoden

(a,b) Fourier(c,d) Hadamard(e,f) Cosinus(links) Decodierte Bilder(rechts) Differenz

Backfrieder-Hagenberg

Beispiel: DCT 1 Koeffizient

11

Backfrieder-Hagenberg

Beispiel: DCT 3 Koeffizienten

Backfrieder-Hagenberg

Transform Coding: Maskengröße

(a) DCT 25% (b) Differenz 8x8 Maske(c) original (d) 2x2 (e) 4x4(f) 8x8

12

Backfrieder-Hagenberg

Quantisierung

Auswahl der Koeffizienten• Zonale Masken• Threshold

– Global– Adaptiv– Maskiert

• Codierung

Backfrieder-Hagenberg

Quantisierung:Masken

(a) Zonale Maske(b) gespeicherte

Bits(c) Threshold Mask(d) Koeffizienten-

Anordnung

13

Backfrieder-Hagenberg

Transform Coding:Quantisierung

Threshold Coding(links)Zonen-Maske(rechts)

Backfrieder-Hagenberg

Threshold und JPEG-Maske

T(u,v)=round(T(u,v)/M(u,v))

14

Backfrieder-Hagenberg

Quantisierung

JPEG Maske(links)4xMaske(rechts)

Backfrieder-Hagenberg

JPEG-Verfahren

15

Backfrieder-Hagenberg

Farbtransformation

• RGB -> YUV ->YCbCr– Cb Abweichung Blau-Gelb– Cr Abweichnung Rot-Cyan

• Komponenten in YUV geringer korreliert• Farbebenen werden getrennt komprimiert

Backfrieder-Hagenberg

Down-Sampling• Farbkomponente wird komprimiert• Luninanz-Signal bleibt erhalten

z.B. 2x2 Block: Original 4x3=12 WerteKomprimiert: 4+2=6 Werte = 50% reduziert

4:2:0-Abtastung PAL-DV Standard

16

Backfrieder-Hagenberg

Downsampling Schema

Backfrieder-Hagenberg

Transformation

• Bildung von 8x8 Blöcken• Diskrete Cosinustransformation

– Basis-Funktionen

17

Backfrieder-Hagenberg

Quantisierung• Gewichtung eines jeden

Koeffizieneten der DCT

⎟⎟⎠

⎞⎜⎜⎝

⎛=

),(),(),('

vuqvuGroundvuG

Quantisierungs-Tabelle• eine Tabelle pro Farbebene• für jeden Koeffizienten eine Qualitätswert• niedrige Werte -> geringer Verlust

Backfrieder-Hagenberg

Quantisierungstabelle

Beispiel:

18

Backfrieder-Hagenberg

CodierungUmordnen der 8x8 Maske zu einem linearen Array:

Zigg-Zagg-Ordering:Durch starke Quantisierung der hohen Frequenzen, entstehen lange Nullfolgen•Huffman coding•Runlength Coding

Backfrieder-Hagenberg

Zusammenfassung:

• Farbtransformation• Downsampling• Diskrete Cosinus-Transformation• Quantisierung• Codierung

Orange markierte Schritte komprimieren Daten