The JPEG standard (ISO/IEC 10918-1)

Vicente González Ruiz

July 28, 2022

Contents

 1 Intro
 2 Lossless JPEG [2]
 3 Codec LS-JPEG
  3.1 Compressor
  3.2 Descompressor
 4 Huffman encoding in LS-JPEG
 5 Huffman decoding in LS-JPEG
 6 Lossy JPEG
 7 \([0,255]\rightarrow [-128,127]\)
 8 8x8 2D-DCT
 9 Basis functions of the 8x8 2D-DCT
 10 Advantages of the 8x8 2D-DCT
 11 Scalar quantization
 12 Entropy encoding
 13 Interlacing of the color components
 14 Entropy encoding of the runs
 15 Progressive transmission
 16 The hierarchical algorithm
 17 Motion JPEG (M-JPEG)
 18 Lab
 19 Resources

1 Intro

2 Lossless JPEG [2]

3 Codec LS-JPEG

3.1 Compressor

  1. Generate \(\hat {s}\).
  2. Compute the prediction error \(e\leftarrow s - \hat {s}\).
  3. Encode \(e\).

3.2 Descompressor

  1. Generate \(\hat {s}\) (idential to the Step 1 of the compressor).
  2. Descode \(e\).
  3. Compute the pixel value \(s\leftarrow e+\hat {s}\).

4 Huffman encoding in LS-JPEG

  1. Search \(e\) in \(DIFF\) and select \(SSSS\).
  2. Encode \(SSSS\) following the base code.
  3. If \(e>0\), then:

    1. Encode \(e\) using a binary number of \(SSSS\) bits. The most significant bit of \(e\) will be always 1.
  4. Else:

    1. Encode \(e-1\) using a binary number of \(SSSS\) bits. The most significant bit of \(e\) will be always a 0.

Example (\(e=5\))

Example (\(e=-9\))

Category Huffman code
\(SSSS\) \(DIFF\)
0 0
1 -1,1
2 -3,-2,2,3
3 -7,\(\cdots \),-4,4,\(\cdots \),7
4 -15,\(\cdots \),-8,8,\(\cdots \),15
5 -31,\(\cdots \),-16,16,\(\cdots \),31
6 -63,\(\cdots \),-32,32,\(\cdots \),63
7 -127,\(\cdots \),-64,64,\(\cdots \),127
8 -255,\(\cdots \),-128,128,\(\cdots \),255
9 -511,\(\cdots \),-256,256,\(\cdots \),511
10 -1023,\(\cdots \),-512,512,\(\cdots \),1023
11 -2047,\(\cdots \),-1024,1024,\(\cdots \),2043
12 -4095,\(\cdots \),-2048,2048,\(\cdots \),4095
13 -8191,\(\cdots \),-4096,4096,\(\cdots \),8191
14 -16383,\(\cdots \),-8192,8192,\(\cdots \),16383
15-32767,\(\cdots \),-16384,16384,\(\cdots \),32767
16 -32768
\(SSSS\) Base code
0 00
1 010
2 011
3 100
4 101
5 110
6 1110
7 11110
8 111110
9 1111110
10 11111110
11 111111110
12 1111111110
13 11111111110
14 111111111110
15 1111111111110
16 11111111111110

5 Huffman decoding in LS-JPEG

  1. Decode the \(SSSS\) category using the base code.
  2. Decode the magnitude. Let \(x\leftarrow \) the next input bit.
  3. If \(x\ne 0\), then:

    1. \(e\leftarrow x << (SSSS-1) + \text {siguientes} (SSSS-1)\) bits.
  4. Else:

    1. \(e\leftarrow (-1)~\text {AND}~(x << (SSSS-1)+\text {siguientes}~(SSSS-1)~\text {bits}+1)\).

Example (decode \(100101\))

Example (decode \(1010110\))

6 Lossy JPEG

For a RGB image, the baseline algorithm consist of:

  1. Transform the image from the RGB to the YCbCr domain.
  2. Subsample the crominance (CrCb).
  3. Shift each color component to the range \([-128,127]\).
  4. For each component (Y, Cb y Cr):

    1. Apply the (\(8\times 8\))-DCT to each component.
    2. Quantize the DCT coefficients.
    3. Entropy encode the quantized coefficients.

7 \([0,255]\rightarrow [-128,127]\)

8 8x8 2D-DCT

