Region Growing Segmentation

Region growing is a bottom-up segmentation technique that builds image regions incrementally, starting from one or more seed pixels and repeatedly annexing neighboring pixels that satisfy a homogeneity criterion relative to the growing region. Unlike thresholding, which partitions pixels purely by intensity value, region growing enforces spatial connectivity: a pixel can only join a region if it is adjacent (in the 4-neighbor or 8-neighbor sense) to a pixel already in that region. The output is, by construction, a set of connected components that tile (part of) the image. Three ingredients define any region-growing algorithm. First, the seed set $S_0$: one or more starting pixels, chosen manually, by a grid, or by local extrema of some feature (e.g., pixels with locally minimal gradient magnitude, indicating flat, likely-homogeneous interior points). Second, the connectivity structure: which neighbor pixels are candidates for inclusion — typically the 4 orthogonal neighbors or the 8 including diagonals. Third, the homogeneity predicate $H(p, R)$: a Boolean or thresholded test of whether candidate pixel $p$ is similar enough to current region $R$ to be absorbed. Common choices include

where $\mu_R$ and $\sigma_R$ are the running mean and standard deviation of intensities inside $R$, updated as pixels are added, and $T$, $k$ are user-chosen tolerances. The middle and right variants are strictly more powerful than the seed-only test because they let the region's notion of "typical value" adapt as it grows across a smoothly varying but non-constant surface (e.g., shading gradients), at the cost of being sensitive to growth order and to noisy early absorptions dragging $\mu_R$ off target. Region growing sits in the same conceptual family as Image Thresholding but adds the missing ingredient — spatial coherence — and foreshadows Morphological Operations, which are typically applied afterward to smooth jagged region boundaries, fill small holes, and remove spurious pixel-scale artifacts that a purely local homogeneity test cannot prevent.

The clean way to implement seeded region growing is as a breadth-first search (or, for order-robust variants, a best-first search using a priority queue) over the pixel grid graph, where the "already visited" test of ordinary BFS is augmented with the homogeneity test.

Step 1 — Seed selection. Choose one seed per intended region: manually clicked points, a regular grid of candidate seeds later merged, or automatic seeds at local intensity extrema / low-gradient plateaus. Each seed gets a unique region label.

Step 2 — Initialize. For each seed, create a region record holding its label, its running mean $\mu$, running sum of squares (for variance), and pixel count $n=1$. Push the seed into a FIFO queue (or priority queue, keyed by similarity) and mark it visited.

Step 3 — Grow. Pop a pixel $p$ from the queue. For each unvisited neighbor $q$ of $p$ (4- or 8-connected):

• Evaluate the homogeneity predicate $H(q, R)$ using the current running statistics of region $R$.
• If it passes, label $q$ with $R$'s label, mark it visited, update $R$'s running mean/variance to include $I(q)$, and push $q$ onto the queue.
• If it fails, leave $q$ unvisited (it may later be claimed by a different, adjacent region, or remain unlabeled background).

