Druckdatei der Arbeit

Transcrição

Inhaltsverzeichnis
Einleitung
3
1.
Grundlagen I: Die menschliche Wahrnehmung
5
2.
Grundlagen II: Das digitale Bild
9
3.
Exkurs: Die digitale Aufnahme
22
4.
Das JPEG-Verfahren
24
5.
Farbraumveränderung
27
6.
Die Diskrete Kosinustransformation
28
7.
Quantisierung
47
8.
Codierung
49
9.
Decodierung der JPEG-Bilddatei
55
10. Verschiedene Dateitypen im Vergleich
58
11. Änderungen in JPEG2000
58
Resümee
59
Anhang
63
Die Autoren
72
Quellenverzeichnis
73
„Die JPEG-Kompression“ von Sebastian Wickenburg, Aeneas Rooch und Johannes Groß
2/73
Einleitung
Das Internet ist aus unserem heutigen modernen Leben nicht mehr wegzudenken: Ob man sich E-Mails schreibt
oder im Chatroom miteinander plaudert, im Web seine Bahnfahrkarte, Bücher oder CDs kauft, ob man sich über
das Kinoprogramm oder die Busfahrpläne informiert, per Internet seine Bankgeschäfte erledigt, Musik und
Software sowie Updates und Gerätetreiber herunterlädt, Computerzubehör und Autos ersteigert, in Foren mit
Leuten aus aller Welt über Fachliches diskutiert, für Hausaufgaben und wissenschaftliche Arbeiten recherchiert
oder ob man sich und seine Firma auf einer eigenen Homepage darstellt - das World Wide Web ist ein fester
Bestandteil unseres Lebens geworden.
Und schon längst ist es mehr als nur ein bloßes Netzwerk, es hat die Ebene einer serviceorientierten virtuellen
Umgebung erreicht, die von Konzernen und Firmen als Möglichkeit der Selbstdarstellung genutzt wird und in
der die verschiedenen Websites um die Gunst der Besucher kämpfen. Bunt, ansprechend, benutzerfreundlich und
"in" müssen Homepages heute sein.
Umso wichtiger für die Welt des Internets ist im Laufe der letzten Jahre das Bild geworden. Bloßer Text auf
Internetseiten ist langweilig, trocken und wirkt veraltet und unprofessionell. Schon längst ist das Bild mehr als
nur Illustration. Es macht das möglich, was die Mittel des Internets sonst nicht hergeben: eine individuelle und
ästhetische Gestaltung der Inhalte; das Bild ist Bestandteil des Layouts, es ist die Fassade nach außen.
Dementsprechend sind Bilder in der Welt des Internets nicht mehr wegzudenken, da sie das Erscheinungsbild
der Websites enorm bestimmen, sozusagen ihre Oberfläche sind, wie folgende Beispiele zeigt: Beim oberen Bild
ist eine Website 1:1 abgebildet, beim unteren sind alle Bilder (d.h. alle als Bilder definierten Objekte der
Homepage, z.B. auch bestimmter Text) weggelassen worden.
Viele Websites benutzen Bilder anstelle von Text, um ihr Erscheinungsbild plattformunabhängig und möglichst
absolut zu gestalten - so auch www.jaguar.de.
3/73
Ohne Bilder, das heißt auch ohne als Bilder definierte Textobjekte, ist die Page nutzlos.
Jedoch benötigen Bilder im Gegensatz zu reinem Text wesentlich mehr Speicherplatz (dieser Sachverhalt dürfte
allgemein bekannt sein; mathematisch wird er in dieser Arbeit u.a. im Kapitel 2 gezeigt). Da die Inhalte des
Internets über Datenleitungen übertragen werden, deren Kapazität begrenzt ist, wird also ständig nach einer
Möglichkeit gesucht, speicherintensive Objekte, also umfangreiche Datenmengen, zwecks eines schnelleren
Transportes zu verkleinern.
Datenkompression gibt es nicht erst, seit das Internet die Haushalte der Normalbürger erobert hat, ganz im
Gegenteil: Seit Daten (jeder beliebigen Art) ausgetauscht werden, wird schon aus Bequemlichkeit nach
Möglichkeiten gesucht, den Umfang des Auszutauschenden zu verkleinern (z.B. durch Abkürzungen beim
Schriftwechsel), was mit der Weiterentwicklung der Telekommunikation natürlich zunehmend wichtiger
geworden ist. Gerade im Internet begegnen wir heutzutage täglich ausgefeilten Methoden der
Datenkomprimierung, ohne es zu merken.
Die bekannteste Art der Internet-Datenkompression transparent zu machen und darzustellen, ist Ziel dieser
Arbeit.
Wir werden erläutern, wie man heute mit ausgearbeiteten mathematischen Methoden Bilddaten verkleinert und
gleichzeitig den Verlust an Bildqualität möglichst gering hält. Wir betrachten, erklären und veranschaulichen die
Arbeitsweise und die mathematischen Hintergründe des Grafikformats JPEG, des bekanntesten und am weitesten
verbreiteten Bildformates im Internet. Zuvor werden wir dazu klären müssen, wie Bilder vom menschlichen
Auge überhaupt "gesehen" werden, wie sie technisch in Daten umgewandelt werden und wie sogenannte
"digitale Bilder" beschaffen sind und wie sie "funktionieren". Schließlich blicken wir in die nähere Zukunft und
beleuchten die neuesten, jedoch noch nicht als Standard etablierten Techniken der Bildkomprimierung fürs
Internet.
Wer nun anmerkt, einige Kapitel (z.B. Kapitel 1 über die menschliche Wahrnehmung) hätten mit Mathematik
wenig zu tun, der möge beachten, dass man "Mathematik im Alltag" schwer anschaulich und für alle Leser (mit
unterschiedlichen Vorkenntnissen) verständlich darstellen kann, ohne die umliegenden anderen Wissensgebiete
zu betrachten, die mit der Mathematik in diesem Thema zusammenhängen.
Eine Zusammenfassung dieser Arbeit (ohne detaillierte Erläuterungen) können Sie im Kapitel „Resümee“ lesen,
um sich einen ersten überblick zu verschaffen oder bereits Bekanntes zu wiederholen. Ansonsten führt Sie diese
Arbeit Schritt für Schritt mit ausführlichen Erklärungen und Beispielen durch die Thematik.
4/73
1 Grundlagen I: Die menschliche Wahrnehmung
Diese Arbeit beschäftigt sich damit, wie digitalisierte Bilder so bearbeitet werden können, dass sie weniger
Speicherplatz in Anspruch nehmen, trotzdem aber möglichst wenig von ihrer Qualität einbüßen müssen. Es ist
naheliegend, sich ganz zu Anfang einen überblick zu verschaffen, wie wir überhaupt "sehen".
1.1 Anatomie und Physiologie
Die Bilderzeugung im Auge funktioniert wie in einer mechanischen Kamera: Wir "sehen", indem Lichtstrahlen
durch die Pupille und die Linse ins Auge fallen. An der Linse (und auch an der Hornhaut, die zu vernachlässigen
ist) werden die Lichtstrahlen gebrochen; sie bündelt diese und sorgt für ein klares Abbild der Umgebung auf der
Netzhaut, die sich an der Rückwand des Auges befindet. Feine Muskelfasern zwischen Linse und der festen,
äußeren Haut des Augapfels können die Dicke der Linse durch Streckung verändern, sodass sowohl von
nahegelegenen als auch von weiter entfernten Gegenständen ein scharfes Bild auf der Netzhaut entsteht. Die
Netzhaut ist eine Schicht aus feinen lichtempfindlichen Rezeptoren und dünnen Nervenzellen, die in
verschiedene Gruppen geteilt sind:
-
Mit den Stäbchen können wir Lichtintensität unterscheiden, jedoch keine Farben. Mit ihnen sehen
wir in der Dämmerung (deshalb auch das Sprichwort, nachts seien alle Katzen grau).
-
Mit den Zäpfchen sehen wir nur, wenn es hell ist, mit ihnen können wir Farben wahrnehmen. Es wird
angenommen, dass es drei Sorten von Zäpfchen gibt, die eine charakteristische Empfindlichkeit auf das
Farbspektrum aufweisen, wie in der untenstehenden Grafik verdeutlicht.
Stäbchen und Zäpfchen leiten den Lichteindruck ins Gehirn weiter, wo bestimmte Teile des Gehirns die Signale
empfangen und verarbeiten. Nun erst sehen wir.
Anatomie des menschlichen Auges: 1=Linse / 2=Hornhaut / 3=Iris,Regenbogenhaut /
4=Pupille / 5=Gelber Fleck / 6=Blinder Fleck (Bild: NightSky).
Die Zäpfchen finden sich am engsten "zusammengepackt" im Zentrum der Netzhaut, das man "gelber Fleck"
nennt; an dieser Stelle ist die Netzhaut am empfindlichsten und die Auflösung, mit der wir sehen, am größten. Je
weiter wir uns vom gelben Fleck entfernen, desto weniger Zäpfchen finden wir vor und desto mehr wird ergo
5/73
mit den Stäbchen gesehen. Dort, wo der Sehnerv das Auge verlässt, sitzen logischer Weise gar keine Sehzellen,
man spricht hier vom blinden Fleck.
Nachdem Licht durch Hornhaut und Linse gefallen sowie dort gebrochen und gebündelt worden ist, reagieren
Nervenzellen an der Netzhaut auf die Lichtsignale und leiten sie weiter zum Gehirn (Bild: Chibret Augenatlas, 1998).
Bedingt durch die "Bauteile" des menschlichen Auges sind unserer Wahrnehmung Grenzen gesetzt:
-
Auflösung: Insgesamt 6 Millionen Zapfenzellen und 130 Millionen Stabzellen finden sich auf der
menschlichen Netzhaut (die größte Dichte der Zäpfchen ist wie gesagt am gelben Fleck, wo sich knapp
160.000 Zapfenzellen pro Quadratmillimeter befinden). Eine ganz alltägliche CCD-Kamera kann da
nicht mithalten: Ihr Sensor-Array verfügt meist nur über 756x581, also etwa 440.000 Bildpunkte.
-
Farben: Wie wir auch noch ausführlich darstellen werden, können digitale Bilder bis zu 256
Graustufen und Farbbilder bis zu etwa 16,7 Millionen verschiedene Farbtöne aufweisen, was ein
bisschen Verschwendung ist, da unser Auge nur etwas weniger als 100 Grautöne und etwa 7 Millionen
Farben unterschieden kann.
1.2 Wahrnehmungspsychologie
Wie gerade eben beschrieben, nehmen wir Farben über die Rezeptoren für farbiges Licht (rot, grün, blau) in der
Netzhaut auf. Da die Empfindlichkeit dieser Rezeptoren für andere Farben genetisch kodiert ist, unterscheidet sie
sich bei allen Menschen. Jeder Mensch hat demnach ein anderes Farbempfinden.
Die Auswirkungen menschlicher Reaktionen auf das Erscheinen einer bestimmten Farbe sind verallgemeinerbar
(obgleich der biologische Hintergrund immer noch nicht hinreichend geklärt ist): Farben, die man z.B. mit
Geschwindigkeit und Schnelligkeit verbindet und die man als anregend und lebhaft empfindet, sind warm und
kräftig (zum Beispiel: Rot, Gelb, Orange). Kalte Farben (wie Blau und Grün) wirken hingegen beruhigend oder
entspannend. Auch die Intensität der Farben spielt eine Rolle: Sanfte Farben mit wenig Intensität vermitteln
Geborgenheit und Bequemlichkeit, starke Farben mit hoher Intensität wirken aggressiver.
6/73
Farben wie gelb und Orange werden als warm und lebendig empfunden wie bei "Mädchen mit blauen Vögeln" (August Macke) und "Die Wahrsagerin" (Michelangelo Caravaggio)
(Bilder: http://reisserbilder.at).
Marc Chagalls "Blumenstilleben" und Claude Monets "Impression (Bütten)" zeigen:
Farben wie Blau und Grün wirken beruhigend und kühl
(Bilder: http://reisserbilder.at).
Es spielt auch eine Rolle, in welcher Umgebung eine bestimmte Farbe gesehen wird. Je nach den Farbtönen, die
eine bestimmte Farbe einfassen, wird diese Farbe in unterschiedlichen Tönungen wahrgenommen. Darüber
hinaus ist sicherlich jedem bekannt, dass nicht nur Farben, sondern auch Größe und Verhältnisse unterschiedlich
wahrgenommen werden, abhängig von ihrer Umgebung. Dies sei hier nicht weiter vertieft.
1.3 Farben
Bevor wir uns den Grundlagen der Bilddigitalisierung widmen und dem eigentlichen Thema der
Bildkompression nähern, betrachten wir zunächst einmal, was Farben überhaupt sind und wie der Mensch sie
(z.B. bei der digitalen Bildverarbeitung) darstellen kann.
Das für den Menschen sichtbare Licht nimmt nur einen ganz kleinen Teil des Wellenspektrums ein. Je nach
Länge der Wellen in diesem Spektrum erscheint ein Lichtstrahl in einer bestimmten Farbe: Ein Lichtstrahl mit
einer Wellenlänge von 700nm erscheint zum Beispiel rot, ein Lichtstrahl mit einer Wellenlänge von ca. 500nm
7/73
erscheint blau. Wenn ein weißer Lichtstrahl (ein Gemisch aller Wellenlängen, wie nachher ausführlich gezeigt
wird) auf eine Fläche trifft, die alle Wellenlängen außer Rot absorbiert, dann erscheint diese Fläche rot.
Wenn wir nun einen bestimmten Farbton mathematisch beschreiben wollen, gibt es mehrere Möglichkeiten, da
Farben über verschiedene Schemata definiert werden können (vergleichbar ist dieses mit verschiedenen
Zahlenmengen, die es gibt: eine bestimmte ganze Zahl kann als Dezimalzahl, Bruch und Wurzel geschrieben
werden, es handelt sich aber stets um die gleichen Zahl).
Das RGB-Modell, das man auch additive Farbmischung nennt, baut auf den drei Grundfarben Rot, Grün und
Blau auf, aus denen sich jede andere Farbe mischen lässt. Werden alle drei Farben zu gleichen Teilen (also mit
gleicher Intensität) gemischt, erhalten wir weißes Licht. Auch das Sonnenlicht enthält diese drei Grundfarben.
Die subtraktive Farbmischung oder auch CMYK bedient sich der Farben Cyan, Magenta und Gelb. Eine
Mischung dieser drei Komponenten ergibt in der Theorie Schwarz, in der Praxis allerdings nur ein sehr dunkles
Braun. Durch Zugabe von Schwarz (auch Tiefe genannt) enthält man auch im Bereich der sogenannten unbunten
Farben (Grau, Schwarz, Weiß) eine gute Reproduktionsqualität.
Das HSB-Modell entspricht unserer verbalen Farbbeschreibung am meisten: Während es enorm schwierig ist,
ein "blasses Lila" in RGB oder CMYK zu beschreiben (die mathematische Darstellung eines solchen Farbtones
in verschiedenen Formaten ist unten zu finden), lässt sich eine solche Farbbeschreibung in HSB recht schnell
umsetzen. Das System beinhaltet nämlich die Komponenten Farbton (Hue), Sättigung (Saturation) und
Helligkeit (Brightness). Die Farbton-Komponente gibt die reine Farbinformation an, die Skala reicht hier bis 360
Grad. Die Sättigung gibt das Verhältnis zwischen der reinen Farbstärke und den unbunten Anteilen an (0% ist
also immer ein Grauwert und 100 % die kräftigste, reine Farbe). Die Helligkeit entspricht der Helligkeit von 1%
bis 100%. Dabei stellt 0% immer Schwarz dar, 100% immer Weiß.
An späterer Stelle werden wir das YUV-Modell erwähnen, welches im Prinzip das gleiche wie das HSB-Modell
ist, nur sind die Komponenten anders angeordnet und anders benannt: Y=Luminanz (Helligkeit), U=Farbton,
C=Chrominanz (Farbsättigung).
Der gleiche Farbton - über 3 veschiedene Skalen beschrieben
8/73
2 Grundlagen II: Das digitale Bild
Um Bilder mit Computern darstellen und speichern (sprich: verarbeiten) zu können, müssen diese in einem
digitalen Format vorliegen, d.h. so beschaffen sein, dass sie rechnerisch zu erfassen und alle wichtigen
Informationen (Farbe, Größe, Helligkeit - eben alles, was ein Bild ausmacht und definiert) aus ihnen anhand von
Daten zu entnehmen sind. Wissenschaftlich und ganz allgemein lässt sich sagen: Ein Bildformat ist eine
Ansammlung von Daten, die ein Bild beschreiben. Dabei spielen die Organisation und die Struktur dieser Daten
eine entscheidende Rolle (entsprechend gibt es, wie noch dargestellt wird, große Unterschiede zwischen
verschiedenen Bildformaten, die Daten auf unterschiedliche Weise organisieren). Eine übersicht über
verschiedene Bildformate und ihre Eigenschaften gibt das Kapitel 10.
Die Digitalisierung, also der Prozess, bei dem aus einem Bild für einen Computer lesbare Daten gemacht
werden, erfolgt bei der Bildaufnahme durch einen Scanner oder eine Digitalkamera, wobei natürlich die Art und
Technik der Bildaufnahme für die Qualität der Daten, die am Ende herauskommen, entscheidend ist. Eine
technisch detaillierte Beschreibung, wie Bilder in Digitaldaten umgewandelt werden, können Sie im nächsten
Kapitel lesen.
2.1 Das Pixelformat (Bildmatrizen)
Prinzipiell unterscheidet man bei digitalen Bilddaten zwischen zwei Arten.
Zum einen gibt es Vektorbilder. Bei diesen werden Linien, Flächen und Polygonzüge gespeichert, die
mathematisch recht einfach durch Vektoren beschrieben werden können. Die Vor- und Nachteile liegen auf der
Hand: Vektorformate sind beliebig skalierbar (vor allem sind sie ohne Qualitätsverlust vergrößerbar), da das
Bild, egal in welcher Größe, stets auf der Grundlage der vektoriellen Daten berechnet wird. Bilder, die in einem
solchen Format vorliegen, zeigen in der Regel mathematisch konstruierbare Objekte, Comics und Illustrationen,
da diese durch Linien beschrieben werden können. Für komplexe Bilder (wie Fotos oder vielfarbige
Darstellungen) eignet sich diese Speichermethode hingegen nicht, da sich derartige Bildinhalte nicht
mathematisch konstruieren lassen, ergo auch nicht sinnvoll als Vektorbild gespeichert werden können.
Wir befassen uns in dieser Arbeit mit der anderen Art, Bilder digital zu speichern, den Pixelbildern. Bei dieser
Methode der Datenspeicherung wird das kontinuierliche Bild räumlich diskretiert, d.h. es wird in kleine Punkte
zerteilt, deren Farbe jeweils einzeln angegeben wird. Diese Punkte sind die kleinsten Einheiten eines Bildes. Sie
sind (aus technischen Gründen, die mit den Aufnahmesystemen zusammenhängen, vgl. Kapitel 3) quadratisch
und werden Pixel (picture elements) genannt. Man stell sich ein digitales Bild
Zeilen und
Zeilen, also
Pixel, d.h. Bildpunkte hat:
mit
Die Elemente
Stelle
des Bildes
also als eine Matrix vor, die
und
.
sind die Pixel, die den Grauwert oder die Farbe des Bildpunktes an der
angeben. Man beachte bei der Bezeichnung, dass
die erste Zeile einer Matrix die Zeile
sowie die letzte Zeile die Zeile
Wie solche Bildmatrizen formatintern organisiert werden, d.h. wie die Zahlenwerte
Bildformaten gespeichert werden, wird später im Kapitel 2.4 erläutert.
und
gilt, da
ist.
in unterschiedlichen
9/73
Bei starker Vergrößerung sind die einzelnen Bildpunkte gut erkennbar (Bild: Kai's Power Goo).
Betrachten wir an dieser Stelle einmal den Zusammenhang zwischen Pixelanzahl und Erscheinungsform des
Bildes, um die Beschaffenheit des Pixelsystems deutlich zu machen.
Wie eben erwähnt, wird das vorliegende Bild beim Digitalisieren räumlich diskretiert, das heißt, es wird in
Bildpunkte zerlegt. Diesen Vorgang nennt man Rasterung. Hierbei ist wichtig, wie groß der Bildbereich ist,
dem ein Pixel zugeordnet wird. Denn 1 Pixel ist lediglich definiert als 1 Bildpunkt, und beim Digitalisieren kann
man selbst bestimmen, wie groß so ein Pixel denn nun sein soll (wie bereits angedeutet, ist die Größe, die ein
Pixel hat, auch durch das Aufnahmeverfahren technisch bedingt, siehe Kapitel 3). Je mehr solcher Punkte ein
Bild nun hat (d.h.: je kleiner der Bereich ist, den wir als Pixel definieren), desto höher ist die Auflösung, wie
folgendes Beispiel veranschaulicht:
Die unterschiedliche Auflösung bei der Bildaufnahme verursacht die Qualitätsunterschiede (Bild: Mustang Multimedia
Spezial).
10/73
Eine hohe Auflösung benötigt also eine große Anzahl von Pixeln. Entsprechend beansprucht ein
hochauflösendes Bild mehr Speicherplatz und Kapazität bei der Verarbeitung als eine Aufnahme mit niedriger
Auflösung, d.h. mit wenigen Bildpunkten. Schon hier wird das Ziel der Bild-Kompression deutlich: Eine
Verringerung der zu speichernden Daten bei möglichst gleichbleibender Qualität (denn einfach nur die
Auflösung zu verkleinern, ist nicht zweckmäßig, da das Bild sich so qualitativ verschlechtert).
Jedoch kann ein Bild bei der Digitalisierung nicht nur räumlich, sondern muss auch "farblich" diskretiert werden,
um später alle Informationen der ursprünglichen Abbildung enthalten zu können: Das Ausgangsbild wird 1.
zerlegt in Pixel, von denen 2. jeder einzelne eine Farbinformation enthält. Wird der Farbwert (oder Grauwert,
wenn es sich nicht um eine Farbaufnahme handelt) diskretiert, spricht man von der Quantisierung. Mit diesem
einfachen Modell - Rasterung und Quantisierung - ist ein Bild hinreichend beschrieben.
Wird nun ein Bild quantisiert (wir gehen hier der Einfachheit halber von einem Bild in Graustufen aus), so misst
das Aufnahmesystem (z.B. ein Scanner) die mittlere Helligkeit über einem Pixel, dessen Größe vorher definiert
wurde. Dazu bildet es den gemessenen Grauwert auf eine Skala ab, die (in der Regel) 256 Abstufungen zwischen
schwarz und weiß bietet (es sind auch mehr Abstufungen möglich), und ordnet jedem Helligkeitswert einen
Zahlenwert auf der Skala zu. Handelt es sich um ein Bild in reinem schwarz/weiß (man spricht dann von einem
Binärbild, weil nur zwei Farbabstufungen vorkommen, von gr. bi = zwei), hat diese Skala nur zwei Werte.
Zum Vergleich: Verschiedene (Tonwert-)Skalen, auf die das Ausgangsbild abgebildet wird (Bild: Mustang Multimedia
Spezial).
Wie man vorstellen kann, bestimmen die Anzahl der Grautöne (also die Größe der Skala) und die Anzahl der
Pixel (die Größe eines Bildpunktes) die Datengröße des Bildes. Eine Aufnahme, die nur über die 2 Farben
schwarz und weiß verfügt und in einer Auflösung von z.B. 16x16 Pixel gespeichert ist, benötigt weniger
Speicherkapazität als eine Aufnahme, die über 256 Grautöne verfügt und in einer Rasterung von 64x64 pixel
vorliegt.
Ein konkretes Beispiel zeigt den Zusammenhang zwischen Rasterung und Quantisierung; bei konstanter
Speicherkapazität von 1 Kilobyte können zwei Bilder mit folgenden Eigenschaften gespeichert werden:
11/73
a)
64x64 Pixel mit 4 Graustufen = 4096x2 Bit = 1 kByte
b)
32x32 Pixel mit 256 Graustufen = 1024x8 Bit = 1 kByte
Hier verwenden wir bereits die Größen Bit und Byte, die im Zusammenhang mit Speicherbedarf und Datengröße
Verwendung finden und in der Regel bekannt sind. Genaue Definitionen und Erklärungen zu diesen Größen gibt
es im Kapitel 2.2 sowie im Kapitel 3.
Da Rasterung und Quantisierung gleichermaßen die Datenmenge eines Bildes bestimmen, kann zum Beispiel
eine grobe Rasterung, die zu einem erheblichen Qualitätsverlust führen würde, durch eine feinere Quantisierung
ausgeglichen werden. Ein Bild, das also schlecht aufgelöst ist, bleibt dadurch erkennbar, dass es über viele
Farbinformationen verfügt. Das Zusammenspiel von Auflösung und Anzahl der Graustufen, also über Rasterung
und Quantisierung, veranschaulichen folgende Grafiken:
Wie Rasterung und Quantisierung die Bildqualität beeinflussen: a) Originalzeichen, b) grob binär digitalisiert
(=2 Farben, geringe Auflösung 10dpi), c) fein binär digitalisiert (=2 Farben, mittlere Auflösung 30dpi), d)
grobe Rasterung, feine Quantisierung (=8 Farben, niedrige Auflösung 10 dpi)
Es wird deutlich: Rasterung und Quantisierung haben Auswirkungen auf die Bildqualität: Durch zu geringe
Quantisierung oder Rasterung gehen Bildinformationen verloren. Mehr noch: Es kommen gegebenenfalls sogar
noch Störungen hinzu. Dies ist unter anderem bei der digitalen Aufnahme mit grober Abtastung von
Rasterbildern der Fall, wenn Bilder gescannt werden, die aus feinen Mustern, wie eben dem Punktraster eines
Fotos oder einer schraffierten Fläche, bestehen. Die auftretenden periodischen Störungen nennt man Aliasing,
bei Störungen in einem Punktraster spricht man vom Moiree-Effekt.
Eine schraffierte Fläche wurde beim Digitalisieren zu grob abgetastet. Folge: Es entstehen periodische
Störungen, sogenannte Aliasing-Effekte.
12/73
Wird ein Punktraster zu grob abgetastet, entstehen auf dem Bild ebenfalls periodische Störungen, sogenannte
Moiree-Effekte.
2.2 Grundlagen der Datenspeicherung
Nun da wir wissen, dass digitalisierte Bilder als zweidimensionale Funktionen verstanden werden können, die
räumlich und farblich diskretiert sind, also jeder Pixel der Bildmatrix durch einen Wert beschrieben wird,
betrachten wir, welche Eigenschaften dieser Wert (lassen wir den Begriff vorerst ganz allgemein) annehmen
kann, was er aussagt und wie sich verschiedene Werte auf die Speicherung des Bildes auswirken.
Wie bereits gesagt, gibt der Wert, den ein Bildpunkt annehmen kann, die Farbe oder den Grauwert an. Dies
wollen wir nun präzisieren: Liegt ein Bild in Graustufen vor (normaler Weise verfügen "normale" Bilder über
256 verschiedene Grautöne), ist der Pixelwert eine skalare Größe und gibt die Helligkeit an (0=schwarz,
255=weiß). Mathematisch ist ein herkömmliches Graustufenbild also folgendermaßen definiert:
mit
und
und
.
Bei Farbbildern verhält es sich ähnlich. Wie eingangs erwähnt (Kapitel 1.3), können alle für den Menschen
sichtbaren Farben additiv mit den Grundfarben Rot, Grün und Blau gemischt werden. Dieses System hat sich
auch in der digitalen Welt durchgesetzt: Beim RGB-Format beinhaltet ein Pixel die exakte Farbinformation, also
3 verschiedene Werte; der Pixelwert kann hier als dreidimensionaler Vektor aufgefasst werden, der über seine
Komponenten die Rot-, die Grün- und die Blauintensität des Pixels angibt.
Werden digitale Daten (ganz allgemein, nicht nur Bilder) gespeichert, so liegt dem Speicherprozess ein binäres
System zu Grunde, das zwischen 0 und 1 unterscheidet. Die kleinste Speichereinheit, die entweder 0 oder 1 sein
kann, nennt man "Bit". Eine Gruppierung von 8 Bit wird "Byte" genannt (siehe „Hintergrund-Information zu
Bits und Bytes“).
Wird nun ein digitales Graubild gespeichert, so nimmt jeder der Pixel einen Wert zwischen 0 und 255 an. Diese
Werte werden binär gespeichert, das heißt, dass 0 dem binären Wert 0 entspricht, 92 zum Beispiel dem Wert
1011100 und 255 dem Wert 11111111. Maximal werden also 8 Zeichen (0 oder 1) benötigt, um jeden beliebigen
Wert zwischen 0 und 255 darzustellen, man spricht dann von einem Bild mit 8-Bit-Farbtiefe (da das Binärsystem
ein System von 2er-Potenzen ist, kann man allgemein sagen: Mit einer Maximalanzahl, d.h. einer Farbtiefe von
Bit kann man bis zu
verschiedene Farbwerte speichern, wobei
).
13/73
Verschiedene Grauwerte und ihre binären Entsprechungen
2.3 Globale Eigenschaften von digitalisierten Pixelbildern
In den folgenden Abschnitten wollen wir untersuchen, wie sich optische Unterschiede zwischen Bildern
mathematisch ausdrücken, wie sich zum Beispiel hohe Helligkeit oder niedriger Kontrast in der Pixelmatrix des
Bildes äußern. Wir gehen dabei (der Einfachheit halber, es geht ja schließlich um die Darstellung des Prinzips)
von Graustufenbildern aus, die eine Farbtiefe von 8 Bit haben, also über 256 verschiedene Graustufen verfügen
(dieses ist auch das gängige Format für Graustufenbilder in der Praxis).
Das augenfälligste Merkmal eines Bildes ist sicherlich seine Helligkeit. Dem Betrachter fällt beim ersten
Ansehen eins Bildes sofort auf, ob es insgesamt zu hell oder zu dunkel ist. Hier ist es zweckmäßig, zur
Beurteilung der Helligkeit, den mittleren Grauwert zu bestimmen, also den durchschnittlichen Grauwertwert,
den alle Pixel des Bildes haben. Wie schon aus der Statistik der Mittelstufe bekannt, summiert man dazu alle
Grauwerte und teilt sie durch die Anzahl der Summanden.
Bzw. kurz geschrieben:
Dieser mittlere Grauwert ist in vielen Fällen nützlich, da er eine brauchbare Charakterisierung der Helligkeit des
Bildes liefert, jedoch führt er (wie jeder Durchschnitt, da er extreme Ausreißer nicht berücksichtigt) in manchen
Fällen auch auf eine falsche Spur, wie folgende Beispiele zeigen:
-
für ein gleichmäßig gefärbtes Bild
-
für ein stark unterbelichtetes Bild
mit exakt mittlerer Helligkeit ist
ist
14/73
-
für ein stark überbelichtetes Bild
ist analog
-
für ein Bild
-
der mittlere Grauwert des Sonnenuntergang-Bildes beträgt
-
der mittlere Grauwert des Bildes mit den Löwen beträgt
mit schwarz-weißem Schachbrettmuster ist
Das Bild mit den Löwen ist vergleichsweise hell, daher ist der mittlere Grauwert auch größer als beim
Sonnenuntergangsbild, das insgesamt eher dunkel ist (Bilder: Kai's Power Goo).
Beim Betrachten der Beispiele wird deutlich, dass der mittlere Grauwert mit Vorsicht zu genießen ist: So ist zum
Beispiel der Wert eines homogen gefärbten Bildes mittlerer Helligkeit mit dem eines Schachbrettmusters
identisch, weil der Durchschnitt der Grauwerte gleich ist, nur werden diese Bilder sicherlich verschieden
wahrgenommen. Im folgenden definieren wir daher ein weiteres wichtiges Charakteristikum, das uns
Informationen über die Beschaffenheit eines Bildes gibt.
Aus der Statistik ist bekannt, dass man zur Beurteilung einer Verteilung (wir betrachten das digitalisierte Bild ja
als Verteilung verschiedener Grauwerte, daher die Analogie) untersucht, wie sehr die einzelnen Werte gestreut
sind, das heißt, wie sehr sie vom Mittelmaß abweichen. Zweckmäßig ist hier, die mittlere quadratische
Abweichung (oder auch: Varianz) zu bestimmen, da bei diesem Streuungsmaß keine negativen Ergebnisse
auftreten können (diese werden durch das Quadrieren eliminiert) und auch Daten, die besonders stark vom
Mittelwert abweichen und somit das Aussehen des Bildes stark beeinflussen (vgl. Schachbrettmuster und
eintönig mittelgrau eingefärbtes Bild), durch die Quadrierung stärker ins Gewicht fallen als diejenigen in der
Nähe des Mittelmaßes. Die Varianz, die angibt, wie sehr die einzelnen Grauwerte
abweichen, ist definiert durch:
vom Mittelwert
Da stärkere Abweichungen vom Mittelwert mehr ins Gewicht fallen als Grauwerte nahe des Mittelwertes, ist
ein Maß für den Kontrast. Während die beiden Fälle "Schachbrett" und "homogenes Mittelgrau" die gleiche
mittlere Helligkeit aufweisen, zeigen sich nun in der Varianz große Unterschiede:
-
das homogene Graubild besitzt nur einen Farbton, die mittlere quadratische Abweichung ist also
15/73
-
bei einem Schachbrettmuster (die Größe spielt keine Rolle, da schwarz und weiß zu gleichen Anteilen
über das Bild verteilt sind, daher in der folgenden Rechnung auch Division durch 2) beträgt die Varianz
Das Schachbrett-Bild hat also einen hohen Kontrast (wie trivial zu erkennen: den höchstmöglichen), das
homogene Bild mit mittlerem Grau gar keinen.
Mit den beiden Maßen Mittelwert und Varianz haben wir nun zwar zwei Kriterien definiert, mit denen wir
globale, statistische Aussagen über ein Bild machen können, jedoch ist es weiterhin sinnvoll zu erfahren, wie
groß der Anteil der einzelnen Grauwerte am Gesamtbild ist. Wir führen also Histogramme ein, an denen solche
quantitativen Aussagen abzulesen sind:
Das Histogramm gibt für jeden Grauwert
aus der Menge aller Grauwerte
im Bild
oder relative Häufigkeit
sowie
eines Bildes
seine absolute
an. Wie für alle relativen Häufigkeiten bei Verteilungen gilt also:
,
da die relative Häufigkeit eines Grauwerts nicht negativ oder > 1 sein kann und da die Summe aller Häufigkeiten
zusammen immer 1 ergeben muss (mehr als 100% Anteil an einem Bild können Grautöne ja nicht haben). An
einigen Beispielen wollen wir die Eigenschaften von Histogrammen zeigen:
-
bei einem gleichmäßig mit dem Grauton
eingefärbten Bild erhalten wir für den Grauton
und alle anderen (im Bild nicht vorhandenen Grautöne)
-
und
bei einem ausgewogenen Bild (ausgewogene Helligkeit, ausgewogener Kontrast) kommen alle 256
Grauwerte
alle
-
die Häufigkeiten:
etwa in gleichem Umfang vor; im optimalen Fall erhalten wie also
bei einem dunklen Bild mit wenig Kontrast erhalten wir für die niedrigen Grauwerte
für
, die die
dunklen Bildpartien ausmachen, hohe Werte für
-
Ein Schachbrett sowie alle anderen Bilder, die ebenfalls die 2 Farben schwarz (0) und weiß (255)
gleich häufig enthalten, hat folgende Verteilung:
und
-
sowie
für alle anderen Grautöne
untenstehende Histogramme zeigen die Grauwertverteilungen für die Beispielbilder
"Sonnenuntergang" und "Löwen" sowie für einen (nahezu) homogenen Verlauf von schwarz nach weiß
16/73
Das Löwen-Bild ist recht ausgewogen, es verfügt über einige dunkel und einige helle Partien, die meisten
Bildanteile liegen jedoch im mittleren Skalen-Bereich (Bilder: Kai's Power Goo).
Das Sonnenuntergang-Bild ist insgesamt dunkel, so zeigt das Histogramm eine große Häufigkeit von schwarzähnlichen Grauwerten; der mittelgraue Himmel sorgt ebenfalls für einen starken Ausschlag des Histogramms,
helle Bildbereiche fehlen fast vollständig (Bilder: Kai's Power Goo).
Beim fast homogenen Farbverlauf von schwarz nach weiß treten alle 256 Grautöne in gleicher Häufigkeit auf,
daher ist das Histogramm auch annähernd gleichmäßig (kleinere Unterschiede sind durch die
Messungenauigkeit und Bildschirmdarstellung bedingt).
Histogramme geben, wie hier deutlich wird, keine Auskunft darüber, wo sich die einzelnen Grauwerte räumlich
befinden, sondern zeigen lediglich ihre Häufigkeit im Bild an (benötigt man örtliche Aussagen, kann man
Histogramme an Linien ausrichten, die durch das Bild gehen, und so zu jedem Punkt auf der Linie den dort
17/73
gemessenen Grauwert erhalten; solche Histogramme nennt man Grauwertprofile, auf die jedoch hier nicht
näher eingegangen wird).
Kurze Erwähnung sollten hingegen die relativen Summenhäufigkeiten finden. Während die
Grauwerthäufigkeit
Summenhäufigkeit
Natürlich muss gelten:
die Häufigkeit eines einzelnen Grauwertes
im Bild angibt, gibt die relative
Auskunft darüber, wie hoch der Anteil aller Grauwerte
, da - wie bereits gezeigt - schon
unterhalb von
gilt und da in
extremen Fällen entweder gar kein Grauwert oder alle Grauwerte des Bildes unterhalb von
Funktion
ist:
liegen. Die
ist somit monoton steigend.
Die relative Summenhäufigkeit für den Grauwert 120 beträgt 0,3986, das heißt: Die Grauwerte zwischen 0 und
120 sind im Bild mit etwa 40% vertreten.
Zuletzt in diesem Kapitel führen wir den Begriff der Entropie ein. Da es sich dabei um ein Maß des
durchschnittlichen Informationsgehaltes eines Bildes handelt, passt es ganz gut zum Oberbegriff "Globale
Eigenschaften", auch wenn wir die Entropie später noch einmal ausführlich aufgreifen werden (Kapitel 8).
Die Entropie
gibt die minimale Anzahl von Bits an, die man benötigt, um ein Pixel im Bild zu speichern,
und ist somit auch eine Anzeige, ob man mit Kompressionstechniken überhaupt den Speicherplatzbedarf
verringern kann. Sie ist definiert durch:
Betrachten wir zum besseren Verständnis, was die Entropie angibt, ein paar Beispiele:
-
bei einem gleichmäßig mit dem Grauton
-
bei einem Bild mit ausgewogener Helligkeit und ausgewogenem Kontrast kommen alle 256 Grauwerte
eingefärbten Bild erhalten wir für die Entropie
etwa in gleichem Umfang vor, es gilt also für jeden Grauwert
; die Entropie ist in
diesem Falle (jeder Grauwert ist gleichhäufig, daher kann man statt der Summierung den Term unter
der Summe mit der Anzahl der Graustufen, mit 256, multiplizieren):
18/73
. Jeder einzelne Pixel benötigt
also 8 Bit, sprich 1 Byte, wenn man ihn ohne Verluste speichern möchte.
-
Ein Schachbrett sowie alle anderen Muster, die nur 2 Grautöne
und
Häufigkeit vorkommen, hat die Entropie 1, da:
enthalten, die in gleicher
und somit
Gehen wir davon aus, dass uns keine weiteren Informationen über das Bild vorliegen, wird 1 Bit pro
Pixel benötigt, um das Bild zu speichern.
-
Liegt ein Binärbild vor, dessen Farben schwarz und weiß unterschiedlich oft auftreten, zum Beispiel
und
, so beträgt die Entropie:
Für ein solches Bild würde also weniger als 1 Bit zur verlustfreien Speicherung eines Pixels benötigt.
Dieses kann durch geeignete Kompressionsmethoden erreicht werden.
Eine Herleitung der angegebenen Entropie-Fomel sowie Erklärungen zum besseren Verständnis liefern wir in
Kapitel 8, wenn uns die Entropie thematisch wieder begegnet. An dieser Stelle reicht erst einmal die reine
Kenntnis der Formel.
2.4 Datenstruktur
Nachdem wir nun wissen, was digitale Bilder genau sind, welche Charakteristika sie aufweisen und wie sich
diese mathematisch ausdrücken, betrachten wir im folgenden, wie die Bilddaten strukturiert sind, das heißt, wie
die einzelnen Zahlen, die die Pixel-Position, die Farbwerte, die Bildgröße etc. angeben, in einer Bilddatei
organisiert werden. Ausführlich behandeln wir zwei spezielle Arten der Datenorganisation in Kapitel 8, hier
jedoch soll ein erster Eindruck über verschiedene Datenstrukturen vermittelt werden; der Einfachheit halber
betrachten wir Binärbilder.
Die unkomplizierteste Art der Organisation ist die Lauflängen-Codierung, die in der Praxis recht häufig
vorkommt (siehe Kapitel 10). Diese Methode nutzt die Gegebenheit aus, dass, wenn gleiche Pixelwerte
hintereinander auftreten, man diese, statt sie einzeln zu schreiben, zusammenfassen kann. Wie man sich
vorstellen kann, ist diese Methode besonders bei schwarz-weißen, also Binärbildern, nützlich, wohingegen sie
bei einem Bild mit 24 Millionen Farben eher unpraktisch ist, da viel zu viele Farbwerte existieren, als dass
mehrere identische häufig aufeinander folgen würden. Man kann die Lauflängenkodierung als Multiplikation
auffassen: Statt alle "Summanden" einzeln hinzuschreiben, gibt man nur den Wert und seinen Faktor an.
Nehmen wir als Beispiel die Pixelzeile:
000111100000111111000000011111111
Diese kann auf verschiedene Arten zusammengefasst werden, zum Beispiel, in dem man die Zeile in 0- und 1Blöcke zerlegt und zu jedem Block der Wert (0 oder 1) und seine Länge angibt:
19/73
(3,0), (4,1), (5,0), (6,1), (7,0), (8,1).
Wenn wir nun noch festlegen, dass sich Schwarz und Weiß (also 0 und 1) immer abwechseln, dass die
Grauwerte also alternieren, erhalten wir folgende Schreibweise, die gegenüber der ursprünglichen Pixelzeile um
81,8% verkleinert ist (wir betrachten beispielshalber nur die Zeichenanzahl, in Binärcodes muss die
Kompression entsprechend ausgerechnet werden):
3 4 5 6 7 8.
Meist ist der Längenangabe eine obere Grenze gesetzt, z.B. 1 Byte. Sollte ein Wert nun z.B. 190 mal
vorkommen, so muss man den Block aufspalten - und, da wir ja ein Abwechseln der Blöcke festgelegt haben,
einen Block der Länge Null der anderen Farbe einschieben:
255 0 35.
Wir können die Pixelzeile 000111100000111111000000011111111 auch darstellen, indem wir die Länge und
die Position der 1-Blöcke angeben, alles andere muss dann ja ein 0-Block sein. Bei dieser Art ergibt sich für
unsere Beispielpixelzeile die Darstellung:
(3,4), (12,6), (25,8).
In Kapitel 8 werden wir eine Variante dieser Lauflängencodierung kennen lernen, die bei der Verschlüsselung
und der Komprimierung von Bilddaten im JPEG-Format angewandt wird. Es gibt noch zahlreiche andere
Möglichkeiten, Bilddaten zusammenzufassen, jedoch beziehen sich diese im Großen und ganzen auf Binärbilder,
da, wie bereits gesagt, bei einer Farbraum-Wertemenge von 2 Farben (Schwarz und Weiß) öfter Pixel des
gleichen Wertes nebeneinander liegen und daher zusammengefasst werden können als bei einer FarbraumMenge von 255 Abstufungen (die wir im RGB-Format in den Kanälen Rot, Grün und Blau haben).
Für die Codierung von Binärbildern gibt es zum Beispiel Richtungscodes. Die einzelnen Pixel
eines Bildes
sind dabei nicht durch ihre Koordinaten m und n in der
Bildmatrix beschrieben, sondern über eine
einheitliche Benennung der umliegenden Bildpunkte eines bestimmten Pixels, der "Nachbarn":
Man kann die Position von Pixeln auch angebenindem man sie im Bezug auf einen bestimmten Ausgangspixel
durchnummeriert. Bei diesem Pixelnachbarn-System bekommen alle Nachbarn vom Pixel p eine Nummer
zugeordnet, mit der sie relativ zu p eindeutig beschrieben sind.
Der 4-Nachbar eines Pixels
ist demnach der Pixel
Nachbarn, die eine gemeinsame Kante mit dem Pixel
, der 1-Nachbar der Pixel
. Diejenigen
haben, also die 0-, 2-, 4-, und 6-Nachbarn, heißen
direkte Nachbarn. Die anderen, die nur eine Ecke mit dem Pixel
Nachbarn genannt.
gemeinsam haben, werden indirekte
Mit dieser Art der Codierung lassen sich viele Operationen schnell und einfach durchführen, wie zum Beispiel
das Drehen eines Bildes um Vielfache von 45°, da hierbei die Richtungscodes nur um eine ganzzahlige
Konstante erhöht werden müssen, wobei man mit modulo 8 rechnen muss, um aus dem System der einheitlichen
Bezeichnung (siehe obige Grafik) nicht herauszufallen. Auch lassen sich mit Richtungscodes die Höhe und
20/73
Breite einer Fläche sowie deren Umfang oder auch der Abstand zwischen zwei Punkten ziemlich schnell und
einfach berechnen. Das sei hier jedoch nur am Rande angemerkt, da wir uns mit vollfarbigen Grafiken und deren
Kompression nach dem JPEG-Verfahren befassen.
2.5 Begrifflichkeit
Zu Abschluss des Kapitels über die Grundlagen der digitalen Bilder sei noch etwas zur Terminologie angemerkt:
Umgangssprachlich hat es sich etabliert, von "der Pixel" zu sprechen. Ursprünglich heißt es jedoch "das Pixel",
da Pixel ja die Abkürzung für "picture element" und somit im Deutschen das Neutrum durchaus angebracht ist
(DAS Bildelement, ergo auch DAS Pixel). Jedoch verhält es sich bei diesem Phänomen wohl wie mit "das
Virus" und "der Virus" in der Biologie...
21/73
3 Exkurs: Die digitale Aufnahme
Nachdem wir uns nun die Grundlagen der menschlichen Wahrnehmung und der digitalen Bilder erschlossen
haben, ist es sinnvoll, vor dem Einstieg ins eigentliche Thema einen kurzen Exkurs zu machen und sich
anzusehen, wie Bilder überhaupt technisch in diskretierte Pixelbilder, in Pixelmatrizen, "verwandelt" werden.
3.1 Der Scanner
Der Scanner ist das verbreitetste Gerät, mit dem Bilder digitalisiert werden. Der typische Graustufenscanner
verarbeitet eine normale Bildvorlage und gibt digitale Bilddaten aus, indem die Bildvorlage beleuchtet wird,
welche daraufhin das einfallende Licht mehr oder weniger stark reflektiert (dunkle Stellen "schlucken" den
Lichtstrahl, helle Stellen werfen ihn zurück). Das zurückkommende Licht wird dann über Stablinsen von
lichtempfindlichen, elektronischen Bauteilen aufgenommen, sogenannten CCDs (Charge Coupled Devices), die
entsprechend der Lichtintensität der Reflexion einen Wert an den PC übermitteln, welcher daraus dann die
Helligkeit des Bildpunktes bestimmt (siehe „Hintergrund-Information zu CCD-Sensoren und zur
Signalübersetzung“).
Herkömmliche Farbscanner funktionieren nach dem gleichen Prinzip wie die Graustufenscanner, hier gibt es nur
einige Weiterentwicklungen:
1.
2.
3.
Es können Farbfilter eingesetzt werden. Die Vorlage wird also in drei Scandurchgängen mit weißem
Licht beleuchtet, wobei in jedem Durchgang den CCDs ein anderer Farbfilter (Rot, Grün und Blau, mit
denen sich jede Farbe darstellen lässt, siehe Kapitel 1.3) vorgesetzt wird. Allerdings ist dieses
Verfahren technisch aufwendig, unpräzise und obendrein langsam, daher findet es wenig Anwendung.
Es können drei farbige Fluoreszenz-Lampen eingesetzt werden, welche nur den entsprechenden
Farbanteil der Vorlage reflektieren. Hierbei ist nur ein Scandurchgang erforderlich.
Es kann ein Prisma eingesetzt werden. Der Scanner beleuchtet die Vorlage mit einer weißen Lampe,
deren Licht reflektiert und anschließend durch ein Prisma geleitet wird. Dieses zerlegt den Lichtstrahl in
seine Rot-, Grün- und Blau-Komponenten. Um diese nun zu messen, müssen drei verschiedene Reihen
mit CCDs im Scanner installiert werden. Bei diesem Verfahren erhält man gute Ergebnisse, da wenig
Farbverfälschungen (im Gegensatz zum Filter-Verfahren) auftreten können und auch nur ein
Scandurchgang gebraucht wird, die Vorlage zu erfassen.
Aufbau eines herkömmlichen Scanners (Bild: http://www.geocities.com/ally77jp/).
22/73
3.2 Die Digitalkamera
Bei digitalen Fotoapparaten, die wesentlich neuer sind als die Scannertechnologie, werden farbige Pixel erzeugt,
indem lichtempfindliche Zellen durch drei Farbfilter belichtet werden, ähnlich dem Scanner-Filter-Verfahren.
Anschließend misst ein CCD-Sensor (wie gesagt: Charge Coupled Device) die Helligkeit, ordnet sie dem
jeweiligen Bildpunkt zu und gibt einen Wert an den PC weiter.
Wie bereits in Kapitel 2.2 erläutert, können mit einer Darstellung von 8 Bit (also 8 Stellen, die die Werte 0 oder
1 annehmen können) 256 verschiedene Abstufungen unterschieden werden. Aus Kapitel 1.1 wissen wir auch,
dass das bereits mehr Helligkeitswerte sind, als der Mensch erkennen kann.
Warum nun trotzdem viele Bilder von Kameras nicht nur in 256, sondern auch in 1024 und 2048 Farbtönen (also
10- und 12 Bit-Farbtiefe) ausgegeben werden, hat einen simplen Grund: Der Mensch nimmt
Helligkeitsunterschiede in den hellen Bildbereichen deutlicher wahr als in den dunklen (man nennt dieses eine
"logarithmische Helligkeitsempfindung"), im Gegensatz zum elektronischen CCD-Chip, der nur die genaue
Menge an Licht misst, die auf die Pixel trifft. Damit die digital erfassten Bilder für den Menschen aussehen wie
das originale Motiv, wandeln einige Kameras die Spannungswerte nicht in 256 sondern in 1024 oder 4096
Stufen um, was sich meist besonders bei der Detailwiedergabe in den dunklen Bildbereichen bemerkbar macht.
Die digitale Farbfotografie funktioniert ebenso (hier von "funktioniert analog" zu sprechen, wäre denkbar
unpassend): Für jeden der Farbkanäle Rot, Grün und Blau werden die Spannungswerte gewandelt und ergeben
im Gesamtbild die entsprechenden Farbwerte. Wird in jedem Kanal mit 256 Abstufungen aufgenommen,
erhalten wir die 16,7 Millionen rechnerischen Farbwerte, über die viele Bilder verfügen, die allerdings weder am
Monitor noch im Druck dargestellt werden können (siehe Kapitel 1.1 und nachfolgender Abschnitt 3.3).
3.3 Auflösungen und Druckverfahren
Damit man Pixelbilder nicht als Pixelmatrizen erkennt, sondern ein Foto sieht, müssen die einzelnen Bildpunkte
entsprechend klein sein. Ebenso muss ein Bild über eine große Menge Pixel verfügen, wenn es eine bestimmte
Größe haben soll. Liegen zwei Bildpunkte weniger als knapp 1/15 mm auseinander und befinden wir uns in 25
cm Entfernung, so können wir diese Punkte nicht mehr als getrennte Punkte erkennen. Entsprechend dürfen die
Pixel bei einem Betrachtungsabstand von 1 Meter höchstens 1/3 mm voneinander entfernt sein.
Man kann also sagen: Steht man 25 cm vor einem Bild, reichen etwa 12 Pixel auf einem mm aus, damit man das
Bild wie ein Foto wahrnimmt. 12 Pixel pro mm sind 304,8 Pixel pro Inch. Bildpunkte pro Inch ist nämlich die
gängige Einheit beim Maß von Auflösungen. In diesem Fall (12 Pixel/mm = 304,8 Pixel/Inch) kann man sagen:
Ein Auflösung von etwa 300 dpi (dpi = Dots pro Inch = Bildpunkte pro Inch) genügt, damit wir die einzelnen
Bildpunkte nicht mehr erkennen. Bei einem Abstand von 1 m reichen etwa 80 dpi aus.
Hier muss natürlich angemerkt werden, dass das Verfahren, mit dem das Bild ausgegeben wird, eine
entscheidende Rolle spielt, da je nach Ausgabeverfahren die Betrachtungsentfernung anders ist - manche
Methoden sind feiner, manche gröber).
23/73
4 Das JPEG-Verfahren
Das Hauptaugenmerk dieser Abhandlungen liegt auf einer bestimmten Kompressionsart für digitale Bilddateien,
die nun, nachdem alle Voraussetzungen und Grundlagen geklärt sind, ausführlich behandelt werden soll. In
diesem Kapitel finden sich einige Worte zum prinzipiellen Bildkomprimieren Kapitel 4.1 sowie eine kleine
übersicht, wie das JPEG-Format im Groben funktioniert Kapitel 4.3. Die einzelnen Schritte werden detailliert ab
Kapitel 5 präsentiert und vorgerechnet.
4.1 Verschiedene Kompressionsarten
Prinzipiell unterscheidet man Bildkompression nach zwei verschiedenen Methoden: Der verlustfreien und der
verlustbehafteten Kompression.
Bei der verlustfreien Kompression (oder auch lossless compression) findet keine Reduktion der Bilddaten
statt, die Bildinformationen zerstören würde, sodass hier jedes Bildelement erhalten bleibt. Diese Methode findet
vor allem dann Einsatz, wenn mit komplexen, aufwendig zu berechnenden oder teuren Bilddaten gearbeitet wird,
die nicht verloren gehen dürfen (zum Beispiel in der Medizin, bei der Analyse von Satellitenbildern etc.).
Digitale Formate, die ohne Qualitätsverlust speichern, sind zum Beispiel BITMAP und TIFF. Solche
unreduzierten Bilddaten sind speicheraufwendig, dafür haben sie auch eine hohe Qualität.
Bei der verlustbehafteten Kompression (lossy compression) ist dies nicht der Fall: Hier wird weniger Wert auf
die Bildqualität gelegt als darauf, die Dateigröße möglichst gering zu halten. Daher werden die Bilddaten bei
dieser Methode reduziert, sodass das Ausgangsbild nicht 1:1 wiederherstellbar ist, sondern eine schlechtere
Qualität bietet. Durch zu starkes Komprimieren können durch den Wegfall von Bilddaten Fehler im Bild
entstehen; diese nennt man Artefakte. Verlustbehaftete Bildkompression wird da eingesetzt, wo große
Datenmengen nicht ohne weiteres verarbeitet werden können, das Paradebeispiel ist hier das Internet, das wie
alle Netzwerke keine besonders hohe Übertragungsgeschwindigkeit hat, sodass BMP-Bilder zum Beispiel viel zu
viel Ladezeit in Anspruch nähmen. Dateiformate, die Bilddaten reduzieren und daher auch weniger
Speicherplatz benötigen, sind zum Beispiel GIF und JPEG.
24/73
Ein verlustfrei gespeichertes Bild (links) und ein verlustbehaftetes (rechts) im Vergleich. Beim rechten Bild fällt
auf, dass sich nicht nur Artefakte gebildet haben, die bei stärkeren Kompression auch ohne Vergrößerung
erkennbar sind, sondern das Bild mit zunehmender Kompression auch Schärfe und Kontrast einbüßt (Bild: Mustang
Multimedia Spezial).
4.2 Kompressionsmodi bei JPEG
Das JPEG-Format ist von besonderem Interesse, weil es sich im Internet als Bildstandard durchgesetzt hat, um
vielfarbige Bilder in True Color mit möglichst geringem Platzbedarf zu speichern (siehe „HintergrundInformation zur Entstehung von JPEG“).
Die Idee war dabei, einen Algorithmus zur Kompression "natürlicher" Grauton- oder Farbbilder zu
entwickeln, das heißt einen Kompressionsalgorithmus Bilder zu finden, der Bilddaten so reduziert, dass sie für
das menschliche Auge wenig Qualität verlieren (mit "natürliche Bilder" sind solche gemeint, die in der Praxis
und im Alltag auftreten, wie zum Beispiel herkömmliche Urlaubsfotos). Schwerpunkte bei der Erstellung eines
geeigneten Algorithmus' waren einerseits eine hohe Kompressionsrate und andererseits eine hohe
Geschwindigkeit zum Kodieren und Dekodieren.
Leider konnte man keinen einzigen Algorithmus allein für alle Anforderungen entwickeln, sodass das
Kompressionsverfahren in vier verschiedene Modi gegliedert wurde.
·
·
Beim progressive mode wird das Bild in mehreren Durchgängen kodiert und dekodiert. Bei jedem
weiteren Durchgang verbessert sich dabei die Bildqualität, was besonders nützlich ist, wenn Daten über
große Entfernungen übertragen werden. Sobald das Bild eine für den Benutzer ausreichende Schärfe
erreicht hat, kann dieser die Übertragung stoppen.
Der hirarchical mode speichert das Bild in einer geringeren Auflösung und ebenfalls in voller
Auflösung. Das gering aufgelöste Bild kann wesentlich schneller übertragen und dekodiert werden und
eignet sich somit bestens als schnelle Vorschau auf das eigentliche Bild. Bei Interesse kann dann die
vollaufgelöste Version geladen werden.
25/73
·
·
Der lossless mode ist das einzige Verfahren, das verlustfrei kodiert und dekodiert. Der große Nachteil
ist, dass die Kompressionsrate recht gering ist, weil der volle Informationsgehalt gespeichert wird.
Beim sequentiell mode wird das Bild in einem einzigen Durchgang von links oben nach rechts unten
dekodiert, was in der Praxis für die meisten Anwendungen gut geeignet ist, die besten
Kompressionsraten erzielt und am leichtesten zu implementieren ist.
Auf das Verfahren des sequentiell mode wollen wir nun näher eingehen, da es das gebräuchlichste ist. Die
anderen drei vorgestellten Techniken sind nur in Ausnahmefällen und ganz spezifischen Einsatzbereichen
sinnvoll, basieren aber im Prinzip auf den gleichen Verfahren wie der sequentiell mode.
4.3 Ablauf der JPEG-Kompression
Die Kompression von Bilddaten durch das standardisierte JPEG-Verfahren verläuft folgendermaßen:
1.
2.
3.
4.
5.
6.
Es liegen Bilddaten im RGB-Format vor, von denen jeder einzelne Wert eine Zahl zwischen 0 und 255
ist. Diese werden in das YUV- oder YCbCr-Modell übertragen, wo die einzelnen Komponenten
(Helligkeit, Farbton und Sättigung, siehe Kapitel 1.3) verschieden stark gewichtet werden.
Außerdem wird eine Indexverschiebung vorgenommen, d.h. die Werte aus der Wertemenge [0;255]
werden als Zahlen zwischen -128 und 127 dargestellt. Die 3 nun vorliegenden sogenannten "Layer",
was eine Bezeichnung für die verschiedenen Datenmengen für Y, U,V, Cb oder Cr ist (man kann also
von "Datenschichten" sprechen), werden nun einzeln weiterbearbeitet.
Jedes Layer wird in 8*8 große Pixelblöcke eingeteilt (das komplette Verfahren muss natürlich auf alle
Matrizen und alle Layers einzeln angewendet werden), auf die im folgenden LINK die diskrete
Kosinustransformation einzeln angewendet wird. Die diskrete Kosinustransformation oder DCT (aus
dem Englischen: discrete cosine transform) interpretiert die Helligkeits- bzw. Farbwerte als
Überlagerung von Kosinusfunktionen, die deren Schwankungen angeben, d.h wie stark sich die Werte
von Ort zu Ort ändern, und transformiert die Werte in Amplituden für Kosinusfunktionen verschiedener
Frequenzen. Hierbei ähneln sich die Amplituden für hohe Frequenzen, wodurch man einen Vorteil für
die anschließende Kodierung erhält.
Die entstandenen Amplituden werden noch quantisiert, indem sie durch einen vom Benutzer
festlegbaren Quantisierungsfaktor dividiert und danach gerundet werden, wobei viele Werte gleich Null
werden.
Im Folgenden wird die quantisierte Matrix codiert. Dazu wird die 8*8-Matrix in einen 1*64-Vektor
umgeschrieben, sodass die zahlreichen Nullen, die beim Quantisieren entstanden sind, hintereinander
stehen und sich gut zusammenfassen lassen. Ist diese erste Reduzierung der Datenmenge erfolgt, so
wird die eigentliche Huffman-Codierung angewendet, bei der jedem Wert ein einzigartiger Binärcode
zugeordnet wird. Eine große Speicherplatzersparnis wird dadurch erreicht, dass beim HuffmanVerfahren häufig auftretenden Werten ein kurzer, seltenen Werten ein langer Code zugeteilt wird und
die Codes der einzelnen Werte außerdem ohne Trennzeichen auskommen und aneinandergereiht
werden können.
Wenn das Bild nun decodiert wird, werden die Binärcodes wieder in Zahlenwerte umgewandelt und
ausführlich ausgeschrieben, sodass man wieder einen 1*64-Vektor, bzw. eine 8*8-Matrix erhält. Zur
Dequantisierung werden die quantisierten Werte in dieser Matrix einfach mit dem
Quantisierungsfaktor multipliziert. Die inverse DCT sorgt dann dafür, dass aus den Amplituden wieder
die ursprünglichen Helligkeits- bzw. Farbwerte hergestellt werden. Zur besseren Unterscheidung wird
die DCT auch forward DCT genannt. Wenn immer wir im folgenden von DCT sprechen, ist die forward
DCT gemeint. Die von der inversen DCT erhaltenen Werte ergeben nun das komprimierte Bild.
26/73
5 Farbraumveränderung
Digitale Bilder werden gewöhnlicherweise im RGB-Modell dargestellt. Da das Auge Helligkeitsunterschiede
besser wahrnehmen kann als Farbunterschiede (siehe dazu Kapitel 1.1), ist es für die Reduzierung der
Datenmenge sinnvoll, Helligkeiten mit höherer Auflösung zu speichern als Farben. Zweckmäßig hierfür ist eine
Umwandlung der RGB-Daten in ein Farbmodell, bei dem Helligkeitswerte getrennt von Farbwerten gespeichert
werden, wie das YUV- oder das YCbCr-Modell (vgl. Kapitel 1.3). Hierbei ist Y jeweils der Helligkeitswert, U
der Farbton und V die Farbsättigung. Cb beschreibt die Abweichungen vom Grau- zum Blauwert, Cr vom Grauzum Rotwert. Die Umwandlung geschieht folgendermaßen:
Vom RGB- ins YUV-Modell:
Y = 0,299R + 0,587G +0,114B
U = 0,493(B - Y)
V = 0,877(R - Y)
oder
vom RGB- ins YCbCr-Modell
Y = 0,299R + 0,587G + 0,114B
Cb = -0,1687R - 0,3313G + 0,5B + 128
Cr = 0,5R - 0,4187G - 0,0813B + 128
Bei der JPEG-Kompression wird keines dieser beiden Farbmodelle bevorzugt. Wichtig für die Kompression ist
lediglich, dass nach der Umwandlung in einen anderen Farbraum ein sogenanntes Subsampling vorgenommen
wird, d.h. dass die Farbwerte U, V oder Cb, Cr mit geringerer Auflösung gespeichert werden als die Helligkeit
Y.
Hierbei werden zum Beispiel für 4 Pixel 4 Helligkeitswerte, aber jeweils nur 2 Farbwerte oder sogar nur ein
Farbwert gespeichert, die dann Mittelwerten der 4 vorgegebenen Werte entsprechen. Ein Subsampling mit noch
gröberer Auflösung für die Farbwerte ist aufgrund der dadurch stark verschlechterten Qualität des Bildes nicht
sinnvoll (siehe „Beispielrechnung für das Subsampling“):
Wie noch in Kapitel 6 besprochen werden wird, ist es für eine weitere Kompression der Daten zweckmäßig, die
256 möglichen Werte, die von 0 bis 255 reichen, als Werte des Intervalls [-128; 127] darzustellen. So entspricht
z.B. der alte Wert 0 dem Wert -128 in der neuen Wertemenge. Diese Vorgehensweise wird Indexverschiebung
genannt.
27/73
6a Die Eindimensionale Diskrete Kosinustransformation
Nach der Indexverschiebung wird eine zweidimensionale diskrete Kosinustransformation angewendet. Es bietet
sich an, zum besseren Verständnis zuerst die simplere eindimensionale DCT zu besprechen, um von dort dann
später auf die zweidimensionale DCT zu schließen. Die mathematische Anwendbarkeit der eindimensionalen
wie der zweidimensionalen DCT ist selbstverständlich nicht nur auf Bildpunkte beschränkt, jedoch erscheint es
sinnvoll, sie hier nur im Zusammenhang mit diskreten Bildpunkten zu besprechen. Damit man die
eindimensionale DCT anwenden kann, müssen Werte von Bildpunkten in nur einer Dimension gegeben sein.
Diese eindimensionale Anordnung kann zum Beispiel eine Zeile der zweidimensionalen Verteilung der
Bildpunkte im Bild darstellen.
Die Werte sind also zum Beispiel von links nach rechts angeordnet.
x
f(x)
0
f(0)
1
f(1)
2
f(2)
3
f(3)
...
...
Die diskrete Kosinustransformation ist eine mathematische Operation, die die diskrete Ort-Werte Zuordnung in
eine diskrete Frequenz-Amplituden Zuordnung umwandelt. Die Frequenz einer Kosinusfunktion gibt in diesem
Falle an, wie oft sich der Verlauf der periodischen Kosinusfunktion pro Ortseinheit wiederholt. Amplituden sind
hier definiert als die betraglichen Maximalwerte, die eine dazugehörige Kosinusfunktion annimmt.
Durch die entstandene Zuordnung wird beschrieben, wie sehr die Werte um die Mitte des Intervalls [-128; 127],
die bei -0,5 liegt, schwanken. Ausgedrückt wird dies in Amplituden von Kosinusschwingungen verschiedener
diskreter Frequenzen. Das heißt, die neue Frequenz- Amplituden Zuordnung beschreibt, wie "schnell" und stark
sich die Werte im Verlauf der Funktion f(x) verändern. Eine niedrige Amplitude für eine bestimmte Frequenz
bedeutet, dass die f(x)-Werte mit dieser Frequenz nur geringfügig um die Mitte des Intervalls [-128; 127]
schwingen.
Die diskrete Funktion f(x) wird als Überlagerung von Kosinusschwingungen verschiedener Frequenzen gedeutet.
Das heißt, die f(x)-Werte werden als Addition der Funktionswerte der verschiedenen Kosinusfunktionen an der
Stelle x interpretiert. Eine Überlagerung von Kosinusfunktionen bedeutet also die Summe von
Kosinusfunktionen. Zur besseren Vorstellung, wie so etwas aussehen kann, liegt hier ein Beispiel vor, das drei
Kosinusfunktionen zeigt, die (wie wir später sehen werden) auch in der DCT benutzt werden, und deren
Überlagerung angibt.
28/73
Eine Überlagerung von Kosinusfunktionen bedeutet die Summe von Kosinusfunktionen. Als Beispiel betrachten
wir diese drei cos-Funktionen k2(x), k3(x) und k7(x).
29/73
Werden obige drei cos-Funktionen überlagert, so addieren sich die Funktionswerte und wir erhalten diese neue
Funktion kSum(x).
Bei der DCT entspricht die Anzahl der definierten Orte der Anzahl der verschiedenen betrachteten Frequenzen.
Bei der eindimensionalen DCT werden horizontal angeordnete Werte in horizontal verlaufende Schwingungen
umgewandelt, d.h. die Kosinusfunktion ist eine Funktion des Ortes. Die Frequenzen werden dabei genauso
durchnummeriert wie die Orte, wobei größere Nummern der Frequenzen auch größere Frequenzen bedeuten.
u
F(u)
0
F(0)
1
F(1)
2
F(2)
3
F(3)
...
...
Die Formel für die eindimensionale DCT lautet:
6.1
hierbei ist:
·
·
·
N
u
: Amplitude der Kosinusschwingung mit der Frequenz der Nummer u
: Anzahl sowohl der verschiedenen Orte als auch der Frequenzen
: Nummer der Frequenz in Horizontalrichtung
30/73
·
x
·
·
: Nummer des Ortes in Horizontalrichtung
: Pixelwert am Ort x
: Ein Korrigierungsfaktor, den wir bei der Besprechung der inversen DCT näher behandeln
werden
Für den Spezialfall u = 0 ergibt sich dann
6.2
,
da hier
und cos(0) = 1 ist.
Da bei der JPEG Komprimierung eine 2D-DCT (zweidimensionale DCT) mit N = 8 benutzt wird, werden wir
von nun an vor allem auch die 1D-DCT mit N = 8 betrachten. Für sie gilt:
6.3
Wir wissen also nun, dass die Frequenzen von 0 bis 7 in Schritten von 1 durchnummeriert werden. Dies allein
sagt nichts über die Werte der tatsächlichen Frequenzen aus, denn die Zahlen 0 bis 7 bezeichnen lediglich deren
Nummer, sozusagen deren Stellung in der Tabelle. Um die Frequenzen aus deren Nummern errechnen zu
können, geht man folgendermaßen vor:
Für die Frequenz
einer Kosinusschwingung
gilt:
Durch geeignetes Umformen unserer Kosinusfunktion aus 6.3
erhält man
.
Man kann b nun einfach ablesen:
6.4
.
31/73
Die Frequenz errechnet sich also durch:
.
Die Frequenzen sind demnach:
u
0
1
2
3
4
5
6
7
0
Zusammenhang zwischen den Nummern u und den Frequenzen
. Aus Gründen der Anschaulichkeit wurden
die Frequenzen ungekürzt dargestellt.
Wenden wir uns nun wieder der Formel 6.3 zu, durch die unter Verwendung der vorgegebenen Daten der Wert
F(u) ausgerechnet werden kann. Im folgenden wird dargelegt werden, was unter F(u) zu verstehen ist.
Die Werte von F(u) entsprechen einem Maß für die Amplituden von Schwingungen der Frequenz der Nummer u
im Bild. Sie sind nur ein Maß für die Amplituden, da sie, wie wir noch sehen werden nicht genau den
Amplituden entsprechen.
Wie man anhand der obigen Tabelle sehen kann ist die Frequenz von u = 0 selbst null, was bedeutet dass keine
Schwingung vorhanden ist. F(0) beschreibt daher den gleichbleibenden Anteil aller Werte von f(x). Dies
bedeutet nichts anderes, als dass eine Art Mittelwert aller f(x) gebildet wird. Es ist deshalb eine Art Mittelwert,
da sich folgender Ausdruck, der durch Einsetzen von N = 8 in 6.2 entsteht,
von der Definition des arithmetischen Mittelwertes für alle f(x)
nur um den Faktor
unterscheidet. Die Formulierung "der gleichbleibende Anteil aller Werte von f(x)"
eröffnet nun auch ihren Sinn: Der gleichbleibende Anteil ist der Wert, der, falls man ihn für alle Orte gleich
annimmt, über alle Orte aufaddiert die gleiche Summe ergeben würde wie die Summe der tatsächlichen Werte
von f(x). Dies ist auch eine Beschreibung des arithmetischen Mittelwertes. Der gleichbleibende Anteil bedeutet
nichts anderes als der arithmetische Mittelwert. Wie schon gesagt, beschreibt F(0) den gleichbleibenden Anteil,
also den arithmetischen Mittelwert, indem es einen Wert angibt, der sich nur durch einen Faktor, nämlich
,
vom arithmetischen Mittelwert unterscheidet.
F(0) wird auch DC- Koeffizient genannt, was von direct current, Gleichstrom, abgeleitet wird.
Da alle anderen Werte von u für Frequenzen stehen, die von 0 verschieden sind, werden alle Werte von F(x)
außer F(0) AC- Koeffizienten genannt, welches von alternating current kommt, was Wechselstrom bedeutet.
Für ein besseres Verständnis der AC-Koeffizienten betrachten wir noch einmal den Term 6.4.
Wichtig: die folgenden überlegungen zur Berechnung der AC-Koeffizienten sind nur gültig für
!
32/73
Wie bereits gezeigt bewirkt der Faktor
, dass alle Frequenzen ein Vielfaches von
sind. Auf einer
Intervalllänge von 8 durchläuft die Kosinusfunktion also ein Vielfaches der halben Periode. Unsere
Kosinusfunktion ist um 0,5 nach links verschoben und die diskreten x-Werte von 0 bis 7 bilden die
Definitionsmenge.
Alle unsere cos-Funktionen, wie z.B. hier k(x) mit u=6, stellen sich als um 0,5 nach links verschobene, normale
cos-Funktionen dar.
Dies bewirkt, dass die x-Werte gleichmäßig in dem Intervall [-0,5; 7,5], das die Länge 8 hat, verteilt sind.
"Gleichmäßig verteilt" soll hier bedeuten, dass es für jeden diskreten x-Wert mit der Differenz x zum Anfang
des Intervalls, einen von diesem verschiedenen x zum Ende des Intervalls gibt, was nur durch eine gerade
Anzahl von definierten x-Werten zu erreichen ist. Diese gleichmäßige Verteilung bleibt auch bei mehrfacher
Halbierung des Intervalls erhalten, solange Mindestens zwei x-Werte im Teilintervall definiert sind. Den Grund
dafür können Sie unter „Hintergrund-Information zur gleichmäßigen Verteilung“ lesen. Diese wichtige
symmetrische Eigenschaft werden wir später benutzen.
In Formel 6.3 kann man f(x) schreiben als
.
6.5
Man geht nun also davon aus, dass f(x) der Wert einer Kosinusfunktion der Frequenz u mit der Amplitude Au(x)
ist. Das heißt, wenn man voraussetzt, dass f(x) der Wert einer Kosinusfunktion an der Stelle x mit der Frequenz
der Nummer u ist, muss diese Kosinusfunktion die Amplitude Au(x) besitzen, damit f(x) auf dieser liegen kann.
Der Grund für die Indexverschiebung wird nun auch deutlich. Für die DCT benutzen wir Kosinusfunktionen, die
symmetrisch um den Wert 0 schwingen, also solche, die nicht in f(x)-Richtung verschoben sind. Diese Tatsache
kann man an obigen Formeln der Kosinusfunktionen erkennen. Diese Kosinusfunktionen sind mathematisch
einfacher darzustellen als welche, die um einen von null verschiedenen f(x)-Wert schwingen, also in f(x)Richtung verschoben sind. Wenn die Elemente unserer Wertemenge nun auch symmetrisch um den Wert 0
verteilt sind, kann man sie als Funktionswerte solcher einfachen Kosinusfunktionen interpretieren. In unserem
Fall wurden durch die Indexverschiebung allerdings alle f(x)-Werte symmetrisch um den Wert -0,5 angeordnet.
Die Mitte aller Werte, -0,5, um die die f(x)-Werte "schwingen", kommt dem Wert 0 jedoch nah genug um, um
obige Interpretation zu rechtfertigen (lesen Sie dazuu die „Vertiefende Anmerkung der Verfasser“).
33/73
Durch Einsetzten von 6.5 wird aus 6.3:
6.6
Zur weiteren Bearbeitung der Formel benutzen wir eine vereinfachte Darstellung der Kosinusfunktion, was uns
später auch noch sehr nützlich sein wird. Wir nutzen aus, dass diese Kosinusfunktion eine mittelbare Funktion
ist, d.h. dass sie die Funktion einer Funktion ist. Denn, bevor man den Kosinus anwendet, wird der Term in der
Klammer berechnet. Man kann unsere Kosinusfunktion daher auch schreiben als
, wobei
ist.
Oder einfach:
Durch die Funktion
.
wird ein Winkel angegeben, auf den dann der Kosinus angewendet werden kann. Die
Funktion
liefert also die Definitionsmenge für die Funktion
abhängig von dem Parameter u.
Man kann nun, indem man den Kosinus als eine Funktion von
. Diese Definitionsmenge ist
auffasst, zur Betrachtung aller 8
Kosinusfunktionen dieselbe Funktion
benutzen, bei der allerdings abhängig von u verschiedene Werte definiert sind. Dies bringt den Vorteil mit sich, dass man mit einer Funktion arbeiten kann, die für alle u
die gleichen Eigenschaften besitzt, wie z.B. Symmetrie und Frequenz.
Mithilfe dieser Erkenntnis lässt sich nun auch 6.6 weiterbearbeiten. Zu diesem Zweck benutzen wir nun den
trigonometrischen Satz des Pythagoras. Er lautet:
6.7
,
wobei gelten muss:
6.8
.
Der Vorteil, den man durch die Verwendung des trigonometrischen Satz des Pythagoras erhält, liegt auf der
Hand. Laut 6.6 muss man die Produkte der Amplituden mit der quadrierten Kosinusfunktion über alle x
aufsummieren. Im trigonometrischen Satz des Pythagoras werden auch zwei quadrierte Kosinuswerte addiert.
Wenn nun die Möglichkeit bestünde, dass man Paare von Winkeln, und somit von x-Werten, hat, die obige
Bedingung 6.8 erfüllen, könnte man mithilfe von 6.7 die Amplituden zu einem ganzzahligen Vielfachen
aufaddieren.
Der Übersicht halber können alle Funktionswerte anders dargestellt werden, was für sie auch die Folge hat, dass
für sie eine andere aber äquivalente Bedingung besteht. Diese Bedingung möchten wir als Folge der
übersichtlicheren Darstellung der Funktionswerte nun festsetzen.
34/73
Die Funktion
ist periodisch, d.h., dass sich ihr Verlauf nach gewissen Intervallen auf der
Achse wiederholt. Diese Abstände heißen Periode und sind hier gleich .
Dies ist, wie man an der Zeichnung erkennen kann nicht die einzige Besonderheit von
außerdem im Intervall [0;
] an der Geraden
Wertemenge bereits im Intervall [0;
mit
. Die Funktion ist
gespiegelt. Die Funktion nimmt also alle Elemente der
] an. Jeder Wert von
für ein
kann also durch ein
ausgedrückt werden.
Dies geschieht folgendermaßen: Gegeben sei ein
ungeraden Vielfachen von
-
mit dem Betrag des Abstands
ist. Es gilt nun, da alle Funktionswerte gleich sind, deren
gleichen Betrag von einem ungeraden Vielfachen von
, also auch von
zum nächsten
-Koordinaten um den
, abweichen:
, wobei der neue Winkel
6.9
innerhalb des Intervalls
liegt. Die folgenden drei Tabellen sollen zeigen, wie man diese anderen
Werte benutzen kann, um die Funktionswerte anders darzustellen.
-
35/73
angegeben, wobei die
In dieser Tabelle werden die Funktionswerte unserer Kosinusfunktion
-Werte einfach unter Benutzung der jeweiligen u und x mit unserem Term für
Hier werden die k(x)-Werte ausgedrückt als solche mit
ausgerechnet wurden.
. Diese Kosinusfunktion nimmt auch
36/73
negative Werte an und ist punktsymmetrisch um
Funktionswerte von
In der Graphik sieht man , wie
den zweiten
. Deshalb können negative Funktionswerte als
mit negativem Vorzeichen ausgedrückt werden.
den gleichen Funktionswert hat, wie
. Deswegen kann man
-Wert benutzen, um ersteren Funktionswert zu beschreiben.
In dieser Graphik kann man erkennen, dass die Funktion bei
den negativen Funktionswert von
37/73
annimmt. Man kann zur Beschreibung des ersteren Funktionswertes also den negativen
Funktionswert des zweiten Winkels benutzen.
Durch Quadrierung fallen die negativen Vorzeichen weg, und man kann alle Werte von
wie oben bereits dargelegt, als Funktionswerte von
Gegeben sind in unserem Fall die beiden
die Differenz
-Koordinaten
haben. Sie haben die Differenzen
Vielfachen von
Werten, die hier ja
und
bzw.
,
darstellen.
, die wegen
zum jeweils nächsten ungeraden
. Addiert man diese beiden Differenzen erhält man die Differenz zwischen den beiden
-
ist:
38/73
6.10
Aus 6.9 und 6.10 erhält man:
. Analog gilt auch:
.
Wegen 6.10 ist also die neue Bedingung, die von den vereinfacht dargestellten Funktionswerten erfüllt sein
muss, um den trigonometrischen Satz des Pythagoras anzuwenden, wenn man alle Funktionswerte als
mit
beschreibt:
6.11
Durch die DCT muss nun gewährleistet sein, dass es immer 4 Paare von Winkeln gibt, die Bedingung 6.11
erfüllen. Dies ist der Fall, wenn der eine Winkel, ausgedrückt als Element von
Intervalls also von
um
verschieden ist und der andere von
um -
vom Anfang des
.
Wie bereits festgestellt sind alle x-Werte gleichmäßig in einem Intervall verteilt, dass ein Vielfaches einer halben
Periode der Kosinusfunktion beträgt, die nicht quadriert ist. Die halbe Periode ist also hier , da nicht g(x)
sondern die nichtquadrierte Kosinusfunktion gemeint ist. Da durch die Funktion
alle x-Werte für ein u in
gleicher Weise auf
projiziert werden, sind auch die -Werte gleichmäßig in einem Intervall verteilt, dass ein
Vielfaches der halben Periode beträgt. Halbiert man dieses Intervall solange, bis man Teilintervalle erhält, die
betragen, sind die -Werte in diesen Intervallen immer noch gleichmäßig
ein ungerades Vielfaches von
verteilt, was wir oben schon für x-Werte gezeigt haben und für -Werte genauso wahr ist. Erinnern wir uns an
die Definition des Ausdrucks "gleichmäßig verteilt", welche besagte, dass sich zwei verschiedene
den gleichen Betrag vom Anfang bzw. Ende des Teilintervalls unterscheiden müssen.
-Werte um
Hier hat das Teilintervall die Länge
und in diesem Intervall gibt es, wie gezeigt, immer mindestens zwei
Werte, die sich um den gleichen Betrag vom Anfang bzw. Ende dieses Teilintervalls unterscheiden. In allen
anderen Teilintervallen verhält es sich gleich. Somit ist die Bedingung 6.11 für alle definierten Winkel
also für ein u, erfüllt.
>,
Man betrachte ein solches Paar von Winkeln, für die diese Bedingung erfüllt ist:
6.12
Da es sich hierbei also um ein besagtes Paar handelt, gilt auch:
39/73
6.13
Falls die Summanden in 6.13 beide gleich 0,5 sind, wird durch 6.12 der arithmetische Mittelwert zwischen
Au(x1) und Au(x2) berechnet. Gewöhnlich gilt nicht dieser Spezialfall und die Summanden unterscheiden sich.
Dies bewirkt, dass ein gewichteter Mittelwert von Au(x1) und Au(x2) gebildet wird. Es gibt für jedes
vier
solcher Paare. Gemäß 6.6 wird also die Summe von 4 gewichteten Mittelwerten gebildet und danach halbiert.
Das Ergebnis repräsentiert also das doppelte des Mittelwerts der Amplitude für die Frequenz von u, der nicht das
arithmetische Mittel sondern ein gewichtetes darstellt.
Es besteht kein offensichtlicher Grund, warum manche x-Werte über alle Frequenzen betrachtet einen stärkeren
Einfluss auf die Bestimmung der mittleren Amplitude haben sollten als andere. Dies würde das Ergebnis, das die
mittleren Amplituden angibt, verfälschen.
Im Folgenden möchten wir zeigen, dass dies nicht der Fall ist, sondern dass kein x-Wert über alle Frequenzen
gesehen, also insgesamt, mehr Gewicht bei der Bestimmung der Durchschnittsamplituden erhält, als ein anderer.
Um sicherzustellen, dass kein x-Wert bevorzugt wird, betrachten wir nun die Funktion
für ein
feststehendes x und über alle u. Zu diesem Zweck definieren wir x als Parameter und u als Variable. Die
Funktion
wird dann zu
und dementsprechend erhalten wir
,
wobei aus Gründen der Übersichtlichkeit wieder alle g(u) durch ein
dargestellt werden.
In der Tabelle kann man erkennen, dass es für jedes x über alle Frequenzen außer u = 0 gesehen die gleichen 7
Werte für g(u) gibt. über alle u gesehen hat jeder x-Wert also den gleichen Anteil an den mittleren Amplituden.
Man erkennt außerdem, dass alle 7 Werte verschieden sind. Einen mathematischen Beweis finden Sie unter
„Beweis: Alle 7 g(u)-Werte sind verschieden“.
Wie bereits gesehen, gibt es für g(x) immer zwei Phi-Werte, die sich um den gleichen Betrag von 0 bzw. von
unterscheiden. Da es nur 7 verschiedenen Werte gibt, die g(u) annehmen kann, nimmt g(x) auch nur dieselben 7
verschiedenen Werte an, wenn der Parameter
ist; die Funktionen geben schließlich beide die gleichen
Werte an, da im Rahmen der Definitionsmenge bei beiden alle u und x durchlaufen werden, wobei einmal der
eine Variable ist und einmal der andere. Unter diesen 7 verschiedenen Werten muss es also 3 der oben
beschriebenen Paare von g(u) Werten geben, von denen sich jedes zu 1 aufaddiert. Der siebte Wert, welcher 0,5
beträgt liegt bei
und ist selbst sein Partner. Der Mittelwert aller dieser Werte ist deshalb
.
40/73
Es ist nun also gezeigt, dass jeder f(x)-Wert im Durchschnitt mit der gleichen Gewichtung in die Bestimmung
der mittleren Amplituden eingeht, nämlich 0,5. Mit 8 Au(x) pro u erhält man durch Aufsummierung, wie in 6.6
vorgeschrieben also das vierfache einer mittleren Amplitude.
Das bedeutet also, dass über alle Frequenzen die einzelnen Amplituden für ein x eine mittlere Gewichtung von
0,5 in einem Wertepaar erreichen, obwohl sie gegenüber den Amplituden anderer x-Werte einzelner Frequenzen
unterschiedlich gewichtet werden, um die Durchschnittsamplituden zu bestimmen. Das heißt: Im Durchschnitt
werden alle x-Werte bei der Berechnung der mittleren Amplituden gleich gewichtet.
Wenn ein gewisser x-Wert an der Bestimmung der mittleren Amplitude für eine bestimmte Frequenz einen
geringen Anteil hat, hat er bei einer anderen Frequenz eine große Gewichtung. Diese Erkenntnis ist besonders
für die Umkehrung der DCT wichtig, auf die wir in Kapitel 9 näher eingehen.
ergibt die Summe in 6.6, wie gezeigt, das Vierfache einer mittleren gewichteten Amplitude für
Für alle
die Schwingung der f(x)-Werte. Aus 6.6 wird daher:
.
F(u) ist also das doppelte der Amplitude der Funktion f(x) für die Frequenz u.
41/73
6b Die Zweidimensionale Diskrete
Kosinustransformation
Die Übertragung der 1D-DCT auf die 2D-DCT fällt nun recht einfach. Man muss sich darüber im Klaren sein,
dass f(x,y) nun von zwei Variablen abhängig ist, die auf eine dritte Dimension projiziert werden.
Am Beispiel für u=v=4 ist hier gezeigt, wie der Graph einer kontinuierlichen Kosinusfunktion aussieht, die
Variablen in zwei Dimensionen besitzt.
Man kann sich das so vorstellen, dass f(x) der 1D-DCT z.B. das örtliche Auf und Ab der Meereswellen im
Querschnitt beschreiben könnte, f(x,y) könnte die örtlichen Schwingungen der gesamten Meeresoberfläche
beschreiben. Im Fall von Schwingungen in Bildern beschreibt f(x) einen Querschnitt durch das Bild, wohingegen
f(x,y) die gesamte Bildoberfläche angibt. Bei der JPEG Kompression ist das die gesamte Bildoberfläche eines
einzeln bearbeiteten 8 mal 8 großen Datenblocks.
42/73
Überlagerung zweier solcher Kosinusfunktionen.
Die 2D-DCT entsteht durch Multiplikation zweier 1D-DCT, wobei f(x) und f(y) zu einem f(x,y) kombiniert
werden. Es wird daraus nicht etwa f2(x,y), da man sich die diskrete zweidimensionale Verteilung der f-Werte als
eine Aneinanderreihung von eindimensionalen Verteilungen von f-Werten vorstellen kann. Die Werte bleiben
gleich, für eine korrekte Zuordnung werden nun allerdings zwei Variablen benötigt. Die Formel der 2D-DCT
lautet also:
6.14
Natürlich ist auch hier
Es gibt 8 verschiedene horizontal- und 8 verschiedene Vertikalfrequenzen. Es gibt also 64 verschiedene
Kombinationen dieser und demnach 64 F(u,v) Werte. Analog zur eindimensionalen DCT ist der Wert F(0,0) der
DC-Koeffizient, alle anderen AC-Koeffizienten.
Zunächst möchten wir wieder den DC Koeffizienten besprechen. Für ihn sind u = 0 und v = 0. Deswegen werden
die Kosinuswerte zu 1 und die Faktoren Cu und Cv sind beide
. Deshalb erhalten wir
43/73
.
Man summiert alle f-Werte auf und teilt durch 8. Es gibt 64 verschiedene f-Werte und deren Summe entspricht
dem 64-fachen Mittelwert aller f(x,y). Wir schreiben daher um:
Wie man sieht, ist der DC-Koeffizient der 2D-DCT das 8-fache des arithmetischen Mittelwertes aller f(x,y).
Gehen wir nun näher auf die AC-Koeffizienten ein. Wie schon bei der 1D-DCT kann auch hier zur
Vereinfachung der trigonometrische Satz des Pythagoras benutzt werden, um die mittlere Amplitude zu
berechnen. Analog zu 6.5 und 6.6 kann 6.14 also geschrieben werden als:
6.15
Im folgenden werden zunächst die Fälle behandelt in denen gilt:
und
.
In diesen Fällen sind die Faktoren Cu und Cv beide gleich 1. Man berechne die Summe nacheinander:
Der rechte Summenterm entspricht pro forma der Summe in 6.6. Geht man vor wie für 6.6, erhält man für die
Summe den vierfachen gewichteten Mittelwert der Amplituden für ein x und alle y :
Nun muss noch über alle x summiert werden:
Verfährt man analog zu oben, wird daraus:
F(u,v) ist also das vierfache einer gewichteten durchschnittlichen Amplitude.
Für den Fall, dass entweder u = 0 oder v = 0 sind, geht man ähnlich vor, man muss jedoch beachten, dass nun ein
Faktor Cu oder Cv gleich
6.15 wird dann:
ist. Setzen wir für die folgende Bearbeitung willkürlich fest, dass v = 0 ist. Aus
44/73
6.16
Hierbei gilt:
Unter der Annahme, dass v = 0 ist, ist also diese Summe gleich der 8-fachen Durchschnittsamplitude für die
Frequenz 0, was nichts anderes ist als das 8-fache des Durchschnittswertes aller f(y)-Werte.
6.16 wird dann zu
.
Hierbei ist die Summe wieder das 4-fache der Durchschnittsamplitude, also erhält man:
Da diese Tatsache ebenso gilt, wenn u = 0 ist und
, schreiben wir allgemein:
,
wobei entweder
ist.
F(u,v) gibt also für den Fall, dass eine Frequenz gleich null ist, das
-fache der mittleren Amplitude an.
Fazit
Die DCT transformiert die ortsabhängigen Pixelwerte, d.h. Helligkeits- oder Farbwerte, in frequenzabhängige
Amplituden. Zu diesem Zweck werden die Pixelwerte als Überlagerung von diskreten Kosinusfunktionen
verschiedener Frequenzen interpretiert, und zu jeder dieser Kosinusschwingungen wird durch die DCT eine
Amplitude bestimmt. Die DCT gibt diese Amplituden jedoch nicht direkt aus, sondern liefert bestimmte
Vielfache der einzelnen Amplituden.
Wichtig ist, dass aus den bei der DCT entstandenen Amplituden die ursprünglichen Pixelwerte wieder richtig
hergestellt werden können. Durch die DCT gehen also keine Informationen verloren, was der Grund dafür ist,
dass allein durch Anwendung der DCT auch kein Speicherplatz gespart werden kann. Die DCT ist verlustfrei.
Würde man die durch die DCT entstandenen Amplituden direkt ohne weitere Zwischenschritte codieren, wäre
man sogar vor das Problem gestellt, dass die Wertemenge der zu codierenden F(u,v)-Werte größer ist als die
Wertemenge von f(x,y). F(0,0) gibt zum Beispiel den 8-fachen Mittelwert aller f(x,y) an, welche Werte von -128
bis 127 annehmen können. F(u,v) hat also eine Wertemenge von [-1024; 1016]. Für andere u und v verhält es
45/73
sich ähnlich, wobei jedoch die Faktoren, mit denen die Amplituden multipliziert werden, nicht so groß sind.
Allerdings gibt es noch eine interessante Tatsache, die die niedrigeren Faktoren zum Teil ausgleichen kann. Kein
f(x,y) liegt auf einem Maximum einer Kosinusfunktion mit einer Frequenz (u,v). Amplituden geben allerdings
den Funktionswert beim Maximum der Kosinusschwingung an. Deshalb kann eine durch die DCT angegebene
Amplitude für eine bestimmte Frequenz (u,v) größer sein als 127 oder kleiner als -128, wenn f(x,y) geeignete
Werte annimmt, die zu dieser bestimmten Frequenz "passen".
46/73
7 Quantisierung
In natürlichen Bildern gibt es auf kleinem Maßstab von 8 mal 8 Pixeln keine starken Helligkeits- oder
Farbunterschiede. Demnach werden die AC-Koeffizienten mit steigenden Frequenzen tendenziell kleiner.
Man definiert für jeden einzelnen Ort (u,v) einen Quantisierungsfaktor Q(u,v). Nun werden die F(u,v)-Werte
quantisiert, indem man jeden F-Wert an der Stelle (u,v) durch einen entsprechenden Quantisierungsfaktor Q an
der Stelle (u,v) teilt und auf die nächste ganze Zahl, also Integerzahl, rundet.
Durch das Quantisieren, also das Teilen und Runden der Werte, wird eine Reduzierung der Wertemenge von
F(u,v) erreicht, was den Vorteil einer späteren Kodierung mit weniger Bits ermöglicht. Außerdem werden viele
hochfrequente AC-Koeffizienten zu 0 quantisiert, was durch Redundanz einen Vorteil bei der Kodierung
bietet (dass gleiche Werte zusammengefasst werden, haben wir bereits in Kapitel 2.4 gezeigt, weitere Details zur
Codierung finden Sie in Kapitel 8).
Links: geringer Quantisierungsfakor, rechts: hoher Quantisierungsfakor. Je stärker die Quantisierung ist, desto
ungenauer wird die Wiederherstellung des Ausgangsbilds und desto mehr Artefakte treten auf.
Je höher der Quantisierungsfakor ist, desto größer wird, wie man bei den beiden Beispielbildern oben erkennen
kann, die Ungenauigkeit bei der Wiederherstellung der ursprünglichen F(u,v) Werte, da die entstandenen
Rundungsfehler nun bei der Dequantisierung mit einem höheren Faktor multipliziert werden müssen, um die
ursprünglichen Werte zu erlangen, wodurch die Fehlerfortpflanzung größer wird, als wenn mit einem kleinen
Faktor multipliziert würde.
Das menschliche Auge ist allerdings nicht sehr empfindlich für hochfrequente Schwingungen im Bild (siehe
Kapitel 1.1), weswegen man höhere Quantisierungsfaktoren für höhere Frequenzen benutzen kann, um auf
Kosten von stärkeren Rundungsfehlern, die allerdings auf Grund der Unzulänglichkeiten des menschlichen
Auges nicht wichtig sind, den Vorteil von mehr entstandenen Nullen nutzen zu können.
47/73
Die DCT-Koeffizienten, die mit größeren Frequenzen tendenziell kleinere Werte annehmen, werden durch
Quantisierungsfaktoren geteilt. Diese Faktoren werden mit höheren u- und v-Werten größer. Ergebnis: Viele der
kleinen DCT-Koeffizienten (diejenigen mit hohen Frequenzen) werden so (nach dem Teilen und Runden) zu Null
quantisiert.
48/73
8 Codierung
Nach der Quantisierung der 8*8 Blöcke werden nun alle Werte codiert, um weiteren Speicherplatz zu sparen.
Dieses geschieht üblicherweise mit der sogenannten Huffman-Codierung, die die Werte in Binärcode
umwandelt und es sich dabei zu Nutzen macht, dass bestimmte Werte häufiger vorkommen als andere. Warum
das dem Komprimieren förderlich ist, wie es funktioniert und wie man die 8*8-Blöcke vorher vorbereiten muss,
sehen wir im Laufe dieses Kapitels.
8.1 Zick-Zack-Umsortierung
Durch das Quantisieren sind viele Null-Werte entstanden, was ja auch unsere Absicht war, um Redundanzen
zusammenfassen zu können. Aus Kapitel 2.4 wissen wir, dass Werte gruppiert werden können, wenn sie
hintereinander stehen. Damit das in unseren 8*8-Matrizen der Fall ist, muss man sie im Zick-Zack Kurs
abgelesen, denn dann stehen möglichst viele der beim Quantisieren entstandenen Nullen hintereinander.
Man liest die Werte einer 8*8-Matrix im dargestellten Zick-Zack-Verfahren ab, um so die häufig auftretenden
Nullen am Ende der Matrix zu gruppieren.
Nun haben wir die Werte hintereinander aufgeschrieben, die 8*8-Matrix also in einen 1x64-Vektor
umgewandelt. Grundlage für die Erstellung eines sogenannten Huffman-Codes ist nun eine stochastische
Verarbeitung der Werte, die die Matrix enthält, denn es ist wesentlich zweckmäßiger, häufig auftretenden
Werten einen kurzen Code und seltener vorkommenden Werten einen langen zu geben, als jeden einzelnen Wert
ungeachtet, wie oft er auftritt, mit der gleichen Codelänge zu verschlüsseln.
8.2 Huffman-Codierung: Stochastische Auswertung
Bevor wir den Huffman-Code auf unseren Vektor anwenden, demonstrieren wir das System der stochastischen
Auswertung, indem wir folgendermaßen statt 64 verschiedenen Zahlenwerten ein herkömmliches Wort codieren,
bestehend aus bestimmten der 26 Buchstaben des Alphabets, was etwas anschaulicher sein dürfte. Als Beispiel
sei hier die beliebte Begrüßung unserer ehemaligen Mathematiklehrerin willkommen, die da heißt:
"MOORJEEEN". Wir wollen für dieses Wort nun einen einzigartigen Code finden, der ohne Zweifel
dekodierbar ist. Dies ist eine wichtige Voraussetzung, denn wir wollen auf Trennzeichen zwischen den Codes
49/73
verzichten (um nicht unnötig Speicher zu belegen) und automatisch erkennen, wo ein Buchstabe anfängt und
aufhört.
Zunächst bestimmen wir die relativen Häufigkeiten der einzelnen Buchstaben:
Dann ordnen wir die Paare nach Wahrscheinlichkeiten (von der größten zur kleinsten):
Nun fassen wir die beiden Buchstaben mit den kleinsten Wahrscheinlichkeiten zusammen und geben dem einen
den Code 0, dem anderen den Code 1:
Im nächsten Schritt werden wieder die beiden Elemente mit den kleinsten Wahrscheinlichkeiten
zusammengefasst, denen dann wieder die Ziffern 0, bzw. 1 zugeordnet werden. Die Buchstaben G und N
erhalten jeweils einen neuen Code, indem dem alten einfach 1 vorangestellt wird.
So verfahren wir nun, bis alle Buchstaben diesen Prozess durchlaufen haben:
Das Verfahren ist hiermit zu Ende geführt und zeigt nun für jeden Buchstaben einen Huffman-Code an,
dargestellt durch Binärzahlen. Unser Ausgangswort MOORJEEEN erhält jetzt also folgenden Code:
50/73
1000101101110000000111
Oft wird in der Praxis auch von einem Huffman-Baum gesprochen, da man den Vorgang, die jeweils seltensten
Werte zusammenzufassen und ihnen 0 oder 1 zuzuordnen, auch in Form eines (aus der Schulstochastik
bekannten) Wahrscheinlichkeits-Baumes darstellen kann, nur dass hier die Pfade einen Code für jedes Element
der Ergebnismenge angeben:
Den Code für ein bestimmtes Symbol liest man ab, indem man die einzelnen Pfade des Huffman-Baumes
entlangliest; für "J" ergibt sich so der Code 110. Die "leeren" Knoten sind keine Panne oder ein unschöner
Nebeneffekt, sondern notwendig: Sie sorgen dafür, dass die einzelnen Codes einzigartig sind und dass kein Code
Präfix eines anderen ist (das wird später noch genau erläutert).
Der Code 1000101101110000000111 ist eindeutig identifizierbar mit dem Ausgangswort MOORJEEEN, ohne
dass Trennzeichen nötig sind, was genau die Stärke der Huffman-Codierung ist: mit möglichst wenig Platz (es
entfällt Speicherplatz für Trennzeichen) kann eine lange Information gespeichert werden. Wir sehen auch, dass
die Buchstaben, die im Beispielwort oft auftauchen, kurze Codes erhalten haben. Das führt ebenfalls zur
Minimierung des Speicherplatzes. Wäre das Ausgangswort MOORJEEEN normal in Binärcode umgewandelt
worden, hätte man statt der 22 Stellen des Huffman-Codes (1000101101110000000111) 42 benötigt (jedem
Buchstaben wird seine Platzzahl im Alphabet in Binärform zugeordnet, außerdem kommen 8 Trennzeichen
hinzu, da die Codes nicht eindeutig sind).
Neben diesem Verfahren des Codierens gib es auch die arithmetische Codierung - sie unterscheidet sich wenig
von der Huffman-Codierung, da sie die Wahrscheinlichkeiten als Dezimalzahlen angibt, und nicht als Brüche.
Allerdings ist sie patentgeschützt, was viele Benutzer zurückschrecken lässt und wieder auf die HuffmanCodierung verweist.
8.3 Huffman-Codierung: Hintergründe
Im Folgenden wollen wir kurz darstellen, warum der Huffman-Code so ideal ist, weshalb er kurz ist und warum
er keine Trennzeichen benötigt. Dazu müssen wir etwas weiter ausholen: Die Huffman-Codierung gehört in das
große Feld der Informationstheorie. Eingeführt sei an dieser Stelle der Begriff der Entropie:
Betrachtet man ein Zufallsexperiment mit n möglichen Ausgängen, was durch den endlichen
Wahrscheinlichkeitsraum
mit
beschrieben wird, so herrscht Unsicherheit über den
Ausgang dieses Experiments. Die Unsicherheit über den Ausgang des Experiments messen wir mit der Zahl
H(p), der Entropie des Experiments. Das Maß der Unbestimmtheit muss nun auch anschaulich verständlich
gemacht werden: Wir stellen uns ein Experiment vor, in dem es n verschiedene Versuchsausgänge gibt. Die
Person A weiß schon, wie der Versuch ausgegangen ist, Person B soll dies mit Hilfe von Fragen herausfinden.
Die mittlere Anzahl von Fragen, die B benötigt, um die Antwort herauszufinden ist nun die wahre Entropie.
Wir gelangen so zur Definition: Für ein Zufallsexperiment
ist die wahre Entropie
der Erwartungswert der Anzahl benötigter Fragen bei optimaler Fragestrategie.
definiert als
51/73
Die Formel der sogenannten ideellen Entropie, mit der wir rechnen, nennen wir an dieser Stelle noch einmal (uns
ist sie bereits in Kapitel 2.3 begegnet):
Falls es Sie interessiert, geben wir Ihnen hier eine Herleitung im Anhang „Beweis: Jeder Huffman-Code ist
optimal“ an. Wer dem nicht ganz akribisch nachgehen möchte, dem liefern wir im Folgenden zwei Beispiele zur
Verdeutlichung:
1.
Das Experiment, bei dem schon vor Ausführung gesagt werden kann, wie es ausgeht, hat die wahre
Entropie 0. Im Allgemeinen gilt dann auch H(p) > 0
2.
Beim Münzwurf, also bei
ist offensichtlich optimal. Somit ist
welches Ereignis eingetreten ist.
, fragt man nach dem Versuchsausgang etwa: "Ist es
?" Das
, denn es ist nur eine Frage nötig, um herauszufinden,
Wir ersetzen jetzt die Worte "ja" und "nein" durch die Zeichen 0 und 1. Die Fragestrategie kann nun anhand
eines Codes ausgedrückt werden. Ein Wort sei eine endliche Folge von Nullen und Einsen. Ist
die Länge des Wortes, zum Beispiel hat
bezeichnen wir mit
Folge von Zeichen nennen wir das leere Wort, es hat die Länge 0.
die Länge
ein Wort, so
. Die leere
Damit ein Code optimal wird, muss er zwei Eigenschaften erfüllen: er muss die Präfixeigenschaft besitzen und
eine injektive Abbildung sein. Die Präfixeigenschaft besagt, dass kein Codewort Präfix eines anderen sein darf.
Praktisch gesagt heißt das, dass kein Codewort in den Anfangszeichen eines anderen Codewortes vorkommen
darf. Injektive Abbildung heißt, dass jedem Versuchsausgang eindeutig ein Codewort zugeordnet ist. Beide
Eigenschaften sind durch das Huffman-Verfahren gegeben, das speziell darauf ausgerichtet wurde, keine Codes
zu erzeugen, die Präfix eines anderes sein können.
Wir betrachten als Beispiel fünf Codes
, von denen aber nur drei brauchbar sind. Finden Sie heraus, welche
aus je einem der oben genanntem Gründen nicht benutzt werden können!
Haben Sie herausgefunden, welche beiden Codes nicht brauchbar sind? Code 1 und 2 sind nicht brauchbar: Code
1 ist nämlich nicht injektiv und Code 2 besitzt nicht die Präfixeigenschaft.
8.4 Codierungsmuster und Huffman-Codierung
Wieder zurück zu unserer quantisierten Matrix, bzw. unserem Vektor: Der Wert in der oberen linken Ecke der
quantisierten Matrix (bzw. der erste Wert unseres Vektoren) ist der DC-Wert - er wird gesondert verschlüsselt.
Weil er der mit Abstand der größte Wert ist, wird nämlich nicht sein eigener Wert codiert, sondern die Differenz
zum DC-Wert des vorangehenden Blocks:
52/73
Der Code besitzt zwei Symbole: das erste gibt an, wie viele Bits benötigt werden, um den codierten Wert zu
speichern. Zur Bestimmung dieser Bitzahl gibt es eine Tabelle im Anhang „Tabelle zur Bitzahl“. Symbol 2
gibt einfach den Wert an.
In unserem Beispiel sei der DC-Wert des vorangehenden Blocks 29. Die Differenz zu unserem Block ist damit 2.
Dieser Wert 2 wird nun in "Symbolform" gebracht: Zum Speichern der 2 werden 2 Bits benötigt und das Symbol
selbst ist 2. Daraus folgt die Zwischendarstellung in der Form (2)(2).
Für die Codierung der AC-Werte gilt nun ein etwas anderes Muster: Auch hier werden zwei Symbole benutzt,
das erste hat aber zwei Komponenten. Die erste Komponente ist die so genannte Lauflänge des Symbols, d.h.
die Anzahl der ununterbrochenen Nullen, die dem Symbol vorangehen seit dem letzten Symbol, was ungleich
null war. Die zweite Komponente ist wieder die Anzahl der Bits, die benötigt werden, um die Zahl zu speichern.
Im zweiten Symbol wird die Zahl selbst festgehalten.
Für unsere erste Zahl ungleich Null in der Zick-Zack Reihe, den DCT-Koeffizienten AC3, bedeutet das:
·
·
·
Symbol 1: Lauflänge 1 und Bitzahl 1
Symbol 2: der Wert selbst -7
Fertige Zwischendarstellung: <(1;1),-7>
53/73
Der quantisierte DCT-Koeffizient AC70 zum Beispiel hat den Wert -3. Dieser Wert kann mit 2 Bit codiert
werden, vor ihm stehen im Zick-Zack-Kurs 11 Nullen. Also lautet seine Tupel-Beschreibung <(11;2),-3>.
Die Nullen, die in der letzten langen Sequenz hintereinander auftauchen, werden mit einen "End-of-block"Symbol dargestellt: (0;0), d.h. es folgen bis zum Ende des Blocks nur noch Nullen.
Alle Werte des Blocks müssen in diese Art der Zwischendarstellung umgeformt werden, um sie dann zu
codieren. Die geschieht nun mit der oben angedeuteten Huffman-Codierung.
Symbol 1 und Symbol 2 werden getrennt auf der Basis einer stochastischen Auswertung codiert. Diese
Auswertung kann man wie im obigen Beispiel beschrieben selbst vornehmen, um dann für jedes Symbol einen
einzigartigen Code zu erhalten. Allerdings ist dies bei den 8*8 Blöcken sehr viel Arbeit, die man sich ersparen
kann. Es gibt nämlich Tabellen, die auf empirischen Werten beruhen und so ein schnelleres Verfahren
ermöglichen (zwar sind diese Tabellen nicht immer optimal, weil sie eben allgemein für alle Matrizen gelten,
aber da sie vorgefertigt sind und die herkömmlichen zu verschlüsselnden Werte abdecken, kann zugunsten der
gesparten Mühe beim Selbercodieren ein nicht zu 100% optimaler Code hingenommen werden). Wir haben
einige solcher Tabellen ausgewählt, die uns die Mühe beim Codieren erleichtern - wer mag, kann gerne selbst
eine stochastische Auswertung unseres Vektors vornehmen und sich selbst einen Code basteln, es wird aber viel
Arbeit werden. Eine „Beispielcodierung für unseren Vektor“ geben wir Ihnen im Anhang an.
54/73
9 Decodierung der JPEG-Bilddatei
Nachdem jede einzelne 8*8-Pixelmatrix, die 64 Bildpunkte mit je 3 Layers (Helligkeits-, Farbton- und
Farbsättigungswerte von 0 bis 255) trägt, die Indexverschiebung, die Diskrete Cosinus Transformation, die
Quantisierung und die Huffman-Codierung durchlaufen hat, ist die JPEG-Kompression abgeschlossen: Eine
Bilddatei mit wenig Speicherplatzbedarf liegt uns vor.
Nun ist die schönste und effektivste Datenkompression sinnlos, wenn die Ursprungsdaten nicht wieder
hergestellt werden können: Das JPEG-Format ist natürlich auch decodierbar, sodass die komprimierten Bilder
auch wieder angeschaut werden können.
Wie wir jedoch während der letzten Kapitel schon angedeutet haben: Das Ausgangsbild lässt sich nicht zu
100% wieder herstellen, denn wir haben beim Komprimieren ja einen Verlust an Bilddaten in Kauf
genommen.
Um das komprimierte Bild nun wieder herzustellen, wird das gesamte bisherige Verfahren "rückwärts"
angewandt.
9.1 De-Codierung
Zuerst wird der Binärcode entschlüsselt, den wir nach dem Huffman-Verfahren selbst (oder mit Hilfe von
empirischen Codierungs-Tabellen) erstellt haben. Dieses bedarf keiner großen Rechenoperationen, da der
Huffman-Code ja die Präfixeigenschaft erfüllt (siehe Kapitel 8.3). Somit ist beim Lesen des Binärcodes für den
PC ohne Trennzeichen eindeutig, wann ein Wert aufhört und wann ein neuer anfängt. Welcher Binärcode
welcher Zwischendarstellung entspricht, entnimmt der PC beim Lesen der Bilddatei entweder den
mitgespeicherten Tabellen oder den programmeigenen empirisch erstellen Tabellen, auf die in der Bilddatei
verwiesen wird.
Liegen nun erst einmal die Zwischendarstellungen (wir erinnern uns: in Tripel-Form) vor, können ebenso
problemlos die 8*8-Blöcke wieder zusammengesetzt werden, da die Tripel ja angeben, welcher Wert an welcher
Stelle innerhalb eines 1*64-Vektors steht und wie viele Nullen ihm vorausgehen. Alle Vektoren sortieren wir
nach dem rückwärts angewandten Zick-Zack-Verfahren (siehe Kapitel 8.1) wieder um, sodass wir je eine 8*8Matrix erhalten, in der die bearbeiteten DCT-Koeffizienten stehen.
9.2 Dequantisierung
Bis hierhin ist die Entschlüsselung der JPEG-Kompression nicht sonderlich schwierig, da es sich um reine,
einfache Umkehroperationen handelt, denen man die Binärwerte unterzieht. Nun haben wir also eine Beispiel8*8-Matrix mit bearbeiteten DCT-Koeffizienten, aus denen wir wieder die ursprüngliche Farbinformationen
lesen wollen.
Durch die Dequantisierung können jedoch die ursprünglichen, unbearbeiteten DCT-Koeffizienten nicht wieder
korrekt hergestellt werden, da man mit gerundeten Werten arbeitet (siehe Kapitel 7). Es werden die durch
Division der DCT-Koeffizienten durch den jeweiligen Quantisierungsfaktor Q(u,v) entstandenen quantisierten
Werte mit Q(u,v) multipliziert:
Hierdurch erhält man DCT Koeffizienten, die von den ursprünglichen etwas abweichen.
55/73
9.3 Die Inverse Diskrete Kosinustransformation
Durch die inverse DCT werden aus den decodierten und dequantisierten DCT-Koeffizienten nun wieder
Pixelwerte hergestellt. Diese Pixelwerte entsprechen natürlich nicht genau den ursprünglichen f(x,y), da im
Laufe der Quantisierung Informationen weggefallen sind. Die inverse DCT kann aber im Prinzip, also wenn sie
mit den genauen DCT-Koeffizienten arbeiten würde, die ursprünglichen Pixelwerte wieder genau herstellen.
Die Formel der zweidimensionalen inversen DCT lautet:
9.1
Wir haben in Kapitel 6 dargelegt, dass die f(x,y)-Werte als überlagerung von Kosinusfunktionen aufgefasst
werden und dass durch die DCT die Durchschnittsamplituden jeder relevanten Kosinusfunktion berechnet
werden. "Überlagerung" bedeutet nun, dass ein f(x,y)-Wert der Summe der Funktionswerte aller berechneten
Kosinusfunktionen an der Stelle (x,y) entspricht.
Man erhält aus den Amplituden wieder die f(x,y)-Werte, indem man durch Multiplikation der Amplituden mit
dem Kosinus an der Stelle (x,y) die Funktionswerte der Kosinusfunktionen an dieser Stelle berechnet und alle
miteinander addiert. Da F(u,v) einem Vielfachen der Durchschnittsamplitude der Kosinusfunktion mit der
Frequenz der Nummer (u,v) entspricht, multipliziert man F(u,v) mit obigen Faktoren, wodurch man dann die
Durchschnittsamplitude erhält.
Hierbei ist natürlich auffällig, dass die Faktoren, mit denen F(u,v) multipliziert wird, nämlich
9.2
die gleichen sind, die auch schon bei der Forward DCT benutzt wurden. Es ist angenehm, dass man keine neuen
Faktoren definieren musste. Das ist auch der Grund dafür, warum die Faktoren von vorn herein so gewählt
wurden.
Bevor man bei der Forward DCT die Faktoren benutzt gibt die Summe in 6.18 den Wert
aus, wobei
die Durchschnittsamplitude ist.
Durch Anwendung der obigen Faktoren 9.2 erhält man dann für F(u,v):
.
Multipliziert man F(u,v) bei der inversen DCT dann wieder mit den Faktoren 9.2 erhält man also:
56/73
Bei der inversen DCT kann man demnach wieder die gleichen Faktoren benutzen, wodurch man die
Durchschnittsamplituden erhält, mit denen man dann die Funktionswerte der Kosinusfunktionen ausrechnen
kann. Wenn man dann noch diese Funktionswerte aufaddiert, wie in 9.1, erhält man f(x,y). Eine ZurückVerschiebung in die Wertemenge [0;255] ergibt dann die ursprünglichen, diskretierten Pixel, die Orts- und
Farbinformationen tragen - das komprimierte Ausgangsbild (eine Konvertierung zurück in den RGB-Farbraum
kann erfolgen).
57/73
10 Verschiedene Dateitypen im Vergleich
Dieses Kapitel haben wir in der Druckversion bewusst ausgelassen; es enthält nur unwesentliche Informationen
zur JPEG-Kompression selbst, sondern soll dabei helfen, das Format JPEG im Vergleich zu anderen digitalen
Bildformaten zu bewerten, benötigt dafür aber eine Menge Platz.
11 Änderungen in JPEG2000
JPEG2000 ist der Nachfolger des schon über 10 Jahre alten Formats JPEG.
JPEG hatte vor allem zwei Schwachpunkte: Zum einen konnten keine zusätzlichen Informationen bei den Daten
abgespeichert werden, was heute jedoch in vielen Fällen dringend benötigt wird (zum Beispiel Informationen
über den Autor des Bildes, digitale Wasserzeichen, Kommentare etc.), zum anderen treten bei hohen
Kompressionsraten starke Verfälschungen im dekomprimierten Bild auf, was ja, wie wir inzwischen wissen,
durch die diskrete Cosinus-Transformation und die Quantisierung verursacht wird.
JPEG2000 hat nun einige veränderte technische Eigenschaften, die entscheidende Qualitätsverbesserungen zur
Folge haben. Zunächst wird die diskrete Cosinus-Transformation durch die Wavelet-Transformation ersetzt.
Diese neue Transformation teilt das Bild nicht mehr in 8*8 Blöcke, sondern codiert es fortlaufend, so dass
höhere Kompression, aber bessere Bildqualität erreicht wird als bei JPEG. Die Datenmenge wird auch geringer,
was in einer höheren Geschwindigkeit beim Übertragungsvorgang resultiert. Dies ist bei der heutigen Nutzung
von Netzwerken und Internet nur zu begrüßen.
Zusammenfassend und als Anreiz, sich weiter über unsere Arbeit hinaus mit dem Thema JPEG-Kompression zu
befassen, lässt sich also sagen, dass die entscheidenden Schwachpunkte des alten JPEG-Verfahrens durch
JPEG2000 wegfallen, bzw. deutlich reduziert werden.
58/73
Resümee
Bilder werden digitalisiert, indem sie räumlich und farblich diskretiert werden, das heißt, sie werden in
quadratische Bildpunkte, sogenannte Pixel, zerlegt. Jeder Bildpunkt enthält eine Orts- und eine Farbinformation.
Ein digitales Bild
ist demnach als eine Matrix zu verstehen, die
Pixel hat, wobei
und
Zeilen und
. Die Elemente
Grauwert oder die Farbe des Bildpunktes an der Stelle
des Bildes
Spalten, also
sind die Pixel, die den
angeben.
Beim Digitalisieren bestimmen Rasterung und Quantisierung das Aussehen des digitalen Bildes: Die
Rasterung definiert die Größe eines Bildbereichs, die 1 Pixel zugeordnet wird, die Quantisierung gibt an, wie
viele Farbinformationen ein Pixel aufnimmt (2=Schwarz/weiß; 256 Graustufen=normales Graubild; 16,7 Mio.
Farben=normales Farbfoto). Die Auflösung eines Bildes, das heißt, wie groß ein Pixel ist, bzw. wie viele Pixel
auf ein bestimmtes Maß passen, wird in dpi angegeben: Dots per Inch (Pixel pro Inch).
Wird nun ein digitales Farbbild gespeichert, so besitzt es 3 Schichten (Layers), die jeweils eine Farbinformation
tragen: Eine speichert die Rot, eine die Grün- und eine die Blauwerte, die jeweils zwischen 0 und 255 liegen.
Dies ist das gängige RGB-Modell. Wenn ein RGB-Bild ohne Qualitätsverlust gespeichert wird (zum Beispiel im
TIFF- oder im BITMAP-Format), so wird viel Speicherplatz benötigt: Jeder Pixel kann 2563 verschiedene Werte
annehmen (256 für jeden Layer), die binär codiert werden müssen und entsprechend Platz in Anspruch nehmen.
Wenn nun der Speicherbedarf eines Bildes mit der JPEG-Kompression reduziert wird, werden verschiedene
Mittel genutzt, den Speicherumfang zu verringern.
Die vorhandenen RGB-Bilddaten werden zunächst in den YUV- oder YCbCr-Raum übertragen. Statt eine
Farbinformation über Rot-, Grün- und Blauwerte darzustellen, wird sie durch Helligkeit, Farbton, Farbsättigung
(YUV), bzw. durch Helligkeit, Abweichungen vom Grau- zum Blauwert und Abweichung vom Grau- zum
Rotwert (YCbCr) ausgedrückt.
Y = 0,299R + 0,587G + 0,114B
U = 0,493(B - Y)
V = 0,877(R - Y)
bzw.
Y = 0,299R + 0,587G + 0,114B
Cb = -0,1687R - 0,3313G + 0,5B + 128
Cr= 0,5R - 0,4187G - 0,0813B + 128
In den beiden Farbräumen YUV und YCbCr kann man sich zu Nutze machen, dass das menschliche Auge für
Helligkeitsunterschiede empfindlicher ist als für Farbunterschiede; daher werden die Helligkeitswerte genauer
gespeichert als die anderen Informationen: Es wird ein Subsampling vorgenommen, indem mehrere Farbwerte
gemittelt werden und dieser gemittelte Wert stellvertretend für die Originalwerte gespeichert wird. Die
gängigsten Subsampling-Verhältnisse sind 4:2:2 und 4:1:1, was bedeutet, dass, während die Y Werte, also die
Helligkeitswerte, mit voller Auflösung gespeichert werden, die beiden Farbwerte U, V oder Cb, Cr nur mit
jeweils halber bzw. viertel Auflösung gespeichert werden. Für sie werden 4 Werte zu zwei bzw. zu einem
gemittelt.
Was nun folgt, ist die Indexverschiebung, die die 256 Werte aus der Wertemenge [0; 255] in die Wertemenge [128;127] verschiebt. Für die folgenden Operationen zerlegt man das Bild außerdem in seine einzelnen Layer und
diese jeweils in 8*8-Pixel-Blöcke. Diese enthalten Pixelwerte aus Wertemenge [-128;127], die durch eine
Funktion f(x,y) beschrieben werden, wobei x und y die Koordinaten des Pixels sind.
Auf diese Werte wendet man die zweidimensionale diskrete Kosinustransformation (DCT) an. Die Formel
hierfür lautet:
59/73
Bei der DCT werden die f(x,y) Werte als Resultat von überlagerten Kosinusfunktionen interpretiert. Wenn man
nun ein gewisses f(x,y) als Wert einer Kosinusfunktion einer bestimmten Frequenz und Amplitude am Ort (x,y)
festlegt, kann man f(x,y) schreiben als
Für die gleiche Frequenz, gemeint sind damit die beiden Frequenzen in den zwei Dimensionen, kann man dies
auch für alle anderen (x,y) festlegen. Da die f(x,y) Werte in natürlichen Bildern gewöhnlicherweise nicht genau
eine bestimmte zweidimensionale Kosinusfunktion beschreiben, erhält man für die verschiedenen (x,y)
unterschiedliche Amplituden. Ein f(x1,y1) muss dann durch die Kosinusfunktion der vorausgesetzten Frequenzen
(u,v) mit der Amplitude Au,v(x1,y1) entstanden sein, ein f(x2,y2) durch eine mit Au,v(x2,y2). Durch Einsetzten des
neuen Ausdrucks für f(x,y) erhält man:
Diese Formel errechnet nun einen Wert, der für
das Vierfache eines Mittelwertes aller
Amplituden für die bestimmte Frequenz angibt. Dieser Mittelwert ist normalerweise nicht arithmetisch, da die
quadrierten Kosinuswerte gewöhnlich nicht für jeden Ort gleich 0,5 sind. Für
ist F(u,v) um
größer als ein solcher Mittelwert. Außerdem berechnet man mit obiger Formel für F(0,0) das
den Faktor
achtfache des arithmetischen Mittelwertes aller f(x,y).
Da das F für eine bestimmte Frequenz (u,v) nur eine Art Mittelwert angibt, lässt sich durch diesen Wert nicht das
ursprüngliche f(x,y) wiederherstellen. f(x,y) ist nicht hinreichend durch das F einer u,v Kombination
beschrieben. Deshalb werden mehrere F(u,v) Werte berechnet, aus denen dann später die originalen f(x,y)
berechnet werden können.
Die F(u,v) Werte werden nun noch quantisiert, indem man sie durch Quantisierungsfaktoren Q(u,v) einer
Quantisierungstabelle dividiert und auf die nächste Integerzahl rundet:
Damit wird erreicht, dass viele hohe Frequenzen, die durch kleine Werte repräsentiert werden, durch das Teilen
mit großen Faktoren und das anschließende Runden gleich Null werden, was bei der nun folgenden Codierung
Vorteile und Platzersparnis bringt.
Bei der Codierung geht es darum, die Koeffizienten des 8*8-Blocks mit einem einzigartigen Binärcode zu
verschlüsseln. Dazu wird die sogenannte Huffman-Codierung herangezogen, mit der dies optimal möglich ist.
Im ersten Schritt werden die Werte der Matrix in eine Lauflängen-Zwischendarstellung gebracht, die angibt,
wie viele Nullen einem bestimmten Wert vorangehen (damit werden lange Folgen von Nullen möglichst
platzsparend zusammengefasst), wie viele Bits zur Speicherung des Wertes notwendig sind und was der Wert
selbst ist. Jeder Wert ungleich 0 wird demnach als Tripel (3-Tupel) zwischendargestellt.
Diese Zwischendarstellungen werden nun stochastisch ausgewertet, d. h. es werden die relativen Häufigkeiten
der Werte aufgelistet. Um zu codieren, werden nun immer den beiden Werten mit den kleinsten
60/73
Wahrscheinlichkeiten der Code 0 und 1 zugeordnet. Im nächsten Schritt wird den bereits entstandenen Codes
diese 0 oder 1 vorangestellt (die jeweils neu verschlüsselten Werte erhalten wieder eine einzelne 0 oder 1 als
Code, dem dann ggf. weitere Symbole vorangestellt werden). So wird mit den Werten weiter verfahren, bis allen
ein einzigartiger Binärcode zugeteilt ist, der am so entstandenen Huffman-Baum abgelesen werden kann. So
werden den am häufigsten auftretenden Werten kurze Codes zugeteilt, weniger häufig vorkommenden hingegen
lange Codes. Um nicht für jedes Bild und jede Matrix aufwendig neue Codes zu kreieren, werden häufig bereits
fertige Verschlüsselungstabellen benutzt, die auf empirischen Daten beruhen und im großen und ganzen eine
recht ordentliche Codierung bieten. Dieser Binärcode, der die Präfixeigenschaft besitzt (d.h. die codierten
Symbole sind eindeutig und kein Code kommt im Anfang eines anderen Codes vor), kann dann ohne
Trennzeichen Tripel-Wert für Tripel-Wert zusammengesetzt werden und stellt so die Codierung der 8*8-Blöcke
dar.
Um das Bild nun wieder herzustellen, wird das gesamte bisherige Verfahren "rückwärts" angewandt.
Zuerst wird also der Binärcode entschlüsselt, was anhand der Codierungs-Tabellen ja ohne weiteres möglich
ist: da der Code die Präfixeigenschaft erfüllt, ist eindeutig, welcher Code zu welcher Zwischendarstellung
gehört; dem angewandten Huffman-Verfahren ist es eigen, dass die lange Code-Kette ohne Probleme oder
Verwechslungen wieder in die richtigen einzelnen Ausgangswerte zerlegt werden kann. Anhand der
entschlüsselten Zwischendarstellungen (in Tripel-Form) können nun wieder die 8*8-Blöcke zusammengesetzt
werden, da die Tripel ja angeben, welcher Wert an welcher Stelle steht und wie viele Nullen ihm vorausgehen.
Durch die Dequantisierung der nun vorliegenden Werte, also durch Multiplikation mit dem jeweiligen
Quantisierungsfaktor, können die ursprünglichen DCT Koeffizienten nur mit Abweichungen wiederhergestellt
werden, da ja nach dem Quantisieren gerundet wurde. Dieses macht sich in der Bildbeschaffenheit bemerkbar: Je
stärker anfangs quantisiert wurde, desto mehr Ungenauigkeiten und auch Fehler (sogenannte Artefakte) hat das
Bild am Ende.
Jeder der 64 nun erhaltenen F(u,v) Werte pro 8*8-Matrix ist ein Vielfaches einer Durchschnittsamplitude, aus
der für einen konkreten Ort (x,y) mithilfe der Kosinusfunktion ein ganz bestimmter Wert f'u,v(x,y) erzeugt
werden kann, der, unabhängig von den Ungenauigkeiten der Dequantisierung, normalerweise nicht dem
ursprünglichen Pixelwert f(x,y) entspricht. Der Grund dafür ist offensichtlich: Die F(u,v) Werte sind Vielfache
der Durchschnittsamplitude für alle Orte, welche normalerweise nicht der zu (x,y) gehörenden Amplitude
Au,v(x,y) entspricht, durch die mithilfe der Kosinusfunktion der Wert f(x,y) hergestellt werden kann. Würden die
F(u,v) Werte nicht den Vielfachen sondern den Durchschnittsamplituden entsprechen, würde man durch
Addition aller f'u,v(x,y) für einen konkreten Ort und für alle Frequenzen den ursprünglichen Wert f(x,y) erhalten.
Die verschiedenen F(u,v) Werte entsprechen aber bestimmten Vielfachen der Durchschnittsamplituden, weshalb
jeder noch mit einem Faktor verkleinert werden muss, bevor man ihn anwendet, um ein f'u,v(x,y) zu berechnen.
Dieser Faktor ist
Jetzt erst offenbart sich nämlich der Grund für die Wahl dieser Faktoren bei der DCT. Allein durch die Summen
in der Formel
erhält man nämlich Werte, die um den Faktor
61/73
größer sind als die jeweilige Durchschnittsamplitude. Für die Berechnung von F(u,v) multipliziert man diese
deshalb mit den oben genannten Faktoren. Für F(u,v) erhält man dann
also ein Vielfaches der Durchschnittsamplitude für die Frequenz (u,v).
Um die Durchschnittsamplitude zu erhalten und um die davon abhängigen f'u,v(x,y) zu erhalten, multipliziert man
jedes F(u,v) bei der inversen DCT wieder mit dem gleichen Faktor, der schon bei der forward DCT benutzt
wurde. Man erhält dann:
Diese Durchschnittsamplitude kann man nun benutzen, um die f'u,v(x,y) zu berechnen, die dann aufaddiert
werden, um f(x,y) zu erhalten:
Die erhaltenen f(x,y) Werte repräsentieren nach dem Verschieben in die Wertemenge [0;255] wieder Helligkeitsund Farbwerte, die dann (Layer für Layer und Matrix für Matrix zusammengesetzt) als Bild dargestellt werden
können.
62/73
Anhang
Hintergrund-Information: Bits und Bytes
Jedwede Information wird von den Computer-Schaltkreisen auf das Erkennen niedriger und hoher Spannungen
reduziert. Niedrige Spannungen bekommen den Wert 0 zugeordnet, hohe den Wert 1. Mit diesen beiden Werten
(daher "binär") kann jede Information dargestellt werden; die kleinste Speichereinheit (die entweder den Wert 0
oder den Wert 1 annehmen kann) wird "Bit" genannt.
Der Begriff wurde von dem amerikanischen Mathematiker Claude Shannon
(geboren 1916, gestorben 2001) geprägt, er führte ihn erstmals 1940 in seiner
Doktorarbeit "Symbolic Analysis of Relay and Switching Circuits" am
Massachusetts Institute of Technology (MIT) ein. Ausgangspunkt war damals die
Frage, wie man menschliche Vermittler in Telefonzentralen ersetzen könnte. In der
Abhandlung beschreibt C. Shannon die Anwendung sogenannter Boolscher Logik
in elektronischen Schaltkreisen (i.e. die Formulierung und Lösung von Problemen
durch die beiden Symbole 0 und 1), womit er die Grundlagen der Informatik
formulierte.
Shannon wird uns in dieser Arbeit an späterer Stelle noch begegnen, nämlich
immer wenn es um Datenspeicherung geht...
Hintergrund-Information zu CCD-Sensoren und zur Signalübersetzung
CCD-Sensoren sind Halbleiterelemente - angeordnet wie ein Schachbrettmuster -, die z.B. lichtempfindliche
Siliziumzellen tragen. Aufgrund der physikalischen Eigenschaften haben sie die Möglichkeit, jede einzelne
dieser Zellen auszulesen, was z.B. bei einem Silberkorn nicht möglich war.
Erzeugung der Farben über die Belichtung lichtempfindlicher Zellen durch drei Farbfilter: Die Helligkeitswerte
hinter den Filtern werden von den CCD-Sensoren erfasst, die in Form eines Schachbrettmusters z.B.
lichtempfindliche Siliziumzellen tragen und den gemessenen Wert an den PC senden (Bild: www.digit.de).
Nun gibt der CCD-Sensor die gemessenen Helligkeitswerte in Form von elektrischer Spannung an den PC
weiter, der jedoch mit den Stromsignalen nichts anfangen kann. Daher muss eine übersetzungseinheit (ein
sogenannter Analog/Digital-Wandler) zwischengeschaltet werden, der jedem Spannungswert eine Kombination
aus 0 und 1 zuordnet.
63/73
Aufbau eines CCD-Sensors: Die lichtempfindlichen Siliziumzellen, die die eingehende Lichtintensität messen,
sind blau dargestellt; die Schicht, die die Ladungen transportiert, die später in einem Analog/Digital-Wandler in
für den PC "verständliche" Binärcodes umgewandelt werden, ist grau eingefärbt (Bild: www.digit.de).
Hintergrund-Information zur Entstehung von JPEG
JPEG ist die Abkürzung für die Gruppe "Joint Photographic Expert Group", einer Zusammenarbeit vom CCITT
(Consultative Comittee in International Telegraph and Telephone) und der ISO/IEC (International Standards
Organisation/International Electronic Comisson), die 1988 einen Standard zur Bildkompression entwickeln
wollte, da es damals kein digitales Bildformat mit guter Kompression gab und sich mit der verstärkten Nutzung
des Internets der Bedarf an einem gut komprimierenden Bildformat abzeichnete.
Das Ergebnis dieser Zusammenarbeit wurde 1992 veröffentlicht: Der erste Format-Entwurf hieß damals noch
"ISO/IEC International Standard 10918-1"; der Gruppenname "JPEG" wurde jedoch bald zum Namen für diesen
Standard selbst.
Schnell erfreute sich das Bildformat auf der ganzen Welt großer Beliebtheit, da es neben der hohen
Kompressionsrate, die erzielt werden kann, oder auch der Option, die Bilddaten auch ohne Verlust zu speichern,
jedes beliebige Farbmodell unterstützt (z.B. RGB, YUV oder auch YCbCr).
Beispielrechnung für das Subsampling
Angenommen, für die Speicherung jedes Wertes wird ein Byte benötigt, dann werden für 4 Pixel mit jeweils 3
Werten bei voller Auflösung 12 Byte benötigt. Bei Anwendung eines Subsamplings kann der Speicherbedarf
jedoch reduziert werden:
·
·
für ein 4:2:2-Subsampling: 4 Byte + 2 Byte + 2 Byte = 8 Byte
für ein 4:1:1-Subsampling: 4 Byte + 1 Byte + 1 Byte = 6 Byte
Nur durch unterschiedliche Auflösung der einzelnen Layer kann also bereits eine Datenmengenreduzierung von
bis zu 50% erreicht werden.
Anmerkung der Verfasser zur Indexverschiebung
Die Annahme, dass es für die Anwendung der DCT genügt, dass die Mitte aller Pixelwerte bei -0,5 liegt, gründet
auf einer Einschätzung der Verfasser.
Wir haben leider keine Literatur gefunden, die diese ungünstigen Folgen der Indexverschiebung (nämlich, dass
die Mitte aller Pixelwerte nicht genau 0 ist) näher erläutert. In unseren Quellen hieß es stets lediglich, dass die
64/73
Pixelwerte in die Wertemenge [-128; 127] übertragen werden. Darauf, dass dadurch die Pixelwerte jedoch
immer noch nicht symmetrisch um den Nullpunkt verteilt sind, wurde nicht eingegangen.
Nach Meinung der Verfasser wäre es günstiger, für die Pixelwerte eine Wertemenge zu definieren, in der die
Werte symmetrisch um den Wert 0 angeordnet sind. Zweckmäßig wäre hierfür die Wertemenge [-128; 128] ohne
0. Definierte man solch eine Wertemenge, könnten alle Pixelwerte als Werte einer Kosinusfunktion der Frequenz
u mit der Amplitude Au(x) aufgefasst werden, die symmetrisch um den Wert 0 schwingt. Wie bei solchen
Kosinusfunktionen haben dann auch die niedrigsten und höchsten Elemente unserer Wertemenge den gleichen
Betrag. Wie man noch sehen wird, wird bei der DCT für keinen Pixelwert die Stelle auf der Kosinusfunktion
angenommen, an dem der Kosinus 0 ist, weshalb auch kein Pixelwert 0 nötig ist.
Hintergrund-Information zur "gleichmäßigen Verteilung"
Die Differenzen vom Anfang des Intervalls zum kleinsten definierten x-Wert, 0, und vom Ende des Intervalls
zum größten definierten x-Wert, 7, haben beide den Betrag 0,5. Außerdem sind die Differenzen zwischen den
einzelnen definierten x-Werten gleich 1. Wenn man nun das Intervall halbiert, erhält man die zwei Teilintervalle
I1 = [ -0,5; 3,5[ und I2 = [ 3,5; 7,5[. In beiden befinden sich 4 definierte x-Werte. In einem Teilintervall
unterscheiden sich der kleinste und der größte definierte x-Wert vom Anfang bzw. Ende des Teilintervalls um
den Betrag 0,5. Dies geschieht am Berührpunkt der Teilintervalle durch die Halbierung der definierten x-Wert
Differenz 1.
Bei einer weiteren Halbierung der Teilintervalle in 4 Intervalle der Länge 2 wird die gleichmäßige Verteilung in
analoger Weise erhalten.
Beweis: Alle 7 g(u)-Werte sind verschieden
Wie man in der Tabelle sieht, gibt es nur 7 verschiedene Werte, die
Wichtig ist nun, die Frage zu beantworten, ob für ein x und alle
für
annehmen kann.
die bestimmte Werte der Funktion
mehrmals vorkommen.
Wir werden nun beweisen, dass dies nicht der Fall ist, indem wir davon ausgehen, dass Werte mehrmals
vorkommen, um dann in der Rechnung einen Widerspruch zu erkennen. Diese vorgehensweise wird auch
indirekter Beweis genannt.
Behauptung: Es gibt mindestens zwei Werte von g(u) für
Diese Behauptung ist wahr, wenn
beliebigen ungeraden Vielfachen von
, die gleich sind.
zwei Winkel annehmen kann, die den gleichen betraglichen Abstand zu
besitzen.
65/73
Für h gilt dann:
,
ist. Der Term (2m + 1) ist dann eine ungerade Zahl. Damit die Abstände zweier Winkelwerte
wobei
und
zu ungeraden Vielfachen von
gleich groß sind, muss
sein.
Das heißt es muss gelten:
,
6.20
wobei
.
Die Terme (2m + 1) sowie (2n + 1) ergeben dann ungerade Zahlen.
Setzen wir nun
Man kann
ein:
kürzen:
66/73
Man kann nun den Faktor 16 kürzen:
6.21
Zur weiteren Bearbeitung muss man eine Fallunterscheidung machen. Es gibt zwei zu unterscheidende Fälle:
1.
2.
Die Werte in den Betragszeichen sind auf der linken und rechten Seite der Gleichung gleich.
Die Werte in den Betragszeichen sind auf der linken und der rechten Seite der Gleichung betraglich
gleich, aber mit anderem Vorzeichen.
Man muss für die beiden Fälle anders vorgehen. Betrachten wir zunächst den ersten Fall. Da die Werte gleich
sind, benötigt man keine Betragszeichen mehr:
Die Terme (u1 - u2) und (m - n) sind ganze Zahlen. Deshalb bedeutet die Gleichung, dass die Werte 16 und (2x +
1) gemeinsame Vielfache besitzen. Durch Primzahlzerlegung kann man beweisen, dass diese Gleichung nicht
stimmt und das es kein gemeinsames Vielfaches gibt. Primzahlzerlegung der rechten Seite der Gleichung liefert:
Wenn die rechte und die linke Seite ein gemeinsames Vielfaches besitzen, muss die linke Seite der Gleichung
nach einer Primzahlzerlegung also den Faktor 24 besitzen.
(2x + 1) kann aber nur ungerade Werte annehmen, enthält also noch nicht einmal den Faktor 2. (u1 - u2) dagegen
kann zwar gerade Werte annehmen jedoch nur bis höchstens 6, wie z.B. bei (7 - 1). In diesem Term ist also als
zweierpotenz höchstens der Faktor 22 enthalten. Durch das Produkt (2x + 1)(u1 - u2) kann demnach kein
Vielfaches von 16 gebildet werden.
Für den 2.Fall verfahren wir ähnlich. Da hier die Betragszeichen in der Gleichung gebraucht werden, muss man
bestimmten Rechenregeln, die für Beträge gelten, folgen. Nach diesen Regeln muss man in solchen Gleichungen
einen Wert auf der einen Seite subtrahieren, wenn man ihn auf der anderen Seite addiert. Aus 6.21 wird dann:
Wegen der Betragszeichen kann man auf der rechten Seite mit -1 multiplizieren. Klammert man dazu noch 16
aus, wird daraus:
67/73
Auch hier kann die Gleichung nicht stimmen, da von dem Term in den Betragszeichen auf der linken Seite kein
Vielfaches gebildet werden kann, das den gleichen Betrag hat wie ein Vielfaches von 16. Denn (2x + 1) ist auch
hier immer ungerade und (u1 + u2) kann an geraden Werten nur solche bis 12 annehmen. Die höchste
zweierpotenz, die in (u1+u2) entahlten sein kann, ist 23. Damit ist es nicht möglich ein Vielfaches zu bilden, dass
den gleichen Betrag wie ein Vielfaches von 16 hat.
Es ist nun bewiesen, dass g(u) für ein festes x nie den gleichen Wert mehrmals annehmen kann.
Tabelle zur Bitzahl
Zur Bestimmung der zur Speicherung der Differenz zum DC-Wert des vorangehenden Blocks erforderlichen
Bitzahl wird nun eine Tabelle herangezogen:
Die auf den ersten Blick vielleicht unverständliche Zuordnung der Bits zu den jeweiligen Werten ist sehr einfach
- das Prinzip lautet: Die Anzahl der Stellen der zu kodierenden Zahl in Binärschreibweise (Zweiersystem) ist die
Anzahl der Bits. Bei negativen Zahlen wird dieses System genauso angewandt.
Beispiel:
·
·
Die Zahl "1" im Zehnersystem ist auch die Zahl "1" im Zweiersystem, hat dort also eine Stelle und ist
damit mit einem Bit speicherbar.
Die Zahl "130" im Zehnersystem ist die Zahl "10000010" im Zweiersystem, hat dort acht Stellen, wird
demnach mit acht Bits gespeichert.
Beweis: Jeder Huffman-Code ist optimal
Da unsere eigenen Beweisansätze leider gescheitert sind, wir aber trotzdem einen Hintergrund zu der Aussage
liefern wollen, dass der Huffman-Code eine optimale Darstellung ist, haben wir folgenden Beweis dem
Vorlesungsskript Stochastik von Prof. E. Bolthausen (Zürich) entnommen.
Er verläuft mit Induktion nach n, der Länge des Wahrscheinlichkeitsvektors. Der Fall n=2 ist trivial.
Induktionsschluss von n - 1auf n: Wir nehmen an, dass der Satz für Vektoren der Länge
Sei (p1,....,pn) ein beliebiger Wahrscheinlichkeitsvektor der Länge n mit
für alle
gezeigt ist.
.
68/73
Wir können annehmen, dass
erreichen.
gilt, denn dies lässt sich durch Vertauschen stets
ein Huffman Code für diesen Vektor. Sei
Sei
ein beliebiger anderer Code mit den Codewörtern
. Wir zeigen nun
(1)
.
nach aufsteigender Länge. Den geordneten Code nennen wir
Zunächst ordnen wir die Codewörter von
; für die Codewörter gilt
. Die Menge der Codewörter ist dieselbe
geblieben. Es ist ziemlich offensichtlich, dass
Wort
, indem wie von
die letzten
ist. Falls
ist, so stutzen wir das
Binärzeichen weglassen. Dieses Wort sei
. Wegen
. Das neue Wort
kann aber auch nicht
der Präfixeigenschaft unterscheidet sich dieses Wort von
Präfix eines der anderen Wörter sein, denn seine Länge ist zumindest die der anderen. Also ist
ein Code.
, so setzen wir
Gilt
haben die Länge
oder
. In jedem Fall gilt
. Sei
. Mindestens zwei Wörter von
das aus den ersten m-1 Zeichen von
bestehende Wort. Dann gilt
. Wir nehmen das letztere an, der andere Fall geht genau gleich. Wir betrachten nun
zwei Fälle:
1.
Eines der anderen Wörter von
ist, so vertauschen wir
2.
der Länge m ist das
nicht bereits das zweitletzte Wort
mit dem zweitletzten Wort. Diesen (eventuell neuen) Code nennen wir
Keines der anderen Wörter der Länge m ist
neuen Code
. Falls
. Dann ersetzen wir
durch
. Die Präfixeigenschaft wird dadurch nicht zerstört, denn
und
. Dann ist
ein Code für
einzusehen, müssen wir nur die Präfixeigenschaft nachprüfen. Das Wort
war ja schon Codewort.
mit
. Um dies
kann aber kein Präfix von
sein, denn die Längen dieser Codewörter sind kleiner oder gleich
verschieden von
und nennen den
, denn die Längen sind gleichgeblieben. Wir schreiben
Es gilt offenbar
.
, und
waren
.
größer oder gleich der
Nach Induktionsvoraussetzung ist die mittlere Länge des Codes
mittleren Länge das zugehörigen Huffman-Codes, also
,
69/73
wobei
ein Huffman-Code für (p1,...,pn-2,pn-1+pn) ist. Nach der rekursiven Konstruktion des Huffman-
Codes
aus
ist
. Somit gilt
.
Damit ist
(1) gezeigt.
Beispielcodierung für unseren Vektor
Wir wollen nun einmal exemplarisch für unseren Beispielvektor eine Codierung vornehmen, wobei wir jedoch
keine eigene stochastische Auswertung durchführen, sondern uns auf empirische Tabellen verlassen, die bereits
Codes enthalten, die in der Regel recht günstig sind.
Tabelle 1: Huffman-Codierung für Symbol 1 der AC-Werte.
70/73
Tabelle 2: Codierung für Symbol 2 der AC-Werte
Aus diesen beiden Tabellen können wir nun ablesen, welche Codes den AC-Werten entsprechen, die in unserem
Vektor stehen.
Tabelle 3: Codierungsmuster für die AC-Werte des 8*8 Blocks.
Durch Aneinanderreihen der einzelnen Codes erhalten wir dann einen einzigartigen Binärcode für den Vektor,
sprich: für den ursprünglichen 8*8 Block:
·
·
für den DC-Wert: 00011111
für die AC-Werte: 111100100010110011101101110001 100110011110001010000001001100
111101001101100100011000100100 01111111111111010000000010001010
71/73
Die Autoren
Sebastian Wickenburg, Aeneas Rooch und Johannes Groß sind zur Zeit (im September 2002) zusammen 58
Jahre alt, also nicht mehr die Jüngsten. Insgesamt haben sie zusammen 27 Jahre lang das Gymnasium am Ostring
in Bochum besucht, der Stadt, in der jeder von ihnen mit einer Wahrscheinlichkeit von p=0,67 wohnt.
Am Gymnasium am Ostring, der alten Schule von Herbert Grönemeyer, haben sie in diesem Jahr mit Erfolg das
Abitur errungen - zur Verblüffung aller, die die Abiturklausur im Mathe-LK mitgeschrieben haben, die man
durchaus als "interessant" bezeichnen konnte. Doch trotzdem haben sie der Mathematik nicht abgeschworen,
sondern sich aufgemacht, die Hintergründe der JPEG-Kompression zu ergründen.
Viel Wert wurde bei dieser Arbeit auf die Präsentation gelegt, um allen Lesern mit ihren unterschiedlichen
Vorkenntnissen die einzelnen Schritte plausibel und das Thema insgesamt anschaulich darzustellen, denn gerade
die Mathematik leidet oft unter schlechter Didaktik. Dass auch mal ein bisschen Biologie, Psychologie und
Physik mit im Spiel ist, lässt sich hier und da nicht vermeiden, wenn man der Mathematik im Alltag nachgeht...
Die Autoren danken:
·
·
·
·
Prof. Dr. Peter Eichelsbacher von der Ruhr-Universität Bochum für das große Engagement bei der
Beratung und der Beantwortung der Fragen
Roland Franken von "digit! Online" für die schnelle Hilfe beim Verstehen der gemeinen Digitalkamera
Fabian Jakobs für das freundliche Zur-Verfügung-Stellen seines Huffman-Java-Applets
Prof. Dr. Ehrhard Behrends von der FU Berlin dafür, dass die drei alten Kaliber überhaupt teilnehmen
durften
Bei Fragen, Kritik und Anregungen können Sie uns mailen, wir würden uns über Rückmeldung freuen:
·
·
·
[email protected]
[email protected]
[email protected]
72/73
Quellenverzeichnis
Bei der Erstellung dieser Arbeit haben wir folgende Quellen benutzt:
·
·
Bildverarbeitung interaktiv; Herbert Kopp; B.G. Teubner Stuttgart, 1997
Vorlesungsskript Stochastik von Prof. E. Bolthausen, Zürich
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
http://homepages.uni-tuebingen.de/student/horst.rechner/Ausarbeitung.html
http://www.improve-mtc.de/Veroffentlichungen/Multimedia2/multimedia2.html
http://goethe.ira.uka.de/seminare/rftk/
http://goethe.ira.uka.de/seminare/redundanz/vortrag11/
http://i31www.ira.uka.de/docs/semin94/02_JPEG/
http://www-lehre.informatik.uni-osnabrueck.de/~mm/
http://www.fuji.de
http://www.ti5.tu-harburg.de/Staff/Lamers/stab/
http://www.dbg.rt.bw.schule.de/lehrer/ritters/info/kompr/huffman.htm
http://www.ztt.fh-worms.de/de/sem/ws95_96/kompressionsalgorithmen/node9.html
http://www.informatik.uni-leipzig.de/ifi/lehre/ Heyer2000/ADKapitel10/tsld026.htm
http://www.digit.de/
http://www.ronnz.de/bildkompression/kompression.html
http://www.uni-giessen.de/faq/archiv/jpeg-faq.part1-2/msg00001.html
http://isl.ira.uka.de/info2/schulungsmaterial/animationen/huffman/applet.html
http://www.geocities.com/ally77jp/scanner.html
http://www.realschule-taufkirchen-vils.de/schueler/klassen/10a/Schueler/Treffler/funktionsweise.htm
Wie wir in der Schule gelernt haben, sind Internetquellen mit höchster Vorsicht zu genießen. Das haben wir
getan.
73/73

Druckdatei der Arbeit

Transcrição

Documentos relacionados

Importeure, Bekleidungs- und Zubehör

Sportcamp auf Zypern Agia Napa 2013

Ara Pacis Augustae

Die Aeneis des Vergil – im Unterricht behandelte - bernd

Anlieferung

Technische Daten Lumix DMC-FZ20 Kamera-Typ Digital

Datenblatt: TH-103PF9EK

Konica Revio C2: Technische Daten

Herunterladen - Thomas Electronic Onlineshop

Datenblatt: PT