How JPEG works

Introduction - Images
An image is a 2D matrix of values Color images consist of 3 RGB matrices, Grayscale images consist of one This basic format is BMP

Introduction - JPEG
JPEG – Joint Photographic Expert Group Late 1980’s, early 1990’s Consumer level computers
Relatively high processing power Low bandwidth.

Goal: File size↓ Picture quality~ Voted as international standard in 1992 Photos Scanned text or images with sharp transitions

Introduction - Motivation
2 Observations:
A large majority of useful image content changes slowly across images Experiments show that the human eye is less sensitive to loss of high spatial frequencies

Now let’s see how we can use these observations!!!

Outline
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Outline – phase 1 (lossless)
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Color transform RGB->YCbCr
Red

RGB Image
Green

Blue

Color transform RGB->YCbCr
Transformation in the color space RGB has all the information, however, if we want to encode, we can’t decide which of the Red/Green/Blue is more important. Y – brightness (luma), Cb – Chromatic blue, Cr – Chromatic red. Only Y will show black/white TV. More bits are used for Y, less for the Cb/Cr.

To help protect y our priv acy , PowerPoint has block ed automatic download of this picture.

Color transform RGB->YCbCr
•General RBG -> YPbPr

•YPbPr -> YCbCr •ITU-R BT.601 Standard
K B = 0.114 , K R = 0.299

RGB → YCbCr Y = 0.3R + 0.6G + 0.1B

YCbCr → RGB R = Y + 1.4 ( Cr − 128 )

Cb = −0.2 R − 0.3G + 0.5 B + 128 G = Y − 0.3 ( Cb − 128 ) − 0.7 ( Cr − 128 ) Cr = 0.5 R − 0.4G − 0.1B + 128 B = Y = 1.8 ( Cb − 128 )

Color transform RGB->YCbCr

K B = 0.114 , K R = 0.299

Color transform RGB->YCbCr
Red

RGB Image
Green

Blue

•Marge’s hair •Bart’s shirt

Color transform RGB->YCbCr
Y

RGB Image
Cb

Cr

Outline – phase 2 (lossless)
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Divide the picture
The picture is divided to 8x8 pixel blocks The 2 phases are performed for each block separately.

Outline – phase 3 (lossless)
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Conversion to frequency domain
Purpose:
Convert from spatial domain to frequency domain Be able to separate what the eye can see from the imperceptible. Similar to deleting high frequencies in MP3 format

Conversion to frequency domain
Methods:
Discrete Fourier transform - DFT Discrete Sine transform - DST Discrete Cosine transform – DCT

We use DCT – Why?

Conversion to frequency domain – why to use DCT
DFT:
Converts signal of both imaginary and real numbers. Higher complexity than DCT \ DST.

DST:
Works on sine basis functions If values in borders are high, higher coefficients are used No average base function

DCT:
No imaginary coefficients Values at borders are not necessarily low Gives better results – higher low frequencies coefficients, lower high frequencies coeffs. More energy is concentrated in the small frequencies

1D Sine basis functions basis function 1 1 0.8 0.6 0 0.4 0.2 0 -0.5 -0.5 -0.5 0 0 1 basis function 2 1 basis function 3 1 basis function 4 0.5 0.5 0.5

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

basis function 5 1 1

basis function 6 1

basis function 7 1

basis function 8

0.5

0.5

0.5

0.5

0

0

0

0

-0.5

-0.5

-0.5

-0.5

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

1D Cosine basis functions basis function 0 1 0.8 0.6 0 0.4 0.2 0 -0.5 -0.5 -0.5 0 0 1 basis function 1 1 basis function 2 1 basis function 3 0.5 0.5 0.5

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

basis function 4 1 1

basis function 5 1

basis function 6 1

basis function 7

0.5

0.5

0.5

0.5

0

0

0

0

-0.5

-0.5

-0.5

-0.5

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

-1

1

2

3

4

5

6

7

8

1D Cosine basis functions
A set of Orthogonal basis functions that span the eight sample space. DC coefficient (u=0)
Average value

AC coefficients (u>0)
The higher the frequency, the less we notice the signal.

