Image Segmentation: Techniques, Thresholding, Clustering, Edge Detection & Applications

TAKEAWAYS:

• Image segmentation divides an image into disjoint regions based on homogeneity (intensity, texture, or color) or discontinuity (edges, boundaries).
• Thresholding (e.g., Otsu’s method) separates foreground/background using pixel intensity, while clustering (e.g., K-means) groups similar pixels in feature space.
• Edge detection (Sobel, Canny) identifies boundaries between regions, and region-growing merges adjacent pixels with similar properties.
• Morphological segmentation uses erosion/dilation to refine regions, and graph-based methods (e.g., normalized cuts) partition images via energy minimization.
• Applications span medical imaging (tumor detection), autonomous driving (lane segmentation), and facial recognition (feature extraction).
• Evaluation metrics (Dice coefficient, IoU) quantify segmentation accuracy compared to ground truth.

1. Introduction to Image Segmentation

Why Segment Images?

• Object identification: Locate and isolate objects (e.g., a tumor in an MRI scan).
• Feature extraction: Prepare data for higher-level analysis (e.g., facial recognition).
• Data compression: Represent images compactly by storing region properties.
• Scene understanding: Interpret complex scenes (e.g., traffic signs in self-driving cars).

Types of Segmentation

Segmentation methods can be broadly classified into:

1. Discontinuity-based (edge detection).
2. Similarity-based (thresholding, region growing, clustering).
3. Hybrid methods (combining multiple techniques).

2. Thresholding-Based Segmentation

Thresholding is the simplest segmentation technique, where pixels are classified into foreground and background based on a global or local intensity threshold.

How It Works

• Global thresholding: A single threshold $T$ is applied to the entire image.
  • If $I(x,y)>T$, pixel belongs to foreground.
  • Else, background.
• Local thresholding: Threshold varies across regions (e.g., adaptive thresholding for uneven lighting).

Methods

Worked Example: Otsu’s Method

Problem: Segment a binary document image (e.g., a scanned receipt) to separate text from background. Steps:

1. Compute the histogram of pixel intensities (0–255).
2. Assume two classes: foreground (text) and background (paper).
3. Find the threshold $T$ that maximizes inter-class variance: $${\sigma }^2(T)={\omega }_1(T)\cdot {\omega }_2(T)\cdot [{\mu }_1(T)-{\mu }_2(T){]}^2$$ where:
   • ${\omega }_1,{\omega }_2$: weights of foreground/background.
   • ${\mu }_1,{\mu }_2$: mean intensities.
4. Apply $T=180$ (example value for a dark-text-on-light-background image).

Visualization:

graph LR
    A["Original Image"] --> B["Histogram"]
    B --> C["Compute Optimal T"]
    C --> D["Apply Threshold"]
    D --> E["Segmented Image"]

Real-World Tie-In:

• eSewa receipt processing: Thresholding separates text (e.g., transaction IDs) from the background for OCR (Optical Character Recognition).
• Nepal Rastra Bank’s currency validation: Detects counterfeit notes by segmenting and analyzing ink patterns.

3. Clustering-Based Segmentation

Clustering groups pixels into $K$ clusters based on feature similarity (e.g., RGB, texture). Common methods:

• K-means: Partitions pixels into $K$ clusters by minimizing within-cluster variance.
• Fuzzy C-means: Allows soft assignment (pixels belong to clusters with probabilities).
• Mean-shift: Non-parametric clustering that finds dense regions in feature space.

K-means Segmentation Worked Example

Problem: Segment a satellite image into vegetation, water, and urban regions. Steps:

1. Extract RGB features for each pixel.
2. Initialize $K=3$ centroids randomly.
3. Assign each pixel to the nearest centroid (Euclidean distance in RGB space).
4. Recompute centroids as the mean of assigned pixels.
5. Repeat until convergence.

Visualization:

graph TD
    A["Satellite Image"] --> B["Extract RGB Features"]
    B --> C["Initialize 3 Centroids"]
    C --> D["Assign Pixels to Clusters"]
    D --> E["Update Centroids"]
    E -->|"Converged?"| F{"No"}
    F -->|"Yes"| G["Segmented Image"]
    F --> C

