Brianna Lynn's Project 6

Image Compression

In this project, we studied the Discrete Cosine Transform, which interpolates dta, using basic functions that are all cosine functions, and involves only real computations.Its orthogonality characteristics make least squares approximations simple. The Discrete Cosine Transform (DCT) of x=[x0,x1,...,xn-1]T is the n-dimensional vector y=[y0,y1,...,yn-1]T, where y=Cx, where C is the nxn matrix whose entries are defined by:

Cij = √2/√naicos(i(2j+1)π/2n

for i,j=0,1,...,n-1 where ai=1/√2 if i=0 and ai=1 if i=1,2,...,n-1

Since C is a real orthogonal matrix, C's transpose, CT, is equal to C's inverse, C -1.The rows of an orthogonal matrix pairwise orthogonal unit vectors. We used the two-dimensional Discrete Cosine Transform (2-D DCT), the 2-D DCT of an nxn matrix X is the matrix Y=CXCT. The inverse two-dimensional Discrete Cosine Transform is the nxn matrix Y is the matrix X=CTYC.

We also studied quantization, which allows the effects of low-pass filtering to be achieved in a more selective way. We will retain low-accuracy versions of some coefficients at a lower storage cost. The main idea is to assign fewer bits to store information about the lower right corner of the transform matrix Y, instead of throwing it away. To quantize z modulo q, z=round(y/q). So dequantize y=qz. In this context, "round" means round to the nearest integer. The quantization error is the difference between the input y and the output y after quantizing and dequantizing. The maximum error quantization modulo q is q/2. We used the linear quantization matrix, which is defined by qkl=8p(k+l +1) for 0<k,l<7, where p is called the loss paramter. We used p=1,2, and 4. We did Computer Problems 11.2.3-11.2.6 in our textbook

Step 1

Using an image of my pug, Hammond, imported into Matlab, and cropped into pixel dimensions of multiples of 8 and put into grayscale, I used the 2-D DCT and linear quantization to interpolate the photo data.

Using an extracted 8x8 pixel block:

Step1 Code

We applied the 2-D DCT and then linear quantization with p=1,2,4:

Original Using 2-D DCT Using linear quantization: p=1 Using linear quantization: p=2 Using linear quantization: p=4
YQ=
12 4 -1 1 0 0 0 0
5 1 0 0 0 0 0 0
0 -2 -2 0 0 0 0 0
-1 -2 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0		 YQ=
6 2 0 0 0 0 0 0
2 1 0 0 0 0 0 0
0 -1 -1 0 0 0 0 0
-1 -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		 YQ=
3 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
0 0 0 0 0 0 0 0

It is clear that using 2-D DCT works and linear quantzation works well as long as p is small. Once p=4, the image gets distorted as the pixels can be seen.

Using the whole photo:

Step 1 (whole photo) Code

We applied the 2-D DCT and then linear quantization with p=1,2,4:

Using linear quantization with p=1,2,4:

Original Using 2-D DCT Using linear quantization: p=1 Using linear quantization: p=2 Using linear quantization: p=4

It is clear that using 2-D DCT works and that linear quantzation works well as long as p is small. Once p=4, the image gets distorted as the pixels can be seen.

Step 2

Using the same image but quantizing it with a JPEG-suggested Q, and using p=1, the image look liked this:

Original New Image Matrix Q
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

It seems that linear quantization works better using the JPEG-suggested Q than the Q used before (defined in the intro).

Step 3

Using the color version of the image of my pug, I carried out the same steps separately for each color using Step3 Code: red, green, and blue. The pictures below are the separate images of ren, green, and blue using linear quantization with p=1 and p=2.

red green blue

Recombing as a color image gives using linear quantization with p=1 and p=4:

Original Using linear quantization: p=1 Using linear quantization: p=4

As you can see above, the colors came out well and when p=1, the image looks pretty good. But as p is increased, the image looks more pixelated.

Step 4

Lastly, I used the same colored image of my dog and transformed the RGB (red green blue) values to luminance /color difference coordinates, using Step4 Code. This is often referred as the Baseline JPEG. We let the lumance, Y=.299R + .587G +.114B, where R, G, and B are the red, green, and blue parts of the image. The color differences are U=B-Y and V=R-Y. I then carried out the same steps for each part Y,U, and V separately then recombined them, using Bnew=Unew+Ynew, Rnew=Vnew+Ynew, and Gnew=(Ynew-.299Rnew-.114Bnew)/.587, as a color image.

Original Using the Y matrix Using the U matrix Using the V matrix

As you can see, the Y matrix carries most of the image information while the U and V matrices just provide more detail.

Recombing as a color image gives using linear quantization with p=1 and p=4:

Original Using linear quantization: p=1 Using linear quantization: p=4

As you can clearly see, the color does not show up very well, at least the image is not blurry.

Brianna's Projects

Brianna's Homepage