A systematic examination of 2-D signals and systems

A systematic examination of 2-D signals and systems

1. Signal Processing: From 1-D to 2-D (m-D ) and 2-D Fourier Transform Dimodifikasi dari kuliah Prof. Min Wu Electrical and Computer Engineering Department University of Maryland, College Park Pengolahan Sinyal & Kom . Multimedia ( 2014-2015) Lecture 4

2. Overview Today A systematic examination of 2-D signals and systems 2-D Fourier Transform 2

3. 1-D and 2-D Sig. Proc: Similarity and Differences Many signal processing concepts can be extended from 1-D to 2-D to multi-dimension Major differences The amount of data involved becomes several magnitude higher Audio: CD quality 44.1K samples/second Video: DVD quality 720*480 at 30 frames/sec => 10.4 M samples/sec Less complete mathematic foundations for multi-dimension SP E.g. A 1-D polynomial can be factored as a product of first-order polynomials (as we see and use in ZT, filter design, etc) A general 2-D polynomial cannot always be factored as a product of lower-order polynomials Notion of causality: Causal processing a 2-D signal: from top to bottom & left to right Causality often matters more for temporal signal than spatial signal 3

4. 2-D Signals (1/2) Continuously indexed vs. discretely indexed (sampled) 2-D Impulse (unit sample function) Any 2-D discrete function can be represented as linear combination of impulses 4

5. 2-D Signals ( 2/2 ) 2-D step function Extensions: line impulse and 1-sided step function 5

6. Periodicity of 2-D Discrete Signal x[n 1 ,n 2 ] is (rectangular) periodic with a (positive integer-valued) period T 1 -by- T 2 at rectangular repetition grid if x[n 1 ,n 2 ] = x[n 1 +T 1 , n 2 ] = x[n 1 , n 2 +T 2 ] for  integers (n 1 , n 2 ) Interpreting the conditions: periodic tiling of column and row strips => tiling a basic rectangular shaped cell over a rectangular grid Example: cos [  n 1 /2 +  n 2 ] is periodic with a period 4-by-2 Is cos [ n1 + n2 ] periodic? Periodicity of continuous vs discrete signal: sampled version of two-variable sinusoids are generally not periodic, unless periods are integers. How about tiling of a non-rectangular cell or at a non-rectangular grid? => More general periodicity 6

7. More General 2-D Periodicity x[n 1 ,n 2 ] is general periodic with two integer period vectors N 1 -by- N 2 if for  integers (n 1 , n 2 ) we have x[n 1 ,n 2 ] = x[n 1 +N 11 , n 2 +N 21 ] i.e. x[ n + N 1 ] = x[n 1 +N 12 , n 2 +N 22 ] i.e. x[ n + N 2 ] Periodic tiling of a cell enclosed by N 1 and N 2 . Linearly independent period vectors: det ( N 1 , N 2 )  Rectangular periodicity occurs when matrix [ N 1 N 2 ] is diagonal. Will revisit such non-rectangular tiling in “lattice sampling” and texture analysis 7

8. Separability x[n 1 ,n 2 ] is called a separable signal if it can be expressed as x[n 1 ,n 2 ] = f[n 2 ]  g[n 1 ] In matrix notation of the image X, an separable image can be represented by the outer product of two column vectors: X = f  g T E.g. the impulse signal is separable:  [n 1 ,n 2 ] =  [n 1 ]   [n 2 ] Separable signals form a special class of multi-dimensional signals Consider indices range: 0  n 1  N 1 1,  n 2  N 2 1 A general 2-D signal x[n 1 ,n 2 ] has N 1  N 2 degrees of freedom A separable signal has only N 1 + N 2  1 degrees of freedom = * 8

9. 2-D System: How to Characterize it? A 2-D system often refers to a system that maps a 2-D input signals to a 2-D output signal Such a system may be represented by y[n 1 ,n 2 ] = H ( x[n 1 ,n 2 ] ) Linear system H( ) : for all a, b, x1[ ], x2[ ] H (a  x 1 [n 1 ,n 2 ] + b  x 2 [n 1 ,n 2 ]) = a  H (x 1 [n 1 ,n 2 ]) + b  H (x 2 [n 1 ,n 2 ]) Impulse responses: h( m,n ; m’,n ’) = H (  [m-m’, n-n’] ) is the output at location ( m,n ) in response to a unit impulse at ( m’,n ’) => Point Spread Function (PSF): impulse response for system with positive inputs & outputs (such as intensity of light in imaging system) A linear sys can be characterized by its impulse responses 9

