Assignment 3 Solution

Your assignment should be handed in electronically on UW Learn. The submission should include one pdf le containing the assignment answers and the cover sheet and all the m- les required to run the code, with no folder structure (not zipped).







Analytic Questions




(10 marks)



(a) Calculate by hand the discrete Fourier transform of f = (1; 2; 3; 2):




(b) Calculate by hand the inverse discrete Fourier transform of F = (4; 1; 0; 1):




(15 marks)



Let fF0; : : : ; FN 1g be the DFT of a sequence ff0; : : : ; fN 1g de ned by




N 1

Fk = N1 X fnW nk




n=0




2 i

with W = e N the Nth root of unity. Show your work and simplify where possible.




(a)
Give a formula for Fk for all k when fn = ( 1)n for n = 0; :::; N 1.
(b)
Suppose (f0; : : : ; fN 1) = (
1; : : : ; 1; 1; : : : ; 1) having the rst half negative one and


remaining half one (with N
even). Show that F2k = 0; k = 0; 1; : : : ;
N
1.


2



( 20 marks)



Consider the sequence of eight numbers f = ( 1; 0; 2; 0; 1; 0; 2; 0 ).




What are the two arrays (g and h, each of length 4) that are used in computing the DFT of f by the FFT method?



Compute G and H, the two DFTs for fgig and fhig, respectively, using the de nition of DFT of 4 values. Simplify if possible.



Using G and H from part b), write out the DFT of the array f.



Using the FFT butter y algorithm, compute by hand the DFT of f.



1



(15 marks) (Edge Sharpening)



A discrete grey scale image is given by a two dimensional array of grey scale values fij de ned on a square grid xj = jh yj = jh where h is the grid spacing. An algorithm for edge enhancement is




f = f@x2
+ @y2 !


@2f


@2f








where is a positive, constant parameter. If F is the two dimensional Discrete Fourier Cosine Transform (DCT) of f then a continuous approximation to the discrete grey scale values is given by

N
1 N 1
2 kx


2 ‘y
kX X














f(x; y) =
Fk;‘ cos(


N
) cos(
N
)):
=0 ‘=0















Apply the edge sharpening algorithm to this continuous approximation.




Edge enhancement is typically viewed as sharpening higher frequencies in an image. If we view the result in terms of the following algorithm




= DCT (f)



F = F ilter F




f = inverseDCT (F )




then interpret the meaning of this lter and explain why it tends to sharpen edges.













Signal Processing (20 marks)



Sound samples of a train whistle are recorded at a rate of 8192 samples per second. The total number of samples is N = 12880, and thus the length of the signal is 1.57 seconds. However, the recording is polluted by the background noise of bird chirps. The signals of the train whistle, bird chirps, and the polluted train whistle are shown below.























































The polluted recording has been obtained simply by superimposing the two signals. As one can see, in the time domain it would be rather di cult to separate the bird chirps from the train whistle in the mixed signal. Your job is to denoise the polluted (noisy) signal by using the discrete Fourier transform. The noisy signal is provided on the website in the le




2




train bird.mat. Use the load command to load the data into your workspace in MATLAB. The le contains the signal, y, and the sampling rate, Fs. Once the data is loaded you can hear the signal by using the command soundsc(y,Fs).







Write a MATLAB script to do the following:




Load the data and plot the input signal.



Compute the DFT of the original signal, and plot the power spectrum. (Hint: use the fft and abs commands.)



Implement a low-pass lter to isolate the train whistle, and a corresponding high-pass lter to isolate the bird chirps. (Hint: study the power spectrum carefully, and use trial and error.)



Plot the denoised signal of the train whistle and its power spectrum.


















A hard copy of your code and the four gures produced by it. Present the plots of the signals and the plots of the spectra side-by-side for comparison. (Hint: use the subplot(2,2) command.)




A brief description of your implementation and the results. In particular: (i) describe what your code does, (ii) identify the frequency threshold you used to lter the signal, and (iii) comment on the similarities and di erences between the noisy and denoised signals.




Image Compression (20 marks)



In this problem, we study the compression of gray-scale images. In Appendix F of the course notes, Images in Matlab, you have the information needed to convert such images into a two-dimensional array. Compression is obtained by dropping relatively small Fourier coe cients on 8 8 pixel subblocks. By this we mean that if ffi;jg are the original pixel values in a given subblock, and fFk;‘g are the corresponding DFT, then we drop any Fk;‘ satisfying




jFk;‘j < Fmax tol:




Here Fmax is the maximum of fjFk;‘jg in each block and tol is our drop tolerance.




The le mountain:jpg, available on the course web site, contains an image to be used in this question.




Compression



Create a MATLAB function, Compress.m, that has the following prototype:




[Y, drop] = Compress(X, tol)




It takes as inputs the original image, X, and the drop tolerance parameter, tol, and outputs a compressed image Y. It also returns the drop ratio, drop, which is de ned to be:

drop ratio = Total number of nonzero Fourier coe cients dropped:




Total number of pixels in the image




3




If drop ratio = 0, then no nonzero Fourier coe cient is dropped; if drop ratio = 1, then all Fourier coe cients are dropped. In general, it should be between 0 and 1.




Your MATLAB function needs to do the following:




Compute the 2D Fourier coe cients (fft2) for every 8 8 subblock.




For each subblock, set those Fourier coe cients having modulus less than the relative tolerance level to 0.




Record the number of coe cients dropped.




Reconstruct the compressed 8 8 image array by using the inverse 2D Fourier trans-form (ifft2). Note: the reconstructed image array must be set to the real part (real) of the inverse transform.




Return the entire compressed image as Y and the drop ratio as drop, after all the 8 8 subblocks for all the components have been processed.




Compression Levels



Determine (by trial and error) four values of tol resulting in drop ratios of 0.1, 0.45,




0.75 and 0.9. Write a MATLAB script, MyScript.m, to do the following:




Execute Compress.m with these sets of tol values.




Display the four compressed images (using subplot and subimage). Indicate the tol value and the resulting drop ratio used for each image.




Plot the normalized mean square error between the original image and the compressed image vs the drop ratio for the compressed image. If Y is the processed image, and X is the original image, the normalized mean square error can be found with the Matlab command:




nms error = sqrt(mean2((Y-X).^ 2)/(mean2(X).^ 2));







Submit the following:




A copy of the functions Compress.m and MyScript.m.



A gure with the 4 plots of the compressed images.



The error vs drop ratio plot of the compressed images.



A brief commentary on your results.






















































4