Edges and regions, the short way

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

Segmentation algorithms use one of two basic properties of intensity values:

There are only two ways to split a picture into objects. Say that first.

1. Discontinuity: partition the image where intensity changes sharply, i.e. at edges.

Look for places where brightness suddenly jumps (dark to bright). Those jumps are the borders of objects.

Methods: point, line and edge detection (gradient, LoG, Canny), watershed.

The tools that find those jumps: Sobel gradient, Canny and so on.

2. Similarity: partition the image into regions that are similar according to a predefined criterion.

Instead of borders, put pixels that look alike into the same group (e.g. all bright pixels = object).

Methods: thresholding, region growing, region splitting and merging.

The tools that make groups: one cut-off value (threshold), or spreading from a seed (region growing).

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

∂f/∂x = f(x+1) − f(x)

1st derivative = next pixel minus this pixel: how much the brightness changes in one step.

∂²f/∂x² = f(x+1) + f(x−1) − 2f(x)

2nd derivative = how much that change itself changes: right + left − 2 × middle.

Example ramp 5 5 4 3 2 1 0 0: 1st = 0 -1 -1 -1 -1 -1 0; 2nd = -1 0 0 0 0 1.

Brightness slides down 5 to 0 one step at a time (a ramp). Work out both rows with the formulas above; this example earns marks.

(1) The 1st derivative is non-zero along the entire ramp, giving a thick edge.

It is −1 at every step of the slope, so the whole slope lights up: the edge looks wide.

(2) The 2nd derivative is non-zero only at the start and end of the ramp, with opposite signs (a double edge), and zero along the ramp.

It only reacts where the slope begins (−1) and ends (+1): two thin lines, one negative and one positive.

(3) It crosses zero at the edge centre, where the 1st derivative is maximum. Its sign tells dark→light or light→dark.

Between the −1 and the +1 it passes through 0: that crossing point is the middle of the edge. Which sign comes first tells which way the brightness goes.

The 2nd derivative responds strongly to isolated points and is very sensitive to noise, so the image is smoothed first.

A single noisy dot gives a huge 2nd-derivative value, so we blur the image a bit before using it.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

(a) Two principal approaches, based on two basic properties of intensity values:

Same answer as section 1. Write both approaches with their methods; that's the 4 marks.

1. Discontinuity: partition the image where intensity changes abruptly, e.g. at edges. Methods: point, line and edge detection (gradient, Laplacian / LoG, Canny).

Find where brightness suddenly jumps; those jumps are the borders.

2. Similarity: partition the image into regions that are similar according to a predefined criterion. Methods: thresholding, region growing, region splitting and merging.

Group pixels that look alike.

(b) Why Gaussian before Laplacian: the Laplacian ∇²f is a second derivative, which is extremely sensitive to noise: every noisy pixel gives a strong response and false zero crossings (false edges).

The Laplacian reacts hugely to any single odd pixel, so noise shows up as fake edges.

Smoothing with a Gaussian G(x,y) = e^{−(x²+y²)/2σ²} first suppresses the noise, so the zero crossings of the Laplacian mark only real edges: g(x,y) = ∇²[G(x,y) ★ f(x,y)].

Blur first to kill the noise, then take the Laplacian. Now the zero crossings are real edges.

Both are linear, so they combine into one mask, the LoG ("Mexican hat"): ∇²[G ★ f] = [∇²G] ★ f. This is cheaper, and the zero crossings give well-localised edges. σ controls the scale: larger σ = more smoothing, only coarse edges.

You can pre-combine blur + Laplacian into a single mask and slide it once. Bigger σ = more blur = only the big edges remain.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

Three criteria:

Canny promises three things. Write all three.

(1) Good detection: mark all real edges, few missed, few false.

Find every real edge, and don't invent fake ones from noise.

(2) Good localisation: detected edge as close as possible to the true edge.

The line you draw sits exactly on the real border, not shifted to the side.

(3) Single response: only one response per edge.

One edge = one thin line, not three parallel lines.

Five steps:

Then list the 5 steps in order.

1. Smoothing: f_s = G ★ f, with Gaussian G(x,y) = e^{−(x²+y²)/2σ²}, to remove noise.

Blur the picture a little so tiny noise dots don't look like edges. ★ = slide the Gaussian mask over the image; σ = how strong the blur is.

2. Gradient with Sobel masks: M = √(g_x² + g_y²), α = tan⁻¹(g_y/g_x).

g_x = how fast brightness changes left to right, g_y = top to bottom (the two Sobel masks). M = edge strength (big M = strong edge). α = the direction in which brightness increases.

3. Non-maximum suppression: round α to 0°, 45°, 90° or 135°; keep a pixel only if its M is not smaller than both neighbours along that direction, else set it to 0.

After step 2 an edge is several pixels thick, like a hill. Walk across the hill (direction α) and keep only the top; set the slopes to 0. Now every edge is 1 pixel thin.

4. Double threshold T_H : T_L = 2:1 or 3:1. M ≥ T_H → strong; T_L ≤ M < T_H → weak; M < T_L → discarded.

Two cut-off values. Above the high one = sure edge. Below the low one = sure NOT an edge. In between = "maybe". The high one is 2 to 3 times the low one.

5. Hysteresis: keep a weak pixel only if it is 8-connected to a strong pixel.

A "maybe" pixel survives only if it touches a "sure" pixel (in any of the 8 directions). Real edges are long lines, so a maybe next to a sure is part of it; a lonely maybe is just noise.

Why two thresholds: one high T loses real edges (false negatives); one low T keeps noise (false positives). Hysteresis keeps the weak pixels that continue a real edge, giving thin, continuous edges.