10. Shift Invariance Shift invariant system: If H (x[m, n]) = y[ m,n ], then H ( x[m - m , n - n ] ) = y[m - m , n - n ] Impulse response for Linear Shift-Invariant (LSI) System A function of the two displacement index variable only: h( m,n ; m’,n ’) = h[ m-m’, n-n’] i.e. the shape of the impulse response does not change as the location of input impulse moves in the ( m,n ) plane I/O relation for a LSI system: Equal to the 2-D convolution of the input with an impulse response 10

11. 2-D Convolution Rotate the impulse response array h(  ,  ) around the original by 180 degree Shift by (m, n) and overlay on the input array x( m’,n ’) Sum up the element-wise product of the above two arrays The result is the output value at location (m, n) From Jain’s book Example 2.1 11

12. Review of 1-D Fourier Transform Transform Time Domain (cont’s or discrete? periodic?) Frequency Domain (transform domain) (cont’s or discrete? periodic?) Fourier Series (FS) Fourier Transform (FT) Discrete-Time Fourier Transform (DTFT) Discrete Fourier Transform (DFT) 12

13. Lec4 – Multi-dim Sig/Sys [ 13 ] Review of 1-D Fourier Transform

14. 2-D Fourier Transform for a 2-D continuous function Horizontal and vertical spatial frequencies (unit: cycles per degree of viewing angle) Separability: separable 2-D complex exponentials allow 2-D transform to be realized by a succession of 1-D transforms along each spatial coordinate Many other properties can be extended from 1-D FT convolution in one domain  multiplication in another domain inner product preservation (Parseval energy conservation theorem) F(  x , y) F(  x ,  y ) F(  x , y) 14

15. Freq. Response & Eigen Functions for LSI System Eigen function of a system Defined as an input function that is reproduced at the output with a possible change only by a multiplicative factor (i.e. amplitude and phase) Eigen function for 1-D LTI system is exp[j2  x  x ] Fundamental property of a Linear Shift Invariant System Eigen functions are 2-D complex exponentials exp[j2 (x  x + y  y )] Frequency response H(  x,  y ) for a 2-D continuous LSI system is the Fourier Transform of its impulse response represents the (complex) amplitude of the system response for an complex exponential input at spatial frequency (  x,  y ) exp[j2 (x  x + y  y )] H(  x ,  y ) exp[j2 (x  x + y  y )] H 15

16. 2-D Discrete Space Fourier Transform For Discrete/Sampled 2-D Functions Note: (1) X(  1,  2 ) is periodic with period 2  by 2  (2) exp{j(m  1 + n  2 )} are eigen functions of 2-D discrete LSI system 16

17. 2-D DFT (on Discrete Periodic 2-D Function) W N = exp{- j2  / N} complex conjugate of primitive N th root of unity Separability: realize 2-D DFT by succession of 1-D DFTs Allow for leveraging 1-D fast transform algorithms for 2-D Circular convolution in one domain ~ multiplication in another domain convolving w/ periodic signal => circular convolution Overall normalizing factor of the transform pair = 1 / (MN) 17

18. 2-D DFT Property Tables are from Gonzalez-Woods 2/e online slides; book pp210-211. 18

19. 19

20. 20

21. Image examples are from Gonzalez-Woods 2/e online slides. 2-D sinc function plots from B. Liu Princeton EE488 F’06. Slide from B. Liu – EE488 F’06 Princeton Examples of 2-D DFT 21

22. 2-D Box Function and its FT Image examples are from Gonzalez-Woods 3/e online slides. F[ u, v ] = ATZ [sin(  uT) / (  uT)] [sin(  vZ) / (  vZ)] 22

23. More Examples MATLAB: csig=cos(ramp * 4 * pi); J=csig’ * ramp; 256 x 256 MATLAB: J=cos(4*pi*ramp)*cos(4*pi*ramp)’; To use imshow, need to scale J so that 0 ≤ J ≤ 1 . Slide from B. Liu – EE488 F’06 Princeton

