Image processing

3-2020-? Lecture 5
 :
Data Compression o r BrooaaddCCaasstt:
FFor Br = 1 6 6
M Mbbitit//ss
te
bit raate=16 6
Withthe
With thegrowing
growingneed
needofofreal-time
real-timevideo
videoapplication,
application, TTVVbit r 85 Mbbititss//ss
TV =8885 M
thevideo
the videocompression
compressionplays
playsthe
theimportant
importantrole
roleof
ofBand
Band HHDDTV =
5
Widthefficiency
Width efficiencyfor
forboth
bothtransmission
transmissionand
andstorage.
storage.
4
3

1
6
JPEG Compression
JPEG is an image compression standard that was developed by the “Joint
Photographic Experts Group”. JPEG was formally accepted as an
international standard in 1992.

• Main Steps in JPEG Image Compression

– Color space transform - transform RGB to YcbCr
• Each channel is coded independently
• Subsample color.
– Perform DCT on image blocks.
– Quantization
• Coefficients are quantized
• Reduce the total number of bits needed for a compressed image
– Zig-zag scan
– DPCM on DC coefficients
– Run-length encoding on AC coefficients
– Entropy coding on DCT coefficients (Huffman or Arithmetic).
JPEG works for both color and grayscale image

Gray
 YCbCr
• Y ： the luminance of the image which represents the brightness.
• Cb ： the chrominance of the image which represents the difference between the
gray and blue.
• Cr ： the chrominance of the image which represents the difference between the
gray and red.

Chrominance
(a) 4 : 4 : 4 (b) 4 : 2 : 2
Subsampling
(c) 4 : 2 : 0 (d) 4 : 1 : 1
W W W W

H Y H Y H Y H Y

t is n ot
e fo rma
h
e of t to the
W W/2 W/2 W/4
n a m
H/2 Cb The r e lated .
H C y s
alwa ratio
H Cb H Cb
b
mp l in g
subsa
W W/2 W/2 W/4
H/2 Cr
H Cr H Cr H Cr
5
 Matlab
Rgb2ycbcr
Convert RGB color values to YCbCr color space
RGB = imread('board.tif');
YCBCR = rgb2ycbcr(RGB);

Y Cb Cr
ycbcr2 Rgb

Convert YCbCr color values to RGB color space

 Shift to zero by subtracting 128 Allows using
In Encoder Side signed integer to represent both DC and AC
coefficients

Image RGB to Shift by 8*8 2D-DCT

