[SOLVED] (csc420) assignment 1 part i: theoretical problems (60 marks) [question 1] convolution (10 marks)

[1.a] (5 marks) Calculate and plot the convolution of x[n] and h[n] specified below:
x[n] = (
1 −3 ≤ n ≤ 3
0 otherwise
h[n] = (
1 −2 ≤ n ≤ 2
0 otherwise
(1)
[1.b] (5 marks) Calculate and plot the convolution of x[n] and h[n] specified below:
x[n] = (
1 −3 ≤ n ≤ 3
0 otherwise
h[n] = (
2 − |x| −2 ≤ n ≤ 2
0 otherwise
(2)We define a system as something that takes an input signal, e.g. x(n), and produces an
output signal, e.g. y(n). Linear Time-Invariant (LTI) systems are a class of systems that
are both linear and time-invariant. In linear systems, the output for a linear combination of
inputs is equal to the linear combination of individual responses to those inputs. In other
words, for a system T, signals x1(n) and x2(n), and scalars a1 and a2, system T is linear if
and only if:
T[a1x1(n) + a2x2(n)] = a1T[x1(n)] + a2T[x2(n)]Also, a system is time-invariant if a shift in its input merely shifts the output; i.e. If T[x(n)] =
y(n), system T is time-invariant if and only if:
T[x(n − n0)] = y(n − n0)[2.a] (5 marks) Consider a discrete linear time-invariant system T with discrete input signal
x(n) and impulse response h(n). Recall that the impulse response of a discrete system
is defined as the output of the system when the input is an impulse function δ(n), i.e.
T[δ(n)] = h(n), where:
δ(n) = (
1, if n = 0,
0, else.
Prove that T[x(n)] = h(n) ∗ x(n), where ∗ denotes convolution operation.
Hint: represent signal x(n) as a function of δ(n).[2.b] (5 marks) Is Gaussian blurring linear? Is it time-invariant? Make sure to include your
justifications.
[2.c] (5 marks) Is time reversal, i.e. T[x(n)] = x(−n), linear? Is it time-invariant? Make
sure to include your justifications.Vectors can be used to represent polynomials. For example, 3rd-degree polynomial (a3x
3 +
a2x
2 + a1x + a0) can by represented by vector [a3, a2, a1, a0].
If u and v are vectors of polynomial coefficients, prove that convolving them is equivalent to
multiplying the two polynomials they each represent.
Hint: You need to assume proper zero-padding to support the full-size convolution.The Laplace operator is a second-order differential operator in the “n”-dimensional Euclidean
space, defined as the divergence (∇.) of the gradient (∇f). Thus if f is a twice-differentiable
real-valued function, then the Laplacian of f is defined by:
∆f = ∇2
f = ∇ · ∇f =
Xn
i=1
∂
2
f
∂x2
i
where the latter notations derive from formally writing:
∇ =

∂
∂x1
, . . . ,
∂
∂xn

.Now, consider a 2D image I(x, y) and its Laplacian, given by ∆I = Ixx+Iyy. Here the second
partial derivatives are taken with respect to the directions of the variables x, y associated
with the image grid for convenience. Show that the Laplacian is in fact rotation invariant.In other words, show that ∆I = Irr + Ir
′r
′, where r and r
′ are any two orthogonal directions.Hint: Start by using polar coordinates to describe a chosen location (x, y). Then use the
chain rule.Using the sample code provided in Tutorial 2, examine the sensitivity of the Canny edge
detector to Gaussian noise. To do so, take an image of your choice, and add i.i.d Gaussian
noise to each pixel. Analyze the performance of the edge detector as a function of noise variance. Include your observations and three sample outputs (corresponding to low, medium,
and high noise variances) in the report.In this question, the goal is to implement a rudimentary edge detection process that uses a
derivative of Gaussian, through a series of steps. For each step (excluding step 1) you are
supposed to test your implementation on the provided image, and also on one image of your
own choice. Include the results in your report.Step I – Gaussian Blurring (10 marks): Implement a function that returns a 2D Gaussian matrix for input size and scale σ. Please note that you should not use any of the
existing libraries to create the filter, e.g. cv2.getGaussianKernel(). Moreover, visualize this2D Gaussian matrix for two choices of σ with appropriate filter sizes. For the visualization,
you may consider a 2D image with a colormap, or a 3D graph. Make sure to include the
color bar or axis values.Step II – Gradient Magnitude (10 marks): In the lectures, we discussed how partial
derivatives of an image are computed. We know that the edges in an image are from the
sudden changes of intensity and one way to capture that sudden change is to calculate the
gradient magnitude at each pixel. The edge strength or gradient magnitude is defined as:
g(x, y) = |∇f(x, y)| =
q
g
2
x + g
2
y
where gx and gy are the gradients of image f(x, y) along x and y-axis direction respectively.Using the Sobel operator, gx and gy can be computed as:
gx =


−1 0 1
−2 0 2
−1 0 1

 ∗ f(x, y) and gy =


−1 −2 −1
0 0 0
1 2 1

 ∗ f(x, y)Implement a function that receives an image f(x, y) as input and returns its gradient g(x, y)
magnitude as output using the Sobel operator. You are supposed to implement the convolution required for this task from scratch, without using any existing libraries.Step III – Threshold Algorithm (20 marks): After finding the image gradient, the
next step is to automatically find a threshold value so that edges can be determined. One
algorithm to automatically determine image-dependent threshold is as follows:
1. Let the initial threshold τ0 be equal to the average intensity of gradient image g(x, y),
as defined below:
τ0 =
Ph
j=1
Pw
i=1 g(i, j)
h × w
where h and w are the height and width of the image under consideration.2. Set iteration index i = 0, and categorize the pixels into two classes, where the lower
class consists of the pixels whose gradient magnitudes are less than τ0, and the upper
class contains the rest of the pixels.3. Compute the average gradient magnitudes mL and mH of lower and upper classes,
respectively.4. Set iteration i = i + 1 and update threshold value as:
τi =
mL + mH
25. Repeat steps 2 to 4 until |τi − τi−1| ≤ ϵ is satisfied, where ϵ → 0; take τi as final
threshold and denote it by τ .
Once the final threshold is obtained, each pixel of gradient image g(x, y) is compared
with τ . The pixels with a gradient higher than τ are considered as edge point and
is represented as white pixel; otherwise, it is designated as black. The edge-mapped
image E(x, y), thus obtained is:
E(x, y) = (
255, if g(x, y) ≥ τ
0, otherwise
Implement the aforementioned threshold algorithm. The input to this algorithm is the gradient image g(x, y) obtained from step II, and the output is a black and white edge-mapped
image E(x, y).Step IV – Test (10 marks): Use the image provided along with this assignment, and also
one image of your choice to test all the previous steps (I to III) and to visualize your results
in the report. Convert the images to grayscale first.Please note that the input to each step
is the output of the previous step. In a brief paragraph, discuss how the algorithm works for
these two examples and highlight its strengths and/or its weaknesses.