Week 4 - Segmentation and Clustering p3,4

Question 1

What is model- free clustering

Answer 1

“non-parametric clustering”
clustering techniques that do not assume a specific parametric form for the underlying data distribution

Question 2

What is mean-shift clustering

Answer 2

An advanced technique for clustering based segmentation
“model -free” does not make assumptions on data shape or number of clusters
Essentially smooths a distribution and finds its peaks

Question 3

What is a mode

Answer 3

Where the density reaches a peak (local maximum) - highest frequency
easy to see, hard to compute

Question 4

How does iterative mode search work

Answer 4

1. Initialise random seed (random number generation), and window W
2. Calculate centre of gravity (the “mean”) of W:
   
   1. Σ x H(x)
3. Shift the search window to the “mean”
4. Repeat Step 2 until convergence

Can use the derivative f’(x) of the kernel density estimate f(x) to find the direction we have to move it to find the local maximum

Question 5

Mean shift visualisation using dot clusters

Answer 5

1) choose random point (not necessarily dot) and region of interest around it
2) calculate centre of mass for this region
3) calculate mean shift vector pointing us towards this centre of mass
4) shift along vector and repeat

We repeat from every single point which is very laborious

Question 6

How do we make mean shift more efficient

Answer 6

Record the trajectories of all regions that move to the same mode (attraction basin)
We can then cluster all data points in the same attraction basin of a mode

Question 7

What is an attraction basin

Answer 7

attraction basin of an attractor is the region of the state space from which trajectories lead to that attractor

Question 8

Pros of mean shift clustering

Answer 8

model-free
A single parameter
potentially finds global maxima
finds multiple of modes
robust to outliers

Question 9

Cons of mean shift clustering

Answer 9

output heavily depends on window size
(large window-> fewer and large clusters, small window -> more and smaller clusters)
window size selection is not trivial
computationally expensive
does not scale well with dimension of feature space

Question 10

What is Graph theoretic segmentation

Answer 10

The approach in which an image is represented as a graph
- Node for every pixel
- Edge between every pair of pixels (p,q)
- Affinity weight (cost) for each edge wpq

Question 11

How does segmenting via graphs work

Answer 11

Delete links that cross between segments
Easiest to break links that have low similarity (low weight)
- Similar pixels should be in the same segments
- Dissimilar pixels should be in different segments

Question 12

How is a weighted graph represented by a square matrix

Answer 12

Row and column for each vertex
ij th element of a matrix = the weight of the edge from the vertex i to vertex j
The diagonal entries represent the edge from the node to itself (loop)

Question 13

What sort of matrix is used for an undirected graph

Answer 13

A symmetric matrix
Half the weight in each of the ijth and jith elements

Question 14

How can we measure affinity

Answer 14

denoted: aff(x,y)
- Distance
- Intensity I(x) - I(y)
- Colour

We place the similarity weight calculated on each edge of the graph

Question 15

What is affinity

Answer 15

similarity

Question 16

What is ideal for the weight between similar noes

Answer 16

Large

(different nodes = small)

Question 17

How does scale affect affinity

Answer 17

small σ: group only nearby points

large σ, broader gaussian: group far-away points

Question 18

What is a graph cut

Answer 18

The set of edges whose removal makes a graph disconnected

Question 19

What is the cost of a graph cut

Answer 19

Sum of weights of cut edges
Σwpq

Question 20

What is a minimum cut

Answer 20

The least costly cut
Not always the best cut
It is bias to cutting off the lesser weight (smaller, isolated sections)

Question 21

What is the best cut?

Answer 21

minimises the number of edges crossing between the partitions

Question 22

What is the normalise cut (NCut)

Answer 22

The goal is to penalise large segments (as minimum cuts favour small cuts -> large segments)

Question 23

What is the normalised cut equation

Answer 23

NCut(A,B) = cut(A,B)/ assoc(A,V) + cut(A,B) /assoc(B,V)

Question 24

What is Assoc(A,A)

Answer 24

Sum of all weights (association) within a cluster

Question 25

What is Assoc(A,V)

Answer 25

assoc(A,A) + cut(A,B) is the sum of all weights associated with nodes in A

Question 26

What assoc do big segments have

Answer 26

Large assoc(A,V)
Because it will have many edges with weights
Thus decreasing Ncut(A,B)

Question 27

How does NCut reduce bias to smaller cuts

Answer 27

Want smaller NCut
By reducing big segments NCut, we have more chance of choosing them over small

Question 28

What can be said about finding the globally optimal cut

Answer 28

NP-complete
a relaxed version can be solved using a generalised eigenvalue problem

Question 29

Pros of normalised cut

Answer 29

Generic framework, flexible to choice of affinity function
“model free”

Question 30

cons of normalised cut

Answer 30

Time and memory complexity can be high EG dense graphs → many affinity computations

Question 31

What is a GrabCut

Answer 31

Segmentation method that takes user input into account
User input = red box around the desired cut

Question 32

How do we evaluate segmentation

Answer 32

f1 score

Question 33

How do we calculate F1 Score

Answer 33

F = 2PR / (P+R)

Question 34

How does grabcut work

Answer 34

Immediately treats all pixels in the red box as foreground and then recursively improves

Iterates between 2 steps:

1. segmentation using graph cuts
   
   1. decides if a pixel is fore or background (binary)
   2. (requires having foreground model)
2. Once we have this segmentation
   
   1. Uses unsupervised clustering to learn two different models for foreground vs background
   2. sends this back to segmentation for improvement

Has very successful results

Question 35

How do we improve efficiency of segmentation

Answer 35

Superpixels
Group together similar looking pixels
cheap, local over-segmentation

Question 36

What do we need to ensure about chosen superpixels

Answer 36

• Do not cross boundaries
• have similar size
• have regular shape
• algorithm has low complexity

Question 37

What is precision P

Answer 37

percentage of marked boundary points that are real ones

Question 38

What is recall R

Answer 38

percentage of real boundary points that were marked