COMP9517_24T2W5_Image_Segmentation_Part_2.pdf

COMP9517: Computer Vision Image Segmentation Part 2 Professor Erik Meijering Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 1 How to improve image segmentation results? Processing using mathematical morphology...

COMP9517: Computer Vision Image Segmentation Part 2 Professor Erik Meijering Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 1 How to improve image segmentation results? Processing using mathematical morphology How to clean up background noise? How to clean up object noise? How to separate touching objects? How to close holes in objects? How to extract object contours? How to compute distances? …  Binary mathematical morphology (applies to binary images)  Gray-scale mathematical morphology (applies to gray-scale images) Nonlinear image processing based on set-theory rather than on calculus Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 2 Binary image representations x 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0  1  2 0 0 1 0 0 0 0 0 0 0 I = {(1,1),(2,1),   3 0 0 0 0 0 0 0 0 0 0 (7,1),(2, 2), y 4 0 0 0 0 0 0 0 0 0 0   (5,5),(5,6), 5 0 0 0 0 0 1 0 0 0 0 6 0 0 0 0 0 1 1 0 0 0 (6,6),(6,7),   0 0 0 0 0 0 1 0 0 0 7 0 (2,8),(3,8)} 8  0 1 1 0 0 0 0 0 0  9 0 0 0 0 0 0 0 0 0 0  Binary image Image as matrix Image as set white = foreground 1 = foreground black = background 0 = background Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 3 Basic set operations NA NB Given sets A = { } ai i =1 and B = { } bi i =1 , with ai , bi ∈ Z n, we have Translation: {ci | ci = Ax = ai + x, ai ∈ A} for any given x ∈ Z n {xi | xi = Reflection: Ar = −ai , ai ∈ A} A Ax A Complement:= c {xi | xi ∉ A} Ac Union: A ∪= B {xi | xi ∈ A ∨ xi ∈ B} A∪ B B Intersection: A ∩= B {xi | xi ∈ A ∧ xi ∈ B} Difference: A −= B {xi | xi ∈ A ∧ xi ∉ B} A− B A∩ B Cardinality: | A |= NA and | B |= NB Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 4 Dilation of binary images Definition of binary dilation: I= ⊕S n { x | Sxr ∩ I ≠ ∅} That is, the set of points x ∈ Z for which the intersection of the imageI with the reflected version of a structuring element S translated to x , is not empty I I ⊕S Added S ⊕ = (0,0) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 5 Erosion of binary images Definition of binary erosion: = I S {x | S x ⊆ I } n That is, the set of points x ∈ Z for which the structuring element S translated over x is completely contained in the image I I I S Removed S = (0,0) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 6 Structuring elements In principle a structuring element can have any shape … … but the symmetric 3 x 3 structuring element is used most often Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 7 Dimensional decomposition Decomposition of the basic structuring element I⊕ = (I ⊕ )⊕ I = (I ) Dilation Erosion Iterative decomposition I⊕ = I⊕ ⊕ ⊕ ⊕ Applies to dilation and erosion Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 8 Opening of binary images Definition of binary opening: I  S = ( I S)⊕ S That is, an erosion followed by a dilation using the same structuring element Example using the basic 3 x 3 structuring element: I I S I S Eliminates details smaller than the structuring element outside the main object Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 9 Closing of binary images Definition of binary closing: I S = ( I ⊕ S ) S That is, a dilation followed by an erosion using the same structuring element Example using the basic 3 x 3 structuring element: I I ⊕S I S Eliminates details smaller than the structuring element inside the main object Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 10 Morphological edge detection Difference between the dilated and the eroded image I ⊕S I I ⊕S −I S – outer edge + inner edge Copyright (C) UNSW I S COMP9517 24T2W5 Image Segmentation Part 2 11 Binary object outlines How to get a one-pixel thick outline of all objects in the image? I I ⊕S −I Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 12 Reconstruction of binary objects How to create an image containing selected objects only? Create a marker image R0 containing seed pixels from each selected object of image I and then iteratively compute Ri= ( Ri −1 ⊕ S ) ∩ I until Ri = Ri −1 Objects of interest I R0 R Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 13 Reconstruction of binary objects How to remove objects that are only partly in the image? Take the boundary pixels B of input image I as the seeds, compute the reconstruction R from those seeds, and subtract the result from the input I B R O – Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 14 Reconstruction of binary objects How to fill all holes in all of the objects in the image? Take the complement I c of image I , take the boundary pixels of I c as seeds, compute reconstruction R of I c from those seeds, take the complement R c I Ic R Rc Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 15 Distance transform of binary images How to compute the distance of object pixels to the background? Denote input image I as I 0 and iteratively compute I i = I i −1 S for i = 1, 2,... while setting all pixels eroded in iteration i to value i in the output image D I D Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 16 Ultimate erosion of binary images How to find representative center points for all the objects? Compute the distance transform of the image and find all the local maxima This is the same as keeping only the last object pixels before final erosion I D M Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 17 Ultimate erosion and reconstruction How to separate objects that are touching each other? Perform ultimate erosion and then perform a reconstruction of the result with the additional constraint that objects may not merge I D M R Since elongated objects may result in multiple local maxima this approach works best for objects that are more or less circular Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 18 Ultimate dilation of binary images How to find the background points equidistant to the objects? Iteratively dilate the image while imposing the non-merging constraint The result is called the Voronoi (or Dirichlet) tessellation of the objects I V Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 19 Ultimate dilation of binary images How to find the background points equidistant to the objects? Iteratively dilate the image while imposing the non-merging constraint The result is called the Voronoi (or Dirichlet) tessellation of the objects I V Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 20 Skeletonization of binary images How to find a representative centerline of the objects? Iteratively apply conditional erosion (thinning) that does not break the connectivity of the result and does not remove single pixels or end-pixels The resulting one-pixel thick structure is called the skeleton of the object Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 21 Binary morphology of nD images The presented concepts extend to any dimensionality Example of a 3D binary image Volumetric pixels (“voxels”) 3 x 3 x 3 voxel structuring element  3D dilation  3D opening  3D erosion  3D closing  And all algorithms based on it Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 22 Gray-scale mathematical morphology Consider nD gray-scale images as (n+1)D binary images… U U −1 2D gray-scale image I 3D binary image U ( I ) The landscape surface with the volume below is called the umbra of the image Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 23 Dilation of gray-scale images I ⊕ S U −1 [U ( I ) ⊕ U ( S ) ] Definition of gray-scale dilation: = That is, the binary dilation of the umbra U ( I ) of gray-scale image I with the umbra U ( S ) of gray-scale structuring element S , turned back into gray-scale Example in 1D U (I ) Added I I ⊕S (0,0) ⊕ S U (S ) Any gray-scale S is possible but the flat one (as shown here) is used most often Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 24 Dilation of gray-scale images Equivalent definition: ( I ⊕= S ) ( x) max p {I (x − p) + S (p)} For a flat and symmetrical structuring element this is simply local max-filtering I S I ⊕S 7 x 7 pixels ⊕ Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 25 Erosion of gray-scale images Definition of gray-scale erosion: I S = U −1 [U ( I ) U ( S )] That is, the binary erosion of the umbra U ( I ) of gray-scale image I with the umbra U ( S ) of gray-scale structuring element S, turned back into gray-scale Example in 1D U (I ) Removed I I S (0,0) S U (S ) Any gray-scale S is possible but the flat one (as shown here) is used most often Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 26 Erosion of gray-scale images Equivalent definition: ( I S ) (x) min p {I (x + p) − S (p)} = For a flat and symmetrical structuring element this is simply local min-filtering I S I S 7 x 7 pixels Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 27 Opening of gray-scale images Definition of gray-scale opening: I  S = ( I S)⊕ S Gray-scale erosion and then gray-scale dilation with same structuring element I S I S 3 x 3 pixels  Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 28 Closing of gray-scale images Definition of gray-scale closing: I S = ( I ⊕ S ) S Gray-scale dilation and then gray-scale erosion with same structuring element I S I S 3 x 3 pixels Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 29 Morphological smoothing of gray-scale images Suppressing image structures of specific size (and shape)  High-valued (bright) image structures are removed by gray-scale opening  Low-valued (dark) image structures are removed by gray-scale closing I I S (radius = 7 pixels) I S (radius = 25 pixels) Behold the power of nonlinear filtering (not possible with linear filtering) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 30 Morphological gradient of gray-scale images Difference between the dilated and the eroded image D= I ⊕ S I G= D − E – Copyright (C) UNSW E=I S COMP9517 24T2W5 Image Segmentation Part 2 31 Morphological gradient of gray-scale images 32 Outer gradient and inner gradient D D−I I Copyright (C) UNSW E I −E Morphological gradient of gray-scale images Sum of outer gradient and inner gradient D−I + Copyright (C) UNSW I −E COMP9517 24T2W5 Image Segmentation Part 2 33 Morphological Laplacean of gray-scale images Difference between outer gradient and inner gradient D−I L = D + E − 2I D I E – G L 0 Copyright (C) UNSW I −E COMP9517 24T2W5 Image Segmentation Part 2 34 Top-hat filtering of gray-scale images I ⊕S (Radius 10 pixels) Closing S O ̶ Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 35  Top-hat filtering of gray-scale images Image intensity 36 Notice that the profiles are 1D but the filtering was performed in 2D I ⊕S S Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 Position along scan line  Top-hat filtering of gray-scale images Image intensity 37 I O + 255 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 Position along scan line Summary of mathematical morphology Powerful toolbox of methods around image segmentation  Gray-scale morphology for pre-processing Removal of gray-scale noise Before segmentation Removal of background shading Removal of unwanted image structures  Binary morphology for post-processing Closing holes in objects and background Finding the inner or outer outline of objects After segmentation Detecting and separating touching objects Extracting representative shapes of objects Computing distances within and between objects Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 38 Example exam question Given a binary input image 𝐼𝐼 to which we apply the following algorithm: Step 1: Create a copy 𝐶𝐶 of input image 𝐼𝐼. Step 2: Copy the boundary pixels of 𝐶𝐶 into new image 𝐵𝐵. Step 3: Compute the reconstruction 𝑅𝑅 of 𝐶𝐶 from 𝐵𝐵. Step 4: Compute output 𝑂𝑂 by subtracting 𝑅𝑅 from 𝐼𝐼. What does the output image 𝑂𝑂 contain? A. The same objects as the input image whatever the input. B. The same objects as the input image but with holes filled. C. The same objects as the input image except the boundary objects. D. The same objects as the input image but with touching objects separated. Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 2 39