数字图像处理课件lecture3.pdf

1 2 There are many definitions:Segmentation subdivides an image into its constituent regions or objects(Gonzales,pp567)Segmentation is a process of grouping together pixels that have similar attributes(Efford,pp250)Image Segmentation is the process of partitioning an image into non-intersecting regions such that each region is homogeneous and the union of no two adjacent regions is homogeneous(Pal,pp1277)What is Image Segmentation?Segmentation is typically associated with pattern recognition problems.It is considered the first phase of a pattern recognition process and is sometimes also referred to as object isolation.3 Image Processing for Pattern Recognition Feature Extraction Acquisition Preprocessing Classification Post Processing Scaling Centering Enhancement Filtering(Transform)Binarization(Thresholding)Edge detection Thinning Pixel Feature(Histogram)Boundary Projection Moments Transformation Matching Tree Classification Neural Network 4 5 1.Detecting Edges Using Differencing Marks Image points of high contrast can be detected by computing intensity differences in local image regions.High contrast High contrast 6 Typically,such points form the border(or edge)between different objects or scene parts.Neighborhood templates or masks can be used.We start by using one-dimensional(1D)signals.The 1D signals could just be rows or columns of a 2D image.(a)(b)Border 7 Differencing 1D Signals Mathematic formula of derivatives:22)(,)(dxydxfdxdyxf=Masks can be used to represent of the derivatives of a signal.11)()()()(=iiiiixxxfxfxxfxfxi f(x)x 0 xi-1 f(xi)f(xi-1)Assuming that the sample spacing is x=1,the derivative of f(x)can be approximated by )()()(1iiixfxfxf Given that the signal S is a sequence of samples from some function f,then 8 Si-1 Si Si+1 Si+2 S=Si+1-Si Si-Si-1 S=Si+1-2Si+Si-1 S=f(x)S The first(S)and second(S)difference signals are scaled approximations to the first and second derivatives of the signal S Masks M and M represent the derivative operations -1+1 M=-2+1+1 M=9 The first derivative of f(x)can be approximated by applying the mask M=-1,1 to the samples in S can obtain an output signal S.Its convenient to think of the values of S as occurring in between the samples of S.A high absolute value of Si indicates where the signal is undergoing rapid change or high contrast.Signal S itself can be differentiated a second time using mask M to produce output S”,which corresponds to the second derivative of the original function f.The approximate second derivative can be computed by applying the mask M to the original sequence of samples S.1,1mask 1+=+=MiSiSiS 1,2,1 mask 12 1 )1()1(1=+=+=+=MiSiSiSiSiSiSiSiSiSiS10-1+1 M=Examples S1=12 12 12 12 12 24 24 24 24 24 S1 M=0 0 0 0 12 0 0 0 0 0 S1i i 0 12 24 S1i i 0 12 S1 is an upward step edge,the first derivative mask M can be used to detect the edge(border)11 S2=24 24 24 24 24 12 12 12 12 12 S2 M=0 0 0 0 -12 0 0 0 0 0 S2i i 0 12 24 S2i i 0-12 S2 is a downward step edge,the first derivative mask M can be used to detect the edge(border)S3i i 0 12 24 S3=12 12 12 12 24 12 12 12 12 12 S3 M=0 0 0 12-12 0 0 0 0 0 12 S3i i 0-12 S3 is a bright impulse or line,the first derivative mask M can be used to detect the edge(border)12 S4=12 12 12 12 15 18 21 24 24 24 S4 M=0 0 0 3 3 3 3 0 0 0 S4i i 0 3 S4 is an upward ramp,the first derivative mask M can be used to detect the edge(border)S4i i 0 12 24 15 18 21 24 13 Use of another common first derivative mask,which has 3 coordinates and is centered at signal point Si,so that it computes the signal difference across the adjacent values.First Derivative Mask M=-1,0,1 0-1+1 M=Because x=2,it will give a high estimate of the actual derivative unless the result is divided by 2.Moreover,this mask is known to give a response on perfect step edges that is 2 samples wide.14 Examples S1=12 12 12 12 12 24 24 24 24 24 S1 M=0 0 0 0 12 12 0 0 0 0 S1i i 0 12 24 S1 is an upward step edge,the first derivative mask M can be used to detect the edge(border)with 2 samples wide.0-1+1 M=S1i i 0 12 15 S2=24 24 24 24 24 12 12 12 12 12 S2 M=0 0 0 0 -12-12 0 0 0 0 S2i i 0 12 24 S2i i 0-12 S2 is a downward step edge S3i i 0 12 24 S3=12 12 12 12 24 12 12 12 12 12 S3 M=0 0 0 12 0 -12 0 0 0 0 S3 is a bright impulse or line 12 S3i i 0-12 16 S4=12 12 12 12 15 18 21 24 24 24 S4 M=0 0 0 3 6 6 6 3 0 0 S4 is an upward ramp S4i i 0 12 0-1+1 M=S4i i 0 12 24 15 18 21 24 17 Use of second derivative mask,signal contrast is detected by a zero-crossing,which localizes and amplifies the change between two successive signal values.Second Derivative Mask M”=-1,2,-1 2-1-1 M”=S1i i 0 12 24 S1=12 12 12 12 12 24 24 24 24 24 S1 M”=0 0 0 0 -12 12 0 0 0 0 12 S”1i i 0-12 Example:S1 is a upward step edge zero-crossing 18 S2=24 24 24 24 24 12 12 12 12 12 S2 M”=0 0 0 0 12-12 0 0 0 0 S2i i 0 12 24 S2 is a downward step edge 12 S”2i i 0-12 S3i i 0 12 24 S3=12 12 12 12 24 12 12 12 12 12 S3 M”=0 0 0-12 24-12 0 0 0 0 S3 is a bright impulse or line 12 S”3i i 0-12 24 zero-crossing zero-crossing 19 S4=12 12 12 12 15 18 21 24 24 24 S4 M”=0 0 0 -3 0 0 0 3 0 0 S4i i 0 12 24 S4 is an upward ramp 2-1-1 M”=3 S”4i i 0-3 15 18 21 24 20 Some properties of derivative masks -1+1 M=2-1-1 M”=0-1+1 M=Coordinates of derivative masks have opposite signs in order to obtain a high response in signal regions of high contrast.The sum of coordinates of derivative masks is zero so that a zero response is obtained on constant regions.Second derivative masks produce zero-crossings at points of high contrast.First derivative masks produce high absolute values at points of high contrast.S1i i 0 12 24 21-1+1 M=0-1+1 M=2-1-1 M”=Input Images 22 Differencing 2D Images(Detecting Edges Detecting Edges of 2D Images)of 2D Images)The maximum change of the contrast in the 2D picture function f(x,y)occurs along the direction of the gradientgradient 梯度梯度 of the function.(Edge)High contrast The direction of the gradient 梯度梯度 fGxxFfGyy=23 Mathematic formula Mathematic formula of the gradient:of the gradient:Gradient magnitude or 22()()fffxy+Gradient direction xfyf/tan1fx fy f Lower/Higher intensities Higher/Lower intensities fx fy f fffxy+24 25 26 Using masks to estimate the gradient Three masks:Sobel masks 2 1 0-1-2-1 1 0 0 G x=0-1 2-1 0 1 1 0-2 G y=1 1 0-1-1-1 1 0 0 0-1 1-1 0 1 1 0-1 G x=G y=Prewitt masks G x=G y=Robert masks 1 0-1-1 1 0 0 0 27 a)Original Image-Lena b)Enhanced Lena by Histogram Equalization c)Edge map by Roberts operator e)Edge map by Sobel operator d)Edge map by Prewitt operator 28 Step-1.Compute:(),618yxNMxfxMask Mx is overlaid on image neighborhood N8x,y so that each intensity Nij can be multiplied by weight Mij;Finally all these products are summed.Prewitt masks 64 42 15 35 66 12 14 38 65 fx fy f N8x,y 1 1 0-1-1-1 1 0 0 M x=()1830502761 )1242()1464()3865(61 ,618=+=+=yxNMxfx29 Step-2.Compute:(),618yxNMyfyMask My is overlaid on image neighborhood N8x,y so that each intensity Nij can be multiplied by weight Mij;Finally all these products are summed.64 42 15 35 66 12 14 38 65 fx fy f N8x,y 0-1 1-1 0 1 1 0-1 M y=()1623512661 )4265()1566()1238(61 ,618+=+=yxNMyfy30 Step-3.Compute:Gradient magnitude xfyf/tan1 Gradient direction 2222()()181624fffxy+=+=421816tan/tan11=xfyf22()()fffxy+31 1 1 0-1-1-1 1 0 0 M x=0-1 1-1 0 1 1 0-1 M y=Lower intensities Higher intensities 64 42 15 35 66 12 14 38 65 fx fy f N8x,y()1830502761 )1242()1464()3865(61 ,618=+=+=yxNMxfx()16,618=yxNMyfy2222()()181624fffxy+=+=421816tan/tan11=xfyf32 Example (a)Image of Judith Prewitt (b)Gradient image showing result using the Prewitt 33 operator (a)(b)33 Sobel masks:the Sobel operator represents many,but not all,of the image edges.2 1 0-1-2-1 1 0 0 M x=0-1 2-1 0 1 1 0-2 M y=(a)Image of noisy squared and rings,(b)Coding of gradient direction computed by 33 Sobel operator.(a)(b)34 22222fffxy=+22(1,)(1,)2(,)ff xyf xyf x yx=+22(,1)(,1)2(,)ff x yf x yf x yy=+Laplacian masks 2(1)(1,)(,1)(,1)4(,)ff xf xyf x yf x yf x y=+010141010Mask:35 Laplacian masks 2-1-1 Mx”=2-1-1 My”=0101141010H=Mask:36 Laplacian masks The other mask:1112181,1111213242,121121142122,161211015040101HHHH=37 Supplement:Sharpening filters Objective:1.Highlight fine detail in and image 2.Enhance detail that has been blurred 3.Edge detection before image segmentation 4.Object location and recognition 5.Image art 38 Supplement:Sharpening filters High pass filters High-boost filters Differencing filters High pass filters Principle of mask design Advantage:enhance edges Shortcoming:enhance other discontinuities and discard low frequency information 40 High-boost filters For Laplacian masks 22(,)(,)(,)(,)(,)f x yf x yg x yf x yf x y=+If the center coefficient of the Laplacian mask is negative If the center coefficient of the Laplacian mask is positive (a)Origin image (b)Laplacian filtered image(3*3)(c)Enhanced image 42 2(,)(,)(,)(,)(,)*1(,)4(,)(1,)(1,)(,1)(,1)5(,)(1,)(1,)(,1)(,1)g x yf x yf x yf x yf x yHf x yf x yf xyf xyf x yf x yf x yf xyf xyf x yf x y=+=+(1,1)(1,)(1,1)(,1)(,)(,1)*(1,1)(1,)(1,1)(,)*f ijf ijf ijf i jf i jf i jf ijf ijf ijf x y+=+=0101510100101141010H=010151010 43 01015101044 0106141010HA=+The other mask:1117181111HA=+High-boost Laplacian masks Differencing filters Gradient filter Robert filter Prewitt filter Sobel filter Laplacian filter 46 Conclusion Smoothing filter：系数都为正，一般系数之和等于1。Sharpening filter：系数有正有负，若没有提升，系数之和等 于0；否则，系数之和大于零。Spatial filter Smoothing filterSmoothing filter Sharpening filter Average filter Median filter The first Derivative The sencond Derivative Mini Project1:Enhance image a)Origin image b)Laplacian of a)c)Sharpened image by adding a)and b)d)Edge image by sobel operator and smoothing image using 5*5 mask e)b)*d)f)Sharpened image by adding a)and e)49 Mini Project2:Enhance image Image characteristic:A narrow range of low gray-level values High noise content(a)Origin image 50 Mini Project2:Enhance image Origin image Laplacian enhanced Roberts gradient Box filter smoothed Sharpened+Sharpen enhaced Power-law strech Output 51 Laplacian+(a)111181111(a)Origin image(b)52 Robert(a)Origin image(c)53 5*5 box smooth(c)(d)+(a)(d)(b)(e)C=1=0.5(e)(f)56 Enhanced Image Origin image 57 2.Gaussian Filtering&Log Edge Detection The Gaussian function has important applications in many areas of mathematics,including image filtering.It can be used for smoothing images or detecting edges.Definition:A Gaussian function of one variable with spread is of the following form,where c is some scale factor.A Gaussian function of two variables is 222)(xcexg=1-D 2222)(),(yxceyxg+=2-D 58 The Gaussian with its first and second derivatives are important in filtering operations.22221)(xexg=222321)(xxexg=222352212)(xexxg=59 Two masks for Gaussian smoothing 2 1 2 1 2 1 1 4 2 G3 3=A 33 mask approximating a Gaussian obtained by matrix multiplication 1,2,1T 1,2,1;2D Gaussian function 3D Representation 2D Representation 60 G77=55 55 70 70 70 90 55 55 70 26 26 33 26 12 33 26 26 12 33 26 12 26 26 12 33 7 7 3 3 9 9 3 1 7 7 1 3 9 3 1 7 7 1 3 7 7 3 3 9 A 77 mask approximating a Gaussian with =2 obtained by using to generate function values for integers x and y and then setting c=90 so that the smallest mask element is 1.2222)(),(yxceyxg+=2D Representation 3D Representation 852585212521012521258525861 Detecting Edges with the LOG Filter LOG filter(Laplacian of Gaussian)-1D 222352212)(xexxg=62 Detecting Edges with the LOG Filter LOG filter(Laplacian of Gaussian)-2D 63(2)An 1111 mask approximating the Laplacian of a Gaussian with=2.Guassian smoothing+Laplancian b)Edge map by LOG 0.005 a)Original image b)Edge map by LOG 0.008 65 66 3.The Canny Edge Detector The Canny edge detector is a very popular and effective operator(Gaussian smoothing+Sobel).The Canny operator first smoothes the intensity image,then produces extended contour segments by following high gradient magnitudes from one neighborhood to another.L.G.Shapiro,G.C.Stockman,L.G.Shapiro,G.C.Stockman,Computer Computer VisionVision,Prentice Hill,2001,Prentice Hill,2001 67 Example An input image(a)is smoothed using Gaussian filters of size(b)=4,and(c)=1 before performing edge detection.More detail and more noise is shown for the smaller filter.(b)(c)(a)=4 =1 68 Example:(a)Image of the great arch in St.Louis;(b)results of Canny operator with =1;(c)results of Canny operator with =4;(a)(b)(c)69 Examples(a)Image of Maos Memorial.(b)Result of applying Canny operator with =1.(c)Result of =2.Some objects are detected very well,so are some shadows.(a)(b)(c)Roberts Prewitt Sobel Laplacian LOG Canny BW=edge(I,type)first order differential second order differential 71 Thresholding Used in image segmentation(classify pixels based on their gray levels)Fixed thresholding is to distinguish object(s)from background.Threshold fixed manually.Adaptive threshold calculates threshold level via histogram of the image.Ideally histogram should have two peaks.However single and multiple peak histograms are not uncommon.72 Different Histograms Thresholding 73 74 75 Zm N-1 RHST z 76 77 78 Use of Boundary Characteristics for Use of Boundary Characteristics for Histogram Improvement Histogram Improvement From the privies discussion,an indication of whether a pixel is on an edge may be obtained by computing its gradient.In addition,use of the Laplacian can yield information regarding whether a given pixel lies on the dark or light side of an edge.The average value of the Laplacian is 0 at the transition of an edge,so in practice the valleys of histograms formed from the pixels selected by a gradient/Laplacian criterion can be expected to be sparsely populated.We can calculate gradient f and the Laplacian 2f at any point(x,y)in an image.These two quantities may be used to form a three-level image,as follows 000),(22 T(i,j)I(i,j)=uint8(255);else I(i,j)=uint8(0);end end end imshow(I);Sauvola Christian 97 where m is local mean,s is local standard deviation,R is the dynamic range of standard deviation fixed to 128 and k is a constant set to 0.20.5.The improved method performs better for well-scanned document images,but it faces difficulties in dealing with images that do no correspond with the hypothesis.where M is the minimum gray level of the whole image,R is set to the maximum of the standard deviations of the image and k is fixed at 0.5.Adaptive Thresholding the algorithm focuses only on the maximum standard deviation of the entire image,its performance degrades when the input image involves great changes in background luminance.98 Meng-Ling Feng 99 Based on empirical study,setting the values of a1,k1,and k2 in the ranges of 0.1-0.2,0.01-0.05 and 0.15-0.25 and r to 2,respectively,can generally produce good binarization results.100 Segmentation Thresholding in RGB space For color or multi-spectral images,it may be possible to set different thresholds for each color channel,and so select just those pixels within a specified cuboid in RGB space.Another common variant is to set to black all those pixels corresponding to background,but leave foreground pixels at their original color/intensity(as o