Background Subtraction

Background subtraction separates the moving objects in a video from the scene behind them. A model of what the camera sees when nothing of interest is present, the background, is kept for every pixel, and each new frame is compared with it; pixels that differ enough are labelled foreground. Stauffer and Grimson described it as thresholding the error between an estimate of the image without moving objects and the current image (Stauffer & Grimson, 1999, abstract). The same task is also called foreground detection, motion detection or, in the benchmark literature, change detection (Goyette et al., 2012). With a static camera it is a cheap first step: the masks it produces are cleaned with mathematical morphology, grouped into connected regions and passed to object tracking, counting or classification. The hard part is the model, because real backgrounds change.

The mixture model itself, with Stauffer and Grimson’s update equations and an example on a flickering background, is in Gaussian Mixture Model. Segmenting moving objects when the camera itself moves, with motion cues rather than a background model, is motion segmentation.

Problem Definition

The input is a video from a camera that does not move, or moves only slightly. At each time $t$ the method holds a background model built from frames $I_1, \dots, I_{t-1}$ and outputs a binary mask $F_t$ with $F_t(\mathbf{x}) = 1$ where the pixel $\mathbf{x}$ belongs to the foreground. In Barnich and Van Droogenbroeck’s terms, the comparison of the observed image with the background model, called foreground detection, splits the image into two complementary sets of pixels: the foreground, which contains the objects of interest, and the background (Barnich & Van Droogenbroeck, 2011, §II). The method is usually causal and online: it labels frame $t$ before seeing frame $t+1$, and it updates the model as it goes.

What counts as foreground is not a property of pixels but of the application. Barnich and Van Droogenbroeck note that there is no gold-standard definition of what should be detected, because it depends on the application level (§II). The CDnet benchmark makes one definition explicit for its ground truth: changing regions are people, animals or man-made objects such as cars, boats, trains and bags; swaying trees, waves and flags belong to the background; light reflections, heat turbulence and spotlight halos are not moving objects even when moving objects cause them; and an object that stops, such as a car at a traffic light or an abandoned bag, should be detected for a short while and then merged into the background (CDnet website, dataset overview). That last rule makes the task depend on time: the same still object is foreground for some seconds and background afterwards.

Two artefacts follow from keeping a model. When a static object starts moving, the method detects the object and also the hole it leaves in the background model; Barnich and Van Droogenbroeck call that hole a ghost and note that it is irrelevant for motion interpretation (§I). And when the first frames used to build the model contain moving objects, the model starts wrong and has to recover; ViBe, which initializes from a single frame, produces ghosts this way (§III-B).

Input and Output

• Input: frames from a fixed camera, as grey levels, colour or other channels. Stauffer and Grimson reported running their mixture model on grey-level, RGB and HSV values and on local linear filter responses (Stauffer & Grimson, 1999, §5). CDnet includes far-infrared videos as a category of its own (Goyette et al., 2012, §3.1).
• Output: one binary mask per frame. Some methods add a third label for shadows: OpenCV’s MOG2 implementation marks shadow pixels with the value 127 by default (OpenCV 4.14.0, bgfg_gaussmix2.cpp). Many methods can also return a background image, for example a weighted average of the means of a mixture’s background components (getBackgroundImage in OpenCV’s MOG2).
• Downstream: Stauffer and Grimson grouped foreground pixels into regions with a two-pass connected-components algorithm, tracked the regions with a multiple-hypothesis tracker built from Kalman filters, and removed noise by ignoring components of one or two pixels (Stauffer & Grimson, 1999, §2.3–§2.4 and footnote 1). Tracking-by-detection trackers take the regions from a detector instead.

Variants

• Static camera, the classical case. All the methods below assume that a pixel keeps looking at the same scene point.
• Small camera motion. Camera jitter is a CDnet category of its own (Goyette et al., 2012, §3.1). ViBe’s authors attribute its tolerance of small displacements to the sharing of samples between neighbouring pixel models (Barnich & Van Droogenbroeck, 2011, §IV-D).
• Moving or pan-tilt-zoom cameras. The model must follow the camera. ViBe’s authors handled pans by estimating the global displacement between frames with the Lucas–Kanade estimator on a grid of background points, moving the pixel models inside a larger mosaic, and initializing the models of newly seen areas from a single frame (§IV-D). CDnet 2014 added a PTZ category, which its authors say requires different techniques from static-camera videos (Wang et al., 2014, §3.1). Without a background model, moving objects are found from motion itself, the subject of motion segmentation and of optical flow estimation.
• Background estimation. Some uses need only a clean image of the empty scene. Braham and Van Droogenbroeck took the temporal median of 150 frames, which they note is appropriate when each pixel shows the background at least half of the time (Braham & Van Droogenbroeck, 2016, §II-A).
• Related tasks. Change detection in remote sensing compares images of the same place taken months apart, with registration and radiometric problems of its own. Video object segmentation segments chosen objects whatever their motion, usually given their masks in the first frame.

Challenges

The CDnet authors list sudden illumination changes, background movement, shadows, camouflage and ghosting as challenges that no single algorithm handled competently (Goyette et al., 2012, §1). Stauffer and Grimson’s list of what a video surveillance and monitoring system should handle includes lighting changes, swaying trees, slow-moving objects and objects introduced into or removed from the scene (Stauffer & Grimson, 1999, §1).

