2-D Fourier Transforms - New York University

1 2-D Fourier Transforms Yao Wang Polytechnic University University , Brooklyn Brooklyn, NY 11201. With contribution from Zhu Liu, Onur Guleryuz, and Gonzalez/Woods, Digital Image Processing, 2ed Lecture Outline Continuous Fourier Transform (FT). 1D FT (review). 2D FT. Fourier Transform for Discrete Time Sequence (DTFT). 1D DTFT (review). 2D DTFT. Linear Li C. Convolution l ti 1D, Continuous vs. discrete signals (review). 2D. Filter Design Computer Implementation Yao Wang, NYU-Poly EL5123: Fourier Transform 2. What is a transform? Transforms are decompositions of a function f(x). into some basis functions (x, u). u is typically the freq. index. Yao Wang, NYU-Poly EL5123: Fourier Transform 3. Illustration of Decomposition 3. f 3. f = 1 1+ 2 2+ 3 3. o 2. 2. 1. 1. Yao Wang, NYU-Poly EL5123: Fourier Transform 4. Decomposition Ortho-normal basis function 1, u1 u2. ( x, u1 ) * ( x, u2 )dx 0, u1 u2. Forward . Projection of ) ( x, u ) . F (u ) f ( x), f ( x) . *. ( x, u )dx d f(x) onto (x,u).

2 Inverse . Representing f(x) as sum of f ( x) F (u ) ( x, u )du . (x,u) for all u, with weight F(u). Yao Wang, NYU-Poly EL5123: Fourier Transform 5. Fourier Transform Basis function ( x, u ) e j 2 ux , u , . Forward Transform . F (u ) F{ f ( x)} f ( x)e j 2 ux dx d . Inverse Transform . f ( x) F {F (u )} F (u )e j 2 ux du 1.. Yao Wang, NYU-Poly EL5123: Fourier Transform 6. Important Transform Pairs f ( x) 1 F (u ) (u ). f ( x) e j 2 f0 x F (u ) (u f 0 ). f ( x) cos(2 f 0 x) F (u ) (u f 0 ) (u f 0 ) . 1. 2. f ( x) sin( 2 f 0 x) F (u ) . 1. (u f 0 ) (u f 0 ) . 2j 1, x x0 sin( 2 x0u ). f ( x) F (u ) 2 x0 sinc(2 x0u ). 0, otherwise u sin( t ). where, sinc(t ) . t Derive the last transform pair in class Yao Wang, NYU-Poly EL5123: Fourier Transform 7. FT of the Rectangle Function sin( 2 x0u ) sin( t ). F (u ) 2 x0 sinc(2 x0u ) where, sinc(t ) . u t f(x) f(x) x0=2. x0=1. -1 1 x -2 2 x Note first zero occurs at u0=1/(2 x0)=1/pulse-width, other zeros are multiples of this. Yao Wang, NYU-Poly EL5123: Fourier Transform 8.

3 IFT of Ideal Low Pass Signal What is f(x)? F(u). -u0 u0 u Yao Wang, NYU-Poly EL5123: Fourier Transform 9. Representation of FT. Generally, both f(x) and F(u) are complex Two representations Real and Imaginary F (u ) R(u ) jI (u ). Magnitude and Phase F (u ) A(u )e j (u ) , where I. I(u) F(u). I (u ). A(u ) R(u ) 2 I (u ) 2 , (u ) tan 1. R (u (u ). (u). R(u) R. Relationship R (u ) A(u ) cos (u ), i (u ). ) I (u ) A(u ) sin Power spectrum P (u ) A(u ) F (u ) F (u ) F (u ). 2 * 2. Yao Wang, NYU-Poly EL5123: Fourier Transform 10. What if f(x) is real? Real world signals f(x) are usually real F(u) is still complex, complex but has special properties F * (u ) F ( u ). R (u ) R( u ), A(u ) A( u ), P(u ) P ( u ) : even function ) (u ) ( u ) : odd function I (u ) I ( u ), Yao Wang, NYU-Poly EL5123: Fourier Transform 11. Property of Fourier Transform Duality f (t ) F (u ). F (t ) f ( u ). Linearity F a1 f1 ( x) a2 f 2 ( x) a1 F{ f1 ( x)} a2 F{ f 2 ( x)}. Scaling S li F af ( x) aF{ f ( x)}.

