Information about Lect5 v2

Published on March 8, 2014

Author: SenthilnathanSubramaniyam

Source: slideshare.net

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, …

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

Read more

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 Home. USC. EE. EE 260. 16-Noise1. Download Document. Showing pages : 33 - 35 of 35. This ...

Read more

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

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 Lecture 5, Feb 25 th, 2008 ... Microsoft PowerPoint - lect5_v2.ppt Author: xlx Created Date:

Read more

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

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

Read more

## Add a comment