<jupyter_start><jupyter_text>Question 7 Fourier Transform<jupyter_code>import cv2
import numpy as np
import matplotlib.pyplot as plt
import math
import time
%matplotlib inline
#Load image
cer = cv2.imread("images/ceramic.jpg",0)
plt.imshow(cer,cmap='gray')
print(cer)
actualFFT = np.fft.fft2(cer)<jupyter_output><empty_output><jupyter_text>Part 1 ![image.png](attachment:d25ff181-dd60-4499-9925-8fb9b5865900.png)<jupyter_code>def DFT2D(a):
    aDFT = np.zeros((a.shape[0],a.shape[1]),dtype='complex64')
    rO = a.shape[0]
    cO = a.shape[1]
    for l in range(rO):
        for m in range(cO):
            for j in range(rO):
                for k in range(rO):
                    val = -2j*math.pi*((l*j)/rO+(k*m)/cO)
                    aDFT[l,m] = np.exp(val)
    return aDFT.astype('complex64')<jupyter_output><empty_output><jupyter_text>Part 2 ![image.png](assets/FFT1D.png)<jupyter_code>def FFT1D(a):
    if a.shape[0]==1:
        return a
    a_odd = a[1::2]
    a_even = a[::2]
    F_odd = FFT1D(a_odd)
    F_even = FFT1D(a_even)
    aFFT = np.zeros(a.shape[0],dtype='complex64')
    out = np.zeros(a.shape[0]//2,dtype='complex64')
    R = np.arange(a.shape[0]//2)
    out = np.exp(-2j*np.pi*R/a.shape[0])
#     out_odd = out*F_odd
#     print(aFFT[:a.shape[0]//2].shape)
#     print(np.array(F_even + out*F_odd).shape)
    aFFT[:a.shape[0]//2] = F_even + out*F_odd
    aFFT[a.shape[0]//2:] = F_even - out*F_odd
    return aFFT.astype('complex64')
def FFT2D(a):
    if a.shape[0]==1:
        return a
    flag1 = abs(np.log2(a.shape[0]) - int(np.log2(a.shape[0])))
    flag2 = abs(np.log2(a.shape[1]) - int(np.log2(a.shape[1])))
    #Row Case
    if flag1!=0:
        #Add zeros
        r_zero = np.zeros((int(2**(np.ceil(np.log2(a.shape[0]))))-a.shape[0],a.shape[1]))
        a = np.append(a,r_zero,axis=0)
    #Col Case
    if flag2!=0:
        #Add zeros
        c_zero = np.zeros((a.shape[0],int(2**(np.ceil(np.log2(a.shape[1]))))-a.shape[1]))
        a = np.append(a,c_zero,axis=1)
    
    out = np.zeros_like(a,dtype='complex64')
    #Row-Wise
    for i in range(a.shape[0]):
        out[i] = FFT1D(a[i])
    #Col-Wise
    for i in range(out.shape[1]):
        out[:,i] = FFT1D(out[:,i])

    return out
k_val = [1,2,3,4,5,6,7]
upgrade = np.zeros((7))
noob = np.zeros((7))
for k in range(len(k_val)):
    kk = k_val[k]
    cerI = cv2.resize(cer, (2**kk,2**kk), interpolation = cv2.INTER_AREA)
    initial = time.time()
    out = FFT2D(cerI)
    upgrade[k] += time.time() - initial 
    
    initial = time.time()
    out = DFT2D(cerI)
    noob[k] += time.time() - initial 
#Zoomed-in version
plt.rcParams["figure.figsize"] = (15,15)
plt.plot(k_val,noob,'b-.')
plt.plot(k_val,upgrade,'g-')
plt.legend(['Inefficient','Efficient'])
plt.show()
out = FFT2D(cer)
fig, axs = plt.subplots(1, 2, figsize=(15,15))
axs[0].imshow(np.log(1 + np.abs(np.fft.fftshift(actualFFT))), cmap='gray')
axs[0].title.set_text("Obtained from inbuilt numpy function")
axs[1].imshow(np.log(1 + np.abs(np.fft.fftshift(out))), cmap='gray')
axs[1].title.set_text('Obtained from self-made function',)<jupyter_output><empty_output><jupyter_text>Part 3 ![image.png](assets/InvFFT1D.png)<jupyter_code>def InvFFT1D(x):
    s1 = x.copy()
    #Psedo-reverse 1 to N-1
    s1[1:] = s1[:0:-1]
    InvFFT1D = FFT1D(s1)/s1.shape[0]
    return InvFFT1D

A = np.array([2,4,5,2,6])
print(A[1:])
print(A[:0:-1])
A[1:] = A[:0:-1]
print(A)
def InvFFT2D(a):
    if a.shape[0]==1:
        return a
    out = np.zeros_like(a,dtype='complex64')
    #Row-Wise
    for i in range(a.shape[0]):
        out[i] = InvFFT1D(a[i])
    #Col-Wise
    for i in range(out.shape[1]):
        out[:,i] = InvFFT1D(out[:,i])
    Inv2D = np.real(out)
    return Inv2D
reGain = InvFFT2D(out)
reGain = reGain[:cer.shape[0],:cer.shape[1]]
plt.imshow(np.rint(reGain),cmap='gray')
plt.title("Regained Output from doing inverse fourier transform")<jupyter_output><empty_output><jupyter_text>On doing inverse fourier transform, we get the same input image  Part 4<jupyter_code>preFlip = FFT2D(out)
preFlip = preFlip[preFlip.shape[0]-cer.shape[0]:,preFlip.shape[1]-cer.shape[1]:]
plt.imshow(np.abs(preFlip),cmap='gray')
plt.title("FFT of FFT of Image")<jupyter_output><empty_output><jupyter_text>We have obtained a flipped version of the input image. To solve this we actually reverse flip it in the frequency domain then do the FFT.<jupyter_code>flipIt = np.flip(out, axis=(0, 1))
z = FFT2D(flipIt)
z = z[:cer.shape[0],:cer.shape[1]]
plt.imshow(np.abs(z),cmap='gray')
plt.title('FFT of FFT of Original Image after flipping')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19024814976055726, 'fraction_numerical': 0.04114061819764911, 'mean_word_length': 3.717659137577002, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '319096', 'license': 'MIT', 'n_tokens_mistral': 2108, 'n_tokens_neox': 2031, 'n_words': 327, 'path': 'Assignment 2/src/Q07.ipynb', 'repo_name': 'aravind-3105/Digital-Image-Processing-Assignment1', 'size': '4594'}