• Illumination change. Gradual change (time of day, clouds) and sudden change (lights switched on) both alter every background pixel. A model that adapts slowly calls the whole frame foreground; one that adapts fast absorbs slow objects. Stauffer and Grimson found their tracker robust to all but relatively fast lighting changes, such as floodlights turning on and partly cloudy, windy days (§4). Some cameras add their own changes through automatic exposure, which CDnet mentions as global brightness fluctuations (Goyette et al., 2012, §3).
• Dynamic background. Swaying branches, rippling water, fountains and flickering monitors make one pixel see several surfaces in turn. Stauffer and Grimson’s scatter plots show bimodal pixel histories from water specularities and monitor flicker (Stauffer & Grimson, 1999, Figure 2). CDnet’s Dynamic Background category holds boats on shimmering water, cars beside a fountain, and traffic in front of a tree shaken by wind (Goyette et al., 2012, §3.1).
• Shadows. A moving shadow changes the background as much as an object does, and is attached to the object. CDnet’s Shadows category has strong and faint shadows, cast by moving objects and by trees and buildings (§3.1).
• Camouflage. An object whose colour or temperature matches the background cannot be told apart pixel by pixel. CDnet has no camouflage category partly because, its authors note, almost every real video contains some camouflage (§3.1); many methods had large false negative rates on the thermal videos, which the authors attribute mostly to camouflage (§5).
• Intermittent object motion. Objects that stop and start again, abandoned objects and parked cars that drive away cause ghosts and missed detections. CDnet’s Intermittent Object Motion category tests this (§3.1), and the 2014 paper lists it among the problems no method handled well: any object that stops for some time ends up mis-detected (Wang et al., 2014, §5).
• Other conditions. Sensor noise, compression artefacts and radial distortion vary with the camera (Goyette et al., 2012, §3); CDnet 2014 adds bad weather, frame rates of 0.17 to 1 frame per second, night traffic with headlights, PTZ cameras and air turbulence (Wang et al., 2014, §3.1).

Approaches

Most classical methods work on each pixel independently and leave spatial consistency to post-processing; Barnich and Van Droogenbroeck note that this produces local misclassifications, since perturbations often affect individual pixels (Barnich & Van Droogenbroeck, 2011, §II). The families below differ in how they represent the history of a pixel and how they update it.

Frame differencing and running averages

The simplest detector compares a frame with the previous one,

$$F_t(\mathbf{x}) = \big[\, |I_t(\mathbf{x}) - I_{t-1}(\mathbf{x})| > \tau \,\big].$$

It needs no model and adapts instantly, but by construction it responds only where intensity changes between two frames: at the leading and trailing edges of a moving object, not inside a uniform one, and not at all for an object that stops.

A background image $B_t$ fixes the stopped-object problem. ViBe’s paper lists the simplest choices: a static background frame, the running average, first-order low-pass filtering, temporal median filtering, and a single Gaussian per pixel (§II). The exponentially weighted running average, the form ViBe’s authors give for the first-order low-pass filter they use as a baseline, is

$$B_t = (1 - \alpha)\, B_{t-1} + \alpha\, I_t, \qquad F_t(\mathbf{x}) = \big[\, |I_t(\mathbf{x}) - B_{t-1}(\mathbf{x})| > \tau \,\big],$$

which they ran with $\alpha = 0.05$ and $\tau = 20$ (§IV-B). Here $1/\alpha$ frames set the memory. By our reasoning, a background that brightens or darkens at $s$ grey levels per frame is followed with a lag of about $s/\alpha$, so the method tolerates gradual change while $s/\alpha < \tau$. Stauffer and Grimson summarized the weaknesses of averaging: it fails with many or slow-moving objects, cannot represent bimodal backgrounds, recovers slowly when the background is uncovered, and uses one predetermined threshold for the whole scene (Stauffer & Grimson, 1999, §1.1).

Sigma–delta filters replace the weighted average by an increment or decrement of one grey level towards the current value; ViBe’s authors describe them as popular for embedded processing because they need no floating-point unit (Barnich & Van Droogenbroeck, 2011, §II). A single Gaussian per pixel adds a per-pixel variance and with it a per-pixel threshold. Pfinder used one, and reported good results indoors after an initialization period in an empty room; Ridder et al. modelled each pixel with a Kalman filter, which made their system more robust to lighting changes but, in Stauffer and Grimson’s assessment, still slow to recover and poor with bimodal backgrounds (Stauffer & Grimson, 1999, §1.1).

Per-pixel Gaussian mixtures

Stauffer and Grimson (1999) modelled the recent history of each pixel as a mixture of $K$ Gaussians, 3 to 5 in their system, updated online instead of by EM. Each new value is matched against the components, the matched component’s weight, mean and variance are updated, a value that matches nothing replaces the least probable component, and the components with the largest $\omega/\sigma$ that together account for a fraction $T$ of the data form the background. Gaussian Mixture Model gives the equations and shows the behaviour on a flickering patch. Three properties matter for the task. Each pixel gets its own threshold, 2.5 standard deviations of the matched component, which the authors found useful when different regions have different lighting (§2.1). A repetitive motion such as leaves or a flag can contribute two or more background components when $T$ is large enough (§2.2). And when an object that had become background moves away, the old background component is still in the mixture and is quickly reinstated (§2.1). The authors named $\alpha$ and $T$ as the method’s two significant parameters, and reported that after quick changes in cloud cover the model stabilized within 10 to 20 seconds (§1.2 and §3). They did not try to remove shadows: for their applications it was more important to track an object with its shadow than to crop or miss dark objects (§4).

