The two segmentation approaches, line masks, derivatives at edges, Sobel and Prewitt, LoG, and every Canny step with a pixel-by-pixel simulator. Past questions are solved the way you would write them; Fall 2024 is left out.
Slide 3. Image segmentation is part of image processing and of computer vision; it is the first step in image analysis:
Slide 4. Example: segmenting rice grains gives a binary image where each pixel gets a label: 0 = not a rice grain, 1 = rice grain.
Slide 5. What it does: divides the image into regions; separates objects from the background and gives them labels; partitions the image into meaningful regions for an application. It lets us count objects, measure geometry (area, perimeter) and study properties (intensity, texture) of each object.
Slide 6. Principal approaches, based on two basic properties of intensity values:
| property | idea | methods (slide 7) |
|---|---|---|
| similarity | partition the image into regions that are similar according to predefined criteria | thresholding (pixel intensities), region based (grouping similar pixels), match based (compare to a template) |
| discontinuity | partition the image at sharp changes in intensity, such as edges | edge based (edges that separate regions), watershed (regions of local intensity minima) |
Write down the types of image segmentation based on the two basic properties of intensity values. (F25 quiz: what are the two principal approaches to image segmentation?)
Segmentation algorithms use one of two properties of intensity:
1. Discontinuity: partition the image where intensity changes sharply, e.g. at edges. Methods: point, line and edge detection (gradient, LoG, Canny); watershed.
2. Similarity: partition the image into regions that are alike by a predefined rule. Methods: thresholding, region growing, region splitting and merging, template matching.
Slide 8. Three basic gray-level discontinuities: points, lines, edges. We look at how derivatives behave at them; the common way is to run a mask through the image.
Slides 9–10 (glance). Isolated points: use the Laplacian mask; R = Σ wkzk; mark g(x,y) = 1 if |R| ≥ T, else 0 (turbine-blade X-ray example).
Slide 11. Line detection: these masks extract lines one pixel thick running in a particular direction. The preferred direction is weighted with a larger coefficient (2):
| -1 | -1 | -1 |
| 2 | 2 | 2 |
| -1 | -1 | -1 |
| -1 | -1 | 2 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | -1 | 2 |
Check it on a one-pixel-thick horizontal line (all 10 on the middle row) and a +45° line, at the centre pixel:
| mask | horizontal line | +45° line |
|---|---|---|
| R1 horizontal | 60 | 0 |
| R2 +45° | 0 | 60 |
| R3 vertical | 0 | 0 |
| R4 −45° | 0 | 0 |
Try it, step by step: run each line mask over a horizontal and a +45° line. The mask along the line gives the biggest number.
Draw the four line detection masks: horizontal, +45°, vertical, −45°.
| -1 | -1 | -1 |
| 2 | 2 | 2 |
| -1 | -1 | -1 |
| -1 | -1 | 2 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| -1 | 2 | -1 |
| 2 | -1 | -1 |
| -1 | 2 | -1 |
| -1 | -1 | 2 |
The 2s mark the direction each mask looks for; every mask sums to 0.
Slides 13–14. Edges are pixels where the brightness function changes abruptly. Edge models:
Slide 15. The image strip (ramp, isolated point, thin line, flat segment, step) and its derivatives:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f(x) | 5 | 5 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | 6 | 0 | 0 | 0 | 0 | 1 | 3 | 1 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 7 |
| 1st | 0 | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 6 | -6 | 0 | 0 | 0 | 1 | 2 | -2 | -1 | 0 | 0 | 0 | 7 | 0 | 0 | 0 | |
| 2nd | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 6 | -12 | 6 | 0 | 0 | 1 | 1 | -4 | 1 | 1 | 0 | 0 | 7 | -7 | 0 | 0 |
Try it, step by step: both derivatives along the slide 15 strip, one position at a time.
Slides 16–17. Derivatives are used to find discontinuities: the 1st derivative tells where an edge is (its maximum is at the centre of the edge); the 2nd derivative shows the edge direction by its sign (dark-to-light or light-to-dark) and passes through zero (changes sign) at the centre of the edge.
Slide 18. Zero crossing: the point where a function's sign changes. Edge detection with the Laplacian marks the points where the result crosses zero as edge points. It finds edges in all directions but works poorly when there is noise.
Slide 19. Derivative-based edge detectors are extremely sensitive to noise: a little noise on a ramp makes the 1st derivative noisy and the 2nd derivative useless. So we smooth first.
Define the first-order and second-order discrete derivatives of a 1-D digital image function f(x). What relation can be obtained between first- and second-order derivatives for an edge that is a ramp of constant slope?
Example ramp 5 5 4 3 2 1 0 0: 1st derivative 0 −1 −1 −1 −1 −1 0; 2nd derivative −1 0 0 0 0 1.
Relation on a ramp: (1) the 1st derivative is nonzero (constant) along the entire ramp, so it gives a thick edge; (2) the 2nd derivative is nonzero only at the onset and end of the ramp, with opposite signs (a double edge), and zero along the ramp; (3) the line joining those two values crosses zero near the middle of the ramp: this zero crossing marks the edge centre, where the 1st derivative is largest. The sign of the 2nd derivative also tells whether the edge goes dark→light or light→dark.
Slide 20. Two categories: gradient based (look for the maximum and minimum of the 1st derivative) and Laplacian based (look for zero crossings of the 2nd derivative). Slide 21: gradient: Sobel, Roberts cross, Prewitt; Laplacian: Laplacian of Gaussian; hybrid (both): Canny.
Slide 22. Three main steps in edge detection: (1) filtering (smoothing) to remove noise; (2) differentiation to highlight where intensity changes; (3) detection (thresholding) to decide which changes are significant; (4) localisation: find the exact edge location.
Slides 23–24. The gradient points toward the maximum increase of intensity. The edge is the boundary between regions of different intensity, so by convention the edge direction is perpendicular to the gradient: edge direction = gradient direction − 90°.
| -1 | 0 | 1 |
| -1 | 0 | 1 |
| -1 | 0 | 1 |
| -1 | -1 | -1 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| -1 | 0 | 1 |
| -2 | 0 | 2 |
| -1 | 0 | 1 |
| -1 | -2 | -1 |
| 0 | 0 | 0 |
| 1 | 2 | 1 |
Slides 25–27. 3×3 convolution masks; the differences are calculated at the centre pixel. Sobel puts weight 2 on the centre row/column (a little smoothing). Pipeline: image → Gx and Gy masks → ∇f → threshold → edges.
Slide 29. Gradient methods: simple to implement and give edges and their direction, but are sensitive to noise and not accurate in locating edges. Slides 31–32: too much detail (e.g. brickwork) gives too many edges; smooth the image first.
3×3 image [3 7 6; 2 5 8; 3 4 7]. Find the Sobel gradient-magnitude image and the edge direction of the central pixel.
Gx = (z3 + 2z6 + z9) − (z1 + 2z4 + z7) = (6 + 16 + 7) − (3 + 4 + 3) = 19; Gy = (z7 + 2z8 + z9) − (z1 + 2z2 + z3) = (3 + 8 + 7) − (3 + 14 + 6) = -5.
|∇f| ≈ |19| + |-5| = 24 (exact √(19² + -5²) = 19.65).
Gradient angle α = tan⁻¹(-5/19) = -14.74°; edge direction = α − 90° = -104.74°.
Whole magnitude image with zero padding:
| 3 | 7 | 6 |
| 2 | 5 | 8 |
| 3 | 4 | 7 |
| 19 | 12 | -19 |
| 21 | 19 | -21 |
| 13 | 14 | -13 |
| 9 | 20 | 21 |
| -3 | -5 | -1 |
| -9 | -20 | -21 |
| 28 | 32 | 40 |
| 24 | 24 | 22 |
| 22 | 34 | 34 |
Try it, step by step: Sobel and Prewitt step by step on SP22 and on the SP25 bright point.
3×3 patch [10 10 10; 10 50 10; 10 10 10]. Apply the Sobel operator in the horizontal direction; gradient value at the centre pixel?
Gx = (10 + 2×10 + 10) − (10 + 2×10 + 10) = 0. The left and right columns are equal, and Sobel's centre weight is 0, so the bright point is not seen by the gradient (Gy = 0 too). The full working is also on the deck 07 page.
Slide 33. LoG steps: (1) smoothing with a Gaussian filter; (2) enhance edges with the Laplacian operator. We usually smooth with a Gaussian before the Laplacian.
Slide 34 (glance): LoG(x,y) = −1/(πσ⁴) [1 − (x² + y²)/(2σ²)] e−(x² + y²)/(2σ²); a 5×5 approximation is [0 0 −1 0 0; 0 −1 −2 −1 0; −1 −2 16 −2 −1; 0 −1 −2 −1 0; 0 0 −1 0 0].
Slide 36. LoG properties: computationally cheaper (the two filters combine into one); no information about edge direction; false and missing edges can remain; localisation is better than gradient operators.
Slide 37. Marr–Hildreth algorithm: Gaussian smoothing, Laplacian, zero crossings mark the edge location, linear interpolation for sub-pixel location: g(x,y) = ∇²[G(x,y) ★ f(x,y)].
What are the two principal approaches to image segmentation? Why is a Laplacian filter typically combined with Gaussian smoothing (LoG) before edge detection in noisy environments?
Two approaches: discontinuity (split where intensity changes abruptly: points, lines, edges) and similarity (group pixels that are alike: thresholding, region growing, split-and-merge).
Why Gaussian + Laplacian: the Laplacian is a 2nd derivative, which is extremely sensitive to noise: every noisy pixel gives a strong response and false zero crossings. Gaussian smoothing first suppresses the noise, so the Laplacian's zero crossings mark real edges. Because both are linear, they combine into one LoG mask (cheaper), and the zero crossings give well-localised edges.
Slide 39. Three criteria:
| criterion | meaning |
|---|---|
| good detection | find and mark all real edges (few missed, few false) |
| good localisation | minimal distance between the detected edge and the real edge |
| clear (single) response | only one response per edge |
Slide 40. Five steps:
Let d1…d4 be the four basic directions of a 3×3 region (horizontal, −45°, vertical, +45°). (1) Find the direction dk closest to α(x,y). (2) If M(x,y) is less than at least one of its two neighbours along dk, set gN(x,y) = 0 (suppress); otherwise gN(x,y) = M(x,y). Example (slide 47): α = 17° rounds to 0°, so compare pixel A with its left and right neighbours B and C; keep A only if it is larger.
| gradient value | class | fate |
|---|---|---|
| ≥ TH | strong (sure edge) | kept immediately |
| between TL and TH | weak (candidate) | kept only if 8-connected to a strong pixel; otherwise treated as noise |
| < TL | non-edge | discarded |
Slide 53. Threshold too low → false edges remain: false positives. Threshold too high → real edge points are removed: false negatives. Slide 56: a high threshold reduces false positives but increases false negatives; a low one does the opposite. Canny reduces both: non-maximum suppression removes extra (false-positive) pixels, and hysteresis keeps weak pixels that continue a real edge (fewer false negatives), filling gaps and giving thin, continuous contours.
Slide 57. A and B are above High: sure edges. D is below Low: sure non-edge. C and E are weak; C is connected to B so it is kept; E is not, so it is discarded (edges are assumed to be long lines).
gN is given (after step 3); TH = 100, TL = 45.
| 200 | 0 | 57 |
| 0 | 45 | 101 |
| 50 | 0 | 0 |
| 200 | 0 | 0 |
| 0 | 0 | 101 |
| 0 | 0 | 0 |
| 0 | 0 | 57 |
| 0 | 45 | 0 |
| 50 | 0 | 0 |
| 200 | 0 | 57 |
| 0 | 45 | 101 |
| 0 | 0 | 0 |
57 touches 101 and 45 touches 200 and 101: kept. 50's neighbours are 0, 45 (weak) and 0: no strong neighbour, so it is dropped.
Try it, step by step: slide 59: steps 4 and 5 only (gN given). Change the thresholds to see pixels move between strong, weak and gone.
Canny has 5 steps. The 3×3 result of the first two steps (magnitude, direction) is given. (i) Complete the remaining 3 steps with high threshold 100 and low threshold 45. (ii) Identify false positive / false negative edges. (iii) What happens with high = 245 and low = 10?
| 200 ↓ | 40 ↓ | 57 ↙ |
| 10 → | 20 ↑ | 101 ← |
| 50 ↑ | 41 ↑ | 74 ← |
Step 3 · non-maximum suppression: compare each pixel with its two neighbours along its arrow; keep it only if it is not smaller than them.
| pixel | M | arrow | neighbours along the arrow | result |
|---|---|---|---|---|
| (0,0) | 200 | ↓ | (1,0) = 10, (-1,0) outside | kept |
| (0,1) | 40 | ↓ | (1,1) = 20, (-1,1) outside | kept |
| (0,2) | 57 | ↙ | (1,1) = 20, (-1,3) outside | kept |
| (1,0) | 10 | → | (1,1) = 20, (1,-1) outside | suppressed → 0 |
| (1,1) | 20 | ↑ | (0,1) = 40, (2,1) = 41 | suppressed → 0 |
| (1,2) | 101 | ← | (1,1) = 20, (1,3) outside | kept |
| (2,0) | 50 | ↑ | (1,0) = 10, (3,0) outside | kept |
| (2,1) | 41 | ↑ | (1,1) = 20, (3,1) outside | kept |
| (2,2) | 74 | ← | (2,1) = 41, (2,3) outside | kept |
| 200 | 40 | 57 |
| 0 | 0 | 101 |
| 50 | 41 | 74 |
Step 4 · double threshold (TH = 100, TL = 45):
| 200 | 0 | 0 |
| 0 | 0 | 101 |
| 0 | 0 | 0 |
| 0 | 0 | 57 |
| 0 | 0 | 0 |
| 50 | 0 | 74 |
Step 5 · hysteresis:
| weak pixel | value | strong 8-neighbours | decision |
|---|---|---|---|
| (0,2) | 57 | 101 at (1,2) | kept |
| (2,0) | 50 | none | discarded |
| (2,2) | 74 | 101 at (1,2) | kept |
| 200 | 0 | 57 |
| 0 | 0 | 101 |
| 0 | 0 | 74 |
(ii) 74 at (2,2) is weak but survives because it touches the strong 101: if it was noise it is a false positive. 50 at (2,0) is weak with no strong neighbour and is dropped: if it was a real edge it is a false negative (40 and 41 are below TL and dropped too).
(iii) With TH = 245 nothing is strong, so hysteresis keeps no weak pixel: the output is empty (every real edge becomes a false negative). TL = 10 alone would let almost everything in as weak (false positives); 245:10 breaks the 2:1–3:1 rule.
Try it, step by step: F23 Q3(a): all three remaining steps, pixel by pixel. Set TH = 245, TL = 10 for part (iii).
A pixel has gradient magnitude 80 after non-maxima suppression; low = 50, high = 100. How is it classified?
50 ≤ 80 < 100, so it is a weak edge pixel. In hysteresis it is kept (becomes an edge) only if it is 8-connected to a strong pixel (≥ 100); otherwise it is discarded as noise.
How many steps are in Canny edge detection and what are they? Explain any one step (F21: explain non-maximum suppression). What are false positive and false negative edge pixels? How does Canny reduce these errors? (F21 also: what is image segmentation?)
Segmentation (F21): dividing an image into meaningful regions, e.g. objects and background, as the first step of image analysis.
Five steps: (1) Gaussian smoothing; (2) gradient magnitude and direction; (3) non-maximum suppression; (4) double thresholding; (5) edge tracking by hysteresis.
Non-maximum suppression: the gradient magnitude forms wide ridges around edges. For each pixel, round its gradient angle to 0°, 45°, 90° or 135° and compare its magnitude with the two neighbours along that direction; keep it only if it is the largest, otherwise set it to 0. This thins edges to one pixel.
False positive: a pixel marked as edge that is not a real edge (noise), caused by a threshold that is too low. False negative: a real edge pixel that is missed, caused by a threshold that is too high.
How Canny reduces them: NMS removes non-peak pixels (fewer false positives); double thresholding with hysteresis keeps weak pixels only when they connect to strong edges, so real but faint edge parts are kept (fewer false negatives) while isolated weak noise is dropped.
What is hysteresis thresholding in Canny? What are false positive and false negative edge pixels? How are they overcome?
Hysteresis thresholding: uses two thresholds. Pixels ≥ TH are strong (sure) edges; pixels < TL are discarded; pixels in between are weak and kept only if 8-connected to a strong edge. It links edge pieces and fills gaps.
False positive: non-edge (noise) marked as edge (threshold too low). False negative: real edge missed (threshold too high).
Overcome: NMS keeps only local maxima (fewer false positives); the low threshold plus the connectivity rule recovers faint parts of real edges (fewer false negatives) while isolated weak responses are removed.
(i) Apply Canny to extract edges from f(x,y) of size m × n; draw a schematic of the whole process to g(x,y). (ii) Explain non-maxima suppression gN(x,y) OR hysteresis thresholding gNH, gNL.
(ii) Hysteresis: gNH = gN ≥ TH, gNL = gN ≥ TL, then gNL = gNL − gNH. (a) locate the next unvisited edge pixel p in gNH; (b) mark as valid all weak pixels of gNL connected to p (8-connectivity); (c) repeat until all of gNH is visited; (d) set to 0 the pixels of gNL not marked; the output is gNH plus the marked gNL pixels. (Or explain NMS as in SP22 above.)
How many steps are in Canny and what are they? (F22: explain the three main criteria of Canny.)
5 steps: smoothing, finding gradients, non-maximum suppression, double thresholding, edge tracking by hysteresis.
Three criteria: good detection (mark all real edges), good localisation (detected edge as close as possible to the true edge), single (clear) response (one response per edge).
What is the primary goal of edge detection? Name two gradient-based operators. What is the role of non-maximum suppression in Canny? What is region growing?
Goal: to find the pixels where intensity changes sharply, i.e. object boundaries, so the image can be segmented and its structure kept with much less data.
Two gradient operators: Sobel and Prewitt (also Roberts).
NMS role: thins the thick gradient ridges to one-pixel-wide edges by keeping only the local maximum along the gradient direction; this improves localisation and removes false responses.
Region growing: start from seed pixel(s) and repeatedly add neighbouring pixels that are similar (e.g. |difference| ≤ T) until no more can be added (details on the deck 09 page).
The Fall 2025 deck stops before section 10.2.7, so the Hough transform is not in the slides. SP25 still asked a 4-mark part, so here is a short answer.
Find the line through (2,1), (3,2), (4,3). Are they collinear? Derive the polar representation of a line used in the Hough transform. Why is it preferred?
Slope (2,1)→(3,2) = (2 − 1)/(3 − 2) = 1; slope (3,2)→(4,3) = (3 − 2)/(4 − 3) = 1. Equal slopes through a common point, so the points are collinear: y = x − 1.
Polar form: describe a line by the perpendicular from the origin: its length ρ and its angle θ. Every point (x, y) on the line satisfies ρ = x cos θ + y sin θ. For y = x − 1 (x − y − 1 = 0) the unit normal is (1, −1)/√2, so θ = −45° and ρ = 1/√2 ≈ 0.707. Check (2,1): 2 cos(−45°) + 1 sin(−45°) = 0.707.
Why preferred: in y = ax + b the slope a goes to infinity for vertical lines, so the parameter space is unbounded. In (ρ, θ) both parameters are bounded: θ ∈ [−90°, 90°], ρ ∈ [−D, D] with D the image diagonal, so a finite accumulator array works for every line.
| what | formula |
|---|---|
| gradient | |∇f| = √(Gx² + Gy²) ≈ |Gx| + |Gy|, α = tan⁻¹(Gy/Gx) |
| 2nd derivative | f(x+1) + f(x−1) − 2f(x) |
| LoG / Marr–Hildreth | g = ∇²[G ★ f], edges at zero crossings |
| double threshold | gNH = gN ≥ TH; gNL = (gN ≥ TL) − gNH |