Mathematical morphology • A tool for extraction of shape related information from images – We will first work with binary (0 or 1) images – Later extend to grayscale images • Based on set theory – Reflection of a set: – Translation of a set: 1 € ˆ B = w w = −b, for b ∈ B{ }€ B( )z= c c = b + z, for b ∈ B{ }Structuring element • Structuring element (SE): A set that defines a binary shape which we will use for morphological processing – 4 examples of SEs – We will pad to smallest possible rectangle. Shaded squares belong to SE. 2Morphological operation: Erosion • From set A, create a new set by running the SE A over A – At each location if B is completely contained in A mark that location as a member of the new set, otherwise don’t. 3Erosion • Set definition 4 € AΘB = z B( )z⊆ A{ }Erosion examples 5Morphological operation: Dilation • Does the opposite of erosion • From set A, create a new set by running the SE A over A – At each location if at least one pixel of the reflection of B overlaps A mark that location as a member of the new set, otherwise don’t. • Set definition 6 € A ⊕ B = zˆ B ( )z A ≠ ∅     Dilation examples 7Duality of erosion and dilation • Erosion of A by B is the complement (background) of the dilation of the complement (background) of A by the reflection of B • Also 8 € AΘB( )c= Ac⊕ˆ B € A ⊕ B( )c= AcΘˆ BOpening and closing • Dilation: expands foreground • Erosion: shrinks foreground • 2 new operations based on dilation and erosion – Opening: breaks narrow connections, eliminates small protrusions, smoothes contour of foreground – Closing: fills in small breaks and concavities, also smoothes contour – There is a duality between opening and closing, too 9 € A  B = AΘB( )⊕ B€ A • B = A ⊕ B( )ΘBOpening and closing example 10 Opening ClosingGeometric interpretations 11 Opening: Roll B inside Closing: Roll B outsideBoundary extraction • The thickness of the boundary depends on the size of the SE 12 € βA( )= A − AΘB( )Boundary extraction example 13 3x3 structuring elementHole filling algorithm • Recursive definition, will converge • X0 needs a seed point in each hole • The dilation is intersected with the complement of A so it can’t cross boundary 14 € Xk= Xk −1⊕ B( ) Ac k =1,2,3,...Hole filling example 15 Seed in one hole only Seed in all holesConnected components • Put a seed point in X0 for component of interest • Recursive, stop when Xk=Xk-1 • 4-connectivity mask? 16 € Xk= Xk −1⊕ B( ) A k = 1,2,3,...8-connectivityCan we place seeds automatically? 1. Pick a random point that is in A 2. Find connected component 3. Remove this component from A 4. Go to 1 unless A empty 17Hit-or-Miss Transformation • A shape detection tool • Contains all points at which B1 found a match in A and B2 found a match in Ac 18 € A * B = AΘB1[ ] AcΘB2[ ]example B1= D,B2= W − DThinning • A*B is the hit-or-miss transform – With no background required so really just erosion 19 € A ⊗ B = A − (A * B) € B = B1,B2,…,Bn{ }A ⊗ B = A ⊗ B1( )⊗ B2( )⊗ B3( )…Skeleton • The skeleton of A is S(A): – If z is a point in S(A) and (D)z is the largest disk centered at z and contained in A, one cannot find a larger disk containing (D)z and included in A – The disk (D)z touches the boundary of A at two or more locations 20Skelotonization 21 € S(A) = Sk(A)k =0KSk(A) = (AΘkB) − (AΘkB )  BK = max k (AΘkB) ≠ ∅{ }A = Sk(A) ⊕ kB( )k =0Kk successive erosions Opening k successive dilationsSkeleton example 22Pruning 23 • Skeletonization can result in spurious components. Pruning can be used to remove these – Read from bookDenosing by opening/closing 24Morphological reconstruction • 2 images and 1 SE – G, mask image constrains transformation – F, marker image defines starting points. • F is assumed to be a subset of G – B, SE defines connectivity • Geodesic dilation of size 1 • Geodesic dilation of size N 25 € DG(1)F( )= F ⊕ B( )G€ DG(n )F( )= DG(1)DG(n −1)F( )( )Geodesic dilation • Geodesic dilation of size 1 • Geodesic dilation of size n 26 € DG1F( )= F ⊕ B( )G€ DG(n )F( )= DG(1)DG(n −1)F( )( )Geodesic erosion • Geodesic erosion of size 1 • Geodesic erosion of size n 27 € EG1F( )= FΘB( )G€ EG(n )F( )= EG(1)EG(n −1)F( )( )Opening by reconstruction • Opening – Erosion removes small objects – Subsequent dilation attempts to restore the shape of remaining objects, but there is no guarantee • Opening by reconstruction – Erosion by B removes small objects – Geodesic dilation is repeated k times until no further change using the original image G as the mask. This restores the exact shapes of remaining objects 28 € DF(k )FΘB( )Opening by reconstruction example 29Gray-scale morphology • Dilation • Erosion – Note the reflection • What are these operations similar to? • This type of SE is called flat. 30 € fΘb[ ]x, y( )=(s,t )∈bminf x + s, y + t( ){ }€ f ⊕ b[ ]x, y( )=(s,t )∈bmaxf x − s, y − t( ){ }SE: Flat disk radius 2Opening and closing • Defined as for binary images. – Open: erode+dilate – Close: dilate+erode • Morphological smoothing – Open with SE, close with same SE 31Morphological smoothing example 32Morphological gradient 33 € f ⊕ b( )− fΘb( )Top-hat / Bottom-hat • Top-hat – Returns objects removed by opening – Used for light objects on dark background • Bottom-hat – Returns objects removed by closing – Used for dark objects on light background • Application – Can be used to preprocess an image before segmentation (by thresholding) to remove effects of illumination. How? 34 € f − f  b( )€ f − f • b( )Example