Edges - Lines - Segmentation

Question 1

Gradient and phase + equations.

Answer 1

…

Question 2

Simple edge detector algorithm.

Answer 2

1. Low-pass filter for noise removal
2. Gradient calculation (all 3 directions)
3. Gradient thresholding

Question 3

Describe Canny’s edge detector.

Answer 3

1. Smoothing with a Gaussian filter
2. Gradient computation (magnitude and phase)
3. Quantize the gradient angles
4. Non-maxima suppression (reduce edge thickness)
5. Hysteresis thresholding (improves edge connection)

Question 4

Describe the Hough transform + equations.

Answer 4

Parameter spaces:

• ab-plane
• sinusoidal curve (vertical lines)

Accumulation cells:

• few cells
• many cells

Counter for each cell:
- an high counter means high number of pixels associated to a line in the image

Question 5

Definitions of the morphological operators.

Answer 5

Erosion and Dilation.

• Opening: erosion + dilation
• Closing: dilation + erosion

Question 6

Definition of image segmentation.

Answer 6

…

Question 7

Otsu’s method for image segmentation.

Answer 7

A global thresholding method based on the histogram.

Finds the optimal threshold:
– Maximizes inter-class variance
– Minimize intra-class variance

see the algortihm on OneNote

Question 8

Describe the Region Growing algorithm.

Answer 8

1. Initialization: threshold the image to select the bright areas
2. Erode each component until 1 point is left (seed points)
3. Specify a predicate to grow the seeds

Question 9

Describe the Watershed algorithm.

Answer 9

A grayscale image can be seen as a topographic surface.

Three types of points:
– Local minima
– Steps: points at which a drop of water would fall to a given minima
– Watershed lines: points at which a drop of water
could fall into two (or more) different minima

GOAL: find watershed lines

Question 10

Describe segmentation by clustering.

Answer 10

• We represent each pixel with a feature vector

- Distance function to compare vectors

Question 11

Describe the k-means for clustering segmentation.

Answer 11

• k clusters and their centers

- minimize the objective function

Question 12

Describe a similar method to the k-means.

Answer 12

1. Create a density function

2. Look for the modes of the density function

Question 13

How to create a density function?

Answer 13

• Starting point: set of samples
• Desired output: density function (PDF)
• Simple approach: kernel density estimation (AKA Parzen window technique)

Question 14

Define the kernel used for creating the density function and how to derive the density function.

Answer 14

…

Question 15

What is mean shift?

Answer 15

Tool for finding peaks in high-dimensional data distribution without computing the density function explicitly; estimate its gradient instead!

Mean shift is a steepest-ascend method.

Question 16

Describe how mean shift works.

Answer 16

1. Compute mean shift vector 𝒎(𝒙)
2. Move the kernel window by 𝒎(𝒙)
3. Stop when the gradient is close to 0
4. Prune the mode by perturbation (Saddle points)

Question 17

What is the Markov Random Field (MRF) model? + equation of the energy function.

Answer 17

Approach for segmentating an image seen as a per-pixel labelling task.

1. Define a set of labels
2. Define an energy function (similar to a cost function)
3. Assign a label to each pixel in order to minimize the energy

Question 18

MRF: describe the data term and smoothness terms.

Answer 18

Data term:
1. Select 𝑚 pixels in the image: one per label
2. Create m feature vectors 𝒙
3. Evaluate 𝐸data as the 𝐿2-norm from the actual
pixel and the reference of that class

Smoothness terms:

• Potts model: any discontinuity has a constant penalization
• Linear smoothness cost: penalization depends on the label distance

Question 19

Belief propagation + analytical formulation.

Answer 19

Belief propagation can be used for improving MRF.

Question 20

Define the active contour framework Snakes.

Answer 20

Framework for delineating an object outline from a possibly noisy 2D image.

A simple elastic snake is defined by a set of n points, the internal elastic energy term and the external edge-based energy term.

The goal is to moving points in order to minimize the total energy,