18-793 – Image and Video Processing
Due date: Tuesday, 12/12/17 at 6pm EST == 3pm PST.
Fall 2017
Finals
Notes on Problem Set. There are SIX problems. Please answer any FOUR. All problems have the same number of points. If you answer more than four, then we will simply use the top four scoring problems.
Submission instructions. (1) All submissions are via email to Aswin at saswin@andrew.cmu.edu . (2) Please send all your files inside a SINGLE zip file named as “lastname.firstname.zip” (3) If you dont have a scanner handy, there are a number of effective cellphone scanning app that you could use. (4) You are given more than 2 days to solve this problem set. Use the time wisely. You should not need more than 3 hours. And do not miss the submission deadline.
Late submissions. Any submission after 6.00pm EST on 12/12/17 will be penalized at 3% per minute. So, any submission after 6.30pm EST will be given zero credit. I will use the time-stamp on the email as the submission time.
Discussions and exam integrity. No discussions are permitted on this exam. Your work should be entirely your own. Failure to abide by this policy is considered cheating/unauthorized assistance. If you refer to material outside of that on canvas, please cite them. Please read up on CMU policy on academic integrity at this link.
Missing information, bugs etc. We have proof read the problem set multiple times to ensure there are no bugs or missing information. Some details are however left out intentionally and are for you to figure out. So, if you really feel some piece of information is missing and need to make an assumption to solve the problem — please go ahead; there is no need to run it by the instructors. Do not forget to mention the assumption that you needed to make to solve the problem.
In spite of above, if you still have any questions, pl email Aswin. However, any answer, should we decide to reply, will be made public to all students.
Software packages: You are expected to code your own solutions. In particular, you are welcome to reuse any code developed during the semester by you or us — but no software outside of that. Ok to use any inbuilt MATLAB command.
2 Finals Q1 [Image restoration] Restore these images. (Please use the images in Q1.zip)
Deliverable: A restored version of each image — include a separate “png” file for each restored image. A brief paragraph per image on steps taken to achieve the result. You are expected to detail logic/intuition behind denoiser, modeling assumptions, and optimization technique used.
Note #1: Evaluation for your submission will take into account both the quality of the restored images as well as the restoration approaches employed.
Note #2: The noise / corruption present in each image is different. Understanding the right noise model is key to solving this problem accurately. Your submission should detail how you tuned/chose the restoration algorithm to specifics of the corruption.
Note #3: Feel free to restore each image using a different approach.
Finals 3
Q2 [Line detection and radon transform] Devise a scheme using the radon transform to find the exact locations of the 2 lines in this image (use the image in Q2.mat). Deliverable # 1. Explain the steps of your methods and why you choose to do so Deliverable # 2. Estimate and report the parameters (slope and intersept) of the lines.
Well explained methods will receive credits and “I measured it with a ruler” will not score you any points.
Figure 1: Noisy image of 2 lines Hint: You might find the MATLAB function findpeaks helpful.
4 Finals
Q3 [Hyperspectral image denoising] Hyper-spectral (HS) capture both the spatial and spectral variations in a scene. In this problem, we are going to look at using group-sparsity to denoise HS images.
Let xλ be a n × n-image (Let N = n2) corresponding to the spectral band denoted by λ. Each xλ is, like all images, compressible in a wavelet basis. However, in addition to this, we can expect the support to be similar across images corresponding to different wavebands, i.e, we can expect xλi and xλj to have similar support in a wavelet basis.
Suppose now we can a noise HS image such that the noisy measurement yk ∈ RN of the form
yk =xλk +ek.
Clearly, recovering all the spectral channels simultaneously enforcing similar support patterns
should help!
Deliverable #1: Formulate an algorithm for recovering the HS cube given noisy mea- surements that enforces not just individual wavelet sparsity but joint wavelet sparsity.
Q3.mat has a test hyper-spectral cube in the variable HSdata. The first two dimensions correspond to spatial variation and the third dimension correspond to spectral variation. Now, simulate noisy measurements by adding random gaussian noise. If X is the noise free HS image and X is the noisy measurement, then we measure the amount of noise added using the Input SNR (in dB) defined as
∥vec(X)∥ Input SNR(X) = 20log 2 ,
10 ∥vec(X − X)∥2
Finals 5
where vec(·) is vectorizes the HS image. Recover the HS data from these measurements using two recovery algorithms: (1) A Naive recovery that assumes wavelet sparsity on each spectral image but NO joint sparsity model; and (2) the solution to the formulation in deliverable 1 that enforces joint support across spectral bands.
Deliverable #2: Plot reconstruction performance in terms of SNR (in dB) for each algorithm for input noise SNR taking values in {0 dB, 10 dB, 20 dB, 30 dB, 40 db, 50 dB }.
6 Finals Q4 [Compressive recovery] Let X0 be a 64 × 64 pixel natural image. We vectorize X0 to
obtain x0 ∈ R4096.
Given in Q4.mat are measurements y ∈ R2048 and a measurement matrix A of size 2048×4096
such that
This is data from a single pixel camera. We do not know much about the noise n except
that its l2-norm is bounded.
Deliverable: Estimate x0 and describe in detail the procedure adopted to estimate it.
You are expected to provide the reconstructed image as a .png file.
Hint: Once you estimate x0, you can get a 2D image by using the command >> X0 = reshape(x0, 64 64);
y = Ax0 + n.
Finals 7
Q5 [RIP] Let A be an M × N matrix that satisfies RIP of order 2K with constant δ2K , i.e., ∀∥x∥0 ≤2K,(1−δ2K)∥x∥2 ≤∥Ax∥2 ≤(1+δ2K)∥x∥2.
Let a and b be K-sparse vectors with disjoint support, i.e.,
∥a∥0 ≤ K, ∥b∥0 ≤ K, and supp(a) ∩ supp(b) = φ.
Show that
|⟨Aa, Ab⟩| ≤ δ2K . ∥a∥2 ∥b∥2
In simple words, what this suggests is that sparse vectors that are orthogonal remain nearly- orthogonal after the operation of A, provided it satisfies RIP.
8 Finals
Q6 [Computational imaging] Let x[n] be a 1D signal of length 256 pixels and h[n] be a 1D blur kernel of length 11 pixels. We will assume that h[n] ∈ {0, 1}, i.e., h[n] is binary valued.
We obtain measurement y[n] of length 266 (= 256+11-1) of the form
10
y[n] = (x ∗ h)[n] + e[n] = h[k]x[n − k] + e[n], k=0
where ∗ is linear convolution and e[n] is additive white noise with mean zero and variance σ2.
Design a kernel h[n] that is optimal for recovering x[n] from y[n] and justify its optimal- ity/design. Please clearly state the criteria under which your kernel is optimal. (You are welcome to use MATLAB).