COMP9517: Computer Vision
Image Segmentation Part 1
Week 5 COMP9517 2021 T1 1
Introduction • What do you see in this image?
Week 5 COMP9517 2021 T1 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
Image
Background
Hand
Ring
Week 5
COMP9517 2021 T1
3
Foreground
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
Week 5
COMP9517 2021 T1 4
Introduction
• Different levels of region identification and segmentation
Week 5 COMP9517 2021 T1 https://arxiv.org/abs/1704.06857 5
Introduction
• Segmentation approaches
– Region based
– Contour based
– Template matching based
– Splitting and merging based
– Global optimisation based
Week 5
COMP9517 2021 T1 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
Week 5 COMP9517 2021 T1 7
Introduction
• Even within an application domain images may vary widely
All these examples are microscope images of biological cells
Week 5 COMP9517 2021 T1 8
• Results from several popular segmentation techniques
a) Active contours
b) Level sets
c) Graph-based merging
d) Mean shift
e) Normalised cuts
f) Binary MRF
Introduction
Week 5
COMP9517 2021 T1 9
Outline
• Recap of basic segmentation methods – Thresholding
– K-means clustering
– Feature extraction and classification
• More sophisticated segmentation methods
– Region splitting and merging
– Watershed segmentation
– Maximally stable extremal regions – Mean-shifting algorithm
– Superpixel segmentation
– Conditional random field
– Active contour segmentation – Level-set segmentation
• How to evaluate segmentation methods – Quantitative evaluation metrics
– Receiver operating characteristic
Week 5 COMP9517 2021 T1 10
Recap of Basic Segmentation Methods
Week 5 COMP9517 2021 T1 11
Thresholding
• Fine if regions have sufficiently different intensity distributions
Image
Histogram
Week 5
COMP9517 2021 T1
12
0
255
Threshold
Segmentation
Thresholding
• Problematic if regions have overlapping intensity distributions
Image
Histogram
Week 5
COMP9517 2021 T1
13
0
255
Threshold?
Segmentation
Thresholding
• Problematic if regions have overlapping intensity distributions
Image
Histogram
Week 5
COMP9517 2021 T1
14
0
255
Threshold?
Segmentation
Thresholding
• Problematic if regions have overlapping intensity distributions
Image
Histogram
Week 5
COMP9517 2021 T1
15
0
255
Threshold?
Segmentation
K-Means Clustering
• Could work if the number of clusters is known a priori
Original Image
Labeled Image
Week 5
COMP9517 2021 T1
16
K-Means Clustering
• Problematic if the number of clusters is not known a priori
Original Image
Labeled Image
Week 5
COMP9517 2021 T1
17
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.
Week 5 COMP9517 2021 T1 18
More Sophisticated Segmentation Methods
Week 5 COMP9517 2021 T1 19
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
Week 5 COMP9517 2021 T1 20
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) =
Week 5
COMP9517 2021 T1 21
0 else
How many connected components (separate objects) are there in this thresholded image?
Connected Components • Connectivity in two dimensions (2D)
4-connected 8-connected
• Connectivity in three dimensions (3D)
Week 5
COMP9517 2021 T1
22
6-connected 18-connected 26-connected
Connected Components
• Number of components depends on the chosen connectivity
Thresholded image 4-connected objects
8-connected objects
Week 5 COMP9517 2021 T1
23
Number of objects = 10
Number of objects = 1
Connected Components Algorithm
N4 N8
• Firstpass
– If an object pixel, check its neighbors (𝑁𝑁 or 𝑁𝑁 ) 48
– 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
– Check each pixel (top-left to bottom-right)
Week 5 COMP9517 2021 T1
24
Region Splitting
• Basic computational approach
– One of the oldest techniques in computer vision
– First compute the histogram for the whole image
– Then find a threshold 𝑡𝑡 that best𝑡𝑡separates the peaks in the histogram
histogram
Week 5 COMP9517 2021 T1 25
Region Splitting
• Basic computational approach
– Repeat until regions are either fairly uniform or below a certain size
– Optimise metrics of intra-region similarity and inter-region dissimilarity
????
Week 5 COMP9517 2021 T1 26
Region Splitting • Histogram based methods
– –
–
– –
Follow a measurement space clustering process
Assume homogeneous objects in the image appear as clusters in measurement space (the histogram in our example)
Histogram clustering can be accomplished by finding the valleys and declaring the intervals between them as the clusters
Segmentation = mapping the clusters back to the image domain Connected components of the cluster labels constitute the segments
Week 5
COMP9517 2021 T1 27
Region Splitting • Recursive version of 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
Week 5
COMP9517 2021 T1 28
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
Week 5 COMP9517 2021 T1 29
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
Week 5
COMP9517 2021 T1 30
D(R,R )= min ω(e)
ij
e∈(vi∈Ri ,vj∈Rj )
Merge any two adjacent regions whose dissimilarity is smaller than
the minimum of the internal differences of these two regions
Region Merging
Felzenszwalb & Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision 59(2): 167–181, 2004.
Week 5 COMP9517 2021 T1 31
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
Week 5 COMP9517 2021 T1 32
Region Growing
https://sbme-tutorials.github.io/2019/cv/notes/6_week6.html
Week 5 COMP9517 2021 T1 33
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
Week 5 COMP9517 2021 T1
34
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 with a priority level corresponding to the gray value of the pixel.
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
Week 5 COMP9517 2021 T1 35
Watershed Segmentation • Example segmentation results
Input image
Segmentation results
Watershed of input Watershed of smoothed input
https://imagej.net/Classic_Watershed
Week 5
COMP9517 2021 T1
36
Watershed Segmentation
• Invert the image or compute edges if needed to get minima
• Important notes regarding watershed based segmentation
Week 5
COMP9517 2021 T1 37
– – – – –
Imagesoftenhavemanylocalminima,leadingtoheavyoversegmentation Preprocessing(imagesmoothing)maybeneededtoreducefalseminima Postprocessing(basinmerging)maybeneededtoreducefragmentation Manydifferentimplementationsandpre/postprocessingcriteriaexist Itispossibletostartfromuser-definedmarkersinsteadoflocalminima
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.
Week 5 COMP9517 2021 T1 38
Maximally Stable Extremal Regions
Week 5 COMP9517 2021 T1 39
Maximally Stable Extremal Regions • Example MSER segmentation results
https://doi.org/10.1186/1687-6180-2012-83
Week 5 COMP9517 2021 T1 40
Mean Shifting
• How would you segment this image based on colour alone?
Week 5 COMP9517 2021 T1 41
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
Week 5
COMP9517 2021 T1 42
– – – –
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
Mean Shifting • Iterative mode searching
Week 5
COMP9517 2021 T1
43
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)=∑x∈N(x)K(xi −x)xi i
2 K(x)=exp( |x|−)
Kernel (weight function)
i ∑xi∈N(x) K(x −x)
Mean (center of gravity)
Mean Shifting
• Iterative re-estimation of the weighted mean
Mean shift vector 𝑚𝑚 𝑥𝑥 − 𝑥𝑥 Week 5
COMP9517 2021 T1 44
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
Week 5 COMP9517 2021 T1 45
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
Week 5
COMP9517 2021 T1 46
Mean Shifting
Week 5 COMP9517 2021 T1 47
Mean Shifting
• Replace segmented region colours by their cluster means
https://doi.org/10.1109/34.1000236
Week 5 COMP9517 2021 T1 48
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
Week 5
COMP9517 2021 T1 49
– – – –
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
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
Week 5 COMP9517 2021 T1 50
Superpixel Segmentation
• Simple linear iterative clustering (SLIC)
– A popular superpixel generation algorithm
– Preserves image 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/
Week 5 COMP9517 2021 T1 51
Superpixel Segmentation • Simple linear iterative clustering (SLIC)
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
d = (l −l )2 +(a −a )2 +(b −b )2 (distance in CIELAB color space) lab j i j i j i
dxy = (xj −xi)2 +(yj −yi)2
Week 5
d 2 d 2 D=lab xy+
m2 S2
(distance in pixel space)
(weight 𝑚𝑚 controls influence of color over spatial distance)
COMP9517 2021 T1 https://doi.org/10.1109/TPAMI.2012.120 52
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)
Week 5 COMP9517 2021 T1 53
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
Week 5
COMP9517 2021 T1
54
Conditional Random Field • Segmentation as an energy minimisation problem
Week 5
COMP9517 2021 T1 55
– Unary potentials 𝜑𝜑
ii
i ij
ij
E(s,c)=∑φ(s,c) ∑ψ(s,s+)
• Computes the cost of superpixel 𝑠𝑠 belonging to class 𝑐𝑐
• Data term (based on graph node values)
𝑖𝑖𝑖𝑖
• A lower cost means a higher likelihood of 𝑠𝑠𝑖𝑖 belonging to 𝑐𝑐𝑖𝑖
– 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)
• Can be obtained via superpixel classification
Conditional Random Field
• Energy minimization is solved via graph cut (max-flow min-cut)
https://doi.org/10.1109/TPAMI.2004.60
Week 5 COMP9517 2021 T1 https://doi.org/10.1109/TGRS.2016.2627638 56
Conditional Random Field
• Segmentation example with multiple source-sink terminals
https://doi.org/10.1109/rivf.2012.6169870
Week 5 COMP9517 2021 T1 57
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
Week 5 COMP9517 2021 T1 58
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
Week 5 COMP9517 2021 T1 59
Active Contour Segmentation • Enforces a solution where gradient information is lacking
OK…
Boundary?
16 x 16 pixels
Week 5 COMP9517 2021 T1
60
Um…
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]→n ⇒ C(s)=[x(s),y(s)] n=2
Define a suitable energy functional
Using internal + image + external energies
1
EC = E.g.
Eint(C(s)) +Eimg(C(s)) +Eext(C(s)) ds
∫
0
Bending Intensity or User energy gradient interaction
Week 5
COMP9517 2021 T1 61
Minimize the energy functional
Using efficient optimization algorithms
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
Week 5
COMP9517 2021 T1 62
– – – – –
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
Level Set Segmentation • Contour evolution over time (iterative) 𝑡𝑡
2D contour
3D level-set function
https://en.wikipedia.org/wiki/Level-set_method
Week 5 COMP9517 2021 T1
63
Level Set Segmentation • Examples of level-set based segmentation
Week 5 COMP9517 2021 T1 https://doi.org/10.1007/s11263-006-8711-1 64
•
Level Set Segmentation
A well-know implementation is the Chan-Vese model Minimize the energy functional
E(C) = μ ⋅length(C) +ν ⋅area(C) + λ ∫ |u −c |2 dxdy
+λ2 ∫|u0−c2|2dxdy Outside(C)
https://doi.org/10.1109/83.902291
101 Inside(C)
Week 5
COMP9517 2021 T1 65
How to Evaluate Segmentation Methods
Week 5 COMP9517 2021 T1 66
Segmentation Method Evaluation
https://grand-challenge.org/
Week 5 COMP9517 2021 T1 67
Evaluation Metrics
Segmented object pixels (set S ) True object pixels (set T )
Pixel classification
• TruePositivesTP=S T∩ Correctly segmented as object
cc
• True Negatives TN = S T∩
Correctly segmented as background
c
• False Positives FP = S T∩
Incorrectly segmented as object
• False Negatives FN = Sc T∩ Incorrectly segmented as background
TN
FP
TP
FN
Week 5
COMP9517 2021 T1
68
Evaluation Metrics
• Sensitivity(=true-positiverate)
Fraction of the true object that is correctly segmented
TP
FN
TP TP + FN
TPR =
• Specificity(=true-negativerate)
TN FP
Fraction of the true background that is correctly segmented
TNR = COMP9517 2021 T1
TN TN + FP
Week 5
69
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
Image Truth
Compute the sensitivity versus the specificity for all possible intensity thresholds 𝜏𝜏 and plot the results
Week 5
τ = 32
τ = 0
τ = 64
τ = 256
1 – Specificity
COMP9517 2021 T1
70
Sensitivity
Evaluation Metrics
• Comparing the performance of methods by ROC analysis
1 – Specificity
Area under the curve (AUC)
Worst = 0.0
0.1
0.2
0.3
0.4
Random = 0.5
0.6
0.7
0.8
0.9
Best = 1.0
Higher AUC = better method
Week 5
COMP9517 2021 T1
71
Sensitivity
Evaluation Metrics
• Precision (= positive predictive value) Fraction of the segmented object
FP
TP
that is correctly segmented
TP TP + FP
P=
• Recall(=sensitivity)
• F-measure Harmonic mean of
precision and recall
F = 2
TP
FN
Fraction of the true object that is correctly segmented
R⋅P ⋅
TP TP + FN
R+P
Week 5
R=
COMP9517 2021 T1
72
Evaluation Metrics
• Jaccardsimilaritycoefficient(JSC)
Fraction of the union of the segmented object and the
true object that is correctly segmented
FP
FN
TP
S ∩T TP JSC= += +
S∪T FP TP FN • Dicesimilaritycoefficient(DSC)
FP
FN
TP
Fraction of the segmented object set joined with the true object set that is correctly segmented
S ∩T 2 TP DSC=2 + + = +
Week 5
S T FP 2TP FN COMP9517 2021 T1 73
Week 5
COMP9517 2021 T1 74
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