Facsimilie Codierung

Bei der Facsimilie Codierung handelt es sich um ein Verfahren zur Kompression von schwarz/weiss Bildern. Dieses Verfahren wird bereits seit langer Zeit beim Faxen verwedet, und ist eines der ersten Kompressionsverfahren überhaupt. Die Kompression ist notwendig, um das zu faxende Bild über die Telefonleitung zu senden.

1 Aufwand

Der Aufwand faximilie-basierter Kompression ist (mindestens) quadratisch.

2 Modell

Es existieren verschiedene Algorithmen, die jedoch von den selben Vorraussetzungen ausgehen: gegeben seien zwei Zustände (schwarz und weiß), die die Zustände eines Marov-Modells bilden. Der Zustand Sb sagt aus, das das zuletzt gesehene Pixel ein schwarzes war. Im Zustand Sw wurde zuletzt ein weißes Pixel betrachtet. Von beiden Zuständen kann man in den jeweils anderen Zustand wechseln, oder aber im gegenwärtigen Zustand bleiben. Mit den bedingten Wahrscheinlichkeiten für die Zustandswechlsel folgt daraus folgendes Modell:

Man kann davon ausgehen, dass einem schwarzen Pixel eher wieder ein schwarzes folgt, und einem weißem Pixel wieder ein weißes.

Es gilt also: P(w|w) und P(b|b) sind größer als P(w|b) und P(b|w). Hieraus ergeben sich dann die einzelnen Wahrscheinlichkeiten für das Auftreten von verschiedenen Blöcken. Mit Hilfe dieser empirisch festgelegten Wahrscheinlichkeiten für die Blockgrößen kann man nun eine sinnvolle Codierung der Blockgrößen bestimmen. Mehr dazu in Abschnitt 4.

3 Varianten

In der Praxis werden in der Regel folgende Algorithmen verwendet: der einsimensionale MH-Algorithmus (MH=modified Huffman), sowie der zweidimensionale MR-Algorithmus (MR=modified READ; READ=relative element adress designate). Der MH-Algorithmus funktioniert auf folgende Weise: Man betrachtet jede Zeile für sich, und bildet nacheinander maximal große schwarze und weiße Blöcke. In jedem erzeugten Block sind also nur Pixel der gleichen Farbe. Anschließend holt man sich den modifizierten Huffman-Code des entsprechenden Farb-/Blöckgröße-Paares. Wichtig ist hier jedoch, das man mit einem weißen Pixelblock beginnt. Beginnt die Zeile mit einem schwarzen Pixelblock, so wird ein vorangedachter weißer Pixelblock der Länge 0 angehangen. Am Ende der Zeile wird noch ein spezieller End-of-Line Huffman-Code hinzugefügt.

function MH (String Bildzeile)
  1. bilde i schwarze und weiße Blöcke maximaler Größe aus der gegebenen Bildzeile
  2. Wenn die Farbe des ersten Blocks c="b", dann speichere die Blöckgröße s=0 und die Farbe c={"b") als ersten Block: A.add=(s,c)
  3. speichere die Blöckgröße s und die Farbe c={"b","w") für jeden Block: A.add=(s,c)
  4. hole den modifizierten HuffmanCode für jedes Paar (c, s) in A und speichere ihn in B: B.add(getModifiedHuffmanCode (c, s))
  5. hole den modifizierten HuffmanCode für das Zeilenende und speichere ihn in B: B.add(getEndHuffmanCode())
function MH_Inverse (String codierteBildzeile)
  1. Setze Blockfarbe c="w"
  2. Für Zeichen i=1..codierteBildzeile.length der codierten Bildzeile, iteriere Schritte 3 bis 7:
  3. Hole Zeichen c: c=codierteBildzeile.charAt(i)
  4. Füge das Zeichen einem TestString hinzu: String A=A+c
  5. Teste, ob der Teststring ein Element des modifizierten HuffmanCodes ist
  6. Wenn ja: hole Blockgröße für entsprechendes Huffman-Code-/Blockfarbe-Paar und speichere: C=add(getBlockSizeFronHuffmanCode(TestString,c)); Wechsele die Blockfarbe; setze TestString=""
  7. Wenn nein: gehe zu (2)
  8. Setzte Pixel entsprechend der Blockgröße in C, abwechselnd weiß und schwanz, beginnend mit weiß
