Dekompression eines Bildes mit Huffman-Baum?
Es wurde zuerst ein Bild mit der Lauflängencodierung komprimiert, anschliessend wurde ein Huffman-Baum für die Lauflängen gemacht (Bild unten). Der Huffman-Baum wird im Header des Bildes mitgegeben und sieht wie folgt aus.:
Die Binärfolge besteht abwechselnd aus einer Lauflänge und einer Farbe. Ich sollte nun laut der Aufgabenstellung ein Bild aufzeichnen, was oben gegeben ist. Ich habe es mehrmals versucht, aber ich konnte nur Breite (7), Höhe (5) und Farbtiefe (3) herausfinden. Wie stelle ich es an?
1 Antwort
In den codierten Bilddaten steht immer abwechselnd ein Huffman-Code, der die Lauflänge codiert, und eine Farbe, deren Wert drei Bit lang ist (Farbtiefe 3 Bit).
Also schauen wir, welcher Huffman-Code am Anfang steht. Dazu beginnen wir in der Wurzel des Baums. Wenn wir eine Null lesen, gehen wir zum linken Kindsknoten, wenn wir eine Eins lesen, zum rechten.
Das erste Bit ist eine Null, also gehen wir nach links und landen bei einem Blattknoten, also ist der Code hier zu Ende. Im Blattknoten ist die Lauflänge 1 gespeichert. Wir lesen die nächsten 3 Bit (Farbtiefe), die sind 000. Also färben wir die nächsten 1 Pixel mit der Farbe 000.
Und jetzt das Ganze von vorne: Wir starten wieder bei der Wurzel. Wir lesen eine Eins und gehen nach rechts. Wir lesen noch eine Eins und gehen nach rechts. Wir lesen wieder eine 1 und sind bei einem Blattknoten angekommen, der die Lauflänge 20 speichert. Wir lesen die Farbe aus: 001. Also färben wir die nächsten 20 Pixel mit der Farbe 001.
Schaffst Du den Rest?
Vielen Dank für die Antwort. Mich haben anfangs die Zahlen unterhalb der Blattknoten verwirrt. Wenn ich mir das so anschaue, sieht es aus, als ob sie die Anzahl Vorkommnisse im Bild darstellen (20-er Folge bspw. nur 1 Mal). Ich hab jetzt das Bild gezeichnet von links nach rechts und oben nach unten: 1 * 000, 20 * 001, 5 * 100, 1 * 000, 2 * 110, 5 * 100, 1 * 000.