01/27/2003 2D Fourier Transform 12D Fourier TransformWeek IV2-D DFT & Properties01/27/20032D Fourier Transform 2Fourier Transform - review1-D:2-D:Fu fx fxe dxf x Fu Fue duFuv f xye dxdyfxy Fuve dudvjuxjuxjuxvyjuxvyaf k pkpafaf≡ℑ =≡ℑ ===−−∞∞−−∞∞−++zzzzzz() ()() () ()(,) (, )(,) (,)21222ππππ01/27/20032D Fourier Transform 32D FT: PropertiesConvolution: f(x,y) g(x,y) = F(u,v) G(u,v)Multiplication: f(x,y) g(x,y) = F(u,v) G(u,v)Separable functions: Suppose f(x,y) = g(x) h(y), ThenF(u,v)=G(u)H(v)Shifting: f(x+x0, y+y0) exp[2π (x0u + y0v)] F(u,v)Linearity: a f(x,y) + b g(x,y) a F(u,v) + b G(u,v)01/27/20032D Fourier Transform 4Separability of the FTFuv f xye dx e dyFuy e dyjux jvyjvy(,) (, )(, )=LNMOQP=−−∞∞−∞∞−−∞∞−zzz222πππ01/27/20032D Fourier Transform 5Separability (contd.)f(x,y) F(u,y) F(u,v)Fourier Transform along X.Fourier Transformalong Y.We can implement the 2D Fourier transform as a sequence of 1-D Fourier transform operations.01/27/20032D Fourier Transform 6Eigenfunctions of LSI SystemsA function f(x,y) is an Eigenfunction of a system T ifT[ f(x,y) ] = α f(x,y) for some constant (Possibly complex) α.For LSI systems, complex exponentials of the form exp{ j2ππππ (ux+vy) }, for any (u,v), are the Eigenfunctions.01/27/20032D Fourier Transform 7Impulse Response and Eigenfunctionsgxy hx sy te dsdthxye e dxdyHuvejusvtjuxvy juxvyjuxvy(,) ( , )(,)(,)()() ()()=--==+-••+- ++zzzz2222ππππConsider a LSI system with impulse response h(x,y).Its output to the complex exponential is01/27/20032D Fourier Transform 82-D FT: Examplef(x,y)xyYXAFuv f xye dxdyAe dx e dyAXYuXuXvYvYejuxvyjuxXjvyYjuXvY(,) (, )sin sin()()===LNMOQPLNMOQP-+-••---+zzzz22020ππππππππ01/27/20032D Fourier Transform 9Example (contd.)01/27/20032D Fourier Transform 10Example201/27/20032D Fourier Transform 11Discrete Fourier TransformConsider a sequence {u(n), n=0,1,2,....., N-1}. The DFT of u(n) isvk unW k NWeunNvkW n NnNNknNjNkNNkn( ) ( ) , , ,.....,,( ) ( ) , , ,...,==−===−=−−=−−∑∑0120101 1101 1Where and the inverse is given byπ01/27/20032D Fourier Transform 122-D DFTOften it is convenient to consider a symmetric transform:In 2-D: consider a NXN imagevkNunWunNvkWNknnNNknnN() ()() ()===--=-ÂÂ110101andvklNumn W WumnNvkl WnNNkmNlnmNlNNkm lnkN(,) ( , ) ,(,) (,)===-=-=---=-ÂÂÂÂ110101010101/27/20032D Fourier Transform 132D DFT -- PROPERTIES■ Separability■ Translation■ Scaling■ Periodicity and Conjugate Symmetry■ Rotation■ convolution01/27/20032D Fourier Transform 14SeparabilityFor each ‘m’, v(m,l) is the 1-D DFT with frequency values l = 0,1,....., N-1vklNWumnWNvml WNkmmNNlnnNNkmmN(,) ( , )(,)===-=-=-ÂÂÂ1101010101/27/20032D Fourier Transform 15SeparabilityThe DFT of a 2-D array can be obtained by first taking the 1-D DFT of each row (or column) and then taking the 1-D DFT of each column (or row).It does not matter if the order of operation is reversed.01/27/20032D Fourier Transform 16Translationum m n n vklejkmlnN(,)(,)(' ')-¢-¢´-+2π01/27/20032D Fourier Transform 17Displaying the DFT: Scalingv(k,l)=DFT{u(m,n)}DisplayC log[1+lv(k,l)l]ConstantLarge dynamic range01/27/20032D Fourier Transform 18In MATLABf = zeros(30,30);f(5:24,13:17)=1;imshow(f, ‘notruesize’);01/27/20032D Fourier Transform 19In Matlab(2)F =fft2(f);F2 = log(abs(F));imshow(F2, [-1, 5], ‘notruesize’);colormap(jet); colorbar;01/27/20032D Fourier Transform 20Displaying the DFTN-1v0N-1uLow frequency components01/27/20032D Fourier Transform 21Displaying (again) & Shiftingumne vk k l lumn v kNlNjkmlnNmn(,) ( ', ')(,)( ) ,(' ')2122π++´---´ --FHIKandThe origin of the F{u(m,n)} can be moved to the center of the array (N X N square) by first multiplying u(m,n) by (-1)m+n and then taking the Fourier transform.Note: Shifting does not affect the magnitude of the Fourier transform.01/27/20032D Fourier Transform 22Displaying DFT|v(k,l) e -j2π[ km’+ln’ ] / N | = |v(k,l)|ABCDDCBALow frequencycomponentsMATLAB Example01/27/20032D Fourier Transform 23In Matlab(3): FFTSHIFTF2= fftshift(F);imshow (log(abs(F2),..)01/27/20032D Fourier Transform 24Another exampleOriginal image Its centered DFT magnitude01/27/20032D Fourier Transform 25Periodicity & Conjugate Symmetryu(m,n) Fv(k,l)v(k,l) = v(k+N, l) = v(k, l+N) = v(k+N, l+N)If u(m,n) is real, v(k,l) also exhibits conjugate symmetryv(k,l) = v* (-k, -l) or | v(k,l) | = | v(-k, -l) |01/27/20032D Fourier Transform 26Rotation(continuous case)If you rotate the image u(m,n) by an angle θ, its F.T alsogets rotated by the same angle.01/27/20032D Fourier Transform 27Rotation01/27/20032D Fourier Transform 28Average ValueuNumnvklNumnevNumn NuuvNnmjkm l nNnmnm======ÂÂÂÂÂÂ-+11001002(,)(,) ( , )(,) ( , )(,)Average or (Scaled Average)π01/27/20032D Fourier Transform 29Convolution (Revisited)Consider 1-D continuous caseConvolution inSpaceMultiplication inFrequencyfx gx fx gx x dxfx Fu gx Gufx gx FuGu() () (')( ') '() (), () ()() () () ()*= -´´*´-••zLet Then 01/27/20032D Fourier Transform 30Let us now assume that we discretize f(x) and g(x) into vectors f(n) and g(n) of lengths A and Bf(n) {f(0), f(1),..... f(A-1)}g(n) {g(0), g(1), g(2),....g(B-1)}(a) DFT and its inverse are periodic functions(b) Convolving two vectors of length A and B gives a vector of dimension A+B-1. (Linear convolution)Discrete Convolution01/27/20032D Fourier Transform 31Length of the ConvolutionBA01/27/20032D Fourier Transform 32Discrete Convolution: an example (Fig 4.36)3200 400f(m)m3200 400f(m)m2200 400h(m)m2200 400h(m)m2200 400h(-m)m2200 400h(-m)m01/27/20032D Fourier Transform 33Discrete conv. (cont.)2200 400h(x-m)mx2200 400h(x-m)mxRange of the DFT=40050001/27/20032D Fourier Transform 34Zero ImbeddingIn order to obtain a convolution theorem for the discrete case, and still be consistent with the periodicity property we need to assume that sequences f( ) and g( ) are periodic with some period M. From (b) it is clear that M> A+B-1 to avoid overlap. Since this period is greater than A or B, the original sequence length must be increased and this is done by appending zeros at the end. Redefine the extended sequences asfnfn n AAnMgngn n BBnMee()()()()=≤≤−≤≤ −RST=≤≤−≤≤ −RST0101010101/27/20032D Fourier Transform 35fn gn fmgn mgn gn Mnn nN n NnNnxyxyxyyxxece e e cmMcxyxy() () ( ) ( )().*= -=+££-=- π==-Â0112 11010where Modulo Note: With n expressed as=