/AA_ASSIGNMENT

Primary LanguageJupyter Notebook

Report

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)

  1. (Done) Implement 1-D DFT ,on coefficient vectors of two polynomials A(x), B(x) by multiplication of Vandermonde matrix. ( O(n 2 ) - Complexity)
  2. (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)
  3. (Done) Pointwise multiply results of Step (2) to produce C(x) in P-V form
  4. (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.
  5. (TODO) Implement 1-D Inverse FFT (I-FFT) on C(x), in PV form (Interpolation) to get C(x) in Coefficient form (CR) Polynomial.
  6. (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)
  7. (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 !!)
  8. (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))
  9. (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.)
  10. (Done) Apply 2D I-FFT, on the Quantized Grayscale image and render it to observe Image Quality.

Dataset Generation

  1. 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
  2. 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.
  3. 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
  4. 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 .

Preparatory Readings Links

  1. Fast Fourier Transform. How to implement the Fast Fourier... | by Cory Maklin | Towards Data Science
  2. Understanding the FFT Algorithm | Pythonic Perambulations
  3. Image Transforms - Fourier Transform ( 2-D FFT)
  4. (2) Image Compression and the FFT - YouTube ( Steve Brunton )
  5. (2) Image Compression and the FFT (Examples in Python) - YouTube ( Steve Brunton)
  6. OpenCV: Basic Operations on Image
  7. Unraveling The JPEG
  8. The RSA Homonym
  9. RSA Encryption/Decryption Example - YouTube