WIXLIB

Two-Dimensional Discrete FourierTransform (2D-DFT)

Definitions Spatial Domain (I)– “Normal” image space– Changes in pixel positions correspond to changes inthe scene– Distances in I correspond to real distances Frequency Domain (F)– Changes in image position correspond to changes inthe spatial frequency– This is the rate at which image intensity values arechanging in the spatial domain image I

Image Processing Spatial Domain (I)– Directly process the input image pixel array Frequency Domain (F)– Transform the image to its frequency representation– Perform image processing– Compute inverse transform back to the spatialdomain

Frequencies in an Image Any spatial or temporal signal has an equivalentfrequency representation What do frequencies mean in an image– High frequencies correspond to pixel values that changerapidly across the image (e.g. text, texture, leaves, etc.)– Strong low frequency components correspond to large scalefeatures in the image (e.g. a single, homogenous object thatdominates the image) We will investigate Fourier transformations to obtainfrequency representations of an image

The Fourier Series Periodic functions can be expressed as thesum of sines and/or cosines of differentfrequencies each multiplied by a differentcoefficient

Property of DFT Linearity:Time/spatial domain: h αf βgFrequency domain: Shifting:FNu 2H αF βG ℑ[(-1) f x ]xE.g. f [a b c d e f g h] then F [1 2 3 4 5 6 7 8]f’ [a -b c -d e -f g -h] then F’ [5 6 7 8 1 2 3 4]

Property of DFT Conjugate symmetry:– For f is real and of length N, then F satisfiesthe following condition.Fk FN k– Where FN k is the complex conjugate of FN k forall k 1,2,3.N-1– Example of length 8, we have– This is case F4 F4 ,which F4 must be real.F1 F7 , F2 F6 , F3 F5

Property of DFT Convolution– Let z be the circular convolution of fand g.zf*g Spatial domain:Frequency domain:1 N 1zk f n g k nN n 0Z u Fu Gu

The Discrete Fourier Transform Since we are dealing with images, we willbe more interested in the discrete FourierTransform (DFT) For a function f(x), x 0,1, ,M-1 we have

The Discrete Fourier Transform Recall Euler’s Formulafrom which we obtainfor u 0, ,M-1 Each term is composed of ALL values of f(x) The values of u are the frequency domain Each F(u) is a frequency component of the transform

The 2D Discrete Fourier Transform Since our images are nothing more than2D discrete functions, we are interested inthe 2D DFTfor u 0, ,M-1 and v 0, ,N-1 and the iDFTis defined as

2D DFT and Inverse DFT (IDFT)f(x, y)F(u, v)M, N: image sizex, y: image pixel positionu, v: spatial frequencyoften usedshort notation:WN e j 2π / N

The Meaning of DFT and Spatial Frequencies Important ConceptAny signal can be represented as a linear combinationof a set of basic components– Fourier components: sinusoidal patterns– Fourier coefficients: weighting factors assigned to the Fouriercomponents Spatial frequency: The frequency of Fourier component Not to confused with electromagnetic frequencies (e.g.,the frequencies associated with light colors)

Spatial Domain In the spatial domain, a single pointcorresponds to the integration of allcontributing frequencies at that position Position is known well, but contributedfrequency is “unlimited”

Frequency Domain In the frequency domain, a single pointcorresponds to the strength of a singlefrequency Each point is influenced by the intensity of ALLpoints in space Frequency is known well, but spatialcontributions are “unlimited”

DFT (Continued) At u v 0, the FDT reduces to This is nothing more than the average grayscalelevel of the image This is often referred to as the DC Component(0 frequency)

DFT (Continued) The FT has the following translation propertywhich for u0 M/2 and v0 N/2 we see that In image processing, it is common to multiply the inputimage by (-1)x y prior to computing F(u,v) This has the effect of centering the transform sinceF(0,0) is now located at u M/2, v N/2

Centered Fourier Spectrum

Real Part, Imaginary Part, Magnitude, Phase, SpectrumReal part:Imaginary rum):Phase(spectrum):PowerSpectrum:

2D DFT PropertiesMean of image/DC component:Highest teSymmetry:MagnitudeSymmetry:

2D DFT PropertiesSpatial domaindifferentiation:Frequency domaindifferentiation:Distribution law:Laplacian:Spatial domainPeriodicity:Frequency domainperiodicity:

Properties of Two-Dimension DFT Linearity (same as 1D DFT) DC coefficient: sum of all term in thematrix (same as 1D) Conjugate symmetry:Fu ,v F u pM , v qN ; p, q I

Properties of Two-Dimension DFT Shifting (similar to 1D DFT)Fourier Transformaeimbfjncgkodhlpa -b-e fi -j-m nc-gk-o-dh-lpDCDC

