JPEG Image Compression
- Devendra Pratap Yadav
I have used the standard JPEG algorithm for compression using DCT, quantization, Run-length and Huffman encoding and written the output to binary .dat file.
We process a color input image and decode each R,G,B channel separately.
For each channel, we do the following:
1. Use 8×8 blocks of the input image.
2. Mean - Normalization (subtract 128 from all pixel values of image)
3. Obtain the DCT transform for each block.
4. Quantization
A standard quantization matrix is used, given as follows:
|
16 |
11 |
10 |
16 |
24 |
40 |
51 |
61 |
|
12 |
12 |
14 |
19 |
26 |
58 |
60 |
55 |
|
14 |
13 |
16 |
24 |
40 |
57 |
69 |
56 |
|
14 |
17 |
22 |
29 |
51 |
87 |
80 |
62 |
|
18 |
22 |
37 |
56 |
68 |
109 |
103 |
77 |
|
24 |
35 |
55 |
64 |
81 |
104 |
113 |
92 |
|
49 |
64 |
78 |
87 |
103 |
121 |
120 |
101 |
|
72 |
92 |
95 |
98 |
112 |
100 |
103 |
99 |
Every pixel value of 8x8 block is divided with corresponding value from quantization matrix and then rounded to the nearest integer.
5. Encoding
the DC coefficients
The top left pixel of
8x8 block for each block are separately stored. The difference of DC
coefficients is stored. We use DPCM to divide the numbers into 11 categories
and encode them using Huffman Encoding.
Any number n is represented as 2(k-1) + t. Where t is the residual represented using k-1 bits. Here, k is
the category of the DC coefficient.
It is encoded in the form H S M:
H = Huffman
code for category k
S = sign bit. 1 if positive
M = k-1 bit representation of t.
6. Encoding the
AC coefficients
There are 63 AC
coefficients in each 8x8 block. They are traversed in zigzag order and
converted to linear array. Then we remove the consecutive run of 0s by using
Run-Length encoding. For any number n, this gives us pair of terms (r, k)
where r is the number of zeros preceding current number and k is the category
of number. This tuple is encoded using Standard Huffman codes provided by JPEG
standard.
Any number n is represented as 2(k-1) + t
It is encoded in the form H S M:
H = Huffman
code for pair (r,k)
S = sign bit. 1 if positive
M = k-1 bit representation of t.
We use a special pair
(15,0) to denote run of 16 zeros and (0,0) to denote
end of block.
Now, obtain a binary sequence corresponding to AC and
DC coefficients.
This is written to binary file and we obtain an encoded image.
Perform the steps in reverse after reading the file to decode the image.
Standard Huffman Tables are used.
Source: https://engineering.purdue.edu/~bouman/grad-labs/JPEG-Image-Coding/pdf/lab.pdf
RESULTS:
Using the menu of our program, we first compress the image and store three compressed .dat files corresponding to each channel of image img1.dat, img2.dat, img3.dat
Then
we again decode the image from the .dat files and
save a .jpg representation using OpenCV.
The following Five images are used for analysis. Their distinctive properties
are mentioned below. The images and their encoded .dat
outputs are placed in Sample_images_and_results.zip.
For proper image comparison, see the .tiff and .jpg files in the folder.
The data table showing various calculated values for the images is as follows:
|
Image (.tiff) |
.tiff size (KB) |
.dat size (KB) |
RMSE |
Compression Ratio |
Redundancy |
|
1 |
1024 |
153 |
7.66 |
6.692810458 |
0.850585938 |
|
2 |
750 |
13.9 |
1.92 |
53.95683453 |
0.981466667 |
|
3 |
901 |
118 |
12.8 |
7.63559322 |
0.869034406 |
|
4 |
1407 |
119 |
3.5 |
11.82352941 |
0.915422886 |
|
5 |
1407 |
25.3 |
3.06 |
55.61264822 |
0.982018479 |
|
6 |
943 |
30.6 |
2.47 |
30.81699346 |
0.967550371 |
1.tiff Very low correlation and redundancy
Large amounts of varying details and colours. Low compression ratio
achieved.
Shown image is compressed by my algorithm (153 KB) and the image is saved using Photoshop is (161 KB). The Photoshop image is slightly sharper. However, both are very similar in quality and show good details.
2.tiff Very High Redundancy
Majority of image is a smooth gradient and has same color.
High compression ratio is achieved.
3.tiff Low correlation and Redundancy
Top sky portion is smooth, but lower portion has good details. Also, the
whole image has uniform Gaussian noise which will cause decorrelation.
Low compression ratio achieved.
Left image is compressed by my algorithm (118 KB) and right image is saved using Photoshop (112 KB). Both are very similar but right image has more sharp details.
4.tiff Moderate Correlation and Redundancy
The bike has sharp details but the background is blurred along with large uniform/correlated area in the middle.
High Compression ratio achieved.
5.tiff Very High Redundancy and Correlation
Image is composed of uniform blocks with very little details. The redundant portion are handled well by run length and Huffman encoding. High compression ratio is achieved.
Left image is compressed by my algorithm (25 KB) and right image is saved using Photoshop (20 KB). The left image is sharper and has less artifacts near the edges. Our algorithm achieves good compression for highly redundant images as well.
Effect of blurring of image:
Same as 3.tiff but blurred with Gaussian Blur of radius 3.0. High
correlation is present due to blurring. Compression ratio improves from 11 to
30 on blurring.
Hence, blurring reduces the details and enhances compression abilities.
High compression ratio achieved.
However, some blockiness is
present in the compressed image as seen below.
Overall the JPEG compression algorithm performs very well and gives good results.