Dr. D. J. Jackson Lecture 9-1Electrical & Computer EngineeringComputer Vision &Digital Image ProcessingFourier Transform Properties, the Laplacian, Convolution and CorrelationDr. D. J. Jackson Lecture 9-2Electrical & Computer EngineeringPeriodicity of the Fourier transform• The discrete Fourier transform (and its inverse) are periodic with period N.F(u,v) = F(u+N,v) = F(u,v+N) = F(u+N,v+N)• Although F(u,v) repeats itself infinitely for many values of u and v, only N values of each variable are required to obtain f(x,y) from F(u,v)– i.e. Only one period of the transform is necessary to specify F(u,v) in the frequency domain.– Similar comments may be made for f(x,y) in the spatial domainDr. D. J. Jackson Lecture 9-3Electrical & Computer EngineeringConjugate symmetry of the Fourier transform• If f(x,y) is real (true for all of our cases), the Fourier transform exhibits conjugate symmetryF(u,v)=F*(-u,-v)or, the more interesting|F(u,v)| = |F(-u,-v)|where F*(u,v) is the complex conjugate of F(u,v)Dr. D. J. Jackson Lecture 9-4Electrical & Computer EngineeringImplications of periodicity & symmetry• Consider a 1-D case:– F(u) = F(u+N) indicates F(u) has a period of length N– |F(u)| = |F(-u)| shows the magnitude is centered about the origin• Because the Fourier transform is formulated for values in the range from [0,N-1], the result is two back-to-back half periods in this range• To display one full period in the range, move (shift) the origin of the transform to the point u=N/2Dr. D. J. Jackson Lecture 9-5Electrical & Computer EngineeringPeriodicity propertiesFourier spectrumwith back-to-backhalf periods in therange[0,n-1]Shifted spectrumwith afull periodin thesame rangeDr. D. J. Jackson Lecture 9-6Electrical & Computer EngineeringPeriodicity properties: 2-D ExampleDr. D. J. Jackson Lecture 9-7Electrical & Computer EngineeringDistributivity & Scaling• The Fourier transform (and its inverse) are distributive over addition but not over multiplication• So,• For two scalars a and b,)},({)},({)},(),({2121yxfyxfyxfyxfℑ+ℑ=+ℑ)},({)},({)},(),({2121yxfyxfyxfyxfℑ×ℑ≠×ℑ)/,/(1),(),(),(bvauFabbyaxfvuaFyxaf⇔⇔Dr. D. J. Jackson Lecture 9-8Electrical & Computer EngineeringAverage Value• A widely used expression for the average value of a 2-D discrete function is:• From the definition of F(u,v), for u=v=0,• Therefore,∑∑−=−==10102),(1),(NxNyyxfNyxf∑∑−=−==1010),(1)0,0(NxNyyxfNF)0,0(1),( FNyxf =Dr. D. J. Jackson Lecture 9-9Electrical & Computer EngineeringThe Laplacian• The Laplacian of a two variable function f(x,y) is given as:• From the definition of the 2-D Fourier transform,• The Laplacian operator is useful for outlining edges in an image22222),(yfxfyxf∂∂+∂∂=∇{}),()()2(),(2222vuFvuyxf +−⇔∇ℑπDr. D. J. Jackson Lecture 9-10Electrical & Computer EngineeringThe Laplacian: Matlab example% Given F(u,v), use the Laplacian% to construct an edge outlined% representation of the f(x,y)[f,fmap]=bmpread('lena128.bmp');F=fft2(f);Fedge=zeros(128);for u=1:128for v=1:128Fedge(u,v)=-(2*pi).^2*(u.^2+v.^2)*F(u,v);endendfedge=ifft2(Fedge);image(real(fedge));colormap(gray(256);Dr. D. J. Jackson Lecture 9-11Electrical & Computer EngineeringConvolution & Correlation• The convolution of two functions f(x) and g(x) is denoted f(x)*g(x) and is given by:• Where α is a dummy variable of integration.• Example: Consider the following functions f(α ) and g(α )∫+∞∞−−=αααdxgfxgxf )()()(*)(11α11/2αg(α)f(α)Dr. D. J. Jackson Lecture 9-12Electrical & Computer Engineering1-D convolution example• Compute g(-α) by folding g(α) about the origin• Compute g(x-α) by displacing g(-α) by the value x1-11/2αg(α)1/2αg(−α)-11/2αg(−α)-11/2αg(x−α)xDr. D. J. Jackson Lecture 9-13Electrical & Computer Engineering1-D convolution example (continued)• Then, for any value x, we multiply g(x-α) and f(α) and integrate from -∞ to +∞• For 0≤x ≤ 1 we have For 1 ≤ x ≤ 2 we have11αf(α)g(x- α)11αf(α)g(x- α)Dr. D. J. Jackson Lecture 9-14Electrical & Computer Engineering1-D convolution example (continued)• Thus we have• Graphically,.211002/12/)(*)(elsewherexxxxxgxf ≤≤≤≤⎪⎩⎪⎨⎧−=11/2xf(x)*g(x)2Dr. D. J. Jackson Lecture 9-15Electrical & Computer EngineeringConvolution and impulse functions• Of particular interest will be the convolution of a function f(x) with an impulse function δ(x-x0)• The functionδ(x-x0) may be viewed as having an area of unity in an infinitesimal neighborhood around x0and 0 elsewhere. That is∫+∞∞−=− )()()(00xfdxxxxfδ∫∫+∞∞−+−=−=−001)()(00xxdxxxdxxxδδDr. D. J. Jackson Lecture 9-16Electrical & Computer EngineeringConvolution and impulse functions (continued)• We usually say that δ(x-x0) is located at x=x0and the strength of the impulse is given by the value of f(x) at x=x0• If f(x)=A then, Aδ(x-x0) is impulse of strength A at x=x0.• Graphically this is:x0xAδ(x-x0)ADr. D. J. Jackson Lecture 9-17Electrical & Computer EngineeringConvolution with an impulse function• Given f(x) is• and g(x)=δ(x+T)+ δ(x)+ δ(x-T)αAαf(α)T xg(α)-TDr. D. J. Jackson Lecture 9-18Electrical & Computer EngineeringConvolution with an impulse function (continued)• f(x)*g(x) isαAxΤ−ΤDr. D. J. Jackson Lecture 9-19Electrical & Computer EngineeringConvolution and the Fourier transform• f(x)*g(x) and F(u)G(u) form a Fourier transform pair• If f(x) has transform F(u) and g(x) has transform G(u) then f(x)*g(x) has transform F(u)G(u)• These two results are commonly referred to as the convolution theorem)(*)()()()()()(*)(uGuFxgxfuGuFxgxf⇔⇔Dr. D. J. Jackson Lecture 9-20Electrical & Computer EngineeringFrequency domain filtering• Enhancement in the frequency domain is straightforward– Compute the Fourier transform– Multiply the result by a filter transform function– Take the inverse transform to produce the enhanced image• In practice, small spatial masks are used considerably more than the Fourier transform because of their simplicity of implementation and speed of operation• However, some problems are not easily addressable by spatial techniques– Such as homomorphic filtering and some image restoration techniquesDr. D. J. Jackson Lecture 9-21Electrical & Computer EngineeringLowpass frequency domain filtering• Given the following relationship• where F(u,v) is the Fourier transform of an image to be