Sampling and ReconstructionSampling and ReconstructionSampled representationsReconstruction1D Example: AudioSampling in digital audioSampling and ReconstructionUndersamplingUndersamplingUndersamplingAliasing in videoAliasing in imagesWhat’s happening?AntialiasingPreventing aliasingLinear filtering: a key ideaMoving AverageWeighted Moving AverageWeighted Moving AverageMoving Average In 2DCross-correlation filteringGaussian filteringMean vs. Gaussian filteringConvolutionConvolution is nice!Tricks with convolutionsImage half-sizingImage sub-samplingImage sub-samplingGaussian (lowpass) pre-filteringSubsampling with Gaussian pre-filteringCompare with...Gaussian (lowpass) pre-filteringImage PyramidsSlide Number 35What are they good for?Gaussian pyramid constructionContinuous convolution: warm-upContinuous convolutionOne more convolutionReconstructionResamplingResamplingCont.–disc. convolution in 2DA gallery of filtersBox filterSlide Number 47Slide Number 48Slide Number 49Effects of reconstruction filtersProperties of filtersRinging, overshoot, ripplesYucky detailsMedian filtersComparison: salt and pepper noise15-463: Computational PhotographyAlexei Efros, CMU, Fall 2008Most slides from Steve MarschnerSampling and ReconstructionSampling and Reconstruction© 2006 Steve Marschner • 3Sampled representations• How to store and compute with continuous functions?• Common scheme for representation: samples– write down the function’s values at many points[FvDFH fig.14.14b / Wolberg]© 2006 Steve Marschner • 4Reconstruction• Making samples back into a continuous function– for output (need realizable method)– for analysis or processing (need mathematical method)– amounts to “guessing” what the function did in between[FvDFH fig.14.14b / Wolberg]1D Example: Audiolow highfrequencies© 2006 Steve Marschner • 6Sampling in digital audio• Recording: sound to analog to samples to disc• Playback: disc to samples to analog to sound again– how can we be sure we are filling in the gaps correctly?© 2006 Steve Marschner • 7Sampling and Reconstruction• Simple example: a sign wave© 2006 Steve Marschner • 8Undersampling• What if we “missed” things between the samples?• Simple example: undersampling a sine wave– unsurprising result: information is lost© 2006 Steve Marschner • 9Undersampling• What if we “missed” things between the samples?• Simple example: undersampling a sine wave– unsurprising result: information is lost– surprising result: indistinguishable from lower frequency© 2006 Steve Marschner • 10Undersampling• What if we “missed” things between the samples?• Simple example: undersampling a sine wave– unsurprising result: information is lost– surprising result: indistinguishable from lower frequency– also was always indistinguishable from higher frequencies– aliasing: signals “traveling in disguise” as other frequenciesAliasing in videoSlide by Steve SeitzAliasing in imagesWhat’s happening?Input signal:x = 0:.05:5; imagesc(sin((2.^x).*x))Plot as image:Alias!Not enough samplesAntialiasingWhat can we do about aliasing?Sample more often• Join the Mega-Pixel craze of the photo industry• But this can’t go on foreverMake the signal less “wiggly”• Get rid of some high frequencies• Will loose information• But it’s better than aliasing© 2006 Steve Marschner • 15Preventing aliasing• Introduce lowpass filters:– remove high frequencies leaving only safe, low frequencies– choose lowest frequency in reconstruction (disambiguate)© 2006 Steve Marschner • 16Linear filtering: a key idea• Transformations on signals; e.g.:– bass/treble controls on stereo– blurring/sharpening operations in image editing– smoothing/noise reduction in tracking• Key properties– linearity: filter(f + g) = filter(f) + filter(g)– shift invariance: behavior invariant to shifting the input• delaying an audio signal• sliding an image around• Can be modeled mathematically by convolution© 2006 Steve Marschner • 17Moving Average• basic idea: define a new function by averaging over a sliding window• a simple example to start off: smoothing© 2006 Steve Marschner • 18Weighted Moving Average• Can add weights to our moving average• Weights […, 0, 1, 1, 1, 1, 1, 0, …] / 5© 2006 Steve Marschner • 19Weighted Moving Average• bell curve (gaussian-like) weights […, 1, 4, 6, 4, 1, …]© 2006 Steve Marschner • 20Moving Average In 2DWhat are the weights H?0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 90 90 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 90 0 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 0 0 0 0 0 0 00 0 90 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0Slide by Steve Seitz© 2006 Steve Marschner • 21Cross-correlation filtering• Let’s write this down as an equation. Assume the averaging window is (2k+1)x(2k+1):• We can generalize this idea by allowing different weights for different neighboring pixels:• This is called a cross-correlation operation and written: • H is called the “filter,” “kernel,” or “mask.”Slide by Steve Seitz22Gaussian filteringA Gaussian kernel gives less weight to pixels further from the center of the windowThi k l i i ti f G i f ti0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 90 90 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 90 0 90 90 90 0 00 0 0 90 90 90 90 90 0 00 0 0 0 0 0 0 0 0 00 0 90 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 01 2 12 4 21 2 1Slide by Steve Seitz23Mean vs. Gaussian filteringSlide by Steve SeitzConvolutioncross-correlation:A convolution operation is a cross-correlation where the filter is flipped both horizontally and vertically before being applied to the image:It is written: Suppose H is a Gaussian or mean kernel. How does convolution differ from cross-correlation?Slide by Steve Seitz© 2006 Steve Marschner • 25Convolution is nice!• Notation:• Convolution is a multiplication-like operation– commutative– associative– distributes over addition– scalars factor out– identity: unit impulse e = […, 0, 0, 1, 0, 0, …]• Conceptually no distinction between filter and signal• Usefulness of associativity– often apply several filters one after another: (((a * b1 ) * b2 ) * b3 )– this is equivalent to applying one filter: a * (b1 * b2 * b3 )Tricks with convolutions=Image half-sizingThis image is too big tofit on the
View Full Document