Transcription
Median Filtering andMorphological FilteringYao WangPolytechnic University, Brooklyn, NY 11201With contribution from Zhu Liu, Onur Guleryuz, andGonzalez/Woods, Digital Image Processing, 2ed
Lecture Outline Median filter Rank order filter Bilevel Morphological filters– Dilation and erosion– Opening and closing Grayscale Morphological filtersYao Wang, NYU-PolyEL5123: Non-linear Filtering2
Median Filter Problem with Averaging Filter– Blur edges and details in an image– Not effective for impulse noise (Salt-and-pepper) Median filter:– Taking the median value instead of the average orweighted average of pixels in the window Sort all the pixels in an increasing order, take the middle one– The window shape does not need to be a square– Special shapes can preserve line structuresYao Wang, NYU-PolyEL5123: Non-linear Filtering3
Median Filter: 3x3 Square Window100100 100100100100200 205203100100195 200200100100200 205195100100100 100100100WindowWidshape100100 100100100100100 200100100100200 200200100100100 195100100100100 100100100Matlab command: medfilt2(A,[3 3])Yao Wang, NYU-PolyEL5123: Non-linear Filtering4
Median Filter: 3x3 Cross Window100100 100100100100200 205203100100195 200200100100200 205195100100100 100100100WindowWidshape100100 100100100100195 200200100100200 200200100100195 200195100100100 100100100Note that the edges of the centersquare are better reservedYao Wang, NYU-PolyEL5123: Non-linear Filtering5
ExampleYao Wang, NYU-PolyEL5123: Non-linear Filtering6
Rank order filters Rank order filters– Instead of taking the meanmean, rank all pixelvalues in the window, take the n-th ordervalue.– E.g. max or min or median Properties– Non-linear T(f1 f2) T(f1) T(f2)Yao Wang, NYU-PolyEL5123: Non-linear Filtering7
Multi-level Median Filtering To reduce the computation, one can concatenate severalsmall median filters to realize a large window operation. When the small windows are designed properly, thisapproach can also help reserve edges better.MedianYao Wang, NYU-PolyEL5123: Non-linear Filtering8
Hybrid Linear/Median Filter One can combine median filters with linearor rank order filters.filtersMED1MED2MINOrMAXOrMEANMED3Yao Wang, NYU-PolyEL5123: Non-linear Filtering9
Morphological Processing Morphological operations are originallydeveloped for bilevel images for shape andstructural manipulations. Basic functions are dilation and erosion. Concatenation of dilation and erosion in differentorders result in more high level operations,including closing and opening.opening Morphological operations can be used forsmoothing or edge detection or extraction ofother features. Belongs to the category of spatial domain filter.Yao Wang, NYU-PolyEL5123: Non-linear Filtering10
Morphological Filtersfor Bilevel Imagesg A binary image can be considered as a setby considering “black”black pixels (with imagevalue “1”) as elements in the set and“white” pixels ((with value “0”)) as outsidethe set. Morphological filters are essentially setoperationsYao Wang, NYU-PolyEL5123: Non-linear Filtering11
Basic Set Operations Let x, y, z, represent locations of 2D pixels,e.g. x (x1, x2), S denote the complete set of allpixels in an image, let A, B, represent subsetsof S. Union (OR) A B {x : x A or x B}BORAA Intersection (AND)A B {x : x A and x B}BAYao Wang, NYU-PolyBANDBAEL5123: Non-linear Filtering12
Basic Set Operations ComplementA {x : x S and x A}NOTAA TranslationTl ti( A) x {z : z y x, y A}TranslationAAx ReflectionAˆ { y : y x, x A}OriginOriginYao Wang, NYU-PolyAReflectionEL5123: Non-linear FilteringA13
Dilation Dilation of set F with a structuring elementH is represented by F HF H {x : ( Hˆ ) F }xwhere Φ represent the empty set. G F H is composed of all the pointsthat when Ĥ shifts its origin to these points,at least one point of Ĥ is included in F. If the origin of H takes value “1”,F F HYao Wang, NYU-PolyEL5123: Non-linear Filtering14
Example of Dilation (1)H, 3x3, originat the centerH, 5x3H5x3, originat the centerYao Wang, NYU-PolyEL5123: Non-linear FilteringDilation enlarges a set.15
Example of Dilation (2)Note that the narrow ridge is closedFGH 3x3H,3x3, origin at the centerYao Wang, NYU-PolyEL5123: Non-linear Filtering16
Erosion Erosion of set F with a structuring elementH is represented by F H , and is definedas,F H {x : ( H ) x F } G F H is composed of points thatwhen H is translated to these points, everypoint of H is contained in F. If the origin of H takes value of “1”, F H FYao Wang, NYU-PolyEL5123: Non-linear Filtering17
Example of Erosion (1)H, 3x3, originat the centerH, 5x3H5x3, originat the centerYao Wang, NYU-PolyEL5123: Non-linear FilteringErosion shrinks a set18
Example of Erosion (2)FGH 3x3H,3x3, origin at the centerYao Wang, NYU-PolyEL5123: Non-linear Filtering19
Structuring element The shape, size, and orientation of thestructuring element depend on applicationapplication. A symmetrical one will enlarge or shrinkthe original set in all directionsdirections. A vertical one, will only expand or shrinkthe original set in the vertical direction.Yao Wang, NYU-PolyEL5123: Non-linear Filtering20
Properties of Dilation and ErosionOperators CommunitivityA B B A, but A B B A.A B {x : ( Bˆ ) x A } {x : y, y A, y ( Bˆ ) x } {x : y, y A, y x Bˆ } {x : y, y A, x y B} {x : z , x z A, z B} {x : z , z x Aˆ , z B} {x : z , z ( Aˆ ) , z B} {x : ( Aˆ ) B } B Axx DualityA B A Bˆ ,Yao Wang, NYU-PolyA B A Bˆ .EL5123: Non-linear Filtering21
Properties of Dilation and ErosionOperators DistributivityA ( B C ) ( A B) ( A C ),)A ( B C ) ( A B) ( A C ),( A B ) C ( A C ) ( B C ).) Chain rule( A B) C A ( B C ),( A B ) C A ( B C ).)Yao Wang, NYU-PolyEL5123: Non-linear Filtering22
Closing and Opening ClosingF H ( F H ) H– Smooth the contour of an image– Fill small gaps and holes OpeningF H ( F H ) H– Smooth the contour of an imageg– Eliminate false touching, thin ridges andbranchesYao Wang, NYU-PolyEL5123: Non-linear Filtering23
Example of ClosingFF H( F H ) HH 3x3H,3x3, origin at the centerYao Wang, NYU-PolyEL5123: Non-linear Filtering24
Example of OpeningFF H( F H ) HH 3x3H,3x3, origin at the centerYao Wang, NYU-PolyEL5123: Non-linear Filtering25
Example of Opening and ClosingYao Wang, NYU-PolyEL5123: Non-linear Filtering26
Properties of Opening andClosing Operators DualityF H F Hˆ , F H F Hˆ . Idempotence(F H ) H F H , (F H ) H F H . Smoothing– Removal of small holes and narrow branchescan be accomplished by concatenatingopening with closing: G ( F H ) HYao Wang, NYU-PolyEL5123: Non-linear Filtering27
Morphological Filters for GrayscaleImages The structure element h is a 2D grayscaleimage with a finite domain (Dh),) similar toa filter The morphological operations can bedefined for both continuous and discreteimages.imagesYao Wang, NYU-PolyEL5123: Non-linear Filtering28
Dilation for Grayscale Image Dilation( f h)( x, y ) max{ f ( x s, y t ) h( s, t ); ( s, t ) Dh , ( x s, y t ) D f }– Similar to linear convolution, with the max operationreplacing the sums of convolution and the additionreplacing the products of convolution.– The dilation chooses the maximum value of f h in aneighborhood of f defined by the domain of hh.– If all values of h are positive, then the output imagetends to be brightergthan the input,p dark details ((e.g.gdark dots/lines in a white background) are eitherreduced or eliminated.Yao Wang, NYU-PolyEL5123: Non-linear Filtering29
Illustration of 1-D Grayscale Dilation( f b)( s ) max{ f ( s x) b( x); x Db } max{ f ( x) b( s x); s x Db }Db [ r,r]s r x s rA rWrong result!Yao Wang, NYU-PolyEL5123: Non-linear Filtering-r 0 r30
Show correct result (in Red!)Yao Wang, NYU-PolyEL5123: Non-linear Filtering31
Erosion for Grayscale Image Erosion( f f h)( x, y ) min{{ f ( x s, y t ) h( s, t ); ( s, t ) Dh , ( x s, y t ) D f }– Similar to linear correlation, with the min operationreplacing the sums of correlation and the subtractionreplacing the products of correlation.– The erosion chooses the minimum value of f-h in aneighborhood of f defined by the domain of hh.– If all values of h are positive, then the output imagetends to be darker than the input,p brightergdetails ((e.g.gwhite dots/lines in a dark background) are eitherreduced or eliminated.Yao Wang, NYU-PolyEL5123: Non-linear Filtering32
Illustration of 1-D Grayscale Erosion( f h)( s ) min{ f ( s x) b( x); x Db }Wrong result!f(s0)-A-rs0-r s0 s0 rYao Wang, NYU-PolyEL5123: Non-linear Filtering33
Show correct resultYao Wang, NYU-PolyEL5123: Non-linear Filtering34
Example of Grayscale Dilation andErosionYao Wang, NYU-PolyEL5123: Non-linear Filtering35
Opening for Grayscale Image Openingf h ( f h) h Geometric interpretation– Think f as a surface where the height of eachpoint is determined by its gray level.– ThinkThi k theth structuret telementlt hash a gray scaleldistribution as a half sphere.– Opening is the surfaces rface formed bby the highestpoints reached by the sphere as it rolls overthe entire surface of f from underneathunderneath.Yao Wang, NYU-PolyEL5123: Non-linear Filtering36
Closing for Grayscale Image Closingf h ( f h) h Geometric interpretation– Think f as a surface where the height of eachpoint is determined by its gray level.– ThinkThi k theth structuret telementlt hash a gray scaleldistribution as a half sphere.– Closing is the ssurfacerface formed bby the lolowestestpoints reached by the sphere as it slides overthe surface of f from aboveabove.Yao Wang, NYU-PolyEL5123: Non-linear Filtering37
Illustration of 1-D GrayscaleOpening and ClosingOpeningEliminate false touching,g,thin ridges and branchesClosingFill smallll gaps andd holesh lYao Wang, NYU-PolyEL5123: Non-linear Filtering38
Example of Grayscale Opening andClosingYao Wang, NYU-PolyEL5123: Non-linear Filtering39
Morphological Operation for ImageEnhancement Morphological smoothing– Opening followed by closing,( f h) h– Attenuated both bright and dark detailsYao Wang, NYU-PolyEL5123: Non-linear Filtering40
Morphological Operation for ImageEnhancement Morphological gradient( f h) ( f h)– The difference between the dilated and eroded images, Valley detection f h f– Detectetect dadark tetext/linest/ es fromo aggrayay bacbackgroundg ou d Boundary detection f f hYao Wang, NYU-PolyEL5123: Non-linear Filtering41
Application in Face Detection Use color information to detect candidate faceregion Verify the existence of face in candidate regionInputimageSkin-tonecolor likelihoodYao Wang, NYU-PolyOpeningprocessedimageEL5123: Non-linear FilteringBlobcoloringFacedetectionresult42
Written Assignment1.For the image A in Figure 1(b), using the structuring element B in Figure 1(a), determine theclosing and opening of A by B.originFigure 1. (a)2.Figure 1. (b)Consider a contiguous image function f and a gray scale structuring element h described by 1 4 x, y 4;f ( x, y ) 0 otherwise 1 1 x, y 1;h( x, y ) 0 otherwiseD i thDerivethe gray scalel dildilationti andd erosioni off f bby hh, respectively.ti lYao Wang, NYU-PolyEL5123: Non-linear Filtering43
Computer Assignment1.2.3.4.5.Write a program which can i) add salt-and-pepper noise to an image with a specifiednoise density, ii) perform median filtering with a specified window size. Consideronly median filter with a square shape. Try two different noise density (0.05, 0.2)and for each density, comment on the effect of median filtering with different windowsizes and experimentally determine the best window size.size You can use imnoise( )to generate noise. You should write your own function for median filtering. You canignore the boundary problem by only performing the filtering for the pixels inside theboundary.In a previous assignment you have created a program for adding Gaussian noiseandd filtfilteringi usingi average filtfilter. AApplyl ththe averagingi filtfilter andd ththe mediandi filtfilter bboththto an image with Gaussian noise (with a chosen noise variance) and with salt-andpepper noise (with a chosen noise density). Comment on the effectiveness of eachfilter on each type of noise.Use the MATLAB pprogramgimdilate(( ) and imerode(( ) on a samplep BW image.g Tryyasimple 3x3 square structuring element. Comment on the effect of dilation anderosion. By concatenating the dilation and erosion operations, also generate resultof closing and opening, and comment on their effects. Repeat above with a 7x7structure element. Comment on the effect of the window size. You can generate abinaryy imageg from a ggrayscaleyone byy thresholding.gRepeat above on a gray scale image, using MATLAB gray scale dilation and erosionfunctions.Optional (for your own practice, will not be graded): write your own program forgray-scale dilation and erosion.Yao Wang, NYU-PolyEL5123: Non-linear Filtering44
Reading R. Gonzalez, “Digital Image Processing,”Chapter 55.33 and Chapter 99. A. K. Jain, “Fundamentals of Digital ImageProcessing ” Section 7Processing,”7.44 and Section 99.9.9Yao Wang, NYU-PolyEL5123: Non-linear Filtering45
Multi-level Median Filtering To reduce the computation, one can concatenate several small median filters to realize a large window operation. When the small windows are designed properly, this approach can also help reserve edges better. Median Yao Wang, NYU-Poly EL5123: Non-linear Filtering 8