Real-World Tie-In:

• Nepal’s NTC’s traffic monitoring: Clustering segments roads, vehicles, and pedestrians in surveillance footage for congestion analysis.
• Daraz’s product categorization: Groups similar items (e.g., shoes) in images for automated tagging.

4. Edge-Based Segmentation

Edges represent discontinuities in intensity, texture, or color. Edge detection is followed by edge linking to form closed boundaries.

Key Edge Detection Operators

Canny Edge Detection Worked Example

Problem: Detect edges in a medical X-ray (e.g., bone fracture). Steps:

1. Noise reduction: Apply Gaussian blur ($\sigma =1$).
2. Gradient computation: Compute intensity gradients $G$ and orientation $\theta$ using Sobel.
3. Non-max suppression: Keep only local maxima in gradient direction.
4. Hysteresis thresholding: Classify edges as strong/weak and link weak edges to strong ones.

Visualization:

graph LR
    A["X-ray Image"] --> B["Gaussian Blur"]
    B --> C["Compute Gradients"]
    C --> D["Non-Max Suppression"]
    D --> E["Hysteresis Thresholding"]
    E --> F["Edge Map"]

Real-World Tie-In:

• Pathao’s autonomous delivery: Edge detection identifies sidewalks, obstacles, and drop-off points in route planning.
• Nepal Police’s license plate recognition: Edges isolate plates from vehicle images for OCR.

5. Region-Based Segmentation

Region-growing starts with seed pixels and merges adjacent pixels with similar properties (e.g., intensity, texture).

Methods

Worked Example: Region Growing for Tumor Detection

Problem: Segment a brain MRI to isolate a tumor. Steps:

1. Select seed points (e.g., manually or via thresholding).
2. Define a similarity criterion: $|I_{\text{pixel}}-I_{\text{seed}}|<20$ (for 8-bit images).
3. Grow regions by adding adjacent pixels that satisfy the criterion.
4. Stop when no more pixels meet the condition.

Visualization:

graph TD
    A["MRI Scan"] --> B["Select Seed"]
    B --> C["Define Similarity Threshold"]
    C --> D["Grow Region"]
    D --> E["Check Adjacent Pixels"]
    E -->|"Condition Met"| D
    E -->|"Terminate"| F["Segmented Tumor"]

Real-World Tie-In:

• Kathmandu’s traffic congestion analysis: Region growing segments vehicles in CCTV footage to count traffic flow.
• Nepal’s NEPSE stock chart analysis: Segments price trends (bull/bear markets) for automated trading signals.

6. Morphological Segmentation

Morphological operations (erosion, dilation, opening, closing) refine regions by shaping them using structuring elements (e.g., disks, rectangles).

Key Operations

Worked Example: License Plate Segmentation

Problem: Clean up a noisy license plate image before OCR. Steps:

1. Apply morphological opening (disk-shaped structuring element, radius = 2) to remove salt-and-pepper noise.
2. Use dilation to connect broken characters.
3. Apply thresholding to binarize the result.

Visualization:

graph LR
    A["Noisy Plate"] --> B["Opening (Noise Removal)"]
    B --> C["Dilation (Connect Characters)"]
    C --> D["Thresholding"]
    D --> E["Clean Plate"]

Real-World Tie-In:

• Ncell’s SIM card verification: Morphological operations clean up fingerprints on SIM slots for automated validation.
• Nepal’s NTC’s road crack detection: Erosion/dilation highlights cracks in pavement images.

7. Graph-Based Segmentation

Graph-based methods (e.g., normalized cuts) represent an image as a graph where:

• Nodes = pixels/regions.
• Edges = similarity between regions (e.g., weight = $e^{-(I_i-I_j{)}^2/2{\sigma }^2}$).

Objective: Partition the graph into $K$ clusters by minimizing a cost function (e.g., cut size).

Normalized Cuts Worked Example

Problem: Segment a face image into skin, hair, and background. Steps:

1. Build a graph where each pixel is a node.
2. Compute edge weights based on intensity similarity.
3. Solve the eigenvector problem to find optimal cuts.
4. Assign pixels to regions based on eigenvectors.

Visualization:

