Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer ScienceDepartment of Mechanical Engineering6.050J/2.110J Information and Entropy Spring 2003Issued: February 7, 2003 Problem Set 2 Due: February 21, 2003Calendar note: This assignment is due two Fridays from lecture since the compression unit is two weekslong.Laboratory ExperimentThis exercise shows you the basis behind compression of images. Most video compression codecs today usea form of the Discrete Cosine Transform (DCT) in their core. The DCT separates an image into its spatialfrequency components in the x and y directions. For example, a solid color image will have a DCT with lowfrequencies while a line drawing image will have a DCT with very high frequencies. The transform of animage has the same number of coefficients as the image, i.e. an 8 × 8 image will have an 8 × 8 DCT. Thetransform is reversible, in the sense that the original image can be recovered, exactly, from its DCT.In MATLAB, type dctdemo to view a demonstration of the DCT. The following is an explanation ofwhat is happening. Clicking on “Info” will give you a little more information.1. The original image is divided into 8 × 8 blocks of pixels.2. DCT is applied to each block, resulting in an 8 × 8 block of DCT coefficients. The values in the upperleft of each block hold the amount of low x and y frequencies and the values in the lower right theamount of high x and y frequencies.3. Compression occurs when small values of the DCT coefficients are set to zero. This can be seen bymoving the horizontal slider to block out certain values and clicking “Apply”.4. The dropped (small) values are set to zero, and the inverse DCT used to produce an approximation ofthe original image.The error image is the subtraction of the original pixel values from the reconstructed pixel values. Whenwe try to compare the quality of a lossy compression algorithm, such as this one, qualitative analysis is toosubjective. Therefore, various numerical formulas have been developed to assign a quantitative value to thequality of the compressed image. In this demo, the mean squared error is used for this purpose.Problem 1: Is it Over-Compressed or is it Modern Art?Write your own video image compressor in MATLAB! This will be as simple as possible, so don’t sweat.Write all your MATLAB commands in ps2p1.m.a. Start off by loading the flower image by typing the following in MATLAB .load imdemos flower; % Load flower matrix from image demos libraryflower = double(flower);% Convert the matrix to double precisioncolormap(’gray’); % Grayscale for any pictures you want to display% (This creates a blank window that we’ll use soon)imshow(flower,[0 255]); % Display flower in the window1b. Perform a 2D DCT operation on 8 × 8 blocks of the image matrix. You might find the com-mands blkproc and dct2 useful. Use the first form of blkproc explained in its help page (helpblkproc), where FUN is ‘dct2’ (put single quotes around dct2). To keep help information fromscrolling off the screen, type more on at the MATLAB prompt.c. Set to z ero all coefficients with absolute value less than 10. An example to do this can be foundin the help of dct2. We will later want to vary this cutoff value and count the number of non-zerovalues. After this step, many codecs apply run length and variable length encoding to transmitor store the image efficiently for later use.d. Perform a 2D Inverse DCT operation on each of the 8 × 8 blocks of the image matrix. The valuesof the resulting matrix will be in floating point, but you should round the elements to the nearestinteger since image pixel values are integers. Use the blkproc and idct2 commands similarly tothe way you performed the forwards DCT in Part b. Then use the round command to completethe reconstruction of the image.e. Determine the mean squared error between the original and reconstructed image. The definitionof mean squared error to use is mean2((x - y).∧2). Values will appear larger than in the demobecause our error definition does no normalization. The answer you should receive is 10.6891.Note that you can see your new image with the imshow command the same way you displayedthe original image. If you want a new window for the image, so it doesn’t just paint over theprevious one, type figure at the MATLAB prompt.Now compose a graph, having along the x-axis the number of non-zero values of the matrix after thecutoff procedure (before you did the inverse DCT), and the mean squared error (after you did the inverseDCT and rounding) on the y-axis. The number of non-zero values is the number of bytes required to storethe image (ignoring overhead), s o smaller means more compression. Range the cutoff value from 0 to 100 inincrements of 4. The use of nnz and plot will do the trick. It will be easiest to use them if you create avector with the numbers of non-zero values and another vector with the mean squared errors.Write in ps2diary the largest byte size for which you can detect the difference between the original imageand the reconstructed image by eye. Include any c omme nts in the diary file. Be sure the script in ps2p1.mis executable in MATLAB.Problem 2: Compression is Fun and EasyNow you can get your hands dirty with the LZW (Lemp e l-Ziv-Welch) compression algorithm.1Although thisproblem will not require the use of MATLAB, you may use it if you wish. A good reference to the LZW algo-rithm is http://www.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html. There are many deriva-tives of LZW that are more powerful, but we’ll stay with what was explained in lecture and in the weblink.a. Use the 7 bit ASCII table that can be found in Chapter 2 of the notes, handed out at the firstlecture, for your basic alphabet. Notice that the ASCII table ends at HEX 7F (Hexadecimal isBase 16 using A - F for values 11 - 15, so HEX 7F is 127). Your dictionary will therefore rangefrom HEX 80 through HEX FF. Encode the following message in HEX using the LZW technique:peter piper picked a peck of pickled peppers1The 2.110/6.050 staff would like to thank Joe Huang, the Spring 2000 class TA, for developing th e image compressionexercise used in this assignment. It is, in our opinion, really cool because it truly links what we discuss in class to the realworld; once you’ve completed it, you will understand and have experience with the way JPEG images are created. For thisreason, the problem has not changed much since