Segmentation

The previous lesson said where the object is with a box, and compared that box’s intersection over union with the figure of a fixed box placed in the middle of the image on the same metric; the window that also searches size got a mean overlap of 0.9076. One thing the box does not say is left: every pixel inside the rectangle that was found counts as the object. A box is a coarse answer made of four numbers; the answer to the question “which pixels” is as many decisions as there are pixels.

In the fiction of this lesson the objects are rectangular blocks, so a perfect box already gives a perfect mask. In this respect the fiction is in favor of the box, and the lesson still shows two things. The first is that when one goes down to the pixel level, the domain baseline changes and comes out surprisingly high. The second is that however well decisions are made at the pixel level, where two objects touch, semantic segmentation cannot separate the two; this is not an accuracy problem but a limit that has to do with the form of the output.

• CV31. The image is fiction. The 12x12 coverage grid is here a small gray-level image; the grid comes from the Visualization, Reporting and Analysis at Scale course and was turned into a learning input in the Deep Learning course. Seed 20260218.
• CV32. The objects are fiction rectangular blocks. Height and width are between 2 and 4, the block pixels sit at a higher gray level than the background, and the noise is produced by the sum of three uniform numbers; the distributions of the two levels overlap at the tails.
• CV33. An image contains one, two, or three blocks. The second and third blocks rest against the edge of the previous one with probability 0.40; if they do not, at least one cell of gap is left between them.
• CV34. There are two labels. The object mask is 0/1 for every pixel and is the target of semantic segmentation; the instance mask writes the block number into every pixel and is the target of instance segmentation.
• CV35. The split is 80/120 and is fixed in this image set. The training set is small on purpose.
• CV36. The domain baseline is assigning every pixel to the dominant class. The dominant class is the background; the reason for the choice is the pixel ratio, and that ratio is printed.
• CV37. Two metrics are read side by side. Pixel accuracy (bigger is better) counts all the pixels; the intersection over union of the object class (intersection divided by union, bigger is better) counts only the object pixels. Intersection over union was defined on boxes in the third lesson; here it is read on sets of pixels.
• CV38. The model is linear and fitted by least squares; the decision threshold is fixed at 0.5. That the threshold choice moves the number was measured in the Supervised Learning course and is not repeated. No library is called.
• CV39. The instance count is read with two procedures: connected components, and rectangle decomposition with the prior “objects are rectangles.”

The Fiction Image and the Domain Baseline

# image.py — MODEL: The image set is FICTION: the 12x12 coverage grid of the Visualization,
# Reporting and Analysis at Scale course and the Deep Learning course is here a small
# gray-level image, and fiction rectangular blocks are placed on it. Seed 20260218.
SEED, M32, SIZE = 20260218, 0xFFFFFFFF, 12
BACKGROUND, BLOCK, NOISE = 0.30, 0.74, 0.30


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


def intersects(a, b, gap):
    return not (a[0] + a[2] + gap <= b[0] or b[0] + b[2] + gap <= a[0]
                or a[1] + a[3] + gap <= b[1] or b[1] + b[3] + gap <= a[1])


def image(no):
    """One coverage frame: gray levels, object mask, instance mask, block count."""
    r = rng(SEED + 400000 + no)
    blocks = []
    for _ in range(1 + pick(r(), [0.24, 0.46, 0.30])):
        h, w = 2 + int(r() * 3), 2 + int(r() * 3)
        adjacent = bool(blocks) and r() < 0.40
        for _ in range(24):
            if adjacent:                      # resting against the edge of the previous block
                a, side = blocks[int(r() * len(blocks))], int(r() * 4)
                sy = a[0] - h if side == 0 else a[0] + a[2] if side == 1 else a[0]
                sx = a[1] if side < 2 else a[1] - w if side == 2 else a[1] + a[3]
            else:
                sy, sx = int(r() * (SIZE - h + 1)), int(r() * (SIZE - w + 1))
            new = (sy, sx, h, w)
            if not (0 <= sy <= SIZE - h and 0 <= sx <= SIZE - w):
                continue
            if any(intersects(new, b, 0 if adjacent else 1) for b in blocks):
                continue
            blocks.append(new)
            break
    g = [[BACKGROUND + (r() + r() + r() - 1.5) * NOISE for _ in range(SIZE)] for _ in range(SIZE)]
    instance = [[0] * SIZE for _ in range(SIZE)]
    for index, (sy, sx, h, w) in enumerate(blocks, 1):
        for i in range(sy, sy + h):
            for j in range(sx, sx + w):
                g[i][j] += BLOCK - BACKGROUND
                instance[i][j] = index
    mask = [[1 if instance[i][j] else 0 for j in range(SIZE)] for i in range(SIZE)]
    return g, mask, instance, len(blocks)


