Contents

1 Intro

• JPEG = Joint Photographic Experts Group.
• Developed in 1992 by the ISO [1].
• True color (up to 24 bits/pixel) and grayscale (up to 8 bits/pixel) images.
• Eligible compression quality between 0 − 100 [3].
• 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, lossless and hierarchical.

2 Lossless JPEG [2]

• Lossless.
• Based on an spatial predictor and a 0-order static variable-length encoder (Huffman).
• The block diagram is

  

  where

  Prediction Context

  Predictors
  P 0	ŝ ← 0
  P 1	ŝ ← a
  P 2	ŝ ← b
  P 3	ŝ ← c
  P 4	ŝ ← a + b − c
  P5	ŝ ← a + (b − c)∕2
  P6	ŝ ← b + (a − c)∕2
  P7	ŝ ← (b + c)∕2

3 Codec LS-JPEG

3.1 Compressor

1. Generate ŝ.
2. Compute the prediction error e ← s −ŝ.
3. Encode e.

3.2 Descompressor

1. Generate ŝ (idential to the Step 1 of the compressor).
2. Descode e.
3. Compute the pixel value s ← e + ŝ.

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)

• SSSS = 3.
• Output ← 100₂.
• Output ← 101₂.

Example (e = −9)

• SSSS = 4.
• Output ← 101₂.
• Output ← 0110₂ (the four least significant bits of the two’s complement of −10₁₀).

Category	Huffman code
SSSS DIFF 0 0 1 -1,1 2 -3,-2,2,3 3 -7,,-4,4,,7 4 -15,,-8,8,,15 5 -31,,-16,16,,31 6 -63,,-32,32,,63 7 -127,,-64,64,,127 8 -255,,-128,128,,255 9 -511,,-256,256,,511 10 -1023,,-512,512,,1023 11 -2047,,-1024,1024,,2043 12 -4095,,-2048,2048,,4095 13 -8191,,-4096,4096,,8191 14 -16383,,-8192,8192,,16383 15 -32767,,-16384,16384,,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 ← the next input bit.
3. If x≠0, then:
   1. e ← x << (SSSS − 1) + siguientes(SSSS − 1) bits.
4. Else:
   1. e ← (−1) AND (x << (SSSS−1)+siguientes (SSSS−1) bits+1).

Example (decode 100101)

• SSSS ← 3.
• x ← 1.
• e ← 2²+ next two input bits (01) = 101₂ = 5₁₀.

Example (decode 1010110)

