Filtering Images in the Spatial Domain Chapter 3b G&WOverviewCross CorrelationCross CorrelationCorrelation: Technical DetailsCorrelation: Technical DetailsCorrelation: Technical DetailsCorrelation: PropertiesCorrelation: PropertiesFilters: ConsiderationsExamples 1Examples 1Examples 2Smoothing and NoiseOther FiltersGaussian KernelGaussian KernelPattern MatchingPattern Matching/DetectionMatched Filter ExampleMatched Filter Example: Correlation of template with imageMatched Filter Example: Thresholding of correlation resultsMatched Filter Example: High correlation → template foundDigital Images: Boundaries are “Lines” or “Discontinuities”Derivatives: Finite DifferencesDerivative ExampleI GOT UP TO HERE ON 9/15/2010 (GUIDO)ConvolutionConvolution: PropertiesComputing ConvolutionComputing ConvolutionSeparable KernelsSeparabilityNonlinear Methods For FilteringMedian FilteringMedian vs GaussianMedian FilterReplacement NoiseSmoothing of S&P NoiseSmoothing of S&P NoiseMedian FilteringMedian FilteringMedian FilteringMedian FilteringOrder StatisticsPiecewise Flat Image ModelsPiecewise-Flat Image ModelsPiecewise-Flat Images and Pixel AveragingBilateral FilterBilateral FilterBilateral FilteringBilateral FilteringNonlocal AveragingUINTA: Unsupervised Information-Theoretic Adaptive Filtering : Excellent Introduction and Additional Readings (Suyash P. Awate)Nonlocal AveragingNonlocal Averaging FormulationAveraging Pixels Based on WeightsNonlocal AveragingSome DetailsNL-Means AlgorithmResultsResultsResultsLess Noisy ExampleLess Noisy ExampleResultsCheckerboard With NoiseQuality of DenoisingMRI HeadMRI HeadFingerprintFingerprintResultsResultsResultsFractalPiecewise ConstantTexture, StructureSlide Number 84Univ of Utah, CS6640 2010 1Filtering Images in the Spatial DomainChapter 3b G&WRoss Whitaker(slightly modified by Guido Gerig)SCI Institute, School of ComputingUniversity of UtahUniv of Utah, CS6640 2010 2Overview• Correlation and convolution• Linear filtering– Smoothing, kernels, models– Detection– Derivatives• Nonlinear filtering– Median filtering– Bilateral filtering– Neighborhood statistics and nonlocal filteringUniv of Utah, CS6640 2010 30.0*95 + 0.1*103 + 0.0*150+ 0.1*36 + 0.6*150 + 0.1*104+ 0.0*47 + 0.1*205 + 0.0*77 = 134.8. . . .. . . .. . . .. . . .100 130 104 99 …87 95 103 150 …50 36 150 104 …20 47 205 77 …. . . .. . . .Filter0.0 0.1 0.00.1 0.6 0.10.0 0.1 0.0Input image Output image0.0*87 + 0.1*95 + 0.0*103+ 0.1*50 + 0.6*36 + 0.1*150+ 0.0*20 + 0.1*47 + 0.0*205 = 55.8Cross Correlation• Operation on image neighborhood and small …– “mask”, “filter”, “stencil”, “kernel”• Linear operations within a moving window55.8134.8Univ of Utah, CS6640 2010 4Cross Correlation• 1D• 2DUniv of Utah, CS6640 2010 5Correlation: Technical Details• How to filter boundary?? ? ? ? ?????Univ of Utah, CS6640 2010 6Correlation: Technical Details• Boundary conditions– Boundary not filtered (keep it 0)– Pad image with amount (a,b)• Constant value or repeat edge values– Cyclical boundary conditions• Wrap or mirroringUniv of Utah, CS6640 2010 7Correlation: Technical Details• Boundaries– Can also modify kernel – no longer correlation• For analysis– Image domains infinite– Data compact (goes to zero far away from origin)Univ of Utah, CS6640 2010 8Correlation: Properties• Shift invariantUniv of Utah, CS6640 2010 9Correlation: Properties• Shift invariant• LinearCompact notationUniv of Utah, CS6640 2010 10Filters: Considerations• Normalize– Sums to one– Sums to zero (some cases, see later)• Symmetry– Left, right, up, down– Rotational• Special case: auto correlationUniv of Utah, CS6640 2010 110 0 00 1 00 0 01 1 11 1 11 1 11/9 *Examples 1Univ of Utah, CS6640 2010121 1 11 1 11 1 11/9 *Examples 1Univ of Utah, CS6640 2010 131 1 11 1 11 1 11 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 11/9 *1/25 *Examples 2Univ of Utah, CS6640 2010 14Smoothing and NoiseNoisy image5x5 box filterUniv of Utah, CS6640 2010 17Other Filters• Disk– Circularly symmetric, jagged in discrete case• Gaussians– Circularly symmetric, smooth for large enough stdev– Must normalize in order to sum to one• Derivatives – discrete/finite differences– OperatorsGaussian KernelUniv of Utah, CS6640 2010 18Gaussian KernelUniv of Utah, CS6640 2010 19Normalization to 1.0Univ of Utah, CS6640 2010 20Pattern MatchingUniv of Utah, CS6640 2010 21Pattern Matching/Detection• The optimal (highest) response from a filter is the autocorrelation evaluated at position zero• A filter responds best when it matches a pattern that looks itself• Strategy– Detect objects in images by correlation with “matched” filterUniv of Utah, CS6640 2010 22Matched Filter ExampleTrick: make sure kernel sums to zeroUniv of Utah, CS6640 2010 23Matched Filter Example: Correlation of template with imageUniv of Utah, CS6640 2010 24Matched Filter Example: Thresholding of correlation resultsUniv of Utah, CS6640 2010 25Matched Filter Example: High correlation → template foundDigital Images: Boundaries are “Lines” or “Discontinuities”Example: Characterization of discontinuities?Univ of Utah, CS6640 2010 30Derivatives: Finite DifferencesUniv of Utah, CS6640 2010 310 -1 00 0 00 1 00 0 0-1 0 10 0 0Derivative ExampleI GOT UP TO HERE ON 9/15/2010 (GUIDO)Univ of Utah, CS6640 2010 32Univ of Utah, CS6640 2010 33• Discrete• Continuous• Same as cross correlation with kernel transposed around each axis• The two operations (correlation and convolution) are the same if the kernel is symmetric about axesConvolutionreflection of wJava demo: http://www.jhu.edu/signals/convolve/Univ of Utah, CS6640 2010 34Convolution: Properties• Shift invariant, linear•Commutative• Associative• Others (discussed later):– Derivatives, convolution theorem, spectrum…Univ of Utah, CS6640 2010 35Computing Convolution• Compute time– MxM mask– NxN imageO(M2N2)“for” loops are nested 4 deepUniv of Utah, CS6640 2010 36Computing Convolution• Compute time– MxM mask– NxN image• Special case: separableO(M2N2)“for” loops are nested 4 deep O(M2N2) O(MN2)Two 1D kernels=*Univ of Utah, CS6640 2010 37Separable Kernels• Examples– Box/rectangle– Bilinear interpolation– Combinations of partial derivatives• d2f/dxdy– Gaussian• Only filter that is bothcircularly symmetric andseparable• Counter examples–