CSE 4227 · Chapter 10 · Deck 09

Segmentation II: region growing, split & merge, thresholding

Region growing with a pixel-by-pixel simulator, split and merge worked on the slide example, global/local/adaptive thresholding with the iterative method, and the case-study questions answered. Fall 2024 is left out.

★ Must study on this page

Region-based segmentation: the idea

slides 3–8Know in 2 lines
In plain wordsDeck 08 found borders (where brightness jumps). This deck finds insides: groups of touching pixels that look alike. A region is just "a blob of connected pixels with similar values".

Slide 3. Segmentation is based on one of two properties of intensity: similarity (partition into regions similar by predefined criteria) and discontinuity (detect region boundaries from local changes in intensity).

Slide 4. In region-based segmentation we identify the regions occupied by objects by grouping pixels that are similar in some region property. A region is a group of connected pixels with similar properties.

20000001010
20000001010
2001431431431431010
2001432002001431010
2001432002001431010
2001431431431431010
20000001010
20000001010
slides 5–7: 8×8 crop. Edge-based looks for the jumps 20|0, 0|143, 143|200; region-based groups 20s, 0s, 143s, 200s, 10s

Slide 8. Two basic region-based techniques: (i) region growing and (ii) region splitting and merging.

Region growing

Must studyslides 9–17Came in past papers
In plain wordsDrop a seed on one pixel inside the object. Look at its neighbours: any neighbour whose value is close enough (difference ≤ T) joins the region. Then look at the new members' neighbours, and so on, like a stain spreading, until nothing new can join.

Slide 9. Region growing groups pixels or subregions into larger regions. The simplest form is pixel aggregation: start with a set of seed points and grow regions by appending to each seed the neighbouring pixels that have similar properties (gray level, texture, colour, shape). It works better than edge-based methods on noisy images, where edges are hard to find.

Slide 10. Bottom-up approach: (1) find starting points; (2) include neighbouring pixels with a similar feature; (3) continue until every pixel is associated with a starting point. Problems: good starting points are not trivial to find, the process is hard to automate, and it needs a good similarity criterion.

Slides 11–13. Start with one pixel of a potential region and add adjacent pixels until the pixels compared are too dissimilar; the first pixel can be the first unlabelled pixel or a chosen set of seeds; usually a statistical test decides who joins. Formally, with input f(x,y), seed array S(x,y) (1 = seed) and predicate Q:

  1. Find all connected components in S and erode each to one pixel.
  2. Form fQ(x,y) = 1 where f satisfies the predicate Q.
  3. Form g(x,y) = 1 for every pixel of fQ that is 8-connected to a seed.
  4. Label each connected component of g with a different label.

It needs a stopping rule: stop when no more pixels satisfy the predicate.

Slides 14–17 · worked exampleworked

The seed is the centre of the image. (a) Grow the region in horizontal and vertical directions (4-connectivity) when the difference between two pixel values is ≤ 5. (b) What if the region is grown in horizontal, vertical and diagonal directions (8-connectivity)?

10101010101010
10101069701010
59106064595660
10591060701062
10605965671065
10101010101010
10101010101010
input; seed (3,3) = 60 outlined

(a) 4-connectivity. Pixels that join, in the order they are added (each compared with the pixel it grows from):

grows fromneighbourtest
(3,3) = 60(2,3) = 64|64 − 60| = 4 ≤ 5
(3,3) = 60(4,3) = 65|65 − 60| = 5 ≤ 5
(2,3) = 64(1,3) = 69|69 − 64| = 5 ≤ 5
(2,3) = 64(2,2) = 60|60 − 64| = 4 ≤ 5
(2,3) = 64(2,4) = 59|59 − 64| = 5 ≤ 5
(4,3) = 65(4,4) = 67|67 − 65| = 2 ≤ 5
(1,3) = 69(1,4) = 70|70 − 69| = 1 ≤ 5
(2,4) = 59(2,5) = 56|56 − 59| = 3 ≤ 5
(4,4) = 67(3,4) = 70|70 − 67| = 3 ≤ 5
(2,5) = 56(2,6) = 60|60 − 56| = 4 ≤ 5
(2,6) = 60(3,6) = 62|62 − 60| = 2 ≤ 5
(3,6) = 62(4,6) = 65|65 − 62| = 3 ≤ 5
10101010101010
10101069701010
59106064595660
10591060701062
10605965671065
10101010101010
10101010101010
(a) region: 13 pixels

