RLE-Bildkompression in Python: Tutorial für COP3504C

Einführung in die Run-Length Encoding (RLE) für Bilder

Stell dir vor, du arbeitest an einem Projekt, bei dem du Pixelgrafiken effizient speichern musst – genau wie beim Erstellen von Pixel-Art für ein Retro-Spiel oder beim Optimieren von Speicherplatz für eine App. In der Programmierung kommt hier die Run-Length Encoding (RLE) ins Spiel. Diese verlustfreie Komprimierung wird häufig in der Bildverarbeitung und Datenkompression eingesetzt, um sich wiederholende Daten zu reduzieren. In diesem Tutorial lernst du, wie du RLE für Bilddaten implementierst – basierend auf dem Projekt COP3504C P1: RLE with Images. Wir werden Schritt für Schritt die wichtigsten Funktionen in Python umsetzen, darunter RLE codieren, decodieren und die Konvertierung zwischen Hex-Strings und Byte-Daten.

Was ist Run-Length Encoding?

RLE ist eine einfache, aber effektive Methode, um Daten zu komprimieren, indem aufeinanderfolgende gleiche Werte als Paar aus Länge und Wert gespeichert werden. Stell dir vor, du hast eine Reihe von Pixeln: 0 0 0 2 2 2 2 2. Statt alle acht Pixel einzeln zu speichern, notierst du: 3-mal 0, dann 5-mal 2. In RLE-Schreibweise: (3,0), (5,2). Das spart Platz – besonders bei Bildern mit großen einfarbigen Flächen, wie sie in Pixel-Art-Spielen oder Animationen vorkommen.

In unserem Projekt arbeiten wir mit Bildern, die als Byte-Arrays gespeichert sind. Die ersten beiden Bytes geben Breite und Höhe an. Jeder Pixelwert liegt zwischen 0 und 15 (16 Farben). Wichtig: Kein Run darf länger als 15 Pixel sein – längere Runs werden aufgeteilt.

Die wichtigsten Funktionen im Überblick

Das Projekt erfordert die Implementierung mehrerer Funktionen. Wir gehen die wichtigsten durch:

1. count_runs(flat_data) → int

Diese Funktion zählt, wie viele Runs (aufeinanderfolgende gleiche Werte) in den Rohdaten vorkommen. Beispiel: count_runs([15,15,15,4,4,4,4,4,4]) ergibt 2, da es zwei Runs gibt: drei 15er und sechs 4er.

2. to_hex_string(data) → str

Wandelt eine Liste von Bytes in einen Hex-String um (ohne Trennzeichen). Beispiel: to_hex_string([3,15,6,4]) ergibt "3f64".

3. encode_rle(flat_data) → bytes

Komprimiert die Rohdaten in RLE-Format. Beispiel: encode_rle([15,15,15,4,4,4,4,4,4]) liefert b'\x03\x0f\x06\x04' (entspricht [3,15,6,4]).

4. get_decoded_length(rle_data) → int

Berechnet die Länge der dekomprimierten Daten aus den RLE-Daten. Beispiel: get_decoded_length([3,15,6,4]) ergibt 9 (3+6).

5. decode_rle(rle_data) → bytes

Dekomprimiert RLE-Daten zurück in die Rohdaten. Beispiel: decode_rle([3,15,6,4]) liefert b'\x0f\x0f\x0f\x04\x04\x04\x04\x04\x04'.

6. string_to_data(data_string) → bytes

Wandelt einen Hex-String in Byte-Daten um. Beispiel: string_to_data("3f64") ergibt b'\x03\x0f\x06\x04'.

7. to_rle_string(rleData) → str

Erzeugt eine lesbare RLE-Darstellung mit Dezimallängen und Hex-Werten, getrennt durch Doppelpunkte. Beispiel: to_rle_string([10,15,6,4]) ergibt "10f:64".

Schritt-für-Schritt-Implementierung

Wir setzen nun die Funktionen in Python um. Dabei gehen wir systematisch vor.

1. count_runs