DATA = [image(i) for i in range(200)]
TRAIN, TEST = DATA[:80], DATA[80:]
PIXELS = len(TEST) * SIZE * SIZE
OBJECT = sum(sum(sum(s) for s in m) for _, m, _, _ in TEST)
print(f"fiction: 200 images {SIZE}x{SIZE}, train {len(TRAIN)}, test {len(TEST)}; "
      f"{OBJECT} object pixels / {PIXELS} in the test set")
print(f"baseline - assigning every pixel to the dominant class (background): "
      f"pixel accuracy {(PIXELS - OBJECT) / PIXELS:.4f}, object intersection over union 0.0000")
g, _, o, k = DATA[97]
for i in range(SIZE):
    print("   " + "".join(str(min(9, max(0, int(g[i][j] * 10)))) for j in range(SIZE))
          + "    " + "".join(".12345"[o[i][j]] for j in range(SIZE)))
print(f"   gray level on the left, instance number on the right; this frame has {k} blocks")

fiction: 200 images 12x12, train 80, test 120; 2193 object pixels / 17280 in the test set
baseline - assigning every pixel to the dominant class (background): pixel accuracy 0.8731, object intersection over union 0.0000
   102330223332    ............
   222322797803    ......2222..
   333006674822    ......2222..
   410235775913    ......2222..
   426354786802    ......2222..
   045333776830    ......1111..
   302211787842    ......1111..
   344130859630    ......1111..
   234251999753    ......1111..
   231130223333    ............
   432153222132    ............
   332423044303    ............
   gray level on the left, instance number on the right; this frame has 2 blocks

The first number of the lesson is in the baseline row. 2,193 of the 17,280 pixels in the test set are object; the ratio is 0.1269. The procedure that learns nothing and writes “background” into every pixel therefore gets 0.8731 in pixel accuracy. This number is not a success but the class ratio itself: because the object pixels are the minority, missing them entirely costs little.

The number of the same output on the second metric is 0.0000. Intersection over union counts only the object class; since the intersection is empty, the ratio is zero. A single output gives 0.8731 and 0.0000 on two metrics. Here the choice of metric is not a preference but the decision that determines what the number means.

The printed frame also shows the second question of the course. The instance map on the right says there are two separate blocks between the sixth and ninth columns; in the gray levels on the left there is a single bright rectangle. Where the two blocks touch, there is no boundary at all between the pixel values.

The Same Model, Two Representations

def window(g, i, j):
    return [g[min(SIZE - 1, max(0, a))][min(SIZE - 1, max(0, b))]
            for a in (i - 1, i, i + 1) for b in (j - 1, j, j + 1)]


def features(g, i, j, wide):
    return [1.0] + (window(g, i, j) if wide else [g[i][j]])


def solve(A, b):
    n, x = len(b), [0.0] * len(b)
    M = [A[i][:] + [b[i]] for i in range(n)]
    for k in range(n):
        p = max(range(k, n), key=lambda r: abs(M[r][k]))
        M[k], M[p] = M[p], M[k]
        for r in range(k + 1, n):
            f = M[r][k] / M[k][k]
            for c in range(k, n + 1):
                M[r][c] -= f * M[k][c]
    for k in range(n - 1, -1, -1):
        x[k] = (M[k][n] - sum(M[k][c] * x[c] for c in range(k + 1, n))) / M[k][k]
    return x


