A Survey of Semantic Segmentation

In plain words

Semantic segmentation means giving every pixel of a picture a label, such as road, car or sky, so a program knows which pixels belong to which kind of thing. This paper is a guided tour of how people have tried to do that. It explains how to score a segmentation, lists the image collections used to measure it, and sorts the methods into groups.

The older methods relied on hand-picked image features and classic classifiers. Later methods use neural networks that look at the whole image at once. The author also lists the situations that trip these systems up, such as lens flare, smoke, camouflage and glass that you can see through.

The paper is a survey. It does not test anything new, so the numbers it quotes come from other people's papers and are not comparable with each other.

TL;DR

A 2016 single-author survey of pixel-level semantic segmentation. It gives a four-part taxonomy, the standard accuracy measures and public datasets, and a short review of classical methods (features, random forests, SVMs, MRFs/CRFs, clustering, graph methods, post-processing) and CNN-based approaches. It also lists failure cases to test for. It proposes no method and reports no experiments of its own. Use it as a map of the field and a source of metric definitions, not as a source of benchmark results.

Problem

Semantic segmentation assigns each pixel a class, so the output groups pixels that belong to the same kind of object §1. The paper frames it against non-semantic segmentation, which has no fixed class set and is therefore under-defined §1. It also separates it from object detection, which must tell apart instances of the same class §1.

The survey names two open items as future work, not done here: a comparative study of the reviewed algorithms on public datasets, and a systematic study of the failure cases in §7 §8.

Method

The paper is a survey. It organises the field in four parts: a taxonomy §2, evaluation and datasets §3, a generic segmentation pipeline §4, and the methods themselves, split into traditional approaches §5 and neural networks §6. A final section lists failure cases §7 and a discussion closes the paper §8.

Taxonomy §2

The survey restricts itself to one class-affiliation setting: each pixel gets exactly one label, and the operation is fully automatic and passive §2. It distinguishes these axes:

• Fixed class set, void class, or unsupervised (no classes) §2.1.
• Single-label versus multiple-label affiliation per pixel §2.2.
• Input type: grayscale or colour, with or without depth, single image, stereo or co-segmentation, and 2D versus 3D §2.3.
• Operation: active (the machine can move objects) versus passive, and automatic versus interactive §2.4.

Evaluation measures §3.1

All measures are defined from a confusion matrix over k classes. Entry n_ij counts pixels of true class i predicted as class j, and t_i is the total number of pixels of class i §3.1.1.

• Pixel accuracy is the sum of the diagonal divided by the total number of pixels. The paper notes two drawbacks: large single-class regions make high accuracy easy, and coarse annotation can hide errors §3.1.1.
• Mean accuracy averages n_ii / t_i over classes §3.1.1.
• Mean intersection over union averages n_ii / (t_i - n_ii + sum over j of n_ji) over classes §3.1.1.
• Frequency-weighted IoU weights each class's IoU by t_i, normalised by the total count §3.1.1.
• Pixels of a void class are excluded from all measures, so the pixel total becomes width times height minus void pixels §3.1.1.
• F-measure for binary tasks uses true positives (tp), false negatives (fn) and false positives (fp), with beta = 1 in most cases §3.1.1. See Pitfalls for a typo in the printed formula.

Speed is measured as latency (time for one image) and throughput (images per time). The paper gives an example latency budget of 20 ms per image for autonomous driving §3.1.2. Stability asks that small input changes, such as blur or a slight viewpoint change, change the output only slightly §3.1.3. Peak memory is named as a measure but the paper found no publication that reports it §3.1.4.

Datasets §3.2

The full dataset table is in app. A. Summary of the sets described in text:

• PASCAL VOC: photographs from a photo-sharing site. The segmentation task has 20 object classes plus background in the 2012 challenge. Evaluation on the 2010 to 2012 data is still possible through the organisers' server §3.2.1.
• MSRCv2: 591 photographs, 21 classes, plus a void label for pixels that are unlabelled or near boundaries §3.2.2.
• Medical sets: Warwick-QU (165 images, 5 gland grades), DIARETDB1 (89 fundus images, 4 lesion types), DRIVE (vessel annotations, 20 test and 20 training images), and Open-CAS endoscopic data (60 + 60 images, instrument versus no instrument, with crowd-sourced labels) §3.2.3.

Pipeline §4

