2D Fourier Transforms

1 2D Fourier TransformsIn 2D, for signalsh(n;m)withNcolumns andMrows, the idea isexactly the same:^h(k;l)=N 1Xn=0M 1Xm=0e i(!kn+!lm)h(n;m)h(n;m)=1 NMN 1Xk=0M 1Xl=0ei(!kn+!lm)^h(k;l)Often it is convenient to express frequency in vector notation with~k=(k;l)t,~n=(n;m)t,~!kl=(!k;!l)tand ~!t~n=!kn+! Fourier Basis Functions:Sinusoidal waveforms of differentwavelengths (scales) and orientations. Sinusoids onN Mimageswith 2D frequency~!kl=(!k;!l)=2 (k=N;l=M)are given by:ei(~!t~n)=ei!knei!lm=cos(~!t~n)+isin( ~!t~n)Separability:Ifh(~n)is separable, ,h(n;m)=f(n)g(m), then,because complex exponentials are also separable, so is the Fourierspectrum,^h(k;l)=^f(k)^g(l).320: Linear Filters, Sampling, & Fourier AnalysisPage: 12D Fourier Basis FunctionsImagRealGrating for (k,l) = (1,-3)RealGrating for (k,l) = (7,1)Blocks image and its amplitude spectrum320: Linear Filters, Sampling, & Fourier AnalysisPage: 2 Properties of the Fourier TransformSome key properties of the Fourier transform ,^f(~!)

2 =F[f(~x)].Symmetries:Fors(x)2R, the Fourier transform is symmetric, ,^s(!)=^s ( !).Fors(x)=s( x)the transform is real-valued, ,^s(!) (x)= s( x)the transform is imaginary, ,i^s(!) Property:F[f(~x ~x0)]=exp( i~!t~x0)^f(~!)(1)The amplitude spectrum is invariant to translation. The phase spec-trum is not. In particular, note thatF[ (~x ~x0)]=exp( i~!t~x0).Proof: substitution and change of :F @nf(~x)@xjn =(i!j)n^f(~!)(2)For intuition, remember that@ei!xdx=i!ei!xand@ Scaling:Scaling the signal domain causes scaling of theFourier domain; , givena2R,F[s(ax)]=1a^s(!=a).Parseval s Theorem:Sum of squared Fourier coefficients is a con-stant multiple of the sum of squared signal : Linear Filters, Sampling, & Fourier AnalysisPage: 3 Convolution TheoremThe Fourier transform of the convolution of two signals is equal tothe product of their Fourier Transforms :F[f g]=F[f]F[g] ^f(!)^g(!):(3)Proof in the discrete 1D case:F[f g]=Xnf ge i!n=XnXmf(m)g(n m)e i!n=Xmf(m)Xng(n m)e i!

3 N=Xmf(m)^g(!)e i!m(shift property)=^g(!)^f(!):Remarks: This theorem means that one can apply filters efficiently in theFourier domain, with multiplication instead of convolution. Fourier spectra help characterize how different filters behave, byexpressing both the impulse response and the signal in the Fourierdomain ( , with the DTFT). The filter s amplitude spectrumtells us how each signal frequency will be attentuated. The fil-ter s phase spectrum tells us how each sinusoidal signal compo-nent will be phase shifted in the response. Convolution theorem also helps prove properties. prove:@@x(h g)=@h@x g=h @g@x320: Linear Filters, Sampling, & Fourier AnalysisPage: 4 Common Filters and their SpectraTo p R o w :Image of Al and alow-pass(blurred) version of it. Thelow-pass kernel was separable, composed of 5-tap 1D impulse re-sponses116(1;4;6;4;1)in Row:From left to right are the amplitude spectrum of Al,the amplitude spectrum of the impulse response, and the product ofthe two amplitude spectra, which is the amplitude spectrum of theblurred version of Al.

4 (Brightness in the left and right images is pro-portional to log amplitude.)320: Linear Filters, Sampling, & Fourier AnalysisPage: 5 Common Filters and their Spectra (cont)From left to right is the original Al, ahigh-passfiltered version ofAl, and the amplitude spectrum of the filter. This impulse responseis defined by (n) h(n;m)whereh[n;m]is the separable blurringkernel used in the previous left to right is the original Al, aband-passfiltered version ofAl, and the amplitude spectrum of the filter. This impulse response isdefined by the difference of two low-pass : Linear Filters, Sampling, & Fourier AnalysisPage: 6 Common Filters and their Spectra (cont)To p R o w :Convolution of Al with a horizontal derivative filter, alongwith the filter s Fourier spectrum. The 2D separable filter is composedof a vertical smoothing filter ( ,14(1;2;1)) and a first-order centraldifference ( ,12( 1;0;1)) Row:Convolution of Al with a vertical derivative filter, andthe filter s Fourier spectrum.

5 The filter is composed of a horizontalsmoothing filter and a vertical first-order central : Linear Filters, Sampling, & Fourier AnalysisPage: 7 Nyquist Sampling TheoremTheorem:Letf(x)be a band-limited signal such that^f(!)=0forj!j>!0for some!0. Thenf(x)is uniquely determined by its samplesg(m)=f(mns)when2 ns>2!0or equivalentlyns< 02where 0=2 =!0. In words, the distance between samples must besmaller than half a wavelength of the highest frequency in the signalspectrumdown-sampledspectrum forup-sampled andlow-pass filteredoriginal signalspectrumoriginal signalspectrumdown-sampledspectrum fordown-sampledspectrum fordown-sampledspectrum forup-sampled andlow-pass filteredup-sampled andlow-pass filteredHere the replicas can be isolated by an ideal low-pass filter (the dottedpass-band), so the original signal can be perfectly :Letf(x)be a single-sided band-pass signal with band-width2!0. Thenf(x)is uniquely determined if sampled at a rate suchthatns< : Linear Filters, Sampling, & Fourier AnalysisPage: 14 AliasingAliasing occurs when replicas overlap:Consider a perspective image of an infinite checkerboard.

6 The sig-nal is dominated by high frequencies in the image near the designed cameras blur the signal before sampling, using the point spread function due to diffraction, imperfect focus, averaging the signal over each CCD operations attenuate high frequency components in the sig-nal. Without this (physical) preprocessing, the sampled image canbe severely aliased (corrupted):320: Linear Filters, Sampling, & Fourier AnalysisPage: 15 DimensionalityA guiding principal throughout signal Transforms , sampling, and alias-ing is the underlying dimension of the signal, that is, the numberof linearly independent degress of freedom (dof). This helps clarifymany issues that might otherwise appear mysterious. Real-valued signals withNsamples haveNdof. We need a basisof dimensionNto represent them uniquely. Why did the DFT of a signal of lengthNuseNsinusoids? Be-causeNsinusoids are linearly independent, providing a minimalspanning set for signals of lengthN.

7 We need no more thanN. But wait: Fourier coefficients are complex-valued, and thereforehave2 Ndofs. This matches the dof needed for complex sig-nals of lengthNbut not real-valued signals. For real signals theFourier spectra are symmetric, so we keep half of the coefficients. When we down-sample a signal by a factor of two we are movingto a basis withN=2dimensions. The Nyquist theorem says thatthe original signal should lie in anN=2dimensional space beforeyou down-sample. Otherwise information is corrupted ( sig-nal structure in multiple dimensions of the originalN-D spaceappear the same in theN=2-D space). The Nyquist theorem is not primarily about highest frequenciesand bandwidth. The issue is really one of having a model for thesignal; that is, how many non-zero frequency components are inthe signal ( , the dofs), and which frequencies are : Linear Filters, Sampling, & Fourier AnalysisPage: 18