Image Compression Exercises Instructions: The following problems can be done interactively or by writing the commands in an M-file (or by a combination of the two). In either case, record all MATLAB input commands and output in a text document and edit it according to the instructions of LAB 1 and LAB 2. For problem 2, include a picture of the rank-1 approximation. For problem 3, include a picture of the rank-10 approximation and for problem 4, include a picture of the lower rank approximation that, in your opinion, gives an acceptable approximation to the original picture. Crop and resize the pictures so that they do not take up too much space and paste them into your lab report in the appropriate order. Step 1. Download the file gauss.jpg and save it to your working MATLAB directory. Then load it into MATLAB with the command A = imread('gauss.jpg'); % note the semicolon! The semicolon is necessary so that MATLAB does not print out many screenfuls of data. The result is a matrix of grayscale values corresponding to a black and white picture of a dog. (The matrix has 268583 entries). Now, A is actually 127 x 629 x 3. To create an image from the matrix A, MATLAB uses the three values A(i,j, 1:3) as the RGB values to use to color the pixel in the i-th row and j-th column. - We have a black and white picture so A(:,:,1) A(:,:,2) A(:,:,3) and we only need to work with A(:,:,1). Step 2. We need to do some initial processing. Type B double (A(:,:,1)); % don't forget the semicolon which converts A into the double-precision format that is needed for the singular value decomposition. Now type B B/255; % semicolon! [US V] = svd (B); % semicolon! This decomposition is just Eq. (1). The gray scale goes from 0 to 255 in a black-and-white JPEG image. We divide B by 255 to obtain values between 0 and 1, which is required for MATLAB's image routines, which we will use later. PROBLEM 1. What are the dimensions of U, S, and V? (Find out by typing size (U) without the semicolon - and likewise for the others.) Here S has more columns than rows; infact columns 428 to 629 are all zeros (When A has more columns than rows, we pad S on the right with zero columns to turn S into an mx n matrix). Otherwise, with this modification, the SVD is just like Eq. 1. PROBLEM 2. Compute the best rank-1 approximation to B and store it in the matrix rank1 (Use the commands given in the Example parts (a) and (b) on page 2, but applied to the matrix B, rather than A. Make sure you suppress the output). Step 3. Let's visualize rank1. To do that, first create C = zeros(size (A)); % semicolon! THIS CONTENT IS PROTECTED AND MAY NOT BE SHARED, UPLOADED, SOLD OR DISTRIBUTED 2019 v18 Copyright School of Mathematical and Statistical Sciences, Arizona State University This creates an array of zeros, C, of the same dimension as the original image matrix A. Step 4. Copy the rank-1 image into C as follows: C(:,:,1) rank1; C(:,:,2) rank1; C(:,,3) rank1; Include the code and the figure in your report. Step 5: We are almost done, except for one hitch. MATLAB does all its scaling using values from 0 to 1 (and maps them to values between 0 and 255 for the graphics hardware). Lower-rank approximations to the actual image can have values that are slightly less than 0 and greater than 1. So we will truncate them to fit, as follows: C = max(0,min (1,C)); Step 6. View the resulting image: image (C), axis image % no semicolon PROBLEM 3. Create and view a rank-10 approximation to the original picture (Use Steps 4-6 but with rank10 instead of rank1. If you mess up - for example, you get an all-black picture - then start over from Step 3.) It is convenient to create an M-file with a for loop to evaluate ou₁v+...+10100 Include the code and the figure. PROBLEM 4. Repeat with rank-20, 30 and 40 approximations (and any other ranks that you'd like to experiment with). What is the smallest rank that, in your opinion, gives an acceptable approximation to the original picture? In your lab write-up, include only the code that gives an acceptable approximation and the corresponding picture. PROBLEM 5. What rank-r approximation exactly reproduces the original picture? You only need to answer the question. Do not include the picture. Hint: Think about the original picture. Do not just answer this question by looking at the figures and guessing. PROBLEM 6. (i) Suppose that a rank-k approximation, for some k, gives an acceptable approximation. How much data is needed to represent the rank-k approximation? Your answer should be an expression in terms of k, m and n. Hint: you need k columns of U, k columns of V, and k singular values of S. (ii) The ratio of the amount of data used for the approximation (which you found in part (i)) and the amount of data of the (original format of the) picture is the compression rate. Find the compression rate for the value of the rank you determined in Problem 1. What does the compression rate represent? Hint: After finding the compression rate for the value of the rank you determined in Problem 4, you may want to present this number as a percentage. Think about how this percentage relates to the amount of data of the original approximation. THIS CONTENT IS PROTECTED AND MAY NOT BE SHARED, UPLOADED, SOLD OR DISTRIBUTED 2019 v18 Copyright School of Mathematical and Statistical Sciences, Arizona State University 5 PROBLEM 7. If we use a high rank approximation, then the amount of data needed for the approximation may exceed the amount of data used in the original representation of the picture. Find the smallest value of k such that the rank-k approximation of the matrix uses the same or more amount of data as the original picture. Approximations with ranks higher than this k cannot be used for image compression since they defeat the purpose of using less data than in the original representation. Hint: Use the general compression rate formula you found in Problem 6, part (ii). When you substitute the numbers for m and n, your k value will be a decimal numbers. Since k represents rank, it must be an integer. Think about whether you should round down or up.