Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 46 ยท Segmentation and Shapes

Segmentation by Clustering and Watershed

Segment images without labels: k-means on pixel colors, region growing from a seed, and the distance transform with watershed to split touching objects.

A threshold splits an image into two groups using one number. Real scenes need more: three colored regions, a gradient background, or two coins that touch and look like one blob. This lesson adds three tools that go beyond a single threshold. Clustering groups pixels that look alike, region growing spreads out from a starting pixel while neighbors stay similar, and watershed cuts touching objects apart using their shape.

None of these methods needs labeled training data. They are unsupervised: the algorithm finds structure in the pixel values and geometry on its own. That makes them great for quick measurements and for preparing masks, and it also means they make mistakes that you have to understand. Before reading on, make sure Thresholding and Connected Components and Labeling feel familiar, because we compare against both.

Clustering pixels with k-means

Every pixel of an RGB image is a point in a three-dimensional color space: (red, green, blue). Pixels of the same object tend to sit close together in that space, forming a cloud. K-means finds k cloud centers and assigns every pixel to its nearest center. The algorithm repeats two steps until nothing changes:

  1. Assign each pixel to the closest center.
  2. Move each center to the mean color of the pixels assigned to it.

You first reshape the image from (H, W, 3) to (H*W, 3), one row per pixel, run the clustering, then reshape the labels back to (H, W). If reshaping is unfamiliar, see Images as Arrays.

Python K-means on pixel colors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three centers come out close to the colors we painted, (200, 40, 40), (30, 120, 40) and (50, 60, 210), even though every pixel was noisy. The cluster numbers themselves are arbitrary: which cluster gets called 0 depends on the random start, so never hard-code "cluster 0 is the background". Rely on the centers (or the cluster sizes) to decide what each cluster means.

The last lines show a second use of the same idea, called color quantization: replace every pixel by its cluster center. km.cluster_centers_[labels] is fancy indexing, a table lookup that turns a label map back into a colored image. With three centers you can store the picture as a tiny palette plus one small number per pixel.

flowchart LR
    A["Image<br/>(H, W, 3)"] --> B["Reshape to<br/>(H*W, 3)"]
    B --> C["K-means<br/>assign and update"]
    C --> D["Labels<br/>(H*W,)"]
    D --> E["Reshape to<br/>(H, W) label map"]
    C --> F["Centers = palette"]

Clustering treats each pixel as an independent point; the image layout only returns at the end.

Limits of color clustering

K-means on color alone has well-known weaknesses:

  • You must choose k. Too few clusters merge different objects; too many split one object into shades.
  • It ignores position. Two separate red objects land in one cluster, and a shadow on a wall may become its own cluster. To add location, append (row, col) columns scaled to a comparable range, so that nearby pixels of similar color group together.
  • It prefers round clouds of similar size. A large, smoothly shaded region can be cut in two while a small bright one is swallowed.
  • Different color spaces give different answers. Clustering in HSV or Lab (see Color Channels and Color Spaces) often matches human perception better than raw RGB.
  • Cost grows with pixels. A 12-megapixel photo has 12 million rows; practitioners shrink the image first, or fit on a random sample of pixels and then predict labels for the rest.

Region growing

Clustering never asks whether two pixels touch. Region growing does the opposite: it starts at a seed pixel and spreads to neighbors that are similar enough, so the result is always one connected region. It is a breadth-first search over the pixel grid (the same idea as a flood fill in a paint program).

The only decisions are the seed and the tolerance: how far a neighbor may differ from the region's current mean. The code below keeps a running total so the mean updates as the region grows.

Python Growing a region from a seed

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The seed sits inside the left bright rectangle, so only its 7 by 6 = 42 pixels are collected. The second bright rectangle is just as bright but is not connected to the first, so it stays out. That is the difference from a threshold, which would select both. When we raise the tolerance to 200, which is larger than the whole intensity range, nothing stops the growth and the region swallows all 240 pixels. Tolerance is the one number that controls everything, and a poor choice either leaks into the background or stops at a noisy pixel.

