Convolution, Edge Detection, Sampling15-463: Computational PhotographyAlexei Efros, CMU, Fall 2006Some slides from Steve SeitzFourier spectrumFun and games with spectra4Gaussian filteringA Gaussian kernel gives less weight to pixels further from the center of the windowThis kernel is an approximation of a Gaussian function:00000000000000000900000000000000090909090900000090909009000000909090909000000909090909000000909090909000000000000000000000000121242121ConvolutionRemember cross-correlation:A convolution operation is a cross-correlation where the filter is flipped both horizontally and vertically before being applied tothe image:It is written: Suppose H is a Gaussian or mean kernel. How does convolution differ from cross-correlation?The Convolution TheoremThe greatest thing since sliced (banana) bread!• The Fourier transform of the convolution of two functions is the product of their Fourier transforms• The inverse Fourier transform of the product of two Fourier transforms is the convolution of the two inverse Fourier transforms• Convolution in spatial domain is equivalent to multiplication in frequency domain!]F[]F[]F[ hghg=∗][F][F][F111hggh−−−∗=Fourier Transform pairs2D convolution theorem example*f(x,y)h(x,y)g(x,y)|F(sx,sy)||H(sx,sy)||G(sx,sy)|Low-pass, Band-pass, High-pass filterslow-pass:band-pass:what’s high-pass?Edges in imagesImage gradientThe gradient of an image: The gradient points in the direction of most rapid change in intensityThe gradient direction is given by:• how does this relate to the direction of the edge?The edge strength is given by the gradient magnitudeEffects of noiseConsider a single row or column of the image• Plotting intensity as a function of position gives a signalWhere is the edge?How to compute a derivative?Where is the edge? Solution: smooth firstLook for peaks inDerivative theorem of convolutionThis saves us one operation:Laplacian of GaussianConsider Laplacian of GaussianoperatorWhere is the edge? Zero-crossings of bottom graph2D edge detection filtersis the Laplacian operator:Laplacian of GaussianGaussian derivative of GaussianMATLAB demog = fspecial('gaussian',15,2);imagesc(g)surfl(g)gclown = conv2(clown,g,'same');imagesc(conv2(clown,[-1 1],'same'));imagesc(conv2(gclown,[-1 1],'same'));dx = conv2(g,[-1 1],'same');imagesc(conv2(clown,dx,'same'));lg = fspecial('log',15,2);lclown = conv2(clown,lg,'same');imagesc(lclown)imagesc(clown + .2*lclown)Image ScalingThis image is too big tofit on the screen. Howcan we reduce it?How to generate a half-sized version?Image sub-samplingThrow away every other row and column to create a 1/2 size image-calledimage sub-sampling1/41/8Image sub-sampling1/4 (2x zoom) 1/8 (4x zoom)Why does this look so crufty?1/2Even worse for synthetic imagesReally bad in videoAlias: n., an assumed namePicket fence recedingInto the distance willproduce aliasing…Input signal:x = 0:.05:5; imagesc(sin((2.^x).*x))Matlab output:WHY?Aj-aj-aj:Alias!Not enough samplesAliasing• occurs when your sampling rate is not high enough to capture theamount of detail in your image• Can give you the wrong signal/image—an aliasWhere can it happen in images?• During image synthesis: • sampling continous singal into discrete signal• e.g. ray tracing, line drawing, function plotting, etc.• During image processing: • resampling discrete signal at a different rate• e.g. Image warping, zooming in, zooming out, etc.To do sampling right, need to understand the structure of your signal/imageEnter Monsieur Fourier…Fourier transform pairsSamplingwSpatial domain Frequency domain1/wsamplingpatternsampledsignalReconstructionFrequency domain1/wwSpatial domainsincfunctionreconstructedsignalWhat happens whenthe sampling rate is too low?Nyquist 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 knowledgeSamplingGood sampling:•Sample often or,•Sample wiselyBad sampling:•see aliasing in action!Gaussian pre-filteringG 1/4G 1/8Gaussian 1/2Solution: filter the image, then subsampleSubsampling with Gaussian pre-filteringG 1/4 G 1/8Gaussian 1/2Solution: filter the image, then subsampleCompare with...1/4 (2x zoom) 1/8 (4x
View Full Document
Unlocking...