Step 4 — Terminate. Stop when the queue is empty for every region. Every pixel is now either labeled with exactly one region or left unlabeled (if it never satisfied any region's predicate).

Step 5 (optional) — Post-process. Merge tiny regions into neighbors, relabel unlabeled pixels via nearest-region assignment, and clean boundaries — commonly using Morphological Operations such as opening/closing. ``` function REGION_GROW(image, seeds, T): n_rows, n_cols = image.shape label = array of size (n_rows, n_cols), initialized to UNLABELED visited = array of booleans, initialized to False regions = empty map from label_id -> RegionStats(mean, sum_sq, count) queue = empty FIFO queue # holds (row, col, label_id) for i, (r, c) in enumerate(seeds): label_id = i + 1 label[r][c] = label_id visited[r][c] = True regions[label_id] = RegionStats(mean=image[r][c], sum_sq=image[r][c]^2, count=1) queue.push((r, c, label_id)) while queue is not empty: (r, c, label_id) = queue.pop_front() R = regions[label_id] for (nr, nc) in NEIGHBORS(r, c, connectivity=8): # bounds-checked if not in_bounds(nr, nc): continue if visited[nr][nc]: continue value = image[nr][nc] if HOMOGENEOUS(value, R, T): visited[nr][nc] = True label[nr][nc] = label_id R.count += 1 R.sum += value R.sum_sq += value * value R.mean = R.sum / R.count queue.push((nr, nc, label_id))

# else: leave unvisited; may be claimed later by another region

# or remain UNLABELED forever return label

function HOMOGENEOUS(value, R, T): return abs(value - R.mean) <= T ``` The critical correctness-preserving detail is that `visited` is set at the moment of acceptance, not at the moment of testing — this is exactly the standard BFS discipline that prevents a pixel from being pushed onto the queue by two different regions and processed twice. Ties (a pixel adjacent to two regions, both willing to accept it) are broken by processing order: whichever region reaches it first in the queue claims it. This first-come-first-served rule is simple but is the direct source of order-dependence discussed in the pitfalls below; a priority-queue variant that always expands the globally most similar pending pixel next (a "best-first" region grower) reduces, but does not eliminate, this dependence.

Time complexity. Each pixel is pushed onto the queue at most once, because it is marked `visited` at the moment of acceptance and the algorithm never re-examines a `visited` pixel as a candidate. Popping and processing a pixel does $O(1)$ work per neighbor under 4- or 8-connectivity (a constant number of neighbors), plus $O(1)$ amortized work to update running mean/variance incrementally. With $N$ total pixels, the total work is

where $c \in \{4, 8\}$ is the connectivity constant. This is identical in form to the $O(V + E)$ bound for BFS on a graph, specialized to a grid graph where $E = O(N)$.

Space complexity. The `label` and `visited` arrays are $O(N)$. The queue holds at most $N$ pixels at any time, so it is $O(N)$ as well. Region statistics are $O(1)$ per region and $O(R)$ total for $R$ regions, dominated by the $O(N)$ terms whenever $R \ll N$ (the typical case). Total space is $O(N)$.

Correctness (connectivity invariant). Define the invariant: at every point during execution, every labeled pixel $q$ with label $\ell$ is connected to the seed of region $\ell$ through a path of pixels, each consecutive pair adjacent, each pixel on the path already labeled $\ell$. This holds initially (seeds are trivially connected to themselves) and is preserved by the growth step: a pixel $q$ is only ever labeled $\ell$ when it is popped as a neighbor of some already-$\ell$-labeled pixel $p$, so the path to $p$'s seed extends by one edge to include $q$. By induction over the sequence of accept operations, the invariant holds at termination, which proves: > Claim. Every output region is a connected subgraph of the pixel adjacency graph. This is precisely the property thresholding lacks and region growing guarantees by construction — the proof is a direct transcription of the standard BFS reachability argument, with the homogeneity predicate simply pruning which edges are traversable.

What correctness does not guarantee. The invariant says nothing about whether the region is semantically correct (i.e., matches the true object boundary). That depends entirely on how well $H$ approximates "is part of the same real-world surface," which is a modeling choice, not something the traversal argument can certify. In particular:

• If two true objects are connected in the image by even a single thin bridge of similar intensity (e.g., a shadow or blur), the algorithm cannot distinguish them — this is leakage, discussed below.
• The final segmentation can depend on the order in which the queue is processed when a boundary pixel is equally eligible for two regions; FIFO BFS and best-first search can produce different final boundaries, both individually "correct" with respect to the invariant but different from each other.

Tradeoffs. Region growing is cheap and simple, and its output is guaranteed connected and free of the salt-and-pepper noise that pure thresholding produces — but it is a greedy, local algorithm: it never backtracks or reconsiders an earlier acceptance in light of later evidence, so early noisy pixels can permanently bias $\mu_R$ and cause a slow "drift" of the region into territory a global view would have excluded. More globally aware alternatives (graph cuts, watershed with markers, level sets) trade this cheapness for the ability to jointly optimize over the whole partition, at higher computational cost.

Consider a tiny $5 \times 5$ grayscale image (intensity values 0–255), with a bright blob in the upper-left and darker background elsewhere. We grow one region from a single seed at $(0,0)$ (value 200), using the mean-based homogeneity test with threshold $T = 15$: accept a neighbor if $|I(\text{neighbor}) - \mu_R| \le 15$. Image (row, col), 0-indexed: ``` row\col 0 1 2 3 4 0 200 195 120 110 105 1 190 205 115 108 100 2 130 125 118 112 102 3 120 118 116 110 100 4 115 112 110 108 100 ``` Trace of the queue (4-connectivity), showing region mean $\mu_R$ before each test:

The queue empties after step 8: no further pixel in the frontier passes the test. The final region is exactly $\{(0,0), (0,1), (1,0), (1,1)\}$ — the four bright corner pixels — while the darker background remains unlabeled, correctly separating the blob from the surrounding tissue-like texture despite the background itself having non-uniform values (110–130) that a naive global threshold at, say, 150 would have handled identically anyway. The instructive part is step 3 versus step 6: pixel (0,2)=120 is rejected early while $\mu_R = 195$, but if the algorithm had instead grown down through (2,0)=130 first and drifted $\mu_R$ downward before ever reaching (0,2), the same pixel might have been accepted — a direct, concrete illustration of order-dependence: the final region boundary is a function not just of the image and $T$, but of traversal order.

Region growing emerged from the earliest wave of digital image processing research, when researchers sought computationally cheap alternatives to global thresholding for photointerpretation and medical scans. The technique's core idea — grow a connected region from a seed using a local similarity test — was formalized and popularized in the image processing literature of the 1970s, alongside split-and-merge quadtree methods that attacked the same problem from the opposite direction (top-down splitting rather than bottom-up growing).

Region growing remains a working tool wherever a human or automated system can supply reliable seed points and needs a fast, interpretable, connectivity-guaranteed segmentation. Medical imaging software uses seeded region growing for interactive tumor, organ, and vessel delineation in MRI and CT, where a clinician clicks a point inside the structure of interest and the algorithm proposes a boundary that a radiologist then edits. Remote sensing pipelines use it to segment land-cover types (water bodies, forest canopy, urban blocks) in satellite imagery, seeding from known ground-truth points. Industrial inspection systems use region growing to isolate a defect region on a manufactured part once a rough location is flagged by a coarser detector. It also serves as a fast preprocessing stage before more expensive graph-based or learned segmentation methods, providing an initial region proposal that is then refined — and it is frequently followed immediately by Morphological Operations to smooth boundaries and by connected-component analysis to filter spurious small regions, reflecting its place as one classical stage in a longer classical vision pipeline that also draws on Image Thresholding and Edge Detection.

Ask the tutor: How would you redesign the homogeneity criterion to make region growing robust against leakage through thin low-contrast bridges?