Image Segmentation

CSS Optional — Paper-II, Section-B · P-II.V.X · Syllabus: Image Segmentation. This page covers the similarity-based half (thresholding, region growing, split-and-merge, clustering, watershed). The discontinuity-based half (point, line, edge, boundary detection) is on Point, Line, Edge and Boundary Detection.

1. Definition

Segmentation partitions an image into regions that correspond to meaningful objects or parts. It is the bridge between low-level processing (image → image) and recognition (image → meaning) — "segmentation quality decides recognition quality".

Formal conditions — regions R1 … Rn of image R must satisfy:

1. R1 ∪ R2 ∪ … ∪ Rn = R (every pixel belongs to some region)
2. Each Ri is a connected set
3. Ri ∩ Rj = ∅ for i ≠ j (no overlap)
4. Q(Ri) = TRUE (every pixel in a region satisfies the similarity predicate Q)
5. Q(Ri ∪ Rj) = FALSE for adjacent regions (neighbouring regions are genuinely different)

2. Two Families of Approach

3. Thresholding

• Global: g(x,y) = 1 if f(x,y) is above T, else 0. Works when the histogram is bimodal (object and background peaks).
• Multiple thresholds: T1, T2 split the image into three classes (e.g. background, soft tissue, bone).
• Variable / adaptive (local): a different T for each block or neighbourhood (e.g. local mean − C). Needed under uneven illumination — standard for scanned documents and OCR.
• Why thresholding fails: noise and uneven lighting blur the valley between the two histogram peaks. Remedies: smooth first, use edge pixels only, or go adaptive.

Basic global (iterative) algorithm:

1. Choose an initial T (e.g. the mean intensity).
2. Split pixels into G1 (above T) and G2 (at or below T).
3. Compute means m1 and m2.
4. New T = (m1 + m2)/2.
5. Repeat 2–4 until T changes by less than a small ΔT.

Otsu's method (optimal global threshold): try every T and choose the one that maximizes the between-class variance σB² = ω0·ω1·(μ0 − μ1)² (equivalently minimizes within-class variance). Automatic, uses only the histogram; the default binarization in most OCR engines.

4. Region-Based Segmentation

Region growing:

1. Pick seed pixel(s) (manually or automatically, e.g. brightest points).
2. Add neighbouring pixels (4- or 8-connected) that satisfy the predicate, e.g. |f(p) − f(seed)| ≤ T.
3. Continue until no more pixels qualify.

• Pros: connected, clean regions; simple. Cons: depends on seed choice and T; can "leak" through weak boundaries.

Region splitting and merging (quadtree):

1. Split any region where Q is FALSE into four quadrants; repeat until every region satisfies Q.
2. Merge adjacent regions whose union satisfies Q.
3. Stop when no split or merge is possible.

• Needs no seed; the quadtree structure is natural for recursive splitting.

5. Other Methods

• Clustering (k-means): treat each pixel's intensity (or colour vector) as a data point; group into k clusters by nearest centre; update centres; repeat. Common for colour segmentation.
• Watershed: treat the gradient image as a topographic surface; "flood" it from minima; dams built where floods meet are the boundaries. Excellent for separating touching objects (cells, coins); prone to over-segmentation, controlled with markers.
• Motion-based: subtract consecutive frames to segment moving objects (CCTV).
• Deep learning: semantic segmentation (label every pixel with a class — U-Net, DeepLab), instance segmentation (separate each object — Mask R-CNN), promptable models (Segment Anything, 2023). Dominant today in medical imaging and autonomous driving.

6. Applications

Tumour and organ delineation in CT/MRI · lane and pedestrian segmentation in self-driving cars · crop and flood-extent mapping from SUPARCO satellite imagery · character isolation in OCR · defect detection on production lines · number-plate localization in Safe City cameras.

---

📐 Worked Numericals

N1 — Iterative global threshold: pixels {10, 20, 30, 40, 200, 210, 220, 90}.

1. T0 = mean = 820/8 = 102.5
2. G1 (above 102.5) = {200, 210, 220} → m1 = 210; G2 = {10, 20, 30, 40, 90} → m2 = 190/5 = 38
3. T1 = (210 + 38)/2 = 124
4. Re-split at 124 → same groups → converged, T = 124

N2 — Otsu's method on a 4-level histogram: counts n = [4, 2, 2, 8] for levels 0–3 (16 pixels) → p = [0.25, 0.125, 0.125, 0.5].

Maximum σB² at class 0 = {0, 1} → levels 0–1 = background, levels 2–3 = object.