Matrix YCbCr )128-( blocks

Ea
ch
In B
de Cod loc
pe e k
nd
en
tly
 Observation for JPEG Compression
• The effectiveness of the DCT transform coding method in JPEG relies
on 3 major observations:
• Observation 1:1 Useful image contents change relatively slowly across
the image, i.e., it is unusual for intensity values to vary widely several
times in a small area, for example, within an 8 x 8 image block.
– much of the information in an image is repeated, hence “spatial
redundancy”.
• Observation 2: 2 Psychophysical experiments suggest that humans are
much less likely to notice the loss of very high spatial frequency
components than the loss of lower frequency components.
– the spatial redundancy can be reduced by largely reducing the high
spatial frequency contents.
– JPEG uses DCT to reduce high-frequency contents and then
efficiently code the results into a string
• Observation 3:Visualacuity(accuracy
3 in distinguishing closely spaced
lines) is much greater for gray (“black and white”) than for color.
– chroma subsampling (4:2:0) is used in JPEG.
DCT Image Compression
DCT is the real part of the 2D Fourier Transform
• DCT

• Inverse DCT

2D-DCT A
2D-IDCT
DCT Properties:

Decorrelation
The principle advantage of image transformation is the removal of
redundancy between neighboring pixels.
This leads to uncorrelated transform coefficients which can be
encoded independently.
 Energy Compaction
 Efficiency of a transformation scheme can be directly measured by its
ability to pack input data into as few coefficients as possible.
 This allows the quantizer to discard coefficients with relatively small
amplitudes without introducing visual distortion in the reconstructed
image.
 DCT exhibits excellent energy compaction for highly correlated images.
 Increasing frequency

Increasing frequency
Visualization of basis Functions

Original image Energy Compaction

block
Transform
DCT Results:

DC component

2D-DCT
low frequency High frequency

low frequency  313 56  27 18 78  60 27  27

 38  27 13 44 32  1  24  10 

  20  17 10 33 21  6  16  9 
  10 8 9 17 9  10  13 1 
 6 1 6 4 3 7 5 5 
 
 2 3 0 3 7 4 0 3 
 4 4 1  2  9 0 2 4 
 
High frequency  3 1 0  4  2 1 3 1 
Mathlab
dct2
2-D discrete cosine transform
B = dct2(A) returns the two-dimensional discrete cosine transform of A.
The matrix B is the same size as A
B = dct2(A,m,n) = dct2(A,[m n])
B = dct2(A,m,n) pads the matrix A with 0's to size m-by-n before
transforming. If m or n is smaller than the corresponding dimension of A,
dct2 truncates A.
Idct2
2-D inverse discrete cosine transform
A = YCBCR(:,:,1) ;
B = dct2(A) ;
C= idct2(B)
Y
Image RGB to Shift by 8*8
2D-DCT
Matrix YCbCr )128-( blocks
DCT Coefficient Quantization

Luminance Quantization Table Chrominance Quantization

• Purpose of quantization
– reduce the total number of bits needed for a compressed image.
• Low-frequency coefficients usually have more energy than high-
frequency coefficients, The human visual system is more sensitive to
low frequencies and more sensitive to luminance to chrominance.

– Low-frequency coefficients require small quantization values.

• The human visual system is
– Luminance channels requires smaller quantization values than
chrominance channels.
• To change the compression ratio
– Simply by multiplicatively scaling the numbers in the Q(u,v) matrix.
• Quality factor
– A user choice offered in every JPEG implementation
– Linearly tied to the scaling factor
• JPEG also allows custom quantization tables to be specified and put in
the header.

Image RGB to Shift by 8 *8

2D-DCT
Matrix YCbCr )128-( blocks
Zig-Zag
Zig-Zag
Convert from 2 D array to 1D array
DPCM
DPCM Entropy
Coding

Used to code DC coefficients.

Entropy Coding of DC Coefficients
.The idea is to replace a number by a pair of symbols (size, amplitude)
where size specify how many bits are needed for represented the
coefficient and amplitude contain the actual bits.
AC category Bit Size DC difference Range Value
category Bit Size
0 0 0
1 1 1,1-
2 2 3 ,2 ,2- ,3-
3 3 7 ,...,4 ,4- ,...,7-
4 4 15 ,...,8 ,8-,...,15-
5 5 31 ,...,16 ,16-,...,31-
6 6 63 ,...,32 ,32- ,...,63-
7 7 127 ,...,64 ,64 ,...,127-
8 8 255 ,..,128 ,128- ,...,255-
9 9 511 ,...,256 ,256-,...,511-
10 10 1023 ,...,512 ,512-,...,1023-
N/A 11 2047 ,...,1024 ,1024-,...,2047-
One’s complement is used for negative numbers
Entropy Coding of DC Coefficients

Code Category
010 0
011 1
100 2
00 3
101 4
110 5
1110 6
11110 7
111110 8
1111110 9
11111110 10
111111110 11
Huffman Coding
• The DC and AC coefficients finally undergo an entropy coding step to
gain a possible further compression.
• Use DC as an example: each DPCM coded DC coefficient is
represented by (SIZE, AMPLITUDE),
 SIZE indicates how many bits are needed for representing the
coefficient,
 AMPLITUDE contains the actual bits.
• In the example we're using, codes 150, 5, −6, 3, −8 will be turned into
(8, 10010110), (3, 101), (3, 001), (2, 11), (4, 0111) .
• SIZE is Huffman coded since smaller SIZEs occur much more often.
• AMPLITUDE is not Huffman coded, its value can change widely so
Huffman coding has no appreciable benefit.
.Entropy Coding-run Length Coding on Acs
• The zigzag scan order has a good chance of concatenating long runs of
zeros.
(32, 6, -1, -1, 0, -1, 0,0,0,-1, 0,0, 1, 0,0, …, 0)
• Replace values by a pair (RUNLENGTH, VALUE) for each run of zeros in
the AC coefficients.
– RUNLENGTH is the number of zeros in the run
– VALUE is the next nonzero coefficient.
– A special pair (0,0) indicates the end-of-block.
• Not considering the first (DC) component, we will have (0,6)(0,-1) (0,-1)
(1,-1)(3,-1)(2,1)(0,0)
Zero Run Length Coding
• Encode each value which is not 0, than add the number of consecutive
zeroes in front of it
• EOB (End of Block) = (0,0)
• Only 4-bit value
• [57,45,0,0,0,0,23,0,-30,-16,0,……,0]
⇒[(0,57)(0,45)(4,23)(1,-30)(0,16)EOB]
• “Eighteen zeroes, 3” ⇒(15,0) ; (2,3) where (15,0) is 16 consecutive zeroes
Huffman Coding

at =1 , the code is said to be efficient . The code redundancy r is defined

as:
Huffman Coding
For X=x1 , x2 , x3 ,………, x5 with p(xi)=0.3,0.25,0.2 ,0.12,0.08 ,
.0.05. Find H,L, ,r

P(xi) Xi
0.55 00 0.45 00 0.3 00 0.3 1 0.3 X
01
0.45 01 0.3 01 0.25 01 0.25 00 0.25 X
12
11 0.25 11 0.25 10 0.2 01 0.2 X3
101 100 0.2 11 0.13 0.12 X4
1000 101 0.12 0.08 X5
1001 0.05 X6

H=2.36 b/symbol
L=2.38 b/symbol
0.991=
r =0.009
Huffman Coding
Image size(16*16)

P(xi) Xi
0.53 00 0.47 00 0.3 00 0.3 00 0.3 00 0.3 10.3 X01
000.23 1
0.47 01 0. 3 01 0.23 01 0.23 01 0.23 01 0.23 X2

1000.23 11
100 0.27 100 0.2 0.15 10 0.15 010.15 X3
101 101 0.2 101 0.15 0.12 11 0.12 0.08 X4
100
0.12 0.12 0.08 0.06 X5
1000 111 110 101
0.08 0.06 0.06 X6
1001 1000 111
1010 1001 0.06 0.06 X7

1011 0.06 X8
Huffman Coding
Image size(16*16)

No.0f bits hist P(xi) Xi

2*77 256*0.3 0.3 X1
2*59 59 0.23 X2
Compression Ratio
3*39 39 0.15 X3
3*21 21 0.08 X4 =692/256*3
4*15 15 0.06 X5 =90.1%
4*15 15 0.06 X6
4*15 15 0.06 X7 =100-90.1=9.9%
4*15 15 0.06 X8
1 256 692
After Compression
In Decode Side

Huffman
De-zigzag
Decoding
Bit-stream Dequantizer
De-DC Huffman
Quantization coding Decoding
Table
B
G
Chrominance R
8X8 YVU color
Upsampling Decoded
IDCT coordinate
(4:2:2 or 4:2:0) Image
Fidelity Criteria
• Resulting image is “close” to original image.
• Usually measure “closeness” with MSE (Mean Squared Error) and PSNR
(Peak Signal to Noise Ratio) – Want low MSE and high PSNR

255

Compression Ratio
JPEG Encoder
JPEG Encoder
JPEG Decoder
JPEG Decoder
JPEG
JPEG
.The proposed algorithm focus on Always , Most of image
reduce the processing time required blocks have this property
taking advantage of inter pixel
The pixels in this block
redundancy
have same value of
amplitude
88 88 88 88 88 88 88 88 704 0 0 0 0 0 0 0
88 88 88 88 88 88 88 88 0 0 00 0 00 0
88 88 88 88 88 88 88 88 0 0 00 0 00 0
88 88 88 88 88 88 88 88 0 0 00 0 00 0
88 88 88 88 88 88 88 88
2D-DCT 0 0 00 0 00 0
88 88 88 88 88 88 88 88
0 0 0 00 0 00
88 88 88 88 88 88 88 88
0 0 0 00 0 00
88 88 88 88 88 88 88 88
0 0 0 00 0 00
DCT for DC DCT for other
element only 63 elements

Quantization Quantization
for DC for other
element 63 elements

zigzag

RLE for DC RLE for other

term only 63 elements

Using DC AC Huffman
Huffman table table
JPEG
JPEG

.The modified algorithm for

encoder side shown

.Where as in the decoder side

modified quantization method is
used by adding advancement
term Δ to equation:

C(u,v)=L(u,v)*Q(u,v)+ Δ
Modified JPEG

No. of
Processing Ratio No. of MJPEG CODEC JPEG CODEC Total
Time of Similar PSNR Compression PSNR Compression Blocks Dimensions Image
Ratio SB/T Blocks (dB) Ratio (dB) Ratio (TB)
MJPEG/ B (SB)
JPEG

0.43 0.6 1850 32.027 32.263 31.830 30.655 3072 256*256*3 House

0.42 0.62 745 37.80 25.65 38.51 24.519 1188 176*144*3 Table

0.61 0.39 1209 31.22 25.761 31.406 24.197 3072 256*256*3 Peppers

0.44 0.59 1820 29.587 22.548 29.513 21.215 3072 256*256*3 Boat

0.70 0.32 1009 26.477 15.745 26.19 15.355 3072 256*256*3 Sailboat
charts illustrated percents omitted operations in equality block contents
Performance of MJPEG scheme compared with JPEG
Arithmetic (or Range)Coding
Unlike the variable-length codes, arithmetic coding, generates non-
block codes. In arithmetic coding, a one-to-one correspondence between
source symbols and code words does not exist. Instead, an entire sequence
of source symbols (or message) is assigned a single arithmetic code word.
The code word itself defines an interval of real numbers between 0 and
1. As the number of symbols in the message increases, the interval used to
represent it becomes smaller and the number of information units (say,
bits) required to represent the interval becomes larger. Each symbol of
the message reduces the size of the interval in accordance with the
probability of occurrence.

No assumption on encode source symbols one at a time.

Sequences of source symbols are encoded together.
There is no one-to-one correspondence between source symbols and
code words.
Slower than Huffman coding but typically achieves better compression.
Arithmetic Coding
• A sequence of source symbols is assigned a single arithmetic code word
which corresponds to a sub-interval in [0,1].
• As the number of symbols in the message increases, the interval used to
represent it becomes smaller.
• Smaller intervals require more information units (i.e., bits) to be
represented.

Encode message: a1 a2 a3 a3 a4
1)Assume message occupies [0, 1)
2)Subdivide [0, 1) based on the probability of αi
3)Update interval by processing source symbols.

