Mean Shift Tracking

Mean shift tracking, also called kernel-based tracking, follows a target through a video by its colour distribution rather than by its exact appearance. The target is described by a colour histogram collected under a kernel that weights pixels near its centre more than pixels near its edge. In each new frame the tracker starts where the target was and moves a window of the same shape uphill on a similarity surface, the Bhattacharyya coefficient between the window’s histogram and the target’s, using mean shift steps. A step costs about as much as computing one histogram, and a few steps per frame are usually enough. Because a histogram ignores where the colours are, the tracker tolerates deformation, rotation and partial occlusion. For the same reason it can be fooled by anything else of the same colours.

Two methods share the name. Kernel-based tracking of Comaniciu, Ramesh and Meer (2000; 2003) derives the mean shift step from the Bhattacharyya coefficient. CAMShift, the Continuously Adaptive Mean Shift of Bradski (1998), written CAMSHIFT in the original and CamShift in OpenCV, runs flat-kernel mean shift on a probability image made by looking up each pixel’s hue in a histogram, and sets the window’s size and orientation from the image moments under it. This article covers both in depth, together with scale adaptation, background-weighted histograms, and the conditions under which the two trackers fail. The Mean Shift article covers the mode-seeking procedure itself (kernel density estimates, the mean shift vector as a normalized gradient, convergence) and gives a short account of the tracker. Object Tracking places both methods among the other families of trackers.

Problem

A single target is marked in the first frame by an ellipse or a box. The task is to report its position, and preferably its size, in every later frame, in real time and with no model of the target other than the first frame. The target may be non-rigid, such as a walking person or a turning face. It may blur, rotate, change size as it approaches or recedes, and be partly hidden. Comaniciu, Ramesh and Meer (2003, §1) split a tracker into two parts: target representation and localization, which is mostly bottom-up, and filtering and data association, which models the target’s dynamics. Their paper deals with the first part. Mean shift tracking finds the target near its last position by appearance alone, and it can be combined with a Kalman filter or a particle filter for the second.

Inputs and Outputs

Input: a video; the target’s region in the first frame; a feature space, usually RGB quantized into $m$ bins for kernel-based tracking or a one-dimensional hue histogram for CAMShift; a kernel profile; a stopping threshold and an iteration cap.
Output: the target’s centre in every frame. Kernel-based tracking with scale adaptation also gives the kernel’s bandwidth. CAMShift gives the window size and, from the second moments, an oriented ellipse. Kernel-based tracking can also report the Bhattacharyya coefficient at convergence, which measures how well the found region matches the model.

Intuition

Picture the similarity between the target’s histogram and the histogram of a window, plotted as a surface over all possible window positions. With hard-edged windows the surface is jagged. Shifting the window by one pixel swaps whole pixels in and out, so the histogram jumps, and finding the peak means testing every position. Weighting each pixel by a smooth kernel that falls to zero at the window’s edge makes the surface smooth. A pixel then enters or leaves the window gradually, and the gradient of the surface points toward the peak.

Kernel-based tracking turns that gradient into a simple rule. Give every pixel in the current window a weight: the square root of how much more common its colour is in the target than in the window. Then move the window to the weighted mean of the pixel positions. Pixels of under-represented target colours pull the window toward them, and pixels of colours the target lacks get weight zero. When the window’s colours match the target’s, the weights are balanced around the centre and the window stops.

CAMShift builds the surface differently. It first paints every pixel with the probability that its hue belongs to the target, then repeatedly moves a flat window to the centroid of that probability. The total probability under the window, its zeroth moment, works as an area: if the window holds more target-coloured mass, it grows, and if less, it shrinks.

Algorithm

Kernel-based tracking (Comaniciu, Ramesh & Meer, 2003, §4.1–§4.2). Given the target model $\hat{\mathbf q}$ and its location $\hat{\mathbf y}_0$ in the previous frame:

In the current frame, compute the candidate histogram $\hat{\mathbf p}(\hat{\mathbf y}_0)$ and its Bhattacharyya coefficient $\rho[\hat{\mathbf p}(\hat{\mathbf y}_0), \hat{\mathbf q}]$ .
Compute a weight $w_i$ for every pixel in the window (eq. 10 below).
Move to the new location $\hat{\mathbf y}_1$ , the kernel-weighted mean of the pixel positions with weights $w_i$ (eq. 11).
Compute $\hat{\mathbf p}(\hat{\mathbf y}_1)$ and $\rho[\hat{\mathbf p}(\hat{\mathbf y}_1), \hat{\mathbf q}]$ .
While $\rho$ at $\hat{\mathbf y}_1$ is smaller than at $\hat{\mathbf y}_0$ , set $\hat{\mathbf y}_1 \leftarrow \tfrac12(\hat{\mathbf y}_0 + \hat{\mathbf y}_1)$ and re-evaluate.
If $\lVert \hat{\mathbf y}_1 - \hat{\mathbf y}_0 \rVert < \epsilon$ , stop. Otherwise set $\hat{\mathbf y}_0 \leftarrow \hat{\mathbf y}_1$ and return to step 2.

In practice only steps 2, 3 and 6 are run. The authors found that the Bhattacharyya coefficient at the new location failed to increase in only 0.1% of cases, so step 5 is dropped and $\rho$ is computed once, at the end, to judge the match (§4.2). The threshold $\epsilon$ keeps $\hat{\mathbf y}_0$ and $\hat{\mathbf y}_1$ within the same pixel in original image coordinates, and a cap $N_{\max}$ , typically 20, keeps the cost per frame bounded; the average was about 4 iterations (§4.2).

CAMShift (Bradski, 1998, “CAMSHIFT Derivation”):

Convert the frame into a colour probability image by looking up each pixel’s hue in the target’s hue histogram.
Choose the initial location of the search window.
Run mean shift: move the window to the centroid of the probability under it, once or until it stops moving, and store the zeroth moment.
Set the window size to a function of the zeroth moment found in step 3.
Repeat steps 3 and 4 until the window’s centre moves less than a threshold.

For video, the converged window’s location and size seed the next frame. Bradski’s Coupled CAMSHIFT computes the probability image only in a region slightly larger than the window, which saves time when target colours do not dominate the image.

Mathematical Formulation

Target model and candidates

The target region is an ellipse. Its row and column coordinates are rescaled by $h_x$ and $h_y$ so that it becomes the unit circle centred at the origin (2003, §2.1). Let $\{\mathbf x^\star_i\}_{i=1..n}$ be these normalized pixel locations, $b(\mathbf x^\star_i) \in \{1, \dots, m\}$ the histogram bin of the pixel’s colour, and $k$ a convex, monotonically decreasing kernel profile, with $K(\mathbf x) = k(\lVert \mathbf x \rVert^2)$ . The target model is