The classic pipeline runs a fixed-size patch classifier over the image: each window is classified, usually for its centre pixel, and the results are combined. Preprocessing (scaling, features such as HOG), data augmentation during training, and post-processing (morphology or MRFs) can be added §4. A 512 by 512 image needs 262144 classifier calls. Striding and interpolation reduce that cost §4. Neural networks run the same operation as a convolution over the whole image §4.

# Sliding-window segmentation  [§4] [fig. 2]
# Input:  image (H, W, 3); fixed-size patch classifier
# Output: one label per pixel (H, W)

def segment(image, classifier, window):
    # Start with an empty label map, same size as the image  [§4]
    labels = empty(H, W)
    # Visit every window position; a stride may skip positions  [§4]
    for each window position (x, y) in image:
        # Cut out the patch at this position  [§4]
        patch = crop(image, x, y, window)
        # The classifier may label only the centre pixel  [§4]
        labels[y, x] = classifier(patch)
    # Optionally refine: morphology, MRFs or CRFs  [§4] [§5.7]
    return labels

Classical methods §5

Features §5.1. Colour spaces (RGB, HSI, Lab, YIQ and others) are the most common features. No space is best in all cases §5.1. The paper states that histogram equalisation can improve contrast §5.1.

• HOG: gradients in x and y are binned into orientation histograms per patch §5.1.2.
• SIFT: a 16 by 16 patch around a keypoint is split into 16 cells of 4 by 4, each with an 8-bin orientation histogram, giving a 128-dimensional vector §5.1.3. The paper calls SIFT a global feature for the whole image in the same passage §5.1.3.
• Bag of visual words (BOV): histograms of quantised local patterns §5.1.4.
• Poselets: manually placed keypoints, hard to define for classes such as aeroplanes or cells §5.1.5.
• Textons: basic texture building blocks; the paper says CNN first layers may learn them §5.1.6.
• Dimensionality reduction: downsampling, or PCA, which ignores class labels §5.1.7.

Unsupervised §5.2. Clustering (k-means, mean shift) on pixel features §5.2.1. Graph-based methods treat pixels as nodes with dissimilarity-weighted edges, cut them with a minimum spanning tree, and read the components as segments §5.2.2. Random walks propagate seed labels by hitting probability §5.2.3. Active contours fit smooth boundaries to edges by minimising an energy §5.2.4. The watershed treats grayscale as a height map and fills basins §5.2.5.

Random decision forests §5.3. An ensemble of decision trees, each trained on a random feature subspace and/or a bootstrap sample of the training set §5.3. Trees are grown until leaves are pure or cannot be split further (the stopping criterion). The paper lists the split-quality measure, the number of trees and a depth limit as tunable, with no values given §5.3.

SVMs §5.4. The paper derives the soft-margin SVM in five steps §5.4:

1. The maximum-margin separating hyperplane, with the constraint y_i (w.x_i + b) at least 1 §5.4.
2. Slack variables xi_i and a penalty C for them, so that 0 <= xi_i <= 1 lies inside the margin and xi_i >= 1 is misclassified §5.4.
3. The dual problem: w is a weighted sum of training vectors with multipliers alpha_i, where 0 <= alpha_i <= C and the sum of alpha_i y_i is zero. Vectors with non-zero alpha_i are support vectors §5.4.
4. Kernels replace dot products: polynomial (degree p, offset r), Gaussian RBF, and sigmoid (with gamma and r) §5.4.
5. Multi-class by one-vs-all (n classifiers) or one-vs-one (n(n-1)/2 classifiers) §5.4.

MRFs §5.5. Undirected graphical models over pixel labels with a neighbourhood graph (4- or 8-neighbourhood). The joint distribution is proportional to exp(-E), where E is a sum of clique potentials. The pairwise example potential is +w when two neighbouring labels differ and -w when they are equal §5.5. Inference is maximum a posteriori (MAP) estimation §5.5. The paper's example counts variables for a 224 by 224 RGB image: 224 times 224 times 3 inputs plus 224 times 224 outputs, which is 200704 §5.5.

CRFs §5.6. A CRF conditions the clique potentials on the input x and models P(y | x), so it need not model the distribution of x §5.6. The simplest potential is a count of a class plus a positive smoothing constant. The paper cites CRF-based systems at the top of PASCAL VOC 2010 §5.6.

Post-processing §5.7. Morphological opening (dilation then erosion) removes small segments, and closing (erosion then dilation) fills small gaps §5.7. Snapping boundaries to an ultrametric contour map is another option §5.7.

Neural networks §6

The survey gives a short history. A neuron takes weighted inputs, sums them and applies an activation function. Weights are learned by gradient descent on an error function such as cross-entropy or squared error §6.

