Application — Counting Objects With and Without Holes: 20-Bio-B4 Robotics, December 2014, Q6

Question 6: Application — Counting Objects With and Without Holes (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A binary image $I$ (1 = object, 0 = background/hole) corrupted by salt-and-pepper noise, containing an unknown number of non-touching, arbitrarily-shaped objects.

Find. An algorithm that correctly reports how many objects have at least one internal hole and how many do not, ignoring noise.

Approach. Denoise first, label foreground objects, then determine which background components are truly enclosed (holes) rather than reachable from the image border.

Proposed hole-counting pipeline: denoise, label foreground objects, separately label background components via a border flood-fill, then classify.

Denoise. Apply a 3×3 median filter to $I$ (impulsive salt-and-pepper noise is exactly the case the median filter is designed for: an isolated flipped pixel is always outvoted by its 8 unaffected neighbours, and, unlike a mean/linear filter, the median does not blur true object boundaries). Follow with a small morphological area-opening (remove any surviving foreground blob below a minimum-area threshold $A_{\min}$, set well below the smallest expected true object) as a safety net against any noise the median filter did not fully remove.
Label foreground objects. Run 8-connected connected-component labelling on the "1" pixels of the cleaned image, producing labels $O_1, O_2, \dots, O_K$ (one per true object, since objects are stated not to touch).
Label background components with a border flood-fill. Run 4-connected connected-component labelling on the "0" pixels. (4-connectivity is deliberately used for the background against 8-connectivity for the foreground — using the same connectivity for both would let a diagonal chain of foreground pixels and a diagonal chain of background pixels cross without ever meeting, the classic connectivity paradox.) Any background component that touches the image border is the outer background; every other background component is fully enclosed.
Classify. For every enclosed background component (a candidate hole) that survives the same area threshold $A_{\min}$ (filtering out any residual pepper-noise speck too small to be a genuine hole), find the foreground label(s) immediately adjacent to its boundary pixels. Since objects do not touch, exactly one object label borders each true hole; mark that object as "has a hole".
Count. Report the number of objects with $\ge 1$ associated hole, and the number with zero.

function countHoles(I):
    I_clean = medianFilter3x3(I)
    I_clean = areaOpen(I_clean, A_min)          // drop tiny leftover foreground specks

    [fgLabels, K]  = connectedComponents(I_clean, value=1, connectivity=8)
    [bgLabels, M]  = connectedComponents(I_clean, value=0, connectivity=4)

    borderLabels = { bgLabels(y,x) : (y,x) on the image border, bgLabels(y,x) != 0 }

    hasHole = array of K false values
    for each background label L in 1..M:
        if L in borderLabels: continue           // reachable from outside -> not a hole
        pixels = pixels with bgLabels == L
        if size(pixels) < A_min: continue         // residual pepper noise, not a real hole
        neighbourObjects = { fgLabels(y2,x2) : (y2,x2) is 4-adjacent to some pixel in pixels,
                              fgLabels(y2,x2) != 0 }
        for k in neighbourObjects: hasHole[k] = true

    nWithHoles    = count(hasHole == true)
    nWithoutHoles = K - nWithHoles
    return nWithHoles, nWithoutHoles

Step	Purpose	Key design choice
Median filter + area-open	Remove salt-and-pepper noise before it can be mistaken for objects or holes	Median (not mean) filter: preserves edges, rejects impulsive noise
Foreground labelling	Identify each true object	8-connectivity
Background labelling + border flood-fill	Distinguish outer background from true enclosed holes	4-connectivity (paired with 8-connectivity foreground to avoid the connectivity paradox)
Area-threshold on holes	Reject any leftover 1-pixel pepper defect that survived filtering	Same $A_{\min}$ philosophy as the foreground clean-up

Check: assumes a minimum true object/hole area $A_{\min}$ can be chosen that is larger than any residual noise blob but smaller than the smallest genuine object or hole in the image; this holds for typical salt-and-pepper (single-pixel) corruption but would need re-tuning if the noise came in larger clusters.

The pipeline above (median filter, 8-connected foreground labelling, 4-connected background labelling with a border flood-fill, area-thresholded hole classification) is robust to isolated salt-and-pepper noise, whereas running the same classification on the raw, un-denoised image gives the wrong count, so the denoising stage is not optional.

Concept & Theory: Topological Object/Hole Counting via Connected Components

Topic: connected-component labelling, the foreground/background connectivity paradox, and hole detection via a border-reachability flood-fill.
Key relations: Euler number $E = (\text{number of objects}) - (\text{number of holes})$ ties this whole question to a single scalar topological invariant; 8-connected foreground must be paired with 4-connected background (or vice versa) to avoid the connectivity paradox.
Why this works: a hole is, by definition, a background region that cannot be reached from outside the image without crossing foreground — which is exactly what a border-seeded flood-fill on the background pixels detects, with no need to reason about the enclosing object's shape at all.
Common pitfall: using the same connectivity (typically 8) for both foreground and background, which for certain diagonal checkerboard-like configurations makes an object appear simultaneously connected to, and disconnected from, the background — the connectivity paradox — and skipping the area threshold on candidate holes, which lets a single surviving pepper-noise pixel masquerade as a hole.
Source: Gonzalez & Woods, Digital Image Processing, ch. 2 (connectivity, the connectivity paradox) and ch. 9 (morphological image processing, region filling, the Euler number).

Question 6 of 6: Application — Counting Objects With and Without Holes

Question 6: Application — Counting Objects With and Without Holes (20 marks)