Week 4 - Segmentation and Clustering p1,2

Question 1

What is the goal of Grouping

Answer 1

Gather features that belong together for efficiency of further processing
Obtain an intermediate representation that compactly describes key parts

Question 2

What is the Gestalt principle

Answer 2

That grouping is key to visual perception
Elements in a collection have properties that result from relationships
(negative space between features)

Question 3

What are the gestalt factors

Answer 3

not grouped ( line of identical dots, spaced evenly)
Proximity
Similarity
Common fate (Elements that move in the same direction belong together)
Common region
Symmetry
Closure
Continuity
Parallelism

Question 4

How do gestalt principles work with computer vision

Answer 4

It is difficult to know how best to apply these ideas via algorithms

Question 5

What is Top-down segmentation

Answer 5

pixels belong together because they are from the same object

Question 6

What is bottom-up segmentation

Answer 6

pixels belong together because they look ‘similar’
We define this similarity: colour, texture, gradient

Question 7

How do we measure segmentation success

Answer 7

It is very hard to measure the success of segmentation; it depends on the application

Compare to human segmentation or to “ground truth”
- But often there is no objective definition segmentation
- Not even agreement between humans

Question 8

What are superpixels

Answer 8

Compact and perceptually meaningful groups of pixels in an image
The idea is to not even try to compute a “correct” segmentation
Lets be content with over-segmentation (more superpixels less big regions)
- there will be the lines that follow the correct segmentation

Question 9

How do we segment via clustering

Answer 9

Using a pixel Intensity histogram
Often we will get curves (peaks) at different respective grey levels (objects)
We use clustering to determine the main intensities

Question 10

How do we use sum of squared differences in clustering

Answer 10

Σclusters i Σpoints p in cluster i ||p - ci||²

We want to minimise SSD between all points p and their nearest centre ci

Question 11

What is the chicken and egg problem in clustering

Answer 11

Know the cluster centre → can allocate correct points to groups
know the group memberships → can get the centres of each cluster

Question 12

What is k-means clustering

Answer 12

1) Pick random k cluster centres
2) determine group members using distance to centre
3) calculate average of each group and update ci

Will always converge to some local minimum but not necessarily the global minimum of SSD||p - ci||²

Question 13

What is Feature Space

Answer 13

A very important factor
Depending on what we chose, we will group pixels in different ways
For example,
Intensity similarity in 1D (grayscale)
Or 3D: (r,g,b)
Or 5D: (r,g,b,x,y)
This encodes both similarity and proximity

Question 14

What are the pros of K means

Answer 14

Simple, fast to compute
Converges to local minimum of within-cluster squared error

Question 15

What are the cons of k means

Answer 15

Have to chose a k
Sensitive to initial centres
Sensitive to outliers
Detects spherical clusters only

Question 16

What is a ‘hard assignment’

Answer 16

Assigning each data point to exactly one cluster/group
It is something we want to avoid

Question 17

What is a soft assignment

Answer 17

Data points can have multiple memberships “fuzzy clustering”
Eg Gaussian mixture model using probability

Question 18

What is the Gaussian Mixture model

Answer 18

Clusters are modelled as gaussians
not just by their mean (k-means)
Gives a generative probability model of x
Expectation-Maximisation (EM) algorithm assigns data to cluster with some soft probability

Question 19

What is the Univariate Gaussian (normal) distribution

Answer 19

Describes the likelihood of observing a continuous random variable along a single dimension
Takes two parameters: μ^ and σ^² > 0

Question 20

How do we calculate μ (MLE)

Answer 20

μ^ = 1/N Σ x^(i)

Question 21

How do we calculate σ² (MLE)

Answer 21

σ^² = 1/N Σ (x^(i) - μ^)²

Question 22

What is the Multivariate normal distribution

Answer 22

Describes the joint distribution of multiple random variables along multiple dimensions

Question 23

How do we calculate μ^ (multivariate)

Answer 23

μ^ = 1/m Σ x^(j)

Question 24

How do we calculate Σ^ (multivariate)

Answer 24

Σ^ = 1/m Σ (xj - μ^)^T(xj - μ^)

T = transpose
m = number of data points
xj = j-th data point (represented as a column vector)
essentially multiplies two difference vectors and gets the square covariance matrix

Question 25

What are the three forms of covariance

Answer 25

Spherical, diagonal, full

Question 26

What is Spherical covariance

Answer 26

[σ² 0
0 σ²]
All variables have the same variance σ²
All have equal importance
visually, a sphere

Question 27

What is diagonal variance

Answer 27

[σ1² 0
0 σ2²]
Each variable has its own variance
Unique variance but no dependencies between variables
Visually: a vertical or horizontal ellipse

Question 28

What is full variance

Answer 28

[σ11² σ12²
σ21² σ22²]
Each variable has its own variance and there can be covariances between different variables (dependent)

Question 29

What is covariance

Answer 29

A measure of how two random variables change together

Question 30

What is a generative model

Answer 30

Generates new data points via a probabilistic distribution
defined by a vector of parameters θ

Question 31

What is Mixture of Gaussians (MoG)

Answer 31

A generative model that represents the data as a weighted sum of multiple Gaussian distributions

Question 32

How does MoG work

Answer 32

1)Start with parameters describing each cluster:
- mean μ, variance σ and size π
- each cluster has the gaussian probability distribution
2)Each gaussian component has probability πc
For instance, if π1=0.6 , component 1 is selected 60% of the time
3)Then we generate a datapoint x using the mean and covaraicne of that gaussian component

Question 33

What is a blob

Answer 33

Component in an image that exhibits some common characteristicent
mean μb, covariance matrices Vb, dimension d
Each blob has a probability (weight) αb

Question 34

What is the likelihood of observing x in a MoG

Answer 34

A weighted mixture of gaussian blobs
P(x|θ) = KΣ αbP(x | θb)
Here x is our soft assignment

Question 35

EM for blob

Answer 35

Find blob with paramaters θ that maximise the likelihood function
P(data | θ) = Π P(x|θ)
θ = mean and covariance

Probability of observing the whole dataset given the parameters = weighted probability of seeing x given parameters

Question 36

What are the steps of EM

Answer 36

1) Expectation step
Use the current parameter guess θ
Compute probability that point x is in blob b

2) Maximisation step
Use the computed expected values
The parameters of each blob (mean and covariance) are updated based on E-step
Update the blobs to maximise the likelihood function

3)Repeat until convergence - parameters are no longer significantly changing

Question 37

How does EM compare to k-means

Answer 37

very similar but EM is using soft assignments

Question 38

What are the applications of EM

Answer 38

Clustering
Segmentation
Model estimation
Missing data problems
finding outliers

Question 39

What are the pros of MoG

Answer 39

Probabilistic interpretation
Soft assignments between data points and clusters
Generative model, can predict novel data points
Relatively compact storage (mean and shape)

Question 40

What are the cons of MoG

Answer 40

Local minima
Initialisation affects the result - good idea to start with k means
Need to know number of components - has been figured out in the ML field
Need to choose generative model
Numerical problems are often a nuisance

Question 41

Gestalt: whole or group

Answer 41

Whole is greater than sum of its parts
Relationships among parts can yield new properties/features

Question 42

What 2 parameters does the multivariate guassian distribution take

Answer 42

• A vector containing mean position, μ^
• A symmetrical “positive definite” covariance matrix Σ^