# Lect5 v2

57 %
43 %
Information about Lect5 v2

Published on March 8, 2014

Author: SenthilnathanSubramaniyam

Source: slideshare.net

Image Transforms and Image Enhancement in Frequency Domain Lecture 5, Feb 25th, 2008 Lexing Xie EE4830 Digital Image Processing http://www.ee.columbia.edu/~xlx/ee4830/ thanks to G&W website, Mani Thomas, Min Wu and Wade Trappe for slide materials

 HW clarification  HW#2 problem 1    Show: f - r2 f ¼ A f – B blur(f) A and B are constants that do not matter, it is up to you to find appropriate values of A and B, as well as the appropriate version of the blur function. Recap for lecture 4

roadmap     2D-DFT definitions and intuitions DFT properties, applications pros and cons DCT

the return of DFT  Fourier transform: a continuous signal can be represented as a (countable) weighted sum of sinusoids.

warm-up brainstorm  Why do we need image transform?

why transform?  Better image processing   Take into account long-range correlations in space Conceptual insights in spatial-frequency information. what it means to be “smooth, moderate change, fast change, …”  Fast computation: convolution vs. multiplication  Alternative representation and sensing   Obtain transformed data as measurement in radiology images (medical and astrophysics), inverse transform to recover image Efficient storage and transmission    Energy compaction Pick a few “representatives” (basis) Just store/send the “contribution” from each basis ?

outline   why transform 2D Fourier transform      a picture book for DFT and 2D-DFT properties implementation applications discrete cosine transform (DCT)   definition & visualization Implementation next lecture: transform of all flavors, unitary transform, KLT, others …

1-D continuous FT   1D – FT 1D – DFT of length N real(g(ωx)) imag(g(ωx)) ω =0 ω =7 x x

1-D DFT in as basis expansion Forward transform real(A) imag(A) u=0 Inverse transform basis u=7 n n

1-D DFT in matrix notations real(A) imag(A) u=0 N=8 u=7 n n

1-D DFT of different lengths real(A) n imag(A) u N=8 N=16 N=32 N=64

performing 1D DFT real-valued input Note: the coefficients in x and y on this slide are only meant for illustration purposes, which are not numerically accurate.

another illustration of 1D-DFT real-valued input Note: the coefficients in x and y are not numerically accurate

from 1D to 2D 1D 2 D ?

Computing 2D-DFT DFT IDFT    Discrete, 2-D Fourier & inverse Fourier transforms are implemented in fft2 and ifft2, respectively fftshift: Move origin (DC component) to image center for display Example: >> >> >> >> I = imread(‘test.png’); F = fftshift(fft2(I)); imshow(log(abs(F)),[]); imshow(angle(F),[]); % % % % Load grayscale image Shifted transform Show log magnitude Show phase angle

2-D Fourier basis real real( ) imag imag( )

2-D FT illustrated real-valued real imag

notes about 2D-DFT  Output of the Fourier transform is a complex number   Decompose the complex number as the magnitude and phase components In Matlab: u = real(z), v = imag(z), r = abs(z), and theta = angle(z)

Explaining 2D-DFT fft2 ifft2

circular convolution and zero padding

zero padded filter and response

zero padded filter and response

observation 1: compacting energy

observation 2: amplitude vs. phase   Amplitude: relative prominence of sinusoids Phase: relative displacement of sinusoids

another example: amplitude vs. phase A = “Aron” P = “Phyllis” FA = fft2(A) FP = fft2(P) log(abs(FA)) log(abs(FP)) angle(FA) ifft2(abs(FA), angle(FP)) Adpated from http://robotics.eecs.berkeley.edu/~sastry/ee20/vision2/vision2.html angle(FP) ifft2(abs(FP), angle(FA))

fast implementation of 2-D DFT  2 Dimensional DFT is separable 1-D DFT of f(m,n) w.r.t n 1-D DFT of F(m,v) w.r.t m    1D FFT: O(N¢log2N) 2D DFT naïve implementation: O(N4) 2D DFT as 1D FFT for each row and then for each column

Implement IDFT as DFT DFT2 IDFT2

Properties of 2D-DFT

duality result

outline   why transform 2D Fourier transform      a picture book for DFT and 2D-DFT properties implementation applications discrete cosine transform (DCT)   definition & visualization implementation