4 Translation f ( x x0 ) F (u )e j 2 x0u , f ( x)e j 2 u0 x F (u u0 ). Convolution f ( x) g ( x) f ( x ) g ( )d . f ( x) g ( x) F (u )G (u ). We will review convolution later! Yao Wang, NYU-Poly EL5123: Fourier Transform 12. Two Dimension Fourier Transform Basis functions ( x, y; u , v) e j ( 2 ux 2 vyy ) e j 2 ux e j 2 vyy , u , v , . Forward Transform . F (u, v) F { f ( x, y )} .. f ( x, y )e j 2 (ux vy ) dxdy Inverse Transform . f ( x, y ) F {F (u , v)} . 1. F (u , v)e j 2 ( ux vy ). dudv . Property P t All the properties of 1D FT apply to 2D FT. Yao Wang, NYU-Poly EL5123: Fourier Transform 13. Example 1. f ( x, y ) sin 4 x cos 6 y f(x,y). F {sin 4 x} sin 4 xe j 2 (ux vy ) dxdy sin 4 xe j 2 ux dx e j 2 vy dy sin 4 xe j 2 ux dx (v). 1. ( (u 2) (u 2)) (v). 2j 1. ( (u 2, v) (u 2, v)) u 2j F(u,v). , x y 0. where ( x, y ) ( x) ( y ) . 0, otherwise v 1. Likewise, F{cos 6 y} ( (u, v 3) (u , v 3)). 2. Yao Wang, NYU-Poly EL5123: Fourier Transform 14. Example 2. f ( x, y ) sin( 2 x 3 y ).

5 2j e . 1 j ( 2 x 3 y ) j ( 2 x 3 y ). e .. F e j ( 2 x 3 y ) e j ( 2 x 3 y ) e j 2 ( xu yv ) dxdy e j 2 x e j 2 ux dx e j 3 y e j 2 yv dy 3 3. (u 1) (v ) (u 1, v ) [X,Y]=meshgrid(-2:1/16:2,-2:1/16:2);. [X Y]=meshgrid( 2:1/16:2 2:1/16:2);. 2 2 f=sin(2*pi*X+3*pi*Y);.. imagesc(f); colormap(gray). 3. Likewise, F e j ( 2 x 3 y ) (u 1, v ) Truesize, axis off;. 2. Therefore h f , 1 3 u F sin( 2 x 3 y ) . 3. (u 1, v ) (u 1, v ) F(u,v). 2j 2 2 . v Yao Wang, NYU-Poly EL5123: Fourier Transform 15. Important Transform Pairs sin( 2 f x x 2 f y y ) . 1. (u f x , v f y ) (u f x , v f y ) . 2j cos(2 f x x 2 f y y ) . 1. (u f x , v f y ) (u f x , v f y ) . 2. 2D rectangular g function 2D sinc function Yao Wang, NYU-Poly EL5123: Fourier Transform 16. Properties of 2D FT (1). Linearity F a1 f1 ( x, y ) a2 f 2 ( x, y ) a1 F{ f1 ( x, y )} a2 F{ f 2 ( x, y )}. Translation j 2 ( x0 u y 0 v ). f ( x x0 , y y0 ) F (u , v)e , f ( x , y ) e j 2 ( u 0 x v 0 y ) F (u u0 , v v0 ). Conjugation f * ( x, y ) F * ( u , v).

6 Yao Wang, NYU-Poly EL5123: Fourier Transform 17. Properties of 2D FT (2). Symmetry f ( x, y ) is real F (u , v) F ( u , v). Convolution Definition of convolution f ( x, y ) g ( x, y ) f ( x , y ) g ( , )d d . Convolution theory f ( x, y ) g ( x, y ) F (u , v)G (u , v). We will describe 2D convolution later! Yao Wang, NYU-Poly EL5123: Fourier Transform 18. Separability of 2D FT and Separable Signal Separability of 2D FT. F2 { f ( x, y )} Fy {Fx { f ( x, y )}} Fx {Fy { f ( x, y )}}. where Fx, Fy are 1D FT along x and y. one can do 1 DFT for each row of original image, then 1D FT along each column of resulting image Separable Signal f(x,y) = fx(x)fy(y). F(u,v). ( ) = Fx((u)F ) y((v), ). where Fx(u) = Fx{fx(x)}, Fy(u) = Fy{fy(y)}. For separable signal, one can simply compute two 1D. Transforms ! Yao Wang, NYU-Poly EL5123: Fourier Transform 19. Example 1. f ( x, y ) sin(3 x) cos(5 y ). f x ( x) sin((3 x) . 1. Fx (u ) (u 3 / 2) (u 3 / 2) . 2j Fy (v) (v 5 / 2) (v 5 / 2) . 1. f y ( y ) cos(5 y ).)

7 2. F (u , v) Fx(u ) Fy (v). 1 3 5 3 5 3 5 3 5 . (u , v ) (u , v ) (u , v ) (u , v ) . 4j 2 2 2 2 2 2 2 2 . u v Yao Wang, NYU-Poly EL5123: Fourier Transform 20. Example 2. 1, | x | x0 , | y | y0. f ( x, y ) . 0, otherwise F (u , v) 4 x0 y0 sinc(2 x0u ) sinc(2 y0 v). x 2. u x0 = 2. y0 = 1. y v -1. 1 1. -2. 2. w/ logrithmic mapping Yao Wang, NYU-Poly EL5123: Fourier Transform 21. Rotation Let x r cos , y r sin , u cos , v sin . 2D FT in polar coordinate (r (r, ) and ( ( , ). 2 . F ( , ) f (r , )e j 2 ( r cos cos r sin sin ) rdrd . 0 0. f (r , )e j 2 r cos( ). rdrd . Property f (r , 0 ) F ( , 0 ). Yao Wang, NYU-Poly EL5123: Fourier Transform 22. Example of Rotation Yao Wang, NYU-Poly EL5123: Fourier Transform 23. Fourier Transform For Discrete Time Sequence (DTFT). One dimensional DTFT. f(n) is a 1D discrete time sequence Forward Transform F(u)) is F( i periodic i di iin u, with ith period i d F (u ) f ( n )e n . j 2 un of 1. Inverse I Transform T f 1/ 2. f ( n) F (u )e j 2 un du 1 / 2.))

