Sampling and ReconstructionReadingWhat is an image?Images as functionsDigital imagesMotivation: filtering and resizingFourier transformsFourier transforms (cont’d)1D Fourier examples2D Fourier transform2D Fourier examplesConvolutionConvolution propertiesConvolution in 2DConvolution theoremsSlide 161D convolution theorem example2D convolution theorem exampleThe delta functionSifting and shiftingThe shah/comb functionSamplingSampling and reconstructionSampling and reconstruction in 2DSampling theoremReconstruction filtersCubic filtersReconstruction filters in 2DAliasingSlide 30Anti-aliasingAnti-aliasing by analytic prefilteringFiltered downsamplingPractical upsamplingSlide 35Practical downsampling2D resamplingNext class: Image ProcessingUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don FussellSampling and ReconstructionUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 2ReadingRequired:Watt, Section 14.1Recommended:Ron Bracewell, The Fourier Transform and Its Applications, McGraw-Hill.Don P. Mitchell and Arun N. Netravali,“Reconstruction Filters in Computer Computer Graphics ,” Computer Graphics, (Proceedings of SIGGRAPH 88). 22 (4), pp. 221-228, 1988.University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 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.( , )( , ) ( , )( , )r x yf x y g x yb x y⎡ ⎤⎢ ⎥=⎢ ⎥⎢ ⎥⎣ ⎦University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 4Images as functionsUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 5Digital imagesIn computer graphics, we usually create or operate on digital (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 Fall 2008 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 helpful to think about images in a more mathematical way…University of Texas at Austin CS384G - Computer Graphics Fall 2008 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 between these two domains:FrequencydomainSpatialdomain€ F(s) = f (x)e−i 2π sx−∞∞∫dx€ f (x) = F(s)ei 2π sx−∞∞∫dsUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 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 generally complex: 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) − iIm(s) = F(s)e−i 2π sUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 91D Fourier examplesUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 102D Fourier transformFrequencydomainSpatialdomainSpatial domain Frequency domain€ F(sx,sy) = f (x, y)e−i 2π sxx−∞∞∫−∞∞∫e−isπ syydxdy€ f (x, y)€ F(sx,sy)University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 112D Fourier examplesSpatial domainFrequency domain€ f (x, y)€ F(sx,sy)University of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 12ConvolutionOne of the most common methods for filtering a function 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 Fall 2008 Don Fussell 13Convolution propertiesConvolution exhibits a number of basic, but important 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 Fall 2008 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 Fall 2008 Don Fussell 15Convolution theoremsConvolution theorem: Convolution in the spatial domain is equivalent to multiplication in the frequency domain.Symmetric theorem: Convolution in the frequency domain is equivalent to multiplication in the spatial domain.€ f ∗ h ⇔ F ⋅H€ f ⋅h ⇔ F ∗ HUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 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 Fall 2008 Don Fussell 171D convolution theorem exampleUniversity of Texas at Austin CS384G - Computer Graphics Fall 2008 Don Fussell 182D convolution theorem
View Full Document
Unlocking...