View
7
Download
0
Category
Preview:
Citation preview
Digitale Signal & Bildverarbeitung Werner Backfrieder
Image CompressionVorlesung FH-Hagenberg
DSB
Digitale Signal & Bildverarbeitung Werner Backfrieder
Kompression
DecoderEncoder
Beseitigung der unnötigen Daten ... Redundanz
Digitale Signal & Bildverarbeitung Werner Backfrieder
Inhalte
• Redundanz• Loss-less Compression
– Hufmann Coding– Runlength Coding
• Lossy Compression– Transform Coding
Digitale Signal & Bildverarbeitung Werner Backfrieder
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
Digitale Signal & Bildverarbeitung Werner Backfrieder
Coding-Redundanz
r 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
Digitale Signal & Bildverarbeitung Werner Backfrieder
Interpixel-Redundanz
• Threshold•Run-length•1024x343•~12.000 runs/ 11 bit•CR=2.63
Digitale Signal & Bildverarbeitung Werner Backfrieder
Psychovisuelle Redundanz
(a) 256, (b) 16 gleichverteilt, (c ) 16 quantisiertGraustufen
Digitale Signal & Bildverarbeitung Werner Backfrieder
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_mi
nimum-redundancy-codes.pdf
Digitale Signal & Bildverarbeitung Werner Backfrieder
Informationstheorie• I(E)=log(1/p(E))=-log(p(E)) Selbstinformation
– sicheres Ereignis p(E)=1 I(E)=0• Beispiel : Text bestehend aus einem Buchstaben
– unwahrscheinliches Ereignis p(E)<<1 => 1/p(E) >>1 I(E) >>0
• Beispiel: “normal-verteilter” Text
• Durchschnittliche Selbstinfo = Entropie
))(log()()(1∑=
−=J
jjj apapzH
Digitale Signal & Bildverarbeitung Werner Backfrieder
Huffman: Source Reduction
• Häufigkeit der Quellsymbole wird ermittelt• zwei Symbole mit niedrigster Wahrscheinlichkeit werde
zusammengefaßt• Reduktion auf zwei Gruppen
Digitale Signal & Bildverarbeitung Werner Backfrieder
Huffman: Codierung
• Oberstes Level: Zuweisung der Symbole 0,1• Aufspaltung der zusammengesetzen Gruppe• Resulierender Code:
– eindeutig, instant, minimale Redundanz (optimal)
Digitale Signal & Bildverarbeitung Werner Backfrieder
Decodierung• Baum wird von oben
nach unten durchlaufen• Dekodiertes Symbol am
Ende eines Zweiges • Symbole eindeutig
(binärer Baum)• Codelänge
unterschiedlich für Symbole
Digitale Signal & Bildverarbeitung Werner Backfrieder
Run-length Coding
• Verfahren für Fax• Zeilenweise Verarbeitung• Codierung (Grauwert, Anzahl)• Binär: Längen von weiß und schwarz
Digitale Signal & Bildverarbeitung Werner Backfrieder
Bitplane-Coding
Bits 7-4 Bits 3-0
Digitale Signal & Bildverarbeitung Werner Backfrieder
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
Digitale Signal & Bildverarbeitung Werner Backfrieder
Transformations Coding
• Einteilung in Sub-Images (8x8)• Transformation• Quantisierung• Code-Generierung
Digitale Signal & Bildverarbeitung Werner Backfrieder
Transformation: Motivation
Digitale Signal & Bildverarbeitung Werner Backfrieder
Beispiel: DCT 1 Koeffizient
Digitale Signal & Bildverarbeitung Werner Backfrieder
Beispiel: DCT 3 Koeffizienten
Digitale Signal & Bildverarbeitung Werner Backfrieder
Transform Coding: Maskengröße
(a) DCT 25% (b) Differenz 8x8 Maske(c) original (d) 2x2 (e) 4x4(f) 8x8
Digitale Signal & Bildverarbeitung Werner Backfrieder
Quantisierung
Auswahl der Koeffizienten• Zonale Masken• Threshold
– Global– Adaptiv– Maskiert
• Codierung
Digitale Signal & Bildverarbeitung Werner Backfrieder
Quantisierung:Masken
(a) Zonale Maske(b) gespeicherte Bits(c) Threshold Mask(d) Koeffizienten-
Anordnung
Digitale Signal & Bildverarbeitung Werner Backfrieder
Transform Coding:Quantisierung
Threshold Coding(links)Zonen-Maske(rechts)
Digitale Signal & Bildverarbeitung Werner Backfrieder
Threshold und JPEG-Maske
T(u,v)=round(T(u,v)/M(u,v))
Digitale Signal & Bildverarbeitung Werner Backfrieder
Quantisierung
JPEG Maske(links)4xMaske(rechts)
Digitale Signal & Bildverarbeitung Werner Backfrieder
JPEG-Verfahren
Digitale Signal & Bildverarbeitung Werner Backfrieder
Farbtransformation
• RGB -> YUV ->YCbCr– Cb Abweichung Blau-Gelb– Cr Abweichnung Rot-Cyan
• Komponenten in YUV geringer korreliert• Farbebenen werden getrennt komprimiert
Digitale Signal & Bildverarbeitung Werner Backfrieder
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
Digitale Signal & Bildverarbeitung Werner Backfrieder
Downsampling Schema
Digitale Signal & Bildverarbeitung Werner Backfrieder
Transformation
• Bildung von 8x8 Blöcken• Diskrete Cosinustransformation
– Basis-Funktionen
Digitale Signal & Bildverarbeitung Werner Backfrieder
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
Digitale Signal & Bildverarbeitung Werner Backfrieder
Quantisierungstabelle
Beispiel:
Digitale Signal & Bildverarbeitung Werner Backfrieder
CodierungUmordnen der 8x8 Maske zu einem linearen Array:
Zigg-Zagg-Ordering:Durch starke Quantisierung der hohen Frequenzen, entstehen lange Nullfolgen•Huffman coding•Runlength Coding
Digitale Signal & Bildverarbeitung Werner Backfrieder
Zusammenfassung:
• Farbtransformation• Downsampling• Diskrete Cosinus-Transformation• Quantisierung• Codierung
Orange markierte Schritte komprimieren Daten
Recommended