8 Yao Wang, NYU-Poly EL5123: Fourier Transform 24. Properties unique for DTFT. Periodicity F(u) = F(u+1). The FT of a discrete time sequence is only considered for u (- . ( , ), ) and u = + is the highest discrete frequency Symmetry for real sequences f ( n) f * ( n) F (u ) F * ( u ). F (u ) F ( u ). F (u ) is symmetric Yao Wang, NYU-Poly EL5123: Fourier Transform 25. Example 1, n 0,1,.., N 1;. f ( n) . 0, others N 1. 1 e j 2 uN sin 2 u ( N / 2). F (u ) e j 2 nu . 1 e j 2 u e j ( N 1)u sin 2 u (1 / 2). n 0. f(n). 0 N-1 n N=10. There are N/2 zeros in (0, ], 1/N apart Yao Wang, NYU-Poly EL5123: Fourier Transform 26. Two dimensional DTFT. Let f(m,n) represent a 2D sequence Forward Transform . F (u , v) . m . n .. f (m, n)e j 2 ( mu nv ). Inverse Transform 1/ 2 1/ 2. f (m, n) F (u , v)e j 2 ( mu nv ) dudv 1 / 2 1 / 2. Properties Periodicity, Shifting and Modulation, Energy Conservation Yao Wang, NYU-Poly EL5123: Fourier Transform 27. Periodicity . F (u , v) . m n . f (m, n)e j 2 ( mu nv ).)

9 F(u,v) is periodic in u, v with period 1, , for all integers k, l: F(u+k, v+l) = F(u, v). To see this consider e j 2 ( m ( u k ) n ( v l )). e j 2 ( mu nv ) e j 2 ( mk nl ). e j 2 ( mu nv ). In MATLAB, frequency scaling is such that 1 represents maximum freq u,v=1/2. Yao Wang, NYU-Poly EL5123: Fourier Transform 28. Illustration of Periodicity u Low frequencies High frequencies 0 v Yao Wang, NYU-Poly EL5123: Fourier Transform 29. Fourier Transform Types Low Pass High Pass Band Pass u u u v v v Non-zero frequency components Yao Wang, NYU-Poly EL5123: Fourier Transform 30. Shifting and Modulation Shifting . F{ f (m m0 , n n0 )} . m n . f (m m0 , n n0 )e j 2 ( mu nv ).. k m m0 , l n n 0 . k l . f (k , l )e j 2 (( k m0 )u (l n0 ) v ).. e j 2 ( m0u n0v ) . k l . f (k , l )e j 2 ( ku lv ). f (m m0 , n n0 ) e j 2 ( m0u n0v ) F (u , v). Modulation j 2 ( mu0 nv0 ). e f (m, n) F (u u0 , v v0 ). Yao Wang, NYU-Poly EL5123: Fourier Transform 31. Energy Conservation Inner Product . f , g.

10 M n . f (m, n) g * (m, n).. f (m, n) G * (u , v)e j 2 ( mu nv ) dudv .. m n .. f (m, n)e j 2 ( mu nv ) G * (u , v)dudv m n . F (u , v)G * (u , v)dudv F , G . Energy Conservation .. 0 .5 0 .5.. 2 2. f (m, n) F (u , v) dudv 0 .5 0 .5. m n . Yao Wang, NYU-Poly EL5123: Fourier Transform 32. Delta Function Fourier transform of a delta function . F (u , v) . m n . (m, n)e j 2 ( mu nv ) 1. (m, n) 1. Inverse Fourier transform of a delta function f (m, n) (u, v)e j 2 ( mu nv ) dudv 1. 0 .5 0 .5. 1 (u, v). Yao Wang, NYU-Poly EL5123: Fourier Transform 33. Example m 1 2 1 f(m,n). f (m, n) 0 0 0 . n 1 2 1 . F (u , v) 1e j 2 ( 1*u 1*v ) 2e j 2 ( 1*u 0*v ) 1e j 2 ( 1*u 1*v ). 1e j 2 (1*u 1*v ) 2e j 2 (1*u 0*v ) 1e j 2 (1*u 1*v ). j 2 sin 2 ue j 2 v j 4 sin 2 u j 2 sin 2 ue j 2 v j 4 sin 2 u (cos 2 v 1). Note: This signal g is low p pass in the horizontal direction,, and band pass in the vertical direction. Yao Wang, NYU-Poly EL5123: Fourier Transform 34. Graph of F(u,v). du = [ ];. 20 d = [[ ].]