Computation of 2D-DFTWN e j 2π / NFourier transform matrices:1FN 1···111WN2WN····· N-1 ·2(N-1)WN WN···remember11N-1· · · WN···(N-1)2· · · WNF *N1···111-1WN-2WN····· 1-N ·2(1-N)WN WN···11-N· · · WN···- (N-1)2· · · WNrelationship: FN 1 1 FN*NIn particular, for N 4: 1 111 jj11 F4 1 1 1 1 1j1j 1 111 jj11 F4* 1 1 1 1 j1 j 1

Computation of 2D-DFT To compute the 1D-DFT of a 1D signal x (as a vector): x FN xTo compute the inverse 1D-DFT:1 * x FN xN To compute the 2D-DFT of an image X (as a matrix): X FN XFNTo compute the inverse 2D-DFT:1 * *X 2 FN XFNN

Computation of 2D-DFT: Example A 4x4 image 1 9X 5 6384668238 2 3 3 Compute its 2D-DFT: 1 111 1 1j1j 9X F4 XF4 1 1 1 1 5 1j1j 6MATLAB function: fft2lowest frequencycomponenthighest frequencycomponent384668238 1 111 2 1 j 1 j 3 1 1 1 1 3 1 j 1 j 21211916 1 111 43j12j45j5j1j1j 9 7 36 1 1 1 1 1 2 j 4 5 j 5 j 1 j1j 4 3j 772 5 j32 5j 49j118j47j54j 13 6 13 j 11 6 13 j 49j54j47j118j

建立大小為 m n的矩陣 �� X [1 3 6 8; 9 8 8 2; 5 4 2 3;6 6 3 3]; % 建立 3 4 的矩陣 A XX 1956% 顯示矩陣 A 的內容384668238233 1 9 X 5 6384668238 2 3 3

A fft2(X) A 77.0000 772 5 j32 5j 49j118j47j54j 13 6 13 j 11 6 13 j 49j54j47j118j 2.0000 - 5.0000i 3.00002.0000 5.0000i4.0000 - 9.0000i -11.0000 8.0000i -4.0000 - 7.0000i -5.0000 - 4.0000i-13.0000-6.0000 13.0000i -11.0000-6.0000 -13.0000i4.0000 9.0000i -5.0000 4.0000i -4.0000 7.0000i -11.0000 - 8.0000i

Matlab 共軛複數 x* a- bi 複數大小r a 2 b 2 複數向量的夾角 θ tan-1 (b/a) 複數實部a r cosθ, 複數虛部b r sinθ, 複數指數表示法 x r ei上述各函數對應MATLAB的複數指令為 x* conj(x) r abs(x), θ angle(x), a real(x), b imag(x), x r*exp(i*angle(x))

Computation of 2D-DFT: Example 772 5 j32 5j 4 9 j 11 8 j 4 7 j 5 4 j X 13 6 13 j 11 6 13 j 49j54j47j118j Real part: X realImaginary part: 77232 41145 13 6 11 6 5 4 11 4Magnitude: 77 5.3935.39 9.8513.608.066.4 X magnitude 13 14.32 11 14.32 9.856.408.0613.60 X imag 0 5 05 9874 0 13 0 13 9478 Phase: 1.19 001.19 1.152.512.092.47 X phase 3.142.003.14 2.00 2.472.09 2.51 1.15

Real part: real(A)Real part: ans X77 2 3 24 -11 -4 -5-13 -6 -11 -64 -5 -4 -11real 77 4 13 423 11 4 6 11 5 42 5 6 11

Imaginary part: imag(A)Imaginary part: ans 0-909-5 0 58 -7 -413 0 -134 7 -8 Ximag 0 9 0 9 508 713047 4 13 8 5

Magnitude:Magnitude: abs(A)ans Xmagnitude 77 9 . 85 13 9 . 8577.0000 5.3852 3.0000 5.38529.8489 13.6015 8.0623 6.403113.0000 14.3178 11.0000 14.31789.8489 6.4031 8.0623 13.60155 . 39313 . 608 . 0614 . 32116 . 408 . 065 . 39 6 .4 14 . 32 13 . 60

Phase: angle(A) ans Phase: X phase 0 1.15 3.14 1.15 1.1902.51 2.092.003.142.472.090 -1.19030 1.1903-1.1526 2.5128 -2.0899 -2.46693.1416 2.0032 3.1416 -2.00321.1526 2.4669 2.0899 -2.51281.19 2.47 2.00 2.51

