Assignment Questions

LSI System

Show that a smoothing filter with a 1/3 [1 1 1] filter kernel is an LSI system.

For a system to be an LSI system, it must be:

Linear: op(A+B)=op(A)+op(B) Shift-Invariant: If g(x)=w*f(x), then w*f(x-x0)=g(x-x0)

• Proving Linearity: Let A=[1 2 3 4], B=[4 5 6 7] op=averaging using 1/3[1 1 1] (f)

  f*(A) = $[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}][0\,1\,2\,3\,4\,0]$=[1 2 3 $\frac{7}{3}$] (Note that we use 0 padding on either side) f*(B) = $[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}][0\,4\,5\,6\,7\,0]$=[3 5 6 $\frac{13}{3}$] f*(A+B) = $[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}][0\,5\,7\,9\,11\,0]$=[4 7 9 $\frac{20}{3}$]

  Clearly, f*(A+B)=f(A)+f(B). Therefore, it is linear.

  (In other words, an average of the averages of sets of numbers will be the same as the average of the entire set. So, averaging is linear).

• Proving shift-invariance: Let f(x)=[0 a b 0] Here, w=$[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}]$

  g(x) = $[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}][0\,0\,a\,b\,0\,0]$ = $[\frac{a}{3}\,\frac{(a+b)}{3}\, \frac{(a+b)}{3}\,\frac{b}{3}]$ (f(x) was again padded with 0s)

  Now, let x$_0$=-1 So, f(x-x$_0$) = f(x+1) = [a b 0 0] (when we +, we shift left and then replace empty elements by 0s)

  Therefore, w*f(x-x$_0$) = w*f(x+1) =$[\frac{1}{3} \,\frac{1}{3} \,\frac{1}{3}][0\,a\,b\,0\,0\,0]$ (padded) = [$\frac{(a+b)}{3}\, \frac{(a+b)}{3}\,\frac{b}{3}\,0$] Also, g(x-x$_0$) = g(x+1) = [$\frac{(a+b)}{3}\, \frac{(a+b)}{3}\,\frac{b}{3}\,0$]

  Clearly, w*f(x-x$_0$) = g(x-x$_0$). This proves shift-invariance.

Therefore, smoothing using the given filter is an LSI system.

Apply a median filter with a 3-neighborhood. Is it an LSI system? Discuss.

Consider 1D arrays A=[1 2 3 4] and B=[2 5 1 7].

Checking for linearity:

Here, op is the 3-neighborhood median filtering.

op(A) = median filtering of [0 1 2 3 4 0] (padded) = [median(0,1,2) median(1,2,3) median(2,3,4) median(3,4,0)] = [1 2 3 3] op(B) = median filtering of [0 2 5 1 7 0] (padded) = [median(0,2,5) median(2,5,1) median(5,1,7) median(1,7,0)] = [2 2 5 1]

op(A+B) = median filtering of [0 3 7 4 11 0] = [median(0,3,7) median(3,7,4) median(7,4,11) median(4,11,0)] = [3 4 7 4]

Clearly op(A+B) != op(A)+op(B). Therefore, median filtering is not linear. (This happens because the median of a joint set of values is, in general, not the median of individual sets of the pixel values).

Since it is not linear, it cannot be an LSI system.

1D Convolution

Convolve a [1,1,1] filter with a [0,0,0,1,1,1,0,0,0] signal and plot/graph the result.

Before convolving with the filter, the signal plot is:

Convolution:

[1 1 1]*[0 0 0 0 1 1 1 0 0 0 0] (padded) = [(1*0+1*0+1*0) (1*0+1*0+1*0) (1*0+1*0+1*1) (1*0+1*1+1*1) (1*1+1*1+1*1) (1*1+1*1+1*0) (1*1+1*0+1*0) (1*0+1*0+1*0) (1*0+1*0+1*0)] = [0 0 1 2 3 2 1 0 0]

Signal Plot after convolving:

Box Filtering and Median Filtering

Consider the images of a bar, point and edge. Perform filtering using a 3x3 box filter and 3x3 median filtering and discuss the results.

(The images are 3x3 and have been padded as shown. Dark regions are 1s.)

Image	After 3x3 Box Filtering	After 3x3 Median Filtering
Bar
Point
Edge

Box filtering blurs the bar, point and edge. (Images become unsharp)

Median filtering eliminates the bar and point, but preserves the edge. (This shows that the median filter removes small, thin structures but preserves step edge structures)

Linearity in Canny Edge Detection

In Canny Edge detection, we use linearity to compute the first derivative of the Gaussian. Which of the following implementations would you choose w.r.t. number of operations and efficiency?

I would choose the second operations in each case.

Reason: In the first option, we have to compute the partial derivatives of the Gaussian and then convolve the result with the image. This would involve 2 convolution operations (one with each partial derivative). In the second option, we only convolve once (notice that the terms inside the bracket are the same) and since the Gaussian is separable, it can be implemented efficiently. Computing the partial derivatives of the convolved result is also a simple task.