Fourier AnalysisImage ScalingImage sub-samplingSlide 4Even worse for synthetic imagesReally bad in videoAlias: n., an assumed nameAliasingJean Baptiste Fourier (1768-1830)A sum of sinesFourier TransformFrequency SpectraFT: Just a change of basisIFT: Just a change of basisFinally: Scary MathSlide 16Extension to 2DSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Curious things about FT on imagesSlide 25Slide 26Various Fourier Transform Pairs2D convolution theorem exampleLow-pass, Band-pass, High-pass filtersFourier Analysis15-463: Rendering and Image ProcessingAlexei EfrosImage ScalingThis image is too big tofit on the screen. Howcan we reduce it?How to generate a half-sized version?Image sub-samplingThrow away every other row and column to create a 1/2 size image- called image sub-sampling1/41/8Slide by Steve SeitzImage sub-sampling1/4 (2x zoom) 1/8 (4x zoom)Why does this look so crufty?1/2Slide by Steve SeitzEven worse for synthetic imagesSlide by Steve SeitzReally bad in videoSlide by Paul HeckbertAlias: n., an assumed namePicket fence recedingInto the distance willproduce aliasing…Input signal:x = 0:.05:5; imagesc(sin((2.^x).*x))Matlab output:WHY?Aj-aj-aj:Alias!Not enough samplesAliasing•occurs when your sampling rate is not high enough to capture the amount of detail in your image•Can give you the wrong signal/image—an aliasWhere can it happen in graphics?•During image synthesis: •sampling continous singal into discrete signal•e.g. ray tracing, line drawing, function plotting, etc.•During image processing: •resampling discrete signal at a different rate•e.g. Image warping, zooming in, zooming out, etc.To do sampling right, need to understand the structure of your signal/imageEnter Monsieur Fourier…Jean Baptiste Fourier (1768-1830)had crazy idea (1807):Any periodic function can be rewritten as a weighted sum of sines and cosines of different frequencies. Don’t believe it? •Neither did Lagrange, Laplace, Poisson and other big wigs•Not translated into English until 1878! But it’s true!•called Fourier SeriesA sum of sinesOur building block:Add enough of them to get any signal f(x) you want!How many degrees of freedom?What does each control?Which one encodes the coarse vs. fine structure of the signal?xAsin(Fourier TransformWe want to understand the frequency of our signal. So, let’s reparametrize the signal by instead of x:xAsin(f(x) F()Fourier TransformF()f(x)Inverse Fourier TransformFor every from 0 to inf, F() holds the amplitude A and phase of the corresponding sine •How can F hold both? Complex number trick!)()()(iIRF 22)()(IRA )()(tan1RIWe can always go back:Frequency SpectraUsually, amplitude is more interesting than phase:FT: Just a change of basis...*=M * f(x) = F()IFT: Just a change of basis...*=M-1 * F() = f(x)Finally: Scary MathFinally: Scary Math…not really scary:is hiding our old friend:So it’s just our signal f(x) times sine at frequency )sin()cos( xixexiQPQPΑxAxQxP122tansin()sin()cos(xAsin(phase can be encodedby sin/cos pairExtension to 2Din Matlab, check out: imagesc(log(abs(fftshift(fft2(im)))));This is the magnitude transform of the cheetah picThis is the phase transform of the cheetah picThis is the magnitude transform of the zebra picThis is the phase transform of the zebra picCurious things about FT on imagesThe magnitude spectra of all natural images quite similar•Heavy on low-frequencies, falling off in high frequences•Will any image be like that, or is it a property of the world we live in?Most information in the image is carried in the phase, not the amplitude•Seems to be a fact of life•Not quite clear whyReconstruction with zebra phase, cheetah magnitudeReconstruction with cheetah phase, zebra magnitudeVarious Fourier Transform PairsImportant facts•The Fourier transform is linear•There is an inverse FT•if you scale the function’s argument, then the transform’s argument scales the other way. This makes sense --- if you multiply a function’s argument by a number that is larger than one, you are stretching the function, so that high frequencies go to low frequencies•The FT of a Gaussian is a Gaussian.The convolution theorem•The Fourier transform of the convolution of two functions is the product of their Fourier transforms•The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transformsSlide by David Forsyth2D convolution theorem example*f(x,y)h(x,y)g(x,y)|F(sx,sy)||H(sx,sy)||G(sx,sy)|Slide by Steve SeitzLow-pass, Band-pass, High-pass filterslow-pass:band-pass:what’s
View Full Document
Unlocking...