[PDF] Introduction to two-dimensional Fourier analysis

[PDF] 2D Fourier Transform - DiUnivrIt

Signals as functions (1D, 2D) – Tools • 1D Fourier Transform – Summary of definition and properties in the different cases • CTFT, CTFS, DTFS, DTFT • DFT

[PDF] 2-D Fourier Transforms

2D FT • Fourier Transform for Discrete Time Sequence (DTFT) – 1D DTFT Property – All the properties of 1D FT apply to 2D FT Yao Wang, NYU-Poly

[PDF] Lecture 2: 2D Fourier transforms and applications

Fourier transforms and spatial frequencies in 2D the 1D Fourier analysis with which you are familiar As in the 1D case FTs have the following properties

Introduction to two-dimensional Fourier analysis

Several properties of the Fourier transform are of interest in two-dimensional Fourier analysis of images Specifically, translation, rotation, distributivity, scaling, correlation, and convolution properties will be discussed

Fourier Transform Tables

We also use the elementary properties of Fourier transforms to extend some of the results form DFTs Table A 6 collects several two-dimensional transforms

[PDF] Discrete Fourier Transform - WPI Computer Science (CS) Department

Properties of 2D Fourier Transform ○ All properties of 1D Fourier transform apply + additional properties ○ Similarity: Forward and inverse transforms are 

[PDF] Fourier transform, in 1D and in 2D

where O is a local neighborhood of a 'current position' i and h is the convolution kernel (also convolution mask) Page 12 12/65 Fourier Tx, properties (1)

[PDF] Properties of the Fourier Transform - School of Physics and Astronomy

equivalent to multiplying its Fourier transform by a circularly symmetric quadratic of −4π2w2 The two dimensional Fourier Transform F(u,v), of a function f(x,y) is a  

TWO-DIMENSIONAL FOURIER TRANSFORMS - ScienceDirectcom

consider the properties of their two-dimensional Fourier transform Spatial aliasing and anti-aliasing criteria are discussed Finally, it is shown that any

[PDF] Some Properties of Fourier Transform

3 mar 2008 · ELEC 8501: The Fourier Transform and Its Applications One consequence of the two-dimensional rotation theorem is that if the 2D function is 

[PDF] 2d heat equation derivation

[PDF] 2d image to 3d model python

[PDF] 2d picture to 3d model

[PDF] 2d to 3d conversion image processing

[PDF] 2eme couronne parisienne

[PDF] 2nd order polynomial equation

[PDF] 2nd tier entitlement calculator

[PDF] 2p france x reader

[PDF] 2p france x reader deviantart

[PDF] 2p france x reader fluff

[PDF] 2p france x reader lemon

[PDF] 2p france x reader lemon forced

[PDF] 2p france x reader tumblr

[PDF] 3 avenue de paris 78000 versailles

[PDF] 3 basic laws of logarithms

BehaviorResearchMethods&Instrumentation

1983, Vol.15(2),308-318

SESSIONX

ANINTRODUCTIONTOTWO-DIMENSIONAL

FASTFOURIERTRANSFORMSAND

THEIRAPPLICATIONS

Introductiontotwo-dimensional

Fourieranalysis

M. S. RZESZOTARSKI

F. L. ROYER

and

G. C.GILMORE

The application of two-dimensional Fourier analysis provides new avenues for research in visual perception. Thistutorialserves as anintroductionto some of the methods used in two-dimensionalFourier analysis and anintroductionto two-dimensionalimage processing in general.

Two-dimensionalFourieranalysis is apowerfultool

thathas seen increasingpopularity inrecentyears due to rapidadvancementsin digital image processinghardware.

Thepurposeofthispaperis topresentanintroduction

totwo-dimensionalFourieranalysis usingnumerous presentationserves as anintroductiontotwo-dimensional image processing using thetwo-dimensionalFourier transformas atoolto achieve thattend.Specificappli cations ofFourieranalysis topsychologyare covered byRoyer,Rzeszotarski,and Gilmore(1983).DIGITAtIMAGEREPRESENTAnONS

Animage can bedescribedmathematicallyas some

