COMP9517_24T2W5_Image_Segmentation_Part_1.pdf

COMP9517: Computer Vision Image Segmentation Part 1 Professor Erik Meijering Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 1  Introduction What do you see in this image? Copyright (C) UNSW COM...

COMP9517: Computer Vision Image Segmentation Part 1 Professor Erik Meijering Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 1  Introduction What do you see in this image? Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 2  Introduction Segmentation is the process of partitioning an image into a set of meaningful regions for further analysis One of the oldest and most widely studied problems in computer vision Background Image Hand Ring Foreground Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 3  Introduction Region properties to facilitate image segmentation – Regions should be uniform / homogeneous in some characteristics – Region interiors should be simple and without holes or missing parts – Adjacent regions should have significantly different values in terms of the characteristics in which individually they are uniform – Boundaries of each region should be smooth and spatially accurate Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 4  Introduction Different levels of region identification and segmentation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 https://arxiv.org/abs/1704.06857 5  Introduction Segmentation approaches – Region based – Contour based – Template matching based – Splitting and merging based – Global optimisation based Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 6  Introduction Issues and challenges – So far there is no single segmentation method working well for all problems – Special domain knowledge of the application is typically essential for the development of successful computer vision methods for segmentation Source: http://www.isbe.man.ac.uk/~bim/Models/asms.html Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 7  Introduction Even within an application domain images may vary widely All these examples are microscope images of biological cells Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 8  Outline Recap of basic segmentation methods – Thresholding – K-means clustering – Feature extraction and classification More sophisticated segmentation methods 1. Region splitting and merging 5. Superpixel segmentation 2. Watershed segmentation 6. Conditional random field 3. Maximally stable extremal regions 7. Active contour segmentation 4. Mean-shifting algorithm 8. Level-set segmentation How to evaluate segmentation methods – Quantitative evaluation metrics – Receiver operating characteristic Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 9  Recap of Basic Segmentation Methods Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 10  Thresholding Fine if regions have sufficiently different intensity distributions Image Histogram 0 255 Threshold Segmentation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 11  Thresholding Problematic if regions have overlapping intensity distributions Image Histogram 0 255 Threshold? Segmentation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 12  Thresholding Problematic if regions have overlapping intensity distributions Image Histogram 0 255 Threshold? Segmentation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 13  Thresholding Problematic if regions have overlapping intensity distributions Image Histogram 0 255 Threshold? Segmentation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 14  K-Means Clustering May work if the number of clusters is known a priori Original Image Labeled Image Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 15  K-Means Clustering Problematic if the number of clusters is not known a priori Original Image Labeled Image Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 16  Feature Based Classification Segmentation by sliding-window patch-wise feature extraction and then classification… requires many examples for training Original Image Ground Truth Labeled Image Schroff et al. Single-histogram class models for image segmentation. In: Computer Vision, Graphics and Image Processing, Springer, 2006. Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 17  More Sophisticated Segmentation Methods Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 18  1. Region Splitting and Merging Basic computational approach – Recursively split the whole image into pieces based on region statistics – Recursively merge regions together in a hierarchical fashion – Combine splitting and merging sequentially Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 19  Region Splitting and Merging The simplest possible technique – Apply thresholding and then compute connected components – Rarely sufficient due to lighting and intra-object statistical variations 1 if f ≥ t θ ( f , t) =  0 else How many connected components (separate objects) are there in this thresholded image? Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 20  Connected Components Connectivity in two dimensions (2D) 4-connected 8-connected Connectivity in three dimensions (3D) 6-connected 18-connected 26-connected Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 21  Connected Components Number of components depends on the chosen connectivity Thresholded image 4-connected objects 8-connected objects Number of objects = 10 Number of objects = 1 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 22  Connected Components Algorithm First pass N4 N8 – Check each pixel (top-left to bottom-right) – If an object pixel, check its neighbors (𝑁𝑁4 or 𝑁𝑁8 ) – If no neighbors have labels, assign a new label – If neighbors do have labels, assign the smallest – Record label equivalences while assigning Equivalence sets {1,2,6} {3,4,5} Second pass – Check each pixel (top-left to bottom-right) – Replace each label with its smallest equivalent – All background pixels default to the zero-label Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 23  Region Splitting Clustering in the measurement space – Assume homogeneous regions in the image appear as clusters in measurement space (simple example: the histogram) – Optimise metrics of intra-region similarity and inter-region dissimilarity – Clustering can be accomplished by finding the valleys in the space and declaring the intervals between them as the clusters – Segmentation is mapping the clusters back to the image domain – Connected components of the cluster labels constitute the segments Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 24  Region Splitting Recursive histogram based splitting – Perform histogram mode seeking first on the whole image – Then on each of the regions obtained from the resultant clusters – Until the regions obtained cannot be decomposed further Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 25  Region Merging Heuristics-based region merging – Using the relative boundary lengths and edge strengths – Using the distance between the closest points or farthest points – Using the average colour difference or size difference Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 26  Region Merging Graph-based region merging – Use relative dissimilarities between regions 𝑅𝑅𝑖𝑖 to merge – Represent regions as a graph using minimum spanning tree (MST) – Define a dissimilarity measure 𝜔𝜔 such as intensity difference – Compute internal region dissimilarity using the graph edges 𝑒𝑒 I ( R) = max ω (e) e∈MST( R ) – Compute dissimilarity between adjacent regions D( Ri , R j ) = min ω (e) e∈( vi ∈Ri , v j ∈R j ) – Merge any two adjacent regions whose dissimilarity is smaller than the minimum of the internal differences of these two regions Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 27  Region Merging Felzenszwalb & Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision 59(2): 167–181, 2004. Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 28  Region Merging Merging by region growing – Define a similarity measure – Start from one seed pixel for the region – Add neighbouring pixels to the region if they are similar – Repeat previous step until no more pixels are similar https://users.cs.cf.ac.uk/Dave.Marshall/Vision_lecture/node35.html Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 29  Region Growing https://sbme-tutorials.github.io/2019/cv/notes/6_week6.html Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 30  2. Watershed Segmentation Based on the analogy of immersion of a topographic surface f ( x) Water Build a dam Watershed lines (dams) Basin Basin Basin Basin Basin Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 31  Watershed Segmentation Meyer’s flooding algorithm 1) Choose a set of markers to start the flooding. These could be, for example, all local minima. Give each a different label. 2) Put neighbouring pixels of each marker into a priority queue. A pixel with more similar gray value has higher priority. 3) Pop the pixel with the highest priority level from the queue. If the neighbours of the popped pixel that have already been labelled all have the same label, then give the pixel that same label. Put all non-labelled neighbours that have never been in the queue into the queue. 4) Repeat step 3 until the queue is empty. The resulting non-labelled pixels are the watershed lines Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 32  Watershed Segmentation Example segmentation results Input image Segmentation results Watershed of input Watershed of smoothed input https://imagej.net/Classic_Watershed Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 33  Watershed Segmentation Invert the image or compute edges if needed to get minima Important notes regarding watershed based segmentation – Images often have many local minima, leading to heavy oversegmentation – Preprocessing (image smoothing) may be needed to reduce false minima – Postprocessing (basin merging) may be needed to reduce fragmentation – Many different implementations and pre/postprocessing criteria exist – It is possible to start from user-defined markers instead of local minima Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 34 3. Maximally Stable Extremal Regions Basics of maximally stable extremal regions (MSER) – Connected components characterised by almost uniform intensity surrounded by contrasting background – Constructed through a process of trying multiple thresholds and analyzing the shape of the connected components – Selected regions are connected components whose shape remains virtually unchanged over a large set of thresholds. https://www.youtube.com/watch?v=tWdJ-NFE6vY Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 35  Maximally Stable Extremal Regions Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 36  Maximally Stable Extremal Regions Example MSER segmentation results https://doi.org/10.1186/1687-6180-2012-83 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 37  4. Mean Shifting How would you segment this image based on colour alone? Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 38  Mean Shifting K-means clustering has limitations – Need to choose K – Sensitive to outliers – Prone to local minima Mean shifting is a good alternative in many applications – Seeks stationary points (peaks/modes) in a density function – Attempts to find all possible cluster centers in feature space – Does not require knowing the number of clusters a priori – Is a variant of iterative steepest-ascent method Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 39  Mean Shifting Iterative mode searching 1. Initialize a random seed point 𝑥𝑥 and window 𝑁𝑁 2. Calculate the mean (center of gravity) 𝑚𝑚(𝑥𝑥) within 𝑁𝑁 3. Shift the search window to the mean 4. Repeat Step 2 until convergence m( x ) = ∑ xi ∈N ( x ) K ( xi − x) xi ( x) exp(− | x |2 ) K= ∑ xi ∈N ( x ) K ( xi − x) Mean (center of gravity) Kernel (weight function) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 40  Mean Shifting Iterative re-estimation of the weighted mean Mean shift vector 𝑚𝑚 𝑥𝑥 − 𝑥𝑥 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 41  Mean Shifting Use a set of seed points to find all possible cluster centers https://sbme-tutorials.github.io/2019/cv/notes/6_week6.html Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 42  Mean Shifting Performing image segmentation by mean shifting – Define features (colour, gradients, texture, et cetera) – Transform image pixels to points in the feature space – Initialise windows at multiple seed locations in feature space – Perform mean shifting for each window until convergence – Merge windows that end up near the same location – Cluster all points according to window traversal https://doi.org/10.1109/34.1000236 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 43  Mean Shifting Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 44  Mean Shifting Replace segmented region colours by their cluster means https://doi.org/10.1109/34.1000236 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 45  Mean Shifting Advantages – Model-free (does not assume any prior shape on data clusters) – Has just a single parameter (window size) – Finds variable number of modes (clusters) – Robust to outliers Limitations – Computationally expensive (need to shift many windows) – Output depends on window size parameter value – Window size (bandwidth) selection is not trivial – Does not scale well with dimensionality of feature space Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 46  5. Superpixel Segmentation Pixel-wise sliding window segmentation – Too many windows (a.k.a. image patches) Superpixel-based segmentation improves efficiency – Group similar pixels into a superpixel – Superpixels together are an over-segmentation of the image – Ultimate segmentation (classification) performed on superpixels Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 47  Superpixel Segmentation Simple linear iterative clustering (SLIC) – A popular superpixel generation algorithm – Preserves object boundaries, is fast, and memory efficient Superpixels of size 64, 256, and 1024 pixels (approximately) https://ivrl.epfl.ch/research-2/research-current/research-superpixels/ Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 48  Superpixel Segmentation Simple linear iterative clustering (SLIC) https://doi.org/10.1109/TPAMI.2012.120 1. Initialise cluster centers 𝐶𝐶𝑗𝑗 on pixel grid with step size 𝑆𝑆 2. Move 𝐶𝐶𝑗𝑗 to position in 3 × 3 window with smallest gradient 3. Compute distance 𝐷𝐷𝑖𝑖𝑖𝑖 for each pixel 𝑖𝑖 in 2𝑆𝑆 × 2𝑆𝑆 window around 𝐶𝐶𝑗𝑗 4. Assign each pixel 𝑖𝑖 to the cluster 𝐶𝐶𝑗𝑗 with smallest distance 𝐷𝐷𝑖𝑖𝑖𝑖 5. Recompute cluster centers as mean colour and position of pixels in 𝐶𝐶𝑗𝑗 6. Iterate (go to Step 3) until the residual error is small dlab = (l j − li ) 2 + (a j − ai ) 2 + (b j − bi ) 2 (distance in CIELAB color space) d xy = ( x j − xi ) 2 + ( y j − yi ) 2 (distance in pixel space) 2 dlab d xy2 =D 2 + 2 (weight 𝑚𝑚 controls influence of color over spatial distance) m S Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 49  6. Conditional Random Field Superpixels provide a basis for further segmentation – Determine spatial relationship between the superpixels – Compute similarities between superpixels – Group superpixels to form larger segments Conditional random field (CRF) approach A probabilistic graphical model that encodes the relationships between observations (i.e. superpixels) and constructs a consistent interpretation (i.e. segmentation) for a set of data (i.e. an image) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 50  Conditional Random Field An undirected graphical structure – Nodes: superpixels (value based on features of superpixels) – Edges: adjacency (value based on similarity between superpixels) Superpixels Graph https://doi.org/10.1007/s11263-008-0140-x Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 51  Conditional Random Field Segmentation as an energy minimisation problem E ( s, c ) = ∑ ϕ (s , c ) +∑ψ (s , s ) i i i ij i j – Unary potentials 𝜑𝜑 Data term (based on graph node values) Computes the cost of superpixel 𝑠𝑠𝑖𝑖 belonging to class 𝑐𝑐𝑖𝑖 A lower cost means a higher likelihood of 𝑠𝑠𝑖𝑖 belonging to 𝑐𝑐𝑖𝑖 Can be obtained via superpixel classification – Pairwise potentials 𝜓𝜓 Smoothness term (based on graph edge values) Computes a cost of neighbourhood consistency A cost is assigned if adjacent superpixels are assigned to different classes Higher similarity results in a lower cost (0 if assigned to the same class) Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 52  Conditional Random Field Energy minimization is solved via graph cut (max-flow min-cut) https://doi.org/10.1109/TPAMI.2004.60 https://doi.org/10.1109/TGRS.2016.2627638 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 53  Conditional Random Field Segmentation example with multiple source-sink terminals https://doi.org/10.1109/rivf.2012.6169870 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 54  7. Active Contour Segmentation A contour based approach to object segmentation – Aims to locate object boundaries in images by curve fitting – Represents the curve by a set of control points and interpolation – Iteratively moves the control points to fit the curve to the object – Uses image, smoothness and user-guidance forces along curve Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 55  Active Contour Segmentation A well-known implementation is called the snakes algorithm – Smoothly follows high intensity gradients at the object boundary – Bridges areas of noise or missing gradients using smooth interpolation Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 56  Active Contour Segmentation Enforces a solution where gradient information is lacking Boundary? OK… 16 x 16 pixels Um… Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 57  Active Contour Segmentation Enforces a solution where gradient information is lacking Define a suitable contour model Circle, ellipse, or spline (open or closed) C :[0,1] → R n ⇒ C ( s ) = [ x( s ), y ( s ) ] n=2 Define a suitable energy functional Using internal + image + external energies 1 EC = ∫  E 0 int (C (s) ) + Eimg (C (s) ) + E ext (C (s) ) d s E.g. Bending Intensity or User energy gradient interaction Minimize the energy functional Using efficient optimization algorithms Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 58  Active Contour Segmentation Active contours / snakes are parametric models – Explicit representations of the object boundaries – Typically requires manual interaction to initialize the curve – It is challenging to change the topology of the curve as it evolves – Curve reparameterization may be required for big shape changes Level-set methods have become more popular alternatives – Implicit representations of the object boundaries – Boundaries defined by the zero-set of a higher dimensional function – Level-set function evolves to make the zero-set fit and track objects – Easily accommodates topological changes in object shape – Computationally more demanding than active contours Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 59  8. Level Set Segmentation Contour evolution over time (iterative) 𝑡𝑡 2D contour 3D level-set function https://en.wikipedia.org/wiki/Level-set_method Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 60  Level Set Segmentation Examples of level-set based segmentation https://doi.org/10.1007/s11263-006-8711-1 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 61  Level Set Segmentation A well-know implementation is the Chan-Vese model Minimize the energy functional E (C ) = µ ⋅ length(C ) +ν ⋅ area(C ) + λ1 ∫ | u0 − c1 |2 dxdy Inside( C ) + λ2 ∫ Outside( C ) | u0 − c2 |2 dxdy https://doi.org/10.1109/83.902291 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 62  How to Evaluate Segmentation Methods Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 63  Segmentation Method Evaluation https://grand-challenge.org/ Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 64  Evaluation Metrics Segmented object pixels (set S ) True object pixels (set T ) Pixel classification FP True Positives TP= S ∩ T TP Correctly segmented as object FN True Negatives TN= S c ∩ T c Correctly segmented as background False Positives FP= S ∩ T c Incorrectly segmented as object TN False Negatives FN= S c ∩ T Incorrectly segmented as background Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 65  Evaluation Metrics Sensitivity (= true-positive rate) Fraction of the true object that is correctly segmented TP TP FN TPR = TP + FN TN Specificity (= true-negative rate) Fraction of the true background that is correctly segmented FP TN TNR = TN + FP Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 66  Evaluation Metrics Receiver operating characteristic (ROC) of a method Plot of the true-positive rate (sensitivity) versus the false-positive rate (one minus the specificity) of a method as a function of its free parameter(s) Example: Thresholding Sensitivity τ = 32 τ =0 τ = 64 Image Truth Compute the sensitivity versus the τ = 256 specificity for all possible intensity thresholds 𝜏𝜏 and plot the results 1 – Specificity Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 67  Evaluation Metrics Comparing the performance of methods by ROC analysis Area under the curve (AUC) Worst = 0.0 0.1 0.2 0.3 Sensitivity 0.4 Random = 0.5 0.6 0.7 0.8 0.9 Best = 1.0 1 – Specificity Higher AUC = better method Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 68  Evaluation Metrics Precision (= positive predictive value) Fraction of the segmented object that is correctly segmented TP FP TP P= F-measure TP + FP Harmonic mean of precision and recall Recall (= sensitivity) R ⋅P Fraction of the true object that F= 2 ⋅ is correctly segmented R+P TP FN TP R= TP + FN Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 69  Evaluation Metrics Jaccard similarity coefficient (JSC) Fraction of the union of the segmented object and the FP true object that is correctly segmented TP FN S ∩T TP JSC = = S ∪T FP + TP + FN Dice similarity coefficient (DSC) Fraction of the segmented object set joined with the true FP object set that is correctly segmented TP FN S ∩T 2 TP DSC 2= = S +T FP + 2 TP + FN Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 70  References and Acknowledgements Chapter 3 & 5 of Szeliski 2010 Shapiro and Stockman 2001 Some images drawn from Szeliski 2010 Some images drawn from papers as indicated Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 71  Example exam question Given the following binary image after segmentation. To automatically identify the objects (in white) in this image we can use the connected components labelling algorithm. How many separate objects will this algorithm find here if it uses 4-connectivity? A. 4 B. 5 C. 6 D. 7 Copyright (C) UNSW COMP9517 24T2W5 Image Segmentation Part 1 72