FH Graubünden PH Graubünden

Pixelbilder komprimieren

Algorithmisches Denken in der Primarschule

Zusammenfassung

Beim analogen wie auch digitalen Versenden von Daten haben wir ein Interesse daran, die Daten möglichst kompakt darzustellen, um möglichst wenige Ressourcen zu verwenden. In dieser Unterrichtseinheit stellen wir die Frage, wie Bilder in einer geeigneten Darstellungsform von einem Sender zu einem Empfänger geschickt werden können und wie dabei die zu übermittelnde Information möglichst kurz dargestellt werden kann.

Zur Darstellung verwenden wir sogenannte Pixelbilder (ein Raster von Pixeln), die über eine klar definierte Codierung zunächst beim Sender komprimiert und anschliessend beim Empfänger wieder dekomprimiert werden können. Die Funktionsweise sowie die Folgen der verwendeten Codierung werden iterativ erarbeitet und analysiert.

Beispielsequenz

Laura zeichnet gerne Bilder. Dazu verwendet sie ein Raster von Gitterpunkten, die wir Pixel nennen. Pixel sind kleine Gitterpunkte, die jeweils entweder komplett schwarz oder komplett weiss eingefärbt sind. Das Bild in Abbildung 1 besteht aus 10 mal 10 Pixeln, von welchen gewisse weiss und die anderen schwarz eingefärbt sind.

.Notenschluessel.png.
Abbildung 1. Eine Note aus Pixeln
Laura möchte ihrer Freundin Rahel am Telefon ihre Pixelbilder beschreiben und liest dazu zeilenweise die Farben aller Pixel vor. Sie beginnt mit dem Pixel in der Ecke oben links und endet mit dem Pixel in der Ecke unten rechts. Die Pixel werden dargestellt durch die Buchstaben S (für schwarze Pixel) und W (für weisse Pixel). Das ursprüngliche Pixelbild wird codiert zu einer Sequenz von S und W, die als Nachricht anschliessend an den Empfänger übermittelt wird. Der Empfänger decodiert die empfangene Nachricht, um wieder das ursprüngliche Bild zu sehen. Schematisch ist dies in Abbildung 2 dargestellt.
.start.png.
Abbildung 2. Übertragung eines Pixelbildes

Aufgabe 1

Codieren Sie das folgende Pixelbild. .A1.png.

Aufgabe 2

Decodieren Sie die folgende Nachricht und finden Sie das entsprechende Pixelbild. .B1.png.

Aufgabe 3

Welches Pixelbild sieht der Empfänger beim Decodieren der folgenden Nachricht? Korrigieren Sie die Nachricht so, dass das ursprüngliche Pixelbild korrekt decodiert werden kann. .B2.png.

Aufgabe 4

Palindrome sind Wörter, die vorwärts und rückwärts gelesen dasselbe Wort darstellen (zum Beispiel ANNA oder RADAR). Gibt es Pixelbilder, deren Codierung vorwärts und rückwärts gelesen dasselbe Pixelbild ergeben? Suchen Sie ein Beispiel. .B3.png.

Aufgabe 5

Die folgenden drei Bilder sind punkt- oder achsensymmetrisch. Welche Aussage(n) sind korrekt? .B4.png. Bilder werden zu Palindromen codiert, wenn sie symmetrisch sind bezüglich ...

  1. ihrer vertikalen Mittelachse,
  2. ihrer horizontalen Mittelachse,
  3. ihrem Mittelpunkt.

Kompression

Beim Codieren des untenstehenden Bildes fällt Rahel auf, dass in der codierten Nachricht oft dieselben Pixel mehrmals nacheinander vorkommen. Das Pixelbild unten wird beispielsweise zu einer Nachricht codiert, die mit 13 weissen und 7 schwarzen Pixeln beginnt. Rahel überlegt sich, wie sie die Codierung kürzer darstellen (also komprimieren) könnte. .Notenschluessel2.png.

Aufgabe 6

Überlegen Sie sich eine Vorgehensweise, wie Sie Nachrichten systematisch kürzen können. Sie können für die Darstellung der komprimierten Nachricht auch Zahlen zur Hilfe nehmen. Testen Sie Ihre Vorgehensweise an den folgenden Beispielen:

Aufgabe 7

Komprimieren Sie die Codierung des folgenden Pixelbildes. Wie viele Zeichen konnten Sie im Vergleich zur unkomprimierten Codierung einsparen? .A4.png.

Aufgabe 8

Das Wiederherstellen eines komprimierten Bildes nennen wir Dekomprimieren. Dekomprimieren Sie die folgende Codierung und stellen Sie das originale Pixelbild wieder her. .A6a.png.