DFT application #1: fast Convolution ? O(N2) Spatial filtering f(x.y)*h(x.y) ? ?

DFT application #1: fast convolution O(N2¢log2N) O(N2) Spatial filtering f(x.y)*h(x.y) O(N4) O(N2¢log2N)

DFT application #2: feature correlation  Find letter “a” in the following image bw = imread('text.png'); a = imread(‘letter_a.png'); % Convolution is equivalent to correlation if you rotate the convolution kernel by 180deg C = real(ifft2(fft2(bw) .*fft2(rot90(a,2),256,256))); % Use a threshold that's a little less than max. % Display showing pixels over threshold. thresh = .9*max(C(:)); figure, imshow(C > thresh) from Matlab image processing demos.

DFT application #3: image filters  Zoology of image filters     Smoothing / Sharpening / Others Support in time vs. support in frequency c.f. “FIR / IIR” Definition: spatial domain/frequency domain Separable / Non-separable

smoothing filters: ideal low-pass

butterworth filters

Gaussian filters

low-pass filter examples

smoothing filter application 1 text enhancement

smoothing filter application 2 beautify a photo

high-pass filters

sobel operator in frequency domain Question: Sobel vs. other high-pass filters? Spatial vs frequency domain implementation?

high-pass filter examples

outline   why transform 2D Fourier transform      a picture book for DFT and 2D-DFT properties implementation applications in enhancement, correlation discrete cosine transform (DCT)   definition & visualization implementation

Is DFT a Good (enough) Transform?  Theory  Implementation  Application

The Desirables for Image Transforms  Theory       Implementation      Inverse transform available Energy conservation (Parsevell) Good for compacting energy Orthonormal, complete basis (sort of) shift- and rotation invariant Real-valued Separable Fast to compute w. butterfly-like structure Same implementation for forward and inverse transform x Useful for image enhancement Capture perceptually meaningful structures in images X X Application   DF T X X ? X X X X X ???

DFT vs. DCT 1D-DCT 1D-DFT a real(a) u=0 u=0 u=7 imag(a) u=7 n=7

1-D Discrete Cosine Transform (DCT) N− 1  π ( 2n +1) k  Z ( k ) = ∑z ( n) ⋅α( k ) cos    2N    n =0  N− 1 π ( 2n +1) k  z ( n) = ∑Z (k ) ⋅α(k ) cos  2 N     k =0  α(0) =   1 , α( k ) = N 2 N Transform matrix A  a(k,n) = α(0) for k=0  a(k,n) = α(k) cos[π(2n+1)/2N] for k>0 A is real and orthogonal  rows of A form orthonormal basis  A is not symmetric!  DCT is not the real part of unitary DFT!

1-D DCT 1.0 -1.0 -100 1.0 100 100 0.0 0.0 0 0 -1.0 -1.0 -100 u=0 to 1 -100 1.0 100 100 0.0 0 0 -1.0 -1.0 -100 u=0 to 2 -100 1.0 Transform coeff. 0 0.0 k 0 1.0 Z(k) 0.0 1.0 Original signal 100 -1.0 n 100 0.0 z(n) 1.0 1.0 100 100 0.0 0.0 0 0 -1.0 -1.0 -100 u=0 to 3 -100 Basis vectors u=0 -100 Reconstructions u=0 to 4 u=0 to 5 u=0 to 6 u=0 to 7

DFT and DCT in Matrix Notations Matrix notation for 1D transform 1D-DCT N=32 1D-DFT A real(A) imag(A)

From 1D-DCT to 2D-DCT u=0 u=7 n=7    Rows of A form a set of orthonormal basis A is not symmetric! DCT is not the real part of unitary DFT!

basis images: DFT (real) vs DCT

Periodicity Implied by DFT and DCT

DFT and DCT on Lena DFT2 DCT2 Shift low-freq to the center Assume periodic and zero-padded … Assume reflection …

