How to Learn the Hoshen–Kopelman Algorithm: Raster Scans, Union–Find Labels, Connectivity and Large-Scale Component Analysis

How can a computer label every connected blob in a huge grid without launching a fresh search from every blob? The Hoshen–Kopelman algorithm solves the problem by scanning the grid in a fixed order, assigning provisional labels, and recording when two labels turn out to mean the same component. A disjoint-set structure then turns those provisional names into final connected-component identities.

This article teaches Hoshen–Kopelman as a Learning Hall progression from a simple paper grid to production connected-component labelling. It complements the broader Union-Find article and the Flood Fill article. Its distinct job is raster-style component labelling through local predecessor checks plus label-equivalence merging.

Quick Read

Scan the grid in a fixed order, commonly left-to-right and top-to-bottom.
For each foreground cell, inspect only already-processed neighbours.
If none are foreground, create a new provisional label.
If one component label is present, copy it.
If several different labels meet, assign one and union their equivalence classes.
After the scan, replace every provisional label by its canonical Union-Find representative.
Connectivity rules matter: 4-connectivity and 8-connectivity can produce different components from the same pixels.
The algorithm grew out of percolation studies but is broadly useful for binary images, lattice simulations and component statistics.

1. Beginner Level: What Counts as One Component?

Imagine a binary image in which 1 means foreground and 0 means background. A connected component is a group of foreground cells linked under a chosen neighbourhood rule.

4-connectivity: a pixel connects through north, south, east and west.
8-connectivity: diagonal neighbours also count.

Consider two foreground pixels that touch only at a corner. Under 4-connectivity they belong to different components; under 8-connectivity they belong to the same component. So connectivity is not a small implementation detail. It is part of the problem definition.

2. Why a Raster Scan Changes the Problem

If we process cells from top-left to bottom-right, then when we reach a cell we already know everything about the cells above it and to its left. For 4-connectivity, the only previously processed neighbours that can connect to the current cell are typically left and up. For 8-connectivity, the previously visited diagonal neighbours can be included too.

This is the key economy: the algorithm never needs to inspect future pixels when assigning a provisional label. It makes a local decision now and records equivalences when later evidence shows that two provisional labels are really one component.

3. The Three Cases Every Foreground Cell Must Handle

No labelled predecessor neighbour: start a new component with a fresh provisional label.
One component is represented: copy that component’s label.
Two or more different component labels meet: choose one label for the pixel and record that all of the encountered labels are equivalent.

The third case is the reason a simple “copy the neighbour label” method is not enough. Two regions that looked separate earlier in the scan may connect through a later bridge pixel. Hoshen–Kopelman does not go back and repaint every old pixel immediately. Instead, it records the equivalence compactly.

4. Worked Example: When Two Labels Become One

input
1 0 1
1 1 1
0 0 1

first row provisional labels
A 0 B

second row, first cell
A 0 B
A . .

second row, middle cell sees A on the left
A 0 B
A A .

second row, right cell sees A on the left and B above
A 0 B
A A A   and record A == B

At first, the top-left and top-right pixels appear unrelated, so they receive labels A and B. The second-row bridge proves they belong to the same component. Rather than relabelling the entire earlier region immediately, the algorithm unions A and B. During final canonicalisation, every A and B becomes one representative.

5. Union–Find Is the Equivalence Ledger

Union–Find, also called disjoint-set union, stores sets of equivalent labels. Two operations matter:

find(x) returns the canonical representative of label x;
union(a, b) merges the equivalence classes containing a and b.

Path compression and union-by-rank or union-by-size keep these operations extremely cheap in practice. Hoshen–Kopelman supplies the pattern of when to create and merge labels; Union–Find supplies the data structure that remembers those equivalences efficiently.

6. Conceptual Algorithm

make an empty disjoint-set structure
next_label = 1