functionf(x,y), where x and yarethespatialcoordi nates ofthepictureand f(x,y)representsthebrightness ofthe image at thepoint(x,y).Computersworkwith digital images inwhichf(x,y)is afunctionwithnumeric values for x, y, andbrightness.Thebrightnessis referredTheauthorwishes to thank LotteJacobifor the useofthe photograph ofAlbert Einstein.Requestsforreprintsshould be addressedto Fred

L.Royer,ResearchLaboratory151B, VA

MedicalCenter,Brecksville, Ohio44141.This work was sup portedby NIA Grant RO1 AG 03178-01 and by the VA Medical

Research Service.

to as the gray level in digital images, and eachelementin the image is called apictureelement,or pixel forshort.

Atypicaldigital image maycontaina

256
by 256 matrixor larger,witha fixednumberofgray levels.

The gray levelrepresentstheamount

oflightthatis transmittedthrougha filmcontainingthe image.Typical ranges ofgray levels are from 0 to255,representinga percenttransmittancethroughthe film offrom .1%to 100%.

Figure

Iashows an image in digital formwith256

gray levels and amatrixsize of256by256 pixels.

Figures 1

b-Idillustratewhathappensif one samples larger. Theabilityto resolve finedetailis lost in Fig ure Id andreducedin Figure Ic. One must sample an image so thattherequireddetailispresentin the digital image. In thisexample,if one is trying todetecteye balls, thenFigure Ic may havesufficientresolution,but if onewants toexaminethedetailsin the hair, one must usemuchfiner sampling(FigureIa inourexample).

The sampling rate isdetermined

byhowmuchdetail one mustretainin an image inorderto see theobjects ofinterest.Clearly,therearetradeoffshere. The maxi mum image size isdeterminedby available digital memory,whereastheminimumimage size isdetermined by therequiredresolution. 308

Copyright1983PsychonomicSociety,Inc.

INTRODUCTIONTOTWO·DIMENSIONALFOURIERANALYSIS 309 Figure I. Digital images with 256 by 256 samples, 64 by 64 samples, 32 by 32 samples, and 16 by 16 samples, each with

256 gray levels.

Figure 2. Digital image with 256 by 256 samples and 32 gray levels,8 gray levels,4 gray levels,and 2 gray levels.

Anotherfactorinstoringadigitalimage is howmany

gray levelsshouldbestoredfor eachpictureelement. The images shown inFigures2a·2dillustratestoragein

32, 8, 4, and 2 gray levels.Note

thatFigure Ia,which has

256gray levels,looksessentiallythesame as Fi

ure 2a. Thehumanvisualsystemcan detectonlyabout

50 gray levels, sotheuseof256isbeyondthe rangeof

humanvisualsystemdetection.As onereducesthe numberofgray levels in an image.contouringbecomes evident.startingwith Figure 2b. The image isbroken intoregions ofconstantgray level. which mayproduce undesirableartifactsin the resulting image. As the numberofgray levels isreduced,thenumberofbitsof digital storage is alsogreatlyreduced.In Figure Ia. thereare16.78million bits ofdigitalinformationin the256 gray-level 256 by 256 image. If a 128 by 128 image size with only 32 gray levels is used. then only .5 million bits arerequired.Inapplicationsillustratedin thispaper.the images allcontain256 gray levels and use amatrixsize of256 by 256.

IMAGE PROCESSING HARDWARE

Theprocess

ofconvertingaphotographor drawing to digital formrequiressometype ofdigital image processingsystem. Atypicalsystemconsists ofan imagedigitizer,a digitalcomputer,a massstoragedevice. and adisplaydevice for output.Thedigitizationhard ware can be a televisioncamerasystem,arotatingdrum filmscanner,or an x,ydigitizer.if simple line drawings are used asinputimages. Mostminicomputerscan performthe analysis ofdigital images,althoughSOmeare tailoredfor thispurposeand workmuchmoreefficiently thanothers.Theoutputdevice can be a videomonitor (television)or arotatingdrumscanner.Adrumscanner rotatesunder computercontrol,and the lightintensity throughthe film atdiscretecoordinatesisrecordedin digital form onmagnetictape as thedrumspins and stepsacross the film.

Foroutput,a negative ismounted

