18-793 Image and Video Processing
Submission instructions.
Fall 2020
• Submissions are due on Thursday 10/08 at 10.00pm ET
• Please upload scans of your solution in GradeScope (via Canvas)
Homework 5
Instructions
• Please solve all non-MATLAB problems using only paper and pen, without resorting to
a computer.
• Please show all necessary steps to get the final answer. However, there is no need to be overly elaborate. Crisp and complete answers.
• For all MATLAB problems, include all code written to generate solutions.
• Please post all questions on the discussion board on the Piazza course website.
• If you feel some information is missing, you are welcome to make reasonable assumptions and proceed. Sometimes the omissions are intentional. Needless to say, only reasonable assumptions will be accepted.
1. (Regularized least squares revisited) Show that the solution to the following optimization problem
arg min ∥y − Ax∥2 + ∥Gx∥2, x
is
Hint. Check matrix cookbook if you need help with differentiation.
x = (A⊤A + G⊤G)−1A⊤y. 2. We will derive the pseudo-inverse of the 1 × 3 matrix
A=11 1 1. 3
(Part a) Derive basis vectors for C(A),C(A⊤),N(A), and N(A⊤).
(Part b) Noting that A is a full rank underdetermined operator, derive the value of its
pseudoinverse A†
(Part c) The pseudo-inverse derived in Part b can be used for solving the colorization problem, where x is a N × N × 3 (3-color) image and y is its grayscale counterpart. Here, the A operator is defined
y[m, n] = (x[m, n, 1] + x[m, n, 2] + x[m, n, 3])/3.
2 Homework 5
(a) x (a) y
Shown in the figure about is an example of x and y. In HW5.mat you have the variable y. Solve for x = A†y.
Deliverable for part c: Code and x visualized as an image. Explain why x looks so diffeerrentt frrom x.
3. (Image processing with simple regularizers) Inpainting is an image processing problem that involves filling in missing pixels in an image.
Let Ω be a set of pixel values that are missing. That is, given an image x, the measure- ments that we have are as follows:
(Deliverable #1) Derive the adjoint of AΩ. We would like to see an analytical expression like that given above for AΩ.
(Deliverable #2) Implement, in MATLAB, a function for AΩ. You are expected to fill in the missing lines.
function y = AOmega(x, omega)
%…..
%[fillin these lines]
%…..
end
(Deliverable #3) Implement, in MATLAB, a function for the adjoint A∗Ω. You are expected to fill in the missing lines.
y = AΩ(x) such that y[m, n] =
Lets denote the operator that produces the image with missing pixels as AΩ.
0 (m,n)∈Ω x[m, n] otherwise
Homework 5 3
function x = AOmega_adjoint(y, omega)
%…..
%[fillin these lines]
%…..
end
Next, using the cgs command, solve the following optimization problem arg min ∥y − AΩx∥2 + λ∥x∥2,
x
for the three Ω sets given in the hw5.mat file. Choose value of λ appropriately.
Use the cameraman image with 256 × 256 pixels as the source image for the problem.
The following command in matlab should get you this.
img = imread(’cameraman.tif’); img = double(img)/255;
(Deliverable #4) Code and recovered image. Also explain your result briefly as well as value of λ used.
Next, using the cgs command, solve the following optimization problem arg min ∥y − AΩx∥2 + λ∥Dxx∥2 + λ∥Dyx∥2,
x
for the three Ω sets given in the hw5.mat file. Dx and Dy are spatial derivatives along x and y respectively. See Problem 2 for the definition of Dx. Dy is similar, except that the gradient is computed along the rows instead of the columns. Choose value of λ appropriately.
(Deliverable #5) Code and recovered image. Also explain your result briefly as well as value of λ used.
Hints: 1) There are some missing details that you are expected to fill in. You are welcome to go with reasonable guesses.
2) You can use your implementation of AΩ operator to simulate measurements from the camera man image.
Problems below wont be graded. We wont release solutions as well. We are happy to verify yours, if you post on piazza, and discuss them