University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don FussellSampling and ReconstructionUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 2ReadingRequired:Watt, Section 14.1Recommended:Ron Bracewell, The Fourier Transform and ItsApplications, McGraw-Hill.Don P. Mitchell and Arun N. Netravali,“Reconstruction Filters in Computer ComputerGraphics ,” Computer Graphics, (Proceedingsof SIGGRAPH 88). 22 (4), pp. 221-228, 1988.University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 3What is an image?We can think of an image as a function, f, from R2 to R:f( x, y ) gives the intensity of a channel at position ( x, y )Realistically, we expect the image only to be defined over arectangle, with a finite range:f: [a,b]x[c,d] [0,1]A color image is just three functions pasted together. Wecan write this as a “vector-valued” function:We’ll focus in grayscale (scalar-valued) images for now.( , )( , ) ( , )( , )r x yf x y g x yb x y! "# $=# $# $% &University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 4Images as functionsUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 5Digital imagesIn computer graphics, we usually create or operate ondigital (discrete) images:Sample the space on a regular gridQuantize each sample (round to nearest integer)If our samples are Δ apart, we can write this as:f[i ,j] = Quantize{ f(i Δ, j Δ) }University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 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 helpfulto think about images in a moremathematical way…University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 7Fourier transformsWe can represent a function as a linear combination(weighted sum) of sines and cosines.We can think of a function in two complementary ways:Spatially in the spatial domainSpectrally in the frequency domainThe Fourier transform and its inverse convert betweenthese two domains:FrequencydomainSpatialdomain! F(s) = f (x)e"i 2#s x"$$%dx! f (x) = F(s)ei 2"sx#$$%dsUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 8Fourier transforms (cont’d)Where do the sines and cosines come in?f(x) is usually a real signal, but F(s) is generallycomplex:If f(x) is symmetric, i.e., f(x) = f(-x)), then F(s) =Re(s). Why?FrequencydomainSpatialdomain! F(s) = f (x)e"i 2#sx"$$%dx! f (x) = F(s)ei 2"sx#$$%ds! F (s) = Re(s) " i Im(s) = F (s) e"i 2#sUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 91D Fourier examplesUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 102D Fourier transformFrequencydomainSpatialdomainSpatial domain Frequency domain! F(sx,sy) = f (x, y)e"i 2#sxx"$$%"$$%e"i 2#syydxdy! f (x, y) = F(sx,sy)ei 2"sxx#$$%#$$%ei 2"syydsxdsy! f (x, y)! F(sx,sy)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 112D Fourier examplesSpatial domainFrequency domain! f (x, y)! F(sx,sy)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 12ConvolutionOne of the most common methods for filtering afunction is called convolution.In 1D, convolution is defined as:where ! ) h (x) = h("x) ! g(x) = f (x) * h(x)= f (" x )h(x #" x )d" x #$$%= f (" x )) h (" x # x)d" x #$$%University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 13Convolution propertiesConvolution exhibits a number of basic, butimportant properties.Commutativity:Associativity:Linearity:! a(x) " b(x) = b(x) " a(x)! [a(x) " b(x)]" c(x) = a(x) "[b(x) " c(x)]! a(x) "[k # b(x)] = k # [a(x) " b(x)]a(x) " (b(x) + c(x)) = a(x) " b(x) + a(x) " c(x)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 14Convolution in 2DIn two dimensions, convolution becomes:where*=f(x,y ) h(x ,y) g(x ,y) ! ) h (x, y) = h("x,"y) ! g(x, y) = f (x, y) " h(x, y)= f (# x ,# y )h(x $# x )(y $# y )d# x d# y $%%&$%%&= f (# x ,# y )) h (# x $ x)(# y $ y)d# x d# y $%%&$%%&University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 15Convolution theoremsConvolution theorem: Convolution in thespatial domain is equivalent tomultiplication in the frequency domain.Symmetric theorem: Convolution in thefrequency domain is equivalent tomultiplication in the spatial domain.! f " h # F $ H! f " h # F $ HUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 16Convolution theoremsTheoremProof (1))(*)()()()()*()(*)()()()()*(GFFGGFGFgffggfgf1-1-1-1-1-1-FFFFFFFFFFFF==== ! F( f * g) = f (" t )g(t #" t )d" t e#i$tdt#%%&#%%&= f (" t )g(t #" t )e#i$" t e#i$(t#" t )dtd" t #%%&#%%&= f (" t )g(" " t )e#i$" t e#i$" " t d" " t d" t #%%&#%%&= f (" t )e#i$" t d" t g(" " t )e#i$" " t d" " t #%%&#%%&= F( f )F(g)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 171D convolution theorem exampleUniversity of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 182D convolution theorem example*f(x,y )h(x ,y)g(x ,y)|F(sx,sy)||H(sx,sy)||G(sx,sy)|University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 19The delta functionThe Dirac delta function, δ(x), is a handytool for sampling theory.It has zero width, infinite height, and unitarea. It is usually drawn as:University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 20Sifting and shiftingFor sampling, the delta function has two importantproperties.Sifting:Shifting:! f (x)"(x # a) = f (a)"(x # a)! f (x) "#(x $ a) = f (x $ a)University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 21The 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 shahfunction takes the same form:where so = 1/T.! III(x) ="(x # nT)n= 0$%! III(s) ="(s # ns0)n= 0$%University of Texas at Austin CS384G - Computer Graphics Spring 2010 Don Fussell 22Now, we can talk about sampling.The Fourier spectrum gets replicated by spatial
View Full Document