graph TD
    A["Face Image"] --> B["Build Graph"]
    B --> C["Compute Edge Weights"]
    C --> D["Solve Eigenvector Problem"]
    D --> E["Partition Graph"]
    E --> F["Segmented Face"]

Real-World Tie-In:

• WhatsApp’s sticker segmentation: Graph cuts isolate stickers from complex backgrounds for resizing.
• YouTube’s content moderation: Segments violent/non-violent regions in videos for automated flagging.

8. Evaluation Metrics

Segmentation accuracy is quantified using:

Worked Example: For a tumor segmentation task:

• Ground truth (GT): 1000 pixels labeled as tumor.
• Predicted (P): 900 pixels labeled as tumor, with 850 true positives.
• Dice score: $\frac{2\times 850}{1000+900}=0.92$ (92% accuracy).

In the Real World

1. eSewa’s Receipt Processing:

   • Thresholding + OCR: Segments text from receipts (e.g., transaction IDs, amounts) using adaptive thresholding, then applies OCR to extract data for digital records.
   • Why it matters: Automates invoice verification for tax compliance.

2. Pathao’s Autonomous Delivery:

   • Edge detection + region growing: Detects sidewalks (edges) and drop-off zones (regions) in route planning to avoid obstacles.
   • Why it matters: Reduces delivery errors in Kathmandu’s chaotic traffic.

3. Nepal’s NTC’s Traffic Monitoring:

   • Clustering (K-means) + morphological operations: Segments vehicles/pedestrians in CCTV footage to analyze congestion patterns.
   • Why it matters: Helps optimize traffic signal timings in Pokhara/Lalitpur.

4. Ncell’s SIM Card Authentication:

   • Morphological cleaning + OCR: Removes smudges from fingerprint images on SIM slots before matching against databases.
   • Why it matters: Prevents fraud in mobile top-ups.

5. NEPSE’s Stock Chart Analysis:

   • Region growing: Segments bull/bear markets in historical price charts to generate trading signals.
   • Why it matters: Assists algorithmic traders in timing buy/sell decisions.

Exam Tip

What Examiners Look For

1. Definitions:

   • Clearly distinguish between thresholding, clustering, and edge-based methods.
   • Example: "Thresholding uses intensity values, while clustering groups pixels in feature space."

2. Mathematical Steps:

   • For Otsu’s method, show the inter-class variance formula and how $T$ is chosen.
   • For K-means, describe centroid initialization and convergence criteria.

3. Visualizations:

   • Draw histograms for thresholding, feature spaces for clustering, and edge maps for Canny.
   • Label all axes and regions (e.g., "foreground," "background").

4. Applications:

   • Link methods to real-world problems (e.g., "Use region growing for tumor segmentation in MRI scans").
   • Avoid vague answers like "used in medical imaging"; specify how (e.g., "seed selection in brain scans").

5. Evaluation:

   • Calculate Dice coefficient or IoU for a given segmentation result.
   • Example: Given GT and predicted masks, compute overlap metrics.

Common Pitfalls

• Ignoring noise: Always mention preprocessing (e.g., Gaussian blur before Canny).
• Incorrect assumptions: Never assume a method works for all images (e.g., global thresholding fails with uneven lighting).
• Skipping steps: For K-means, show all iterations (even if simplified).

Model Answer Structure

Use this template for exam questions:

1. Introduction: Define the method (1 mark).
2. Steps: List and explain each step with math/formulas (4 marks).
3. Example: Show a worked trace with small numbers (3 marks).
4. Applications: Name 2 real-world uses (1 mark).
5. Limitations: Mention 1 weakness (1 mark).

Practice Questions

1. Short Answer:
   • "Explain how Otsu’s method selects the optimal threshold. Provide the formula for inter-class variance."
2. Long Answer:
   • "Segment a binary document image using adaptive thresholding. Show the steps, including how local thresholds are computed, and discuss its advantage over global thresholding."
3. Problem-Solving:
   • "Given a 3×3 image with pixel values [[10, 20, 30], [40, 50, 60], [70, 80, 90]], apply K-means (K=2) starting with centroids at 20 and 70. Show the final segmentation after one iteration."