Informatik am GSG

Grundlage: Das RGB-Farbmodell
Man kann sich diese Farbmischung so vorstellen, als würden je eine Lichtquelle mit rotem, grünem und blauem Licht auf einen Punkt scheinen. Das Licht auf dem Punkt ist dann eine Mischung aus den drei Farben. Die Intensität der jeweiligen Farbe ist umso stärker, je stärker die jeweilige Lichtquelle strahlt.

Überschneiden sich zwei Lichtkreise, so entstehen die Sekundärfarben, Gelb, Magenta und Cyan. In der Mitte überschneiden sich alle drei Lichtkreise, wobei die Mischung Weiß erscheint. Die Farbe Schwarz wird durch die Dunkelheit (kein Licht) im umgebenden Raum dargestellt.
Die Farbanteile (r, g, b) werden dabei in Zahlen von 0 bis 255 codiert. So ergeben sich 256⋅256⋅256=2⁸⋅2⁸⋅2⁸=2²⁴=16777216 verschiedene Farben. Für jeden Farbanteil werden aufgrund der 256=2⁸ Möglichkeiten 8 bit, also ein Byte, Speicher benötigt. Da es drei Farbanteile sind, benötigt ein gespeichertes bit eines Bildes somit 3⋅8=24bit, oder 3 Byte. Beispiele für die binäre Darstellung einiger Farben:

Das Bild „Pfeil“, siehe oben, wird im Bitmap-Format Punkt für Punkt gespeichert. Das bedeutet, je-der Pixel kann mit 0 für weiß und 1 für schwarz einzeln gespeichert werden. Im Bitmap-Format (.bmp) wird jede Farbe mit 8bit gespeichert, durch die Vorabinformation an den Computer, dass 0 weiß und 1 schwarz bedeutet, sparen wir hier bereits Speicherplatz ein. Die zusätzlichen Informationen, z. B. die Maße des Bildes, wer das Bild erstellt hat u. s. w. (die sogenannten Metadaten) werden für unser Verfahren nicht betrachtet. Es werden nur die Einsparmöglichkeiten des Dateikörpers untersucht.
Dateikopf: Zwei Farben, 0 für Weiß, 1 für Schwarz, 17x11 (durch die Information 17x11 weiß der Computer, wann eine Zeile beendet ist.).
Dateikörper: 0000000000000000000000000011100000000000000011100000000000000011100001111111111111100011111111111111100111111111111110000000000000111000000000000011100000000000001110000000000000000000000
Also ist das Bild 11x17 = 187 Bit groß zuzüglich des Speicherplatzes für einen Namen und anderen Zusatzinformationen zur Datei. Bei einem Schwarz-Weiß-Bild mit der Auflösung 1024 x 768 Pixel ist der Dateikörper bei der Bit-map-Codierung bereits 786432 Bit groß. Ist es möglich, die Größe des Dateikörpers zu verkleinern, ohne Bildinformationen zu verlieren? Statt 0000000000000000000000000011100000000000000011100000000000000011100001111111111111100011111111111111100111111111111110000000000000111000000000000011100000000000001110000000000000000000000 kann man auch 26-mal weiß, 3-mal schwarz, 15-mal weiß, 3-mal schwarz, ... schreiben.

1. Vervollständigen Sie die so entstehende Reihe (die Abkürzungen mit 26w, 3s,... genügen).

Das erscheint momentan nicht unbedingt kürzer, aber nun wird die folgende Codierung vereinbart: Ein Codewort besteht aus vier Zeichen. Das erste bit legt die Farbe fest (0 für Weiß und 1 für Schwarz). Die folgenden drei bit geben an, wie oft die Farbe wiederholt wird (000 für einmal, 001 für zweimal und so weiter).
Das ergibt die folgende Codetabelle:

2. Codieren Sie das Bild "Pfeil" der vorherigen Seite mit dieser Tabelle.
3. Dekodieren Sie die folgenden Daten für ein Bild mit 8 Pixel Breite und 11 Pixel Höhe. 0111-0111-0001-1011-0110-1000-0110-1000-0101-1001-0100-1000-0101-1000-0110-1011-0111-0111-0001
4. Die bisher verwendete Form der Lauflängencodierung bestand aus Codeblöcken von je vier bit. Entwickeln Sie eine Codetabelle für eine Gesamtblocklänge von drei bit.
5. Vergleichen Sie den 4-bit-Code mit dem 3-bit-Code. Untersuchen Sie, bei welcher Art von Bild die 4-bit-Codierung von Vorteil ist und bei welcher Art von Bild die 3-bit-Codierung.

