1Sampling and Pyramids15-463: Rendering and Image ProcessingAlexei Efros…with lots of slides from Steve SeitzTodaySamplingNyquist RateAntialiasingGaussian and Laplacian Pyramids2Fourier transform pairsSamplingwSpatial domain Frequency domain1/wsamplingpatternsampledsignal3ReconstructionFrequency domain1/wwSpatial domainsincfunctionreconstructedsignalWhat happens whenthe sampling rate is too low?4Nyquist RateWhat’s the minimum Sampling Rate 1/w to get rid of overlaps?Frequency domain1/wwSpatial domainsincfunctionSampling Rate ≥ 2 * max frequency in the image• this is known as the Nyquist RateAntialiasingWhat can be done?Sampling rate ≥ 2 * max frequency in the image1. Raise sampling rate by oversampling• Sample at k times the resolution• continuous signal: easy• discrete signal: need to interpolate2. Lower the max frequency by prefiltering• Smooth the signal enough• Works on discrete signals3. Improve sampling quality with better sampling• Nyquist is best case!• Stratified sampling (jittering)• Importance sampling (salaries in Seattle)• Relies on domain knowledge5SamplingGood sampling:•Sample often or,•Sample wiselyBad sampling:•see aliasing in action!Gaussian pre-filteringG 1/4G 1/8Gaussian 1/2Solution: filter the image, then subsample• Filter size should double for each ½ size reduction. Why?6Subsampling with Gaussian pre-filteringG 1/4 G 1/8Gaussian 1/2Solution: filter the image, then subsample• Filter size should double for each ½ size reduction. Why?• How can we speed this up?Compare with...1/4 (2x zoom)1/8 (4x zoom)Why does this look so crufty?1/27Image resampling (interpolation)So far, we considered only power-of-two subsampling• What about arbitrary scale reduction?• How can we increase the size of the image?Recall how a digital image is formed• It is a discrete point-sampling of a continuous function• If we could somehow reconstruct the original function, any new image could be generated, at any resolution and scale 1 2 3 4 5d = 1 in this exampleImage resamplingSo far, we considered only power-of-two subsampling• What about arbitrary scale reduction?• How can we increase the size of the image?Recall how a digital image is formed• It is a discrete point-sampling of a continuous function• If we could somehow reconstruct the original function, any new image could be generated, at any resolution and scale 1 2 3 4 5d = 1 in this example8Image resamplingSo what to do if we don’t know 1 2 3 4 52.51d = 1 in this example• Answer: guess an approximation• Can be done in a principled way: filteringImage reconstruction• Convert to a continuous function • Reconstruct by cross-correlation:Resampling filtersWhat does the 2D version of this hat function look like?Better filters give better resampled images• Bicubic is common choiceWhy not use a Gaussian?What if we don’t want whole f, but just one sample?performs linear interpolation(tent function) performs bilinear interpolation9Bilinear interpolationSmapling at f(x,y):Image PyramidsKnown as a Gaussian Pyramid [Burt and Adelson, 1983]• In computer graphics, a mip map [Williams, 1983]• A precursor to wavelet transform10A bar in the big images is a hair on the zebra’s nose; in smaller images, a stripe; in the smallest, the animal’s noseFigure from David ForsythGaussian pyramid constructionfilter maskRepeat• Filter• SubsampleUntil minimum resolution reached • can specify desired number of levels (e.g., 3-level pyramid)The whole pyramid is only 4/3 the size of the original image!11Laplacian PyramidLaplacian Pyramid (subband images)Created from Gaussian pyramid by subtractionGaussian PyramidWhat are they good for?Improve Search• Search over translations– Like homework– Classic coarse-to-fine stategy• Search over scale– Template matching– E.g. find a face at different scalesPrecomputation• Need to access image at different blur levels• Useful for texture mapping at different resolutions (called mip-mapping) Image Processing• Editing frequency bands separetly• E.g. image blending… next
View Full Document
Unlocking...