113. Image processing2ReadingJain, Kasturi, Schunck, Machine Vision. McGraw-Hill, 1995. Sections 4.2-4.4, 4.5(intro), 4.5.5, 4.5.6, 5.1-5.4.23Image processingAn image processing operation typically defines a new image g in terms of an existing image f.The simplest operations are those that transform each pixel in isolation. These pixel-to-pixel operations can be written:Examples: threshold, RGB Æ grayscaleNote: a typical choice for mapping to grayscale is to apply the YIQ television matrix and keep the Y.(,) ((,))gxy tf xy=0.596 0.275 0.3210.212 0.523 0.30.299 0.587 0.11411IQYRGB−−−⎡⎤ ⎡ ⎤⎡⎤⎢⎥ ⎢ ⎥⎢⎥=⎢⎥ ⎢ ⎥⎢⎥⎢⎥ ⎢ ⎥⎢⎥⎣⎦ ⎣ ⎦⎣⎦4Pixel movementSome operations preserve intensities, but move pixels around in the imageExamples: many amusing warps of images[Show image sequence.]%%(, ) ((, ), (, ))gxy f xxy yxy=35NoiseImage processing is also useful for noise reduction and edge enhancement. We will focus on these applications for the remainder of the lecture…Common types of noise: Salt and pepper noise: contains random occurrences of black and white pixels Impulse noise: contains random occurrences of white pixels Gaussian noise: variations in intensity drawn from a Gaussian normal distribution6Ideal noise reduction47Ideal noise reduction8Practical noise reductionHow can we “smooth” away noise in a single image?Is there a more abstract way to represent this sort of operation? Of course there is!59Discrete convolutionFor a digital signal, we define discrete convolution as:%=∗=−=−∑∑''[] [] []['][ ']['][' ]iigi f i hifihi ifihi i%where [ ] [ ].hi h i=−10Discrete convolution in 2DSimilarly, discrete convolution in 2D becomes:=∗=−−=−−∑∑∑∑%''''[,] [,] [,][','][ ', '][','][' ,' ]jijigi j f i j hi jfi jhi i j jfi jhi ij j%where [ , ] [ , ].hi j h i j=−−611Convolution representationSince f and h are defined over finite regions, we can write them out in two-dimensional arrays:Note: This is not matrix multiplication!Q: What happens at the edges?62 79 23 119 120 105 4 010 10 9 62 12 78 34 010 58 197 46 46 0 0 48176 135 5 188 191 68 0 492 1 1 29 26 37 0 770 89 144 147 187 102 62 208255 252 0 166 123 62 0 31166 63 127 17 1 0 99 30X .2 X 0 X .2X 0 X .2 X 0X .2 X 0 X .212Mean filtersHow can we represent our noise-reducing averaging filter as a convolution diagram (know as a mean filter)?713Effect of mean filters14Gaussian filtersGaussian filters weigh pixels based on their distance from the center of the convolution filter. In particular:This does a decent job of blurring noise while preserving features of the image.What parameter controls the width of the Gaussian? What happens to the image as the Gaussian filter kernel gets wider?What is the constant C? What should we set it to?22 2()/(2)[, ]ijehi jCσ−+=815Effect of Gaussian filters16Median filtersA median filter operates over an mxm region by selecting the median intensity in the region.What advantage does a median filter have over a mean filter?Is a median filter a kind of convolution?917Effect of median filters18Comparison: Gaussian noise1019Comparison: salt and pepper noise20Edge detectionOne of the most important uses of image processing is edge detection: Really easy for humans Really difficult for computers Fundamental in computer vision Important in many graphics applications1121What is an edge?Q: How might you detect an edge in 1D?22GradientsThe gradient is the 2D equivalent of the derivative:Properties of the gradient It’s a vector Points in the direction of maximum increase of f Magnitude is rate of increaseHow can we approximate the gradient in a discrete image?(, ) ,fffxyxy⎛⎞∂∂∇=⎜⎟⎝∂ ∂ ⎠1223Less than ideal edges24Steps in edge detectionEdge detection algorithms typically proceed in three or four steps: Filtering: cut down on noise Enhancement: amplify the difference between edges and non-edges Detection: use a threshold operation Localization (optional): estimate geometry of edges beyond pixels1325Edge enhancementA popular gradient magnitude computation is the Sobel operator:We can then compute the magnitude of the vector (sx, sy).101202101121000121xyss−⎡⎤⎢⎥=−⎢⎥⎢⎥−⎣⎦⎡⎤⎢⎥=⎢⎥⎢⎥−−−⎣⎦26Results of Sobel edge detection1427Second derivative operatorsThe Sobel operator can produce thick edges. Ideally, we’re looking for infinitely thin boundaries.An alternative approach is to look for local extrema in the first derivative: places where the change in the gradient is highest.Q: A peak in the first derivative corresponds to what in the second derivative?Q: How might we write this as a convolution filter?28Localization with the LaplacianAn equivalent measure of the second derivative in 2D is the Laplacian:Using the same arguments we used to compute the gradient filters, we can derive a Laplacian filter to be:Zero crossings of this filter correspond to positions of maximum gradient. These zero crossings can be used to localize edges.22222(, )fffxyxy∂∂∇=+∂∂2010141010⎡⎤⎢⎥∆= −⎢⎥⎢⎥⎣⎦1529Localization with the LaplacianOriginal SmoothedLaplacian (+128)30Marching squaresWe can convert these signed values into edge contours using a “marching squares” technique:1631Sharpening with the LaplacianOriginalLaplacian (+128)Original + Laplacian Original - LaplacianWhy does the sign make a difference?How can you write each filter that makes each bottom image?32Spectral impact of sharpeningWe can look at the impact of sharpening on the Fourier spectrum:201015 1010δ−⎡⎤⎢⎥−∆ = − −⎢⎥⎢⎥−⎣⎦Spatial domain Frequency domain1733SummaryWhat you should take away from this lecture: The meanings of all the boldfaced terms. How noise reduction is done How discrete convolution filtering works The effect of mean, Gaussian, and median filters What an image gradient is and how it can be computed How edge detection is done What the Laplacian image is and how it is used in either edge detection or image sharpening34Next time:Affine TransformationsTopic:How do we represent the rotations, translations, etc. needed to build a complex scene from simpler objects?Read:• Watt, Section 1.1.Optional:• Foley, et al, Chapter 5.1-5.5.• David F. Rogers and J. Alan Adams, Mathematical Elements for Computer Graphics, 2nd Ed., McGraw-Hill, New York, 1990, Chapter
View Full Document
Unlocking...