Region Growing & Split-and-Merge

"Plant me a seed and I will spread to every neighbor that resembles my heart. Plant it badly and I will swallow the whole image. Choose wisely."

A Region-Growing Routine With Boundless Enthusiasm

The previous section left us with a baseline that segments color correctly but ignores the image grid entirely, producing speckle and merging objects that merely share a color. This section restores spatial connectivity in the most direct way imaginable: a region is grown one neighbor at a time, so it is connected from its first pixel to its last. We are trading the global-but-blind view of clustering for a local-but-grounded one. The flood-fill machinery here is a close cousin of the connected-components labeling you met in Chapter 6; the difference is that the inclusion test now depends on intensity similarity, not just on a fixed binary mask.

1. Region Growing: Flood-Fill With a Predicate Basic

The algorithm is a breadth-first or depth-first traversal of the pixel grid, gated by a homogeneity predicate $P$. Starting from a seed pixel $s$, maintain a queue of candidate pixels. Pop a pixel, and for each of its 4- or 8-connected neighbors that has not yet been assigned a region, test $P$. If the neighbor passes, add it to the region and push it onto the queue; if it fails, it becomes a boundary and is left for another region. Growth stops when the queue empties.

The predicate is where all the design lives. Three common forms, in order of robustness:

• Compare to the seed. Include neighbor $p$ if $|I(p) - I(s)| \le \tau$. Simple, but a region can drift far from the seed's value through a chain of small steps, the so-called leakage problem.
• Compare to the immediate neighbor. Include $p$ if $|I(p) - I(q)| \le \tau$ where $q$ is the already-included pixel we are expanding from. This follows gentle gradients and leaks even more readily across a slow ramp.
• Compare to the running region mean. Include $p$ if $|I(p) - \bar{I}_{\text{region}}| \le \tau$, updating $\bar{I}$ as the region grows. This resists leakage best, because the region's accumulated statistics anchor the test, and it is the form used in the code below.

Figure 11.2.1 traces the first few expansion steps from a single seed under the region-mean predicate, showing how the frontier advances into homogeneous territory and halts at an intensity step.

Here is a compact from-scratch region grower using the region-mean predicate and a queue. It works on a grayscale image and returns a boolean mask of the grown region.

import numpy as np
from collections import deque

def region_grow(gray, seed, tau=12.0, connectivity=4):
    """Grow a region from `seed` (row, col); include a pixel if its value is
    within tau of the region's running mean. Returns a boolean mask."""
    h, w = gray.shape
    mask = np.zeros((h, w), dtype=bool)
    r0, c0 = seed
    mask[r0, c0] = True
    total, count = float(gray[r0, c0]), 1          # running sum and pixel count
    q = deque([(r0, c0)])
    nbrs = [(-1,0),(1,0),(0,-1),(0,1)]
    if connectivity == 8:
        nbrs += [(-1,-1),(-1,1),(1,-1),(1,1)]

    while q:
        r, c = q.popleft()
        for dr, dc in nbrs:
            rr, cc = r + dr, c + dc
            if 0 <= rr < h and 0 <= cc < w and not mask[rr, cc]:
                region_mean = total / count
                if abs(float(gray[rr, cc]) - region_mean) <= tau:
                    mask[rr, cc] = True
                    total += float(gray[rr, cc])    # update stats as region grows
                    count += 1
                    q.append((rr, cc))
    return mask

gray = np.array([[101,99,103,42,40],
                 [100,100,98,39,41],
                 [97,102,104,38,40]], dtype=np.uint8)
m = region_grow(gray, seed=(1,1), tau=12)
print(m.astype(int))
# [[1 1 1 0 0]
#  [1 1 1 0 0]
#  [1 1 1 0 0]]   <- the bright block grew; the dark block was rejected

2. Seed Selection: Where You Start Decides Everything Basic

A region grower is only as good as its seeds. A seed placed inside the object grows the object; a seed placed on a boundary grows ambiguously; a seed placed in the wrong region grows the wrong thing. Three strategies dominate:

• Manual seeds. A user clicks inside each region of interest. This is the interactive segmentation tradition, and it remains how the magic-wand tools in image editors work. It is also the conceptual ancestor of the click prompts SAM uses in Chapter 24.
• Automatic seeds from extrema. Use local intensity minima or maxima, or the peaks of the distance transform from Chapter 6, as seeds. This is exactly the marker-finding move that Section 11.3's marker-controlled watershed formalizes.
• Grid seeds. Place seeds on a regular lattice and grow all of them at once, letting regions compete for pixels. This is the seed-of-an-idea behind superpixels in Section 11.5.