Betrachten wir eine Codierung, welche in einem Supermarkt für Artikel genutzt wird. Jeder Artikel erhält eine Ziffernkombination aus acht Ziffern. Die ersten drei Ziffern sind eine Ländernummer, die folgenden vier stehen für die interne Artikelnummer und die letzte Ziffer ist eine sogenannte Prüfziffer. Ein Beispiel: 20954789

Die Prüfziffer berechnet sich folgendermaßen. Zunächst berechnet man eine gewichtete Summe der ersten sieben Ziffern nach der Methode:

Die Prüfziffer ist die Ziffer, welche die Summe zum nächsten Vielfachen von 10 ergänzt. Hier: 81+9=90

1. Implementieren Sie ein Programm in Scratch, welches aus einer eingegebenen Länder- und Artikelnummer eine entsprechende Prüfziffer erstelle und das gesamte Codewort ausgibt.
2. Implementieren Sie ein Programm in Scratch, welches ein eingegebenes Codewort dieser Art auf seine Korrektheit überprüft. Ist die Prüfziffer falsch, soll eine entsprechende Fehlermeldung ausgegeben werden.
3. Analysieren Sie, wie viele Fehler diese Codierung sicher erkennen kann.

In einem Bild sind sechs verschiedene Farbtöne enthalten. Die beiden Farben Rot und Schwarz treten sehr häufig auf, Blau und Gelb mit einer mittleren Häufigkeit, grün und violett selten. Um Speicherplatz bei der Codierung zu sparen, sollen Farben, die häufig vorkommen mit einem kurzen Code dargestellt werden, seltene Farben mit einem längeren Code. Hierzu sollen neben einem Standardcode (Code A) zwei weitere Codierungsvarianten (Code B und Code C) betrachtet werden.

In der folgenden Abbildung ist Code A in einem Codebaum grafisch dargestellt:

1. Erstellen Sie jeweils einen Codebaum für den Code B und den Code C.
2. Analysieren Sie, ob sich die Codefolge 110111101000 unter Verwendung der Codes A, B und C jeweils eindeutig decodieren lässt. Warum ist es wichtig, dass das Decodieren eindeutig sein muss?
3. Vergleichen Sie die Codebäume der drei Codes A, B und C miteinander: Lässt sich an der Struktur des Baums eine grundsätzliche Problematik für das Decodieren erkennen? Was bedeutet dies für die Notwendigkeit, Trennzeichen (Pausen) zwischen den Codes der einzelnen Farbwerte verwenden zu müssen?

Möchte man nun ein Bild auf einem Computer speichern, so wird für jedes einzelne Pixel „notiert“ welche Farbe dieses besitzt. Das geschieht in der Regel durch eine Binärcodierung, also durch eine eindeutige Folge von Nullen und Einsen. Für das nebenstehende Bild wurde die folgende Codefolge festgelegt:

Wenn in einem Bild eine Farbe häufig direkt nacheinander vorkommt, kann man viel Speicher spa-ren: Man gibt einfach an, wie oft eine bestimmte Farbe hintereinander vorkommt. Diese Anzahl nennt man Lauflänge. Dann muss man nicht für jedes Pixel einzeln die Farbe notieren. Hierzu be-nötigt man neben der Codetabelle für die Farben noch eine Codetabelle für die Anzahl.

Notiert man nun zuerst die Anzahl und dann den zugehörigen Farbwert, ergibt sich in Zeichen-schreibweise zunächst die Codefolge 5b6r3g6r5b. Da die Lauflänge 6 nicht in der Tabelle ent-halten ist, muss man diese zusammensetzen. Eine Möglichkeit ist die folgende Codefolge: 5b3r3r3g3r3r5b.Ersetzt man die Zeichen dann noch durch die zugehörigen Binärcodes, erhält man die finale Codefolge: 1100100110011010100110011100.
Hinweis: In der Codetabelle für die Lauflängen kann man beliebige Werte verwenden. Wichtig ist nur, dass man alle möglichen Lauflängen codieren kann. Im vorliegenden Beispiel kann man z. B. die Lauflänge 6 durch 3+3 oder auch durch 5+1 (oder etwas ungeschickt durch 1+1+2+2 oder …) zusammensetzen.