• AlexNet-style CNNs use ReLU, max(0, x), which the paper says trains much faster than sigmoid, and dropout, which sets random outputs to zero during training §6. Input images were downsampled to 256 by 256 §6.
• Fully convolutional networks apply a classifying network as a filter over the whole image, giving a per-pixel class distribution for images of any size §6.
• A recurrent CNN for segmentation §6, and a deeper network reported to beat the earlier approaches §6.

Failure cases §7

The paper lists cases to test for, with no systematic study behind them §7.

• Lens flare: light scattered inside the lens (KITTI road test set has examples) §7.1.
• Vignetting: darker corners §7.2.
• Blur: from lens focus, fast motion, smoke or foam; one example is smoke from cauterisation during surgery §7.3.
• Partial occlusion: a model-based system may suffer §7.4.1.
• Camouflage: animals hiding, or labels that are wrong §7.4.2.
• Semi-transparent objects: whether a pixel behind a glass belongs to the glass or the object behind it is a definition question §7.4.3.
• Viewpoint: unusual camera positions absent from training data §7.4.4.

Hyperparameters

The survey gives no training recipe. Values below are those the text states; a blank value means the paper does not state it.

Results

The paper reports no experiments of its own. The table below lists the results it quotes from cited work. These are author-reported by the original authors, on different datasets, hardware and years, so they are not comparable with each other.

Dataset summary from the table in app. A. The paper gives these as the public ground-truth databases it lists. Image resolutions are ranges unless a single value is given.

Source: app. A.

Paper vs code

No official code. The paper links no code, the abstract and arXiv metadata name no repository, and it has no method to implement. The only links in the source are a PASCAL VOC evaluation server, a Wikimedia category, lecture notes and licence and ORCID references. A GitHub repository search for the survey title with a guessed author handle (martin-thoma, not linked by the paper) returned nothing. Per our survey rule, the linked repositories of survey papers are paper lists, not implementations.

Pitfalls

• Printed F-measure formula is wrong. The text writes F_beta as (1+beta)^2 times tp over ((1+beta^2) tp + beta^2 fn + fp) §3.1.1. The numerator should be (1+beta^2) tp, not (1+beta)^2 tp. With beta = 1 the printed form gives 2 for a perfect prediction, so use the standard F-measure §3.1.1.
• MSRCv2 class count is inconsistent. The text lists 21 classes plus a void label §3.2.2. The appendix table lists 23 classes app. A. Check the dataset's own documentation before use.
• "Segmentation over union" means intersection over union. The text uses the wrong name for the PASCAL challenge criterion §3.2.1.
• Gaussian RBF kernel has redundant parameters. The formula uses both gamma and sigma in one exponent §5.4. Pick one parameterisation and state it. The paper gives no default values for either.
• MRF example variables are ambiguous. The paper's pairwise potential is written over x_1 and x_2 §5.5, but its text says y are labels and x are pixel values. Implement the form you mean, and note that the paper's sign convention penalises unequal labels with +w §5.5.
• CRF smoothing constant is not stated §5.6. The paper says the constant keeps the term from becoming zero, but gives no value.
• Pixel accuracy is not mean IoU. Pixel accuracy is dominated by large regions; the paper notes that over 30% accuracy is reachable from prior knowledge alone §3.1.1. Compare runs with the same measure.
• Latency numbers are not comparable. The paper says runtimes depend on hardware and implementation §3.1.2. Its 10-second and 415 ms figures come from very different machines and years §3.1.2 §5.3.
• Scores quoted are from different benchmarks. The rank and accuracy figures come from different years and datasets §5. They are not a leaderboard.
• Memory is not measured in the literature the paper reviewed, by the paper's own statement §3.1.4.
• Survey, not experiments. The paper proposes no method and runs no experiments. Its failure-case list is a checklist, and the paper says no systematic study exists §7 §8.
• Data licensing. Several figures in the paper are third-party images. This card uses none of them. Some datasets in app. A have their own licences.

Lineage

• Builds on: none stated. The survey cites earlier methods (e.g. Ohta et al. 1978 as one of the first papers mentioning semantic segmentation §8).
• Compared against: not applicable; no experiments.
• Related work the text names: a fully convolutional network that applies a classifying network over the whole image §6; a recurrent CNN for segmentation §6; a deeper network (Dai et al. 2015) §6; and CRFs combined with neural networks §8. The text does not give authors for the first two, and no cards exist for them yet.
• Superseded by: not stated in this wiki.