Fully Convolutional Networks

A standard image classifier — say a stack of convolutions followed by flattening and one or more fully connected (FC) layers — commits to a fixed input size and produces a single fixed-length output vector. The FC layer computes each output as a weighted sum over every spatial location and channel of its input, which is equivalent to a convolution whose kernel is exactly as large as the input feature map (stride 1, valid padding, no spatial extent left afterward). This is not an approximation; it is an algebraic identity. If the FC weight matrix is reshaped into a kernel tensor of shape (out_channels, in_channels, H, W) matching the input feature map's spatial size, the convolution and the matrix multiply compute the same numbers. Once this substitution is made throughout the network, every layer is a convolution, and the whole network becomes a composition of local, translation-equivariant operators. Feeding in a larger image than the one used during training no longer produces an error — it produces a larger output map, where each output position corresponds to a spatial neighborhood (a receptive field) in the input. A network trained as a 224×224 classifier, when made fully convolutional and given a 500×500 image, outputs a coarse grid of class scores, one score-vector per receptive-field location, rather than one score-vector for the whole image. This is a heatmap, not a label. Because pooling and strided convolutions are used to build hierarchical features cheaply, the resulting output map is much coarser than the input (e.g., 1/32 the resolution for a network with five stride-2 stages). To produce a dense, pixel-aligned prediction, an FCN adds an explicit upsampling stage — via bilinear interpolation, transposed convolution (sometimes loosely called "deconvolution"), or sub-pixel convolution — that maps the coarse heatmap back to the input resolution. Because coarse features lose fine spatial detail (object boundaries, thin structures), FCNs additionally use skip connections: they fuse the coarse, semantically rich prediction from deep layers with finer-grained, higher-resolution features from shallow layers, recovering detail that pure upsampling cannot invent.

The FCN construction has three logically separate stages: convolutionalization of a classifier backbone, upsampling of the resulting coarse output, and skip fusion to sharpen the output. Below is the mechanism as originally formulated (FCN-32s, FCN-16s, FCN-8s), which generalizes directly to later encoder-decoder segmentation networks.

Step 1 — Convolutionalize the backbone. Take a pretrained classifier (e.g., VGG-16): a sequence of conv/pool blocks followed by FC6, FC7, FC8 (the classifier head). Replace FC6 (which multiplies over a 7×7×512 feature map) with a 7×7×512 → 4096 convolution; replace FC7 (4096→4096, effectively over 1×1 spatial extent) with a 1×1 convolution; replace FC8 (4096 → 1000 classes) with a 1×1 convolution mapping to the number of segmentation classes instead. All the pretrained convolutional weights transfer unchanged; the reshaped FC weights transfer unchanged too, since the identity above is exact.

Step 2 — Coarse prediction and upsampling (FCN-32s). The convolutionalized network, run on an H×W image, yields a class-score map at stride 32 (for a VGG-style backbone with five pooling layers), of size roughly (H/32)×(W/32)×C, where C is the number of classes. A single transposed convolution with stride 32 upsamples this directly back to H×W. This baseline is called FCN-32s. It is simple but spatially blurry: 32× upsampling in one shot cannot restore fine boundaries lost over five pooling stages.

Step 3 — Skip connections for finer detail (FCN-16s, FCN-8s). To sharpen the output, the network combines the stride-32 prediction with a prediction computed from the stride-16 feature map (from an earlier pooling stage, `pool4`). The stride-32 map is upsampled 2× (to stride 16) via transposed convolution, then added elementwise to a 1×1-convolution class-score map computed from `pool4`. The sum is then upsampled 16× to full resolution — this is FCN-16s. Repeating once more with the stride-8 feature map (`pool3`) gives FCN-8s: fuse stride-32 (upsampled ×2) with stride-16 (`pool4` scores), upsample the sum ×2 again, fuse with stride-8 (`pool3` scores), then upsample ×8 to the final resolution. Each additional skip roughly halves the residual blur, because it injects spatial detail from a shallower, higher-resolution stage before the final upsampling has to guess it back.

