Lucas Parra CCNY City College of New York BME I5000 Biomedical Imaging Lecture FT Fourier Transform Review Lucas C Parra parra ccny cuny edu Blackboard http cityonline ccny cuny edu 1 Lucas Parra CCNY City College of New York Fourier Transform 1D The Fourier Transform FT is defined as H k FT h x dx h x e The FT is an invertible transformation 1 i2 kx h x FT H k dk H k e We can show this using dk H k e i 2 kx i2 kx dk e i 2 kx dk dx h x e x i 2 k x x h x Notational convention Use k for spacial and for temporal frequency 2 Lucas Parra CCNY City College of New York Fourier Transform Frequency Domain H k is in general complex valued H k R k i I k A k e i k with R k Re H k I k Im H k and Amplitude A k H k R k I k Phase I k k arctan R k 2 2 Positive frequencies k 0 counterclockwise rotation Negative frequencies k 0 clockwise rotation H k k k 0 h x e i 2 k0 x 3 Lucas Parra CCNY City College of New York Fourier Transform Examples 4 Lucas Parra CCNY City College of New York Fourier Transform Examples 5 Lucas Parra CCNY City College of New York Fourier Transform Convolution Theorem Convolution is defined as b x dx h x g x x h x g x Convolution Theorem states that B k FT h x g x H k G k Note that with the convolution theorem we can implement convolution as a multiplication in the frequency domain h x FT g x FT H k G k B k FT 1 b x 6 Lucas Parra CCNY City College of New York Fourier Transform Convolution Theorem Proof FT h x g x dx h x g x e i 2 kx dx dx h x g x x e i 2 kx dx dx h x g x e i 2 k x x dx h x e i 2 kx dx g x e i 2 kx H k G k 7 Lucas Parra CCNY City College of New York Fourier Transform Inverse Filter With the Convolution Theorem we can derive the inverse convolution or inverse filter b x g x h x B k G k H k Therefore B k G k H k And the inverse filter is given by the inverse FT of H 1 k g x FT 1 1 b x H k 8 Lucas Parra CCNY City College of New York Fourier Transform 2D and higher The Fourier transform in 2D is defined as H k x k y dx dy h x y e i2 k x x k y y The inverse transform is defined correspondingly Note that the exponent is separable and therefor the Fourier transform can be applied sequentially in each dimension H k x k y dy e i 2 k y y dx h x y e i2 k x x In multiple dimensions with k kx ky kz T r x y z T i 2 k r H k d r h r e 9 Lucas Parra CCNY City College of New York Fourie Transform k space Source C A Mistretta 10 Lucas Parra CCNY City College of New York 2D Fourier Transform Phase and Amplitude Note that the in images the phase carries most of the information 11 Lucas Parra CCNY City College of New York 2D Fourier Transform Phase and Amplitude Note that the in images the phase carries most of the information 12 Lucas Parra CCNY City College of New York Fourier Transform 2D Convolution The 2D convolution with a PSF h x y is b x y dx dy h x y g x x y y h x y g x y The Convolution Theorem applies in higher dimensions as well B k x k y G k x k y H k x k y Even though h x y may not be separable h x y h x h y with the convolution theorem we never have to truly compute a 2D convolution 13 Lucas Parra CCNY City College of New York Fourier Domain System Response Consider stationary oscillatory input to a LSI system h x i 2 k x g x e b x h x g x dx h x e i 2 k x x H k e i2 k x The output is the input times the FT of the impulse response e i2 k x i 2 kx H k H k e The oscillation with frequency k has been modified in phase and amplitude A A H k arg H k i H k Ae 14 Lucas Parra CCNY City College of New York Fourier Domain System Response FT inversion formula tells us that arbitrary input g x can be decomposed into sum of oscillations weighted by G k g x dk G k e i2 kx The system response to that is given by the convolution theorem B k H k G k G k1 g x FT G k2 G k3 H k1 H k2 FT 1 b x H k3 15 Lucas Parra CCNY City College of New York Fourier Domain System Response Radon inverse filter kernel H k k high pass filter 16 Lucas Parra CCNY City College of New York Fourier Domain System Response 2 Gaussian low pass filter kernel H k exp k 1 27 2 2 17 Lucas Parra CCNY City College of New York Fourier Domain System Response 2D 18 Lucas Parra CCNY City College of New York Fourier Transform FFT The numerical implementation of the FT is discrete in x and k is referred to as Discrete Fourier Transform DFT N 1 G k g x e x 0 N 1 1 g x N j 2 kx N G k e j 2 kx N k 0 A fast algorithm is available FFT to compute the DFT in only N log2 N operations instead of N2 Convolution with long filters is therefore often implemented using the FFT FFT requires N to be a power of 2 19 Lucas Parra CCNY City College of New York Fourier Transform Filter with FFT To filter signals with lengths not a power of 2 Pad zeros at the end up to next power of 2 FFT multiply each frequency inverse FFT keep only fist L values Matlab b x y h x y g x y using fft assumes h smaller than g L size g N 2 ceil log2 L b ifft2 fft2 g N 1 N 2 fft2 h N 1 N 2 if isreal g h b real b end b b 1 L 1 1 L 2 Demonstrate fftshift inverse filtering separability Assignment FT Generate image with randomized phase and original amplitude and image with random amplitude and original phase 20