12. Fourier analysis andsampling theory2ReadingRequired: Watt, Section 14.1Recommended: Ron Bracewell, The Fourier Transform and Its Applications, McGraw-Hill. Don P. Mitchell and Arun N. Netravali,“Reconstruction Filters in ComputerComputer Graphics ,” Computer Graphics, (Proceedings of SIGGRAPH 88). 22 (4),pp. 221-228, 1988.3What is an image?We can think of an image as a function, f, from R2to R: f( x, y ) gives the intensity of a channel at position ( x, y ) Realistically, we expect the image only to be defined over a rectangle, with a finite range:• f: [a,b]x[c,d] Æ [0,1]A color image is just three functions pasted together. We can write this as a “vector-valued”function:We’ll focus in grayscale (scalar-valued) images for now.(, )(, ) (, )(, )rxyfxy gxybxy⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦4Images as functions5Digital imagesIn computer graphics, we usually create or operate on digital (discrete) images: Sample the space on a regular grid Quantize each sample (round to nearest integer)If our samples are ∆ apart, we can write this as:f[i ,j] = Quantize{ f(i ∆, j ∆) }6Motivation: filtering and resizingWhat if we now want to: smooth an image? sharpen an image? enlarge an image? shrink an image?Before we try these operations, it’s helpful to think about images in a more mathematical way…7Fourier transformsWe can represent functions as a weighted sum of sines and cosines.We can think of a function in two complementary ways: Spatially in the spatial domain Spectrally in the frequency domainThe Fourier transform and its inverse convert between these two domains:2() ( )isxFs f xe dxπ∞−−∞=∫2() ()isxfx Fse dsπ∞−∞=∫FrequencydomainSpatialdomain8Fourier transforms (cont’d)Where do the sines and cosines come in?f(x) is usually a real signal, but F(s) is generally complex: If f(x) is symmetric, i.e., f(x) = f(-x)), then F(s) = A(s). Why?2() ( )isxFs f xe dxπ∞−−∞=∫2() ()isxfx Fse dsπ∞−∞=∫FrequencydomainSpatialdomainπθ−=+=2()() () ()()isFs As iBsFse91D Fourier examples102D Fourier transform2( )(,) (,)xyisxsyxyFs s f xye dxdyπ∞∞−+−∞ −∞=∫∫2( )(,) ( , )xyisxsyxy x yfxy Fsse dsdsπ∞∞+−∞ −∞=∫∫FrequencydomainSpatialdomainSpatial domain Frequency domain(,)xyFs s(,)fxy112D Fourier examplesSpatial domainFrequency domain(,)xyFs s(,)fxy12ConvolutionOne of the most common methods for filtering a function is called convolution.In 1D, convolution is defined as:%() () ()(')( ') '(')(' ) 'gx f x hxfxhx xdxfxhx xdx∞−∞∞−∞=∗=−=−∫∫%≡−where ( ) ( ).hx h x13Convolution propertiesConvolution exhibits a number of basic, but important properties.Commutativity:Associativity:Linearity:∗∗=∗∗[() ()] () ()[() ()]ax bx cx ax bx cx()(() ()) () () () ()ax bx cx ax bx ax cx∗+=∗+∗∗=∗() () () ()ax bx bx ax∗⋅ =⋅ ∗()[ ()] [() ()]ax kbx k ax bx14Convolution in 2DIn two dimensions, convolution becomes:(,) (,) (,)( ', ') ( ', ') ' '(',')(' ,' ) ' 'gxy f xy hxyf x y h x x y y dx dyf x y h x x y y dx dy∞∞−∞ −∞∞∞−∞ −∞=∗=−−=−−∫∫∫∫%%where ( , ) ( , ).hxy h x y=−−*=f(x,y) h(x,y) g(x,y)15Convolution theoremsConvolution theorem: Convolution in the spatialdomain is equivalent to multiplication in the frequency domain.Symmetric theorem: Convolution in the frequency domain is equivalent to multiplication in the spatial domain.fh FH∗←⎯→⋅fh FH⋅←⎯→∗161D convolution theorem example172D convolution theorem example*f(x,y)h(x,y)g(x,y)|F(sx,sy)||H(sx,sy)||G(sx,sy)|18The delta functionThe Dirac delta function, δ(x), is a handy tool for sampling theory. It has zero width, infinite height, and unit area. It is usually drawn as:19Sifting and shiftingFor sampling, the delta function has two important properties.Sifting:Shifting:()( ) ()( )fx xa fa xaδδ−= −()()()fx x a fx aδ∗−=−20The shah/comb functionA string of delta functions is the key to sampling. The resulting function is called the shah or combfunction:which looks like:Amazingly, the Fourier transform of the shah function takes the same form:where so= 1/T.III() ( )nxxnTδ∞=−∞=−∑III() ( )onssnsδ∞=−∞=−∑21Now, we can talk about sampling.The Fourier spectrum gets replicated by spatial sampling!How do we recover the signal?Sampling22Sampling and reconstruction23Sampling and reconstruction in 2D24Sampling theoremThis result is known as the Sampling Theoremand is due to Claude Shannon who first discovered it in 1949:A signal can be reconstructed from its samples without loss of information, if the original signal has no energy in frequencies at or above ½ the sampling frequency.For a given bandlimited function, the minimum rate at which it must be sampled is the Nyquistfrequency.25Reconstruction filtersThe sinc filter, while “ideal”, has two drawbacks: It has large support (slow to compute) It introduces ringing in practiceWe can choose from many other filters…26Cubic filtersMitchell and Netravali (1988) experimented with cubic filters, reducing them all to the following form:The choice of B or C trades off between being too blurry or having too much ringing. B=C=1/3 was their “visually best” choice. The resulting reconstruction filter is often called the “Mitchell filter.”3232(12 9 6 ) ( 18 12 6 ) (6 2 ) 11( ) (( 6 ) (6 30 ) ( 12 48 ) (8 24 ) 1 260BCx BCx B xrx B Cx B Cx B Cx B C xotherwise⎧−− +−+ + +− <⎪⎪=−− ++ +−− ++ ≤<⎨⎪⎪⎩2 1.5 1 0.5 0 0.5 1 1.5 200.5127Reconstruction filters in 2DWe can also perform reconstruction in 2D…28AliasingSampling rate is too low29AliasingWhat if we go below the Nyquist frequency?30Anti-aliasingAnti-aliasing is the process of removing the frequencies before they alias.31We can fill the “magic” box with analytic pre-filtering of the signal:Why may this not generally be possible?Anti-aliasing by analytic prefiltering32Filtered downsamplingAlternatively, we can sample the image at a higher rate, and then filter that signal:We can now sample the signal at a lower rate. The whole process is called filtered downsampling or supersampling and averaging down.33Practical upsamplingWhen resampling a function (e.g., when resizing an image), you do not need to reconstruct the complete continuous function.For zooming in on a function, you need only use a reconstruction filter and evaluate as needed for each new sample.Here’s an
View Full Document
Unlocking...