Aufgabe 9

Für gewisse Pixelbilder bietet die Komprimierung keine Vorteile. Es ist sogar möglich, dass die Komprimierung einen nachteiligen Effekt hat und sich die Länge der Darstellung insgesamt verlängert. Finden Sie ein Beispiel, wo dies der Fall ist und erklären Sie, woran es liegt, dass dieses Bild so schlecht komprimiert wird. .A5.png.

Lösungen zu den Aufgaben

Aufgabe 1

.L1.png.

Aufgabe 2

.B1L.png.

Aufgabe 3

Die codierte Nachricht ergibt nicht das ursprüngliche Bild. Zwei Pixelwerte wurden falsch codiert: .B2L.png.

Aufgabe 4

Eine Nachricht, die vorwärts und rückwärts gelesen dasselbe Pixelbild ergibt, ist unten dargestellt. .B3L.png.

Aufgabe 5

Bilder werden zu Palindromen (Nachrichten, die vorwärts und rückwärts gelesen dasselbe Bild beschreiben) codiert, wenn sie symmetrisch bezüglich ihrem Mittelpunkt sind.

Aufgabe 6

Wir zählen jeweils, wie oft dieselbe Pixelfarbe am Stück verwendet wird und notieren anschliessend die Zahl gefolgt von der jeweiligen Farbe. Lange Sequenzen gleichbleibender Pixelfarben können auf diese Weise massiv gekürzt werden wie wir in der Tabelle unten erkennen.

Ursprüngliche Nachricht Komprimierte Nachricht
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 30S
WWWWWWWWWWWWWSSSSSSS 13W7S
WWWSSSSWWSSSSSWWW 3W4S2W5S3W
WWWWWSWWWWWS 5W1S5W1S

Aufgabe 7

Die komprimierte Codierung zählt 53 Zeichen im Vergleich zu 100 in der unkomprimierten Codierung. Durch die Komprimierung wurden somit 47 Zeichen eingespart. .A4L.png.

Aufgabe 8

.L6a.png.

Aufgabe 9

.L5.png. Die Komprimierungsmethode nützt nur etwas, wenn mehrere Pixel mit der gleichen Farbe aufeinanderfolgen, da dann die Anzahl Wiederholungen der Farbe gezählt wird und wir die Anzahl vor der jeweilige Farbcodierung notieren. In diesem Beispiel wechseln sich schwarz und weiss ständig ab, so dass unsere Methode anstatt zu komprimieren, die Gesamtlänge der Nachricht verdoppelt.

Didaktischer Kommentar

In der Informatik spielt die Komprimierung von Bildern und weiteren Datenformaten wie zum Beispiel Videos und Liedern eine grosse Rolle, da kleinere Dateien schneller über das Internet übermittelt werden können als grosse. Gerade beim Streamen von Filmen und Serien ist die Komprimierung sehr wichtig, da dabei riesige Datenmengen verschickt werden. Wir sind deshalb daran interessiert, alle Dateien zuerst so gut wie möglich zu komprimieren, bevor wir sie über das Internet verschicken.

Die Unterrichtseinheit enthält die folgenden Aspekte des algorithmischen Denkens.

Weiterführende Hinweise

Diese Unterrichtseinheit beschäftigt sich mit der verlustfreien Komprimierung, das heisst, dass das dekomprimierte Bild identisch mit dem Originalbild ist und keine Details verloren gehen. Es existiert auch eine verlustbehaftete Komprimierung, welche die Bilder noch stärker komprimieren kann, allerdings auf Kosten von Bilddetails. Nach der Dekomprimierung sind nicht mehr alle Details enthalten.

Für die Codierung der verschiedenen Pixelfarben verwendet diese Unterrichtseinheit bewusst Buchstaben, so dass Zahlen dazu verwendet werden können, um bei der Komprimierung anzugeben, wie häufig eine Pixelfarbe nacheinander vorkommt. Ein Computer speichert sowohl das originale als auch das komprimierte Bild ausschliesslich mit binären Ziffern «0» und «1» ab. Damit die Speicherung gelingt, müssen weitere Regeln festgelegt werden, so dass die «Anzahl der Wiederholungen der nachfolgenden Pixelfarbe» beim Dekomprimieren immer klar von der «Pixelfarbe» getrennt werden kann. Wir gehen in dieser Unterrichtseinheit jedoch nicht auf diese Ebene herunter, sondern bleiben auf der Abstraktion mit den Buchstaben für die Pixelfarbe und der Zahl für die Anzahl der Wiederholungen. Von dieser Unterrichtseinheit ausgehend, kann die Codierung der Pixel auf Hardwareebene thematisiert werden.

Zurück PDF Übungen als PDF