Zivkovic (2004) and Zivkovic and van der Heijden (2006) adapted the number of components per pixel. Their papers could not be read for this article; Wang et al. describe the method as a recursive GMM with an improved update of the Gaussian parameters and automatic selection of the number of modes (Wang et al., 2014, §4), and the description below follows OpenCV’s BackgroundSubtractorMOG2, whose source cites both papers and carries Zivkovic’s name as author (OpenCV 4.14.0, bgfg_gaussmix2.cpp). In that implementation every component’s weight is updated as

$$\omega_k \leftarrow \omega_k + \alpha\, (o_k - \omega_k) - \alpha\, c_T,$$

with $o_k = 1$ for the matched component and 0 otherwise, and a constant $c_T$ (0.05 by default) that pulls every weight down. A component whose weight falls below $\alpha\, c_T$ is discarded, so a pixel with a simple history keeps one or two components while a pixel on a swaying branch keeps several. The matched component’s mean and variance move towards the new value at the rate $\alpha/\omega_k$, so a component with little weight adapts fast and a heavy one slowly; Stauffer and Grimson’s rate is $\alpha$ times the Gaussian density at the new value instead. Components are kept sorted by weight, and a pixel is background if it lies within $\sqrt{T_b}$ standard deviations of a component whose higher-ranked components together weigh less than the background ratio. The defaults are a history of 500 frames ($\alpha = 1/500$), $T_b = 16$ (four standard deviations) for the background test, a separate threshold of 9 (three standard deviations) for deciding that a value belongs to an existing component, at most five components, a background ratio of 0.9, an initial variance of 15 and variance limits of 4 and 75 (bgfg_gaussmix2.cpp). During the first frames the learning rate is $1/\min(2n, \text{history})$ after $n$ frames, so the model fills quickly before settling to its long memory.

Kernel density estimation and sample-based models

Non-parametric models skip the choice of a density shape and keep recent values themselves. Kernel density estimation, for which Barnich and Van Droogenbroeck cite Elgammal, Harwood and Davis (2000), a paper not read for this article, among others, estimates each pixel’s background density from samples of its recent history (§II),

$$\hat{p}(\mathbf{x}_t) = \frac{1}{N} \sum_{i=1}^{N} K(\mathbf{x}_t - \mathbf{x}_i),$$

in its generic form, with a value of low estimated density labelled foreground. As Barnich and Van Droogenbroeck describe this family, kernel methods respond quickly to high-frequency events in the background because new values enter the model directly, but they update their samples first-in first-out, which makes events at different speeds hard to handle together; Elgammal et al. and others therefore kept a short-term and a long-term model (Barnich & Van Droogenbroeck, 2011, §II). With a first-in first-out policy, 300 samples cover only 10 seconds at 30 frames per second, so a pixel covered by a slow object for longer is absorbed into the background (§III-C). Consensus methods such as SACON keep a cache of recent background values and require a new value to match most of them (§II). OpenCV’s BackgroundSubtractorKNN, documented as implementing the k-nearest-neighbour method of Zivkovic and van der Heijden (2006), keeps three sets of 7 samples per pixel (short-, mid- and long-term) by default, with a squared-distance threshold of $20^2$ (OpenCV 4.14.0, background_segm.hpp and bgfg_KNN.cpp).

ViBe (Barnich & Van Droogenbroeck, 2011) keeps $N$ observed values per pixel, $M(\mathbf{x}) = \{v_1, \dots, v_N\}$, and estimates no density at all. A value $v(\mathbf{x})$ is background when at least $\#_{\min}$ samples lie within a radius $R$ of it:

$$\#\{\, S_R(v(\mathbf{x})) \cap \{v_1, \dots, v_N\} \,\} \ge \#_{\min}$$

(§III-A, Eq. 2). The authors argue that a few close samples estimate a background distribution more reliably than a majority of many, which resembles keeping only the central part of the distribution. Three choices distinguish the update (§III-B–§III-C):

• Initialization from one frame. Each model is filled with values drawn at random from the pixel’s 8-connected neighbourhood in the first frame, on the assumption that neighbouring pixels share a temporal distribution. Detection works from the second frame, and the same mechanism answers sudden illumination changes: discard the model and re-initialize.
• Conservative, random, subsampled update. Only values classified as background enter a model, and then only with probability $1/\varphi$; the new value replaces a sample chosen at random, not the oldest. A sample then survives an update with probability $(N-1)/N$, and its remaining lifespan decays exponentially, $P(t, t + \mathrm{d}t) = e^{-\ln(N/(N-1))\,\mathrm{d}t}$ (Eqs. 5–6), independently of how long it has already been in the model.
• Spatial propagation. A background value is also written into the model of a randomly chosen neighbour: in the text when the pixel’s own model is updated (§III-C4), in the Appendix A pseudocode with an independent chance of $1/\varphi$. A purely conservative update would never absorb the area freed by a parked car that leaves; propagation lets background samples diffuse into it. Because a ghost usually resembles the surrounding background, it is eroded from its border, while a real object that stops, whose colours differ from its surroundings, stays foreground much longer (§IV-C).

