Die Idee der Huffman-Codierung (bezogen auf die Bildverarbeitung) beruht auf der Annahme, daß in einem Bild einige Farbwerte häufiger vorkommen als andere.
Die Farben sind mit einem Bitcode von statischer Länge gespeichert, d.h. jede Farbe wird z.B. durch einen Bytewert repräsentiert. Huffman schlägt vor, einen Code variabler Länge zu verwenden, d.h. häufig vorkommende Farbcodes werden durch kürzere, seltenere Farbcodes werden durch länger Bitkombinationen ersetzt.
Dieses Verfahren ist schon vom Morsealphabet bekannt. Huffman hat aber
einen Algorithmus zur Feststellung von optimalen variablen Codes entwickelt.
Zunächst werden die Häufigkeiten der einzelnen Farben festgestellt.
Danach wird ein Binärbaum aufgebaut, an dessen Wurzelknoten die einzelnen
Farbwerte stehen. Der Weg durch den Binärbaum liefert den variablen
Code, wobei ein linker Zweig 0 und ein rechter 1 liefert. Das geniale (und
auch notwendige) an diesem Verfahren ist die Eindeutigkeit der gefundenen
Codes, so daß die Codes keine Trennzeichen benötigen.
|
![]() |
||||||||||||||||
Daraus ergeben sich folgende Codierungen:
|
Vor- und Nachteile
Ein Nachteil der Huffman-Codierung besteht darin, daß neben den codierten Bilddaten auch die
Codierungstabelle gespeichert werden muß. Enthält ein Bild zuviele unterschiedliche Farbwerte, so
wird der Platzgewinn durch die kürzeren Codes durch den Speicherbedarf der Codierungstabelle aufgehoben
oder sogar überschritten.
Besteht das Bild nun aber aus wenigen Farbwerten, so zeigt sich ein deutlicher Vorteil der Huffman-Codierung
gegenüber der Runlength-Codierung: Die Huffman-Codierung
ist unabhängig von der Position der verschiedenfarbigen Pixeln.