Segmentation and Clustering p3 - Lecture 10 - Week 4

Question 1

How is an image represented as a graph?

Answer 1

Fully-connected graph
- Node (vertex) for every pixel
- Link between every pair of pixels (p,q)
- Affinity weight (cost) wpq for each link (edge)
- wpq measures similarity
- similarity is inversely proportional to difference (in colour and position…)

Question 2

How does graph theoretic segmentation work?

Answer 2

graph cuts are made, easiest to break links that have low similarity (low weight)

After making cuts, similar pixels are in the same segments, dissimilar pixels are in different segments

Question 3

How can affinity (similarity) be assigned in graph based segmentation?

Answer 3

Distance (spatially)
Intensity
Colour

These functions take a sigma value to change scale

Question 4

What is a graph cut?

Answer 4

Set of edges whose removal makes a graph disconnected

A cut has a cost equal to the sum of the weights of the cut edges

Question 5

What techniques can be used to get a good cut for graph theoretic segmentation?

Answer 5

Minimum cut
- Efficient algorithms exist for finding them
Not the best because:
- Weight of cut proportional to number of edges in the cut
- Minimum cut tends to cut off very small, isolated components

Normalised Cut (NCut)
- Fix the fact that minimum cut penalises large segments by normalising for size of segments

Finding the globally optimal cut is NP-complete, but a relaxed version can be solved using a generalised eigenvalue problem.

Question 6

Pros and Cons of Normalised Cuts

Answer 6

Pros:
- Generic framework, flexible to choice of function that computes weight (“affinities”) between nodes
- Does not require any model of the data distribution

Cons:
- Time and memory complexity can be high
- Dense, highly connected graphs => many affinity computations
- Solving eigenvalue problem

Question 7

How does GrabCut work?

Answer 7

User draws a box and gets the subject they select (Basically like snapchat stickers)

1. Segmentation using graph cuts
   - Requires have foreground model
2. Foreground-background modelling using unsupervised clustering
   - Requires having segmentation

Question 8

How can segmentation efficiency be improved?

Answer 8

Problem: Images contain many pixels
- Even with efficient graph cuts

Use superpixels
- Group together similar-looking pixels for efficiency of further processing
- Cheap, local over-segmentation

Several approaches to super pixels but it’s important to ensure that they:
- Do not cross boundaries
- Have similar size
- Have regular shape
- Algorithm has low complexity

Question 9

How can we evaluate segmentation?

Answer 9

vs the ground truth, using precision and recall to get the metric F

Question 10

What is Precision P?

Answer 10

The percentage of the marked boundary points that are real ones

Question 11

What is Recall R?

Answer 11

The percentage of real boundary points that were marked

Question 12

What is F?

Answer 12

F = 2PR/(P+R)