The default parameters are $N = 20$, $R = 20$ (grey levels), $\#_{\min} = 2$ and $\varphi = 16$ (§IV-A, Appendix A). The random choices make ViBe non-deterministic; the authors note that two runs on the same sequence differ slightly (§III-C). On two sequences with hand-made ground truth, a windy outdoor scene and a PETS 2001 sequence, ViBe, in its colour and grey-level versions, had a higher percentage of correct classification than the seven other methods compared, which included two Gaussian mixture implementations (one of them Zivkovic’s), a codebook method and the first-order filter, and ran at about 200 frames per second on $640 \times 480$ images (§IV-B, Figures 7–8). A version reduced to one comparison and one byte of memory per pixel still classified better than the two mixture methods (§IV-F). The comparison used no shared benchmark. The paper also mentions a patent on the method (§I).

Shadows

A cast shadow darkens the background without changing its colour much. OpenCV’s MOG2 uses that property, citing Prati et al. (2003): a foreground value $\mathbf{x}$ is a shadow if, for one of the background components with mean $\boldsymbol{\mu}$, the brightness ratio $a = \mathbf{x}^\top \boldsymbol{\mu} / \|\boldsymbol{\mu}\|^2$ lies between $\tau$ and 1 and the colour distortion $\|a\boldsymbol{\mu} - \mathbf{x}\|^2$ is within the background threshold scaled by $a^2$ times the component’s variance (bgfg_gaussmix2.cpp, detectShadowGMM). With the default $\tau = 0.5$, a pixel more than twice as dark as the background is not a shadow (background_segm.hpp). Stauffer and Grimson observed the limit of such colour reasoning outdoors: on bright days, shadowed regions and the shady sides of dark objects were both black (Stauffer & Grimson, 1999, §4). CDnet labels hard shadows in its ground truth so that shadow errors can be measured, and its 2012 evaluation found false-positive rates inside hard shadows between 0.33 and 0.64 for the 18 methods tested (Goyette et al., 2012, §3.2, §5 and Table 3).

Post-processing and combination

Morphological opening removes isolated false positives and closing fills holes before connected components are labelled, and the smallest components are dropped, as Stauffer and Grimson did. At CDnet 2012, a superpixel-based Markov random field that refines the mask of any other method (PSP-MRF) ranked second overall, and the authors note that it reduces both false positives and false negatives of the method it is applied to (Goyette et al., 2012, §5). At CDnet 2014, a pixel-wise majority vote of the three best methods outperformed every single method, which the authors read as evidence that the methods are complementary (Wang et al., 2014, §5).

Trained networks

Braham and Van Droogenbroeck (2016) presented their method as the first application of convolutional networks to background subtraction. They kept the background model trivial, a grey-level temporal median of 150 frames, and trained a small LeNet-5-like network to classify the centre pixel of a pair of $27 \times 27$ patches, one from the current frame and one from the background image (§II). The network was trained separately for each video on the first half of its labelled frames and tested on the second half. On the CDnet 2014 videos they selected, its mean F-measure was 0.9046 when trained on ground truth and 0.7897 when trained on the output of an existing combination of methods (IUTIS-5), against 0.7444 for the Gaussian mixture and 0.7298 for kernel density estimation as reported on the CDnet website (Table II).

Tezcan, Ishwar and Konrad (2020) pointed out that the best supervised methods were trained on labelled frames of the very videos they were tested on. They called such methods video-optimized when the frames come from the test video and video-group-optimized when random frames of all test videos are used, and their survey of the field lists FgSegNet among the former, trained on 200 hand-picked frames of each test video (Tezcan et al., 2020, §2.2 and Table 1). Their BSUV-Net is video-agnostic: a U-Net-type fully convolutional network (see U-Net) receives the current frame, an empty background frame (a median of foreground-free early frames) and a recent background frame (the median of the 100 preceding frames), each with a foreground probability map from a DeepLabv3 segmentation network trained on ADE20K, and is trained with a relaxed Jaccard loss and an illumination augmentation that adds a random global offset to each colour channel (§3). Evaluated over 18 train–test splits in which every CDnet 2014 video is tested by a network that never saw it, BSUV-Net reached an F-measure of 0.7868, against 0.7583 for SWCD and 0.7403 for PAWCS among unsupervised methods (WisenetMD has 0.7668 in Table 2 but 0.7535 in the paper’s Table 3); FgSegNet v2, retrained in the same video-agnostic way, fell to 0.3715 (§4.2 and Table 2).

Example: lighting change and a swaying region

The NumPy code below compares four families on a synthetic video whose ground truth is known. The background is scikit-image’s bundled camera image, downsampled by four, with sensor noise of standard deviation 3. From frame 150 the whole scene dims linearly to 60% of its brightness over 150 frames, about 0.3 grey levels per frame at the mean intensity. A $32 \times 32$ striped region sways three pixels back and forth every 16 frames, and counts as background, as swaying trees do in CDnet. Three rectangular objects, two bright and one dark, cross the scene from frame 60; the dark one passes through the swaying region while the scene dims. Where the dark object crosses dark parts of the image or the bright objects cross bright ones, object and background differ by less than the methods’ thresholds, a camouflage that limits every method.