\hat q_u = C \sum_{i=1}^{n} k\!\left(\lVert \mathbf x^\star_i \rVert^2\right) \delta\!\left[b(\mathbf x^\star_i) - u\right], \qquad C = \frac{1}{\sum_{i=1}^{n} k(\lVert \mathbf x^\star_i \rVert^2)}, \qquad \text{(2, 3)}

with $\delta$ the Kronecker delta. The authors argue that peripheral pixels are the least reliable, because they are often occluded or mixed with background, so the kernel’s down-weighting makes the estimate more robust (§2.1). A candidate centred at $\mathbf y$ in the current frame, with the same normalization and bandwidth $h$ , has

\hat p_u(\mathbf y) = C_h \sum_{i=1}^{n_h} k\!\left(\left\lVert \frac{\mathbf y - \mathbf x_i}{h} \right\rVert^2\right) \delta\!\left[b(\mathbf x_i) - u\right]. \qquad \text{(4)}

Because the pixels lie on a regular lattice and $\mathbf y$ is one of its nodes, $C_h$ does not depend on $\mathbf y$ and can be precomputed for each $h$ (§2.2). Writing the similarity $\hat\rho(\mathbf y) = \rho[\hat{\mathbf p}(\mathbf y), \hat{\mathbf q}]$ with these kernel-weighted histograms gives a function that inherits the kernel’s smoothness. A differentiable profile yields a differentiable similarity (§2.3).

The Bhattacharyya coefficient and its metric

Comaniciu, Ramesh and Meer measure similarity by the sample Bhattacharyya coefficient and define a distance from it (2003, §3):

d(\mathbf y) = \sqrt{1 - \rho[\hat{\mathbf p}(\mathbf y), \hat{\mathbf q}]}, \qquad \rho[\hat{\mathbf p}(\mathbf y), \hat{\mathbf q}] = \sum_{u=1}^{m} \sqrt{\hat p_u(\mathbf y)\, \hat q_u}. \qquad \text{(6, 7)}

$\rho$ is the cosine of the angle between the unit vectors $(\sqrt{\hat p_1}, \dots, \sqrt{\hat p_m})$ and $(\sqrt{\hat q_1}, \dots, \sqrt{\hat q_m})$ . The authors list its properties (§3): $d$ is a metric, proved in their appendix, whereas the Bhattacharyya distance and the Kullback divergence violate at least one distance axiom. It has a clear geometric meaning. It is invariant to the target’s scale up to quantization effects, because it compares normalized histograms. It is valid for arbitrary distributions, and it approximates the chi-squared statistic without the singularity that chi-squared has at empty bins. The CVPR 2000 version motivated the coefficient differently, through its close relation to the Bayes error of telling the two distributions apart (2000, §3). It also contrasted the coefficient with histogram intersection, which it called scale variant (2000, §3). The distance $\sqrt{1-\rho}$ is the Hellinger distance discussed in similarity and distance measures.

Linearization and the mean shift step

Maximizing $\rho$ is equivalent to minimizing $d$ . A Taylor expansion of each $\sqrt{\hat p_u(\mathbf y)}$ around the candidate at the previous location, $\sqrt{\hat p_u(\mathbf y)} \approx \sqrt{\hat p_u(\hat{\mathbf y}_0)} + \bigl(\hat p_u(\mathbf y) - \hat p_u(\hat{\mathbf y}_0)\bigr) / \bigl(2\sqrt{\hat p_u(\hat{\mathbf y}_0)}\bigr)$ , gives (§4.1)

\rho[\hat{\mathbf p}(\mathbf y), \hat{\mathbf q}] \approx \frac12 \sum_{u=1}^{m} \sqrt{\hat p_u(\hat{\mathbf y}_0)\, \hat q_u} + \frac12 \sum_{u=1}^{m} \hat p_u(\mathbf y) \sqrt{\frac{\hat q_u}{\hat p_u(\hat{\mathbf y}_0)}} . \qquad \text{(8)}

The approximation holds while the candidate’s histogram does not change drastically from $\hat{\mathbf p}(\hat{\mathbf y}_0)$ , which the authors take to be the usual case between consecutive frames. Bins with $\hat p_u(\hat{\mathbf y}_0) = 0$ are simply not used. Substituting eq. 4 turns the second term into a sum over pixels:

\rho \approx \frac12 \sum_{u=1}^{m} \sqrt{\hat p_u(\hat{\mathbf y}_0)\, \hat q_u} + \frac{C_h}{2} \sum_{i=1}^{n_h} w_i\, k\!\left(\left\lVert \frac{\mathbf y - \mathbf x_i}{h} \right\rVert^2\right), \qquad w_i = \sum_{u=1}^{m} \sqrt{\frac{\hat q_u}{\hat p_u(\hat{\mathbf y}_0)}}\, \delta\!\left[b(\mathbf x_i) - u\right]. \qquad \text{(9, 10)}

The first term does not depend on $\mathbf y$ . The second is a kernel density estimate over pixel positions, with pixel $i$ weighted by $w_i$ . Its local mode is found by mean shift, with $g(x) = -k'(x)$ (§4.1):

\hat{\mathbf y}_1 = \frac{\sum_{i=1}^{n_h} \mathbf x_i\, w_i\, g\!\left(\left\lVert \frac{\hat{\mathbf y}_0 - \mathbf x_i}{h} \right\rVert^2\right)}{\sum_{i=1}^{n_h} w_i\, g\!\left(\left\lVert \frac{\hat{\mathbf y}_0 - \mathbf x_i}{h} \right\rVert^2\right)}. \qquad \text{(11)}

The recommended Epanechnikov profile, $k(x) = \tfrac12 c_d^{-1}(d+2)(1-x)$ for $x \le 1$ and 0 otherwise, has a constant derivative. Equation 11 then reduces to the weighted average $\hat{\mathbf y}_1 = \sum_i \mathbf x_i w_i / \sum_i w_i$ (eqs. 12–13). Each step therefore climbs the linearized objective, not $\rho$ itself, which is why step 5 of the algorithm exists. The weight $w_i$ takes one value per colour bin, so the step is a histogram ratio looked up at every pixel, followed by a centroid. The authors also read the procedure as matched filtering: $\rho$ is the correlation between the unit vectors $\sqrt{\hat{\mathbf q}}$ and $\sqrt{\hat{\mathbf p}(\mathbf y)}$ , and mean shift finds a local maximum of that field of correlation coefficients (§4.2).