9 Basis functions of the 8x8 2D-DCT

10 Advantages of the 8x8 2D-DCT

11 Scalar quantization

Luminance Chrominance
16111016 24 40 51 61
12 12 14 19 26 58 60 55
14131624 40 57 69 56
14 17 22 29 51 87 80 62
18223756 68109103 77
24 35 55 64 81 104 113 92
49647887103121120101
72 92 95 98 112 100 103 99
1718244799999999
18 21 26 66 99 99 99 99
2426569999999999
47 66 99 99 99 99 99 99
9999999999999999
99 99 99 99 99 99 99 99
9999999999999999
99 99 99 99 99 99 99 99

12 Entropy encoding

  1. Substract to the DC coefficient the DC coefficient of the last encoded block. This calculus exploits the correlation between blocks.
  2. Run the coefficients using the zig-zag pattern:

    in order to (partially) sorter the coefficients attending to their magnitude. Notice that, after a given coefficient, the remainder ones are zero. This situation if encoded using the EOB (End Of Block) special symbol.

  3. Encode the runs of non-zero coefficients using a variable-length code.1

13 Interlacing of the color components

Example

\(8\times 8\)-DCT

7975798282869494
76 78 76 82 83 86 85 94
7275677880787482
74 76 75 75 86 80 81 79
7370756778787985
69 63 68 69 75 78 82 80
7676717167798083
72 77 78 69 75 75 78 78
\(\Leftrightarrow \)
619-29 8 2 1-3 0 1
22 -6 -4 0 7 0 -2 -3
11 0 5-4-3 4 0-3
2 -10 5 0 0 7 3 2
6 2-1-1-2 0 0 8
1 2 1 2 0 2 -2 -2
-8 -2-4 1 2 1-1 1
-3 1 5 -2 1 -1 1 -3

Quantization

619-29 8 2 1-3 0 1
22 -6 -4 0 7 0 -2 -3
11 0 5-4-3 4 0-3
2 -10 5 0 0 7 3 2
6 2-1-1-2 0 0 8
1 2 1 2 0 2 -2 -2
-8 -2-4 1 2 1-1 1
-3 1 5 -2 1 -1 1 -3
div
16111016 24 40 51 61
12 12 14 19 26 58 60 55
14131624 40 57 69 56
14 17 22 29 51 87 80 62
18223756 68109103 77
24 35 55 64 81 104 113 92
49647887103121120101
72 92 95 98 112 100 103 99
=
39 -3 1 0 0 0 0 0
2 -1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 -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

EOB generation

14 Entropy encoding of the runs

The whole bit-stream for our example is:

100101 0100 0110 001 000 001 11110100 1010

Finally, the block is encoded using only \(35\) bits. Therefore, the compression ratio is 15:1 approximately (\(0.55\) bits/pixel).

15 Progressive transmission

16 The hierarchical algorithm

17 Motion JPEG (M-JPEG)

Lena \(512\times 512\) RGB original

Lena at \(1.0\) bpp (\(\text {PSNR}=32.85\) dB)

800

Lena at \(0.5\) bpp (\(\text {PSNR}=30.91\) dB)

800

Lena at \(0.4\) bpp (\(\text {PSNR}=30.09\) dB)

800

Lena at \(0.3\) bpp (\(\text {PSNR}=28.97\) dB)

800

Lena at \(0.2\) bpp (\(\text {PSNR}=26.64\) dB)

800

Lena at \(0.1\) bpp (\(\text {PSNR}=21.29\) dB)

800

18 Lab

19 Resources

[1]   The Joint Photographic Experts Group (JPEG). Recommendation T.81: Digital Compression and Coding of Continuous-tone Still Images. International Telecommunication Union (ITU), September 1992.

[2]   The Joint Photographic Experts Group (JPEG). FCD 14495, Lossless and Near-Lossless Coding of Continuous Tone Still Images (JPEG-LS). The International Standards Organization (ISO)/The International Telegraph and Telephone Consultative Committee (CCITT), July 1997.

[3]   G. K. Wallace. The JPEG Still Picture Compression Standard. Communications of the ACM, 34(4):30 – 44, April 1991. Se puede conseguir en ftp://ftp.uu.net/graphics/jpeg/wallace.ps.Z.

1It is possible to use Huffman and arithmetic coding. However, the marginal gain of the last one (about a 10%) and the patents that are behind it cause that the Huffman version is the most used one.