The methods are frame differencing; the running average with ViBe’s baseline settings ($\alpha = 0.05$, $\tau = 20$) and with a ten times slower $\alpha = 0.005$; Stauffer and Grimson’s mixture with $K = 3$, $\alpha = 0.01$, $T = 0.7$, an initial standard deviation of 10 and a replacement weight of 0.05; and ViBe with its published defaults, implemented as in the paper’s Appendix A. The paper gives no values for $\alpha$ and $T$, which are our choices. The rate at which a matched component’s mean and variance move is a choice the sources leave open: Stauffer and Grimson print $\rho = \alpha\,\eta(X_t \mid \mu_k, \sigma_k)$, while OpenCV’s MOG2 uses $\alpha/\omega_k$, so the code runs both. Each mask is scored by the F-measure of the frame, averaged over the frames with foreground in three phases: steady light (frames 50–149), dimming (150–299) and dim (300–399). The false-positive rates are measured inside the swaying region and over the rest of the background, and the last column averages F over all frames after a $3 \times 3$ binary opening.

import numpy as np
from scipy.ndimage import binary_opening
from skimage import data

# Synthetic grey-level video, 96 x 128 pixels, 400 frames. The background is the
# bundled camera image (downsampled by 4). A gradual dimming starts at frame 150
# (gain 1.0 -> 0.6 over 150 frames); a striped region sways like branches
# (+-3 px, period 16 frames); three objects cross the scene from frame 60 on.
rng = np.random.default_rng(0)
bg = data.camera().astype(float).reshape(128, 4, 128, 4).mean(axis=(1, 3))[16:112]
H, W, T = bg.shape[0], bg.shape[1], 400
yy, xx = np.mgrid[0:H, 0:W]
sway = (yy >= 8) & (yy < 40) & (xx >= 92) & (xx < 124)
m = bg[sway].mean()
# objects: top row, height, width, intensity, first frame, end frame, start column, speed
objs = [(58, 14, 10, 230.0, 60, 190, -10, 1.0),
        (14, 12, 12, 25.0, 120, 280, -12, 0.9),      # crosses the swaying region
        (66, 14, 10, 230.0, 290, 400, 130, -1.2)]
frames, truth = [], []
for t in range(T):
    f = bg.copy()
    f[sway] = m + 40 * np.sin(2 * np.pi * (xx[sway] - 3 * np.sin(2 * np.pi * t / 16)) / 6)
    fg = np.zeros((H, W), bool)
    for r0, h, w, val, t0, t1, x0, v in objs:
        if t0 <= t < t1:
            x = int(round(x0 + v * (t - t0)))
            obj = (yy >= r0) & (yy < r0 + h) & (xx >= x) & (xx < x + w)
            f[obj] = val
            fg |= obj
    gain = 1.0 if t < 150 else (0.6 if t >= 300 else 1.0 - 0.4 * (t - 150) / 150)
    frames.append(gain * f + rng.normal(0, 3, (H, W)))
    truth.append(fg)
frames, truth = np.array(frames), np.array(truth)


def frame_difference(frames, thr=20.0):
    masks = [np.zeros(frames[0].shape, bool)]
    masks += [np.abs(frames[t] - frames[t - 1]) > thr for t in range(1, len(frames))]
    return masks


def running_average(frames, alpha, thr=20.0):
    B, masks = frames[0].copy(), []
    for x in frames:
        masks.append(np.abs(x - B) > thr)
        B = (1 - alpha) * B + alpha * x               # blind update: every pixel
    return masks


def stauffer_grimson(frames, rate, K=3, alpha=0.01, Tb=0.7, k=2.5, var0=100.0, w0=0.05,
                     var_min=4.0):
    """Per-pixel mixture with the online update of Stauffer & Grimson (1999).
    rate='printed': rho = alpha * eta (their Eq. 8); rate='1/w': rho = alpha / w,
    the matched component's weight after its update (as in OpenCV's MOG2)."""
    shape = frames[0].shape
    w = np.zeros((K,) + shape); w[0] = 1.0
    mu = np.zeros((K,) + shape); mu[0] = frames[0]
    var = np.full((K,) + shape, var0)
    masks = []
    for x in frames:
        rank = np.argsort(-w / np.sqrt(var), axis=0)  # order by w / sigma
        ws = np.take_along_axis(w, rank, axis=0)
        B = 1 + (np.cumsum(ws, axis=0) <= Tb).sum(axis=0)   # first B exceed Tb (Eq. 9)
        is_bg = np.zeros((K,) + shape, bool)
        for i in range(K):
            np.put_along_axis(is_bg, rank[i:i + 1], (i < B)[None], axis=0)
        within = np.abs(x - mu) <= k * np.sqrt(var)
        wr = np.take_along_axis(within, rank, axis=0)
        any_match = wr.any(axis=0)
        first = np.take_along_axis(rank, wr.argmax(axis=0)[None], axis=0)[0]
        M = np.zeros((K,) + shape, bool)
        np.put_along_axis(M, first[None], any_match[None], axis=0)
        masks.append(~(M & is_bg).any(axis=0))
        w = (1 - alpha) * w + alpha * M                # Eq. 5
        if rate == "printed":
            rho = alpha * np.exp(-0.5 * (x - mu) ** 2 / var) / np.sqrt(2 * np.pi * var)
        else:
            rho = alpha / np.maximum(w, 1e-12)
        rho = np.minimum(rho, 1.0)
        mu = np.where(M, (1 - rho) * mu + rho * x, mu)                    # Eq. 6
        var = np.where(M, (1 - rho) * var + rho * (x - mu) ** 2, var)     # Eq. 7
        var = np.maximum(var, var_min)                 # floor, as OpenCV's MOG2 (fVarMin)
        repl = np.zeros((K,) + shape, bool)            # no match: replace least probable
        np.put_along_axis(repl, rank[-1][None], (~any_match)[None], axis=0)
        mu = np.where(repl, x, mu); var = np.where(repl, var0, var); w = np.where(repl, w0, w)
        w /= w.sum(axis=0)
    return masks


