Www.vis.uni-stuttgart.de Image compression Seminar : Bildverarbeitung und Computer Vision Betreuer : Prof. Dr.-Ing. Andrés Bruhn Wintersemester 2015/16

ww

w.v

is.u

ni-s

tuttg

art.d

e Image compressionSeminar : Bildverarbeitung und Computer VisionBetreuer : Prof. Dr.-Ing. Andrés BruhnWintersemester 2015/16

Cagri Tasci04.12.2015

ww

w.v

is.u

ni-s

tuttg

art.d

e Bildkomprimierung : Idee & Motivation

Digitale Bilder : Benötigen viele Bits zur Darstellung & Speicherung Erzeugen große Datenmengen

Bildkompression: Reduziert Anzahl der benötigten Bits :

Durch effizientere Codierung Durch Erkennung & Entfernung von Redundanz Durch Qualitätsverlust in akzeptablem Rahmen

Erhöht somit Anzahl speicherbarer Bilder. Vorteilhaft für Bildverarbeitung & Anwendungen. Verlustfreie oder Verlustbehaftete Kompression

Cagri Tasci04.12.2015 2

ww

w.v

is.u

ni-s

tuttg

art.d

e Verlustfreie / Verlustbehaftete Kompressions

Verlustfreie Kompressionsverfahren sämtliche Informationen bleiben Erhalten Dekomprimierung möglich Verfahren erzielen effizientere Kodierung Grad der Komprimierung begrenzt

Verlustbehaftete Kompressionsverfahren Nehmen Qualität-/ Informationsverlust in kauf Verlust möglichst unmerklich!! Nutzen Eigenschaften des Menschlichen Sehvermögens Original Bild wird verändert Dekomprimierung nicht möglich


ww

w.v

is.u

ni-s

tuttg

art.d

e Huffman Coding

1952 von David A. Huffman entworfen Algorithmus zur effizienteren Kodierung Reduziert Anzahl zur Kodierung benötigter Bits:

Ordnet jedem Symbol Kodierung mit variabler Länge zu Häufigere Symbole werden kürzer kodiert

Code ergibt sich durch entstandene Baumstruktur. Baumstruktur wird für Dekodierung gebraucht. Quelle: http://www1.ucsc.edu


ww

w.v

is.u

ni-s

tuttg

art.d

e Huffman Coding : Verfahren

1. Input : Bild mit n unterschiedlichen Symbolen Beginne mit „Alphabet“ der Größe n

2. Ordne jedem Symbol eine Auftrittswahrscheinlichkeit zu

3. zwei Symbole mit geringster WS werden Kinder eines neuen Knotens Erhalte Alphabet der Größe n-1 Neuer Knoten hat Summe der

Wahrscheinlichkeiten seiner Kinder4. Wiederhole Schritt 3 für alle Symbole5. Kodiere jedes linke Kind mit 0

Kodiere jedes rechte Kind mit 16. Speichere Huffman Kodierten Input


H U F M A N1/7 1/7 2/7 1/7 1/7 1/7

2/72/73/7

4/7

0

0 0

0

0

1

1

111

00 01 100 101 110 111

Speichere :100-01-00-00-101-110-111

ww

w.v

is.u

ni-s

tuttg

art.d

e Run length Encoding

Einfaches Verfahren Reduziert Redundanz Effizient bei sich häufig wiederholenden Symbolen Übertrage nur Symbol mit jeweiligem Multiplikator Für : AAAABBBCCCCCC => 4A3B6C Besonders für simple Bilder ( z.B. Binary ) geeignetPROBLEM :

Symbole mit nur sehr geringer Wiederholrate Kontinuierlicher Helligkeitsverlauf/-wechsel ist gewöhnlich

LÖSUNG : Modifizierter RLE mit Bitplane Encoding


ww

w.v

is.u

ni-s

tuttg

art.d

e Bitplane Encoding

Übersetze jeden Grauwert in seine 8 Bit Darstellung Beispiel 181 = 10110101

Zerlege das Gesamte Bild in Bitplanes : Für jede Bitstelle wird jeweils ein Bitplane generiert. Bitplane berücksichtigt nur diese eine Bitstelle Jeder Pixel wird im Bitplane mit seinem Wert an jeweiliger Bitstelle dargestellt Es entstehen also 8 Binärbilder Die „höherwertigen“ Bitplanes enthalten kaum Störungen , können also effizient

kodiert werden.PROBLEM: Selbst bei geringer Wertänderung können sich viele Bitstellen ändernLÖSUNG: Gray Code :

Kodiert den Wert so das beim Inkrementieren sich jeweils nur eine Bitstelle ändert


Quelle : Alessio Damato

ww

w.v

is.u

ni-s

tuttg

art.d

e Verlustbehaftete Kompression


Quelle : Cagri c. Tasci

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG Image Compression Standard

1992 von Joint Photographic Experts Group eingeführt Bietet 4 Kompressions Modi

Bekanntester Modus basiert Auf Diskreter Cosinus Transformation Kompression erfolgt in 6 Schritten

Farbraumwechsel Subsampling DCT auf 8x8 Pixeln Quantisierung der Koeffizienten Neuordnung der Koeffizienten Modifizierte Huffman Kodierung


ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG : Schritt 1 : Farbraumwechsel


Konvertiere den Farbraum von (R,G,B) zu (Y,Cb,Cr)

Originalbild (R,G,B)

