Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer ScienceDepartment of Mechanical Engineering6.050J/2.110J Information and Entropy Spring 2006Issued: February 14, 2006 Problem Set 3 Due: February 17, 2006Laboratory AssignmentIn 6.050J/2.110J, MATLAB will be used frequently in problem sets and demonstrations. MATLAB is amathematics software package that is efficient at matrix operations as well as a good tool for data visualiza-tion. Access MATLAB on any Athena workstation by typing add matlab at your athena% prompt. Thentype matlab & to enter the program. A separate window will appear, in which you can enter MATLABcommands.Whenever a problem requires MATLAB, write a text file that holds the commands or functions thatyou would normally type into the MATLAB command line. This text file, also known as an M-file, shouldhave a .m extension (e.g., filename.m). This file can be executed in the MATLAB window by typing thefilename without the .m extension. This takes away the drudgery of retyping commands over and over again.Programs like vi, textedit, emacs, and pico can be used to create and edit the M-file on Athena. Moreover,we also request that you type diary (in MATLAB) which keeps track of all your commands and outputsfrom MATLAB. The results are placed in a file called diary. Please create a separate M-file for each problemand e dit the diary for readability.Go through the MATLAB Tutorial (http://www-mtl.mit.edu/Courses/6.050/2006/notes/matlab.pdf)given out in class to familiarize yourself with the syntax and environment. Remember that at any time, youcan type help at the MATLAB prompt (before typing this, type more on to turn on page-by-page viewing).It is our intention that MATLAB be used as a helpful tool in this course, and that it not be a barrier toanyone’s success in the course. We also hope that you’ll develop skill with MATLAB which may be usefulto you in other classes. To that end, we’re here to help you if you run into problems, so feel free to ask usfor assistance. If you have any questions, please email [email protected] 1: Is it Over-Compressed or is it Modern Art?This exercise demonstrates some of the basic ideas behind image compression. You will write your own videoimage compressor in MATLAB!1This will be as simple as possible, so don’t sweat. Write all your MATLABcommands in ps3p1.m. For simplicity the images you will work with in this exercise have no color. Eachpixel is represented by a number: 0 if the pixel is black, 1 if the pixel is white, or a number between 0 and1 for shades of gray. Thus a picture is represented by a matrix (a two-dimensional array) of numbers.Usually pixel values are represente d by a small number of bits, often 8 bits, in which case only a finitenumber of shades can be represented. For the purpose of this exercise you may assume that the shades arerepresented by real numbers, so any shade can be represented.Most modern video compression algorithms use a form of the Discrete Cosine Transformation (DCT).The original image is broken up into blocks, in our case 8 pixels high and 8 pixels wide. For each block,the DCT is applied to the matrix of pixel values. The result is another matrix of the same size, with values1The 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 last few years, and we are trusting you to complete it without consulting lastyear’s solutions. We hope you enjoy it!1Problem Set 3 2(DCT coefficients) that are numbers, not necessarily in the range from 0 to 1. One of these coefficients is(to within a scale factor) the average value of all 64 pixels. Other coefficients describe the variation of shadeacross the block.The DCT is reversible, in the sense that the original image can be calculated exactly from the matrix ofcoefficients. No information is lost, but in turn no compression has occurred because the DCT co e ffic ientsrequire as many bits as the original image. What irreversible compression algorithms such as JPEG do isdiscard small DCT c oefficients, thereby saving on the number of bits needed. When it is time to render theimage, the inverse DCT transformation is applied, and the result, which is not quite the same as the originalimage, is displayed. If the choice of which coefficients to discard is done well, the changes in the image asperceived by the human eye are minimal.In MATLAB, type dctdemo to view a demonstration of the DCT. Click on ”Info” for detailed information.Here’s a brief description of what is going on.1. The original image you choose is divided into 8 x 8 blocks of pixels.2. DCT is applied to each block. The resulting matrix of coefficients has at the upper left the coefficientthat gives the average. Coefficients down and to the right measure how rapidly the pixel values change,i.e., whether the block has pixels with high spacial frequencies. For example, the coefficient at the lowerright is large only if the block had pixels with sort of a checkerboard pattern. If the image is relativelysmooth over the block in question, only a few coefficients toward the upper left will be significant.3. Compression occurs when small values of DCT coefficients are set to zero. You can do this by movingthe horizontal slider to block out certain values and then clicking ”Apply”. MATLAB will render theresulting c ompresse d image.4. The error image shows the res ult of subtracting the original pixel values from the reconstructed values.Play with this demonstration long enough to observe the trade-off between compression (e.g., the per-centage of co e fficie nts discarded) and visual fidelity.a. Start off by loading the vertigo image by typing the following in MATLAB.load imdemos vertigo; % Load vertigo matrix from image demos libraryvertigo=double(vertigo);% 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(vertigo,[0 255]);% Display vertigo in the windowb. 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