• SSSS ← 4.
• x ← 0.
• (Using 8 bits of precision) e ← 11111111₂ AND (0000₂ + 110₂ + 1₂) = 11110111₂ = −9₁₀ (the four least significant bits of 0111₂ are supposed to be 1.

Lab

1. Download ftp.cs.cornell.edu:/pub/multimed/ljpg.tar.Z and compile it.
2. Fill the table
     Codec | lena boats pepers zelda Average  
   --------+--------------------------------  
         : |    :     :      :     :       :  
   ls-jpeg | ....  ....   ....  ....    ....

6 Lossy JPEG

Para una imagen RGB, el algoritmo bsico consiste en:

1. Convertir la imagen al dominio YCbCr.
2. Submuestrear la crominancia.
3. Desplazar cada componente al rango [−128,127].
4. Para cada componente (Y, Cb y Cr):
   1. Aplicar la (8 × 8)-DCT a cada componente.
   2. Cuantificar los coeficientes DCT.
   3. Codificar entrpicamente los coeficientes cuantificados.

7 [0,255] → [−128,127]

• Every component should be 0-average. For this reason, if the values of the Y, Cb and CR components are in the range [0,255], the 128 is substracted (pixel-to-pixel) from each of them.
• This is neccesary to reduce the arithmetic precision of the computation of the next step (the DCT).

8 8x8 2D-DCT

• Every component is DCT-transformed in blocks of 8 × 8 pixels.

9 Basis functions of the 8x8 2D-DCT

• Every 8 × 8-DCT coefficient represent the weight that the corresponding pattern has to reconstruct the block.

10 Advantages of the 8x8 2D-DCT

• A lower total computational cost:
  It’s faster the computation of ( × ) 8 × 8-DCTs than only one N × N-DCT.
• “In-line” operation:
  The compressor process the images using blocks of 8 × 8 pixels, independiently of the size of the image.

11 Scalar quantization

• The main objective of the 8 × 8-DCT is the spatial compactation of the energy in the image. As a consequence, a small set of coefficients accumulate the most part of this energy.
• After this decorrelating step, the DCT coeffients are also very decorrelated. Therefore, scalar quantization is a good choice to quantize the spectral domain in order to reduce de amoun of encoded data.
• The quantization generates a big number of DCT coefficients very close or equal to 0, following a Laplace probability distribution.
• The quantization step is so important in the result that the JPEG studied and determined the best quantization matrixes (one for the luma and other for the chroma).

• At it can be seen, there is an overall tendence to preserve the low frequencies of the image.

• The quantization is described by

  (1)

  where Z[⋅,⋅] is the quantization matrix.

• It is possible to use different quantization matrixes, but they should be sent to the decompressor.

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.¹

13 Interlacing of the color components

• Typically, in JPEG the 4:2:0 subsamplig pattern is the most used one (see Section ??).
• The color interlacing enables the pipelined (IO and CPU) reconstruction of the images row-by-row.
  1. With interlacing:

     

  2. Without interlacing:

     

Example

• Let’s encode a block of a grayscale image (luminance of “lena”).

  

8 × 8-DCT

• Notice that the most part of the energy is concentrated in the DC coefficient and in the AC subrrounding coefficients.

Quantization

• Notice that the high frecuencies have been erased.

EOB generation

• The coeficients of the matrix

  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

  are visited using the zig-zag scan to tind the EOB. The result is

  39

  -3

  2

  1

  -1

  1

  0

  0

  0

  0

  0

  -1

  EOB

14 Entropy encoding of the runs

• Encoding of the DC coefficient. Substract to the DC coefficient the previous one. In the last example, we have 39 − 34 = 5. This value is encoded as a residue using the LS-JPEG encoding machinery (see Section 4). The result is 100101₂.
• Encoding of the AC coefficients. We encode the pairs ¡number-of-previous-zeros,non-zero-value¿ in two steps.
  1. Find the SSSS category correspoding to the AC coefficient. For example, if the coefficient is −3, we determine that SSSS ← 2 (see Section 4).
  2. Find the entry ¡number-of-previous-zeros,SSSS¿ in the table of AC codes proposed by the JPEG:

     JPEG AC codes (Luminance)
     Run/category	Longitud	Base code
     0/0	4	1010 (=EOB)
     0/1	3	00
     0/2	4	01
     0/3	6	100
     :	:	:
     15/10	26	1111 1111 1111 11110

     and output the base code bits. In our example, we output 01₂.

  3. Execute the Step 3 of the LS-JPEG encoding algorithm taking e = the AC coeffient. In our example, we output −3 − 2 = −4 using a binary number of SSSS = 2 bits that is 00₂.

The whole bit-stream for our example is:

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

15 Progressive transmission

• Very useful when the images are transmited over slow links.
• There are three positilities:
  1. Progressive transmission based on spectral selection:
     • All the low frequency coefficients are transmitted before than the rest of them.
     • Provides up to 64 scans.
  2. Progressive transmission based on bit-plane selection:
     • The most significant bit-planes of all coefficients are transmitted before than the rest of them.
     • Provides up to 11 scans.
  3. Progressive transmission based on a mixture of the last progressions:
     • 11 or even 64 scans could not be enough if the transmission time is big and the computational power of the received is high. In this case, the coefficients can be transmitted by bit-planes, but selecting also the coefficients attenting to their frequency.
     • Up to 704 scans.

16 The hierarchical algorithm

• It is based on building a differential pyramid and after that, every level of the pyramid (residue image) is compressed using the losy encoder or the lossless encoder.
• To create the pyramid we can use the following algorithm:
  1. Subsample (filtering previously) the image in a factor of 2 in each dimension.
  2. Interpolate the subsampled image in a factor of 2 in each dimension.
  3. Substract this image to the original one, obtaining a residue image that is the base of the pyramid (the high frequencies). Notice that if we add this image and the image obtained in the Step 1, we recover the original image.
  4. Repeat this process considering the subsampled image as the original one.
• This multi-resolution representation is useful in those cases where the original resolution of the image is too large to the actual display/printing system.

17 Motion JPEG (M-JPEG)

• When each image of a sequece is compressed idependently using JPEG, we are using a Motion JPEG compressor.
• Notice that, if the quality of the compression is constant, the size of each compressed image cound be different:

Lena 512 × 512 RGB original

Lena at 1.0 bpp (PSNR = 32.85 dB)

Lena at 0.5 bpp (PSNR = 30.91 dB)

Lena at 0.4 bpp (PSNR = 30.09 dB)

Lena at 0.3 bpp (PSNR = 28.97 dB)

Lena at 0.2 bpp (PSNR = 26.64 dB)

Lena at 0.1 bpp (PSNR = 21.29 dB)

18 Lab

• Download and compile the snr.c command line tool.
• For each image of the the Image Compression Corpus, build a table with the structure:
  # bpp MSE

  where the bpp (bit per pixel) is the result of compute the resulting bit-rate after compress and decompress the images using the command line tools cjpeg and djpeg.

• Use gnuplot to draw the rate-distortion curve of JPEG for each of the test images.

References