in alight-tightboxthatisthenexposedby abeam of modulatedlight usingthedigitaldataonmagnetictape todeterminethemodulation.A video monitoris com monlyused for outputin imageprocessingapplications. The monitorcan bephotographed,asillustratedby most ofthephotoscontainedin thispaper,or it can be used directlyas the viewing screen.

TWO·DIMENSION

FOURIERTRANSFORMS:

ANINTUITIVEINTRODUCTION

Theprinciple

ofFourieranalysis is based on the premise thatany image(orsignal ifone-dimensional)can beequivalentlyrepresentedin twodifferentdomains, aspatial(ortime)domainand afrequencydomain.

Fourierstatedthatone canperformalineartransfor

mationbetweenthe twodomainsand stillmaintainthe uniqueness ofthe image(orsignal).Ifyou have a one dimensionaltimedomainsignalrepresentedby some numberofsamples N,thenyou canequivalentlyrepre sent thatsignal in thefrequencydomainusing sines and cosines ofvaryingfrequencieswithNsamplesrepre senting theamplitudesoftheindividualsine and cosine components.In twodimensions,therepresentationis thesame,exceptthereare N by Nsamples.Thistrans formationbetweenthe twodomainshas someadditional advantagesdue to changes in some ofthepropertiesof

310RZESZOTARSKl,ROYER,ANDGILMORE

Figure 5. Rectangular pulse image with two sinusoids summed. frequencyinformationto represent it. This is an impor tantconceptthatwill have implications in later dis cussions.

Theextensionto two dimensions is complicated by

the multiplicative nature oftwo-dimensional images. In this case, the sinusoids in thehorizontaldirection are summed as are those in the verticaldirection,and the resulting image value at somepointis theproduct of

these two sumsofsinusoids. This can bebetterunder-Figure 3. Sine-wavegrating image, 512by512 samples.

images (or signals) when working in one domain or the other.

The two-dimensionalFouriertransformisdifficult

tocomprehendat first glance, butit can bebetter understoodin terms of some simple examples using images withinformationin only onedirection(one dimensional images).These aresimilarto one-dimensional signals, and the Fouriertransformswill be familiar to one who has worked with one-dimensional signals. An example of a one-dimensional image is thesine-wave gratingillustratedin Figure 3. The image varies in gray level sinusoidally across the image butisconstantin the vertical direction. This represents an image with fre- "quencycontentin only onedirection,andwithonly one frequencycomponentpresent. We can examine

Fourier'sprinciple byconstructinga familiar image

using the summation of various sinusoids. Let us con structa one-dimensional rectangular pulse image in which we have a region ofbrightnesscorrespondingto the positive part of the pulse and two dark regions representing the negativeportionsof the rectangular Figure 4. Rectangular pulse image with one sinusoid (funda- pulse. This can beconstructedby summingtogetheramental). seriesofsinusoids with varying frequencies and ampli- tudes. Figures 4-7 illustrate the successivesummation of sinusoids. The upper curve in the images shows the resulting gray-level proftle across the image. The result ing image looks more and more like a rectangular pulse as higher frequency sinusoids are added in. Notethatthe high-frequencycomponentshave the most effect on the transitionregionbetweenblack and white. In an image, regions ofrapidly changing gray scale are referred to as edges, and it is the edgeinformation thatrequires high- .._;.--.#':' . ; -;0,:/\::::/\ , iV\J •••c ...,.:::::> c:::::::'. direction. tion of frequency components in each direction. The lower left quadrants of Figures

9-12show the sinusoid

currently being added to the images.whereas the upper left and lower left and lower right quadrants illustrate the summation in one dimension, as shown previously. The upper right image is the resulting product of the upper left and lower right images(which are sums of sinusoidsin one direction) and showsthe development of this bright square asmore and more sinusoidsare added. summed. stood by exammmg Figure 8, in which an image is illustrated with only one frequency component in each direction. In this case, the image is dark wherever one ofthe cosines is negative, and the image is bright if the two cosines are positive. In a typical image, there are many sinusoids in each direction so the image is far more complex. An example ofthis summation is illu strated in Figures

9-12,inwhich an imageconsistingofa

sum ofsinusoids in both directions is illustrated. The resulting image is a bright square surrounded by a dark background. The figures illustrate thesuccessiveaddi-direction.

