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?

2 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). Inverse . Representing f(x) as sum of f ( x) F (u ) ( x, u )du.

3 (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 ).

4 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. IFT of Ideal Low Pass Signal What is f(x)? F(u). -u0 u0 u Yao Wang, NYU-Poly EL5123: Fourier Transform 9.

5 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 ).

6 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)}. 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.

7 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).

8 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 ) . 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).

9 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 )}.

10 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). 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.