3/23/21
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
SEGMENTATION QUESTIONS REGARDING ANYTHING?
Slides:
James Hays Isabelle Guyon, Erik Sudderth, Mark Johnson, Derek Hoiem
‘-
1
3/23/21
Image Segmentation
• Segmentation attempts to partition the pixels of an image into groups that strongly correlate with the objects in an image
• Typically the first step in any automated computer vision
‘-
application
3
Why Segmentation?
• Useful mid-level representation of an image – can facilitate better
further tasks
• Partitioning image into regions should be homogeneous with respect to some characteristic (gray level, texture, color, motion)
‘-
• The type of desired segmentation depends on the task
• Broad theory is absent at present
• Variety of approaches/algorithms
• Applications finding people, summarizing video, annotation figures, background subtraction, finding buildings/rivers in satellite images
4
2
3/23/21
Quiz
• Based on what you already know about image processing and computer vision, how would you do segmentation?
• Did you come up with • Hough Transform?
‘-
‐ Let’s assume you don’t know what objects are in the image • Edge Detection?
• Texture Grouping?
• What if the elements are characters? • Thresholding?
5
Segmentation algorithms generally are based on one of two basis properties of intensity values
• Discontinuity: to partition an image based on abrupt changes in intensity (such as edges) ‘-
• Similarity: to partition an image into regions that are similar according to a set of predefined criteria
6
3
3/23/21
Boundaries or Regions are equally as good
‘-
7
‘-
8
4
3/23/21
Segmentation and Grouping
• Grouping (or clustering)
• collect together tokens that
“belong together”
• Fitting
• associate a model with tokens • issues
• which model?
• which token goes to which
element?
• how many elements in the model?
‘-
9
Grouping in humans
• Figure-ground discrimination
• grouping can be seen in terms of allocating some
elements to a figure, some to ground
• impoverished theory
• Gestalt properties
• elements in a collection of
elements can have properties
that result from relationships
(Muller-Lyer effect)
‘-
‐ Gestalt-qualitat
• A series of factors affect
whether elements should be grouped together
‐ Gestalt factors
5
3/23/21
‘-
‘-
6
3/23/21
Occlusion cues are important
‘-
13
Aren’t they?
‘-
14
7
3/23/21
Regions and Edges
• Ideally, regions are bounded by closed contours
• We could “fill” closed contours to obtain regions • We could “trace” regions to obtain edges
• Unfortunately, these procedures rarely produce satisfactory results. ‘-
15
Regions and Edges
• Edges are found based on DIFFERENCES between
values of adjacent pixels.
• Regions are found based on SIMILARITIES between
‘-
values of adjacent pixels.
• Goal associate some higher level – more meaningful units with the regions of the image
16
8
3/23/21
Machine Learning
‘-
Dimensionality Reduction
• PCA, ICA, LLE, Isomap, Autoencoder
• PCA is the most important technique to know. It takes advantage of correlations in data dimensions to produce the best possible lower dimensional representation based on linear projections (minimizes reconstruction error).
• PCA should be used for dimensionality reduction, not for discovering patterns or making predictions. Don’t try to assign semantic meaning to the bases.
‘-
18
9
3/23/21
Machine Learning
‘-
19
‘-
20
10
3/23/21
Redrawing Borders
• Suppose we want to draw the states so all regions have
equal population? • Methods?
‘-
21
Move borders to add/remove cities?
‘-
3) Redraw borders 2) “Move” close cities to add/remove population 4) Repeat
1) Label Cities with Population
22
11
3/23/21
Move borders to add/remove cities?
‘-
3) Redraw borders 2) “Move” close cities to add/remove population 4) Repeat
1) Label Cities with Population
23
‘-
• http://fakeisthenewreal.org/reform/
24
12
3/23/21
Why do we cluster?
• Summarizing data
– Look at large amounts of data
– Patch-based compression or denoising
– Represent a large continuous vector with the cluster number
‘-
• Prediction
– Images in the same cluster may have the same labels
• Counting
– Histograms of texture, color, SIFT vectors
• Segmentation
– Separate the image into different regions
Slide: Derek Hoiem
25
What features we can cluster on? • For State Boundaries?
• Population
• For Images?
‘-
• If we were to “segment” an image, what would YOU use?
• Color?
• Texture? • Edges?
26
13
3/23/21
Clustering example: image segmentation
Goal: Break up the image into meaningful or perceptually similar regions
‘-
27
Segmentation for feature support or efficiency
50×50 Patch
Slide: Derek Hoiem
50×50 Patch
‘-
[Felzenszwalb and Huttenlocher 2004]
28
14
3/23/21
Foreground/Background
‘-
Rother et al. 2004
29
Types of segmentations
‘-
Oversegmentation Undersegmentation
Multiple Segmentations
30
15
3/23/21
Major processes for segmentation • Bottom-up: group tokens with similar features
• Top-down: group tokens that likely belong to the same object
‘-
[Levin and Weiss 2006]
31
Clustering: group together similar points and represent them with a single token
‘-
2) How do we compute an overall grouping from pairwise similarities?
Slide: Derek Hoiem
Key Challenges:
1) What makes two points/images/patches similar?
32
16
3/23/21
How do we cluster? • K-means
– Iteratively re-assign points to the nearest cluster center
• Single-link clustering
– Start with each point as its own cluster and iteratively merge the
closest clusters
• Mean-shift clustering
– Estimate modes of pdf • Spectral clustering
– Split the nodes in a graph based on assigned links with similarity weights
33
‘-
Clustering for Summarization
• Let’s represent a cluster by its “center” (in feature space)
and the list of data points it contains
• Goal: cluster to minimize variance in data given clusters
• Preserve information
‘-
Cluster Center Data
Slide: Derek Hoiem
**12
c ,δ argmin c,δ
N
ji
ij
NK
c x
ij
Whether xj is assigned to ci
34
17
3/23/21
K-means algorithm
1. Randomly select K centers
2. Assign each point to nearest center
3. Compute new center (mean) for each cluster
Illustration: http://en.wikipedia.org/wiki/K-means_clustering
‘-
35
K-means algorithm
1. Randomly select K centers
2. Assign each point to nearest center
3. Compute new center (mean) for each cluster
Illustration: http://en.wikipedia.org/wiki/K-means_clustering
‘-
Back to 2
36
18
3/23/21
1. Initialize cluster centers: c0 ; t=0
2. Assign each point to the closest center
NK
t 1 t1
3. Update cluster centers as the mean of the points
δ argmin δ
2
c x
ij
‘-
c argmin c
ij
N
ji
ij
NK t1t2
c x
ij
4. Repeat 2-3 until no points are re-assigned (t=t+1)
Slide: Derek Hoiem
N
ji
37
K-means converges to a local minimum
‘-
38
19
3/23/21
K-means: design choices
• Initialization
• Randomly select K points as initial cluster center • Or greedily choose K points to minimize residual
• Distance measures
• Traditionally Euclidean, could be others
• Optimization
• Will converge to a local minimum
• May want to perform multiple restarts
‘-
39
K-means clustering w/ intensity or color
Image
Clusters on intensity Clusters on color
‘-
40
20
3/23/21
Based Only on Color • 11 different regions
‘-
41
w/ Color and Position
‘-
42
21
3/23/21
How to choose the number of clusters?
• Validation set
• Try different numbers of clusters and look at performance
‐ When building dictionaries (discussed later), more clusters typically work better
‘-
Slide: Derek Hoiem
43
How to evaluate clusters? • Generative
• How well are points reconstructed from the clusters?
• Discriminative
• How well do the clusters correspond to labels?
‐ Purity
‐ For each cluster, count the number of data points from the most common
class
‐ Take the sum over all clusters and
‐ Divide by the total number of data points.
• Note: unsupervised clustering does not aim to be discriminative
Slide: Derek Hoiem
‘-
44
22
K-Means pros and cons
• Pros
• Finds cluster centers that minimize
conditional variance (good representation of data)
• Simple and fast*
• Easy to implement
• Cons
• Need to choose K
• Sensitive to outliers
• Prone to local minima
• All clusters have the same parameters
(e.g., distance measure is non-
adaptive)
• *Can be slow: each iteration is O(KNd)
for N d-dimensional points • Usage
• Rarely used for pixel segmentation
‘-
Building Visual Dictionaries
1.
2.
3.
Sample patches from
a database
– E.g., 128 dimensional SIFT vectors
Cluster the patches
– Cluster centers are the dictionary
Assign a codeword (number) to each new patch, according to the nearest cluster
‘-
45
46
3/23/21
23
3/23/21
Examples of learned codewords
‘-
Most likely codewords for 4 learned “topics” EM with multinomial (problem 3) to get topics
http://www.robots.ox.ac.uk/~vgg/publications/papers/sivic05b.pdf Sivic et al. ICCV 2005
47
How do we cluster? • K-means
– Iteratively re-assign points to the nearest cluster center
• Single-link clustering
– Start with each point as its own cluster and iteratively merge the
closest clusters
• Mean-shift clustering
– Estimate modes of pdf • Spectral clustering
– Split the nodes in a graph based on assigned links with similarity weights
48
‘-
24
3/23/21
Single Link Clustering
‘-
49
‘-
50
25
3/23/21
‘-
51
‘-
52
26
3/23/21
‘-
53
Single Link Clustering
How to define cluster similarity?
– Average distance between points, maximum distance, minimum distance
– Distance between means or medoids How many clusters?
– Clustering creates a dendrogram (a tree)
– Threshold based on max number of clusters or based on distance between merges
‘-
54
27
distance
3/23/21
Summary: Single Link Clustering
Good
• Simple to implement, widespread application • Clusters have adaptive shapes
• Provides a hierarchy of clusters ‘-
Bad
• May have imbalanced clusters
• Still have to choose number of clusters or threshold
• Need to use an “ultrametric” to get a meaningful hierarchy
55
How do we cluster? • K-means
• Iteratively re-assign points to the nearest cluster center
• Single-link clustering
• Start with each point as its own cluster and iteratively merge the
closest clusters
• Mean-shift clustering – Estimate modes of pdf
• Spectral clustering
– Split the nodes in a graph based on assigned links with similarity weights
56
‘-
28
3/23/21
Mean shift segmentation
• Versatile technique for clustering-based segmentation
‘-
D. Comaniciu and P. Meer, Mean Shift: A Robust Approach toward Feature Space Analysis, PAMI 2002.
57
Mean shift algorithm
• Try to find modes of this non-parametric density
‘-
58
29
3/23/21
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
59
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
60
30
3/23/21
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
61
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
62
31
3/23/21
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
63
Mean shift
Slide by Y. Ukrainitz & B. Sarel
‘-
Region of interest
Center of mass
Mean Shift vector
64
32
3/23/21
Mean shift
Slide by Y. Ukrainitz & B. Sarel
Region of interest
Center of mass
‘-
65
Mean shift segmentation results
‘-
Comaniciu and Meer 2002
67
33
3/23/21
‘-
Comaniciu and Meer 2002
68
Mean-shift: other issues
• Speedups
• Binned estimation
• Fast search of neighbors
• Update each window in each iteration (faster convergence)
‘-
• Other tricks
• Use kNN to determine window sizes adaptively
• Lots of theoretical support
D. Comaniciu and P. Meer, Mean Shift: A Robust
Approach toward Feature Space Analysis, PAMI 2002.
69
34
3/23/21
Mean shift pros and cons
• Pros
• Good general-practice segmentation
• Flexible in number and shape of regions • Robust to outliers
• Cons
• Have to choose kernel size in advance
• Not suitable for high-dimensional features
• When to use it
• Oversegmentatoin
• Multiple segmentations
• Tracking, clustering, filtering applications
‘-
70
Which algorithm to use?
• Quantization/Summarization: K-means • Aims to preserve variance of original data
• Can easily assign new point to a cluster
Quantization for computing histograms
‘-
Summary of 20,000 photos of Rome using “greedy k-means”
http://grail.cs.washington.edu/projects/canonview/71
35
3/23/21
Which algorithm to use? • Image segmentation: Single Link
• More flexible with distance measures (e.g., can be based on boundary prediction)
• Adapts better to specific data
• Hierarchy can be useful ‘-
http://www.cs.berkeley.edu/~arbelaez/UCM.html
72
Things to remember
• K-means useful for summarization, building
dictionaries of patches, general clustering
‘-
• Spectral clustering useful for determining relevance, summarization, segmentation
• Agglomerative clustering useful for segmentation, general clustering
7
3
36
3/23/21
Motion Segmentation
Given a set of image points obtain:
• Number of independently moving objects
• Segmentation: object to which each point belongs • Motion: rotation and translation of each object
• Structure: depth of each point
‘-
74
Motion Segmentation Problem
‘-
Three frames from the MPEG “flower garden” sequence
• Given optical flow at each point
• partition/segment the flow field into regions belonging to
individual planes “layers”
Figure from “Representing Images with layers,”, by J. Wang and E.H. Adelson, IEEE Transactions on Image Processing, 1994, c 1994, IEEE
Some example slides from Forsythe and Ponce. Computer Vision, A modern approach.
37
3/23/21
‘-
Three frames from the MPEG “flower garden” sequence
Figure from “Representing Images with layers,”, by J. Wang and E.H. Adelson, IEEE Transactions on Image Processing, 1994, c 1994, IEEE
Grey level shows region no. with highest probability
‘-
Segments and motion fields associated with them
Figure from “Representing Images with layers,”, by J. Wang and E.H. Adelson, IEEE Transactions on Image Processing, 1994, c 1994, IEEE
38
3/23/21
Next time
• Classification and Recognition
‘-
39