CSE486Robert CollinsLecture 10:Pyramids and Scale SpaceCSE486Robert CollinsRecall• Cascaded Gaussians– Repeated convolution by a smaller Gaussianto simulate effects of a larger one.• G*(G*f) = (G*G)*f [associativity]CSE486Robert CollinsExample: Cascaded Convolutions[1 1] * [1 1] --> [1 2 1][1 1] * [1 2 1] --> [1 3 3 1][1 1] * [1 3 3 1] --> [1 4 6 4 1]..and so on…1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1and so on…Pascal’s TriangleCSE486Robert CollinsAside: Binomial Approximation1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1and so on…Pascal’s TriangleBinomialCoefficientsCSE486Robert CollinsAside: Binomial ApproximationLook at odd-length rows of Pascal’s triangle:1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1and so on…[1 2 1]/4 - approximatesGaussian with sigma=1/sqrt(2)[1 4 6 4 1]/16 - approximatesGaussian with sigma=1An easy way to generate integer-coefficientGaussian approximations.CSE486Robert CollinsFrom Homework 2CSE486Robert CollinsMore about Cascaded ConvolutionsFun facts:The distribution of the sum of two random variablesX + Y is the convolution of their two distributions Given N i.i.d. random variables, X1 … XN, the distributionof their sum approaches a Gaussian distribution (aka thecentral limit theorem)Therefore:The repeated convolution of a (nonnegative)filter with itself takes on a Gaussian shape.(for the mathematically inclined)CSE486Robert CollinsGaussian Smoothing atDifferent Scalesoriginal sigma = 1CSE486Robert Collinsoriginal sigma = 3Gaussian Smoothing atDifferent ScalesCSE486Robert CollinsGaussian Smoothing atDifferent Scalesoriginal sigma = 10CSE486Robert CollinsIdea for Today:Form a Multi-Resolution Representationoriginalsigma = 10sigma = 3sigma = 1CSE486Robert CollinsPyramid RepresentationsBecause a large amount of smoothing limitsthe frequency of features in the image, we donot need to keep all the pixels around!Strategy: progressively reduce the number ofpixels as we smooth more and more.Leads to a “pyramid” representation if wesubsample at each level.CSE486Robert CollinsGaussian Pyramid• Synthesis: Smooth image with a Gaussian anddownsample. Repeat.• Gaussian is used because it is self-reproducing(enables incremental smoothing).• Top levels come “for free”. Processing costtypically dominated by two lowest levels(highest resolution).CSE486Robert CollinsGaussian PyramidHigh resLowresCSE486Robert CollinsEmphasis: Smaller Imageshave Lower ResolutionCSE486Robert CollinsGenerating a Gaussian PyramidBasic Functions:Blur (convolve with Gaussian to smooth image)DownSample (reduce image size by half)Upsample (double image size)CSE486Robert CollinsGenerating a Gaussian PyramidBasic Functions:Blur (convolve with Gaussian to smooth image)DownSample (reduce image size by half)Upsample (double image size)CSE486Robert CollinsDownsampleBy the way: Subsampling is a bad idea unless you have previously blurred/smoothed the image! (because it leads to aliasing)CSE486Robert CollinsTo Elaborate: Thumbnailsoriginal image262x195downsampled (left)vs. smoothed thendownsampled (right)131x9765x4832x24CSE486Robert CollinsTo Elaborate: Thumbnailsoriginal image262x195131x97downsampled (left)vs. smoothed thendownsampled (right)CSE486Robert CollinsTo Elaborate: Thumbnailsoriginal image262x195downsampled (left)vs. smoothed thendownsampled (right)65x48CSE486Robert CollinsTo Elaborate: Thumbnailsoriginal image262x195downsampled (left)vs. smoothed thendownsampled (right)32x24CSE486Robert CollinsUpsampleHow to fill in the empty values?Interpolation:• initially set empty pixels to zero• convolve upsampled image with Gaussian filter! e.g. 5x5 kernel with sigma = 1.• Must also multiply by 4. Explain why.CSE486Robert CollinsSpecific ExampleFrom Crowley et.al., “Fast Computation of Characteristic Scale using a Half-Octave Pyramid.” Proc International Workshop on Cognitive Vision (CogVis), Zurich, Switzerland, 2002.General idea: cascaded filtering using [1 4 6 4 1] kernel to generate a pyramid with two images per octave (power of 2 change in resolution). When we reach a full octave, downsample the image.blur blurblur blurdownsampleCSE486Robert CollinsEffective Sigma at Each LevelCrowley etal.CSE486Robert CollinsEffective Sigma at Each LevelCAN YOUEXPLAIN HOWTHESE VALUESARISE?CSE486Robert CollinsBasic idea: different scales are appropriate for describing differentobjects in the image, and we may not know the correct scale/sizeahead of time.Concept: Scale SpaceCSE486Robert CollinsExample: Detecting “Blobs” atDifferent Scales.But first, we have to talkabout detecting blobsat one scale...CSE486Robert