def train_model(dataset, wide):
    """Per-pixel linear decision function; fitted by least squares. MODEL."""
    d = 10 if wide else 2
    A, b = [[0.0] * d for _ in range(d)], [0.0] * d
    for g, m, _, _ in dataset:
        for i in range(SIZE):
            for j in range(SIZE):
                x, y = features(g, i, j, wide), float(m[i][j])
                for p in range(d):
                    b[p] += x[p] * y
                    for q in range(p, d):
                        A[p][q] += x[p] * x[q]
    for p in range(d):
        for q in range(p):
            A[p][q] = A[q][p]
    return solve(A, b)


def predict(w, g, wide):
    return [[1 if sum(a * c for a, c in zip(w, features(g, i, j, wide))) >= 0.5 else 0
             for j in range(SIZE)] for i in range(SIZE)]


def measure(dataset, w, wide):
    correct = inter = union = 0
    for g, m, _, _ in dataset:
        k = predict(w, g, wide) if w else [[0] * SIZE for _ in range(SIZE)]
        for i in range(SIZE):
            for j in range(SIZE):
                correct += k[i][j] == m[i][j]
                inter += k[i][j] and m[i][j]
                union += k[i][j] or m[i][j]
    return correct / (len(dataset) * SIZE * SIZE), inter / max(1, union)


W1, W9 = train_model(TRAIN, False), train_model(TRAIN, True)
print(f"{'representation':<25}{'pixel accuracy':>16}{'intersection over union':>25}")
for name, w, wide in (("baseline (all background)", None, False),
                      ("single pixel value", W1, False),
                      ("3x3 neighborhood window", W9, True)):
    acc, iou = measure(TEST, w, wide)
    print(f"{name:<25}{acc:>16.4f}{iou:>25.4f}")

representation             pixel accuracy  intersection over union
baseline (all background)          0.8731                   0.0000
single pixel value                 0.9540                   0.6412
3x3 neighborhood window            0.9851                   0.8843

The only difference between the two rows is the representation. The model family is the same (a linear decision function), the fitting procedure is the same (least squares), the threshold is the same (0.5), the training set is the same. What changes is what the input is: a single number, or the pixel itself together with its eight neighbors.

The difference shows up in two sizes on the two metrics. Pixel accuracy goes from 0.9540 to 0.9851, a movement of 0.0311. Intersection over union goes from 0.6412 to 0.8843, a movement of 0.2431. What the second representation adds is the same thing; the first metric shows an eighth of it, because 87% of the accuracy denominator is background pixels anyway, and both representations hardly ever err on a background pixel.

Read against the baseline, the gain of the 3x3 window in pixel accuracy is 0.1120. When 0.8731 is not written next to this number, the sentence “98.5% accuracy” can be made, and that sentence hides that the procedure that learns nothing gets 0.8731. The rule of the course is paid once more here: a number whose domain baseline is not written counts as unmeasured.

The answer to the question of where the contribution of the neighborhood window comes from is in the noise. A single pixel value errs on its own because the distributions of the two gray levels overlap at the tails; the mean of the neighbors shrinks the same noise, and a lone bright pixel in the background is suppressed by its surroundings. This is something different from the weight sharing of the convolution layer measured in the Deep Learning course: here there is a single small set of learned weights, and the gain comes from the coverage of the input.

Where Semantic Segmentation Stops

def connected_components(mask):
    seen, found = [[0] * SIZE for _ in range(SIZE)], []
    for i in range(SIZE):
        for j in range(SIZE):
            if mask[i][j] and not seen[i][j]:
                seen[i][j], stack, cells = 1, [(i, j)], []
                while stack:
                    a, b = stack.pop()
                    cells.append((a, b))
                    for da, db in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        p, q = a + da, b + db
                        if 0 <= p < SIZE and 0 <= q < SIZE and mask[p][q] and not seen[p][q]:
                            seen[p][q] = 1
                            stack.append((p, q))
                found.append(cells)
    return found


