18-793 – Image and Video Processing
Due date: Tuesday, 12/11/17 at 11pm EST == 8pm PST.
Fall 2018
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. gradescope. (4) You are given more than 3 hours 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 11.00pm EST on 12/11/17 will be penalized at 3% per minute. So, any submission after 11.33pm EST will be given zero credit. I will use the time-stamp on the submission website 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 I 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.
Q1 [Adjoint] In filter banks it is common to have convolutional operator followed immedi- ately by a subsampling/downsampling operator. The overall operation is called convolution with stride.
Let D ≥ 1 be an integer-valued stride parameter. Given a filter k of dimensions L × L, the convolution with stride operator A takes in as input an N D × N D image x and outputs an N × N image y such that
L−1 L−1
y=A(x) =⇒ m,n∈{0,…,N−1},y[m,n]=k[a,b]x[mD−a,nD−b].
a=0 b=0
Assume that the x[m, n] = 0 for values of m, n outside {0, . . . , L − 1}.
Deliverable: Derive an expression for the adjoint operator A∗.
2 Finals
Q2 [Recovering blur kernel] In Q2.mat, there are two variables: imsharp and imblur, which is a blurred version of the former. All we are given is that the size of blur kernel is 15 × 15. Recover the blur kernel.
(left) Sharp image. (right) blurred noisy image
Deliverables: 1) A brief discussion of the strategy for recovering blur kernel. 2) Mathe- matical formulation of the strategy. 3) MATLAB code. 4) Recovered blur kernel visualized using imagesc.
Some notes: 1) Note the sizes of imsharp and imblur. 2) Some measurement noise has been added. The added noise was Gaussian and white.
Q3 (Orthogonal matching pursuit (OMP) (TL;DR) Prove that in OMP the same column is never selected twice.
(Verbose) We discussed the OMP algorithm in class which describes a greedy iterative tech- nique for solving the sparse approximation problem
min∥y−Dx∥ s.t ∥x∥0 ≤K. x
Given a vector y ∈ RM and an M × N dictionary D = [d1,d2,…,dN], the algorithm is initialized with an empty support set Ω = φ and a residue r = y.
In each iteration, the following steps are undertaken.
• Atom selection. Find the atom/column of the dictionary that is closest, in angle, to the current residue, i.e.
k = argmax|⟨dj,y⟩| j
• Update support. This column index is added to the existing support. Ω←Ω∪k
• Least squares on support. Form a new signal estimate is obtained by solving a least squares problem constrained by the current support.
xΩ =argmin∥y−DΩxΩ∥2, x
Finals 3 where DΩ is the matrix made of columns of D indexed by Ω, and xω is the subset of
elements of x indexed by Ω.
• Calculate residue. The residue is given as
r = y − D x
Your goal is to show that if a column index i ∈ Ω, then that column wont be selected in the
firststep,i.e.,i∈Ω =⇒ k̸=i.
Q4 [Fan beam tomography] Fan-beam tomography is an alternate setup, different from the parallel-beam tomographic setup that we studied in class. In a fan-beam tomographic setup, the X-ray source is not collimated and hence, the line-integrals are along lines passing through the location of the source (see Figure 1). In this problem, we will analyze the fan-beam tomographic setup.
↵=à
!
#
DiRamadeituesr of circle: D
”
Source
(%&,(&)
𝛼
𝐷
𝑦
𝜃
(𝒙𝝉,𝒚𝝉)
𝜏
𝑥
𝛾
(𝑥&,𝑦&)
Figure 1: Diagram for fan-beam tomography. As compared to a parallel beam tomography, the lines of integration aren’t parallel, but pass through a point source.
1. Figure 1 shows the setup for our problem. Given an angle θ, the source is located at (xs,ys) as shown in Figure 1. Let α to be the local coordinate on the 1D sensor line. Given a 2D image f, we can now define the fan-beam projector Bθ such that Bθ(f) = bθ, where bθ(α) is the integral along the line joining the source (xs,ys) to the point (xα,yα) defined by α on the sensor.
Deliverable: Derive an expression for bθ(α).
In Q4.mat, you are given fan beam measurements in the variable rad, a vector of angles in radians theta, and the radius D. The code used for simulating the measurements is also given in Q4.m.
x↵,y↵
4 Finals 2. Write a MATLAB for backprojection from fan beam measurements.
Deliverable: Code for backprojection and backprojection result.
Remark. The fan-beam radon transform is simply the collection of projections when we varyθ,i.e.,AF,thefan-beamradontransform,isdefinedasAF ={Bθ,θ∈[−π/2,π/2)}. Similar, let AP be the (parallel-beam) radon transform that we discussed in class.
An interesting observation is that A∗F AF ≈ A∗P AP , and hence the backprojection (BP) of fan beam measurements is identical to the estimate obtained by BP for parallel-beam.
3. Recall that naive back-projection produces overly smooth results. Design a scheme for fan-beam tomography that fixes these overly smooth results. This should be similar in spirit to the filtered BP that we discussed in class for parallel-beam tomography. Deliverable: A strategy for filtered BP from fan-beam tomography measurements
4. Using the strategy above, recover the image corresponding to the fan beam measurements. Deliverable: Code and recovered image.
You are expected to do your own coding for this problem and use inbuilt commands sparingly. The commands radon and iradon are not to be used.
Q5 [Sines and spikes] A classical problem in signal processing is to separate sines and spikes. In Q5.mat, you are given four signals sig1, sig2, sig3 and sig4, each of which is an example of such a signal.
Formulate a strategy for separating the signal for separating the sines and spikes from their sum.
Deliverable: A mathematical formulation along with its justification.
Finals 5
Implement your strategy in MATLAB.
Deliverable: Code
Run your code on the four signals given in Q5.mat.
Deliverable: For each signal, plot the recovered sine and spike components.
Q6 [Multi-image deblurring] In Q6.mat you are given two blurred images, imblur1 and imblur2, and two corresponding blur kernels, k1 and k2. Both images are blurry versions of the same sharp image. Recover the sharp image jointly from the two blurred images. Do compare it to the single image deblurring results where you recover the sharp image from each of the blurred images individually.
Deliverables: 1) A formulation of multi-image deblurring. 2) MATLAB code for imple- menting your formulation. 3) Recovered sharp images from deblurring each image individu- ally. 4) Recovered sharp image from joint deblurring.