A subtle point: when many seeds grow simultaneously, you must decide what happens when two frontiers meet. The usual rule is first-come-first-served, the pixel joins whichever region reached it first, which makes the result mildly dependent on traversal order. OpenCV's cv2.floodFill implements single-seed growing with a configurable tolerance and is the fastest path to a working region grower.

import cv2
import numpy as np

img = cv2.imread("scene.jpg")
h, w = img.shape[:2]
mask = np.zeros((h + 2, w + 2), np.uint8)   # floodFill requires a +2 border mask

seed = (w // 2, h // 2)                      # (x, y), note OpenCV's column-first order
# loDiff / upDiff: how far below / above the seed a neighbor may be and still join.
# FLOODFILL_FIXED_RANGE compares each pixel to the SEED, not to its neighbor.
flags = 8 | cv2.FLOODFILL_FIXED_RANGE | (255 << 8)
num, _, mask, rect = cv2.floodFill(
    img.copy(), mask, seed, newVal=(0, 255, 0),
    loDiff=(12, 12, 12), upDiff=(12, 12, 12), flags=flags)

print(num, "pixels grown into the region; bounding box:", rect)
# 48217 pixels grown into the region; bounding box: (61, 70, 410, 305)

3. Split-and-Merge: Top-Down Homogeneity Intermediate

Region growing is bottom-up: it starts from points and expands. Split-and-merge is its top-down dual. It starts with the whole image as one region and recursively subdivides:

1. Split. If a region fails the homogeneity predicate (for example its intensity variance exceeds a threshold), split it into four equal quadrants. Recurse on each quadrant. This produces a quadtree, in which every leaf is a homogeneous square block.
2. Merge. Sweep the leaf blocks and merge any two adjacent ones whose union still satisfies the predicate. Repeat until no more merges are possible.

The split phase guarantees homogeneity but produces an over-segmented grid of squares with blocky boundaries; the merge phase glues those squares back into natural regions. Figure 11.2.2 shows the quadtree split of a synthetic image with one textured corner.

Split-and-merge has a real advantage over region growing: it needs no seeds. The recursive structure visits the whole image, so nothing depends on a lucky starting point. Its disadvantages are equally real: the quadtree's square subdivision imposes blocky, axis-aligned boundaries that the merge step only partly removes, and the merge step's adjacency bookkeeping is fiddly to implement correctly. scikit-image does not ship a single split-and-merge call, but its region adjacency graph tools make the merge phase tractable, and the closely related felzenszwalb segmentation of Section 11.4 achieves the same homogeneity-driven merging far more efficiently.

from skimage.future import graph
from skimage.segmentation import felzenszwalb
from skimage import data

img = data.astronaut()
labels = felzenszwalb(img, scale=200, sigma=0.8, min_size=50)  # fast initial regions
rag = graph.rag_mean_color(img, labels)                        # build adjacency graph
merged = graph.cut_threshold(labels, rag, thresh=29)           # merge similar neighbors
print("regions before merge:", labels.max() + 1,
      " after merge:", merged.max() + 1)
# regions before merge: 412  after merge: 78

4. The Limits of Greedy Growing Intermediate

Region growing and split-and-merge share a hidden weakness: both make greedy, local decisions and never reconsider them. Once region growing admits a pixel, it stays admitted, even if it later turns out to be the gateway through which the region leaked into a neighbor. Once split-and-merge merges two blocks, the merge is permanent. Neither method optimizes a global objective, so neither can recover from an early mistake. This is precisely the gap that Section 11.4's graph-cut formulation closes: by writing the segmentation as the minimum of a global energy, graph cuts find the partition that is best overall, not merely the one that greedy local steps stumbled into.

There is also a problem these methods cannot even attempt: touching objects of the same intensity. Two cells pressed against each other, or two coins overlapping slightly, present no intensity boundary between them, so region growing floods straight across and returns them as one region. No homogeneity predicate can split them, because by the predicate's own measure they are homogeneous. Separating them requires shape information, specifically the geometry of how the blob narrows at the junction, and that is exactly what the watershed transform of the next section reads off the distance transform. Keep the touching-cells problem in mind; it is the headline motivation for Section 11.3.