Initial Subinterval Probability Source Symbol

[0.0,0.2) 0.2 a1
[0.2,0.4) 0.2 a2
[0.4,0.8) 0.4 a3
[0.8,1.0) 0.2 a4
Arithmetic Coding
Initial Subinterval Probability Source Symbol
[0.0,0.2) 0.2 a1
[0.2,0.4) 0.2 a2
[0.4,0.8) 0.4 a3
[0.8,1.0) 0.2 a4

Encoding Sequence
a1 a2 a3 a3 a4
1 0.2 0.08 0.072 0.0688
a4 a4 a4 a4 a4
0.06752

a3 a3 a3 a3 a3

a2 a2 a2 a2 a2

a1 a1 a1 a1 a1
0 0 0.04 0.056 0.0624

a1 a2 a3 a3 a4 [0.06752, 0.0688) or, 0.068

Arithmetic Coding
• The message a1 a2 a3 a3 a4 is encoded using 3 decimal digits or 3/5 =
0.6 decimal digits per source symbol.

• The entropy of this message is:

Note: finite precision arithmetic might cause problems due to

truncations!

-(3 x 0.2log10(0.2)+0.4log10(0.4))=0.5786 digits/symbol

Arithmetic Decoding

Decode 0.572

1.0 0.8 0.72 0.592 0.5728