def vibe(frames, N=20, R=20.0, n_min=2, phi=16, seed=0):
    """ViBe (Barnich & Van Droogenbroeck, 2011), grey level, as in their Appendix A."""
    g = np.random.default_rng(seed)
    shape = frames[0].shape
    rows, cols = np.indices(shape)

    def neighbour(r, c):                               # random 8-neighbour, clipped at borders
        d = g.integers(0, 8, r.shape)
        dr = np.array([-1, -1, -1, 0, 0, 1, 1, 1])[d]
        dc = np.array([-1, 0, 1, -1, 1, -1, 0, 1])[d]
        return np.clip(r + dr, 0, shape[0] - 1), np.clip(c + dc, 0, shape[1] - 1)

    samples = np.empty((N,) + shape)
    for i in range(N):                                 # initialise from the first frame
        r, c = neighbour(rows, cols)
        samples[i] = frames[0][r, c]
    masks = []
    for x in frames:
        count = (np.abs(samples - x) < R).sum(axis=0)
        is_bg = count >= n_min
        masks.append(~is_bg)
        upd = is_bg & (g.integers(0, phi, shape) == 0)     # update own model
        r, c = rows[upd], cols[upd]
        samples[g.integers(0, N, r.size), r, c] = x[r, c]
        upd = is_bg & (g.integers(0, phi, shape) == 0)     # update a neighbour's model
        r, c = rows[upd], cols[upd]
        nr, nc = neighbour(r, c)
        samples[g.integers(0, N, r.size), nr, nc] = x[r, c]
    return masks


def f_measure(mask, gt):
    tp = (mask & gt).sum(); fp = (mask & ~gt).sum(); fn = (~mask & gt).sum()
    return 2 * tp / (2 * tp + fp + fn)


phases = {"steady": range(50, 150), "dimming": range(150, 300), "dim": range(300, 400)}
methods = {
    "frame difference": frame_difference(frames),
    "running average, alpha 0.05": running_average(frames, 0.05),
    "running average, alpha 0.005": running_average(frames, 0.005),
    "mixture, rho = alpha * eta": stauffer_grimson(frames, "printed"),
    "mixture, rho = alpha / w": stauffer_grimson(frames, "1/w"),
    "ViBe": vibe(frames),
}
static = ~sway
print(f"{'method':30s} {'F steady':>9s} {'F dimming':>10s} {'F dim':>6s} "
      f"{'FPR sway':>9s} {'FPR rest':>9s} {'F opened':>9s}")
for name, masks in methods.items():
    Fs = [np.mean([f_measure(masks[t], truth[t]) for t in r if truth[t].any()])
          for r in phases.values()]
    late = range(50, T)
    fpr_sway = np.mean([(masks[t] & sway & ~truth[t]).sum() / (sway & ~truth[t]).sum() for t in late])
    fpr_rest = np.mean([(masks[t] & static & ~truth[t]).sum() / (static & ~truth[t]).sum() for t in late])
    opened = np.mean([f_measure(binary_opening(masks[t], np.ones((3, 3))), truth[t])
                      for t in late if truth[t].any()])
    print(f"{name:30s} {Fs[0]:9.3f} {Fs[1]:10.3f} {Fs[2]:6.3f} {fpr_sway:9.3f} {fpr_rest:9.3f} {opened:9.3f}")

# Dim phase: is a missed object pixel one whose value (0.6 * 230 = 138) the background
# itself passed through while it dimmed (between 0.6 bg and bg, with a margin of 20)?
seen = (0.6 * bg - 20 <= 138) & (138 <= bg + 20)
print("\ndim phase, miss rate of object pixels whose value the dimming background passed through / did not:")
for name, masks in methods.items():
    miss_in = [(~masks[t] & truth[t] & seen).sum() for t in phases["dim"]]
    miss_out = [(~masks[t] & truth[t] & ~seen).sum() for t in phases["dim"]]
    n_in = sum((truth[t] & seen).sum() for t in phases["dim"])
    n_out = sum((truth[t] & ~seen).sum() for t in phases["dim"])
    print(f"{name:30s} {sum(miss_in) / n_in:.2f} / {sum(miss_out) / n_out:.2f}")

Output:

method                          F steady  F dimming  F dim  FPR sway  FPR rest  F opened
frame difference                   0.081      0.062  0.112     0.354     0.001     0.001
running average, alpha 0.05        0.263      0.303  0.495     0.461     0.015     0.687
running average, alpha 0.005       0.349      0.122  0.014     0.732     0.340     0.328
mixture, rho = alpha * eta         0.646      0.219  0.144     0.335     0.125     0.521
mixture, rho = alpha / w           0.710      0.235  0.301     0.281     0.038     0.621
ViBe                               0.466      0.308  0.131     0.310     0.032     0.659

dim phase, miss rate of object pixels whose value the dimming background passed through / did not:
frame difference               0.89 / 0.87
running average, alpha 0.05    0.03 / 0.00
running average, alpha 0.005   0.93 / 0.00
mixture, rho = alpha * eta     0.96 / 0.01
mixture, rho = alpha / w       0.92 / 0.00
ViBe                           1.00 / 0.09