312RZESZOTARSKI,ROYER,ANDGILMORE

thedistributionofamplitudes using the sumofthe squared amplitudes for the sines and cosines at each frequency. This is referred to as the magnitude squared response and is directly related to the energy ofthe image at a given frequency. In the one-dimensional case, a plot of the magnitude squared vs. frequency is often provided so one candeterminewhere the energy in a signal is located. When working with images, one has two-dimensionalinformationthat cannot easily be represented graphically. As a result, one commonly displays the energy spectrum as an image in which the brighterregions ofthe image correspond to higher energies.Furtherdetails ofthis display are provided later.

Tobetterunderstandthe Fourier energy spectrum,

several one-dimensional examples will be examined first. Figure 13 shows twosine-wavegratings on the left as the spatial domain images, and two energy spectra on the right, representing the frequency domain image.

Since each

ofthe grating images contain only a single frequencycomponent,one would expect to see only a single bright spot corresponding tothatfrequency.

However, the Fourierrepresentation

ofa signal yields bothpositive and negative frequencyinformation,so thesine-wavefrequencycomponentis split equally betweenthe positive and negativecomponents.The bright spot inthecentercorresponds to the zero frequency location in the image, or in our case, the mean luminance of the image, which is positive for any image (unless it istotallyblack). Horizontalsine-wavegratings yield ahorizontalspectrum,and vertical gratings yield a vertical spectrum. Also, thesine-wavegrating with higher frequencycontent(moresine-wavecycles in the image) has itscomponentsdisplacedfurtherfrom the de

The frequency domainrepresentation

ofan imageor signal is frequently displayed as an energyspecturm. Since one has a series of sines and cosines with varying Figure 12. Square pulse image using 25 sinusoids in each amplitudes at each frequency, it is useful to representdirection.

THEFOURIERENERGYSPECTRUM

FigureII.Square pulse image using three sinusoids in each direction.Figure 10. Square pulse image using two sinusoids in each direction.

The basictheoryofthetwo-dimensionalFourier

transformispresentedwith a fewequationsand many

TWO-DIMENSIONALFOURIER

TRANSFORMS:THEORY

issignificant.Thecentralpointis againthedc or mean luminance ofthe image. Since theFouriertransform yields bothpositive and negativefrequencies,we must explainthepresence offour pairsoffrequencycom ponents.These can beexplainedif we indulge in some mathematicstodescribethe process. In the Xdirection, thesignal isoftheformA(l-cos(x)).whereA is the mean value for thatparticulardirection,and in the Y direction.B(l -cos(y)).Since we have amultiplica tive process. the result is some A(

J -cos(x))times

B(l cos(y)),which with somemanipulationyields

AB(l-cos(x)-cos(y)

+cos(xy)/2+cos(x+y)/2).

Themathis

notsoimportantas is the findingthatwe now obtainfour pairsoffrequencycomponentsin the energyspectrum.Two pairs ofcomponentsare in the respectivedirections ofthe original cosines in the spatialimage, and two sum anddifferencepairs arise due to themultiplicativenature ofthe process.

Atypicalimagecontainsmanyfrequencycom

ponentsin eachorientation,so the resulting energy spectrumis fairlycomplex.We cantakealookat the squarepulse as anexampleofa morecompleximage thatis still simpleenoughtounderstand.Figure15 illustratesthe energyspectrumfor bothan ideal square pulse and a square pulseconstructedwithonlya few frequencycomponents.The energyspectrumfor the information.The idealsquarepulsecontainsenergy all thewayoutto the highest resolvablefrequency. Figure 13. Sine-wavegratings and their energy spectra. Figure 14. Image andspectrumusing one sinusoid in each direction. orzero-frequencypoint.Thehighestfrequencyone can achieve is thecaseinwhichthegratingconsistsofalter natingrows ofblackandwhitelines, andtheresulting spectrumislocatedat theendsoftheenergyspectrum lines in thespectralimages.

Theextension

