The JPEG standard (ISO/IEC 10918-1)

Intro

• JPEG = Joint Photographic Experts Group.
• Developed in 1992 by the ISO [ISO, 1992].
• True color (up to 24 bits/pixel) and grayscale (up to 8 bits/pixel) images.
• Eligible compression quality between $0-100$ [Wallace, 1992].
• Visually lossless reconstructions of color images for compression ratios about $1$ bits/pixel (bpp).
• Based on the Discrete Cosine Transform (DCT).
• Several working modes: lossy (JPEG), lossless (JPEG-LS) and hierarchical.

A. lossless JPEG [ISO, 1992]

• Based on an spatial predictor and a 0-order static variable-length encoder (Huffman).

• The block diagram is: where and

Coder

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

Decoder

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

Categories:

Huffman codes:

Encode symbol

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$):

• [1] $SSSS=3$.
• [2] Output $\leftarrow 100_2$.
• [3.A] Output $\leftarrow 101_2$.

Example ($e=-9$):

• [1] $SSSS=4$.
• [2] Output $\leftarrow 101_2$.
• [4.A] Output $\leftarrow 0110_2$ (the four least significant bits of the two's complement of $-10_{10}$).

Decode symbol

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{next}~(SSSS-1)$ bits.
4. Else:
   1. $e\leftarrow (-1)~\text{AND}~(x << (SSSS-1)+\text{next}~(SSSS-1)~\text{bits}+1)$.

Example (decode $100101$):

• [1] $SSSS\leftarrow 3$.
• [2] $x\leftarrow 1$.
• [3.A] $e\leftarrow 2^2+$ next two input bits (01) $=101_2=5_{10}$.

Example (decode $1010110$):

• [1] $SSSS\leftarrow 4$.
• [2] $x\leftarrow 0$.
• [4.A] (Using 8 bits of precision) $e\leftarrow$ $11111111_2$ AND ($0000_2+110_2+1_2) = 11110111_2 = -9_{10}$ (the four least significant bits of $0111_2$ are supposed to be $1$.

Lab

  Codec | lena boats pepers zelda Average                                                                              
--------+--------------------------------                                                                              
      : |    :     :      :     :       :                                                                              
ls-jpeg | ....  ....   ....  ....    ....

B. (Lossy) JPEG

Coder

1. RGB $\rightarrow$ YCbCr.
2. 4:2:0 chroma subsampling.
3. $[0,255]\rightarrow [-128,127]$ for each component.
4. For each component:
   1. Compute $8\times 8$-DCT.
   2. Quantize.
   3. Encode.

Decoder

1. For each component:
   1. Decode.
   2. Compute inverse $8\times 8$-DCT.
2. $[-128,127]\rightarrow [0,255]$ for each component.
3. YCbCr $\rightarrow$ RGB.

RGB $\leftrightarrow$ YCbCr

Cb and Cr signals can be subsampled without visual loss.

4:2:0 chroma subsampling

Reduces the size of Cb and Cr signas in 1/4.

$[0,255]\leftrightarrow [-128,127]$

Each component must be 0-average. This is neccesary to reduce the arithmetic precision of the computation of DCT.

$8\times 8$ DCT