## Description

1. In this part, we will apply the PCA technique for the task of image denoising. Consider the images barbara256.png

and stream.png present in the corresponding data/ subfolder – this image has gray-levels in the range from

0 to 255.

For the latter image, you should extract the top-left portion of size 256 by 256. Add zero mean

Gaussian noise of σ = 20 to one of these images using the MATLAB code im1 = im + randn(size(im))*20.

Note that this noise is image-independent.

(If during the course of your implementation, your program takes

too long, you can instead work with the file barbara256-part.png which has size 128 by 128 instead of 256 by

256.

You can likewise extract the top-left 128 by 128 part of the stream.png image. You will not be penalized

for working on these image parts.)

(a) In the first part, you will divide the entire noisy image ‘im1’ into overlapping patches of size 7 by 7, and

create a matrix P of size 49 × N where N is the total number of image patches. Each column of P

is a single patch reshaped to form a vector. Compute eigenvectors of the matrix PPT

, and the eigencoefficients of each noisy patch.

Let us denote the j

th eigen-coefficient of the i

th (noisy) patch (i.e. Pi)

by αij . Define ¯α

2

j = max(0,

1

N

[

PN

i=1 α

2

ij ] − σ

2

), which is basically an estimate of the average squared

eigen-coefficients of the ‘original (clean) patches’.

Now, your task is to manipulate the noisy coefficients

{αij} using the following rule, which is along the lines of the Wiener filter update that we studied in class:

α

denoised

ij =

αij

1 + σ2

α¯

2

j

.

Here, α

denoised

ij stands for the j

th eigencoefficient of the i

th denoised patch. Note that

σ

2

α¯

2

j

is an estimate of the ISNR, which we absolutely need for any practical implementation of a Wiener

filter update.

After updating the coefficients by the Wiener filter rule, you should reconstruct the denoised

patches and re-assemble them to produce the final denoised image which we will call ‘im2’. Since you chose

overlapping patches, there will be multiple values that appear at any pixel.

You take care of this situation

using simple averaging. Write a function myPCADenoising1.m to implement this. Display the final image

‘im2’ in your report and state its RMSE computed as ∥im2denoised − im2orig∥2

∥im2orig∥2

.

(b) In the second part, you will modify this technique. Given any patch Pi

in the noisy image, you should

collect K = 200 most similar patches (in a mean-squared error sense) from within a 31 × 31 neighborhood

centered at the top left corner of Pi

.

We will call this set of similar patches as Qi (this set will of course

include Pi). Build an eigen-space given Qi and denoise the eigen-coefficients corresponding to only Pi

using the Wiener update mentioned earlier. The only change will be that ¯α

j will now be defined using only

the patches from Qi (as opposed to patches from all over the image).

Reconstruct the denoised version of

Pi

. Repeat this for every patch from the noisy image (i.e. create a fresh eigen-space each time). At any

pixel, there will be multiple values due to overlapping patches – simply average them. Write a function

myPCADenoising2.m to implement this. Reconstruct the final denoised image, display it in your report

and state the RMSE value. Do so for both barbara as well as stream.

(c) Now run your bilateral filter code from Homework 2 on the noisy version of the barbara image. Compare

the denoised result with the result of the previous two steps for both images. What differences do you

observe? What are the differences between this PCA based approach and the bilateral filter?

(d) Consider that a student clamps the values in the noisy image‘im1’ to the [0,255] range, and then denoises

it using the aforementioned PCA-based filtering technique which assumes Gaussian noise. Is this approach

correct? Why (not)? [10 + 20 + 5 + 5 = 40 points]

2. Read Section 1 of the paper ‘An FFT-Based Technique for Translation, Rotation, and Scale-Invariant Image

Registration’ published in the IEEE Transactions on Image Processing in August 1996. A copy of this paper is

available in the homework folder.

(a) Describe the procedure in the paper to determine translation between two given images. What is the time

complexity of this procedure to predict translation if the images were of size N × N? How does it compare

with the time complexity of pixel-wise image comparison procedure for predicting the translation?

(b) Also, briefly explain the approach for correcting for rotation between two images, as proposed in this paper

in Section II. Write down an equation or two to illustrate your point.

[10+10=20 points]

3. Consider a matrix A of size m × n, m ≤ n. Define P = AT A and Q = AAT

. (Note: all matrices, vectors and

scalars involved in this question are real-valued).

(a) Prove that for any vector y with appropriate number of elements, we have y

tP y ≥ 0. Similarly show

that z

tQz ≥ 0 for a vector z with appropriate number of elements. Why are the eigenvalues of P and Q

non-negative?

(b) If u is an eigenvector of P with eigenvalue λ, show that Au is an eigenvector of Q with eigenvalue λ. If v

is an eigenvector of Q with eigenvalue µ, show that AT v is an eigenvector of P with eigenvalue µ. What

will be the number of elements in u and v?

(c) If vi

is an eigenvector of Q and we define ui ≜

AT vi

∥AT vi∥2

. Then prove that there will exist some real,

non-negative γi such that Aui = γivi

.

(d) It can be shown that u

T

i uj = 0 for i ̸= j and likewise v

T

i vj = 0 for i ̸= j for correspondingly distinct

eigenvalues. (You did this in HW4 where you showed that the eigenvectors of symmetric matrices are

orthonormal.)

Now, define U = [v1|v2|v3|…|vm] and V = [u1|u2|u3|…|um]. Now show that A = UΓV

T

where Γ is a diagonal matrix containing the non-negative values γ1, γ2, …, γm. With this, you have just

established the existence of the singular value decomposition of any matrix A.

This is a key result in linear

algebra and it is widely used in image processing, computer vision, computer graphics, statistics, machine

learning, numerical analysis, natural language processing and data mining. [7.5 + 7.5 + 7.5 + 7.5 = 30

points]

4. Suppose you are standing in a well-illuminated room with a large window, and you take a picture of the scene

outside.

The window undesirably acts as a semi-reflecting surface, and hence the picture will contain a reflection

of the scene inside the room, besides the scene outside. While solutions exist for separating the two components

from a single picture, here you will look at a simpler-to-solve version of this problem where you would take two

pictures.

The first picture g1 is taken by adjusting your camera lens so that the scene outside (f1) is in focus

(we will assume that the scene outside has negligible depth variation when compared to the distance from the

camera, and so it makes sense to say that the entire scene outside is in focus), and the reflection off the window

surface (f2) will now be defocussed or blurred.

This can be written as g1 = f1 + h2 ∗ f2 where h2 stands for

the blur kernel that acted on f2. The second picture g2 is taken by focusing the camera onto the surface of the

window, with the scene outside being defocussed.

This can be written as g2 = h1 ∗ f1 + f2 where h1 is the blur

kernel acting on f1. Given g1 and g2, and assuming h1 and h2 are known, your task is to derive a formula to

determine f1 and f2.

Note that we are making the simplifying assumption that there was no relative motion

between the camera and the scene outside while the two pictures were being acquired, and that there were no

changes whatsoever to the scene outside or inside. Even with all these assumptions, you will notice something

inherently problematic about the formula you will derive. What is it? [5+5 = 10 points]