Der MR-Algorithmus betrachtet neben der aktuellen Bildzeile auch noch die vorherige Bildzeile, und vergleicht diese miteinander. Hierdurch wird mehr Korrelation zwischen den Pixeln ausgenutzt, und es ist eine höhere Kompression möglich.

4 Spezielle Codes für den MH-Algorithmus

Entwickelt wurde eine Reihe von Codes, die alle auf folgende Grundlage basieren:

Bei einer Faxseite gibt es nach DIN-Norm 1728 Zeichen je Zeile. Ein Block kann demnach maximal 1728 Zeichen lang sein. Zudem sind ebenfalls 1728 verschieden große Blöcke möglich, so das das HuffmanAlphabet sehr groß werden würde. Aus diesem Grund wird ein Block r, welcher mehr als 63 Zeichen enthält folgendermaßen codiert:

r = 64 * m + t für m=1,2,...27 und t=0,1,...63

Der Block wird dann als Codepaar 64*m und t dargestellt. Codes für 64*m werden Grobcodes (make-up Codes), Codes für 1 bis 63 Schlusscodes (terminate Codes) genannt.

Im Nachfolgenden wird ein Ausschnitt des Codes der geläufigen CCITT Gruppe T4 gezeigt (Dieser wird auch in nachfolgenden Applet verwendet):

5 Beispiel

 
Gegeben Sei folgende Bildzeile (0=weiß, 1=schwarz):
0000 1111 0110 1101 1111 1111 1111 1011 1111 1101 1111 1111 1110 0000

Nun werden nacheinander maximal Große Blöcke gleicher Farbe gebildet:
0000 1111   0   11   0   11   0 11111111111111   0 11111111   0 111111111111  00000
   s    w   s    w   s    w   s              w   s        w   s            w      s        

Nun schauen uns das Paar aus Blockgröße und Blockfarbe an:
4  4  1  2  1  2  1  14  1  8  1  12
s  w  s  w  s  w  s  w   s  w  s   w       

Da wir nicht mit einem weißen Block, wie gefordert, beginnen, fügen wir einen leeren weißen Block hinzu: 
0  4  4  1  2  1  2  1  14  1  8  1  12
w  s  w  s  w  s  w  s  w   s  w  s   w 

Jede Zeile muss mit einem Zeilen-Ende Signal abgeschlossen werden:
0  4  4  1  2  1  2  1  14  1  8  1  12  EOL
w  s  w  s  w  s  w  s  w   s  w  s   w   s  

Und suchen den zu jedem paar entsprechenden Code (0,w --> 00110101;    4,s -->011;     4,w -->1011;   ...):
00110101 011 1011 010 0111 010 0111 010 110100 010 10011 010 001000 000000000001

Nun noch den Code sauber hinschreiben, und fertig:
0011 0101 0111 0110 1001 1101 0011 1010 1101 0001 0100 1101 0001 0000 0000 0000 001

6 Applet

alt="Your browser understands the <APPLET> tag but isn't running the applet, for some reason." Your browser is completely ignoring the <APPLET> tag! Das Beispiel-Applet

Das Applet soll veranschaulichen, wie der MH-Algorithus abläuft.

Handhabung des Applets:

  1. 1. Wählen Sie ein Bild aus, das Sie betrachten möchten
  2. 2. Wählen Sie eine Zeile des Bildes mit Hilfe des Spinners aus, welche detaillierter betrachtet wird.
  3. 3. Drücken Sie den Button "Encodieren".
  4. 4. Die Einzelschritte der Encodierung werden im "Step" Fenster erscheinen.
  5. 5. Decodieren Sie das Bild wieder durch drücken von "Decode"
  6. 6. Die Einzelschritte der Decodierung werden im "Step" Fenster erscheinen
  7. 7. Sie können jederzeit das Applet durch drücken des Buttons "Reset" zurücksetzten

 

 

Entwickelt von Nadine Hassis und Rene Worzischek im Rahmen der Datenkommpressionsvorlesung der Universität Tübingen, 2007.

Quellcode HTML & Java-Source.