The run takes about 2 seconds (NumPy 2.3.5, SciPy 1.16.3, scikit-image 0.25.2). Two changes were made after the first run. The first run of the $\rho = \alpha/\omega$ variant divided by zero: a component with zero weight that matched received $\rho = 1$, its mean jumped to the new value and its variance became exactly zero. A variance floor of 4, OpenCV’s default minimum variance for MOG2, was then added to both mixture variants. The second block of output, the miss rates in the dim phase, was added after the first run to examine where the misses of that phase lie.

No method is good in all three phases, and each failure has a cause visible in the setting.

• Frame differencing finds only the leading and trailing edges of the uniform objects, strips about as wide as the objects move per frame, and fires on the swaying stripes. The opening, which removes structures narrower than three pixels, erases almost all of its detections.
• The fast running average follows the dimming: by the reasoning above its lag is about $0.3/0.05 \approx 6$ grey levels, below its threshold of 20. But one mean per pixel cannot represent the stripes, so much of the swaying region is flagged, and those false positives outnumber the object pixels and keep F low in the steady phase. The opening removes most of these narrow false detections and raises its F to the best opened value in the table. The slow average fails the other way: its lag of about 60 grey levels exceeds the threshold, so false positives spread over the static background and F collapses once the scene is dim.
• The mixtures have the best F in steady light, where several components can cover the stripes, but they drop during the dimming. By our reasoning the cause is the rate at which a matched mean moves: a mean that follows a ramp of $s$ grey levels per frame at rate $\rho$ lags by about $s/\rho$ and stays matched only while that lag is below 2.5 standard deviations. In the $\alpha/\omega$ variant a heavy component has $\rho \approx \alpha = 0.01$, so a ramp of 0.3 grey levels per frame leaves a lag of about 30 grey levels, beyond 2.5 standard deviations unless the standard deviation exceeds 12, four times the noise; the dimming background keeps spawning new components that are foreground until their weights grow. Stauffer and Grimson’s printed rate is at most $\alpha/(\sqrt{2\pi}\,\sigma) \approx \alpha/25$ for the initial standard deviation of 10, from which, as Gaussian Mixture Model’s example shows, the variance barely moves. That variant’s means hardly follow the ramp at all; it also recovers less in the dim phase and has three times the false-positive rate on the static background.
• ViBe follows the dimming better than the mixtures, by our reading because a background pixel writes its current value into its own model about once every 16 frames and receives its neighbours’ values as often, so recent samples keep two matches within 20 grey levels; it has a low false-positive rate on the static background. On the stripes it does better than the running average and falls between the two mixture variants.

The dim phase shows a failure that comes from memory rather than adaptation. The bright object that crosses in that phase, dimmed to $0.6 \times 230 = 138$ grey levels, takes values that much of the background passed through while it dimmed. Every method that remembers the brighter background, the mixtures through their old components, ViBe through samples that its random replacement keeps for a long time, and the slow average through its lag, misses 92 to 100% of such object pixels, while the fast average, which has forgotten the old brightness, misses 3%. A model that keeps old background values to recover quickly from uncovered background, the property Stauffer and Grimson designed for, will also accept a foreground object that happens to match one of them: the model’s memory creates camouflage that is not in the current scene. A short memory has the opposite cost, the absorption of slow and stopped objects that the intermittent-motion category measures.

Datasets and Benchmarks

Before CDnet, background subtraction was evaluated on small or partly labelled sets. The Wallflower dataset has 7 videos, each representing one challenge such as illumination change or background motion, with one labelled frame per video (Goyette et al., 2012, §2.1). PETS, CAVIAR, i-LIDS and ETISEO were designed for tracking and behaviour analysis and are labelled with bounding boxes or high-level events, and VSSN 2006 is semi-synthetic, with real backgrounds and artificially moving objects (§2.1). The CDnet authors argued that the lack of a common realistic benchmark let methods overfit particular scenarios and gave easily implemented methods from the late 1990s an overwhelming share of comparisons (§1).

CDnet 2012 (changedetection.net) was prepared for the IEEE Change Detection Workshop at CVPR 2012 (Goyette et al., 2012). It has 31 camera-captured videos, described in the paper as nearly 90,000 frames (about 70,000 in the website’s overview, while the per-video counts on its 2012 dataset page sum to about 88,000), in six categories chosen so that each challenge is unique to its category: Baseline (4 videos with mild challenges, provided mainly as reference), Dynamic Background (6), Camera Jitter (4), Shadows (6), Intermittent Object Motion (6) and Thermal (5, far-infrared) (§3–§3.1). Resolutions range from $320 \times 240$ to $720 \times 576$ and lengths from 1,000 to 8,000 frames (the website’s 2012 dataset page lists one thermal video of 600 frames), and one Baseline video comes from PETS 2006 while the authors captured the rest (§3).

CDnet 2014 keeps the 2012 videos and adds 22 videos with about 70,000 new frames in five categories: Bad Weather (4 videos, called Challenging Weather in the paper’s text and the website’s overview: blizzards, snow and fog), Low Framerate (4, from 0.17 to 1 frame per second), Night Videos (6, traffic with headlights), PTZ (4: continuous pan, intermittent pan, two-position patrol and zoom) and Turbulence (4, near-infrared footage of heat shimmer filmed from 5 to 15 km) (Wang et al., 2014, §3–§3.1; CDnet website, 2014 dataset). The frames were segmented by a team of 13 researchers from 7 universities (§3). For the new categories, ground truth for only the first half of each video is public, while evaluation uses all frames, a measure the organizers adopted to reduce overtuning (CDnet website, dataset overview).