Only a high cut-off: faint parts of real edges disappear and leave gaps. Only a low cut-off: noise becomes edges. Two cut-offs + the touch rule keep faint parts that connect to strong ones and throw away lonely noise.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

(ii) 74 at (2,2) is weak but kept because it touches the strong 101. If it was really noise, it is a false positive. 50 at (2,0) is weak with no strong neighbour, so it is dropped. If it was a real edge, it is a false negative.

Name one pixel that might be a fake edge that got in, and one that might be a real edge that got thrown out.

(iii) With T_H = 245 no pixel is strong, so hysteresis keeps nothing: the output is empty, every real edge is lost (false negatives). T_L = 10 would let almost every pixel in as weak (false positives). The ratio 245:10 breaks the usual 2:1 to 3:1 rule.

Too high a top cut-off: nothing is "sure", so nothing survives. Too low a bottom cut-off: everything becomes a "maybe".

SP25: 50 ≤ 80 < 100, so the pixel is a weak edge. It becomes an edge only if it is 8-connected to a strong pixel; otherwise it is discarded.

80 is between the two cut-offs, so it is a "maybe".

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

False positive: a pixel marked as an edge that is not a real edge (e.g. noise). Caused by a threshold that is too low.

Fake edge drawn.

False negative: a real edge pixel that is missed. Caused by a threshold that is too high.

Real edge lost.

How Canny reduces them: Gaussian smoothing removes noise before the gradient (fewer false positives). NMS keeps only the local maxima, so thick edges become thin (fewer false positives).

Blur kills noise; NMS deletes the extra pixels around each edge.

Double threshold + hysteresis keeps a weak pixel only when it is connected to a strong edge: faint parts of real edges are kept (fewer false negatives) and isolated weak noise is dropped (fewer false positives).

The touch rule rescues faint real edges and throws away lonely noise.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

Draw the four masks above and label each.

The 2s show the line's direction.

The coefficients sum to 0, so a constant area gives 0; a line in the mask's direction gives the largest response.

Flat area: no answer. Line along the 2s: big answer.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

(i) Draw the boxes above in a row with arrows, and write each box's formula under it.

The schematic is the 5 steps as boxes; the formulas earn the marks.

(ii) Hysteresis: g_NH(x,y) = g_N(x,y) ≥ T_H; g_NL(x,y) = g_N(x,y) ≥ T_L; then g_NL = g_NL − g_NH.

Make a "strong" image and a "weak" image. Remove the strong pixels from the weak image so each pixel is in only one.

(a) Locate the next unvisited edge pixel p in g_NH. (b) Mark as valid all weak pixels in g_NL connected to p (8-connectivity). (c) Repeat until all pixels of g_NH are visited. (d) Set to 0 all unmarked pixels of g_NL.

Start at each strong pixel and follow touching weak pixels; every weak pixel you can reach stays, the rest are deleted.

Output = g_NH + the marked pixels of g_NL.

Final edges = strong ones + rescued weak ones.

Or NMS: round α to 0°, 45°, 90° or 135°; if M(x,y) is less than at least one of its two neighbours along that direction, g_N(x,y) = 0, otherwise g_N(x,y) = M(x,y).

Keep only the top of each edge "hill".

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

g(x,y) = 1 if f(x,y) > T (object point); 0 if f(x,y) ≤ T (background point).

Every pixel brighter than T becomes white (object); everything else becomes black (background).

Global: one T for the whole image, T = T[f(x,y)].

One cut-off number for the entire picture.

Local / regional: T = T[p(x,y), f(x,y)], p = a neighbourhood property such as its mean.

Each small area picks its own cut-off from its own pixels (e.g. its average brightness).

Adaptive (dynamic): T = T[x, y, p(x,y), f(x,y)].

The cut-off also changes with the position in the picture, so it can follow a shadow.

Iterative global threshold: (1) initial T = mean intensity;

Start with a guess: the average brightness.

(2) split: G₁ = pixels > T, G₂ = pixels ≤ T; (3) means μ₁, μ₂;

Split the pixels into a bright group and a dark group, and average each group.

(4) new T = ½(μ₁ + μ₂); (5) repeat until the change in T < ΔT.

The new cut-off is halfway between the two averages. Repeat until it stops moving.

Normal line = write it on the paper. Grey "means" line under it = what it means (do not write that).

Region growing groups pixels into larger regions, starting from seed points and appending neighbouring pixels with similar properties (gray level, texture, colour).

Start from one pixel you know is inside the object, and keep adding neighbours that look like it.

(1) Choose the seed(s).

Pick the starting pixel (the question usually gives it).

(2) A 4- or 8-neighbour joins if it satisfies the predicate, e.g. |f(neighbour) − f(pixel it grows from)| ≤ T.

Check the neighbours (4 = up/down/left/right, 8 = also the diagonals). A neighbour joins if its value is within T of the pixel next to it.

(3) Repeat with the new members.

Every new member checks its own neighbours, so the region spreads like a stain.

(4) Stop when no more pixels satisfy the predicate.

When no neighbour is close enough any more, you are done.

Works better than edge-based methods on noisy images. Problems: good seeds are hard to choose, hard to automate, needs a good similarity rule.

One plus point and three problems: easy marks.

With numbers: table "grows from | neighbour | test", e.g. (3,3)=60 → (2,3)=64: |64 − 60| = 4 ≤ 5 ✓; then the final grid and the pixel count.

Show every joining pixel as one row of the table, then draw the final region. 8-connectivity always gives an equal or bigger region than 4.