Univ of Utah, CS6640 2009 1Filtering in the Fourier DomainRoss WhitakerSCI Institute, School of ComputingUniversity of UtahUniv of Utah, CS6640 2009 2Fourier Filtering• Low-pass filtering• High-pass filtering• Band-pass filtering• Sampling and aliasing• Tomography• Optimal filtering and match filtersUniv of Utah, CS6640 2009 3Some Identities to RememberUniv of Utah, CS6640 2009 4Fourier SpectrumFourier spectrumOrigin in cornersRetiled with originIn centerLog of spectrumImageUniv of Utah, CS6640 2009 5Fourier Spectrum–RotationUniv of Utah, CS6640 2009 6Phase vs SpectrumImage Reconstruction fromphase mapReconstruction fromspectrumUniv of Utah, CS6640 2009 7Low-Pass Filter• Reduce/eliminate high frequencies• Applications– Noise reduction• uncorrelated noise is broad band• Images have sprectrum that focus on low frequenciesUniv of Utah, CS6640 2009 8Ideal LP Filter – Box, RectCutoff freqRinging – Gibbs phenomenonUniv of Utah, CS6640 2009 9Extending Filters to 2D (or higher)• Two options– Separable• H(s) -> H(u)H(v)• Easy, analysis– Rotate• H(s) -> H((u2 + v2)1/2)• Rotationally invariantUniv of Utah, CS6640 2009 10Ideal LP Filter – Box, RectUniv of Utah, CS6640 2009 11Ideal Low-PassRectangle With Cutoff of 2/3ImageFiltered Filtered + HEUniv of Utah, CS6640 2009 12Ideal LP – 1/3Univ of Utah, CS6640 2009 13Ideal LP – 2/3Univ of Utah, CS6640 2009 14Butterworth FilterControl of cutoff and slopeCan control ringingUniv of Utah, CS6640 2009 15Butterworth - 1/3Univ of Utah, CS6640 2009 16Butterworth vs Ideal LPUniv of Utah, CS6640 2009 17Butterworth – 2/3Univ of Utah, CS6640 2009 18Gaussian LP FilteringILPF BLPF GLPFF1F2Univ of Utah, CS6640 2009 19High Pass Filtering• HP = 1 - LP– All the same filters as HP apply• Applications– Visualization of high-freq data (accentuate)• High boost filtering– HB = (1- a) + a(1 - LP) = 1 - a*LPUniv of Utah, CS6640 2009 20High-Pass FiltersUniv of Utah, CS6640 2009 21High-Pass Filters in Spatial DomainUniv of Utah, CS6640 2009 22High-Pass Filtering with IHPFUniv of Utah, CS6640 2009 23BHPFUniv of Utah, CS6640 2009 24GHPFUniv of Utah, CS6640 2009 25HP, HB, HEUniv of Utah, CS6640 2009 26High Boost with GLPFUniv of Utah, CS6640 2009 27High-Boost FilteringUniv of Utah, CS6640 2009 28Band-Pass Filters• Shift LP filter in Fourier domain by convolutionwith deltaLPBPTypically 2-3 parameters-Width-Slope-Band valueUniv of Utah, CS6640 2009 29Band Pass - Two Dimensions• Two strategies– Rotate• Radially symmetric– Translate in 2D• Oriented filters• Note:– Convolution with delta-pair in FD is multiplicationwith cosine in spatial domainUniv of Utah, CS6640 2009 30Band Bass FilteringUniv of Utah, CS6640 2009 31Radial Band Pass/RejectUniv of Utah, CS6640 2009 32Band Reject FilteringUniv of Utah, CS6640 2009 33Band Reject FilteringUniv of Utah, CS6640 2009 34Band Reject FilteringUniv of Utah, CS6640 2009 35Discrete Sampling and Aliasing• Digital signals and images are discrete representationsof the real world– Which is continuous• What happens to signals/images when we samplethem?– Can we quantify the effects?– Can we understand the artifacts and can we limit them?– Can we reconstruct the original image from the discretedata?Univ of Utah, CS6640 2009 36A Mathematical Model of Discrete SamplesDelta functionalShah functionalUniv of Utah, CS6640 2009 37A Mathematical Model of Discrete SamplesDiscrete signalSamples from continuous functionRepresentation as a function of t• Multiplication of f(t) with Shah• Goal– To be able to do a continuous Fourier transformon a signal before and after samplingUniv of Utah, CS6640 2009 38Fourier Series of A Shah FunctionaluUniv of Utah, CS6640 2009 39Fourier Transform of A Discrete SamplinguUniv of Utah, CS6640 2009 40Fourier Transform of A Discrete SamplinguEnergy from higher freqsgets folded back down intolower freqs – AliasingFrequencies get mixed.The original signal isnot recoverable.Univ of Utah, CS6640 2009 41What if F(u) is Narrower in the Fourier Domain?u• No aliasing!• How could we recover the original signal?Univ of Utah, CS6640 2009 42What Comes Out of This Model• Sampling criterion for complete recovery• An understanding of the effects of sampling– Aliasing and how to avoid it• Reconstruction of signals from discrete samplesUniv of Utah, CS6640 2009 43Shannon Sampling Theorem• Assuming a signal that is band limited:• Given set of samples from that signal• Samples can be used to generate the originalsignal– Samples and continuous signal are equivalentUniv of Utah, CS6640 2009 44Sampling Theorem• Quantifies the amount of information in asignal– Discrete signal contains limited frequencies– Band-limited signals contain no more informationthen their discrete equivalents• Reconstruction by cutting away the repeatedsignals in the Fourier domain– Convolution with sinc function in space/timeUniv of Utah, CS6640 2009 45Reconstruction• Convolution with sinc functionUniv of Utah, CS6640 2009 46Sinc Interpolation Issues• Must functions are not band limited• Forcing functions to be band-limited can causeartifacts (ringing)f(t)|F(s)|Univ of Utah, CS6640 2009 47Sinc Interpolation IssuesRinging - Gibbs phenomenonOther issues:Sinc is infinite - must be truncatedUniv of Utah, CS6640 2009 48Aliasing• High frequencies appear as low frequencieswhen undersampledUniv of Utah, CS6640 2009 49Aliasing16 pixels8 pixels0.9174pixels0.4798pixelsUniv of Utah, CS6640 2009 50Overcoming Aliasing• Filter data prior to sampling– Ideally - band limit the data (conv with sincfunction)– In practice - limit effects with fuzzy/soft low passUniv of Utah, CS6640 2009 51Antialiasing in Graphics• Screen resolution produces aliasing onunderlying geometryMultiple high-res samplesget averaged to create onescreen sampleUniv of Utah, CS6640 2009 52AntialiasingUniv of Utah, CS6640 2009 53Interpolation as Convolution• Any discrete set of samples can be consideredas a functional• Any linear interpolant can be considered as aconvolution– Nearest neighbor - rect(t)– Linear - tri(t)Univ of Utah, CS6640 2009 54Convolution-Based Interpolation• Can be studied in terms of Fourier Domain• Issues– Pass energy (=1) in band– Low energy out of band– Reduce hard cut off (Gibbs, ringing)Univ of Utah, CS6640 2009 55TomographyUniv of Utah, CS6640 2009 56Tomography FormulationAttenuationLog gives line integralLine with angle thetaVolume