Next: 3.6.5 Example Up: 3.6 JPEG Previous: 3.6.3 Quantization
From www.ece.purdue.edu/.../jpgcmpr1.html :
After quantization, it is not unusual for more than half of the DCT coefficients to be equal to zero. JPEG incorporates run-length coding to take advantage of this. For each non-zero DCT coefficient, JPEG records the number of zeros that preceded the number, the number of bits needed to represent the number's amplitude, and the amplitude itself. To consolidate the runs of zeros, JPEG processes DCT coefficients in the zigzag pattern shown in figure two:
Encoding
The number of previous zeros and the bits needed for the current number's amplitude form a pair. Each pair has its own code word, assigned through a variable length code ( for example Huffman, Shannon-Fano or Arithmetic coding). JPEG outputs the code word of the pair, and then the codeword for the coefficient's amplitude (also from a variable length code). After each block, JPEG writes a unique end-of-block sequence to the output stream, and moves to the next block. When finished with all blocks, JPEG writes the end-of-file marker.
From www.ztt.fh-worms.de/.../node48.html :
DC Kodierung und Zig-Zag Scanning
Nach der Quantisierung wird der DC-Wert im Gegensatz zu den 63 AC-Werten getrennt behandelt. Die DC-Werte werden stets abhängig vom zuletzt kodierten Block der selben Bildkomponente kodiert. Dabei gilt:
Der Wert in DIFF wird als DC-Wert kodiert. Wenn kein Vorgängerblock existiert, zum Beispiel beim Beginn der Kodierung, so wird der DC-Wert kodiert.
Die AC-Werte werden unabhängig von anderen Werten kodiert. Danach werden alle kodierten Werte mit Hilfe des Zig-Zag Scanning eingelesen.
Zig-Zag Scanning
Das Zig-Zag Scanning ist ein Verfahren, um die Werte einer 8x8 Felder großen Matrix in ein eindimensionales 64 Felder großes Array zu übertragen. Es ist ebenfalls möglich, ein eindimensionales Array in ein zweidimensionales umzuwandeln.
www.ztt.fh-worms.de/.../node49.html
From www.ztt.fh-worms.de/.../node49.html :
Entropie Kodierung
Die Entropie Kodierung ist der letzte Komprimierungsschritt. Hier werden die quantisierten DCT-Werte aufgrund ihrer statistischen Häufigkeit kodiert. Der JPEG Standard umfaßt zwei mögliche Komprimierungsmethoden:
Bei der Huffman-Kodierung wird gefordert, daß die Anwendung eine oder mehrere Huffmantabellen spezifiziert. Diese Huffmantabellen werden dann zur Kodierung als auch zur Dekodierung verwendet. Das bedeutet, daß neben den Quantisierungstabellen auch die Huffmantabellen mit übertragen werden müssen.
From www.ztt.fh-worms.de/.../node53.html :
Entropie Zwischenkodierung
Mit Hilfe der Entropie Zwischenkodierung werden die AC-Werte so kodiert, daß sie später leicht mit Hilfe des Huffman-Verfahrens komprimiert werden können. Jeder von Null verschiedene AC-Wert wird mit der Lauflänge der vorangehenden AC-Nullwerte dargestellt. Dabei wird im Zig-Zag Verfahren abgetastet. Die AC-Werte sehen dann folgendermaßen aus:
AC-Wert= [LauflängeGröße][Amplitude]
Das Symbol-1 stellt zwei Informationen dar: die LAUFLÄNGE und die GRÖSSE. Symbol-2 repräsentiert eine einzige Information: die AMPLITUDE, also der Wert eines von Null verschiedenen AC-Koeffizienten. Die LAUFLÄNGE ist die Anzahl von Nullwerten bei Zig-Zag Abtastung, die vor dem von Null verschiedenen AC-Wert stehen. GRÖSSE ist die Anzahl an Bits die gebraucht wird, um AMPLITUDE binär zu kodieren.
LAUFLÄNGE repräsentiert Nullfolgen der Länge 0 bis 15. Da LAUFLÄNGE aber größer als 15 werden kann wird Symbol-1 mit dem Wert (15,0) als 16 interpretiert. Es kann maximal 3 mal der Ausdruck (15,0) erscheinen. Folgt darauf kein von Null verschiedener AC-Wert mehr, wird das Block-Endezeichen (EOB) Symbol-1 mit dem Wert (0,0) gesetzt. Es markiert das Ende der Data Unit.
Die Darstellungsweise der DC-Werte ist einfacher.
DC-Wert= [Größe][Amplitude]
Symbol-1 repräsentiert hier nur die Anzahl der Bits die gebraucht werden, um Symbol-2, also die AMPLITUDE des DC-Wertes zu kodieren.
From www.ztt.fh-worms.de/.../node54.html :
Variable Längenkodierung
Für die AC- und DC-Koeffizienten wird nun das Symbol-1 mit einem variablen Längen-Code (VLC) kodiert. dieser Code stammt aus der Huffmantabelle, die vom Anwender festgelegt wurde. Jedes Symbol-2 wird dagegen mit einem variablen Längen-Integer-Code (VLI) kodiert, der in der unten stehenden Tabelle dargestellt ist.
SIZE AMPLITUDE CODE 1 -1,1 0,1 2 -3,-2,2,3 00,01,10,11 3 -7..-4,4..7 000,..,011,100,..,111 4 -15..-8,8..15 0000,..,0111,1000,..,1111 5 -31..-16,16..31 00000,..,01111,10000,..,11111 6 -63..-32,32..63 000000,..,011111,100000,..,111111 7 -127..-64,64..127 0000000,..,0111111,1000000,..,1111111 8 -255..-128,128..255 00000000,..,01111111,10000000,..,11111111 9 -511..-256,256..511 000000000,..,011111111,100000000,..,111111111 10 -1023..-512,512..1023 0000000000,..,0111111111,1000000000,..,1111111111
VLC und VLI sind beide variable Längencodes, VLI ist aber kein Huffman Code. Ein wichtiger Unterschied zwischen den beiden Codes ist, daß die Länge des Huffman Codes (VLC) bis zur Dekodierung nicht bekannt ist. Die Länge des VLI Codes ist dagegen im vorherigen VLC Code gespeichert.
Andreas Kriegl 2003-07-23