def rectangle_count(cells):
    """With the prior that objects are rectangles, how many rectangles a component splits into."""
    counts = []
    for axis in (0, 1):
        profile, pieces, previous = {}, 0, None
        for a, b in cells:
            profile.setdefault(a if axis == 0 else b, set()).add(b if axis == 0 else a)
        for k in sorted(profile):
            if previous is None or k != previous + 1 or profile[k] != profile[previous]:
                pieces += 1
            previous = k
        counts.append(pieces)
    return min(counts)


def tally(dataset, w):
    adjacent = component = rectangle = 0
    for g, m, _, k in dataset:
        mask = predict(w, g, True) if w else m
        b = connected_components(mask)
        adjacent += len(connected_components(m)) < k
        component += len(b) != k
        rectangle += sum(rectangle_count(h) for h in b) != k
    return adjacent, component, rectangle


for name, w in (("ground-truth mask", None), ("3x3 prediction", W9)):
    adjacent, component, rectangle = tally(TEST, w)
    print(f"{name:<18} carrying adjacent blocks {adjacent:>3}/{len(TEST)} images; "
          f"instance count wrong: by counting components {component:>3}, "
          f"by rectangle decomposition {rectangle:>3}")

ground-truth mask  carrying adjacent blocks  45/120 images; instance count wrong: by counting components  45, by rectangle decomposition  21
3x3 prediction     carrying adjacent blocks  45/120 images; instance count wrong: by counting components  46, by rectangle decomposition  79

The first row is the ceiling of semantic segmentation, and this ceiling is measured with a perfect mask. 45 of the one hundred twenty test images carry adjacent blocks; the procedure that counts connected components gives the instance count wrong in exactly those 45 images and right in the remaining 75. This is the ratio even when there is no error in the mask at all, because the error is not in the mask but in the form of the question: semantic segmentation writes one class into every pixel, and the pixels of two adjacent blocks are in the same class.

The second procedure adds a prior about the shape of the object — the blocks are rectangles — and counts into at least how many rectangles the component has to be split. On the perfect mask this brings the 45 errors down to 21: in 24 images the adjacency can be read from the non-rectangular shape of the component. In the remaining 21 images the union of the two blocks is itself a rectangle; the frame printed in the previous section is exactly this, and no shape prior can separate the two blocks there.

The third number shows the price of the prior. On the predicted mask the error of the procedure that counts components rises from 45 to 46, which is to say the mask error does almost no harm. Rectangle decomposition, on the other hand, jumps from 21 to 79: a single missing or extra pixel in the prediction takes the component out of being a rectangle, and the procedure splits it into two or three pieces. The prior wins on perfect input and loses on noisy input; and this happens on a mask whose intersection over union is 0.8843.

This is where semantic and instance segmentation part. The output of semantic segmentation is one class per pixel, and a good pixel accuracy never brings this separation; the output of instance segmentation is sets of pixels, and for this either a separate output per object or outside information such as shape is needed. The metric parts as well: while pixel accuracy and intersection over union stay near the ceiling in 45 images, the instance count is wrong.

Summary

• Because 2,193 of the 17,280 pixels in the test set are object, the baseline that assigns every pixel to the dominant class gets 0.8731 in pixel accuracy; the object intersection over union of the same output is 0.0000.
• The same linear model gives 0.9540 and 0.6412 with a single pixel value and 0.9851 and 0.8843 with a 3x3 neighborhood window; the difference comes not from the model family but from the representation, and it shows as 0.0311 and 0.2431 on the two metrics.
• 45 of the one hundred twenty images carry adjacent blocks; even with a perfect mask, counting connected components gets the instance count wrong in these 45 images, because the limit is not in the mask but in the form of the question.
• The prior that objects are rectangles brings the error down to 21 on the perfect mask and raises it to 79 on the predicted mask; the prior makes one pay on noisy input.

Next Step

In four lessons the image was a single frame, and every decision was read from that frame itself. A coverage network produces frames not one by one but one after another: successive readings of the same region form a sequence, and the neighborhood of the sequence is not in space but in time. In this lesson the neighborhood window moved pixel accuracy by 0.0311 and intersection over union by 0.2431; which number moves when the window opens into time. The next lesson counts the inconsistency over time of the decision given per frame, and shows what the best number is that a procedure that learns nothing can get on that metric.