for each cell in raster order:
    if cell is background:
        continue

    neighbour_roots = canonical labels of relevant
                      already-processed foreground neighbours

    if neighbour_roots is empty:
        label[cell] = next_label
        make_set(next_label)
        next_label += 1

    else:
        chosen = one neighbour root
        label[cell] = chosen
        for each other root in neighbour_roots:
            union(chosen, other root)

for each labelled foreground cell:
    label[cell] = find(label[cell])

optionally compact canonical labels to 1, 2, 3, ...

The final compaction step is optional. A correct component identifier does not have to be consecutive, but consecutive labels are convenient for arrays of component sizes, bounding boxes and measurements.

7. A Transparent Python Teaching Implementation

def hoshen_kopelman(binary):
    h = len(binary)
    w = len(binary[0]) if h else 0
    labels = [[0] * w for _ in range(h)]
    parent = [0]  # label 0 is background

    def make_label():
        parent.append(len(parent))
        return len(parent) - 1

    def find(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != x:
            nxt = parent[x]
            parent[x] = root
            x = nxt
        return root

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
        return ra

    for r in range(h):
        for c in range(w):
            if not binary[r][c]:
                continue

            neighbours = []
            if c > 0 and labels[r][c - 1]:
                neighbours.append(find(labels[r][c - 1]))
            if r > 0 and labels[r - 1][c]:
                neighbours.append(find(labels[r - 1][c]))

            if not neighbours:
                labels[r][c] = make_label()
            else:
                chosen = neighbours[0]
                labels[r][c] = chosen
                for other in neighbours[1:]:
                    chosen = union(chosen, other)

    remap = {}
    next_compact = 1
    for r in range(h):
        for c in range(w):
            if labels[r][c]:
                root = find(labels[r][c])
                if root not in remap:
                    remap[root] = next_compact
                    next_compact += 1
                labels[r][c] = remap[root]

    return labels

This version deliberately uses only left and upper neighbours, so it implements 4-connectivity for a 2D raster. To teach 8-connectivity, add the two already-visited diagonals and reason carefully about image boundaries.

8. The Invariant That Makes the Scan Trustworthy

After processing any prefix of the raster, every processed foreground cell has a provisional label whose Union–Find class represents the connectivity discovered so far. If two processed cells are already known to be connected through processed foreground cells, their labels have the same canonical representative.

This invariant is more valuable than memorising code. It tells you why a bridge pixel requires a union, why unprocessed neighbours do not matter yet, and why a final canonicalisation pass is sufficient.

9. Complexity: Almost Linear in the Number of Cells

Let P be the number of grid cells and L the number of provisional labels. The raster scan itself is O(P). With path compression plus a good union rule, a sequence of Union–Find operations has near-constant amortised cost, commonly expressed using the inverse Ackermann function α(L). A practical bound for the whole labelling process is therefore close to O(P·α(L)), followed by an O(P) canonicalisation pass.

In real images, memory traffic can matter more than the inverse-Ackermann term. Reading pixels, writing labels and touching parent arrays efficiently often dominates the measured runtime.

10. Hoshen–Kopelman Versus Flood Fill

Flood fill and Hoshen–Kopelman can both identify connected regions, but their operational shapes are different. Flood fill begins from a seed and explores a component through a frontier such as a queue or stack. Hoshen–Kopelman moves through the raster once and resolves collisions among provisional labels.

Flood fill: natural when you want to grow one region from a known seed or traverse components explicitly.
Hoshen–Kopelman / two-pass labelling: natural when you need labels for every component in a raster or lattice and can exploit scan order.

Neither is universally superior. The right representation depends on whether the receiver needs one region, all regions, streamed statistics, low memory, easy parallelisation or a particular connectivity convention.

11. From Percolation to Image Analysis

Hoshen and Kopelman introduced their cluster-labelling method in 1976 for percolation problems, where one wants to identify connected occupied sites on a lattice without repeatedly storing or exploring full clusters. Later work extended the method to collect cluster statistics more directly.

The same core idea appears in modern connected-component labelling: scan locally, create provisional component names, record equivalences, and finally replace temporary names with canonical ones. That is why an algorithm born in statistical physics belongs equally in an image-processing and data-structures curriculum.

12. Production Libraries: Learn the Semantics Before the API

In Python, skimage.measure.label labels connected regions and lets the caller choose the connectivity. SciPy provides scipy.ndimage.label with a structuring element that determines which neighbours count as connected. These functions are usually preferable to handwritten teaching code in production.

But using a library safely still requires understanding the semantic choices: What is background? Are diagonal neighbours connected? What data type stores the result? Can the number of components exceed the output label range? Does the function operate in-place? Professional competence is knowing which API parameters correspond to the graph you intended to define.

13. Failure Modes Strong Learners Should Test

Wrong connectivity: diagonal contact silently changes the component count.
Forgetting canonicalisation: two provisional labels that were unioned may remain numerically different in the stored image.
Unioning labels without finding their roots: equivalence trees can become inconsistent or unnecessarily deep.
Boundary errors: the first row and first column need careful neighbour checks.
Label overflow: extremely fragmented images can create many provisional components.
Background confusion: treating zero as a valid component label can corrupt equivalence logic.
Double-counting statistics: accumulating component size against provisional labels before merges are resolved can produce incorrect totals unless statistics are reconciled.
Tiled processing gaps: components crossing tile boundaries need an extra equivalence step.
Periodic-boundary mistakes: percolation simulations may wrap around edges, unlike ordinary image labelling.
Dense assumptions: a method suitable for a dense raster may be wasteful for a sparse coordinate list.

14. Professional-Level Scaling

Large images and volumes motivate block-based, run-length, parallel and GPU connected-component algorithms. A common scaling pattern is to label local tiles independently, then reconcile equivalences for labels that meet across tile boundaries. This preserves the central Hoshen–Kopelman idea while changing the unit of work.

For three-dimensional data, neighbourhoods expand to 6-, 18- or 26-connectivity depending on which faces, edges and corners count. For scientific images, production validation should include component count, sizes, topology near borders, and representative pathological cases—not only a visually plausible output image.

15. How to Learn It Without Memorising It

A productive learning sequence is to make the state transitions visible before writing a full implementation. Predict the provisional label of the next pixel, run the scan, inspect the parent table, explain every union, and only then modify the neighbourhood rule.

Predict: label a 5×5 grid by hand.
Run: execute a reference implementation one pixel at a time.
Investigate: record the parent array whenever two provisional labels meet.
Modify: switch from 4-connectivity to 8-connectivity and predict which components merge.
Make: implement component sizes, bounding boxes or 3D labelling.
Validate: compare your result with scikit-image or SciPy across random grids and adversarial corner-touching patterns.

16. Learning Progression: Beginner to Professional

Beginner: understand components and hand-label a binary grid.
Intermediate: implement provisional labels plus Union–Find and prove the scan invariant.
Advanced: add 8-connectivity, statistics, 3D data and tiled boundary reconciliation.
Professional: benchmark memory bandwidth, choose library semantics deliberately, validate label ranges, parallelise safely, and test representative production distributions.

17. Practice Problems

Construct a 4×4 grid whose component count differs between 4- and 8-connectivity.
Find the smallest raster pattern that forces two provisional labels to be unioned.
Trace the parent array after every foreground pixel in a 6×6 example.
Remove path compression and measure the effect on a deliberately awkward Union–Find sequence.
Add component-size computation without double-counting labels that later merge.
Split an image into four tiles and design the boundary-equivalence pass.
Compare your labels with skimage.measure.label on 100 random binary images.

18. Sources and Further Reading

Final idea: Hoshen–Kopelman succeeds because it separates two jobs that beginners often mix together: naming what you know now, and reconciling names when later evidence shows they were the same thing all along. That separation—local progress plus deferred equivalence—is a powerful algorithmic pattern far beyond image labelling.

Small Group Tutorials