EP08_05 — 🟡 Connected Component Labeling: Instance Segmentation

8.14.5 EP08_05 🟡 Connected Component Labeling: Instance Segmentation

The classic segmentation example in this chapter separated coin “instances” simply by their spatial disconnection in the binary mask resulting from Otsu’s thresholding. That final step—labeling each connected component with an instance identifier—is exactly what you have been tasked with implementing here, from scratch, on an already prepared binary mask (0 = background, 1 = object), as if it were a manual reimplementation of cv2.connectedComponents.

This exercise also exposes, in a very concrete way, the limitation discussed in the chapter: the result depends entirely on how “neighborhood” between pixels is defined—and, as you will see in the second example, two diagonal pixels can be considered the same instance or different instances, depending solely on the chosen connectivity, not on any semantic notion of an object.

8.14.5.1 📋 Implementation Guidelines

Input: Read the dimensions \(H \times W\) of the binary mask and its \(H \times W\) values (\(0\) or \(1\)).
Connectivity: Read the integer \(c \in \{4, 8\}\). Under 4-connectivity, the neighbors of \((i,j)\) are \((i{-}1,j)\), \((i{+}1,j)\), \((i,j{-}1)\), and \((i,j{+}1)\). Under 8-connectivity, the four diagonals are added: \((i{-}1,j{-}1)\), \((i{-}1,j{+}1)\), \((i{+}1,j{-}1)\), and \((i{+}1,j{+}1)\).
Component discovery: Traversing the mask in a row-by-row sweep, from left to right and top to bottom, whenever a pixel with value \(1\) that is still unlabeled is found, it starts a new component: assign to it the next available label (the first discovered component receives label \(1\), the second label \(2\), and so on) and propagate this same label to all pixels with value \(1\) reachable from it through a chain of neighbors (according to the chosen connectivity)—by breadth-first search, depth-first search, or union-find, at your discretion.
Background pixels: remain with label \(0\) and do not belong to any instance.
Output: First, print the complete label map—\(H\) lines with \(W\) integers each. Then, for each label \(\ell\) from \(1\) to \(K\) (in discovery order), print Instance l: A pixels, where \(A\) is the number of pixels with that label. Finally, print Total instances: K.

8.14.5.2 📌 Computational Constraints

Discovery order = sweep order: labels are numbered in the order in which each new component is found by the row-wise sweep, not by size or position.
Explicit connectivity: two pixels with value \(1\) belong to the same instance only if there exists a chain of neighbors according to \(c\) linking one to the other—do not mistakenly use the opposite connectivity.
Pure binary mask: all input values are exactly \(0\) or \(1\).

8.14.5.3 🧠 Theoretical Background

Element	Role in classic instance segmentation
Thresholding (Otsu, Chap. 4)	Previous stage that produces the binary mask from the intensity image
Connected component	Each instance is defined solely by the spatial connectivity of object pixels, without any notion of shape, class, or appearance
4- vs. 8-connectivity	Parameter that alters the result: under 8-connectivity, two blobs joined only diagonally become a single instance
Central limitation	The technique merges instances that touch or overlap (even if they are clearly distinct objects), because there is no notion of “object”—only of “connected region”

8.14.5.4 📦 Input and Output Specification (VPL)

Input:

Line 1: Integers \(H\) and \(W\).
Next \(H\) lines: \(W\) integers (\(0\) or \(1\)) each.
Last line: Integer \(c\) (\(4\) or \(8\)).

Output:

\(H\) lines with \(W\) integers each (the label map).
One line per instance, in discovery order: Instance l: A pixels.
Last line: Total instances: K.

8.14.5.5 📌 Examples

Input	Output	Observation
6 6 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 8	0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 0 2 2 Instance 1: 4 pixels Instance 2: 4 pixels Total instances: 2	Two clearly separated \(2\times2\) blocks: the result is the same under 4- or 8-connectivity.
2 2 1 0 0 1 8	1 0 0 1 Instance 1: 2 pixels Total instances: 1	Under 8-connectivity, the two diagonal pixels belong to the same instance. Repeat this example with \(c=4\): the result changes to 2 instances of 1 pixel each—purely due to the change in connectivity, with no difference in the mask.

🎮 Simulator EP08_05: Connected Components (4 vs. 8 Connectivity) Same Mask → Different Labels

The same mask (two diagonal pixels) — toggle the connectivity and observe the number of instances and the colors of the labels change.

–

Figure 8.19: Simulator EP08_05: Connected Components Labeling — 4 vs. 8 Connectivity

%%writefile EP08_05.py
# Python code

Overwriting EP08_05.py

TestSuite("EP08_05.py").run()

✔️ EP08_05.cases already exists in casos/
📋 6 case(s) loaded from casos/EP08_05.cases

🔍 Testing Python: EP08_05.py
⚠️ EP08_05.py: Empty file (fewer than 3 lines). Tests skipped.