ofenergyspectrato twodimensionsis straightforwardif onekeepsinmind thatit is now a multiplicativeprocess. Figure 14 shows aspatialimage in thelowerleftthatconsistsoftheproductoftwo single frequencies,one ineachdirection.Thecorresponding energyspectrumisillustratedin theupperright. NoteFigure 15. Square pulse andspectrum,ideal and limited thatthereare ninediscretepointsatwhichtheenergynumberofsinusoids cases.

314RZESZOTARSKI,ROYER, AND GILMORE

examples ofthe images and energyspectrathatare obtainedwhen one examines some ofthepropertiesof theFouriertransform.For more detailedmathematics, refer to Andrews(1978),Brigham(1974),Daintyand

Shaw(1974),Gonzalez and Wintz(1977),Huang

(1975),Oppenheimand Schafer(1975),Rabiner and

Gold(1975),and Rosenfeld and Kak(1976).

The discretetwo-dimensionalFouriertransform

ofan image f(x,y) is

F(u,v) =

N-1N-1

I/N 2 f(x,y) EXP[-j21T(ux/N+vy/N)),(1) x=o y=O theFouriertransformenables rapidcomputationsince only 2None-dimensionalFouriertransformationsare required,and these can becomputedusing a fastFourier transformalgorithm. Amatrixtransposeis usually performedbetweentransformphases, so only row transformsare done. The resultingFouriertransform matrixis complex, requiring twofloating-pointN by N matrices(unless clever storage schemes areemployed). The individualFouriertransformsare very fast, and the major speedlimitationsare due tomatrixstorage and transpositionproblems.

The inverseFouriertransformalso exists and is

defined by where it is assumed the image is ofsize N by N suchthat f(x,y) is defined for x =0,1, 2,..., N - 1 and y =

0, 1, 2,

..., N - 1, and j is assumed to be the square root of-1.The complexexponentialhas been repre sented here as asummation ofcosines and sines at varying frequencies. Thetransformcan befactoredinto a separable formthatiscomputationallymore appealing.

Itis equivalent toEquation1mathematicallyand is

TRANSFORMPROPERTIES

Itis used totransforman image from the frequency

domainback into the spatialdomain.The inverse trans form can also beconvertedto a moreefficientform, similar toEquation2, enablingefficientcomputation. InverseFouriertransformscan also be used toconstruct images by specifying only thefrequencycomponents thatare to be included. Figures 3-15illustrateexamples thatcan beconstructedusing inversetransformations (i.e.,startingwithaFourierspectrum). N-1

F(u,v) =1/N

2

EXP[-j21Tux/N)

x=O N-l f(x,y)EXP[-j21Tvy/N). y=O (2) f(x,y) =

N-1N-1

F(u,v)EXPfj21T(ux/N+vy/N)).

u=O v=O (3) The resultingFouriertransformF(u,v) is defined for u=O,1,2,...,N-landv=O,1,2,...,N-l, where u and v arefrequencyindexes. The samples in the original image are spaced some dx in distance apart along the x-axis,The y-axis samples are also spaced some dx in distance apart (equal x and y sample spacing).

In thefrequencydomain, the frequencycomponentsare

spaced du apart, where du is defined as(1/N)dx.(The same expression applies to dv.) The sample spacing establishes theresolutionin frequency one can achieve.

For example, toattainbetterfrequencyresolution

(smaller du), one musteithertake more samples(increase N) or sample more flnely(reducesample spacing dx).

This hasimplicationsthatwill be discussed later.

While theequationsappearcomplicatedat first,they

can bemanipulated(Rabiner &Gold, 1975) to make them more manageable. If we make use ofthe separa bilitydemonstratedinEquation2, then the two dimensionaldiscreteFouriertransformcan becomputed by doing two sets ofone-dimensionaltransforms.This simplifies things to thepoint thatalmost any small minicomputercan perform thetransformationsif enoughmemoryis available. Onecomputesthe trans form (orinversetransform)by first doingone-dimensional transformsalong each row in the imagematrix.Then eachcolumn ofthematrixthatwas previously row transformedis againFouriertransformed,yielding the of

In thefrequencydomain,thereare anumberof

propertiesthatmake theFouriertransforma usefultool.

Here, the basictransform propertiesareexaminedto

betterunderstandwhathappensin eachofthe domains.

TheFouriertransform

ofan image isoftenreprequotesdbs_dbs19.pdfusesText_25