1D DCT
S(u) – 1D DCT coefficients s(x) – 1D sample value
C (u ) 7  ( 2 x + 1) uπ   S (u ) = ∑ s ( x ) cos  16   1 2 x =0    C (u ) =  2  7 C (u )  ( 2 x + 1) uπ    1 s ( x) = ∑ S ( u ) cos    2 16 u =0  

u=0 u>0

2D Cosine basis functions
A set of 64 2D basis functions
Multipication of the horizontal and the vertical 1D DCT.

Each 8x8 block is represented by 64 coefficients Actually applying 2 one dimentional DCT transforms, once in the x direction and then in the y direction

2D Cosine basis functions

Demo

2D DCT
S(u,v) – 2D DCT coefficients s(x,y) – 2D sample value
C (u ) C ( v ) 7 7  ( 2 x + 1) uπ S ( u, v ) = ∑∑ s ( x, y ) cos  16 2 2 x =0 y =0    ( 2 y + 1) vπ  cos  16   7 C (v ) 7 C (u )  ( 2 x + 1) uπ   ( 2 y + 1) vπ s ( x, y ) = ∑ ∑ 2 S ( u, v ) cos  16  cos  16 2 v =0 u =0     1  C (u ) =  2  1  u=0 u>0      

2D DCT
Resulting matrix contains 64 values 1024…1023. The biggest time consuming factor, simple methods take O(n^3). Better implementations achieve O(n^2*log(n)) or even faster with decreasing accuracy.

2D DCT
Demonstration of getting image coefficients and restoring image from the coefficients

Demo

Outline – phase 4 (lossy)
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Quantization
Purpose:
Eliminate less significant information Decrease the amount of information in the file Leave the image close to the original for human eye vision.

How?
We use a quantization matrix Each coefficient in divided by separate quantization factor Results are rounded to integers

Quantization matrices

Quantization matrices
Stored in the final JPEG file “Typical used quantization matrices” are result of research on output image quality. After quantization values in the matrix are “small” integers, repetitions should occur more often

Quantization

Demo

Outline – phase 5 (lossless)
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Entropy coding
Purpose:
Encode the resulting Coefficients in minimum bits without loosing more data.

DC coefficient
Encode the difference between the value and already coded value

AC coefficients
Transform to 1D vector + Huffman coding

Entropy coding – AC encoding
ZigZag 2D->1D

Result vector will be encoded using Huffman coding. Trailing zeros marked using EOF marker

Entropy coding – AC encoding

9 0  3  2 1  0 0  0 

3 6 2 0 0 0 0 5 4 0 0 0 0 0  1 5 1 0 0 0 0  5 0 0 0 0 0 0 ⇒ [3, 0,3,5, 6, 2, 4,1, 2,1,5,5, 0, 0, 0, 0,1, 0, 2, EOF ]  2 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 

Entropy coding – Huffman coding

Demo

Outline
Phase 1: Color transform Phase 2: Divide the picture Phase 3: Conversion to frequency domain Phase 4: Quantization Phase 5: Entropy Coding Comparison to other formats

Other formats - GIF
GIF
Uses patented LZW algorithm (Lampel-Ziv-Welch) Reduces number of colors to 256 (8 bit) Lossless compression Main idea: Sequences are stored in a dictionary Works well on solid colors, exact details and small text Bad for photographs

Other formats - GIF
GIF 1,542 bytes JPEG 5,433 bytes GIF 13,534 bytes JPEG 5,822 bytes

Other formats – JPEG2000
JPEG2000
Created in 2000, by the same team that built the JPEG. Changes the DCT to DWT – Discreet wavelet transform Gives much better results for sharp ends and exact details

Other formats – JPEG2000

JPEG 0.4 bits/pixel

JPEG 0.16 bits/pixel JPEG2000 0.4 bits/pixel Original image JPEG2000 0.16 bits/pixel

References http://www.dspguide.com http://en.wikipedia.org http://www.bricklin.com/webphotojournals/ gifvsjpeg.htm The JPEG Image Compression Algorithm. Damon Finell, Dina Yacoub, Mark Harmon