a4
0.8 0.72 0.688 0.5856 0.57152

Decode 0.572
a3

0.4 0.56 0.624 0.5728 056896

a2
a3 a3 a1 a2 a4
0.2 0.48 0.592 0.5664 0.56768
a1
0.0 0.4
0.56 0.56 0.5664
LZW (Dictionary Coding)
LZW (Lempel-Ziv-Welch) coding, assigns fixed-length code words to
variable length sequences of source symbols, but requires no a priori
knowledge of the probability of the source symbols.
The nth extension of a source can be coded with fewer average bits per
symbol than the original source.
LZW is used in:
•Tagged Image file format (TIFF).
•Graphic interchange format (GIF).
Portable document format (PDF)
LZW was formulated in 1984
LZW(Interpixle Redundancy)
• A codebook (or dictionary) needs to be constructed.
• Initially, the first 256 entries of the dictionary are assigned to the
gray levels 0,1,2,..,255 (i.e., assuming 8 bits/pixel) Dictionary Location Entry

r y0 0
Consider a 4x4, 8 bit image na 1 1
126 126 39 39 tio . .
ic
126 126 39 39 l D 255 255
126 126 39 39 i tia - 256
126 126 39 39 In
LZW Coding

39 39 126 126 As the encoder examines image

39 39 126 126 pixels, gray level sequences (i.e.,
39 39 126 126 blocks) that are not in the dictionary
39 39 126 126 are assigned to a new entry.

Dictionary Location Entry

0 0
1 1 - Is 39 in the dictionary……..Yes
. . - What about 39-39………….No
255 255 - Then add 39-39 in entry 256
256 -
39-39

511 -
LZW Coding Concatenated Sequence: CS = CR + P
39 39 126 126
39 39 126 126
39 39 126 126
39 39 126 126

CR = empty
If CS is found:
(1) No Output
(2) CR=CS

:else
Output D(CR) )1(
Add CS to D )2(
CR=P )3(

• The dictionary which was used for encoding need not be sent with the
image.
• Can be built on the “fly” by the decoder as it reads the received code
words.
 JPEG2000 JPEG

Created for computer generated images Created for natural images

Discrete Wavelet Transform algorithm Discrete Cosine Transform
algorithm
Arithmetic Coding. Huffman Coding.
File extention : .jp2, .jpx, .jpf, .mj2 File extension : .jpg or .jpeg
The end