Starting from:
$30
CS475- Homework 3 Solved
For this assignment, note that parts 1 , 2 , and 3 are optional, and are meant to help building a better understanding of the material and studying for the exams. Parts 4 and 5 are worth 15% and 85%, respectively. Make sure to include the code for your functions in your write-up!
Linear independence and basis
1a Consider the vectors u = [1 1]T and v = [3 −1]T. What is the result of the expression αu + βv if α = 2 and β = 1.5? Is this a linear combination? Why or why not?
b Find the scalars α0 and β0 that make the following expression true: α0u+β0v = [4 8]T.
c Express the equation above in matrix form and compute α0 and β0 using MATLAB/Python. Hint: this involves creating a matrix from u and v and computing its inverse.
d Now consider the following 2 vectors in R3: x = [1 1 − 1]T and y = [1 − 1 − 1]T.
Are they independent? Why?
e Find scalars α and β such that αx + βy = [1 0 2]T. Do x and y form a basis for R3? Why or why not?
f Consider the following 3 vectors: x = [1 0 0]T, y = [1 − 1 − 1]T and z = [0 3 − 1]T Are they orthogonal to each other? Do they form a basis for R3? Why?
g Consider the column vectors in the 3 × 3 identity matrix. Do they form a basis for R3? Is this an orthogonal basis? Why? Express the vector [2 1 7]T as a linear combination of these column vectors — by which scalars do we need to multiply each of them?
h Now consider the vectors u = [1 1]T and v = [1 − 1]T. Do they form a basis for R2? If yes, can you make it into an orthonormal basis?
i Consider the vector x = [−1 3]T (which basis is it in, by the way?). Find the scalar coefficients α and β needed to express x in terms of the orthonormal basis from h . Hint: you can find the coefficients in the form of a vector [α β]T using the same approach as in c !
Intro to Fourier series
2a Compute y1 = sin(t) using MATLAB/Python and make a plot of the values in y1. Note that, in order to see the sinusoidal curve, t must be an array, t. It should contain a range of values so as to include one complete period, i.e., [0,2π] (using linspace is a good idea). Choose a small step size between each value in t so that the curve appears relatively smooth (if you’re using linspace, that is equivalent to choosing a large number of points – at least 1000 for best results).
b Using the same t as above, compute y2 = sin(2t) and plot it on top of y1[1]. Now compute the result of sum(y.*y2) (or np.sum(y*y2) in Python). Using a new figure, repeat this procedure for y1 and y3 = sin(3t). What do you notice about the results?
c What is the dot product between y1 and y2? Can we say sin(t) is orthogonal to sin(2t)? Can y1 and y2 be seen as functions of t? Can they be seen as vectors? Explain. Repeat the experiment using each of the following two pairs: y2 and y3; y1 and cos(t).
Comment briefly on the results. d Using the same t as above, plot the function w = 3cos(5t)+7cos(15t)+1.2cos(30t).
e Compute the dot product between w and the following vectors: y1, y2, and y3 (from above), as well as y5 = cos(5t), y−5 = cos(−5t), y15 = cos(15t), y−15 = cos(−15t), y30 = cos(30t), and y−30 = cos(−30t). Always divide your results by n, the length of your vector t. What do you observe?
f If you created a “basis” formed by the vectors above (y1,y2,y3,y−5,y5,y−15,y15,y−30,y30),
what would be the scalar coefficients needed to express w in terms of that basis?
g Now, compute the discrete Fourier transform of your signal w using the function fft; use fftshift[2] to translate the zero-frequency to the middle of the spectrum, followed by abs/np.abs to compute the magnitude of the complex values obtained—you can do all of this using a single line of code: W = abs(fftshift(fft(w))). Now make sure to divide W by n (the length of your t vector) and plot it against its corresponding frequency values, f—this is the vector containing the range of values -n/2:n/2-1 (in Python, this range is equivalent to np.arange(-n/2,n/2)), i.e., the maximum frequency will be half of the sampling rate of your discrete signal (does the name Nyquist come to mind??).
Execute plot(f,W) and either zoom in or set xlim(-50,50) to have a better look at the peaks in your plot[3]: what do they represent? How do their frequency and magnitude values relate to the equation for w? How does this relate to what you did in f ? Finally, what would you expect to happen to your frequency plot if we changed the coefficients 3, 7, and 1.2 in the equation for w to different values? What if we changed the frequencies 5, 15, and 30 to different values?
h Now increase the number of periods in t to at least four (if T is the number of periods you choose, your new range for the values in t should be [0,2πT]). Let w = sawtooth(t, 0.5)4 (a triangular wave) and examine its plot: what can you say about this function? How is it different from the sum of sinusoidals you investigated above? Is it still periodic?
Continuous? Smooth?
Compute its discrete Fourier transform and compare it with what you got above. In particular, what can you say about the frequency distribution? Note: this time, to the get correct frequency values, you must divide the frequency scale by number of periods chosen above
(T).
i Finally, repeat this procedure for w = sawtooth(t) (a sawtooth wave). What is different now? Is it still periodic? Continuous? Smooth? What do you notice about its frequency spectrum?
Computing discrete convolution
3a Inside the following boxes are the impulse responses of a few linear systems. Manually (on paper!) compute the output of each system given its input signal (left column). Assume the grids below represents integers centered at (0,0). Apply your computations only to the integer points, i.e. a discrete convolution. Check your answers against the results returned by running conv/np.convolve on MATLAB/Python, but first make sure you understand the difference between the three possible modes of convolution: 'full','same', and 'valid'.
Ask us if you don’t know how.
b Now you will compute 2-D discrete convolution. On the left is a 2-D input array, and on the right the impulse response (“kernel”) of a linear system. The gray square represents the center (origin) of the kernel. Compute the (full) 2-D convolution between the two (pad with 0s as necessary) and check your result against running conv2/scipy.signal.convolve2d. (Hint: here, because the signals are two-dimensional, you need to flip them both vertically and horizontally before sliding!)
Fourier Transform and convolution with images
In this problem set, we will examine filters and their Fourier transforms. In class, we discussed an expansion of functions into a basis of sines and cosines. Recall from class that one could take the dot product of two functions f and g as follows:
Z hf,gi = f(x)g(x)dx.
Therefore, we can think of expanding a function into sines and cosines much like expanding a vector onto an orthogonal basis. Let fˆsin(ω) = R f(x)sin(ωx)dx be the sine expansion of the function f and fˆcos(ω) = R f(x)cos(ωx)dx be the cosine expansion, where ω is the angular frequency. Then, using Euler’s formula (eiθ = cosθ + isinθ), the Fourier transform of the function f is: Z
fˆ(ω) = fˆcos(ω) + ifˆsin(ω) = f(x)e−iωx dx
(the negative sign in the exponent is simply a convention!).
4a* Prove that ) where f∗g is convolution. In other words, that the
Fourier transform of a convolution is the product of the Fourier transforms of the functions.
Feel free to do this on paper and attach it to your write-up.
5a* Write a function that creates a Gaussian blur filter (flesh out the code in blurfilter.m/py).
Your function should create a matrix M (called filt in the code), where
.
Use the matrices xs and ys provided in blurfilter (e.g., xs(i,j) contains the xij component that should be used in the expression above)[4]. Normalize the sum of the entries to one by dividing by the sum of the entries. Why is this last step desired?
b* Using fft2, compute the 2-dimensional Fourier transform of a filter created using your function from a with σ = 1, and display the absolute value of the transform (abs function) using surf(···, ‘EdgeColor’, ‘none’) (plot surface in Python). What (familiar function) does the Fourier transform of this filter look like? (Hint: Use fftshift to properly center your transformed image in the ωx and ωy directions.)
The appearance of the filter transform can be improved by adding padding to your FFT by using fft2(filter, pady, padx) (in Python, fft2(filter, (pady,padx))) where pady and padx are larger than your filter’s vertical and horizontal dimensions, respectively.
c* Load the Paolina image (remember to convert it to double precision numbers in the range [0,1]!). Filter Paolina (convolve using mode 'same') with a blur filter having σ = 3 and display the result. Compare this with computing the inverse Fourier transform (ifft2) of the pointwise product between the Fourier transforms of Paolina and your filter (compute the transforms of the filter and the image, separately, then compute the inverse transform of the product of the two transforms). Be sure to pad the fft2 of Paolina and the fft2 of your filter to the same size (larger than the image—ideally, equal to Sp + Sf - 1 along each axis, where Sp and Sf are the sizes of Paolina and the filter along each axis, respectively.
How does this relate with what you showed in 4a ?
d* Using your function from a , build a 13x13 Difference of Gaussians filter, with σ1 = 1 and σ2 = 2. In other words, build a 13×13 matrix containing the pointwise difference of two Gaussian filters, the first having σ-parameter σ1 and the second having σ-parameter σ2, with σ2 σ1 . Normalize this filter so that the sum of its entries is zero, by subtracting the mean of the entries of this matrix. Apply this filter to Loki.tiff and Steve.tiff, displaying the result using imagesc/plt.imshow with a gray colormap. How does this filter affect features in the image?
e* Compute the 2-dimensional Fourier transform of this filter and display it. Why is this considered to be a band-pass filter? (Note: Once again you should use fftshift to shift the
Fourier-transformed image.)
f* Flesh out the code in unsharpmask.m to create a function that performs unsharp
masking on an input image. Unsharp masking an image consists of three steps:
1. Blurring the image;
2. Subtracting the blurred image from the original image to create the “mask”;
3. Scaling the mask by some amount and adding it back to the original image.
Use the function to perform unsharp masking on Paolina.tiff with the parameters sigma = 1 and amount = 1 (although feel free to experiment!). Compare the filtered images to the original images (this time, use imagesc(···,[0 1]) or plt.imshow(···, vmin=0, vmax=1) in Python). Describe what the unsharp mask filter appears to be doing to the image.
[1] in MATLAB, use the hold on command after plotting y
[2] in Python, both functions can be imported from the numpy.fft submodule.
[3] you can also play with xticks to customize the frequency values shown along the x-axis in your plot. 4in Python, import the sawtooth function from scipy.signal.
[4] note that this means you can use the power of elementwise operations to compute all Mij entries in a single line of code using xs and ys directly!
Linear independence and basis
1a Consider the vectors u = [1 1]T and v = [3 −1]T. What is the result of the expression αu + βv if α = 2 and β = 1.5? Is this a linear combination? Why or why not?
b Find the scalars α0 and β0 that make the following expression true: α0u+β0v = [4 8]T.
c Express the equation above in matrix form and compute α0 and β0 using MATLAB/Python. Hint: this involves creating a matrix from u and v and computing its inverse.
d Now consider the following 2 vectors in R3: x = [1 1 − 1]T and y = [1 − 1 − 1]T.
Are they independent? Why?
e Find scalars α and β such that αx + βy = [1 0 2]T. Do x and y form a basis for R3? Why or why not?
f Consider the following 3 vectors: x = [1 0 0]T, y = [1 − 1 − 1]T and z = [0 3 − 1]T Are they orthogonal to each other? Do they form a basis for R3? Why?
g Consider the column vectors in the 3 × 3 identity matrix. Do they form a basis for R3? Is this an orthogonal basis? Why? Express the vector [2 1 7]T as a linear combination of these column vectors — by which scalars do we need to multiply each of them?
h Now consider the vectors u = [1 1]T and v = [1 − 1]T. Do they form a basis for R2? If yes, can you make it into an orthonormal basis?
i Consider the vector x = [−1 3]T (which basis is it in, by the way?). Find the scalar coefficients α and β needed to express x in terms of the orthonormal basis from h . Hint: you can find the coefficients in the form of a vector [α β]T using the same approach as in c !
Intro to Fourier series
2a Compute y1 = sin(t) using MATLAB/Python and make a plot of the values in y1. Note that, in order to see the sinusoidal curve, t must be an array, t. It should contain a range of values so as to include one complete period, i.e., [0,2π] (using linspace is a good idea). Choose a small step size between each value in t so that the curve appears relatively smooth (if you’re using linspace, that is equivalent to choosing a large number of points – at least 1000 for best results).
b Using the same t as above, compute y2 = sin(2t) and plot it on top of y1[1]. Now compute the result of sum(y.*y2) (or np.sum(y*y2) in Python). Using a new figure, repeat this procedure for y1 and y3 = sin(3t). What do you notice about the results?
c What is the dot product between y1 and y2? Can we say sin(t) is orthogonal to sin(2t)? Can y1 and y2 be seen as functions of t? Can they be seen as vectors? Explain. Repeat the experiment using each of the following two pairs: y2 and y3; y1 and cos(t).
Comment briefly on the results. d Using the same t as above, plot the function w = 3cos(5t)+7cos(15t)+1.2cos(30t).
e Compute the dot product between w and the following vectors: y1, y2, and y3 (from above), as well as y5 = cos(5t), y−5 = cos(−5t), y15 = cos(15t), y−15 = cos(−15t), y30 = cos(30t), and y−30 = cos(−30t). Always divide your results by n, the length of your vector t. What do you observe?
f If you created a “basis” formed by the vectors above (y1,y2,y3,y−5,y5,y−15,y15,y−30,y30),
what would be the scalar coefficients needed to express w in terms of that basis?
g Now, compute the discrete Fourier transform of your signal w using the function fft; use fftshift[2] to translate the zero-frequency to the middle of the spectrum, followed by abs/np.abs to compute the magnitude of the complex values obtained—you can do all of this using a single line of code: W = abs(fftshift(fft(w))). Now make sure to divide W by n (the length of your t vector) and plot it against its corresponding frequency values, f—this is the vector containing the range of values -n/2:n/2-1 (in Python, this range is equivalent to np.arange(-n/2,n/2)), i.e., the maximum frequency will be half of the sampling rate of your discrete signal (does the name Nyquist come to mind??).
Execute plot(f,W) and either zoom in or set xlim(-50,50) to have a better look at the peaks in your plot[3]: what do they represent? How do their frequency and magnitude values relate to the equation for w? How does this relate to what you did in f ? Finally, what would you expect to happen to your frequency plot if we changed the coefficients 3, 7, and 1.2 in the equation for w to different values? What if we changed the frequencies 5, 15, and 30 to different values?
h Now increase the number of periods in t to at least four (if T is the number of periods you choose, your new range for the values in t should be [0,2πT]). Let w = sawtooth(t, 0.5)4 (a triangular wave) and examine its plot: what can you say about this function? How is it different from the sum of sinusoidals you investigated above? Is it still periodic?
Continuous? Smooth?
Compute its discrete Fourier transform and compare it with what you got above. In particular, what can you say about the frequency distribution? Note: this time, to the get correct frequency values, you must divide the frequency scale by number of periods chosen above
(T).
i Finally, repeat this procedure for w = sawtooth(t) (a sawtooth wave). What is different now? Is it still periodic? Continuous? Smooth? What do you notice about its frequency spectrum?
Computing discrete convolution
3a Inside the following boxes are the impulse responses of a few linear systems. Manually (on paper!) compute the output of each system given its input signal (left column). Assume the grids below represents integers centered at (0,0). Apply your computations only to the integer points, i.e. a discrete convolution. Check your answers against the results returned by running conv/np.convolve on MATLAB/Python, but first make sure you understand the difference between the three possible modes of convolution: 'full','same', and 'valid'.
Ask us if you don’t know how.
b Now you will compute 2-D discrete convolution. On the left is a 2-D input array, and on the right the impulse response (“kernel”) of a linear system. The gray square represents the center (origin) of the kernel. Compute the (full) 2-D convolution between the two (pad with 0s as necessary) and check your result against running conv2/scipy.signal.convolve2d. (Hint: here, because the signals are two-dimensional, you need to flip them both vertically and horizontally before sliding!)
Fourier Transform and convolution with images
In this problem set, we will examine filters and their Fourier transforms. In class, we discussed an expansion of functions into a basis of sines and cosines. Recall from class that one could take the dot product of two functions f and g as follows:
Z hf,gi = f(x)g(x)dx.
Therefore, we can think of expanding a function into sines and cosines much like expanding a vector onto an orthogonal basis. Let fˆsin(ω) = R f(x)sin(ωx)dx be the sine expansion of the function f and fˆcos(ω) = R f(x)cos(ωx)dx be the cosine expansion, where ω is the angular frequency. Then, using Euler’s formula (eiθ = cosθ + isinθ), the Fourier transform of the function f is: Z
fˆ(ω) = fˆcos(ω) + ifˆsin(ω) = f(x)e−iωx dx
(the negative sign in the exponent is simply a convention!).
4a* Prove that ) where f∗g is convolution. In other words, that the
Fourier transform of a convolution is the product of the Fourier transforms of the functions.
Feel free to do this on paper and attach it to your write-up.
5a* Write a function that creates a Gaussian blur filter (flesh out the code in blurfilter.m/py).
Your function should create a matrix M (called filt in the code), where
.
Use the matrices xs and ys provided in blurfilter (e.g., xs(i,j) contains the xij component that should be used in the expression above)[4]. Normalize the sum of the entries to one by dividing by the sum of the entries. Why is this last step desired?
b* Using fft2, compute the 2-dimensional Fourier transform of a filter created using your function from a with σ = 1, and display the absolute value of the transform (abs function) using surf(···, ‘EdgeColor’, ‘none’) (plot surface in Python). What (familiar function) does the Fourier transform of this filter look like? (Hint: Use fftshift to properly center your transformed image in the ωx and ωy directions.)
The appearance of the filter transform can be improved by adding padding to your FFT by using fft2(filter, pady, padx) (in Python, fft2(filter, (pady,padx))) where pady and padx are larger than your filter’s vertical and horizontal dimensions, respectively.
c* Load the Paolina image (remember to convert it to double precision numbers in the range [0,1]!). Filter Paolina (convolve using mode 'same') with a blur filter having σ = 3 and display the result. Compare this with computing the inverse Fourier transform (ifft2) of the pointwise product between the Fourier transforms of Paolina and your filter (compute the transforms of the filter and the image, separately, then compute the inverse transform of the product of the two transforms). Be sure to pad the fft2 of Paolina and the fft2 of your filter to the same size (larger than the image—ideally, equal to Sp + Sf - 1 along each axis, where Sp and Sf are the sizes of Paolina and the filter along each axis, respectively.
How does this relate with what you showed in 4a ?
d* Using your function from a , build a 13x13 Difference of Gaussians filter, with σ1 = 1 and σ2 = 2. In other words, build a 13×13 matrix containing the pointwise difference of two Gaussian filters, the first having σ-parameter σ1 and the second having σ-parameter σ2, with σ2 σ1 . Normalize this filter so that the sum of its entries is zero, by subtracting the mean of the entries of this matrix. Apply this filter to Loki.tiff and Steve.tiff, displaying the result using imagesc/plt.imshow with a gray colormap. How does this filter affect features in the image?
e* Compute the 2-dimensional Fourier transform of this filter and display it. Why is this considered to be a band-pass filter? (Note: Once again you should use fftshift to shift the
Fourier-transformed image.)
f* Flesh out the code in unsharpmask.m to create a function that performs unsharp
masking on an input image. Unsharp masking an image consists of three steps:
1. Blurring the image;
2. Subtracting the blurred image from the original image to create the “mask”;
3. Scaling the mask by some amount and adding it back to the original image.
Use the function to perform unsharp masking on Paolina.tiff with the parameters sigma = 1 and amount = 1 (although feel free to experiment!). Compare the filtered images to the original images (this time, use imagesc(···,[0 1]) or plt.imshow(···, vmin=0, vmax=1) in Python). Describe what the unsharp mask filter appears to be doing to the image.
[1] in MATLAB, use the hold on command after plotting y
[2] in Python, both functions can be imported from the numpy.fft submodule.
[3] you can also play with xticks to customize the frequency values shown along the x-axis in your plot. 4in Python, import the sawtooth function from scipy.signal.
[4] note that this means you can use the power of elementwise operations to compute all Mij entries in a single line of code using xs and ys directly!
1 file (3.0MB)