B [77 2-5*i 3 2 5*i; 4-9*i -11 8*i -4-7*i -5-4*i; -13 6 13*i -11 -6-13*i; 4 9*i -5 4*i -4 7*i -11-8*i] B 77.00002.0000 - 5.0000i 3.00002.0000 5.0000i4.0000 - 9.0000i -11.0000 8.0000i -4.0000 - 7.0000i -5.0000 - 4.0000i-13.0000-6.0000 13.0000i -11.0000-6.0000 -13.0000i4.0000 9.0000i -5.0000 4.0000i -4.0000 7.0000i -11.0000 - 8.0000i 77 4 9j X 13 4 9 j2 5j3 11 8 j 4 7 j 6 13 j 11 5 4j 4 7 j2 5j 5 4j 6 13 j 11 8 j

Computation of 2D-DFT: Example Compute the inverse 2D-DFT: 1 111 11 772 5 j32 5 j 1 1 jjjjjj1j1j114911847541 F4* XF4* 2 11 6 13 j 1 1 1 1 4 1 1 1 1 13 6 13 j jjjjjj1j1j11495447118 1 111 21211916 1j1j43j12j45j5j1 7 36 4 1 1 1 1 9 j1 j 4 3 j1 2 j 4 5 j 5 j 1 1 9 5 63 6 8 8 8 2 X 4 2 3 6 3 3 MATLAB function: ifft2

ifft2(B) ans 1 3 69 8 85 4 26 6 38233 1 9 5 63688428 2 X3 3 3 6

Y fftshift(X) rearranges the outputs of fft, fft2, and fftn bymoving the zero-frequency component to the center of thearray. It is useful for visualizing a Fourier transform with the zerofrequency component in the middle of the spectrum. For vectors, fftshift(X) swaps the left and right halves of X. For matrices, fftshift(X) swaps the first quadrant with thethird and the second quadrant with the fourth.

For higher-dimensional arrays, fftshift(X) swaps "halfspaces" of X along each dimension. Y fftshift(X,dim) applies the fftshift operation along thedimension dim.

fftshift in 2DUse fftshift for 2D functions– smiley2 fftshift(smiley);

fftshift(B) ans -11.0000 77 4 9j X 13 4 9 j-6.0000 -13.0000i -13.00002 5j3 11 8 j 4 7 j 6 13 j 11 5 4j 4 7 j2 5j 5 4j 6 13 j 11 8 j -6.0000 13.0000i-4.0000 7.0000i -11.0000 - 8.0000i 4.0000 9.0000i -5.0000 4.0000i3.00002.0000 5.0000i 77.00002.0000 - 5.0000i-4.0000 - 7.0000i -5.0000 - 4.0000i 4.0000 - 9.0000i -11.0000 8.0000i

Centered Representationv(-N/2, -N/2)(-N/2, N/2)highhighMATLABfunction: fftshiftlowuhighhighFrom Prof. Al Bovik(N/2, -N/2)(N/2, N/2)Example:From [Gonzalez& Woods]

Log-Magnitude Visualization2D-DFTcentereds c log(1 r )From [Gonzalez & Woods]

Periodicity [M,N] point DFT is periodic with period [M,N]M 1 N 1f [m, n] F [k , l ]el kj 2π m n N Mk 0 l 0M 1 N 1f [m M , n N ] F [k , l ]el k j 2π ( m M ) ( n N ) N M k 0 l 0M 1 N 1 F [k , l ]ek 0 l 0 f [m, n]1l kj 2π m n N Mel kj 2π M N N M

2D-DFT (Frequency) Domain Filtering

Convolution Theoremf (x,y)inputimageh(x,y)g(x,y)impulse response(filter)outputimageg ( x , y ) f ( x , y ) h ( x, y )DFTIDFTG(u,v) DFT IDFT DFT IDFTF(u,v) H(u,v)

Frequency Domain FilteringFilter design: design H(u,v)From [Gonzalez & Woods]

2D-DFT Domain Filter Design Ideal lowpass, bandpass and highpasslow-frequencymaskmid-frequencymaskFrom Prof. Al Bovikhigh-frequencymask

Procedure forFiltering in the Frequency Domain1. Multiply the input image by (-1)x y to center thetransform2. Compute the DFT F(u,v) of the resulting image3. Multiply F(u,v) by a filter G(u,v)4. Computer the inverse DFT transform h*(x,y)5. Obtain the real part h(x,y) of 46. Multiply the result by

DFT-Domain Filteringa imread(‘cameraman.tif');Da fft2(a);Da fftshift(Da);figure; imshow(log(abs(Da)),[]);H zeros(256,256);H(128-20:128 20,128-20:128 20) 1;figure; imshow(H,[]);HDb Da.*H;Db fftshift(Db);b real(ifft2(Db));figure; imshow(b,[]);Frequency domainSpatial domain

Two-Dimensional Discrete Fourier Transform (2D-DFT) Definitions Spatial Domain (I) – “Normal” image space – Changes in pixel positions correspond to changes in the scene . The Discrete Fourier Transform Re