Semantic Segmentation

Formally, given an input image $I \in \mathbb{R}^{H \times W \times 3}$ and a fixed set of $C$ classes, semantic segmentation produces a label map $L \in \{1, \dots, C\}^{H \times W}$, assigning exactly one class to every pixel. This is dense, per-pixel multi-class classification, but with a crucial structural difference from ordinary classification: neighboring pixels are highly correlated, and the output has spatial coherence that a good model should exploit rather than predict each pixel independently. The task sits between two extremes. Image-level classification discards all spatial information — a single softmax over the whole image. Object detection keeps coarse spatial information (a bounding box) but not exact shape. Semantic segmentation demands full spatial fidelity: the output must trace the actual silhouette of the pedestrian, not a rectangle around them. Crucially, semantic segmentation is class-based, not instance-based: two adjacent cars are both labeled "car," with no distinction between car #1 and car #2. Separating instances is the job of instance segmentation (Mask R-CNN), a strict superset of this problem. The technical challenge that defines the field is a resolution/semantics tradeoff inherited from any Convolutional Neural Network classification backbone. Standard backbones (VGG, ResNet) repeatedly apply strided convolution or pooling, shrinking spatial resolution by a factor of 2 at each stage — after five stages, a $224\times224$ input becomes a $7\times7$ feature map, a 32× reduction. This is exactly what makes classification work: pooling builds translation-invariant, semantically rich features. But it destroys the fine spatial detail needed to draw a precise pixel boundary. An encoder-decoder network is the architectural answer: keep the classification backbone as an encoder, then attach a decoder that progressively upsamples the coarse feature map back to full resolution, while injecting spatial detail recovered from earlier, higher-resolution encoder layers via skip connections.

The pipeline has four conceptual stages: encoding, bottleneck, decoding with skip fusion, and per-pixel classification.

1. Encoder. A convolutional backbone (e.g., VGG-16, ResNet-50) processes the image through a sequence of stages, each ending in downsampling (stride-2 convolution or max-pooling). Stage $k$ produces a feature map $F_k$ of spatial size $H/2^k \times W/2^k$ with an increasing number of channels. These per-stage feature maps are cached — they will be needed later as skip connections. This is precisely the Fully Convolutional Networks trick: the backbone's final fully connected layers are replaced by $1\times1$ convolutions so the whole network stays convolutional and can process arbitrary input sizes.

2. Bottleneck. At the deepest stage the feature map is small in space (often $H/32 \times W/32$) but rich in channels (512–2048), encoding "what is present" with strong semantic invariance but almost no spatial precision.

3. Decoder with skip fusion. The decoder reverses the encoder, stage by stage. At each decoder stage:

