18-793 – Image and Video Processing
Name:
Andrew ID:
Fall 2019
Finals
Problem
Score
Max
1
5
2
5
3
5
4
5
5
5
6
5
7
5
8
5
Total
40
• Precision and thoroughness are both appreciated. Reaching the correct answer with- out the appropriate justification or incorrect reasoning will be penalized.
• We have proof-read the problem set multiple times to ensure there are no bugs. Some details are however left out intentionally and are for you to figure out. So, if you really think 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 made for solving the problem. Needless to say, unreasonable assumptions are, by definition, unreasonable.
2
Finals
1. Suppose that image f(x,y) has radon transform r(α,θ).
Given a > 0, find the radon transform of f(x, y). aa
Finals 3 2. Consider the image inpainting problem where we are given the following input-output
equation:
y[m, n] = x[m, n]a[m, n],
where a[m, n] = 1 when (m, n) ∈ Ω and zero otherwise. The set Ω is known. Hence,
given Ω, the image formation model above is linear.
Let x[m, n] be the pseudoinverse solution. Show that x[m, n] = y[m, n].
4
Finals
3. Let A be an N × N orthonormal matrix, i.e., A⊤A = AA⊤ = IN, where IN is the N-dimensional identity matrix.
Given positive integer K and y ∈ RN , find the solution (as a closed form expression) to
min ∥y − Ax∥2 s.t. ∥x∥0 ≤ K. x
Finals 5
4. You are given the radon transform of an image. Derive an analytical expression for the image. It is ok if the values in your expression are approximate.
-150
-100
-50
0
50
100
150
1.5
1
0.5
0
0 20 40 60 80 100 120 140 160 theta in [degrees]
alpha
6
5.
Finals
A corrupted image is given below. Devise a strategy for restoring it.
You are given the following information (that you can also readily observe from the image). 1) A small number of squares have been added to the image intensities. 2) Each square is 10 pixels wide. Locations are unknown and need to be automatically estimated.
Your answer is expected to contain the following three components:
a) A mathematical formulation that links the unknown sharp image to the observed corrupted image,
b) An optimization-based formulation for the solution. Specifically, we want to see something of the form min······, and
c) A brief description on how you would solve the optimization in (b).
Finals 7
6. We will study a different approach to derive DCT-II in this problem.
Let x[n], n = 0, . . . , N − 1 be a N-length signal and let d[k] be its DCT-II coefficients.
Lets construct a new signal y[n], of length 2N such that
x[n] 0 ≤ n < N y[n] =
x[2N−1−n] N≤n<2N
Let Y [k] be the 2N-length DFT of y[n], given as Y [k] = 2N−1 y[n]e−j2πkn/(2N).
(Part a) Relate Y [k] to d[k].
(Part b) Derive expressions to invert the DCT-II coefficients using Y [k] as an interme- diary.
n=0
8
7.
Finals
Let f(x) be given as
−x x≤0
f(x) =
0 x>0
(Part a) Sketch f(x)
(Part b) Is f(x) differentiable? Justify.
(Part c) Derive the sub-differential of f(x).
(Part d) Derive an expression for the proximal operator:
minβf(x)+ 1(y−x)2. x2
(Part e) What does this proximal operator become as lim β → ∞?
Finals 9 8. Let A be an M × N matrix with unit-norm columns ai.
Let x0 ∈ RN be some 1-sparse signal. Suppose we obtain linear measurements y = Ax0
where A is an M × N matrix.
(Part a) What property must A satisfy so that OMP recovers x0 from y ? Now, lets assume that we obtain noisy linear measurements of the form
z = Ax0 + n
We only know that the noise is bounded in energy and specifically,
∥n∥ ≤ ε.
(Part b) Derive a sufficient property on A (in terms of all relevant variables) such that OMP recovers the support of x0 correctly ?
10 Finals
Finals 11
12 Finals