Luminanz (Y)

Chroma ( Cb & Cr)Quelle : http://www.peter-junglas.de

Quelle : wikipedia

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG : Schritt 2 : Subsampling


Quelle : wikipedia

Luminanzinformation

Chromainformation

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG : Schritt 3 : DCT

Idee: Übersetzt einzelne Helligkeitswerte vom Ortsraum in Frequenzraum Frequenz soll Farb-/ Helligkeitswechsel repräsentieren

Vorgehen: Bild wird in 8x8 Pixel Blöcke zerlegt Jeder Pixel erhält Koeffizienten im Frequenzraum Für 0. Pixel wird Mittelwert des Blocks eingetragen Für alle anderen Pixel eine Veränderung zum Mittelwert DCT wird angewandt auf

Jeden der 8x8 Blöcke Jede Komponente des Farbraumes ( Y,Cb,Cr)


ww

w.v

is.u

ni-s

tuttg

art.d



DC

AC

AC

(7,7)

(0,0) Niedrige Frequenzen = langsame Änderung

F(7,7):Hohe Frequenz=Rasche Änderung

DC = F(0,0) enthält Mittelwert des Blockes

AC = F(0,1)….F(7,7) Speichert Veränderung zum DC

ww

w.v

is.u

ni-s

tuttg

art.d


Bei gewöhnlichen Bilder : kontinuierlicher Farbverlauf / Helligkeitswechsel Daher : Großteil der Informationen liegt in niedrigen Frequenzen => Werte konzentrieren sich in der oberen Linken Ecke


Quelle : Wikimedia commons

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG : Schritt 4 : Quantisierung

Hierbei entsteht der Großteil der Reduktion & Verlust Hohe Frequenzen werden aus den Blöcken entfernt. Niedrige Frequenzen bleiben erhalten Sämtliche Einträge werden auf simplere zahlen „getrimmt“ Dividiere Jeden DCT Eintrag durch Eintrag in einer Matrix

=> Matrix hat sehr hohe Werte in der unteren rechten Ecke Wahl dieser Matrix entscheidet über Qualität der Kompression. Wird für gewünschten Kompressionsgrad erstellt Je Kompressionsgrad : größere Quantisierung


ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG Schritt 5 : Anordnung der Koeffizienten


Generiert den Mittelwert (DC) am Anfang der Kette Gefolgt von den Frequenzen im Verhältnis zum DC Und anschließend viele „0“ in Folge Ermöglicht effizientere Kodierung

Quelle : https://www.imperialviolet.org/binary/jpeg/

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG Schritt 6 : Modifizierte Huffman Kodierung

Kodiert die entstandene Bitfolge mit modifiziertem Huffman Code Häufig auftretende Werte werden mit weniger Bits kodiert. Anschließend werden durch die Neuordnung entstandenen „0“-Ketten mit

RLE kodiert. Es werden deutlich weniger Bits zum kodieren benötigt


ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG : Auftretende Artefakte

Quelle: http://www.silvanti.com


ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG 2000

Verwendet Wavelet Transformation anstatt von DCT Keine periodischen Funktionen sondern „kurze Pulse“ Frequenz wird mit Ortsinformation kombiniert Gewisser Grad an Lokalität bleibt erhalten

Stärkere aber auch gezieltere Informationsreduktion Blockartefakte werden somit vermieden Effizientere Komprimierung möglich JPEG 2000 unterstützt zudem Alphakanäle


Quelle : Wikimedia commons

ww

w.v

is.u

ni-s

tuttg

art.d

e JPEG & JPEG 2000 vergleich


Quelle : home.htwg_konstanz.de

ww

w.v

is.u

ni-s

tuttg

art.d

e Literaturnachweis & Quellen

1. The JPEG still picture compression standard (1992) Gregory K. Wallace

2. An Image Multiresolution Representation for Lossless and Lossy Compression Amir Said and William A. Pearlman,

3. Digital Image Compression Techniques (1991) Majid Rabbani; Paul W Jones

4. Wie funktioniert eigentlich JPEG? (2011) Florian Kniedler

5. The Data Compression Book Mark Nelson , Jean-loup Gailly

6. Computergrafik.informatiker-wissen.de7. Progressive biplanes coding for lossless image compression

K. Funahashi, H. Kikuchi, and S. Muramatsu, 8. JPEG2000 Image Compression Standard (2012)

David Taubman, Michael Marcellin9. Compressed Image File Formats (1999)

John Miano10. JPEG: Still Image Data Compression Standard

William B. Pennebaker, Joan L. Mitchell


ww

w.v

is.u

ni-s

tuttg

art.d

e Literaturnachweis & Quellen

11. https://www.imperialviolet.org/binary/jpeg/12. A fast computational algorithm for the discrete Cosine Tranform

Wen-hsiung chen, Harrison Smith, S.C. Fralick13. Bitplane coding of DCT coefficients for image and video compression

Fan Ling, Weiping Li, Hongqiao Sun14. Grafikkodierung und –Kompression

Prof. Dr. Christoph Meinel15. www.itwissen.info


ww

w.v

is.u

ni-s

tuttg

art.d

e

Vielen Dank für ihre Aufmerksamkeit


Documents

Www.vis.uni-stuttgart.de Image compression Seminar : Bildverarbeitung und Computer Vision Betreuer : Prof. Dr.-Ing. Andrés Bruhn Wintersemester 2015/16