Transcription
forward DFTinverse DFTmk nl– j 2π ------- ----- M N mk nl j2π ------- ----- M N f ( m, n ) e2-D DISCRETE FOURIER TRANSFORMDEFINITIONM –1N –1 m 0n 0 F ( k, l ) eM – 1N – 11F ( k, l ) --------MNf ( m, n ) k 0l 0 The DFT is a transform of a discrete, complex 2-D array of size M xN into another discrete, complex 2-D array of size M x N188Dr. Robert A. Schowengerdt2003in forward and inverse definitions (“unitary”)Approximates the Continuous Fourier Transform (CFT) under certain conditionsBoth f(m,n) and F(k,l) are 2-D periodic1in inverse definition instead, or -------------MNAlternate definitions:1 --------MN doesn’t matter as long as consistentECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMRELATION OF THE DFT TO THE CFT One view of the DFT is as an approximation to the CFT “ recipe” to convert CFT to DFT:1. sample f(x,y)1f ( x, y ) -------comb ( x X , y Y )XY2. truncate to MX x NY1f ( x, y ) -------comb ( x X , y Y ) rect ( x MX , y N Y )XY3. make periodic1f ( x, y ) -------comb ( x X , y Y ) rect ( x MX , y NY )XY f p ( m, n )1 ---------------------- comb ( x MX , y NY )MX NY189Dr. Robert A. Schowengerdt, i.e. the periodic extension of a 2-D array f(m,n) with sample intervals X Y 1ECE/OPTI533 Digital Image Processing class notes2003
smooth (leakageoccurs here)sample2-D DISCRETE FOURIER TRANSFORM4. take CFTreplicate (aliasingoccurs here)Dr. Robert A. Schowengerdt2003[ F ( u, v ) comb ( uX , vY ) MX NY sinc ( uMX , vNY ) ] comb ( uMX , vNY ) F p ( k, l ), i.e. the periodic extension of a 2-D array F(k,l) with sample intervals 1/X 1/Y 1190 The arrays f and F are both discrete and periodic in space andspatial frequency, respectivelyECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMCALCULATION OF DFT Both arrays f(m,n) and F(k,l) areperiodic (period M x N) andsampled (X x Y in space, 1/MX x 1/NY in frequency) In the CFT, if one function has compact support (i.e. it is space- orfrequency-limited), the other must have support Therefore, aliasing will occur with the DFT, either in space orfrequency. If we want the DFT to closely approximate the CFT,aliasing must be minimized in both domains191Dr. Robert A. Schowengerdt2003 The Fast Fourier Transform (FFT) is an efficient algorithm tocalculate the DFT that takes advantage of the periodicities in thecomplex exponentialCan use 1-D FFT for 2-D DFT (later)ECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMARRAY COORDINATESIIIIIDCIIVreordered output of DFT The DC term (u v 0) is at (0,0) in the raw output of the DFT (e.g.the Matlab function “fft2”)IIIIIraw output of DFTDCQuad IIV Reordering puts the spectrum into a “physical” order (the sameas seen in optical Fourier transforms) (e.g. the Matlab function“fftshift”)192Dr. Robert A. Schowengerdt2003 N and M are commonly powers of 2 for the FFT. Therefore, the DCterm is at (M/2,N/2) in the reordered format for (0,0) indexingand at (M/2 1,N/2 1) for (1,1) indexingECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMSAMPLE INTERVALSsampling (replication) frequency in u and v:product of physical sample intervals in x and u, y and v:uf 1/2X, vf 1/2Yus 1/X, v: vs 1/YXU 1/M, YV 1/N Constraintsfolding frequency in u and v: For images, a convenient, normalized set of units isX Y 1 pixel Therefore,U 1/M cycles/pixel, us 1 cycle/pixel, uf 1/2 cycle/pixelV 1/N cycles/pixel, vs 1 cycle/pixel, vf 1/2 cycle/pixel193Dr. Robert A. Schowengerdt Note, in reodered DFT format, uf and vf are along the first rowand columns of the arrayECE/OPTI533 Digital Image Processing class notes2003
02020201010100000001010103030404040f(m,n) F(k,l) 2003origin-centered F(k,l) 30Dr. Robert A. Schowengerdt2020202-D DISCRETE FOURIER TRANSFORMReordering the 2-D DFTl414k “origin-centered” display23ECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMAliasing in the frequency 1010 F(k,l) 02040403030301010100000001010103030304040Dr. Robert A. Schowengerdt202020 F(k,l) - F(u,v) 20202040 DFT of discrete approximation to a rect(x/W,y/W) 3 Digital Image Processing class notes2003
2-D DISCRETE FOURIER TRANSFORM(M/2,N)(u,v) ( 0.5-1/N,0)cycles/pixel2003(M,N)(u,v) ( 0.5-1/N, 0.5-1/M)cycles/pixelDr. Robert A. SchowengerdtDigital image power spectrum (squared amplitude of F) coordinates(0,0)(u,v) (-0.5,-0.5)cycles/pixel196(M,N/2), (u,v) (0, 0.5-1/M) cycles/pixelECE/OPTI533 Digital Image Processing class notes
Dr. Robert A. Schowengerdt2-D DISCRETE FOURIER TRANSFORMstreetsEXAMPLES OF IMAGE POWER SPECTRAdesertrailroad197fieldsECE/OPTI533 Digital Image Processing class notes2003
Dr. Robert A. SchowengerdtPower Spectra Display2-D DISCRETE FOURIER TRANSFORMDISPLAY OF POWER SPECTRA Large dynamic rangeamplitude at zero-frequency dominates Mask zero-frequency term to zero Contrast stretch with square-root transform198 Repeat constrast stretch as neededECE/OPTI533 Digital Image Processing class notes2003
m 0m M-12n N-12power spectrum419922003due toperiodicborderat n 0and N-1Dr. Robert A. SchowengerdtDC masked8due toperiodicborderat m 0and M-12-D DISCRETE FOURIER TRANSFORMExamplen 02ECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMMATRIX REPRESENTATIONM –1N –1 m 0n 0N–1 n 0mk nl– j 2π ------- ----- M N Dr. Robert A. Schowengerdt1f ( m, n )W N ( n, l ) ---------W M f W N ,MN2002003This section is from lecture notes by my late friend and colleague, Professor StevePark, of the College of William and Mary, Virginia Compact notationmk– j 2π ------- M W M ( m, k )nl– j 2π ----- N f ( m, n ) e Generalizable to other transformsW M ( m, k ) eW N ( n, l ) eM–1 m 0, where WM is M x M, WN is N x N1 DFT definition F ( k, l ) --------MNletthen1F ( k, l ) --------MNwhich is the forward transformECE/OPTI533 Digital Image Processing class notes
*2-D DISCRETE FOURIER TRANSFORM Note that**W M W M W M W M M I M (M x M identity matrix)**W N W N W N W N N I N (N x N identity matrix)then,*W M FW N201Dr. Robert A. Schowengerdt1** --------- ( W M W M ) f ( W N W N )MN, which is the inverse transform1 --------- ( M I M ) f ( N I N )MN fECE/OPTI533 Digital Image Processing class notes2003
WMfMxNNxNWN2-D DISCRETE FOURIER TRANSFORM1 --------MNMxMMatrix Dimensionality Diagram (M N)FMxN1F ---------W M f W NMN Diagram for inverse transform is similar, except no 1/MN factormk nl– j 2π ------- ----- M N eemknl– j2π ------- – j2π ----- M N 202Dr. Robert A. Schowengerdt2003 Note, this representation is possible because the 2-D DFT kernel isseparable, i.e. eECE/OPTI533 Digital Image Processing class notes
2-D DISCRETE FOURIER TRANSFORMDr. Robert A. Schowengerdt2003where f1, f2, . . . fN are the image columns ofCALCULATING THE 2-D DFTf [ f 1 f 2 . . . f N]1F ---------W M f W NMN Step 1write image aslength Mthen,11 11F ---- ----- W M f 1 ----- W M f 2 . . . ----- W M f N W NMN MM1 ---- [ F 1 F 2 . . . F N ]W NN203where each column is a 1-D DFT of length M of the image columnsECE/OPTI533 Digital Image Processing class notes
tF11 t F 2ttF ---- WN N tFN204tWN WNDr. Robert A. Schowengerdt, where each column is an array of length Nnote, W is symmetric2-D DISCRETE FOURIER TRANSFORM Step 2form matrix transpose Step 3 [ g1 g2 . . . g M ]partition image matrix by columnstF1tF2 tFNECE/OPTI533 Digital Image Processing class notes2003
then205Dr. Robert A. Schowengerdt2-D DISCRETE FOURIER TRANSFORM111tF ---- W N g 1 ---- W N g 2 . . . ---- W N g NNNNF [ G1 G2 . . . G M ]twhere each column is a 1-D DFT of length Ntherefore Step 4transpose Ft to get FECE/OPTI533 Digital Image Processing class notes2003
matrixtranspose2-D DISCRETE FOURIER TRANSFORM1-D DFTapplied toeachcolumnmatrixtranspose1-D DFTapplied toeachcolumnM 1-D DFTs of length NM(Nlog2N) operationsCalculating the 2-D DFT - SummaryfN 1-D DFTs of length MN(Mlog2M) operations N(Mlog2M) M(Nlog2N) MNlog2(MN) total operationsassumes 1-D FFT is used and M,N are powers of 2206FDr. Robert A. Schowengerdt Compares to M2N2 total operations for “brute force” 2-D DFTECE/OPTI533 Digital Image Processing class notes2003
Continuous Fourier Transform (CFT) Dr. Robert A. Schowengerdt 2003 2-D DISCRETE FOURIER TRANSFORM DEFINITION forward DFT inverse DFT The DFT is a transform of a discrete, complex 2-D array of size M x N into another discrete, complex 2-D array of size M x N Approximates the under certain conditions