Mean shift finds a zero of the gradient, which could be a saddle point. The authors argue that saddle points are unstable and that image noise perturbs each frame independently, so saddle points do not affect tracking over a sequence (§4.2). They call the region from which the procedure reaches the target the operational basin of attraction. Because of the kernel, it is at least as large as the target model: if the target’s centre in the current frame lies inside the area the model covered in the previous frame, the local maximum is a reliable indicator, provided the representation is discriminative enough to give a unique maximum nearby (§4.2).

CAMShift: back-projection and moments

CAMShift works on a probability image $I(x, y)$ . Bradski (1998) builds a one-dimensional histogram of the hue channel of HSV from sampled skin pixels, and during tracking uses it as a lookup table, with values scaled from 0 to the histogram’s maximum (255 for 8-bit images). This lookup is histogram back-projection. Hue is chosen because HSV separates hue from saturation and brightness. Bradski reports that an earlier model in normalized $(r, g)$ space was much more sensitive to lighting changes (“Color Probability Distributions”). Pixels whose brightness is very low or very high, or whose saturation is very low, are ignored because their hue is undefined or noisy. The thresholds are set at 10% of the maximum pixel value (“Implementation Details”). Within the search window, the moments are

M_{00} = \sum_{x,y} I(x,y), \quad M_{10} = \sum_{x,y} x\, I(x,y), \quad M_{01} = \sum_{x,y} y\, I(x,y), \quad (x_c, y_c) = \left(\frac{M_{10}}{M_{00}}, \frac{M_{01}}{M_{00}}\right),

and the centroid $(x_c, y_c)$ is the mean shift step of a flat kernel. CAMShift’s addition is the size rule. Bradski treats $M_{00}$ as the probability “area” under the window. He divides it by the maximum pixel value to count pixels, takes the square root to get a length, and multiplies by two so that the window grows to cover the whole connected region. Our reading of that prose is $s = 2\sqrt{M_{00}/256}$ for 8-bit probabilities. The equation itself is an image on the archived page, which we could not read. The result is rounded up to an odd number with a minimum of 3. For faces Bradski used width $s$ and length $1.2s$ . To keep the window from overshooting, he lowered the hue histogram by 20 to 80 (out of 255), which shrinks the window to just inside the object and reduces noise.

The second moments give the blob’s orientation and extent. Bradski uses this to track head roll, and in his description the first two eigenvalues give the length and width (“Calculation of Head Roll”). OpenCV 4.10.0’s cv::CamShift uses the normalized central moments $a = \mu_{20}/M_{00}$ , $b = \mu_{11}/M_{00}$ , $c = \mu_{02}/M_{00}$ :

\theta = \operatorname{atan2}\!\left(2b,\; a - c + \sqrt{4b^2 + (a-c)^2}\right), \qquad \text{length}, \text{width} = 4\sqrt{\lambda_{1,2}},

where $\lambda_{1,2}$ are the variances along and across $\theta$ , the eigenvalues of the moment matrix. This $\theta$ equals $\tfrac12 \operatorname{atan2}(2b, a-c)$ by the half-angle identity. Four standard deviations span the full axis of a uniformly filled ellipse, since its variance along a semi-axis $A$ is $A^2/4$ (our arithmetic). OpenCV also sets the window size differently from Bradski’s text. After cv::meanShift converges, the window is enlarged by 10 pixels on each side, the moments are computed there, and the next window’s width (height) is the larger of the two axes’ projections onto the image’s horizontal (vertical) axis, plus 2 pixels. The zeroth moment is not used for the size. The two rules are compared in the example below.

Comaniciu, Ramesh and Meer (2003, §7), citing Bradski’s WACV 1998 paper, objected that projecting the model histogram directly onto the frame can introduce a large bias in the estimated location, and that the resulting measure is scale variant. One way to see this (our reasoning): the probability image scores each pixel independently, so a window full of the target’s most common colour scores higher than one that reproduces the target’s colour mix, whereas the Bhattacharyya objective compares the whole distribution.

Scale Adaptation

Kernel-based tracking adapts the bandwidth by search (2003, §4.3). Because the Bhattacharyya coefficient is scale invariant, the localization is run three times, with $h = h_{\text{prev}}$ and $h = h_{\text{prev}} \pm \Delta h$ , typically $\Delta h = 0.1\, h_{\text{prev}}$ . The bandwidth $h_{\text{opt}}$ with the largest $\rho$ is retained. To avoid over-sensitive adaptation it is filtered,

h_{\text{new}} = \gamma\, h_{\text{opt}} + (1 - \gamma)\, h_{\text{prev}}, \qquad \gamma = 0.1 \text{ by default}. \qquad \text{(14)}

It follows from eq. 14 that the bandwidth can change by at most $\gamma \cdot 10\% = 1\%$ per frame with the default settings (our arithmetic). That is enough for targets that change size slowly but too little for one that doubles in size within a few dozen frames, as the example shows. The 2000 paper described the same scheme as a ±10% change of the radius with an infinite impulse response filter (2000, §4.3). For real-time face tracking the 2003 paper added a second score based on the image gradient perpendicular to the border of the hypothesized face, and chose the scale that maximized the sum of the normalized colour and gradient scores (§6.3).

Scale selection by $\rho$ alone has a weakness that the scale invariance hides (our reasoning). For a target of uniform colour, any window that lies entirely inside the target has the same histogram as the target, so $\rho$ cannot prefer the window that covers the whole target over a smaller one inside it. Only windows that spill into the background are penalized. A target whose colour mix changes from centre to edge, like the two-colour target in the example, gives $\rho$ a peak at the right scale. A later paper by Collins (2003), “Mean-Shift Blob Tracking through Scale Space”, could not be read for this article.

CAMShift’s scale comes for free from the moments and needs no extra searches. Bradski also argues that it removes the need for a motion predictor: an object near the camera can move fast in the image, but it also looks large, so the window is large too; a distant object is small but moves slowly across the image (“How CAMSHIFT Deals with Image Problems”).

Background-Weighted Histograms

A target region drawn by hand usually includes some background, and colours shared by the target and its surroundings make localization less reliable. Comaniciu, Ramesh and Meer (2003, §6.1) compute a background histogram $\{\hat o_u\}$ in a region around the target, of three times the target’s area in their experiments. Let $\hat o^\ast$ be its smallest non-zero entry. The weights

