CMSC 635Aliasing in imagesAliasing in animationAliasingAbstract Vector SpacesSlide 6Vectors and Discrete FunctionsSlide 8Slide 9Vectors and FunctionsSlide 11Function BasesFourier TransformsConvolutionFilteringIdealSamplingReconstructionFiltering, Sampling, ReconstructionSlide 20AntialiasingAnalytic higher order filteringAnalytic Area SamplingSupersamplingAdaptive samplingStochastic samplingWhich filter kernel?Slide 28ResamplingCMSC 635CMSC 635Sampling and AntialiasingSampling and AntialiasingAliasing in imagesAliasing in imagesQuickTime™ and aBMP decompressorare needed to see this picture.Aliasing in animationAliasing in animationAliasingAliasingHigh frequencies alias as low frequenciesHigh frequencies alias as low frequenciesAbstract Vector SpacesAbstract Vector SpacesAdditionC = A + B = B + A(A + B) + C = A + (B + C)given A, B, A + X = B for only one XScalar multiplyC = a Aa (A + B) = a A + a B(a+b) A = a A + b AAdditionC = A + B = B + A(A + B) + C = A + (B + C)given A, B, A + X = B for only one XScalar multiplyC = a Aa (A + B) = a A + a B(a+b) A = a A + b AAbstract Vector SpacesAbstract Vector SpacesInner or Dot Productb = a (A • B) = a A • B = A • a BA • A ≥ 0; A • A = 0 iff A = 0A • B = (B • A)*Inner or Dot Productb = a (A • B) = a A • B = A • a BA • A ≥ 0; A • A = 0 iff A = 0A • B = (B • A)*Vectors and Discrete FunctionsVectors and Discrete FunctionsGeometric Vector Discrete FunctionVector V = (1, 2, 4) V[I] = {1, 2, 4}InterpretationLinearity a V + b U a V[I] + b U[I]Dot Product V • U ∑ (V[I] U*[I])Vectors and Discrete FunctionsVectors and Discrete Functions2t in terms of t0, t1, t2 = [1,.5,.5]2t in terms of t0, t1, t2 = [1,.5,.5]2t1 t t2Vectors and Discrete FunctionsVectors and Discrete Functions2t in terms of t0, t0.5, t1, t1.5, t22t in terms of t0, t0.5, t1, t1.5, t22t1 t0.5t t1.5t2Vectors and FunctionsVectors and FunctionsVector Discrete ContinuousV V[I] V(x)a V + b U a V[I] + b U[I] a V(x) + b U(x)V • U ∑ V[I] U*[I] ∫ V(x) U*(x) dxVectors and FunctionsVectors and Functions2t projected onto 1, t, t22t projected onto 1, t, t22t1 t t2Function BasesFunction BasesTime:Polynomial / Power Series: Discrete Fourier:  integers (where )Continuous Fourier:Time:Polynomial / Power Series: Discrete Fourier:  integers (where )Continuous Fourier:Fourier TransformsFourier TransformsDiscrete TimeContinuousTimeDiscreteFrequencyDiscrete Fourier TransformFourier SeriesContinuousFrequencyDiscrete-time Fourier TransformFourier TransformConvolutionConvolution  WhereDot product withshifted kernel  WhereDot product withshifted kernelFilteringFilteringFilter in frequency domainFT signal to frequency domainMultiply signal & filterFT signal back to time domainFilter in time domainFT filter to time domainConvolve signal & filterFilter in frequency domainFT signal to frequency domainMultiply signal & filterFT signal back to time domainFilter in time domainFT filter to time domainConvolve signal & filterIdealIdealLow pass filter eliminates all high freqbox in frequency domainsinc in spatial domain ( )Possible negative resultsInfinite kernelExact reconstruction to Nyquist limitSample frequency ≥ 2x highest frequencyExact only if reconstructing with syncLow pass filter eliminates all high freqbox in frequency domainsinc in spatial domain ( )Possible negative resultsInfinite kernelExact reconstruction to Nyquist limitSample frequency ≥ 2x highest frequencyExact only if reconstructing with syncSamplingSamplingMultiply signal by pulse trainMultiply signal by pulse trainReconstructionReconstructionConvolve samples & reconstruction filterSum weighted kernel functionsConvolve samples & reconstruction filterSum weighted kernel functionsFiltering, Sampling, ReconstructionFiltering, Sampling, ReconstructionStepsIdeal continuous imageFilterFiltered continuous imageSampleSampled image pixelsReconstruction filterContinuous displayed resultStepsIdeal continuous imageFilterFiltered continuous imageSampleSampled image pixelsReconstruction filterContinuous displayed resultFiltering, Sampling, ReconstructionFiltering, Sampling, ReconstructionCombine filter and sampleIdeal continuous imageSampling filterSampled image pixelsReconstruction filterContinuous displayed resultCombine filter and sampleIdeal continuous imageSampling filterSampled image pixelsReconstruction filterContinuous displayed resultAntialiasingAntialiasingBlur away frequencies that would aliasBlur preferable to aliasingCan combine filtering and samplingEvaluate convolution at sample pointsFilter kernel sizeIIR = infinite impulse responseFIR = finite impulse responseBlur away frequencies that would aliasBlur preferable to aliasingCan combine filtering and samplingEvaluate convolution at sample pointsFilter kernel sizeIIR = infinite impulse responseFIR = finite impulse responseAnalytic higher order filteringAnalytic higher order filteringFold better filter into rasterizationCan make rasterization much harderUsually just done for linesDraw with filter kernel “paintbrush”Only practical for finite filtersFold better filter into rasterizationCan make rasterization much harderUsually just done for linesDraw with filter kernel “paintbrush”Only practical for finite filtersAnalytic Area SamplingAnalytic Area SamplingCompute “area” of pixel coveredBox in spatial domainNice finite kerneleasy to computesinc in freq domainPlenty of high freq still aliasesCompute “area” of pixel coveredBox in spatial domainNice finite kerneleasy to computesinc in freq domainPlenty of high freq still aliasesSupersamplingSupersamplingNumeric integration of filterGrid with equal weight = box filterUnequal weightsPriority samplingPush up Nyquist frequencyEdges: ∞ frequency, still aliasNumeric integration of filterGrid with equal weight = box filterUnequal weightsPriority samplingPush up Nyquist frequencyEdges: ∞ frequency, still aliasAdaptive samplingAdaptive