(b) 8-connectivity also reaches across corners, so the 59 at (3,1), the 60 and 59 at (4,1), (4,2) and the 59 at (2,0) join too:

10101010101010
10101069701010
59106064595660
10591060701062
10605965671065
10101010101010
10101010101010
(b) region: 17 pixels
Answer4-connectivity: 13 pixels; 8-connectivity: 17 pixels. The 10s never join (|10 − 60| = 50 > 5).

Try it, step by step: slides 14–17: watch every neighbour check. Switch “Grow in” to 8-connectivity for part (b).

TrapCompare each new pixel with the pixel it grows from (its neighbour), as the slide answer does. Comparing with the seed value instead can give a different region; the simulator lets you switch to see the difference. Say which one you use.
F22 Final B5(a) (another examiner's paper)5 marks part

7×7 image; region growing with the seed at the centre, 8-direction growth when |difference| ≤ 4.

15151515151515
15151568691515
64646367706815
15157065617166
15156973581515
15151515151515
15151515151515
input; seed (3,3) = 65
grows fromneighbourtest
(3,3) = 65(2,2) = 63|63 − 65| = 2 ≤ 4
(3,3) = 65(2,3) = 67|67 − 65| = 2 ≤ 4
(3,3) = 65(3,4) = 61|61 − 65| = 4 ≤ 4
(3,3) = 65(4,2) = 69|69 − 65| = 4 ≤ 4
(2,2) = 63(2,1) = 64|64 − 63| = 1 ≤ 4
(2,3) = 67(1,3) = 68|68 − 67| = 1 ≤ 4
(2,3) = 67(1,4) = 69|69 − 67| = 2 ≤ 4
(2,3) = 67(2,4) = 70|70 − 67| = 3 ≤ 4
(2,3) = 67(3,2) = 70|70 − 67| = 3 ≤ 4
(3,4) = 61(4,4) = 58|58 − 61| = 3 ≤ 4
(4,2) = 69(4,3) = 73|73 − 69| = 4 ≤ 4
(2,1) = 64(2,0) = 64|64 − 64| = 0 ≤ 4
(1,4) = 69(2,5) = 68|68 − 69| = 1 ≤ 4
(2,4) = 70(3,5) = 71|71 − 70| = 1 ≤ 4
(2,5) = 68(3,6) = 66|66 − 68| = 2 ≤ 4
15151515151515
15151568691515
64646367706815
15157065617166
15156973581515
15151515151515
15151515151515
region: 16 pixels

Values 64, 64, 63 on row 2 and 66 on row 3 never join: no chain of steps ≤ 4 reaches them. (The question also asks for split and merge with T ≤ 5; a 7×7 image cannot be cut into equal quadrants, so state that you pad it to 8×8 or split unevenly, then follow the method below.)

Try it, step by step: F22 B5(a): 8-direction growth with T = 4.

Region splitting and merging

slides 18–33On study list
In plain wordsTop-down instead of bottom-up. Start with the whole image as one region. If a region is not uniform enough, cut it into 4 quarters; keep cutting until every piece is uniform. Cutting can leave neighbouring pieces that really belong together, so finally glue adjacent pieces that are similar.

Slides 18–19. Splitting: start with the whole image as a single region R; select a predicate P (gray values, etc.); successively divide each region into smaller quadrants until P(Ri) = TRUE for every region. The result is a quadtree (R → R1, R2, R3, R4; R4 → R41…R44). Problem: adjacent regions could be the same. Solution: allow merging.

Slide 20. Merging is the opposite of splitting: merge adjacent regions Ri and Rj for which P(Ri ∪ Rj) = TRUE. Split/merge: stop when no further split or merge is possible.

Slides 21–33 example (8×8, T = 4)

Rules on the slides: split a region into quadrants if T < (max − min); merge adjacent regions if T > (maxi − minj) and T > (maxj − mini).

56667766
67675547
66443256
54542346
03233247
00002256
11010344
10102354
input 8×8

Splitting:

regionmax − mindecision
rows 0–7, cols 0–77 − 0 = 77 > 4: split into 4
rows 0–3, cols 0–37 − 4 = 33 ≤ 4: keep
rows 0–3, cols 4–77 − 2 = 55 > 4: split into 4
rows 0–1, cols 4–57 − 5 = 22 ≤ 4: keep
rows 0–1, cols 6–77 − 4 = 33 ≤ 4: keep
rows 2–3, cols 4–53 − 2 = 11 ≤ 4: keep
rows 2–3, cols 6–76 − 4 = 22 ≤ 4: keep
rows 4–7, cols 0–33 − 0 = 33 ≤ 4: keep
rows 4–7, cols 4–77 − 0 = 77 > 4: split into 4
rows 4–5, cols 4–53 − 2 = 11 ≤ 4: keep
rows 4–5, cols 6–77 − 4 = 33 ≤ 4: keep
rows 6–7, cols 4–53 − 0 = 33 ≤ 4: keep
rows 6–7, cols 6–75 − 4 = 11 ≤ 4: keep

The top-left and bottom-left quadrants stay whole; the top-right and bottom-right ones are cut into 2×2 blocks (slide 24). That gives 10 regions.

Merging (adjacent pairs, one at a time):

regions [min…max]cross differencesdecision
[4…7] + [5…7]7 − 5 = 2, 7 − 4 = 3both < 4: merge
[4…7] + [4…7]7 − 4 = 3, 7 − 4 = 3both < 4: merge
[4…7] + [4…6]7 − 4 = 3, 6 − 4 = 2both < 4: merge
[4…7] + [4…7]7 − 4 = 3, 7 − 4 = 3both < 4: merge
[4…7] + [4…5]7 − 4 = 3, 5 − 4 = 1both < 4: merge
[2…3] + [2…3]3 − 2 = 1, 3 − 2 = 1both < 4: merge
[2…3] + [0…3]3 − 0 = 3, 3 − 2 = 1both < 4: merge
[0…3] + [0…3]3 − 0 = 3, 3 − 0 = 3both < 4: merge
56667766
67675547
66443256
54542346
03233247
00002256
11010344
10102354
final: 2 regions. Highlighted = the dark region (values 0–3), as in red on slide 33
AnswerTwo regions remain: a dark one (0–3) and a bright one (4–7).

Thresholding: global, local, adaptive

Must studyslides 35–53Came in past papers
In plain wordsPick one number T. Brighter than T → object (1), otherwise background (0). If the lighting is even, one T for the whole image works (global). If one side is in shadow, use a different T for each neighbourhood (local / adaptive).
g(x,y) = 1 if f(x,y) > T (object point);   0 if f(x,y) ≤ T (background point)

Slides 35–38. Thresholding splits the image into two classes: foreground (objects) and background. Types:

typeT depends onslide 53 form
globala single constant for the whole imageT = T[f(x,y)]
local / regional (variable)properties p(x,y) of a neighbourhood of (x,y), e.g. its meanT = T[p(x,y), f(x,y)]
dynamic / adaptivethe spatial coordinates (x,y) themselvesT = T[x, y, p(x,y), f(x,y)]

Slides 39–41. Global thresholding: one constant threshold for every pixel. It can be fixed or found automatically from the intensity histogram: with a bimodal histogram (object peak + background peak), the optimal T sits in the valley between the peaks.

Iterative (automatic) global threshold, slide 42

  1. Select an initial estimate for T (e.g. the mean).
  2. Segment with T: G1 = pixels > T, G2 = pixels ≤ T.
  3. Compute the means μ1 and μ2 of G1 and G2.
  4. New T = ½(μ1 + μ2).
  5. Repeat 2–4 until the change in T is smaller than ΔT.
  6. Finally g(x,y) = 1 if f(x,y) > T, else 0.
Practice · iterative thresholdworked

Pixel values: 10, 12, 15, 11, 200, 190, 205, 14, 198, 13, 201, 16. Find the threshold (ΔT = 0.5).

TG1 (> T)μ1G2 (≤ T)μ2new TΔT
90.417{200, 190, 205, 198, 201}198.800{10, 12, 15, 11, 14, 13, 16}13.000105.90015.483
105.900{200, 190, 205, 198, 201}198.800{10, 12, 15, 11, 14, 13, 16}13.000105.9000.000
AnswerT ≈ 105.90: the 5 bright values are object (1), the 7 dark values are background (0).

Try it, step by step: the iterative threshold, one round at a time. Try another start T: it lands on the same answer.

Slides 43–45 (glance). Multilevel thresholding for more than two classes: g = a if f > T2, b if T1 < f ≤ T2, c if f ≤ T1; such problems are often better solved with region growing.

Slides 47–48. Basic adaptive thresholding: subdivide the image into small areas and use a different threshold for each subimage; the threshold for a pixel depends on which subimage it lies in (fig 10.30: a shaded image fails with one global T but works per subimage).

Slide 49. Why/when local thresholding: global thresholding works only with uniform illumination; it fails with shadows, gradients or noisy backgrounds (a document with a shadow; a medical scan with uneven contrast). Local thresholding varies across neighbourhoods: T(x,y) = f(local mean, local variance, contrast); each pixel is compared with the statistics of its own neighbourhood.

Slides 50–52. Global threshold τ = f({i ∈ I}); local τa = f({i ∈ Na}) for pixel a with neighbourhood Na. Common choices: T = mean, T = median, T = (max + min)/2 of the neighbourhood; Niblack: T = m + k·s (m = local mean, s = local standard deviation, k = Niblack constant). The neighbourhood size must be chosen.

SP23 Final Q1(b) · brain tumour pipeline2 + 2 + 3 + 2 marks

Brain tumour detection: acquisition → preprocessing → segmentation (ROI) → feature extraction… (i) Method to remove noise from the scans in preprocessing? (ii) Method to partition pixels depending on intensity values? (iii) Which transformation function highlights specific ranges of pixel values? (iv) Which segmentation method groups similar pixels?

(i) Spatial smoothing: a median filter for salt-and-pepper (impulse) noise, keeps edges sharp; a Gaussian / averaging filter for random noise (deck 06).

(ii) Thresholding: g(x,y) = 1 if f(x,y) > T else 0. T can be found automatically with the iterative global method, or locally (adaptive) if the scan's contrast is uneven.

(iii) Intensity-level (gray-level) slicing: make the range [A, B] bright and either darken or keep the other levels, so the tumour's intensity range stands out (deck 04).

(iv) Region growing (from a seed inside the tumour, add neighbours with |difference| ≤ T); split-and-merge also groups similar pixels.

SP25 Final Q3(a) · case study4 + 3 + 3 marks

A scanned document suffers from uneven illumination, faded ink and background noise. Enhance it for readability, then segment text lines and text for OCR. (i) Two enhancement techniques. (ii) Laplacian or Sobel for sharpening, and why? (iii) Which segmentation technique to separate text and text lines?

(i) Enhancement. 1. Noise removal with a median filter (3×3): removes the background specks (impulse noise) while keeping the edges of the strokes. 2. Contrast enhancement for the faded ink: contrast stretching or histogram equalization spreads the crowded gray levels, so faint strokes become darker against the paper (a power-law with γ > 1 also darkens light ink). Because the illumination is uneven, apply it locally (per region) or first remove the slowly varying background.

(ii) Laplacian. Sharpening needs to boost fine detail (thin strokes, character edges) in every direction: the Laplacian is an isotropic 2nd derivative and g = f − ∇²f (or f + ∇²f for the negative mask) sharpens all orientations. Sobel is a 1st-derivative edge detector that gives thick edges and responds per direction; it is used to find edges, not to sharpen. The Laplacian amplifies noise, so denoise first (step i).

(iii) Local (adaptive) thresholding. A single global T fails because one part of the page is darker (slide 49). Use T(x,y) from each pixel's neighbourhood, e.g. the local mean, (max + min)/2, or Niblack T = m + k·s, to turn text into 1 and paper into 0. Then group the text pixels: connected components (or region growing) give characters and words; rows of components with empty gaps between them give the text lines.

Traps and one-minute sheet

slides all
whatformula
thresholdg = 1 if f > T, else 0
iterative TTnew = ½(μG1 + μG2)
local Tmean, median, (max + min)/2 of the neighbourhood
NiblackT = m + k·s
global / local / adaptiveT[f] / T[p, f] / T[x, y, p, f]