18-793 Image and Video Processing
Submission instructions.
Fall 2020
• Submissions are due on Thursday 10/29 at 10.00pm ET
• Please upload scans of your solution in GradeScope (via Canvas)
Homework 7
• Solve any four problems :). Your score will be capped to 10 if you answer more than 4 questions
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. (Time-frequency bandwidth product and scaling) FT
Consider a window function a(t) ←−−→ A(f).
The time bandwidth σt and frequency bandwidth σf are defined as
σt2(a) = t2|a(t)|2dt, σf2(a) = f2|A(f)|2df, Now consider a second window as(t) obtained by scaling a(t) as follows,
respectively.
Show that
1 t s>0, as(t)=√sa s .
σt(as)σf (as) = σt(a)σf (a).
2. (Gaussian and time-frequency bandwidth product) Prove that the Gaussian is the only window for which the time-frequency bandwidth product is equal to it lower bound, i.e., σt2σf2 = 1/16π2.
2 Homework 7 3. (Sparsity and wavelets) We are going to study how sparse images really are under wavelet
transformations.
Collect a set of 16 high-resolution images, each of which is at least 8 or more megapixels. Perform the following operations: (i) Crop each image so that they are “square” (i.e., their width is equal to their height). (ii) Make them grayscale. (iii) Crop the image so that the width/height is a power of 2. Note that it is ok for each image to be of a different size.
Deliverable 1. Printout of the 16 images. Please tile them into one single figure before printing. Commands like subplot and montage might be useful.
Let N0 = 32 and Kfrac = 0.1.
Perform the following operations for each of the images.
• Downsample the image to size N 0 × N 0. Let img be the downsampled image.
• Compute the DWT of level log2(N0), with periodic boundary conditions, and using
the ‘db4’ wavelets. The following two commands achieve this. >> dwtmode(’per’);
>> [s0, cbook] = wavedec2(img, log2(N0), ’db4’);
• Given K = Kfrac*N0*N0, retain the largest K coefficients, in absolute magnitude, in s0
and set the rest to zero. Let shat be thresholded wavelet coefficients.
• Reconstruct the image from the wavelet coefficient. Let imghat be the recovered image.
• Compute the normalized reconstruction error given as
∥img − imghat∥/∥img∥.
We can compute the average normalized reconstruction error by doing the above for
each of the 16 images and averaging the individual errors.
Now, vary N0 to take values {32,64,128,256,512,1024,2048}, computing the average
normalized reconstruction error for each N0.
Deliverable 2. Plot of average normalized reconstruction error as a function of N0.
Explain the implications of your finding in words.
Deliverable 3. Repeat by changing Kfrac = 0.01. As with deliverable 2, we expect a plot of average normalized reconstruction error as a function of N0. Explain the implica- tions of your finding in words.
4. (Properties of CWTs) The Continuous Wavelet Transform (CWT) of a 1D signal i1(t) is given as
W1(τ, s) =
i1(t)ψs,τ (t)dt,
t
Homework 7 3
where
1 t−τ ψs,τ (t) = √s ψ0 s .
Derive expressions for the CWTs for the following signals in terms of W1(τ,s) and other relevant variables.
• i2(t)=i1(t−t0)
• i3(t) = i1(at), where a > 0
5. (Time complexity of DWTs) Discrete wavelets are implemented as a multi-level filter- bank where only the approximation coefficients are repeatedly analyzed at coarser spatial resolutions. Shown below is a three-stage decomposition of a 1D signal x[n].
x[n] is of length N and the filters g[n] and h[n] are both of length L ≪ N. We can assume that that all convolutions are circular.
(Part a) Show that the time-complexity to implement a K-level DWT decomposition is linear in N.
(Part b) Now let L = N. Derive an expression of the time complexity to implement a K-level DWT.
6. Show that the Haar filters, defined by the following four filters, satisfy the criterion for perfect reconstruction.
h [n]=g [n]= 1 (δ[n]+δ[n−1]) a a √2
h [n]=g [n]= 1 (δ[n]−δ[n−1]) d d √2