• Upsample the current (coarse) feature map by a factor of 2, using bilinear interpolation, a learned transposed convolution, or max-unpooling (recording pooled indices from the encoder and scattering values back).
• Fuse it with the encoder feature map at the matching resolution from the cached skip connections — typically by channel-wise concatenation followed by a convolution, or by simple addition (as in FCN's "skip" variants).
• Apply one or more convolutions to blend the fused information and reduce channel dimension.

This is repeated until the feature map returns to the original input resolution $H \times W$.

4. Classification head. A final $1\times1$ convolution maps the fused feature map to $C$ channels — one logit map per class — followed by a per-pixel softmax. The predicted label at pixel $(i,j)$ is $\hat{L}(i,j) = \arg\max_c \, \text{softmax}(z(i,j))_c$. The network is trained end to end by minimizing the average per-pixel cross-entropy loss (often reweighted per class to counteract imbalance):

where $p_c(i,j)$ is the predicted softmax probability of class $c$ at pixel $(i,j)$, $L(i,j)$ is the ground-truth label, and $w_c$ is an optional class weight (e.g., inverse class frequency). ```

# ENCODER-DECODER SEMANTIC SEGMENTATION — forward pass and training step function FORWARD(image, encoder_stages, decoder_stages, num_classes): skips = [] # cache for skip connections x = image for stage in encoder_stages: x = stage.convolve(x) # conv + norm + activation, several times skips.append(x) # save BEFORE downsampling x = stage.downsample(x) # stride-2 conv or max-pool, halves H,W bottleneck = x # coarsest, most semantic feature map x = bottleneck for i, dstage in enumerate(decoder_stages): x = dstage.upsample(x) # double H,W (bilinear / transpose conv / unpool) skip = skips[len(skips) - 1 - i] # matching-resolution encoder feature x = concatenate_channels(x, skip) # fuse fine spatial detail with coarse semantics x = dstage.convolve(x) # blend + reduce channels logits = conv1x1(x, out_channels = num_classes) # per-pixel class scores return logits # shape: H x W x C function TRAIN_STEP(image, ground_truth_labels, class_weights, model): logits = FORWARD(image, model.encoder, model.decoder, model.num_classes) probs = softmax_over_channels(logits) # per-pixel softmax loss = 0 for i in range(H): for j in range(W): c = ground_truth_labels[i][j] if c == IGNORE_LABEL: # e.g., unlabeled border pixels continue loss += class_weights[c] (-log(probs[i][j][c])) loss = loss / count_valid_pixels(ground_truth_labels) gradients = backpropagate(loss, model.parameters) model.parameters = optimizer_update(model.parameters, gradients) return loss function PREDICT(image, model): logits = FORWARD(image, model.encoder, model.decoder, model.num_classes) label_map = argmax_over_channels(logits) # H x W, each entry in {1..C} return label_map ``` Two implementation details matter for correctness. First, the `IGNORE_LABEL` check handles pixels with no ground-truth annotation (common near image borders or ambiguous regions) — omitting this handling silently corrupts the loss with garbage labels. Second, `skips[len(skips) - 1 - i]` must pair the $i$-th decoder stage with the encoder stage of identical* spatial resolution — an off-by-one here silently fuses mismatched feature maps and is a common, hard-to-detect bug (shapes still "work" if the network is symmetric, but semantics are wrong).

Time complexity. Let the input be $H \times W$ pixels with $D$ downsampling stages (typically $D = 5$, giving a 32× reduction), and let each stage use convolutions with $O(k^2 c_{in} c_{out})$ work per output pixel, where $k$ is kernel size and $c_{in}, c_{out}$ are channel counts. The total FLOPs for the encoder are dominated by the early, high-resolution, low-channel stages and the late, low-resolution, high-channel stages roughly balancing out — a hallmark design goal of CNN backbones (halving resolution while doubling channels keeps per-stage compute roughly constant). Overall forward-pass cost is

which is linear in the number of input pixels $HW$ for a fixed network depth and channel schedule, i.e. $O(HW)$ per forward pass at fixed architecture (constants depend on channel widths and kernel sizes, not on $H, W$ growth). The decoder mirrors this cost since it processes the same sequence of resolutions in reverse. Skip-connection concatenation adds only a constant-factor overhead (more channels into the following convolution), not a new asymptotic term.

Space complexity. Memory is dominated by activation storage needed for backpropagation: every cached skip-connection feature map $F_k$ must be retained until its matching decoder stage consumes it, plus all intermediate activations for the backward pass. This gives $O(HW \cdot C_{\max})$ activation memory in the worst case (bounded by the sum over stages of resolution × channel count), which is why segmentation networks are markedly more memory-hungry than classifiers of the same backbone — classifiers can discard early activations sooner, whereas segmentation decoders need them held until late in the forward pass. This is the practical reason segmentation training uses small batch sizes or gradient checkpointing on large images.

Why encoder-decoder with skips is "correct." The core justification is information-theoretic: after $D$ stages of pooling with factor 2, a feature vector at the bottleneck has receptive field covering a $2^D \times 2^D$ patch of the input, giving it the context needed to know what class is present, but the bottleneck map has only $\left(\frac{1}{2^D}\right)^2$ as many spatial locations as the input — most fine positional information (exact edges, thin structures) is provably lost through lossy pooling, since max-pooling and strided convolution are non-invertible many-to-one maps. Naively upsampling the bottleneck alone (bilinear interpolation with no skip fusion, as in the crudest FCN variant) can only produce a blurred re-expansion of already-lost detail — it cannot recover information that pooling discarded. Skip connections sidestep this fundamentally, not just empirically: they route the still-high-resolution activations from shallow layers, computed before the destructive pooling occurred, directly to the decoder. The decoder's final layer therefore has access to both the deep semantic signal (via the upsampled path) and the undestroyed spatial signal (via the skip path), and a learned fusion (concatenation + convolution) lets the network combine them adaptively rather than being forced to average or discard one. This is why FCN-32s (no skips) produces coarse, blobby segmentations while FCN-8s (skips from three resolutions) produces visibly sharper boundaries at the same parameter budget — an empirical result directly explained by this information-flow argument.

Metric correctness — why mIoU, not accuracy. Raw pixel accuracy is misleading under class imbalance: in a street scene, "sky" and "road" may cover 60% of pixels while "pedestrian" covers 0.3%; a model that never predicts "pedestrian" can still score over 90% pixel accuracy. Intersection-over-Union for class $c$ is defined per image (or aggregated over a dataset) as

where $TP_c$, $FP_c$, $FN_c$ count pixels correctly predicted as $c$, incorrectly predicted as $c$, and incorrectly predicted as something else when truly $c$, respectively. Mean IoU averages this per class, not per pixel:

Because each class contributes equally to the average regardless of its pixel frequency, a model that ignores rare classes is penalized directly — its IoU for those classes is 0 or near-0, dragging the mean down regardless of how well it does on frequent classes. This makes mIoU the honest metric for imbalanced, safety-critical segmentation tasks, at the cost of being harder to optimize for directly (IoU is not smoothly differentiable, so training still typically uses cross-entropy or a differentiable surrogate like soft-Dice loss, and mIoU is used only for evaluation).

Consider a tiny $4 \times 4$ image with three classes: `0 = background`, `1 = cat`, `2 = dog`. Ground truth and a hypothetical model prediction:

Ground truth $L$: ``` 0 0 1 1 0 1 1 1 2 2 0 0 2 2 0 0 ```

Predicted $\hat{L}$: ``` 0 0 1 1 0 1 1 2 2 2 0 0 2 2 2 0 ``` Two pixels differ from ground truth: $(1,3)$ true `1`, predicted `2`; $(3,2)$ true `0`, predicted `2`. Pixel accuracy is $14/16 = 87.5\%$ — looks good. Now compute per-class confusion counts.

Verification by direct count: background truth pixels are at positions (0,0),(0,1),(1,0),(2,2),(2,3),(3,3) — 6 pixels; all predicted correctly except (3,2) is falsely predicted `2` where truth is `0`, but (3,2)'s true label is `0` and predicted `2`, so that's a false negative for class 0 and a false positive for class 2. That gives class 0: TP = 5 (all true-0 pixels except the one missed), FN = 1, FP = 0 (no other class was predicted as 0 incorrectly) ✓. Class 2 truth pixels: (2,0),(2,1),(3,0),(3,1) — 4 pixels, all predicted correctly (TP=4)... but the table above lists TP=5 for class 2, which must also include the pixel at (3,2) that was predicted as class 2 but is truly class 0 — that's a false positive, not a true positive. Correcting: class 2 TP = 4 (correctly predicted dog pixels), FP = 2 (the two extra pixels wrongly predicted as dog: (1,3) and (3,2)), FN = 0.

Corrected table:

Notice mIoU (0.767) is markedly lower than pixel accuracy (0.875) even in this tiny, near-balanced example — the two boundary-pixel errors happen to touch every class's IoU, and mIoU punishes the "dog" class disproportionately because the errors are a larger fraction of its already-small pixel count (2 wrong predictions out of only 6 total dog-related pixels vs. background's 1 wrong out of 6). This small trace demonstrates precisely why mIoU is preferred: it is sensitive to per-class quality, not swamped by whichever class covers the most area.

The encoder-decoder segmentation paradigm grew directly out of the shift from patch-based classifiers to fully convolutional, end-to-end trainable networks for dense prediction.

Semantic segmentation underlies the perception stack of autonomous driving systems, where dense road/lane/obstacle labeling feeds directly into path planning. Medical imaging platforms use segmentation networks (descendants of U-Net) to delineate organs and tumors in MRI and CT scans for diagnosis and radiotherapy dose planning. Satellite and aerial imagery pipelines use segmentation to map land use, deforestation, and crop boundaries at continental scale. Photo and video editing tools (background removal, portrait mode blur, virtual backgrounds in video calls) rely on lightweight real-time segmentation networks running on-device. Robotics systems use segmentation for scene understanding, grasp planning, and navigable-surface estimation. The architecture also underlies panoptic segmentation systems that unify semantic and instance segmentation, and it forms the foundation that instance segmentation methods like Mask R-CNN build directly on top of, by adding a mask-prediction branch to a detection pipeline that otherwise reuses the same convolutional feature pyramids.

Ask the tutor: How would dilated (atrous) convolutions change this architecture if we wanted to avoid downsampling resolution at all?