24. Frequency Domain View of Linear Spatial Filtering Image examples are from Gonzalez-Woods 2/e online slides Fig.4.4 & 4.7. 24

25. Optical and Modulation Transfer Function Optical Transfer Function (OTF) for a LSI imaging system Defined as its normalized frequency response Modulation Transfer Function (MTF) Defined as the magnitude of the OTF 25

26. MTF of Human Visual System Direct MTF measurement of Human Visual System (HVS) Use sinusoidal grating of varying contrast and spatial frequency The contrast is specified by ratio of maximum to minimum intensity Observation of this grating shows the visibility thresholds at various spatial frequencies Typical MTF has band-pass shape Suggest HVS is most sensitive to mid-freq. and least to high freq. Some variations with viewer & viewing angle From Jain’s book Figure 3.7 26

27. Image Enhancement via Spatial Filtering 27

28. Spatial Operations with Spatial Mask Spatial mask is 2-D finite impulse response (FIR) filter Usually has small support 2x2, 3x3, 5x5, 7x7 Convolve this filter with image g(m,n) =  f(m-x, n-y) h(x,y) =  f(x,y) h(m-x, n-y) … mirror w.r.t. origin, then shift & sum up In frequency domain: multiplying DFT(image) with DFT(filter) Note: spatial mask is often specified as the already mirrored version of the equivalent FIR filter. Image examples are from Gonzalez-Woods 2/e online slides. 28

29. Spatial Averaging Masks For softening, noise smoothing, LPF before subsampling (anti-aliasing), etc. “isotropic” (i.e. circularly symmetric / rotation invariant) filters: with response independent of directions 1/4 1/4 1/4 1/4 0 1 1 1/9 1/9 1/9 1/9 -1 0 1 -1 1 1/9 1/9 1/9 1/9 1/9 1/8 1/8 1/2 -1 0 1 -1 1 1/8 1/8 29

30. Frequency Response of Averaging Mask Recall: averaging mask is a FIR filter with a square support => take FT to get its frequency response: it is a low pass filter Image examples are from Gonzalez-Woods 2/e online slides. 30

31. Suppressing Noise via Spatial Averaging Image with i.i.d. noise y(m,n) = x(m,n) + N(m,n) Averaged version v(m,n) = (1/N w )  x(m-i, n-j) + (1/N w )  N(m-i, n-j) Noise variance reduced by a factor of N w N w ~ # of pixels in the averaging window SNR improved by a factor of N w if x(m,n) is constant in local window Window size is limited to avoid blurring 31

32. Directional Smoothing Problems with simple spatial averaging mask Edges get blurred Improvement Restrict smoothing to along edge direction Avoid filtering across edges Directional smoothing Compute spatial average along several directions Take the result from the direction giving the smallest changes before & after filtering Other solutions Use more explicit edge detection and adapt filtering accordingly  W  32

33. Lec5 – 2D FT & Spatial Filtering [ 33 ] Coping with Salt-and-Pepper Noise ( From Matlab Image Toolbox Guide Fig.10-12 & 10-13 )

34. Median Filtering Salt-and-Pepper noise Isolated white/black pixels spread randomly over the image Spatial averaging filter may incur blurred output Median filtering Take median over a small window as output ~ nonlinear Median{ x(m) + y(m) }  Median{x(m)} + Median{y(m)} Odd window size is commonly used 3 x 3, 5 x 5, 7 x 7 5-pixel “ + ”-shaped window Even-sized window ~ take the average of two middle values as output Generalize: apply order statistic operations 34

35. Image Sharpening Use LPF to generate HPF Subtract a low pass filtered result from the original signal HPF extracts edges and transitions Enhance edges I  I LP  I HP = I – I LP  I 1 = I + a*I HP 35

36. Example of Image Sharpening v(m,n) = u(m,n) + a * g(m,n) Often use Laplacian operator to obtain g(m,n) Laplacian operator is a discrete form of 2 nd -order derivatives -¼ -¼ 1 -1 0 1 -1 1 -¼ -¼ 36

37. Summary of Today’s Lecture 2-D Signals and Systems 2-D Fourier Transform Image enhancement via spatial filtering Readings Woods, 2 nd ed., Ch. 1 – pp. 1-35. 37