Run-Length Encoding in Python: Bildkompression einfach erklärt

Einführung in Run-Length Encoding (RLE) mit Python

In der heutigen digitalen Welt, in der Bilder und Videos rasant wachsen, ist effiziente Datenkompression unverzichtbar. Run-Length Encoding (RLE) ist eine einfache, aber mächtige Methode der verlustfreien Kompression, die besonders bei Bildern mit großen einfarbigen Flächen, wie Pixel-Art, gut funktioniert. Dieses Tutorial führt dich durch die Kernkonzepte von RLE und zeigt dir, wie du die Methoden für die Hausaufgaben Cop3502c HW 3 und 4 in Python implementierst. Wir nutzen aktuelle Trends aus der Pixel-Art-Szene und Retro-Gaming, um die Konzepte lebendig zu machen.

Was ist Run-Length Encoding?

Stell dir vor, du hast eine Liste von Pixelfarben: [0, 0, 0, 2, 2, 2, 2, 0, 0]. Statt jeden Wert einzeln zu speichern, notiert RLE die Länge der Wiederholung und den Wert. Aus [0, 0, 0] wird [3, 0], aus [2, 2, 2, 2] wird [4, 2] und so weiter. Die komprimierte Liste lautet [3, 0, 4, 2, 2, 0]. Das spart Speicherplatz und ist besonders nützlich für Pixel-Art in Spielen oder bei der Übertragung von Bildern über langsame Netzwerke.

Warum RLE heute noch relevant ist

Obwohl moderne Formate wie JPEG und PNG komplexere Algorithmen verwenden, wird RLE immer noch in vielen Bereichen eingesetzt: von einfachen Bildformaten (BMP, PCX) über Faxe bis hin zur Datenkompression in eingebetteten Systemen. Sogar in der KI-gestützten Bildverarbeitung kann RLE als Vorverarbeitungsschritt dienen, um wiederholte Muster zu erkennen. Auch in der Finanzwelt werden ähnliche Techniken genutzt, um große Datenmengen effizient zu speichern.

Die Aufgabenstellung von Cop3502c HW 3 und 4

In dieser Aufgabe implementierst du mehrere Funktionen, die RLE auf Bilddaten anwenden. Die Bilder sind als Liste von Zahlen (0-15) gespeichert, wobei die ersten beiden Zahlen Breite und Höhe angeben. Du wirst sowohl die Kompression (Encode) als auch die Dekompression (Decode) sowie die Konvertierung zwischen verschiedenen Darstellungsformen (Hexadezimal, RLE-String) programmieren. Das Ziel ist es, ein Menü-gesteuertes Programm zu schreiben, das Bilder lädt, anzeigt und komprimiert.

Die wichtigsten Methoden im Überblick

to_hex_string(data): Wandelt eine Liste von Zahlen in einen Hexadezimal-String um. Beispiel: [3, 15, 6, 4] wird zu "3f64".
count_runs(flat_data): Zählt die Anzahl der Läufe (Runs) in den Rohdaten. Dies ist die halbe Länge der RLE-codierten Liste.
encode_rle(flat_data): Codiert Rohdaten in RLE. Aus [15,15,15,4,4,4,4,4,4] wird [3,15,6,4].
get_decoded_length(rle_data): Gibt die Länge der dekomprimierten Daten zurück.
decode_rle(rle_data): Dekodiert RLE-Daten zurück in die ursprüngliche flache Liste.
string_to_data(data_string): Wandelt einen Hex-String in eine Liste um (Umkehrung von to_hex_string).
to_rle_string(rle_data): Erzeugt einen lesbaren String mit Dezimalzahlen und Hex-Werten, getrennt durch Doppelpunkte. Beispiel: [15,15,6,4] -> "15f:64".
string_to_rle(rle_string): Wandelt einen solchen String zurück in eine RLE-Liste.

Schritt-für-Schritt-Implementierung

1. to_hex_string und string_to_data

Diese Funktionen sind die Brücke zwischen der internen Listenrepräsentation und der hexadezimalen Darstellung. In Python kannst du mit format(x, 'x') eine Zahl in Hex umwandeln. Achte darauf, dass die Hex-Ziffern klein geschrieben werden. Beispiel:

def to_hex_string(data):
    return ''.join(format(x, 'x') for x in data)

Für die Umkehrung liest du jeweils zwei Zeichen aus dem String und wandelst sie mit int(hex_char, 16) um.

2. count_runs und encode_rle

Um die Läufe zu zählen, durchläufst du die Liste und zählst, wie oft sich der Wert ändert. Ein Lauf endet, wenn der nächste Wert anders ist oder die maximale Lauflänge (hier 15) erreicht wird – aber in dieser Aufgabe gibt es keine Längenbeschränkung, da die Bilddaten klein sind. Für encode_rle erstellst du eine neue Liste, indem du für jeden Lauf die Länge und den Wert anhängst.

def encode_rle(flat_data):
    rle = []
    count = 1
    for i in range(1, len(flat_data)):
        if flat_data[i] == flat_data[i-1]:
            count += 1
        else:
            rle.extend([count, flat_data[i-1]])
            count = 1
    rle.extend([count, flat_data[-1]])
    return rle

3. decode_rle und get_decoded_length

Die Dekodierung ist einfach: Für jedes Paar (Länge, Wert) fügst du den Wert so oft zur Ergebnisliste hinzu, wie die Länge angibt. Die Funktion get_decoded_length summiert einfach alle Längen (jedes zweite Element ab Index 0).

def decode_rle(rle_data):
    decoded = []
    for i in range(0, len(rle_data), 2):
        decoded.extend([rle_data[i+1]] * rle_data[i])
    return decoded

4. to_rle_string und string_to_rle

Diese Funktionen erzeugen bzw. parsen das Format "LängeWert:LängeWert:...". Achte darauf, dass die Länge in Dezimal und der Wert in Hex (klein) angegeben wird. Beispiel: "15f:64" bedeutet 15 mal den Wert 15 (f), dann 6 mal den Wert 4. Verwende split(':') und int(part[:-1]) für die Länge, int(part[-1], 16) für den Wert.

Integration in ein Menü-gesteuertes Programm

Dein Hauptprogramm sollte ein Menü anzeigen, das dem Benutzer erlaubt, Daten zu laden (Datei, Testbild, RLE-String, RLE-Hex, Flat-Hex) und anzuzeigen (Bild, RLE-String, RLE-Hex, Flat-Hex). Die Display-Funktion nutzt die vorgegebene ConsoleGfx.display_image(). Ein Beispiel für den Menüablauf findest du in der Aufgabenbeschreibung.

Häufige Fehler und Tipps

Hex-Ziffern klein schreiben: Die Aufgabenstellung erwartet durchgängig Kleinbuchstaben (z.B. "3f64", nicht "3F64").
Keine führenden Nullen bei Längen: In to_rle_string wird die Länge als Dezimalzahl ohne führende Nullen ausgegeben.
Datenstruktur: Die Bilddaten enthalten Breite und Höhe am Anfang. Achte darauf, diese bei der Dekodierung zu berücksichtigen.
Testen mit den Beispieldaten: Verwende die angegebenen Beispiele (Chubby Smiley, Gator), um deine Implementierung zu überprüfen.

Ausblick: RLE in der Praxis

RLE ist nicht nur eine akademische Übung. In der Spieleentwicklung wird es genutzt, um Pixel-Art-Sprites zu komprimieren. Auch in medizinischen Bildgebungsverfahren wie CT-Scans, wo viele schwarze Pixel vorkommen, kann RLE die Dateigröße reduzieren. Sogar in KI-Modellen zur Bilderkennung wird RLE manchmal als Vorverarbeitung eingesetzt, um die Effizienz zu steigern. Mit diesem Wissen bist du bestens gerüstet, um die Hausaufgabe zu meistern und ein tieferes Verständnis für Datenkompression zu entwickeln.

Fazit

Die Implementierung von RLE in Python ist eine ausgezeichnete Übung, um mit Schleifen, Listen und Typumwandlungen zu arbeiten. Indem du die acht Methoden nacheinander umsetzt, baust du ein solides Fundament für komplexere Kompressionsalgorithmen auf. Viel Erfolg bei deiner Abgabe!