AI.Cruz - Learn AI Through Interactive Visualizations

COMPUTER VISION

Watershed Algorithm for Image Segmentation

Watershed treats the gradient image as a topographic landscape and floods it from marker seeds, drawing boundaries where rising water from different basins would meet.

1The Topographic Metaphor

The watershed algorithm borrows its intuition from hydrology. Imagine pouring water onto a mountain range: it flows downhill, collects in valleys, and two streams separated by a ridge belong to different drainage basins. In image processing, the gradient magnitude image |∇I| plays the role of the terrain — high gradient = ridge (edge), low gradient = valley (homogeneous region). The algorithm floods this landscape from local minima upward. Every pixel eventually belongs to the basin whose seed reached it first.

Key mapping: pixel intensity in the gradient image → elevation. Local minimum → basin seed (valley bottom). High gradient → ridge (likely an object boundary). Watershed line → the boundary drawn where adjacent basins meet — this becomes the segmentation contour.

Gradient Image
Computed as |∇I| (Sobel, Canny, or morphological gradient). High values mark transitions between regions. This is the "elevation map" the algorithm floods.

Basin / Region
A connected set of pixels whose flooding water all originated from the same seed. After convergence, each basin becomes one segment in the output label map.

Watershed Line
The set of pixels where two basins would merge. These pixels receive a special label (boundary) in the output image, forming the segmentation contour.

2Markers and the Flooding Algorithm

Naive watershed floods from every local minimum — which causes extreme over-segmentation (see Section 3). The practical version is marker-controlled watershed: you provide seeds (markers) for each object and one background marker, then flood only from those seeds. This gives you direct control over the number of output regions.

Algorithm steps: (1) Compute gradient magnitude |∇I|. (2) Place foreground markers inside each object of interest (e.g., brightest points from distance transform). (3) Place a background marker in background regions. (4) Run priority-queue flooding: pixels are processed in order of gradient height, lowest first. Each pixel inherits the label of the lowest-gradient neighbour already labelled. (5) When a pixel would receive two different labels simultaneously, mark it as a watershed boundary. (6) Output: label map where each pixel is assigned a region ID or boundary.

Markers are typically generated automatically: for cell segmentation, the distance transform of a binary foreground mask is computed first — local maxima of the distance transform correspond to object centres (furthest from any background pixel), making excellent seeds. For more general cases, morphological erosion or manual annotation supplies the markers.

3The Over-Segmentation Problem

The classic failure mode of naive watershed is over-segmentation: even a slightly noisy gradient image has hundreds of spurious local minima, each generating its own basin. The result looks like a shattered mosaic rather than a clean partition. Three standard remedies exist:

Solutions

Marker control — specify exactly how many seeds; watershed cannot create more regions than markers.
Gaussian pre-smoothing — blur the gradient image first to merge shallow noise minima.
H-minima transform — suppress all local minima whose depth is less than threshold h.

When It Happens

Textured regions with many small gradient variations.
Compression artefacts (JPEG blocks create false gradients).
Low-contrast images where object boundaries are barely stronger than noise.
Any scenario where the gradient alone cannot reliably locate objects.

4Applications and Practical Notes

Watershed excels wherever objects touch or overlap, making boundary detection alone insufficient. The classic application is cell counting in microscopy: cells stain as bright blobs that often touch; watershed separates them using the distance-transform-seeded approach. Other applications include geology (watershed of elevation DEMs), document analysis (separating touching printed characters), and industrial inspection (segmenting overlapping components on a conveyor).

OpenCV Usage
cv2.watershed(img, markers) modifies the markers array in place. Boundaries are set to -1. Input must be 8UC3 (BGR image), markers must be 32-bit signed integers with positive region IDs and 0 for unknown pixels.

scikit-image
skimage.segmentation.watershed(gradient, markers) accepts grayscale gradient images. The compactness parameter mixes gradient and Euclidean distance, producing more regular-shaped regions (useful for superpixel generation).

vs. Mean Shift
Mean shift segments by colour density; watershed by gradient topology. Watershed is faster and produces hard boundaries; mean shift is smoother and scale-free. For touching cells use watershed; for colour-based region grouping use mean shift.

Mean Shift →Edge Detection →Semantic Segmentation →

Watershed concept: 1D flood fill from local minima (gradient profile)

import numpy as np

# 1D gradient profile — simulates a cross-section of a gradient magnitude image.
# High values = strong edges (ridges), low values = homogeneous regions (valleys).
gradient = np.array([0.9, 0.3, 0.1, 0.4, 0.85, 0.2, 0.05, 0.3, 0.8, 0.95])

def local_minima(arr):
    mins = []
    for i in range(1, len(arr) - 1):
        if arr[i] < arr[i-1] and arr[i] < arr[i+1]:
            mins.append(i)
    return mins

def watershed_1d(gradient, seeds):
    n = len(gradient)
    labels = [-1] * n  # -1 = unlabelled
    for label, idx in enumerate(seeds):
        labels[idx] = label
    # Iterative flood fill: each unlabelled pixel inherits its neighbour's label
    changed = True
    while changed:
        changed = False
        for i in range(n):
            if labels[i] == -1:
                if i > 0 and labels[i - 1] >= 0:
                    labels[i] = labels[i - 1]
                    changed = True
                elif i < n - 1 and labels[i + 1] >= 0:
                    labels[i] = labels[i + 1]
                    changed = True
    return labels

seeds = local_minima(gradient)
labels = watershed_1d(gradient, seeds)

print("Gradient profile (high = ridge/edge, low = valley/region):")
print("  " + str([round(v, 2) for v in gradient.tolist()]))
print()
print("Auto-detected seeds (local minima): " + str(seeds))
for i, s in enumerate(seeds):
    print("  Region " + str(i) + " seeded at index " + str(s) +
          "  gradient=" + str(round(float(gradient[s]), 2)))
print()
print("Region labels after flooding: " + str(labels))
print()

walls = [i for i in range(len(labels) - 1) if labels[i] != labels[i + 1]]
print("Watershed boundaries at: " + str(walls))
print()

# ASCII visualisation
seg = ""
for i, l in enumerate(labels):
    if i in walls:
        seg += "|"
    seg += chr(65 + l)
print("Segmentation map:  " + seg)
print("Gradient profile:  " + "".join(
    "H" if v >= 0.6 else ("m" if v >= 0.3 else "l")
    for v in gradient
))
print()
print("H=high gradient (ridge/boundary)  m=medium  l=low (valley/region)")
print("| marks the watershed line — placed at gradient ridges between basins.")