Unformatted text preview:

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

UT CS 384G - Sampling and Reconstruction

Documents in this Course
Shading

Shading

27 pages

Shading

Shading

27 pages

Load more
Download Sampling and Reconstruction
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sampling and Reconstruction and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sampling and Reconstruction 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?