v_u = \min\!\left(\frac{\hat o^\ast}{\hat o_u}, 1\right) \qquad \text{(17)}

are small for colours that are prominent in the background, and the authors note they resemble the ratio histogram that Swain and Ballard used for back-projection. They multiply both the target model and every candidate by $v_u$ and renormalize (eqs. 18–21). On their Ball sequence, a ping-pong ball that moves farther than its own size between frames, this let them initialize the model with a $21 \times 31$ region, larger than the ball, which gave a large enough basin of attraction while suppressing the background colours (§6.1).

Ning, Zhang, Zhang and Wu (2012) proved that this background-weighted histogram (BWH) does not change the mean shift step. With BWH, a pixel of bin $u'$ gets the weight $w'_i = \sqrt{\hat q'_{u'} / \hat p'_{u'}}$ . Both the numerator and the denominator carry the factor $v_{u'}$ , which cancels. What remains is $w_i$ times the square root of a ratio of normalization constants, the same factor for every pixel in the window. The weighted mean of eq. 13 is unchanged by a common scale factor, so tracking with BWH gives exactly the same locations as tracking without it (their §3.1, eqs. 9–12). Their fix, the corrected background-weighted histogram (CBWH), transforms only the target model. The weights then become $w''_i = \sqrt{v_{u'}}\, w_i$ up to a constant, so pixels of background-prominent colours really lose influence (§3.2, eqs. 13–15). They also update the background model when the Bhattacharyya coefficient between the current and stored background histograms falls below a threshold, 0.5 by default (§3.3).

Ning et al. tested the two methods in MATLAB with RGB quantized into $16 \times 16 \times 16$ bins and the Epanechnikov kernel, on four sequences with hand-labelled ground truth. On the ping-pong ball sequence, initialized with a $27 \times 31$ region that included much background, they reported a mean centre error of 1.94 pixels (standard deviation 2.44) for CBWH against 11.20 (20.64) for BWH. On a soccer sequence where the player’s green shirt resembles the lawn, they reported 4.62 against 51.12. On a table-tennis player with a deliberately poor initialization, 3.89 against 15.41. On a face sequence with background updating, 3.65 against 7.83 (their Table 2). For the ball sequence their text gives an average of 3.04 iterations per frame for CBWH, while their Table 1 gives 3.74; BWH needed 8.14 in both. One point about the cancellation follows from the derivation (our reasoning). It concerns only the location step. The Bhattacharyya coefficient itself does change under BWH, so scale selection by $\rho$ , which the 2003 paper said background information could disturb (§6.1), is affected.

Parameters

Feature space and bins. The 2003 experiments used RGB with $16 \times 16 \times 16$ bins (§5), the 2000 paper $32 \times 32 \times 32$ , and the face tracker normalized $rg$ with $128 \times 128$ bins (2003, §6.3). More bins make the model more discriminative, but they make the histogram of a small target sparse and sensitive to noise. CAMShift uses hue only, which tolerates lighting changes but cannot separate colours of the same hue.
Kernel profile and bandwidth. The Epanechnikov profile makes each step a plain weighted mean. The bandwidth sets the window and so the basin of attraction, and it should match the target’s size, or be adapted (Scale Adaptation).
Stopping threshold and iteration cap. Sub-pixel thresholds give sub-pixel accuracy at more iterations; $N_{\max} = 20$ bounds the cost per frame.
Scale step and filter. $\Delta h = 0.1h$ and $\gamma = 0.1$ trade responsiveness against jitter.
Background region. For BWH and CBWH, the size of the ring around the target (three times the target’s area in both papers) and, for CBWH, the update threshold.
CAMShift. The hue bins, the saturation and brightness thresholds, the window-size function of $M_{00}$ (or OpenCV’s moment rule), and the downward shift of the histogram that Bradski used to control the window’s size.

Complexity

Each mean shift iteration computes one weighted histogram, at about the cost of an unweighted one because the kernel values are precomputed, plus the weighted centroid. Comaniciu, Ramesh and Meer give the mean cost for one scale as $C_O = N(c_H + n_h c_S) \approx N n_h c_S$ , with $N$ the average number of iterations, $n_h$ the number of target pixels, $c_H$ the cost of a histogram, and $c_S$ the cost of an addition, a square root and a division (2003, eq. 15). An exhaustive search of the basin of attraction, with histograms and coefficients updated incrementally as the window slides, costs about $2 n_h \sqrt{n_h}\, c_S$ (eq. 16). For a $50 \times 50$ target and $N = 4.19$ the ratio is $2 \cdot 50 / 4.19 \approx 24$ (§4.4). An optimized implementation with scale adaptation, which runs three optimizations per frame, ran at 150 frames per second on a 1 GHz PC and could track up to five targets in real time; without scale adaptation the authors say the numbers should be multiplied by three (§4.4). The 2000 paper’s Java implementation ran at 30 frames per second on a 600 MHz PC (2000, §5). CAMShift’s cost is a lookup per pixel in the region and a few moment sums per iteration.

Implementation

The example compares the trackers on a synthetic video whose ground truth is known in every frame. The target is an orange disk with a magenta core of half its radius. Over 61 frames it moves across a background of blue, green, grey and teal blocks, while its radius grows from 10 to 22 pixels and shrinks back. An orange disk of radius 12, with no magenta, crosses the frame at 4 pixels per frame and passes the target at frame 30, when the target is largest. In the pass-by scenario it passes 4 pixels above the target’s edge. In the cross-over scenario it passes in front of the target and hides part of its upper half. Every frame gets Gaussian noise with standard deviation 0.03.

The trackers are all initialized with the true centre and size:

kernel-based tracking with a fixed bandwidth, as in eqs. 2–13, with RGB in $16^3$ bins as in the 2003 experiments;
the same tracker with BWH and with CBWH, both using a background ring from $r$ to $2r$ (three times the target’s area);
scale adaptation by eq. 14 with the paper’s default $\gamma = 0.1$ , and with $\gamma = 1$ (no smoothing), a second value of the parameter that the paper does not report, planned before the first run;
CAMShift with a 16-bin hue histogram and Bradski’s 10% saturation and brightness thresholds, under two window rules: Bradski’s zeroth-moment rule $s = 2\sqrt{M_{00}}$ (probabilities scaled to $[0, 1]$ ), and a port of OpenCV 4.10.0’s cv::CamShift.

