Assignment 5 Solution

Remember the honor code while submitting this (and every other) assignment. You may discuss broad ideas with other students or ask me for any di culties, but the code you implement and the answers you write must be your own. We will adopt a zero-tolerance policy against any violation.

Submission instructions: Follow the instructions for the submission format and the naming convention of your les from the submission guidelines le in the homework folder. Please see assignment5 DFT.rar. Upload the le on moodle before 11:55 pm on 13th November. Only one student per group needs to upload the assignment. We will not penalize submission of the les till 1 pm on 16th November. No late assignments will be accepted after this time. Please preserve a copy of all your work until the end of the semester.


    1. 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-re ecting surface, and hence the picture will contain a re ection 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 rst 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 re ection o 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? [8+7 = 15 points]

    2. Consider a 1D image (for example, a single row from a 2D image). You know that given such an image, computing its gradients is trivial. An inquisitive student frames this as a convolution problem to yield g = h f where g is the gradient image (in 1D), h is the convolution kernel to represent the gradient operation, and f is the original 1D image. The student tries to develop a method to determine f given g and h. What are the fundamental di culties he/she will face in this task? Justify your answer. You may assume appropriate boundary conditions. Now consider that you are given the gradients of a 2D image in the X and Y directions, and you wish to determine the original image. What are the di culties you will face in this task? Justify your answer. Again, you may assume appropriate boundary conditions. [10+10 = 20 points]

    3. Consider the image with the low frequency noise pattern shared in the homework folder in the form of a .mat le. Your task is to (a) write MATLAB code to display the log magnitude of its Fourier transform, (b) to determine the frequency of the noise pattern by observing the log magnitude of the Fourier transform and guessing the interfering frequencies, and (c) to design and implement (in MATLAB) an ideal notch lter to remove the interference(s) and display the restored image. To this end, you may use the t2, i t2, tshift and i tshift routines in MATLAB. [15 points]

    4. Consider the barbara256.png image from the homework folder. Implement the following in MATLAB: (a) an ideal low pass lter with cuto frequency D 2 f40; 80g, (b) a Gaussian low pass lter with 2 f40; 80g. Show the e ect of these on the image, and display all images in your report. Display the frequency response (in log

1

Fourier format) of all lters in your report as well. Comment on the di erences in the outputs. Make sure you perform appropriate zero-padding! [20 points]

    5. 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. Implement the technique in Equation 3 of the paper to align two images which are related to each other by a 2D in-plane translation. Test your implementation on images I and J as follows. I is a 300 300 image containing a 50 70 white rectangle (intensity 255) whose top-left corner lies at pixel (50; 50). All other pixels of I have intensity 0. The image J is obtained from a translation of I by values (tx = 30; ty = 70). Verify carefully that the predicted translation agrees with the ground truth translation values. Repeat the exercise if I and J were treated with iid Gaussian noise with mean 0 and standard deviation 20. In both cases, display the logarithm of the Fourier magnitude of the cross-power spectrum in Equation 3 of the paper. 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?

Also, brie y 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. [8+7=15 points]



0
0
1
0
1


0
1
1
1
1

6. Consider two di erent Laplacian  lter kernels k1
=

1
4
1

and k2
=

1
8
1

. Write down the


@
0
1
0
A


@
1
1
1
A

formulae for their N; N-point Discrete Fourier Transforms in the report. Compute their N; N-point Discrete Fourier Transforms in MATLAB with N = 201, i.e. where the spatial and frequency indices range from -100 to 100 in both canonical directions. Display the magnitude of the DFT on a log scale using the imshow and surf functions in MATLAB along with a colorbar. Besides the plots, include the code snippet for the DFT computation and display in the report. Comment on the di erence in the Fourier transforms of the two kernels. [10+5=15 points]







































2