1. Zeichnen Sie zwei 5x5-Bilder mit vier Farben (rot, grün, blau, orange). In einem Bild soll es viele Farbwech-sel geben, beim anderen sollen die Farben jeweils häufig aufeinander folgen.
2. Geben Sie eine passende Codetabelle für die Farben an und notiere eine Standardcodierung für die beiden Bilder.
3. Geben Sie eine Lauflängencodierung für die beiden Bilder an. Erstelle hierzu zunächst eine passende Tabelle für die Lauflängen.
4. Bestimmen Sie für die Bilder jeweils die Codelänge bei der Standardcodierung und bei der Lauflängencodierung. Berechne, um viel Prozent der Code kürzer (oder sogar länger) geworden ist.
5. (Zusatz) Bei der Datenübertragung eines binären Lauflängencodes wird ein einzelnes Bit falsch übertragen. Untersuche, welche Auswirkungen dies auf die Darstellung des Bildes hat. Welche Auswirkungen hat ein solcher Fehler bei einer Standardcodierung?

Bei der Lauflängencodierung wird ein Bildcode bei geschickter Codierung kürzer. Da man keine Informationen über das Bild verliert, spricht man hier von einer verlustfreien Kompression. Bei „richtigen“ Fotos auf dem Handy (jpg-Dateien) werden noch weitere Kompressionsverfahren verwendet, die zwar viel Speicher sparen, aber auch zu Informationsverlust führen. Solche Verfahren nennt man verlustbehaftet.

Betrachtet man die Tabelle für den Morsecode, sieht man, dass Buchstaben wie E und N sehr kurze Codes besitzen und das Q hingegen einen langen Code. Da bestimmte Buchstaben in unserer Sprache häufiger vorkommen als andere, kann man so beim Codieren viel Speicher (und Zeit) sparen. Eine solche Art der Codierung nennt man Entropiecodierung. Das gleiche Prinzip kann man auch bei anderen Anwendungen benutzen, z. B. beim Codieren von Bildern. Man zählt, wie häufig einzelne Farbwerte vorkommen und weist ihnen dann einen passenden Code zu.

Beim Morsen muss man zwischen den einzelnen Buchstaben eine Pause machen, da man die Buchstaben sonst nicht unterscheiden kann. Ohne Pausen könnte die Codefolge ∙ ∙ - ∙ ein F sein oder auch EAE bedeuten.
Stellt man eine Codetabelle „geschickt“ auf, dann kann man auf diese Pausen verzichten. In der obenstehenden Codetabelle findest du einen Code, bei dem keine Pause bzw. kein Leerzeichen ge-macht werden muss, da keine Verwechslungsgefahr besteht. Einen solchen Code nennt man präfixfrei. Neben der Tabelle ist der zugehörige Codebaum angegeben. Alle Codes stehen am Ende ei-nes Pfades. Wenn das der Fall ist, dann ist der Code auf jeden Fall präfixfrei.

1. Zeichnen Sie ein Bild der Größe 10 x 10 Pixel mit neun verschiedenen Farben.
2. Erstellen Sie eine Codetabelle, bei der jeder Farbcode die gleiche Länge besitzt. Geben Sie dann an, wie viele Bits für das gesamte Bild benötigt werden.
3. Erstellen Sie eine Codetabelle, bei der die Farben, die häufig vorkommen, einen kurzen Code bekommen. Farben, die selten vorkommen, erhalten dann einen längeren Code. Achten Sie darauf, dass ihr Code präfixfrei ist. Zeichnen Sie zur Überprüfung auch den zugehörigen Codebaum.
4. Berechnen Sie mit ihrer Codetabelle zu c) wie viele Bits für das Codieren des gesamten Bildes notwendig sind. Vergleichen Sie mit ihrem Ergebnis aus b).
5. (Zusatz) Eine optimale Codierung bzgl. der Häufigkeiten der einzelnen Farben lässt sich systematisch durch das Erstellen eines Huffman-Baums erstellen.
   Betrachten Sie für eine Beschreibung des Verfahrens die beiden Videos:
   Erstellen Sie dann systematisch eine Codierung für die Farbwerte in der obigen Tabelle mithilfe eines Huffman-Baums. Vergleichen Sie mit ihrer Lösung zu c).

Farben werden technisch häufig durch zwei unterschiedliche Farbcodierungen beschrieben:
Subtraktive Farbmischung: Im Bereich der Drucktechnik benutzt man das Prinzip der subtraktiven Farbmischung. (Weißes Papier → Durch das Mehrfache Auftragen von Farben wird es immer dunkler → Das entspricht einer Subtraktion von Licht). Grundfarben sind hier Cyan (C), Magenta (M) und Gelb (Y). Häufig nimmt man reines Schwarz (K) mit hinzu. Dann spricht man von CMYK. Die Farben sind z. B. von Druckerpatronen oder Tonerkartuschen bekannt.
Additive Farbmischung: Bei selbst leuchtenden Medien, wie z. B. Monitoren, Fernsehern oder Displays verwendet man das Prinzip der additiven Farbmischung. (Dunkler Bildschirm → Durch das Mischen von Lichtpunkten (Pixeln), die sich optisch überlagern, wir das Bild immer heller → Das entspricht einer Addition von Licht.) Als Grundfarben verwendet man hier Rot (R), Grün (G) und Blau (B). Man spricht daher auch von einer RGB-Farbdarstellung.
Stellt man die additive (links!) und die subtraktive (rechts!) Farbmischung in einem Farbkreis dar, so muss man beachten, dass sich die Farben völlig unterschiedlich „mischen“. Es wird durch das Mischen die Helligkeit erhöht oder es reduziert sich die Helligkeit:

Das Farbschema RGB entspricht unserem natürlichen Sehen. Das menschliche Auge besitzt für das Farbsehen drei verschiedene Zapfensorten, die auf unterschiedliche Farbbereiche reagieren und zusammen einen Farbeindruck erzeugen. Da diese Werte erst noch durch das Gehirn interpretiert werden, ist das Farbensehen sehr subjektiv.

1. Informieren Sie sich hierzu im folgenden Video, gucken Sie dieses bis zum Ende:

   In der Computertechnik werden Farbwerte der Grundfarben (RGB) häufig in einer 8-Bit-Codierung gespeichert. Das heißt, dass die einzelnen Grundfarben 28=256 mögliche Werte besitzen, von 0 bis 255. Bei 0 ist die Grundfarbe nicht vertreten. Bei 255 ist die Grundfarbe maximal hinzugefügt.
   Das kann man beispielhaft wie folgt interpretieren:

   Grundfarbe		Rot	Grün	Blau
   Sättigung	Prozent	54,5	4,3	98,0
   	Binär	10001011	00001011	11111010
   	Dezimal	139	11	250

   Die Farbe in der Tabelle wird als 100001011 00001011 11111010 im Computer gespeichert. Als Dezimalfarbwerte erhält man Rot: 139, Grün: 11; Blau: 250. Das ist etwas Rot, nahezu kein Grün, viel Blau. Mischt man die Farben, ergibt sich Violett (
   ).
2. Vervollständigen Sie die folgende Tabelle mithilfe des RGB-Farbmischers:
   Rot: 128
   Grün: 128
   Blau: 128

   Rot	Grün	Blau	Farbton

Wir wollen nun versuchen, das Codieren eines Farbbildes mit Scratch zu programmieren. Lade Sie diese Datei herunter und starten Sie diese in Scratch. Dort gibt es bereits ein zu codierendes Bild auf der Bühne vorgegeben, sowie das Grundgerüst des Codierungsprogramms.

1. Mit dem Block "Begrüßung" soll der Scanner eine Begrüßung nach dem Programmstart sagen.
   Der Block "Ergebnis" soll am Schluss Informationen über die Maße des Bildes, die Anzahl der Pixel und auch das codierte Bild sagen.
   Implementieren Sie diese Funktionalität in den Blöcken "Begrüßung" und "Ergebnis".
2. Mit dem Block "gehe1FeldVor" soll der Scanner genau ein Pixel weitergehen. Die Pixel sind im¬mer 20 Schritte auseinander. Mit dem Block "geheInNächsteZeile" soll der Scanner eine Zeile weiter nach unten und zum ganz linken Pixel gehen. Hinweis: Der Scanner startet im Pixel oben links, bei x=-230 und y=170.
   Implementieren Sie diese Funktionalität in den Blöcken "gehe1FeldVor" und "geheInNächsteZeile".
3. Der Block "scanneBild" soll nun das Einlesen der Pixel und den Aufbau des Codes unter der Variablen bildcode übernehmen.

   Standardvariante

   Schwierigere Variante

   Ziel ist es, für jede Farbe einen entsprechenden Buchstaben als Code zu nutzen und damit den Code bildcode aufbauen. Für die Farbe Rot kann man z. B. den Code "r" nehmen. Der Scanner soll zeilenweise arbeiten und während des Scannens ein anderes Kostüm anziehen. Implementieren Sie diese Anforderungen.

   Ziel ist es, für jede Farbe einen entsprechenden Buchstaben als Code zu nutzen und damit den Code bildcode aufbauen. Für die Farbe Rot kann man z. B. den Code "r" nehmen. Lauflängen sollen ebenfalls berücksichtigt werden. Also wird für z. B. 10 aufeinanderfolgende rote Pixel das Codewort 10r gespeichert. Der Scanner soll zeilenweise arbeiten und während des Scannens ein anderes Kostüm anziehen. Implementieren Sie diese Anforderungen.