advertisement

Lect5 v2

57 %
43 %
advertisement
Information about Lect5 v2

Published on March 8, 2014

Author: SenthilnathanSubramaniyam

Source: slideshare.net

advertisement

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

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