2D Fourier Theory for Image AnalysisRoadmapDifferent basis representationHadamard basisSinusoidal BasisFourier Basis2D DFTFourier BasisFourier transform in MatlabPhase and MagnitudeImage pyramid representationGaussian PyramidLaplacian pyramidGaussian and LaplacianSummation PropertyApplications – Image MosaicingMulti-resolution spline interpolationImage mosaicingGabor filtersTexture Representation: Filter ResponsesExample: Filter ResponsesTexture Similarity based on Response StatisticsConclusions2D Fourier Theory for Image AnalysisMani ThomasCISC 489/689Roadmap 2D image basis Fourier basis Scale-space representation Gaussian pyramid Laplacian pyramid Image mosaicing Gabor filtersDifferent basis representation Recall our discussion of basis vectors for coordinate systems: Describe point as linear combination of ortho-gonal basis vectors: x = a1v1+ ... + anvn The standard basis for images is the set of unit vectors corresponding to each pixel. A toy example:Hadamard basis The standard basis is not the only one we can use to describe animage E.g., the Hadamard basis (basis images shown here for 2 x 2 images, where black = +1, white = -1) For the previous example, we can express the image with these new (normalized) basis vectors as: Coefficients of sum = projection of I onto new basis (dot product) These are the coordinates of the image in “Hadamard space”  We can also say that I has undergone a Hadamard transform H:Sinusoidal Basis Binary-valued, rectangular wave pattern of Hadamard basis doesn’t capture real image gradients well  Idea: Use smoothly-varying sinusoidal patterns at different frequencies, angles for basis imagesFourier Basis The Fourier basis uses the family of complex sinusoidal functions2D DFT Forward 2D DFT Inverse 2D DFT (u, v) are the frequency coordinates while (x, y) are the spatial coordinates M, N are the number of spatial pixels along the x, y coordinates∑∑−=−=+−=1010)//(2),(1),(MxNyNvyMuxjeyxfMNvuFπ∑∑−=−=+−=1010)//(2),(),(MuNvNvyMuxjevuFyxfπFourier BasisvReal(cos) partImaginary(sin) part(u, v) (1, 0) (0, 5)(1, 1)Fourier transform in Matlab Discrete, 2-D Fourier & inverse Fourier transforms are computed by fft2 and ifft2, respectively fftshift: Move origin (DC component) to image center for display Example:>> I = imread(‘test.png’); % Load grayscale image>> F = fftshift(fft2(I)); % Shifted transform>> imshow(log(abs(F)),[]); % Show log magnitude >> imshow(angle(F),[]); % Show phase anglePhase and Magnitude 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)Image pyramid representation Smoothing means removing high frequencies Smoothing required to avoid aliasing Fourier transform of a Gaussian is a Gaussian Convolution is a multiplication ÆGaussian suppresses high frequenciesImage from CS 223-B L9 by Richard SzeliskiGaussian Pyramid Downsampling: Cut width, height in half at each iteration:  Upsampling S↑(I): Double size of image, interpolate missing pixels Let the base (the finest resolution) of an n-level Gaussian pyramid be defined as P0= I. Then the ith level is reduced from the level below it by:Gaussian pyramidfrom Forsyth & PonceLaplacian pyramid The tip (the coarsest resolution) of an n-level Laplacian pyramid is the same as the Gaussian pyramid at that level: Ln(I) = Pn(I) The ith level is expanded from the level above according to Li(I) = Pi(I) − S↑(Pi+1(I)) Synthesizing the original image: Get I back by summing upsampled Laplacian pyramid levelsGaussian and Laplacian Gaussian – Smoothing pyramid Each level is a smoothed and decimated signal of the previous Laplacian – Band pass filter of the images Each level is the difference of a more smoothed and less smoothed imagecourtesy of WolframSummation Property If L0, L1L LNis the sequence of laplaciansLi= Gi– EXPAND[Gi+1], 0<i<NLN= GN The steps used to construct the Laplaciancan be reversed to get the original Expand Liand add it to Li-1to Gi-1G0= ∑i=0NLiApplications – Image MosaicingSeamless joining of images to get a larger viewMulti-resolution spline interpolationFrom the paper by Burt and AdelsonLaplacianlevel4Laplacianlevel2Laplacianlevel0left pyramid right pyramid blended pyramidImage mosaicing Automatic mosaicing Cross correlation to compute translation between images Matlab demo – Burt and Adelson’s paper http://www.cs.huji.ac.il/course/2003/impr/spline83.pdfimage Iimage JavJwwarp refineavaΔv+Pyramid of image J Pyramid of image Iimage Iimage JApplication - Coarse-to-Fine Estimationu=10 pixelsu=5 pixelsu=2.5 pixelsu=1.25 pixelsSlide from CS 223-B L9 by Richard SzeliskiGabor filters Gaussian windowed Fourier Transform Make convolution kernels from product of Fourier basis images and Gaussians×=Odd(sin)Even(cos)FrequencyTexture Representation: Filter Responses Choose a group of filters  Edge/Bar filters: Something like Gabor filters at different orientations, scales Spot filters: Center-surround filters like a Gaussian/difference of Gaussians at multiple scales Run filters over image to get a set of response images Each contains specific texture informationExample: Filter Responsesfrom Forsyth & PonceFilterbankInputimageTexture Similarity based on Response Statistics Collect statistics of responses over an image or subimage Mean of squared response Mean and variance of squared response Euclidean distance between vectors of response statistics for two images is measure of texture similarityConclusions 2D Fourier Theory Image pyramid representation Gaussian pyramid Laplacian pyramid Applications of Image Pyramids Image Mosaicing Gaussian + Laplacian pyramids (Burt and Adelson) Texture statistics Gabor