# Zigzag codification and Huffman coding in JPEG: Matlab code

In this post we are going to explain the science behind the JPEG codification. Have a look to the following image: Figure 1. Lena JPEG Decompressed image
Is it familiar to you? Probably you already know the famous Lena! If you want to learn how the JPEG compression and decompression we highly advice to download our free Matlab code available in Mathworks: http://uk.mathworks.com/matlabcentral/fileexchange/57248-zigzag-codification-and-huffman-coding-in-jpeg–matlab-code

In addition, you will be able to visualize the stages in the process:  Figure 2. Lena JPEG blocks and their corresponding histograms

This code is provided with comments through all the steps in the JPEG algorithm: Figure 3. JPEG encoder and decoder Behind The Sciences code in Matlab
Now, if you want to quickly understand what is going on there, have a look to the following theory:

The entropy coding of JPEG consists in allocating the components in a zigzag order by using the Run-length encodingalgorithm, so the components with similar frequency are grouped and we add zeros and apply the Huffman coding in the components different from zero.

Example:
Let “B” be the matrix of DCT coefficients:

The zigzag sequence would be:
 −26 −3 0 −3 −2 −6 2 −4 1 −3 1 1 5 1 2 −1 1 −1 2 0 0 0 0 0 −1 −1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
The DCT coefficients are ordered in this way to be “scanned” and grouped according to their frequency, in matrix of 8×8.

Huffman coding consists in taking the symbols (for example, the DCT coefficients) and coding them with a variable length which is assigned according to some probabilities. A symbol which is used several times can be coded with just 2 bits, while the symbols that are used less often will be represented with more bits in the code.

A JPEG file contains 4 tables that define the mapping between the variable length codes (from 1 to 16 bits) and the coding values which have a length of 1 byte. In order to create these tables, the algorithm needs to compute the frequency of each symbol (i.e., the DCT code word) in the image and assign the corresponding bit stream. Most of the JPEG coders use the Huffman tables but some of them optimize these tables, which implies creating a binary tree that achieves a better efficiency in the generated Huffman tables.
Therefore, for a given image, the JPEG computation is as follows: Figure 4. JPEG computation scheme (algorithm)

Note that JPEG can use Arithmetic coding instead of Huffman, but in this post, we will focus on Huffman codification. The code tables mentioned earlier need to be known to perform the entropy encoding. The basic 4 blocks that form this encoder are the “statistical model”, “adapter”, storage area” and “encoder”. The statistical model translates the “descriptors” in symbols and each symbol is assigned to code word or probability. The block “adapter” is responsible of the code word assignment (using the Huffman code) or estimate the probabilities (for the arithmetic coding) that are needed by the encoder. The storage area keeps the Huffman table with the code words or the estimated probabilities for the case of the arithmetic codification. By using this code words, the encoder converts this symbols in compressed data bits.

The obtained symbols belong to an alphabet which contains all the possible symbols that the model can generate. Normally, some of these symbols have high probability while some others have lower probability. Recall that the objective of the entropy coding is to assign short code words to high probability symbols and longer ones to the less probable.
The Huffman entropy encoder is formed by the following four blocks: Figure 4. Huffman entropy encoder
The Huffman statistical model converts the descriptors in the actual symbol that is going to be coded. For instance, the model used in JPEG converts the 16 contiguous zeros of AC coefficients in a symbol of 16 zeros. This type of conversion is is performed with the aim of improving the Huffman codes efficiency. The symbols created by the statistical model are sent through the switch S1 to the Huffman encoder or the Huffman adaptor, as shown in the image above.
In a first step, the symbols are fed to the adaptor, where data is analyzed and used to create the Huffman table. In the second stage, the data is coded. Switch S2 makes the Huffman table suitable for the case of an external source.

The following figure shows the Huffman entropy decoder: Figure 5. Huffman entropy decoder

Therefore, the data are decoded in symbols by the Huffman decoder. The code words always come in a Huffman coding table which is loaded in the storage area that we’ve seen earlier. The data needed to generate this table can be introduced with the compressed data. The symbols are translated again by the descriptors in the statistical model.

Finally, the JPEG decoder structure is as follows: Figure 6. JPEG decoder

Sources

•           http://www.cs.cf.ac.uk/Dave/Multimedia/node234.html