N3 — Region growing: seed at row 2, col 3 (value 50); predicate |f − 50| ≤ 5; 4-connectivity.

10 12 50 52 55
11 13 51 53 54
12 14 49 50 56
60 62 48 51 53
61 63 65 50 52

• Accepted (45–55 and connected): row 0 → 50, 52, 55; row 1 → 51, 53, 54; row 2 → 49, 50; row 3 → 48, 51, 53; row 4 → 50, 52
• Rejected: 56 (outside range), 65, and the dark (10–14) and bright (60–63) groups
• Region size = 13 pixels

N4 — Split and merge, predicate Q: max − min ≤ 10.

20 22 80 82
21 23 81 83
20 21 82 80
80 81 81 83

1. Whole image: max − min = 63 → Q false → split into 4 quadrants.
2. Top-left {20, 22, 21, 23} ✓; top-right {80, 82, 81, 83} ✓; bottom-right {82, 80, 81, 83} ✓; bottom-left {20, 21, 80, 81} ✗ → split into single pixels.
3. Merge: top-left + the two 20/21 pixels → dark region; top-right + bottom-right + the two 80/81 pixels → bright region.
4. Final: 2 regions (dark: 6 pixels, bright: 10 pixels).

N5 — k-means (k = 2) on {12, 15, 18, 200, 205, 210}, initial centres 12 and 15.

1. Assign: {12} → c1; {15, 18, 200, 205, 210} → c2. Update: c1 = 12, c2 = 648/5 = 129.6
2. Re-assign: {12, 15, 18} → c1; {200, 205, 210} → c2. Update: c1 = 15, c2 = 205
3. Re-assign → no change → converged: dark cluster around 15, bright cluster around 205.

---

🎯 CSS Exam Angle

• "What is segmentation? Explain its techniques": definition + the 5 formal conditions (short list) → discontinuity vs similarity table → one worked method from each side (Sobel from the detection page, thresholding or region growing here) → applications.
• "Explain thresholding": global vs adaptive, the iterative algorithm, Otsu's criterion in one line, and a sketch of a bimodal histogram with T in the valley.
• A small region-growing grid (N3) makes a strong visual answer in under 10 lines.

📌 Past CSS Paper Frequency

⚠️ MCQ Traps

• Thresholding, region growing and split-and-merge are similarity-based; edge detection is discontinuity-based.
• Otsu maximizes between-class variance (= minimizes within-class variance).
• Global thresholding needs a bimodal histogram and even lighting; otherwise use adaptive thresholding.
• Region growing needs seeds; split-and-merge does not.
• Watershed's classic problem is over-segmentation, fixed with markers.
• Semantic segmentation labels classes; instance segmentation separates individual objects.

Self-Check

1. State the five conditions a valid segmentation must satisfy.
2. Why would a scanned page with a shadow need adaptive thresholding?
3. Compare region growing and split-and-merge in three points.

---

✅ Self-Check (with Answers)

Q1. What are the two basic approaches to segmentation?

Ans: Discontinuity-based — partition at abrupt intensity changes (point, line and edge detection, then edge linking). Similarity-based — group pixels that are alike by a criterion (thresholding, region growing, split-and-merge, clustering, watershed).

Q2. Why does global thresholding fail under uneven illumination, and what is the fix?

Ans: Shading changes the background level across the image, so no single T separates object from background everywhere (the histogram loses its clear valley). Fix: adaptive/local thresholding (a different T per region, e.g. local mean − C), or correct illumination first (e.g. top-hat).

Q3. Apply the iterative threshold algorithm to {20, 25, 30, 150, 160, 170}.

Ans: T0 = 555/6 = 92.5 → G1 = {20, 25, 30}, m1 = 25; G2 = {150, 160, 170}, m2 = 160 → T1 = (25 + 160)/2 = 92.5 → unchanged → T = 92.5.

Q4. What is the main weakness of watershed segmentation and its solution?

Ans: Over-segmentation — every noise-induced local minimum creates a separate basin. Solution: marker-controlled watershed (flood only from chosen markers) and/or smoothing the gradient image first.

Q5. State the core principle of compression-based segmentation.

Ans: Minimum Description Length: the best segmentation is the one that encodes the image in the fewest total bits (boundary bits + region texture bits). Adjacent regions are merged greedily while merging reduces the total coding length.

Q6. Semantic vs instance segmentation?

Ans: Semantic segmentation labels every pixel with a class (all cars = "car"); instance segmentation additionally separates individual objects (car 1, car 2). Examples: U-Net/DeepLab (semantic), Mask R-CNN (instance).