The window rule is a modelling choice on which the sources differ, so both are printed. For both CAMShift variants, the reported box is the axis-aligned bounding box of the moment ellipse: its width and height are four standard deviations of the probability along each image axis. The mean shift trackers report the square circumscribing the kernel. Scores are the centre error and the intersection over union with the true box, $2r \times 2r$ , over frames 1–60. The noise seeds 0–4 are looped, and the per-frame details are for seed 0.

import numpy as np
from skimage.color import rgb2hsv

# Synthetic video: a two-colour target that grows and shrinks, and an orange distractor.
H, W, T = 180, 240, 61
ORANGE, MAGENTA = np.array([0.85, 0.45, 0.12]), np.array([0.8, 0.2, 0.7])
PAL = np.array([[0.2, 0.3, 0.7], [0.25, 0.6, 0.3], [0.5, 0.5, 0.5], [0.2, 0.55, 0.6]])
yy, xx = np.mgrid[0:H, 0:W]
blocks = np.random.default_rng(100).integers(0, 4, (H // 10, W // 10))
BG = PAL[blocks[yy // 10, xx // 10]]                  # blue, green, grey, teal blocks

def truth(t):                                          # centre (row, col) and radius
    return np.array([90 - 20 * np.sin(np.pi * t / 60), 50 + 2.3 * t]), 10 + 12 * np.sin(np.pi * t / 60)

def video(yd, seed):                                   # distractor row yd, passes at t = 30
    rng = np.random.default_rng(seed)
    frames = []
    for t in range(T):
        img = BG.copy(); c, r = truth(t)
        d2 = (yy - c[0]) ** 2 + (xx - c[1]) ** 2
        img[d2 <= r ** 2] = ORANGE                     # orange disk with a magenta core
        img[d2 <= (r / 2) ** 2] = MAGENTA
        img[(yy - yd) ** 2 + (xx - (119 + 4 * (30 - t))) ** 2 <= 12 ** 2] = ORANGE
        frames.append(np.clip(img + rng.normal(0, 0.03, img.shape), 0, 1))
    return frames

# ---- Kernel-based tracking (Comaniciu, Ramesh & Meer, 2003) ----
B = 16                                                 # RGB quantized to 16 x 16 x 16 bins
def rgb_bins(img):
    q = np.minimum((img * B).astype(int), B - 1)
    return (q[..., 0] * B + q[..., 1]) * B + q[..., 2]

def disk(c, h):
    """Pixels within distance h of c, and their Epanechnikov profile k = 1 - ||x - c||^2 / h^2."""
    R = int(np.ceil(h)); r0, c0 = int(round(c[0])), int(round(c[1]))
    ys, xs = np.mgrid[r0 - R:r0 + R + 1, c0 - R:c0 + R + 1]
    d2 = ((ys - c[0]) ** 2 + (xs - c[1]) ** 2) / h ** 2
    keep = (d2 < 1) & (ys >= 0) & (ys < H) & (xs >= 0) & (xs < W)
    return ys[keep], xs[keep], 1 - d2[keep]

def khist(b, c, h, v=None):                            # eqs. (2), (4); with v: eqs. (18), (20)
    ys, xs, k = disk(c, h)
    p = np.bincount(b[ys, xs], weights=k, minlength=B ** 3)
    if v is not None:
        p = p * v
    return p / p.sum()

def locate(b, q, c, h, v_cand=None, eps=0.5, n_max=20):
    """Maximize the Bhattacharyya coefficient by mean shift from c; return (centre, rho)."""
    for _ in range(n_max):
        p = khist(b, c, h, v_cand)
        ys, xs, _ = disk(c, h)
        w = np.sqrt(q[b[ys, xs]] / np.maximum(p[b[ys, xs]], 1e-12))   # weights, eq. (10)
        if w.sum() == 0:
            break
        new = np.array([ys @ w, xs @ w]) / w.sum()     # Epanechnikov profile: eq. (13)
        done = np.linalg.norm(new - c) < eps
        c = new
        if done:
            break
    return c, np.sqrt(khist(b, c, h, v_cand) * q).sum()

def background_weights(b, c, r):                       # eq. (17), background = annulus r..2r
    d2 = (yy - c[0]) ** 2 + (xx - c[1]) ** 2
    o = np.bincount(b[(d2 > r ** 2) & (d2 <= 4 * r ** 2)], minlength=B ** 3).astype(float)
    o /= o.sum()
    with np.errstate(divide="ignore"):
        return np.minimum(o[o > 0].min() / o, 1.0)     # v_u = min(o*/o_u, 1); o_u = 0 gives 1

def track_ms(frames, mode="plain", gamma=None):
    c, h = truth(0)
    b = rgb_bins(frames[0])
    v = background_weights(b, c, h) if mode != "plain" else None
    q = khist(b, c, h, v)                              # BWH and CBWH both weight the model
    v_cand = v if mode == "bwh" else None              # only BWH weights the candidates
    boxes = [(c, h, h)]
    for img in frames[1:]:
        b = rgb_bins(img)
        if gamma is None:                              # fixed bandwidth
            c, _ = locate(b, q, c, h, v_cand)
        else:                                          # Section 4.3: h, h +- 10 %, eq. (14)
            runs = [locate(b, q, c, hh) + (hh,) for hh in (h, 1.1 * h, 0.9 * h)]
            c, _, h_opt = max(runs, key=lambda run: run[1])
            h = gamma * h_opt + (1 - gamma) * h
        boxes.append((c, h, h))
    return boxes

# ---- CAMShift (Bradski, 1998): hue histogram back-projection and moments ----
NH = 16
def hue(img):                                          # hue bin, and pixels where hue is usable
    hsv = rgb2hsv(img)
    ok = (hsv[..., 1] >= 0.1) & (hsv[..., 2] >= 0.1) & (hsv[..., 2] <= 0.9)
    return np.minimum((hsv[..., 0] * NH).astype(int), NH - 1), ok

def moments(P, y0, y1, x0, x1):
    y0, x0, y1, x1 = max(y0, 0), max(x0, 0), min(y1, H), min(x1, W)
    sub = P[y0:y1, x0:x1]
    m00 = sub.sum()
    if m00 <= 1e-12:
        return None
    ys, xs = np.mgrid[y0:y1, x0:x1]
    cy, cx = (sub * ys).sum() / m00, (sub * xs).sum() / m00
    vyy, vxx = (sub * (ys - cy) ** 2).sum() / m00, (sub * (xs - cx) ** 2).sum() / m00
    vxy = (sub * (ys - cy) * (xs - cx)).sum() / m00
    return m00, cy, cx, vyy, vxx, vxy

def camshift_m0(P, c, s):
    """Zeroth-moment window rule: square window of side s = 2 sqrt(M00), odd, at least 3."""
    for _ in range(10):
        for _ in range(10):                            # mean shift: move window to the centroid
            m = moments(P, int(round(c[0] - s / 2)), int(round(c[0] + s / 2)) + 1,
                        int(round(c[1] - s / 2)), int(round(c[1] + s / 2)) + 1)
            if m is None:
                return c, s, None
            shift = np.hypot(m[1] - c[0], m[2] - c[1]); c = np.array(m[1:3])
            if shift < 1:
                break
        s_new = max(3, int(np.ceil(2 * np.sqrt(m[0]))))
        s_new += 1 - s_new % 2
        if s_new == s and shift < 1:
            break
        s = s_new
    return c, s, m

def camshift_cv(P, x, y, w, h, tol=10):
    """Port of cv::CamShift (OpenCV 4.10.0): window from the second moments."""
    for _ in range(10):                                # cv::meanShift, criteria (10 iterations, 1 px)
        m = moments(P, y, y + h, x, x + w)
        if m is None:
            break
        dx, dy = int(round(m[2] - x - w * 0.5)), int(round(m[1] - y - h * 0.5))
        nx, ny = min(max(x + dx, 0), W - w), min(max(y + dy, 0), H - h)
        dx, dy, x, y = nx - x, ny - y, nx, ny
        if dx * dx + dy * dy < 1:
            break
    x0, y0 = max(x - tol, 0), max(y - tol, 0)          # enlarge by 10 px, then moments
    m = moments(P, y0, min(y0 + h + 2 * tol, H), x0, min(x0 + w + 2 * tol, W))
    if m is None:
        return x, y, w, h, None, None
    m00, cy, cx, vyy, vxx, vxy = m
    xc, yc = int(round(cx)), int(round(cy))
    a, b, cc = vxx, vxy, vyy
    theta = np.arctan2(2 * b, a - cc + np.sqrt(4 * b * b + (a - cc) ** 2))
    cs, sn = np.cos(theta), np.sin(theta)
    length = 4 * np.sqrt(max(cs * cs * a + 2 * cs * sn * b + sn * sn * cc, 0))
    width = 4 * np.sqrt(max(sn * sn * a - 2 * cs * sn * b + cs * cs * cc, 0))
    if length < width:
        length, width, cs, sn = width, length, sn, cs
    w = min(max(int(round(abs(length * cs))), int(round(abs(width * sn)))) + 2, (W - xc) * 2)
    h = min(max(int(round(abs(length * sn))), int(round(abs(width * cs)))) + 2, (H - yc) * 2)
    x, y = max(0, xc - w // 2), max(0, yc - h // 2)
    w, h = min(W - x, w), min(H - y, h)
    return x, y, w, h, np.array([y + h / 2, x + w / 2]), m

def track_camshift(frames, rule):
    c, r = truth(0)
    hb, ok = hue(frames[0])
    hist = np.bincount(hb[ok & ((yy - c[0]) ** 2 + (xx - c[1]) ** 2 <= r ** 2)], minlength=NH)
    hist = hist / hist.max()                           # back-projection scaled to [0, 1]
    s = 2 * int(round(r)) + 1
    x, y, w, h = int(round(c[1] - r)), int(round(c[0] - r)), s, s
    boxes = [(c, r, r)]
    for img in frames[1:]:
        hb, ok = hue(img)
        P = hist[hb] * ok                              # colour probability image
        if rule == "m0":
            c, s, m = camshift_m0(P, c, s)
        else:
            x, y, w, h, centre, m = camshift_cv(P, x, y, w, h)
            c = centre if centre is not None else c
        if m is not None:                              # box: 4 sigma extents of the blob
            boxes.append((c, 2 * np.sqrt(m[3]), 2 * np.sqrt(m[4])))
        else:
            boxes.append(boxes[-1])
    return boxes

# ---- Scoring: centre error and box IoU against the true disk's box ----
def iou(b1, b2):
    (c1, hh1, hw1), (c2, hh2, hw2) = b1, b2
    ih = max(0, min(c1[0] + hh1, c2[0] + hh2) - max(c1[0] - hh1, c2[0] - hh2))
    iw = max(0, min(c1[1] + hw1, c2[1] + hw2) - max(c1[1] - hw1, c2[1] - hw2))
    inter = ih * iw
    return inter / (4 * hh1 * hw1 + 4 * hh2 * hw2 - inter)

TRACKERS = {
    "mean shift, fixed h":        lambda f: track_ms(f),
    "  + BWH":                    lambda f: track_ms(f, "bwh"),
    "  + CBWH":                   lambda f: track_ms(f, "cbwh"),
    "mean shift, scale, g = 0.1": lambda f: track_ms(f, gamma=0.1),
    "mean shift, scale, g = 1":   lambda f: track_ms(f, gamma=1.0),
    "CAMShift, M00 window":       lambda f: track_camshift(f, "m0"),
    "CAMShift, OpenCV window":    lambda f: track_camshift(f, "cv"),
}

def score(boxes):
    gt = [(truth(t)[0], truth(t)[1], truth(t)[1]) for t in range(T)]
    err = np.array([np.linalg.norm(b[0] - g[0]) for b, g in zip(boxes, gt)])[1:]
    ov = np.array([iou(b, g) for b, g in zip(boxes, gt)])[1:]
    return err, ov

SEEDS = [0, 1, 2, 3, 4]
for name, yd in [("pass-by (closest gap 4 px)", 32.0), ("cross-over (distractor in front)", 56.0)]:
    results = {k: [] for k in TRACKERS}
    for seed in SEEDS:
        frames = video(yd, seed)
        for k, f in TRACKERS.items():
            results[k].append(f(frames))
    print(f"\n{name}; seed 0 in detail, mean IoU range over seeds {SEEDS[0]}-{SEEDS[-1]}")
    print(f"{'tracker':28s} {'centre err':>10s} {'IoU':>5s} {'IoU>=0.5':>9s} {'IoU t=20-40':>12s} {'IoU, 5 seeds':>13s}")
    for k in TRACKERS:
        err, ov = score(results[k][0])
        rng_iou = [score(bx)[1].mean() for bx in results[k]]
        print(f"{k:28s} {err.mean():8.1f}px {ov.mean():5.2f} {np.sum(ov >= 0.5):6d}/60 {ov[19:40].mean():12.2f}"
              f"   {min(rng_iou):.2f}-{max(rng_iou):.2f}")
    bwh = max(np.abs(a[0] - b[0]).max() for s in range(len(SEEDS))
              for a, b in zip(results["mean shift, fixed h"][s], results["  + BWH"][s]))
    print(f"largest position difference, BWH vs plain, all seeds: {bwh:.1e} px")
    ts = [0, 10, 20, 25, 30, 35, 40, 50, 60]
    print("box width at t =", ts, "(seed 0)")
    print(f"  {'true 2r':26s}", [round(2 * truth(t)[1]) for t in ts])
    for k in ["mean shift, scale, g = 0.1", "mean shift, scale, g = 1", "CAMShift, M00 window", "CAMShift, OpenCV window"]:
        print(f"  {k:26s}", [round(2 * results[k][0][t][2]) for t in ts])
    for k in ["mean shift, fixed h", "CAMShift, M00 window", "CAMShift, OpenCV window"]:
        err, _ = score(results[k][0])
        print(f"  centre error t=22..40, {k}:", np.round(err[21:40]).astype(int).tolist())

pass-by (closest gap 4 px); seed 0 in detail, mean IoU range over seeds 0-4
tracker                      centre err   IoU  IoU>=0.5  IoU t=20-40  IoU, 5 seeds
mean shift, fixed h               8.1px  0.37     12/60         0.22   0.37-0.37
  + BWH                           8.1px  0.37     12/60         0.22   0.37-0.37
  + CBWH                          8.1px  0.37     12/60         0.22   0.37-0.37
mean shift, scale, g = 0.1        5.5px  0.52     24/60         0.36   0.49-0.52
mean shift, scale, g = 1          0.7px  0.94     60/60         0.94   0.93-0.94
CAMShift, M00 window              2.7px  0.71     51/60         0.56   0.71-0.71
CAMShift, OpenCV window           2.0px  0.70     53/60         0.63   0.69-0.71
largest position difference, BWH vs plain, all seeds: 2.0e-11 px
box width at t = [0, 10, 20, 25, 30, 35, 40, 50, 60] (seed 0)
  true 2r                    [20, 32, 41, 43, 44, 43, 41, 32, 20]
  mean shift, scale, g = 0.1 [20, 22, 24, 25, 26, 26, 27, 29, 27]
  mean shift, scale, g = 1   [20, 32, 39, 43, 43, 43, 39, 31, 21]
  CAMShift, M00 window       [20, 35, 46, 71, 47, 71, 46, 36, 23]
  CAMShift, OpenCV window    [20, 35, 46, 48, 45, 65, 45, 37, 29]
  centre error t=22..40, mean shift, fixed h: [11, 11, 12, 11, 12, 11, 12, 12, 12, 11, 11, 12, 11, 11, 10, 11, 11, 11, 11]
  centre error t=22..40, CAMShift, M00 window: [0, 0, 4, 14, 12, 11, 11, 10, 10, 10, 10, 11, 12, 13, 15, 0, 0, 1, 1]
  centre error t=22..40, CAMShift, OpenCV window: [1, 1, 1, 1, 1, 2, 4, 9, 10, 10, 10, 11, 12, 10, 8, 2, 0, 1, 1]

cross-over (distractor in front); seed 0 in detail, mean IoU range over seeds 0-4
tracker                      centre err   IoU  IoU>=0.5  IoU t=20-40  IoU, 5 seeds
mean shift, fixed h               8.0px  0.37     12/60         0.22   0.37-0.37
  + BWH                           8.0px  0.37     12/60         0.22   0.37-0.37
  + CBWH                          8.0px  0.37     12/60         0.22   0.37-0.37
mean shift, scale, g = 0.1        5.4px  0.52     24/60         0.36   0.49-0.52
mean shift, scale, g = 1          0.8px  0.92     60/60         0.91   0.92-0.93
CAMShift, M00 window              1.8px  0.74     56/60         0.65   0.74-0.75
CAMShift, OpenCV window          18.1px  0.49     35/60         0.61   0.49-0.50
largest position difference, BWH vs plain, all seeds: 9.7e-12 px
box width at t = [0, 10, 20, 25, 30, 35, 40, 50, 60] (seed 0)
  true 2r                    [20, 32, 41, 43, 44, 43, 41, 32, 20]
  mean shift, scale, g = 0.1 [20, 22, 24, 25, 26, 27, 28, 29, 27]
  mean shift, scale, g = 1   [20, 32, 39, 43, 39, 42, 38, 31, 20]
  CAMShift, M00 window       [20, 35, 46, 71, 49, 71, 46, 36, 23]
  CAMShift, OpenCV window    [20, 35, 46, 68, 47, 71, 125, 256, 337]
  centre error t=22..40, mean shift, fixed h: [11, 11, 12, 11, 12, 11, 12, 12, 12, 11, 11, 12, 11, 11, 10, 11, 11, 11, 11]
  centre error t=22..40, CAMShift, M00 window: [0, 2, 11, 10, 7, 5, 4, 2, 1, 2, 3, 5, 8, 9, 11, 10, 0, 1, 1]
  centre error t=22..40, CAMShift, OpenCV window: [1, 1, 3, 8, 7, 5, 4, 2, 1, 2, 3, 6, 7, 10, 10, 12, 14, 17, 19]

The run takes about 9 seconds with NumPy 2.3.5 and scikit-image 0.25.2, and two runs gave identical output.

BWH changes nothing, as Ning et al. proved. The positions with and without background weighting agree to about $10^{-11}$ pixels, which is floating-point rounding, in every seed and both scenarios. CBWH gives the same numbers as the plain tracker here. In this scene no target colour occurs in the ring around the first frame’s target, so every target bin keeps $v_u = 1$ and the model barely changes. The benefit Ning et al. reported comes from initial regions that contain background, which this example does not test.

A fixed bandwidth loses the box and biases the centre. Kernel-based tracking with $h = 10$ stays on the target in the printed frames of both scenarios, but its box covers only about a fifth of the grown target’s box and its centre sits 10–12 pixels from the true centre while the target is large. The model was built from the whole small target, about half orange and half magenta under the kernel. A small window at the centre of the grown target sees mostly magenta, so the Bhattacharyya coefficient peaks where the window straddles the core’s edge and reproduces the model’s colour mix (our reading of the numbers). The location error here comes from the scale mismatch, not from the distractor.

Scale adaptation works only if it can keep up. With the paper’s $\gamma = 0.1$ the bandwidth crawls from 20 to 26 pixels wide while the target grows to 44, about the 1% per frame that eq. 14 allows. With $\gamma = 1$ the three-scale search follows the target’s size within a few pixels in both directions and gives the best scores of all trackers, with every frame above 0.5 IoU. For this two-colour target $\rho$ peaks at the right scale. The default smoothing, chosen to suppress jitter, is what limits the growth.

CAMShift tracks scale but absorbs the distractor, and the window rule decides whether it recovers. Both CAMShift variants follow the growth and shrinkage while the target is alone. Their boxes are slightly too large, probably because the orange ring has higher probability than the magenta core and so weights the outer pixels (our reasoning). When the distractor comes close, its orange is as probable as the target’s own, and both windows reach across the gap. At frame 25 or 35, or both, the boxes stretch to 65–71 pixels toward the distractor, and the centre is pulled up to 15 pixels off for up to a dozen frames. In pass-by both variants recover once the distractor has moved on. In cross-over the zeroth-moment rule recovers, but the OpenCV rule’s window keeps growing after frame 35, its centre error rises through frames 36–40, and by frame 50 its box is wider than the frame, and the target is lost. A plausible mechanism, which is our reasoning and was not tested separately: the OpenCV rule sizes the next window from the spread of probability in a window enlarged by 10 pixels. The departing distractor, and the grey pixels whose noisy hue lands in the target’s bins, then widen each window in turn. The zeroth-moment rule grows only with the square root of the mass, however far it is spread. Bradski’s claim that a locked-on CAMShift ignores nearby non-connected distractors held only in part at this distance.

The comparison favours the RGB tracker by design: the distractor lacks the target’s magenta, which only the colour-mix comparison of the Bhattacharyya coefficient can use. The difference between the two families is consistent with Comaniciu, Ramesh and Meer’s critique of back-projection (our reading). The Mean Shift article’s tracking example covers the other failure: a target that moves farther than the basin of attraction, after which the window locks onto a similar-coloured distractor.

Properties and Behavior

Fast and deterministic. A few histogram evaluations per frame, with no search grid and no training; the same input always gives the same track.
Tolerant of deformation and partial occlusion. A histogram ignores the arrangement of colours, and the kernel down-weights the periphery, where occluders first appear. The 2003 paper shows a player tracked through partial occlusion, clutter, a distractor and camera blur (Football, §5), and a person tracked through about 3600 frames of compressed subway video. There, the residual distance stayed near 0.3 and rose to about 0.6 at a partial occlusion (Subway-1, §5).
Self-diagnosing to a degree. The Bhattacharyya coefficient at convergence measures the match. Its drops mark occlusions and changes of appearance, as in the Subway-1 distance curve.
Local. The tracker finds the nearest mode of the similarity surface. It succeeds when the target stays inside the operational basin of attraction and the colour model has a unique nearby maximum (§4.2).
No dynamics. Neither method predicts motion. Kernel-based tracking simply starts from the last position. CAMShift relies on its window size, which grows with the target’s apparent size and so allows larger motion for nearby objects.

Limitations

Similar colours. Anything with the target’s colours competes for the window: background regions, other people, the other hand. CAMShift’s hue-only model also merges colours that differ only in saturation or brightness. Comaniciu et al. advise checking that the chosen representation is discriminative enough for the application (2003, §7).
Occlusion. Partial occlusion is tolerated, but complete occlusion leaves the window on whatever is left, and the model has no memory of motion to bridge the gap. The authors recommend a more sophisticated motion filter when occlusions are present (§7). Their Kalman extension tracked a hand through complete occlusion by the other hand (§6.2).
Large motion. A target whose centre leaves the area of the previous window may not be found. For motion known to exceed the basin, the authors suggest initializing the tracker at several locations chosen by the motion model (§7).
Scale. A fixed bandwidth gives a wrong box and, for structured targets, a biased centre. Selecting the bandwidth by $\rho$ responds slowly with the default filter and cannot distinguish a part of a uniform target from the whole (Scale Adaptation). CAMShift’s moment-based size takes in nearby probability mass.
Appearance change. The model is fixed after the first frame. The 2003 paper assumes a separate module that periodically updates the model when the target’s colours change significantly (§4), and CBWH updates only the background model.
Colour noise. Hue is unstable at low saturation and brightness. Bradski’s thresholds discard such pixels, and dim scenes cannot be tracked without more light or camera gain (“Color Probability Distributions”).
Single target, no identity. The methods track one region and do not resolve which of several similar objects is the target. Multi-object tracking adds data association for that.

Variants

With a Kalman filter. Comaniciu, Ramesh and Meer (2003, §6.2) ran two independent constant-velocity Kalman filters, one horizontal and one vertical, with the kernel tracker supplying the measurement. The measurement uncertainty came from a scaled Gaussian fitted to three points of the similarity surface: the converged peak and two points half a target dimension away. The Kalman Filter article covers the filter, and Motion Models for Tracking the constant-velocity model.
Face tracking with colour and gradient (2003, §6.3): an elliptical face model in normalized $rg$ space, with scale chosen by combined colour and gradient scores.
Other similarity measures and optimizers. Comaniciu et al. (2003, §7) list follow-up work: Chen and Liu’s trust-region optimization of the Kullback–Leibler distance between the same kernel-weighted histograms, and a particle filter for colour-histogram tracking based on their metric $d$ , by Pérez, Hue, Vermaak and Gangnet. Ning et al. cite further variants, among them an EM-like algorithm for colour-histogram tracking by Zivkovic and Kröse and asymmetric-kernel mean shift with automatic scale and orientation selection by Yilmaz.
Discriminative trackers. Later single-object trackers learn to separate the target from its surroundings rather than match a fixed histogram. Discriminative correlation filters and Siamese networks are surveyed in Object Tracking.

History

Mean shift goes back to Fukunaga and Hostetler’s 1975 work on estimating the gradient of a density and was revived by Cheng in 1995; the Mean Shift article tells that history. Bradski’s CAMSHIFT appeared in 1998, in the Intel Technology Journal and at the IEEE Workshop on Applications of Computer Vision. He developed it as the first module of a perceptual user interface, tracking a face’s position, distance and roll at video rate with inexpensive consumer cameras, to steer games and 3D scenes; he remarked that mean shift had never been meant as a tracker. Comaniciu, Ramesh and Meer presented kernel-based tracking at CVPR 2000 and gave the full treatment, with background weighting, Kalman prediction and face tracking, in their 2003 journal paper. The CVPR 2000 paper received the Longuet-Higgins Prize in 2010. OpenCV implements both meanShift and CamShift on a single-channel probability image, such as a back-projection. Ning et al.’s 2012 correction showed that the background-weighted histogram, used in several follow-up works, had left the mean shift iterations unchanged.