Using FFT to implement fast DCT  Reorder odd and even elements z ~ ( n) = z (2n) N for 0 ≤ n ≤ −1 ~ 2 z ( N − n −1) = z ( 2n +1)  Split the DCT sum into odd and even terms N / 2 −1 π ( 4n +1) k  N / 2 −1 π ( 4n + 3) k  Z ( k ) = α( k )  ∑ z ( 2n) ⋅ cos  + ∑ z ( 2n +1) ⋅ cos    2N 2N   n =0    n =0 N / 2 −1 ~ π ( 4n +1) k  N / 2 −1 ~ π ( 4n + 3) k  = α( k )  ∑ z ( n) ⋅ cos  + ∑ z ( N − n −1) ⋅ cos    2N 2N   n =0    n =0 N / 2 −1 ~ π ( 4n +1) k  N −1 ~ π ( 4 N − 4n'−1) k  = α( k )  ∑ z ( n) ⋅ cos  + ∑ z ( n' ) ⋅ cos    2N 2N   n '=N / 2    n =0 N− 1 N− 1  ~ ( n) ⋅ cos π ( 4n +1) k  = Re α( k )e − jπk / 2 N = α( k )∑z z ∑~ (n) ⋅ e − j 2πnk / N     2N   n =0 n =0   = Re α( k )e − jπk / 2 N DFT {~ ( n)} z [ N ]

The Desirables for Image Transforms        DC TX X ? X X Real-valued Separable Fast to compute w. butterfly-like structure Same implementation for forward and inverse transform x X Useful for image enhancement Capture perceptually meaningful structures in images X X Inverse transform available Energy conservation (Parsevell) Good for compacting energy Orthonormal, complete basis (sort of) shift- and rotation invariant Implementation      DF T X X ? X X Theory Application   X X X X X X ???

Summary of Lecture 5   Why we need image transform DFT revisited     What do we need for a transform DCT Coming in Lecture 6:     Definitions, properties, observations, implementations, applications Unitary transforms, KL transform, DCT examples and optimality for DCT and KLT, other transform flavors, Wavelets, Applications Readings: G&W chapter 4, chapter 5 of Jain has been posted on Courseworks “Transforms” that do not belong to lectures 5-6: Rodon transform, Hough transform, …

## Add a comment

 User name: Comment:

## Related pages

### Lect5 Advanced OTA V2 - University of Tehran

Microsoft PowerPoint - Lect5_Advanced OTA_V2 Author: sjafarab Created Date: 12/5/2007 11:54:35 AM ...
Read more

### 49329_Lect5_GAO_LQG_v2(6) - 49329 Control of Mechatronic ...

View Notes - 49329_Lect5_GAO_LQG_v2(6) from ENGINEERIN 49329 at University of Technology, Sydney. 49329 Control of Mechatronic Systems Lecture 5 Gaussian
Read more

### v1 v2 v3 ns v1 v2 v3 ns 2 2 2 n1 n2 n3 2 2 2 2 2 2 v1 ns ...

V1 v2 v3 ns v1 v2 v3 ns 2 2 2 n1 n2 n3 2 2 2 2 2 2 v1 Home. USC. EE. EE 260. 16-Noise1. Download Document. Showing pages : 33 - 35 of 35. This ...
Read more

### Angelo Luongo - MathMods

Angelo Luongo's Profile. Name: Angelo Luongo: ... lect5_stat_bif_v2: Until 2012: 463 lect4_dyn_syst_p2v2: Until 2012: 511 lect3_dyn_syst_p1v2: Until 2012: 406
Read more

### 16:00-16:30

Meths V2 (R0.41) Quant Meths V2 (R0.41) Quant Meths V1 (R0.41) Qual Meths Lect (H0.51) Qual Meths Lect (H0.51) Qual Meths Wkshp (Wolfson) Qual Meths Wkshp
Read more

### Image Transforms and Image Enhancement in Frequency Domain

Image Transforms and Image Enhancement in Frequency Domain Lecture 5, Feb 25 th, 2008 ... Microsoft PowerPoint - lect5_v2.ppt Author: xlx Created Date:
Read more

### Lecture #5 - DePaul University

This is a continuation of the discussion on testing techniques that started with the Basis Path, White Box, testing technique (see Lecture #4).
Read more

### CMFB Compensation Issues - University of Tehran

CMFB Compensation Issues Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 VBCN VBCP Vin+ Vin-Vout-VBP Vout+ C R Two-Stage op-amp © 2007 S. J. Ashtiani 35 CMFB Q9 • CMFB usually ...
Read more

### Google

Advertising Programmes Business Solutions +Google About Google Google.com © 2016 - Privacy - Terms. Search; Images; Maps; Play; YouTube; News; Gmail ...
Read more