Region growing is the engine behind "magic wand" selection tools. Its weakness is leaking through thin or blurry boundaries: one weak spot in an edge lets the region escape. Smoothing first (see Blurring and Denoising) helps.

Splitting touching objects: the distance transform

Suppose two coins overlap slightly. A threshold gives one mask, and connected components reports one object. Intensity cannot separate them, but shape can: a pair of overlapping discs has a narrow "waist" where they join.

The distance transform replaces each foreground pixel with its distance to the nearest background pixel. The result is a height map: the deep interior of a coin gets large values and the border gets small ones. Each coin produces its own peak, and the waist between two coins is a low saddle. scipy.ndimage.distance_transform_edt computes it.

Watershed

Imagine the height map as a landscape and slowly pour water into it from chosen markers. Each marker floods its own basin. When two floods meet, you build a wall there. When the whole landscape is flooded, the walls are the boundaries between regions. This is watershed segmentation.

Watershed needs a landscape where objects are valleys. The distance transform gives hills, so we negate it: -dist. Markers are the peaks of the distance map, found with a maximum filter. The marker-based version below uses a priority queue, so the lowest points are flooded first; this is a compact version of the classic algorithm.

Python Separating two touching discs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line confirms the problem: one connected component, although there are two discs. Two markers are found, one near the center of each disc, and the flood produces two labeled regions with a straight seam where the discs overlap. The pixel counts are close to each other because the discs are the same size.

flowchart TB
    A["Binary mask<br/>two touching discs"] --> B["Distance transform<br/>one peak per disc"]
    B --> C["Find peaks<br/>= markers"]
    C --> D["Flood from markers<br/>on -distance"]
    D --> E["Label map<br/>one id per disc"]

Marker-based watershed turns "one blob" into "two objects" without drawing the cut by hand.

Over-segmentation and the role of markers

The mistake everyone makes with watershed is to start it without markers. If every tiny local minimum becomes its own basin, noise breaks the picture into hundreds of fragments. This is over-segmentation. The cure is to supply good markers: peaks of the distance map above a threshold (as we did with dist > 6), the cores of objects found by eroding a mask, or points a person clicked. The size=9 window in the maximum filter plays a similar role: it forbids two peaks closer than about nine pixels, so a slightly bumpy disc still has just one marker.

Production libraries (scipy.ndimage.watershed_ift, scikit-image's watershed, OpenCV's watershed) add speed and plateau handling, but the idea is exactly what you just ran.

Tip: Choose the method from the problem. One brightness difference: threshold. Several colors: k-means. One connected object that you can point at: region growing. Touching, similar objects: distance transform plus watershed.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why should you not rely on 'cluster 0 is the background' after running k-means?

    K-means numbers clusters in whatever order its centers were initialized. Decide what a cluster means by its center color or its size, not by its index.
  2. 2. What is the main difference between region growing and k-means on colors?

    Region growing spreads through neighbors, so its result is one connected region. K-means treats pixels as independent color points, so two separate red objects land in one cluster.
  3. 3. Why is the distance transform negated before running watershed in the example?

    Watershed floods valleys. The distance transform has its highest values at object centers, so negating it turns each object center into a basin.
  4. 4. What typically causes over-segmentation in watershed?

    Without markers, noise creates many tiny basins and the image is cut into fragments. Supplying one marker per object avoids it.
  5. 5. A region-growing run with a very large tolerance returns the whole image. What happened?

    When the tolerance exceeds the intensity range, no pixel is rejected and the region spreads until the whole image is included.

Summary

  • K-means groups pixels by color: reshape to (H*W, 3), cluster, reshape the labels back. Cluster numbers are arbitrary; centers tell you what each cluster is. It needs k, ignores position and can also quantize colors into a palette.
  • Region growing starts at a seed and collects similar neighbors, giving one connected region. The tolerance controls it, and weak edges let it leak.
  • A threshold plus connected components cannot split touching objects; the distance transform turns shape into peaks that can.
  • Watershed floods from markers over a height map such as -dist and builds walls where floods meet. Good markers prevent over-segmentation.
  • Pick the tool by problem: threshold, k-means, region growing or watershed.

Next, find a known pattern inside a larger image: Template Matching.