Step 4 — Train end-to-end with per-pixel loss. The loss is the sum (or mean) of per-pixel cross-entropy between the predicted class distribution and the ground-truth label at every spatial location, backpropagated through the transposed convolutions, the fusion additions, and the convolutionalized backbone exactly as in ordinary backprop — no special machinery is needed because every operation (conv, transposed conv, elementwise add, softmax) has a standard, well-defined gradient. ```

# --- Stage 1: build a fully convolutional backbone from a classifier --- function convolutionalize(classifier):

# classifier = [conv/pool blocks ..., FC6, FC7, FC8] conv_layers = classifier.conv_blocks # unchanged W6 = reshape(classifier.FC6.weights, kernel=(7,7,512,4096)) W7 = reshape(classifier.FC7.weights, kernel=(1,1,4096,4096)) W8 = reshape(classifier.FC8.weights, kernel=(1,1,4096,num_classes)) return Network(conv_layers + [Conv(W6), ReLU, Conv(W7), ReLU, Conv(W8)])

# --- Stage 2/3: FCN-8s forward pass --- function fcn8s_forward(image, backbone):

# backbone exposes intermediate feature maps at several strides f3 = backbone.forward_to("pool3", image) # stride 8, shape (H/8, W/8, 256) f4 = backbone.forward_to("pool4", image) # stride 16, shape (H/16, W/16, 512) f32 = backbone.forward_to("fc8", image) # stride 32, shape (H/32, W/32, C) score3 = conv1x1(f3, out_channels=C) # class scores at stride 8 score4 = conv1x1(f4, out_channels=C) # class scores at stride 16 up1 = transposed_conv(f32, stride=2) # stride 32 -> stride 16 fuse1 = up1 + score4 # combine coarse + pool4 detail up2 = transposed_conv(fuse1, stride=2) # stride 16 -> stride 8 fuse2 = up2 + score3 # combine + pool3 detail output = transposed_conv(fuse2, stride=8) # stride 8 -> stride 1 (full res) return softmax(output, axis=channel) # per-pixel class distribution

# --- Training loop --- function train(dataset, network): for (image, label_map) in dataset: pred = fcn8s_forward(image, network) # (H, W, C) loss = mean_over_pixels(cross_entropy(pred, label_map)) gradients = backprop(loss, network.parameters) # standard chain rule network.parameters -= learning_rate * gradients return network ```

Time complexity. Convolutionalizing a classifier changes nothing about the cost per output location: a convolution with kernel size k, C_in input channels, C_out output channels applied to an H×W feature map costs

per layer, exactly the FLOP count of the equivalent FC layer applied at one spatial position, times the number of positions. Since a classifier's dense layers were originally applied once (at the single 7×7 or 1×1 "position" left after pooling a fixed-size input), the convolutionalized version applied to a larger image simply repeats that same computation at every valid stride-32 location — cost scales linearly in the number of output positions, with no asymptotic penalty versus running the original classifier as a sliding window. In fact this is asymptotically better than the naive alternative of cropping patches and running the classifier separately on each: because of weight sharing, overlapping receptive fields' convolutions reuse computation, so the fully convolutional forward pass is $O(H \cdot W)$ rather than $O(H \cdot W \cdot k^2)$ redundant re-evaluations that a sliding-window classifier would perform. Transposed convolutions for upsampling by factor s cost $O\left(\frac{H}{s}\cdot\frac{W}{s}\cdot k^2 \cdot C_{in}\cdot C_{out}\right)$ per stage (computed on the smaller, coarse map, then spread to the larger one), so the added upsampling/fusion stages contribute a small constant-factor overhead relative to the main backbone, not a new asymptotic term. Overall forward and backward pass cost is $O(H \cdot W \cdot \text{(backbone FLOPs per pixel)})$, i.e., linear in image area, matching ordinary CNN inference cost.

Space complexity. Memory is dominated by storing feature maps at every stride for backprop: $O\!\left(\sum_{s} \frac{H}{s}\cdot\frac{W}{s}\cdot C_s\right)$ across the strides s = 1, 2, 4, ..., 32 used in the network, which is a geometric-like series dominated by the earliest (largest, but usually lowest-channel) and deepest (smallest, but highest-channel) layers — in practice comparable to the memory of the original classifier, plus the extra skip-branch score maps, which are small since they only have C channels.

Correctness of the FC-as-convolution identity. An FC layer with input flattened from an H×W×C_in tensor computes, for output unit j:

A convolution with a kernel of spatial size H×W (matching the entire input), C_in input channels, and C_out = (number of FC output units) computes, at its single valid output position (since a kernel as large as the input has exactly one position with "valid" padding and stride 1):

These are the same sum if $K_j := W_j$. The two layers are therefore identical functions on inputs of the original training size, guaranteeing that converting a trained classifier loses no accuracy at that size — it is a re-parameterization, not an approximation. On larger inputs, the convolutional form is well-defined (it slides the same kernel over more positions) while the FC form is not (its weight count is tied to a fixed input size), which is precisely the extra capability the FCN exploits.

Correctness of skip fusion. The additive fusion of the ×2-upsampled coarse score with the shallower layer's score map is well-posed only if both operands are the same spatial size and represent scores over the same class set; the network enforces this by upsampling exactly by the stride ratio between the two stages (e.g., 32→16 is a ×2 upsample to match `pool4`'s native stride-16 resolution) and by using a 1×1 convolution on the shallow features to project them into the same C-dimensional class-score space. This ensures the sum is a coherent per-pixel logit combination rather than a dimension mismatch or a semantic mismatch between spaces.

Tradeoffs. Deeper skip fusion (FCN-8s vs FCN-32s) trades a small amount of extra computation and parameters for markedly better boundary accuracy, since it lets the network combine "what" (semantic, from deep layers) with "where" (spatial, from shallow layers) — but it cannot fully recover information genuinely destroyed by pooling (e.g., very thin structures under stride 32 pooling may vanish before any skip connection can rescue them). Transposed convolutions can introduce characteristic "checkerboard" artifacts, motivating later designs (see U-Net) that use learned upsampling plus concatenated (not summed) skip features for cleaner gradients and detail transfer.

Consider a simplified VGG-style backbone processing a 320×320 RGB image for a 21-class segmentation task (20 object classes + background, as in PASCAL VOC), using five stride-2 pooling stages.

Trace of FCN-8s: 1. `score32` is 10×10×21. Apply transposed conv stride 2 → `up1` is 20×20×21. 2. `fuse1 = up1 + score4`, both 20×20×21 → elementwise sum, 20×20×21. 3. Apply transposed conv stride 2 to `fuse1` → `up2` is 40×40×21. 4. `fuse2 = up2 + score3`, both 40×40×21 → elementwise sum, 40×40×21. 5. Apply transposed conv stride 8 to `fuse2` → final output 320×320×21. 6. Apply softmax over the 21-channel axis at every one of the 320×320 = 102,400 pixel locations to get a per-pixel class distribution; `argmax` over channels gives the predicted label map. Contrast with FCN-32s: step 1's `score32` (10×10×21) would instead go straight through a single transposed conv with stride 32 to reach 320×320×21. Empirically (as reported in the original work) FCN-32s achieves noticeably lower mean Intersection-over-Union than FCN-16s or FCN-8s on PASCAL VOC, because a single 32× upsampling step must hallucinate all the boundary detail that pooling discarded across five stages, whereas FCN-8s only has to hallucinate an 8× gap after skip connections have already re-injected `pool3`- and `pool4`-level detail.

Fully convolutional design is now the default substrate for almost any per-pixel vision task, not merely academic segmentation benchmarks. Autonomous-driving stacks use FCN-style heads on top of pretrained backbones for road/lane/obstacle segmentation, feeding downstream planning modules. Medical imaging systems built on U-Net-style encoder-decoders (directly descended from FCN's skip-fusion idea) segment tumors, organs, and vessels in radiology and pathology pipelines. Satellite and aerial imagery analysis uses fully convolutional backbones for land-cover classification and change detection at arbitrary image sizes. Depth estimation, optical flow, surface-normal prediction, and image matting networks all reuse the same core recipe: convolutionalize a pretrained classifier, add upsampling and skip connections, train with a dense per-pixel loss. Even instance segmentation frameworks (e.g., Mask R-CNN's mask branch) embed a small fully convolutional sub-network to predict per-pixel masks within detected regions, showing how the idea composes with detection frameworks. Any system needing "one prediction per pixel, at any input resolution, initialized from a pretrained classifier" descends from this architecture.

Ask the tutor: How exactly does a transposed convolution compute its output, step by step, from a small input feature map?