Open the following file to view our report : AA_Report_PES1UG19CS032_PES1UG19CS534.pdf
Fast Polynomial Multiplication with DFT/FFT implementation, RSA Encryption, Image compression (20 Marks)
- (Done) Implement 1-D DFT ,on coefficient vectors of two polynomials A(x), B(x) by multiplication of Vandermonde matrix. ( O(n 2 ) - Complexity)
- (Done) Implement 1-D FFT on the same vectors, of A(x) and B(x). Ensure above two steps produce same results. ( O(n logn) – Complexity)
- (Done) Pointwise multiply results of Step (2) to produce C(x) in P-V form
- (TODO) RSA encrypt (128-bit , 256-bit and 512-bit ) , with public key , the C(x) in PV form, for transmission security and decrypt with a private key and verify.
- (TODO) Implement 1-D Inverse FFT (I-FFT) on C(x), in PV form (Interpolation) to get C(x) in Coefficient form (CR) Polynomial.
- (TODO) Verify correctness of C(x) , by comparing with the coefficients generated by a Elementary “Convolution For Loop” on the Coefficients of A(x) and B(x)
- (Done) Implement a 2-D FFT and 2-D I-FFT module using your 1-D version (This just means , applying FFT on the Rows First and Columns Next on M x N matrix of numbers !!)
- (Done) Verify your of Step (7) correctness on a Grayscale matrix ( which has random integer values in the range 0-255; 255 → White & 0 → Black))
- (Done) Apply your 2D-FFT on TIFF/JPG (lossless) Grayscale image and drop Fourier coefficients below some specified magnitude and save the 2D- image to a new file.
- ( relates to % compression – permanent Lossy compression)
- ( by sorting and retaining only coefficients greater than some(quantization) value. Rest are made 0.)
- (Done) Apply 2D I-FFT, on the Quantized Grayscale image and render it to observe Image Quality.
- For 1-D, DFT, FFT and Inverse DFT, Inverse FFT use randomly generated polynomial coefficient vectors for A(x) and B(x) of varying degree-bound sizes namely, n = 4, 8, 16, 32, 64, ... 1024 and 2048
- For 2-D Grayscale image, use randomly generated pixel values in the range 0-255 for testing 2-D FFT and 2-D Inverse FFT.
- For testing on actual image, use a Grayscale TIFF or lossless JPEG image and use the Python OpenCV image manipulation API e.g imread( ) , imshape( ) etc., for accessing the raw pixel data of the 2-D image matrix
- For comparing the Efficiency/Asymptotic complexity of your DFT, FFT, Inverse DFT and Inverse FFT, for increasing values of n, compare with Python Numpy built-in FFT/IFFT functions .
- Fast Fourier Transform. How to implement the Fast Fourier... | by Cory Maklin | Towards Data Science
- Understanding the FFT Algorithm | Pythonic Perambulations
- Image Transforms - Fourier Transform ( 2-D FFT)
- (2) Image Compression and the FFT - YouTube ( Steve Brunton )
- (2) Image Compression and the FFT (Examples in Python) - YouTube ( Steve Brunton)
- OpenCV: Basic Operations on Image
- Unraveling The JPEG
- The RSA Homonym
- RSA Encryption/Decryption Example - YouTube