Instructions

Documentation:

.  The assignment documentation consists of two parts, this  .pdf ile and an associated  .ipynb notebook.

.  This ile contains background information and all of the assignment questions.

.  The notebook contains some sample code and provides a template within which you  can complete the code required for the assignment.

.  Any additional iles required for the assignment will be available via Moodle.

While Python is encouraged, you may use Python or MATLAB to complete the assignment. If you use MATLAB, it will be your  responsibility to appropriately translate the skeleton code given  in Python to MATLAB for use.

Submission information:

.  Please submit your assignment via  Moodle by the due date listed in Moodle.

.  Please submit:

– One  .pdf ile with your answers to the questions.

– One code ile (either  .ipynb or  .m) with the code you have written for the assignment

Marking:

.  The assignment will be marked out of 100 and contributes 15% to your inal mark for the unit

.  The contribution of diferent questions to the total assignment mark is indicated next to each question.

.  The weight assigned to tasks may not always relect their diiculty.

.  Coding tasks will be marked based on a combination of clarity of the code and the approach you took to solve the problem.

.  Questions that involve mathematics or explanations of your reasoning will be marked based on a combination of correctness of answers (if there are single correct answers) and clear logical reasoning demonstrating your understanding of relevant concepts.

.  Tasks marked ‘C’ require you to write code in your code submission.

.  Tasks marked ‘Q’ require you to give a written answer in your  .pdf submission.  (For some of these tasks you may wish to write additional code to aid your answer.  Doing so is optional.)

1.2    Exactly interpolating the measurements  (20 marks)

If the noise level is very small, it may be appropriate to compute an estimate x that exactly agrees with the downsampled signal and minimises a criterion that encourages the reconstructed signal x to be smooth, i.e.,

where D is the matrix you found in C1.

Q4  (4 marks) Explain how to apply a change of variables to (2) so that it can be reformulated as

In particular, explain how the variable w is related to the variable x, and how the matrix A and the vector b can be formed from the data vector y and the matrices C and D from C1.

C6  (4 marks) Using appropriate numerical methods, construct and solve (3) for w, and then solve the original problem (2) for x.

Q5  (4 marks)  Explain why you chose the methods you did in C6.

C7  (4 marks) Plot the original signal z, the noisy downsampled signal y, and the solution of (2) on the same set of axes.

Q6  (4  marks) Explain how you can obtain the solution of  (2) by taking an appropriate limiting value of    in (1).  Which method (solving (2) or solving (1) with a limiting value of    ) would you recommend? Why?

2 Part 2:  illing in missing pixels in an image

Consider an m     n greyscale image,  represented via an m     n matrix X with each entry taking values between 0 (black) and 1 (white). Consider a situation where a collection of pixels are missing or occluded.  One context where this can arise is if there are objects covering parts of the image. Here we will focus on situations where the pixels are missing at random.

In this part of the assignment we will look at some simple methods of inpainting, where we try to ill in the part of the image that has been lost when pixel values are missing.

In part 1 we used smoothness as additional information to help reconstruct a signal from partial measurements, here we will focus on using the fact that many natural images are approximately low rank to help with image reconstruction.

In the accompanying notebook, you are given code that:

.  Loads an image, converts it to greyscale, and converts it to an array X.

.  Generates a boolean array indicating which pixels are measured (with value True) and occluded (with value False).

.  Generates  an occluded version of the  image where the occluded  pixels are set to zero, and stores it in an array Y.

Before running the code, you will need to download the ile ece3093assignmentpic.png from Moodle and upload it into your Google drive.  Then the notebook can load the image from your drive. You may need to modify the path in the code given so that it points to where you choose to save this image.  If you would like to experiment with other images apart from this one, feel free to do so!

We will make use of logical indexing for numpy arrays in some parts of the assignment.  You may need to learn the basics of how this works if you haven’t come across it before.

2.1    Building a chequerboard image  (10 marks)

In this section, you will write code to build a 500 pixel by 500 pixel image where each pixel is either black (value 0) or white (value 1) and where the black and white pixels form a chequerboard pattern, consisting of a 10     10 grid with each square alternating between being a 50 pixel by 50 pixel black square or a 50 pixel by 50 pixel white square.

C8  (3 marks) Write code to form the chequerboard image described above and store it in an array Xch. Also form the occluded image Ych.

Q7  (3  marks)  What  is  the  rank  of  the  matrix  Xch  you  have  constructed  that  represents  the chequerboard? What are its singular values?

Q8  (4 marks)  If the chequerboard were a pa     qa pixel image made up of a p     q grid consisting of a-pixel by a-pixel alternating black and white squares, what would be the singular values of the matrix associated with this general chequerbaord image?  Explain your answer.

2.2    Inpainting by low rank approximation  (10 marks)

In this section, you implement a very simple (and not very efective) inpainting method.  You will take the occluded version of an image, stored in the matrix Y , and ind a best rank r approximation. In other words, you will solve