Run-Length Encoding in Python: Bildkomprimierung einfach erklärt (COP3502C HW 3 & 4)

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

In diesem Tutorial lernst du, wie du mit Run-Length Encoding (RLE) Bilddaten in Python effizient komprimieren und dekomprimieren kannst. RLE ist ein verlustfreies Komprimierungsverfahren, das besonders bei Bildern mit vielen sich wiederholenden Pixelfarben – wie Pixel-Art in Retro-Spielen – hervorragende Ergebnisse erzielt. Statt jeden Pixel einzeln zu speichern, wird die Farbe einmal notiert, gefolgt von der Anzahl der Wiederholungen. Dieses Verfahren wird in vielen Bildkomprimierung-Anwendungen eingesetzt, von einfachen Grafiken bis hin zu bestimmten medizinischen Bildformaten.

Die Aufgaben COP3502C HW 3 und 4 verlangen die Implementierung von acht Methoden zur RLE-Verarbeitung. Wir gehen jede Methode Schritt für Schritt durch und zeigen dir, wie du sie in Python umsetzt. Als Beispiel dient ein pixeliges Gator-Bild, das in der Aufgabenstellung erwähnt wird – ähnlich wie bei einem Retro-Game-Sprite.

Grundlagen der Run-Length Encoding

Stell dir vor, du hast eine Reihe von Pixeldaten: [0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 2, 0]. Die Zahl 0 steht für Schwarz, 2 für Grün. Unkomprimiert belegt diese Liste 14 Einträge. Mit RLE gruppierst du aufeinanderfolgende gleiche Werte: [2, 0, 3, 2, 6, 0, 2, 2, 1, 0] – das sind nur 10 Einträge. Das Prinzip: Länge, Wert, Länge, Wert, ....

In der Praxis werden Bilder oft als flache Liste gespeichert, bei der die ersten beiden Zahlen die Breite und Höhe des Bildes angeben. Die Pixelwerte liegen zwischen 0 und 15 (hexadezimal 0–F). Die RLE-Kodierung kann die Datenmenge deutlich reduzieren, besonders bei Bildern mit großen einfarbigen Flächen.

Methoden im Überblick

Dein Programm muss folgende Funktionen enthalten:

to_hex_string(data) – wandelt eine Liste in einen Hex-String um
count_runs(flat_data) – zählt die Anzahl der Läufe in den Rohdaten
encode_rle(flat_data) – kodiert Rohdaten in RLE
get_decoded_length(rle_data) – berechnet die Länge der dekomprimierten Daten
decode_rle(rle_data) – dekodiert RLE zurück zu Rohdaten
string_to_data(data_string) – wandelt Hex-String in Liste um
to_rle_string(rle_data) – formatiert RLE-Daten als lesbaren String
string_to_rle(rle_string) – liest RLE-String ein und erzeugt Liste

1. to_hex_string(data) – Von der Liste zum Hex-String

Diese Methode konvertiert eine Liste von Zahlen (0–15) in einen fortlaufenden Hexadezimal-String. Jede Zahl wird durch ein einzelnes Hex-Zeichen dargestellt. Beispiel: [3, 15, 6, 4] wird zu "3f64".

def to_hex_string(data):
    return ''.join(hex(val)[2:] for val in data)

Die Funktion hex() liefert einen String wie "0xf"; wir extrahieren die letzten Zeichen. So können wir später die Daten kompakt anzeigen.

2. count_runs(flat_data) – Läufe zählen

Zähle, wie oft sich der Wert in der Liste ändert. Jede Änderung beginnt einen neuen Lauf. Beispiel: [15,15,15,4,4,4,4,4,4] hat zwei Läufe: drei 15er und sechs 4er.

def count_runs(flat_data):
    if not flat_data:
        return 0
    runs = 1
    for i in range(1, len(flat_data)):
        if flat_data[i] != flat_data[i-1]:
            runs += 1
    return runs

3. encode_rle(flat_data) – Rohdaten in RLE kodieren

Erzeuge eine Liste, die abwechselnd Länge und Wert jedes Laufs enthält. Aus [15,15,15,4,4,4,4,4,4] wird [3,15,6,4].

def encode_rle(flat_data):
    if not flat_data:
        return []
    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

Beachte: Die Länge wird als Dezimalzahl gespeichert, der Wert als Zahl 0–15.

4. get_decoded_length(rle_data) – Dekomprimierte Länge berechnen