Every ground-truth frame has five labels: static (0), hard shadow (50), outside the region of interest (85), unknown (170) and motion (255) (Goyette et al., 2012, §3.2). Pixels near object boundaries, half-occluded or blurred, are labelled unknown and excluded from scoring; the first few hundred frames of each video are outside the region of interest, so that errors while a model initializes are not counted, and the region of interest also excludes activity unrelated to the category, such as highway traffic behind a traffic-light scene; shadow pixels count as static (§3.2). Each video comes with its region-of-interest mask and the frame range used for scoring (CDnet website, 2014 dataset).

The workshops’ tables show how the methods in this article compare under one protocol, with one parameter set per method for all videos (Goyette et al., 2012, §4). In the 2012 overall results, the F-measures were 0.66 for Stauffer–Grimson, 0.66 for Zivkovic’s mixture, 0.67 for ViBe and 0.67 for Elgammal et al.’s kernel method in its 2002 journal version, while the pixel-based adaptive segmenter PBAS led the ranking with 0.75 (Table 1). By the median over the 18 methods, intermittent object motion was the hardest 2012 category, with a median F of 0.50, and Baseline the easiest at 0.87 (Table 2). In 2014, Stauffer–Grimson scored 0.57 and Zivkovic’s mixture 0.56 over all eleven categories, while FTSG and SuBSENSE scored 0.73 and the majority vote of the top three 0.75 (Wang et al., 2014, Table 3). The median F over the 14 methods was 0.14 on PTZ, 0.41 on night videos and 0.74 on bad weather (Table 4). From the 2012 results the organizers concluded that small recurrent background motion such as ripples and shaken trees no longer posed a significant challenge, while no method was robust to hard shadows, ghosting, intermittent motion and camouflage (§2.2).

Evaluation Metrics

CDnet counts true and false positives and negatives over the scored pixels of each video and reports seven measures (Goyette et al., 2012, §3.3; CDnet website, evaluation page):

Measure	Definition
Recall (Re)	$TP / (TP + FN)$
Specificity (Sp)	$TN / (TN + FP)$
False positive rate (FPR)	$FP / (FP + TN)$
False negative rate (FNR)	$FN / (TP + FN)$
Percentage of wrong classifications (PWC)	$100\,(FN + FP) / (TP + FN + FP + TN)$
Precision (Pr)	$TP / (TP + FP)$
F-measure	$2\,\mathrm{Pr} \cdot \mathrm{Re} / (\mathrm{Pr} + \mathrm{Re})$

Precision and recall and the F1 score are defined in their own articles. Both CDnet papers print the false negative rate as $FN/(TN + FP)$; the website gives $FN/(TP + FN)$, and the FNR column of the 2014 results equals one minus recall, as the website’s formula implies, while the much smaller FNR values in the 2012 table do not. For the Shadows category CDnet also reports FPR-S, the false-positive rate inside hard-shadow areas (§3.3).

Each measure is computed per video, averaged over the videos of a category, and the category averages are averaged again into an overall value. The authors chose this over pooling all pixels so that long or high-resolution videos do not dominate (§3.3). Methods are ranked by averaging their ranks over the seven measures within each category and then over categories (RC), and by averaging their ranks over the seven overall measures (R) (§3.3). Of the seven measures, the F-measure correlated best with the average rankings (§5), and later papers often report it alone. Since the scored pixels are mostly background, measures that include true negatives, such as specificity and PWC, are close to their best values for every method, as the 2014 table shows: specificity is 0.94 to 0.99 for all methods (Wang et al., 2014, Table 3). ViBe’s paper used the percentage of correct classification, which is $100 - \text{PWC}$ (Barnich & Van Droogenbroeck, 2011, §IV, Eq. 7).

Applications

The CDnet organizers list visual surveillance (people counting, action recognition, anomaly detection and post-event forensics), smart environments (room occupancy, fall detection and parking occupancy) and video retrieval as applications of change and motion detection, and note that detection is only a pre-processing step for tracking, classification or estimation (CDnet website, home page). Stauffer and Grimson’s system tracked and classified people and cars in outdoor scenes, and was also used to track birds at a feeder, mice at night, fish in a tank and ants on a floor (Stauffer & Grimson, 1999, §3–§4 and §6). The foreground regions feed multi-object tracking and event analysis such as video anomaly detection. ViBe’s authors embedded a reduced version in a consumer digital camera, processing six $320 \times 240$ frames per second (Barnich & Van Droogenbroeck, 2011, §IV-F).

Open Problems

• Moving cameras, night and turbulence. From error maps over all methods, the CDnet 2014 organizers listed the problems no method handled well: camera motion in PTZ videos, missed vehicles and headlight reflections at night, hard shadows, objects that stop for some time or background objects that are removed, and air turbulence (Wang et al., 2014, §5).
• Stopped objects. When a still object should become background is a matter of definition, and every update rule trades the absorption of stopped objects against the persistence of ghosts.
• Generalization of trained methods. Supervised networks reach high scores when trained on frames of the test videos, but the BSUV-Net results show how much is lost when they are not (Tezcan et al., 2020, Table 2).