Linear FiltersConvolutionExample: Smoothing by AveragingSmoothing with a GaussianAn Isotropic GaussianSlide 6Problem: Image NoiseSolution: Smoothing (Low-Pass) FiltersSmoothing Filters: DetailsGaussian KernelGaussian SmoothingSlide 12Slide 13Example: Gaussian SmoothingSlide 15Convolution NotesDiscrete 2-D ConvolutionCorrelationNormalized correlationSlide 20Slide 21Slide 22Dealing with Image EdgesStep 1Step 2Step 3Step 4Step 5Step 6and so on…Final ResultLinear Shift InvarianceImaging SystemsWhat’s Not a Convolution?Filtering in MatlabDifferentiation and convolutionFinite differencesNoiseSlide 39Slide 40Finite differences and noiseFinite differences responding to noiseThe response of a linear filter to noiseFilter responses (of noise) are correlatedSlide 45Slide 46Slide 47Smoothing reduces noiseSlide 49Gradients and edgesThe Gradient and EdgesEdge CausesEdge DetectionStep edge detection: First Derivative OperatorsSobel Edge Filtering ExampleSlide 56Slide 57Slide 58Slide 59Sobel Edge Filtering Example: ResultSobel Edge Detection: Gradient ApproximationSobelDerivative of GaussianComputer Vision : CISC 4/689Linear Filters•General process:–Form new image whose pixels are a weighted sum of original pixel values, using the same set of weights at each point.•Properties–Output is a linear function of the input–Output is a shift-invariant function of the input (i.e. shift the input image two pixels to the left, the output is shifted two pixels to the left)•Example: smoothing by averaging–form the average of pixels in a neighbourhood•Example: smoothing with a Gaussian–form a weighted average of pixels in a neighbourhood•Example: finding a derivative–form a weighted average of pixels in a neighbourhoodComputer Vision : CISC 4/689Convolution•Represent these weights as an image, H•H is usually called the kernel•Operation is called convolution–it’s associative•Result is:Rij Hi u,j vFuvu,vComputer Vision : CISC 4/689Example: Smoothing by AveragingComputer Vision : CISC 4/689Smoothing with a Gaussian•Smoothing with an average actually doesn’t compare at all well with a defocussed lens–Most obvious difference is that a single point of light viewed in a defocussed lens looks like a fuzzy blob; but the averaging process would give a little square.•A Gaussian gives a good model of a fuzzy blobComputer Vision : CISC 4/689exp x2 y222An Isotropic Gaussian•The picture shows a smoothing kernel proportional to (which is a reasonable model of a circularly symmetric fuzzy blob)Computer Vision : CISC 4/689Smoothing with a GaussianComputer Vision : CISC 4/689Problem: Image Noisefrom Forsyth & PonceComputer Vision : CISC 4/689Solution: Smoothing (Low-Pass) Filters•If object reflectance changes slowly and noise at each pixel is independent, then we want to replace each pixel with something like the average of neighbors–Disadvantage: Sharp (high-frequency) features lost7 x 7 averaging neighborhoodOriginal imageComputer Vision : CISC 4/689Smoothing Filters: Details•Filter types–Mean filter (box)–Median (nonlinear)–Gaussian•Can specify linear operation by shifting kernel over image and taking product1111111113 x 3 box filter kernelComputer Vision : CISC 4/689Gaussian Kernel•Idea: Weight contributions of neighboring pixels by nearness•Smooth roll-off reduces “ringing” seen in box filter0.003 0.013 0.022 0.013 0.0030.013 0.059 0.097 0.059 0.0130.022 0.097 0.159 0.097 0.0220.013 0.059 0.097 0.059 0.0130.003 0.013 0.022 0.013 0.0035 x 5,  = 1Computer Vision : CISC 4/689Gaussian Smoothing•In theory, the Gaussian distribution is non-zero everywhere, which would require an infinitely large convolution mask, but in practice it is effectively zero more than about three standard deviations from the mean, and so we can truncate the mask at this point •Discrete approximation to Gaussian function with sd = 1.4 Source: http://www.cee.hw.ac.uk/hipr/html/gsmooth.htmlComputer Vision : CISC 4/689Gaussian Smoothing•Once a suitable mask has been calculated, then the Gaussian smoothing can be performed using standard convolution methods. The convolution can in fact be performed fairly quickly since the equation for the 2-D isotropic Gaussian shown above is separable into x and y components. Thus the 2-D convolution can be performed by first convolving with a 1-D Gaussian in the x direction, and then convolving with another 1-D Gaussian in the y direction. (The Gaussian is in fact the only completely circularly symmetric operator which can be decomposed in such a way.) Below shows the 1-D x component mask that would be used to produce the full mask shown in previous slide. The y component is exactly the same but is oriented vertically. A further way to compute a Gaussian smoothing with a large standard deviation is to convolve an image several times with a smaller Gaussian. While this is computationally complex, it can have applicability if the processing is carried out using a hardware pipeline.Computer Vision : CISC 4/689Gaussian Smoothing•One of the principle justifications for using the Gaussian as a smoothing filter is due to its frequency response. Most convolution based smoothing filters act as lowpass frequency filters. This means that their effect is to remove low spatial frequency components from an image. The frequency response of a convolution filter, i.e. its effect on different spatial frequencies, can be seen by taking the Fourier transform of the filter. • •Frequency responses of Box (i.e. mean) filter (width 7 pixels) and Gaussian filter ( = 3 pixels).Computer Vision : CISC 4/689Example: Gaussian Smoothing = 1  = 37 x 7kernelOriginal image Box filterComputer Vision : CISC 4/689Convolution•Formalization of idea of overlap (product) of two functions as one is shifted across the other•The area under convolution is product of areas under the functions•The convolution of two Gaussians is another Gaussiancourtesy of mathworld.wolfram.comThe animations above graphically illustrate the convolution of two rectangle functions (left) and two Gaussians (right). In the plots, the green curve shows the convolution of the blue and red curves as a function of t , the position indicated by the vertical green line. The gray region indicates the product as a function of t , so its