Diese Funktion ist das Gegenstück zu count_runs. Sie summiert alle Längenangaben (jedes gerade Element) und gibt die Gesamtzahl der Pixel zurück. Beispiel: [3,15,6,4] ergibt 3+6=9.

def get_decoded_length(rle_data):
    return sum(rle_data[i] for i in range(0, len(rle_data), 2))

5. decode_rle(rle_data) – RLE in Rohdaten zurückverwandeln

Die Umkehrung von encode_rle. Aus [3,15,6,4] wird wieder [15,15,15,4,4,4,4,4,4].

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

Diese Methode ist essenziell, um komprimierte Bilddaten wieder anzuzeigen.

6. string_to_data(data_string) – Hex-String in Liste umwandeln

Ein Hex-String wie "3f64" wird in eine Liste [3,15,6,4] umgewandelt. Jedes Zeichen wird als einzelne Hex-Ziffer interpretiert.

def string_to_data(data_string):
    return [int(ch, 16) for ch in data_string]

Mit int(ch, 16) konvertierst du ein Zeichen wie 'f' in den Wert 15.

7. to_rle_string(rle_data) – RLE-Daten als lesbaren String formatieren

Diese Methode erzeugt eine menschenlesbare Darstellung: Jeder Lauf wird als LängeWert notiert, getrennt durch Doppelpunkte. Die Länge ist dezimal, der Wert hexadezimal. Beispiel: [15,15,6,4] wird zu "15f:64".

def to_rle_string(rle_data):
    parts = []
    for i in range(0, len(rle_data), 2):
        length = rle_data[i]
        value = rle_data[i+1]
        parts.append(f"{length}{hex(value)[2:]}")
    return ':'.join(parts)

8. string_to_rle(rle_string) – RLE-String einlesen

Die Umkehrung von to_rle_string. Aus "15f:64" wird [15,15,6,4].

def string_to_rle(rle_string):
    rle = []
    for token in rle_string.split(':'):
        # Das letzte Zeichen ist der hexadezimale Wert, der Rest die Länge
        length = int(token[:-1])
        value = int(token[-1], 16)
        rle.extend([length, value])
    return rle

Integration in ein Menü-System

Dein Hauptprogramm sollte ein Menü anbieten, über das der Benutzer Daten laden, kodieren, dekodieren und anzeigen kann. Die Aufgabenstellung gibt konkrete Optionen vor: Laden einer Datei, Testbild, RLE-String, RLE-Hex-String oder flache Hex-Daten. Die Anzeigemöglichkeiten umfassen das Bild selbst, die RLE-String-Darstellung, die RLE-Hex-Darstellung und die flachen Hex-Daten.

Ein typischer Ablauf: Der Benutzer lädt ein Bild (z.B. testfiles/uga.gfx), wählt dann Option 7, um die RLE-Darstellung zu sehen, oder Option 9 für die flachen Hex-Daten. Die Methoden arbeiten nahtlos zusammen.

Praxistipp: Fehlerbehandlung und Testen

Achte darauf, dass deine Methoden auch mit leeren Listen oder ungültigen Eingaben umgehen können. Teste jede Funktion einzeln mit den Beispielen aus der Aufgabenstellung. Verwende die ConsoleGfx-Klasse, um Bilder farbig anzuzeigen (dazu musst du das CS1-Theme installieren).

Ein häufiger Fehler ist die Verwechslung von Dezimal- und Hexadezimaldarstellung. Die Längenangaben sind immer dezimal, die Pixelwerte hexadezimal (0–15). Achte bei to_rle_string darauf, dass die Länge maximal 2-stellig sein kann (da die maximale Lauflänge in dieser Implementierung 99 beträgt).

Zusammenfassung

Mit diesen acht Methoden hast du ein vollständiges RLE-System in Python implementiert. Du kannst nun Bilddaten komprimieren und dekomprimieren, was in vielen Bereichen der Bildverarbeitung und Datenkompression nützlich ist. Dieses Wissen ist auch auf andere Datenformate übertragbar, bei denen wiederholte Muster auftreten – etwa bei der Speicherung von Leveldaten in Spielen oder bei der Übertragung von Sensordaten.

Viel Erfolg bei deiner Abgabe! Denke daran: Die Ausgabe deines Programms muss exakt mit den Vorgaben übereinstimmen, sonst gibt es Punktabzug.