Bildkompression mit Run-Length Encoding: Ein praxisnahes Tutorial für COP3504C

Einführung in Run-Length Encoding (RLE)

Run-Length Encoding (RLE) ist ein einfaches, aber effektives verlustfreies Kompressionsverfahren, das besonders bei Bildern mit vielen sich wiederholenden Pixeln (z. B. Pixel-Art in Spielen) eingesetzt wird. Statt jeden Pixel einzeln zu speichern, wird die Farbe einmal notiert, gefolgt von der Anzahl der Wiederholungen. Dieses Verfahren spart Speicherplatz und ist in vielen Bereichen der Bildverarbeitung, aber auch in der Finanzanalyse oder bei der Verarbeitung von Sensordaten nützlich.

Wie funktioniert RLE?

Ein einfaches Beispiel: Eine Reihe von Pixeln [0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 2, 2] wird zu [2, 0, 3, 2, 6, 0, 2, 2] – also Paare aus (Anzahl, Wert). Die Länge der ursprünglichen Daten beträgt 13, die kodierte Länge nur 8 Byte (4 Paare).

Im Projekt 1 von COP3504C implementierst du mehrere Funktionen, um RLE-Daten zu kodieren und zu dekodieren. Das Verständnis dieser Funktionen ist entscheidend für den Erfolg des Projekts.

Die wichtigsten Funktionen im Überblick

• count_runs(flatData): Zählt die Anzahl der „Runs“ (aufeinanderfolgende gleiche Werte) in den flachen Daten.
• to_hex_string(data): Wandelt eine Byte-Liste in einen Hex-String um (z. B. [3, 15, 6, 4] → "3f64").
• encode_rle(flat_data): Kodiert flache Daten in RLE-Format (z. B. [15,15,15,4,4,4,4,4,4] → [3,15,6,4]).
• get_decoded_length(rle_data): Berechnet die Länge der dekodierten Daten aus RLE-Daten.
• decode_rle(rle_data): Dekodiert RLE-Daten zurück in flache Daten.
• string_to_data(data_string): Wandelt einen Hex-String in Byte-Daten um.
• to_rle_string(rleData): Erzeugt einen lesbaren RLE-String mit Dezimalzahlen und Doppelpunkten (z. B. "10f:64").
• string_to_rle(rleString): Wandelt einen solchen RLE-String zurück in Byte-Daten.

Schritt-für-Schritt-Implementierung

1. count_runs – Anzahl der Runs ermitteln

Diese Funktion zählt, wie oft sich der Wert in der Liste ändert. Ein Run endet, wenn der nächste Wert anders ist. Beispiel: [15,15,15,4,4,4,4,4,4] hat zwei Runs: drei 15er und sechs 4er.

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

2. to_hex_string – Daten in Hex-String umwandeln

Wandelt eine Liste von Zahlen (0-255) in einen Hex-String um. Jede Zahl wird zweistellig hexadezimal dargestellt, ohne Leerzeichen.

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

3. encode_rle – RLE-Kodierung

Diese Funktion erzeugt aus flachen Daten die RLE-Repräsentation. Dabei wird für jeden Run die Anzahl und der Wert als Byte-Paar gespeichert.

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

4. get_decoded_length – Länge der dekodierten Daten berechnen

Da RLE-Daten aus Paaren (Länge, Wert) bestehen, ist die dekodierte Länge die Summe aller Längen.

def get_decoded_length(rle_data):
    return sum(rle_data[0::2])

5. decode_rle – RLE-Dekodierung

Diese Funktion expandiert die RLE-Daten zurück in die ursprüngliche flache Liste.

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 bytes(flat)

6. string_to_data – Hex-String in Bytes umwandeln

Diese Funktion ist die Umkehrung von to_hex_string. Sie nimmt einen Hex-String (z. B. "3f64") und wandelt ihn in Byte-Daten um.

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

7. to_rle_string – RLE-Daten als lesbaren String ausgeben

Diese Funktion erzeugt einen String, der die RLE-Daten im Format Länge:Wert (dezimal:hex) getrennt durch Doppelpunkte darstellt.

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

8. string_to_rle – RLE-String in Byte-Daten umwandeln

Diese Funktion parst einen RLE-String (z. B. "10f:64") und wandelt ihn in Byte-Daten um.

def string_to_rle(rleString):
    parts = rleString.split(':')
    rle = []
    for part in parts:
        length, value = part.split(':')
        rle.extend([int(length), int(value, 16)])
    return bytes(rle)

Zusammenhang mit aktuellen Trends

RLE wird nicht nur in der Bildverarbeitung verwendet, sondern auch in vielen modernen Anwendungen. So nutzen beispielsweise KI-gestützte Bildkompressionsverfahren oft RLE als eine von mehreren Stufen. Auch in der Finanzanalyse werden RLE-ähnliche Verfahren eingesetzt, um Kursdaten zu komprimieren, wenn sich Kurse über längere Zeit nicht ändern. In der Spieleentwicklung, besonders bei Pixel-Art-Spielen wie denen auf der Nintendo Switch, ist RLE ein Standardverfahren, um Speicherplatz zu sparen.

Stell dir vor, du entwickelst ein Spiel mit einem Pixel-Art-Charakter, der aus vielen gleichen Farbblöcken besteht. Mit RLE kannst du diese Daten effizient speichern und schnell laden. Das spart nicht nur Speicher, sondern auch Ladezeiten – ein entscheidender Vorteil in der heutigen schnelllebigen Gaming-Welt.

Häufige Fehler und Tipps

• Off-by-one-Fehler: Achte darauf, dass du bei count_runs den ersten Run korrekt zählst und die Schleife richtig indexierst.
• Hex-Darstellung: Verwende immer Kleinbuchstaben für Hex-Ziffern, um Konsistenz zu wahren.
• Typkonvertierung: Die Funktionen geben bytes zurück, nicht list. Achte auf die korrekte Rückgabe.
• Testen mit gegebenen Beispielen: Nutze die Beispiele aus der Aufgabenstellung, um deine Implementierung zu überprüfen.

Fazit

Mit diesen Funktionen bist du bestens gerüstet, um das Projekt 1 von COP3504C erfolgreich abzuschließen. RLE ist ein grundlegendes Kompressionsverfahren, das dir in vielen weiteren Informatikkursen begegnen wird. Viel Erfolg beim Programmieren!