def count_runs(flat_data):
    if not flat_data:
        return 0
    runs = 1
    current = flat_data[0]
    count = 1
    for val in flat_data[1:]:
        if val == current and count < 15:
            count += 1
        else:
            runs += 1
            current = val
            count = 1
    return runs

Erklärung: Wir durchlaufen die Daten und zählen, wie oft sich der Wert ändert. Da Runs maximal 15 lang sein dürfen, zählen wir bei Überschreitung einen neuen Run.

2. to_hex_string

def to_hex_string(data):
    return ''.join(f'{x:01x}' for x in data)

Hier nutzen wir die Formatierung :01x, um jedes Byte als einstellige Hex-Zahl (0-15) darzustellen.

3. encode_rle

def encode_rle(flat_data):
    if not flat_data:
        return b''
    result = []
    current = flat_data[0]
    count = 1
    for val in flat_data[1:]:
        if val == current and count < 15:
            count += 1
        else:
            result.append(count)
            result.append(current)
            current = val
            count = 1
    result.append(count)
    result.append(current)
    return bytes(result)

Die Funktion erzeugt eine Liste von Zahlen, die abwechselnd Länge und Wert enthalten. Am Ende wird sie in Bytes umgewandelt.

4. get_decoded_length

def get_decoded_length(rle_data):
    return sum(rle_data[::2])  # Summiert die Längen an geraden Indizes

Die Längen stehen an den Positionen 0, 2, 4, ... – wir summieren sie auf.

5. decode_rle

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

Wir lesen Paare (Länge, Wert) und fügen den Wert entsprechend oft hinzu.

6. string_to_data

def string_to_data(data_string):
    result = []
    for i in range(0, len(data_string), 2):
        hex_pair = data_string[i:i+2]
        result.append(int(hex_pair, 16))
    return bytes(result)

Hier wird der Hex-String in Zweiergruppen zerlegt und in Integer umgewandelt.

7. to_rle_string

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}{value:01x}')
    return ':'.join(parts)

Die Länge wird als Dezimalzahl, der Wert als Hex-Zahl (ohne führende Null) dargestellt.

Praxisbeispiel: Pixel-Art eines Alligators

Stell dir vor, du hast die Rohdaten eines Pixel-Alligators: [0,0,2,2,2,0,0,0,0,0,0,2,2,0]. Das sind 14 Pixel. Mit encode_rle wird daraus: [2,0,3,2,6,0,2,2,1,0]. Das sind nur 10 Bytes – eine Ersparnis von 4 Bytes. In der Praxis kann die Komprimierung bei großen Bildern mit vielen gleichen Farben noch deutlich höher sein.

Integration in das Menü

Das Programm soll ein Menü bieten, über das der Benutzer Daten laden, anzeigen und konvertieren kann. Typische Optionen sind:

Bild aus Datei laden
Testbild laden
RLE-String einlesen (dezimal mit Trennzeichen)
RLE-Hex-String einlesen
Flat-Hex-String einlesen
Bild anzeigen
RLE-String anzeigen
RLE-Hex-Daten anzeigen
Flat-Hex-Daten anzeigen

Die Implementierung des Menüs erfolgt in main() mit einer Schleife und Benutzereingaben. Die Funktionen aus der Python-Programmierung werden dabei immer wieder aufgerufen.

Tipps für die Fehlersuche

Teste jede Funktion einzeln mit den gegebenen Beispielen.
Achte auf die maximale Run-Länge von 15. Deine encode_rle-Funktion muss Runs automatisch aufteilen.
Nutze die to_hex_string-Funktion zum Debuggen, um Zwischenergebnisse als Hex-String auszugeben.
Verwende bytes und nicht list für die Rückgabewerte, wo gefordert.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie du RLE für Bilddaten in Python implementierst. Die sieben Kernfunktionen decken die wichtigsten Aspekte der Datenkompression ab: Codierung, Decodierung, Hex-Konvertierung und Anzeige. Mit diesem Wissen kannst du nicht nur das Projekt COP3504C P1 lösen, sondern auch grundlegende Konzepte der Bildverarbeitung und Algorithmen verstehen, die in vielen Data Science-Anwendungen nützlich sind. Viel Erfolg beim Programmieren!