Global Image Descriptors

A global image descriptor turns a whole image into one fixed-length vector: how much of each colour it contains, the average colour in each cell of a coarse grid, the energy of oriented filters at a few positions. Two images are then compared by a single distance or similarity between their vectors, with no keypoints to detect and no correspondences to verify. This makes global descriptors cheap to store and to search, and the early content-based retrieval systems described whole images this way, as image retrieval recounts from Smeulders et al.’s review. It also gives them their characteristic weaknesses: a global descriptor mixes the object with everything around it, and it is unchanged by any change of the image that it was built to ignore, whether or not that change mattered. This article covers the hand-designed global descriptors, with colour descriptors in depth: the colour histogram and Swain and Ballard’s colour indexing, colour coordinates and ratio histograms that survive changes of illumination, colour moments, and descriptors that keep coarse spatial layout, among them GIST. Global vectors computed by neural networks are covered under embeddings, and the general contrast between global and local features under image features.

Definition

A global image descriptor is a function $F$ that maps an image $I$ (or a whole detection window) to a vector $F(I) \in \mathbb{R}^D$ of fixed length $D$, independent of the image’s content, together with a similarity or distance for comparing two such vectors. It has no location of its own: unlike a local feature, it does not say where in the image anything is, although it may record coarse position by computing statistics separately in fixed cells.

Hand-designed global descriptors fall into a few families:

• Distributions of pixel values: colour histograms in some colour space, and histograms of values derived from colour, such as chromaticity or ratios between neighbouring pixels.
• Summary statistics: low-order moments of the colour distribution.
• Layout descriptors: the same statistics computed per cell of a coarse grid, a heavily downsampled image, or, in GIST, the energy of oriented band-pass filters averaged over a grid.
• Aggregated local descriptors: local descriptors pooled over the whole image, as in the bag of visual words, which are global in form but local in origin.

Intuition

Suppose a database holds one photograph of each of a few hundred multicoloured household objects, and a new photograph must be matched to one of them. One could find corners and patches and match them one by one. Swain and Ballard proposed something simpler, as Funt and Finlayson (1995) summarize it: count how many pixels of each colour the new image has, count the same for each stored object, and pick the object whose colour counts overlap most. A red-and-yellow cereal box and a blue-and-white shirt differ in their colours long before anyone looks at their shapes.

The counting ignores where the colours are. That is the source of both its strengths and its failures. The object can be moved, turned in the image plane, partly hidden or crumpled, and the counts barely change. But the counts also do not change when two different objects happen to have the same colours in different arrangements, and they can change completely when the light turns yellower, because many pixels then move to other colour bins. Each descriptor below is a different answer to the question of which changes the vector should ignore and which it should notice.

Formal Definition

Colour histograms and histogram intersection

Quantize each pixel’s colour into one of $n$ bins and count: $h_j$ is the number of pixels whose colour falls in bin $j$. The image histogram article defines joint and per-channel colour histograms and the choice of bins; Swain and Ballard, as Funt and Finlayson describe them, converted camera RGB to an opponent colour space with black–white, red–green and blue–yellow axes and quantized it coarsely along the black–white axis, giving 2,048 bins.

Swain and Ballard compared an image histogram $I$ with a model histogram $M$ by histogram intersection,

$$\cap(I, M) = \frac{\sum_{j=1}^{n} \min(I_j, M_j)}{\sum_{j=1}^{n} M_j},$$

the fraction of the model’s pixels that find a pixel of the same colour bin in the image, which runs from 0 to 1. Funt and Finlayson describe the model histograms as computed from images of each object segmented from its background, with the unknown image matched against every stored model and the best intersection winning. Normalizing by the model’s count means that image pixels with colours the model lacks do not lower the score. When the two histograms have the same total $T$, one minus the intersection is a scaled ℓ1 distance, $1 - \cap(I, M) = \frac{1}{2T} \sum_j |I_j - M_j|$, a property Funt and Finlayson credit to Swain; similarity and distance measures compares intersection with the other histogram measures. Swain and Ballard also used histograms to locate objects by backprojection, which the image histogram article describes, and kernel-weighted colour histograms became the target model of mean-shift tracking.

Illumination and invariant colour coordinates

A colour histogram moves when the light changes. Van de Sande, Gevers and Snoek (2010) organize the changes with the diagonal model of illumination change (the von Kries model): the colours of a scene under an unknown light map to those under a reference light by a separate gain on each channel, extended by Finlayson et al. with an offset on each channel,

$$\begin{pmatrix} R^c \\ G^c \\ B^c \end{pmatrix} = \begin{pmatrix} a & 0 & 0 \\ 0 & b & 0 \\ 0 & 0 & c \end{pmatrix} \begin{pmatrix} R^u \\ G^u \\ B^u \end{pmatrix} + \begin{pmatrix} o_1 \\ o_2 \\ o_3 \end{pmatrix}.$$

They note that the model holds for narrow-band camera sensors and that spectral sharpening can bring broad-band sensors closer to it. From it they distinguish five changes: a light intensity change ($a = b = c$, no offset), which also covers uncoloured shadows and shading; a light intensity shift (equal offsets, unit gains), from diffuse light, highlights under white light and interreflections; the two together; a light colour change (unequal gains); and a light colour change with shift (unequal gains and offsets). A descriptor is invariant to a change when its value does not depend on it, derived on the assumption that no colour is clipped at the top of the range.

Several colour coordinates remove some of these changes:

• Chromaticity $r = R/(R+G+B)$, $g = G/(R+G+B)$: a common gain cancels in the ratio, so an rg histogram is invariant to light intensity changes, but not to shifts or to light colour changes (an unequal gain changes $r$ and $g$).
• Opponent colours $O_1 = (R-G)/\sqrt{2}$, $O_2 = (R+G-2B)/\sqrt{6}$, $O_3 = (R+G+B)/\sqrt{3}$: equal offsets cancel in the differences $O_1$ and $O_2$, so their histogram is invariant to intensity shifts; $O_3$ is intensity and has no invariance.
• Hue: invariant to intensity changes and shifts, but unstable near the grey axis, where van de Sande et al. follow van de Weijer et al. in weighting each hue sample by its saturation.
• Transformed colour: each channel standardized to zero mean and unit variance over the image or patch, $R' = (R - \mu_R)/\sigma_R$ and likewise for $G$ and $B$. Because each channel is normalized separately, this removes per-channel gains and offsets, so it is invariant to all five changes.

The colour spaces article introduces chromaticity and hue and notes that shading and shadows change intensity much more than chromaticity.

Colour-ratio histograms

Funt and Finlayson (1995) took a different route to invariance under a change of illuminant colour. Under the diagonal model, the ratio of a channel’s responses at two nearby points is the ratio of the surface albedos there, because the illuminant’s gain for that channel is the same at both points and cancels: $\rho_k^1 / \rho_k^2 = r_k^1 / r_k^2$. Taking logarithms turns ratios into differences, so a derivative of $\log \rho_k$ does not depend on the illuminant’s colour or intensity. Their colour constant colour indexing histograms, instead of colours, the 3-tuples of derivatives of the logarithms of the three channels: (1) take $\log \rho_k$; (2) apply a Laplacian, a Laplacian of Gaussian or four directional first derivatives; (3) count the tuples in a joint histogram. Inside a region of uniform colour the derivative is near zero; along a boundary between two colours every pixel gives about the same tuple, so they describe the count in a bin as a measure of the length of the boundary between two specific colours, where Swain’s histogram measured the area of a colour. They choose bin boundaries non-uniformly, finer near ratio 1 where ratios are more probable, and normalize the intersection by the larger of the image’s and the model’s total counts, since they did not segment the model images.

Their results show both what the change buys and what it costs. On Swain’s own database (55 model images, 24 test images, fixed illumination), Swain’s algorithm put the correct model first for 23 of 24 images, and the ratio histograms for 19 (Laplacian of Gaussian, $\sigma = 1$), 21 (a simple $3 \times 3$ Laplacian) and 22 (first derivatives) (their Table I); the rank counts in two rows of that table, Swain’s and the simple Laplacian’s, add up to 25 and 26 rather than 24, so they are given here as printed. On real images of 11 objects under three illuminants of different colour temperature, the ratio histograms with the Laplacian of Gaussian put the correct model first for 21 or 22 of 22 test images with each illuminant’s images as the model set (Table VI), while Swain’s algorithm, run in these tests on RGB histograms without segmenting the model images, managed 14, 10 and 10 (Table VII).

Colour moments

A colour distribution can also be summarized by a few moments instead of a histogram. Van de Sande et al. use the generalized colour moments of Mindru et al.,

$$M_{pq}^{abc} = \iint x^p y^q \, [I_R(x, y)]^a \, [I_G(x, y)]^b \, [I_B(x, y)]^c \, dx\, dy,$$

of order $p + q$ and degree $a + b + c$. Moments of order 0 carry no spatial information; those of degree 0 carry no colour information; higher orders and degrees are less stable. Their colour-moment descriptor takes all moments up to the first order and the second degree, 27 numbers after dropping the constant $M_{pq}^{000}$, computed after subtracting each channel’s mean, which makes it invariant to light intensity shifts only. Combinations of these moments, the colour moment invariants, are invariant to all five changes. The example below uses a smaller descriptor of our own definition, which summarizes each channel separately by its mean, spread and asymmetry in nine numbers.

Spatial layout

Histograms and order-0 moments ignore where colours are. The simplest way to keep coarse position is to compute the statistics separately in the cells of a fixed grid and concatenate them. In the limit, the descriptor is the image itself at very low resolution: as the k-nearest neighbours article describes, Torralba, Fergus and Freeman (2008) compared $32 \times 32$ colour images by the sum of squared differences and recognized objects and scenes by nearest-neighbour search in a database of about 79 million such images. Grid pooling of histograms is the idea behind the spatial pyramid, which compares histograms over finer and finer grids, as the bag of visual words article describes; van de Sande et al. use $2 \times 2$ and $1 \times 3$ spatial pyramids of their colour descriptors as additional pipelines.

GIST applies the same pooling to oriented filter energies. Oliva and Torralba’s spatial envelope model, as the abstract on their project page states, bypasses the segmentation of objects and regions: it describes a scene by a very low-dimensional representation, the spatial envelope, whose perceptual dimensions (naturalness, openness and others) are estimated from spectral and coarsely localized information, and scenes of the same semantic category lie close together in that space. As scene recognition describes from the official LMgist.m code, GIST converts the image to grey, normalizes local contrast, filters it with a bank of Gabor-like filters (by default 4 scales and 8 orientations), and averages each filter’s magnitude over a $4 \times 4$ grid, giving 512 numbers that are compared by squared Euclidean distance. GIST is therefore a global descriptor of layout and texture, not of colour; Gabor filter covers the filters, and scene recognition covers the descriptor, its variants and its results.

Properties

What each descriptor ignores

Van de Sande et al. (Table I) derive which descriptors are invariant to which of the five illumination changes. The rows for the global descriptors discussed here:

Descriptor	Intensity change	Intensity shift	Change and shift	Colour change	Colour change and shift
RGB histogram	–	–	–	–	–
$O_1, O_2$ histogram	–	+	–	–	–
Hue histogram	+	+	+	–	–
rg histogram	+	–	–	–	–
Transformed colour histogram	+	+	+	+	+
Colour moments (mean-subtracted)	–	+	–	–	–
Colour moment invariants	+	+	+	+	+

Funt and Finlayson’s ratio histograms are not in the table; under their coefficient model a derivative of the log image is invariant to intensity and colour changes where the illumination is locally constant; by our derivation it is not invariant to offsets, since an offset does not separate from the gain inside the logarithm.

Changes of geometry follow from the construction rather than from a table. A histogram, and any statistic of the order-0 kind, is unchanged by any permutation of the pixels: translation, rotation in the image plane, mirroring, and rearrangement of an object’s parts, up to resampling. Funt and Finlayson list what Swain’s method therefore tolerates: position and in-plane orientation do not affect the histogram, a change of shape that preserves colour areas leaves it unchanged, and occlusion changes the histogram and may lower the match confidence. Three-dimensional rotation was handled by storing several views, and the object’s apparent size had to stay roughly the same, as did the illumination. Grid descriptors and GIST give up exactly this freedom: moving the object from one cell to another changes the vector.

Invariance against distinctiveness

Every invariance removes information, and van de Sande et al.’s experiments show the cost. Their descriptors are computed over regions around detected or densely sampled points and then aggregated, so their histograms are local descriptors; the invariance analysis is the same for a histogram of a whole image. On ALOI, a set of 1,000 objects photographed under controlled conditions, matched by a nearest neighbour from one example per object, the descriptors without invariance to light intensity changes (the RGB, opponent and colour moment descriptors) performed poorly when intensity was scaled, and histograms did poorly under changes of light colour, except for the transformed colour histogram and the colour moment invariants, which have that invariance. But under a change in the number and direction of white lights, where the light’s colour does not change, the colour SIFT variants invariant only to intensity scaling (C-SIFT and rgSIFT) did better than the more invariant OpponentSIFT and RGB-SIFT, which the authors judge too invariant for that condition. They also found the hue, rg and transformed colour histograms and the colour moment invariants sensitive to even moderate JPEG compression. Their conclusion is that a descriptor needs enough distinctiveness as well as invariance, and on image and video category recognition (PASCAL VOC 2007 and the Mediamill Challenge) the SIFT-based descriptors outperformed the histogram-based and moment-based ones in the same pipeline.

Clutter, occlusion and normalization

Because a global descriptor sums over the whole image, everything that is not the object enters the vector. The example in image features shows this for a grey-level histogram: replacing one object changed the histogram of the whole image, and after standardization the change spread to the background’s values too. Two remedies come from the matching rule rather than the descriptor. Swain’s normalization by the segmented model’s count ignores image colours the model does not have, so background clutter in the query does not lower the correct model’s score; by the same construction, clutter colours that another model has raise that model’s score. Funt and Finlayson, who did not segment their models, point out the reverse problem: with model normalization, an image with many colour edges can be matched to a model with few by chance, so they normalized by the larger of the two totals, so that a good match needs a large intersection and two histograms of similar size.

Size and search

A global descriptor is one vector per image, so a database is a matrix and a query is a scan or a nearest-neighbour search. The colour histograms above have hundreds to a few thousand bins, a GIST vector 512 numbers, and a $32 \times 32$ colour thumbnail 3,072. Searching many such vectors is the problem of approximate nearest neighbor search; the product quantization experiments that article reports include a set of a million 960-dimensional GIST descriptors. Nonparametric methods use global descriptors to find a query’s neighbours: Liu, Yuen and Torralba’s scene parsing by label transfer, as k-nearest neighbours describes, first retrieves the query’s nearest neighbours by GIST.

Examples

The example builds a small colour-indexing database and measures which descriptor survives which change. Each of 24 synthetic objects is a $64 \times 64$ square of $4 \times 4$ tiles painted with a palette of three colours drawn at random from $[0.1, 0.75]^3$ in RGB (pairwise distance at least 0.15, each colour on at least two tiles), placed on a mid-grey $96 \times 96$ canvas. Light acts as a per-channel gain on the whole scene, the diagonal model above; then Gaussian sensor noise with standard deviation 0.02 is added and values are clipped to $[0.01, 1]$. Each object has one model image. Queries are new renders, three per object and condition, with fresh noise:

• C0, the same scene (the base check);
• C1, an occluding bar of a random colour over 19 of the object’s 64 rows or columns (29.7% of its area);
• C2, the grey background replaced by a $12 \times 12$ grid of randomly coloured blocks;
• C3, a light intensity change (all gains 0.6);
• C4, a light colour change (gains 1.25, 1.0 and 0.7);
• C5, the object’s tiles rearranged at random, with at least 6 tiles changing colour.

Experiment B asks the converse question: 12 of the objects and, for each, a “twin” with the same colours on the same number of tiles in a different arrangement are all stored as separate models, and the queries are new renders of all 24.

Six descriptors are compared, all computed on the whole query image:

1. an RGB histogram with 8 bins per channel and Swain’s intersection, with the model taken from the object region only (a segmented model, as Funt and Finlayson describe Swain’s);
2. the same histogram with the model taken from the whole model image, as Funt and Finlayson did not segment; the sources differ on this choice, so both are printed;
3. an rg chromaticity histogram ($16 \times 16$ bins) with intersection;
4. colour moments, defined here (our choice) as each channel’s mean, standard deviation and the cube root of its third central moment, nine numbers compared by Euclidean distance;
5. a colour layout, our construction: the mean RGB colour in each cell of a $4 \times 4$ grid, 48 numbers compared by Euclidean distance;
6. a ratio histogram after Funt and Finlayson: the Laplacian of Gaussian ($\sigma = 1$) of the log of each channel, counted in a joint histogram of $9 \times 9 \times 9$ uniform bins over $[-1.125, 1.125]$ per channel (zero at a bin centre, values outside the range in the end bins), compared by intersection normalized by the larger total. The uniform bins are our simplification of their non-uniform partition.

The score is the rank of the correct model among all models, counted pessimistically (one plus the number of other models that score at least as well), reported as rank-1 accuracy and mean rank. The script also checks the invariances that hold exactly on noise-free images and the properties of the generated data.

import os
os.environ["OMP_NUM_THREADS"] = "1"          # one BLAS thread: reproducible sums
os.environ["OPENBLAS_NUM_THREADS"] = "1"
os.environ["MKL_NUM_THREADS"] = "1"
import numpy as np
from scipy import ndimage

SEED, N_OBJ, N_INST = 0, 24, 3
SIZE, OBJ, TILE, OFF = 96, 64, 16, 16          # canvas, object side, tile side, object offset
SIGMA_NOISE, GREY = 0.02, 0.5


def make_object(i, seed_base=1000):
    """Palette of 3 distinct colours and a 4x4 grid of tile labels (each colour on >= 2 tiles)."""
    rng = np.random.default_rng([SEED, seed_base + i])
    while True:
        pal = rng.uniform(0.1, 0.75, (3, 3))
        if min(np.linalg.norm(pal[a] - pal[b]) for a in range(3) for b in range(a + 1, 3)) >= 0.15:
            break
    while True:
        lab = rng.integers(0, 3, 16)
        if np.bincount(lab, minlength=3).min() >= 2:
            break
    return pal, lab


def rearrange(lab, rng):
    """Permute the tiles so that at least 6 of them change colour."""
    while True:
        new = lab[rng.permutation(16)]
        if (new != lab).sum() >= 6:
            return new


def paint(pal, lab):
    return np.repeat(np.repeat(pal[lab].reshape(4, 4, 3), TILE, 0), TILE, 1)


def render(obj, rng, background=None, illum=(1.0, 1.0, 1.0), noise=True):
    """Object on a background, lit by a per-channel (diagonal) illuminant, plus sensor noise."""
    img = np.full((SIZE, SIZE, 3), GREY) if background is None else background.copy()
    img[OFF:OFF + OBJ, OFF:OFF + OBJ] = obj
    img = img * np.asarray(illum)
    if noise:
        img = img + rng.normal(0, SIGMA_NOISE, img.shape)
    return np.clip(img, 0.01, 1.0)


# ---------------- descriptors ----------------
def hist_rgb(img, bins=8):
    q = np.minimum((img * bins).astype(int), bins - 1).reshape(-1, 3)
    return np.bincount((q[:, 0] * bins + q[:, 1]) * bins + q[:, 2], minlength=bins ** 3).astype(float)


def hist_rg(img, bins=16):
    s = img.sum(-1)
    h, _, _ = np.histogram2d((img[..., 0] / s).ravel(), (img[..., 1] / s).ravel(),
                             bins=bins, range=[[0, 1], [0, 1]])
    return h.ravel()


def moments(img):
    x = img.reshape(-1, 3)
    mu = x.mean(0)
    return np.concatenate([mu, x.std(0), np.cbrt(((x - mu) ** 3).mean(0))])


def layout(img, g=4):
    c = SIZE // g
    return img.reshape(g, c, g, c, 3).mean((1, 3)).ravel()


def log_laplacian(img):
    return np.stack([ndimage.gaussian_laplace(np.log(img[..., k]), 1.0) for k in range(3)], -1)


def hist_ratio(img, bins=9, half=1.125):
    """Funt-Finlayson colour-ratio histogram: LoG (sigma 1) of the log image, joint 3D histogram."""
    q = np.clip(((log_laplacian(img) + half) / (2 * half) * bins).astype(int), 0, bins - 1)
    q = q.reshape(-1, 3)
    return np.bincount((q[:, 0] * bins + q[:, 1]) * bins + q[:, 2], minlength=bins ** 3).astype(float)


def intersect(q, m):
    return np.minimum(q, m).sum() / m.sum()


NAMES = ["RGB hist, segmented model", "RGB hist, whole image", "rg hist", "colour moments",
         "colour layout", "ratio hist"]


def describe(img, segmented_model=False):
    seg = hist_rgb(img[OFF:OFF + OBJ, OFF:OFF + OBJ]) if segmented_model else None
    return [seg, hist_rgb(img), hist_rg(img), moments(img), layout(img), hist_ratio(img)]


def scores(qd, md):
    """Similarity of a query to a model for each descriptor (higher is better)."""
    return np.array([intersect(qd[1], md[0]), intersect(qd[1], md[1]), intersect(qd[2], md[2]),
                     -np.linalg.norm(qd[3] - md[3]), -np.linalg.norm(qd[4] - md[4]),
                     np.minimum(qd[5], md[5]).sum() / max(qd[5].sum(), md[5].sum())])


def rank_of(S, true):
    """Pessimistic rank of the true model: 1 + number of other models scoring at least as high."""
    return 1 + (np.delete(S, true, axis=0) >= S[true]).sum(0)


# ---------------- experiment A: 24 objects, six conditions ----------------
objects = [make_object(i) for i in range(N_OBJ)]
models = [describe(render(paint(p, l), np.random.default_rng([SEED, 2000 + i])), True)
          for i, (p, l) in enumerate(objects)]

CONDS = ["C0 same", "C1 occlusion", "C2 clutter", "C3 intensity x0.6",
         "C4 illuminant (1.25,1,0.7)", "C5 rearranged"]
checks = {"occluded share": [], "grey in clutter": [], "rearranged min changed": 16}


def query(c, pal, lab, rng):
    obj, bg, illum = paint(pal, lab), None, (1.0, 1.0, 1.0)
    if c == 1:                                   # occluder over 19 of 64 rows or columns
        col, pos = rng.uniform(0.1, 0.75, 3), rng.integers(0, OBJ - 19 + 1)
        before = obj.copy()
        if rng.random() < 0.5:
            obj[pos:pos + 19] = col
        else:
            obj[:, pos:pos + 19] = col
        checks["occluded share"].append(np.any(obj != before, -1).mean())
    elif c == 2:                                 # cluttered background of random blocks
        blocks = rng.uniform(0.1, 0.75, (12, 12, 3))
        bg = np.repeat(np.repeat(blocks, 8, 0), 8, 1)
        tmp = bg.copy(); tmp[OFF:OFF + OBJ, OFF:OFF + OBJ] = obj
        checks["grey in clutter"].append(int(np.all(tmp == GREY, -1).sum()))
    elif c == 3:
        illum = (0.6, 0.6, 0.6)
    elif c == 4:
        illum = (1.25, 1.0, 0.7)
    elif c == 5:
        new = rearrange(lab, rng)
        checks["rearranged min changed"] = min(checks["rearranged min changed"], int((new != lab).sum()))
        obj = paint(pal, new)
    return render(obj, rng, bg, illum)


def run(models, objs, conds, cond_ids):
    out = {}
    for c, cid in zip(conds, cond_ids):
        ranks = []
        for i, (pal, lab) in enumerate(objs):
            for k in range(N_INST):
                rng = np.random.default_rng([SEED, cid, i, k])
                qd = describe(query(c, pal, lab, rng))
                ranks.append(rank_of(np.array([scores(qd, m) for m in models]), i))
        out[cid] = np.array(ranks)
    return out


resA = run(models, objects, range(6), range(6))
print(f"Experiment A: {N_OBJ} objects, {N_OBJ * N_INST} queries per condition; "
      "rank-1 accuracy (mean rank of the true model)")
print(f"{'descriptor':<27}" + "".join(f"{c.split()[0]:>12}" for c in CONDS))
for j, n in enumerate(NAMES):
    print(f"{n:<27}" + "".join(f"{np.mean(resA[c][:, j] == 1):>6.3f} ({resA[c][:, j].mean():>4.1f})"
                               for c in range(6)))

# ---------------- experiment B: 12 objects and their rearranged twins ----------------
twins = []
for i in range(12):
    pal, lab = objects[i]
    twins.append((pal, rearrange(lab, np.random.default_rng([SEED, 3000 + i]))))
objsB = objects[:12] + twins
modelsB = models[:12] + [describe(render(paint(p, l), np.random.default_rng([SEED, 4000 + i])), True)
                         for i, (p, l) in enumerate(twins)]
resB = run(modelsB, objsB, [0], [10])[10]
print(f"\nExperiment B: 12 objects + 12 rearranged twins, {len(resB)} queries (new noise only)")
for j, n in enumerate(NAMES):
    print(f"{n:<27} rank-1 {np.mean(resB[:, j] == 1):.3f}  mean rank {resB[:, j].mean():.2f}")

# ---------------- checks ----------------
pal, lab = objects[0]
base = render(paint(pal, lab), None, noise=False)
dim = render(paint(pal, lab), None, illum=(0.6, 0.6, 0.6), noise=False)
col = render(paint(pal, lab), None, illum=(1.25, 1.0, 0.7), noise=False)
perm = np.random.default_rng([SEED, 9]).permutation(16)
rea = render(paint(pal, lab[perm]), None, noise=False)
pals = np.array([p for p, _ in objects])
print("\nChecks")
print("K0 C0 rank-1 = 1 for every descriptor:", bool(np.all(resA[0] == 1)))
print("K1 noise-free rg hist, intensity x0.6, L1 diff:", np.abs(hist_rg(base) - hist_rg(dim)).sum())
print("K2 noise-free ratio hist, illuminant, L1 diff:", np.abs(hist_ratio(base) - hist_ratio(col)).sum(),
      f"(max |LoG log| diff {np.abs(log_laplacian(base) - log_laplacian(col)).max():.1e})")
print("K3 noise-free rearrangement (", int((lab[perm] != lab).sum()), "tiles changed): RGB hist L1 diff",
      np.abs(hist_rgb(base) - hist_rgb(rea)).sum(), "| moments max diff",
      f"{np.abs(moments(base) - moments(rea)).max():.1e}")
print("K4 palette range", pals.min().round(3), pals.max().round(3), "| min palette distance",
      round(min(min(np.linalg.norm(p[a] - p[b]) for a in range(3) for b in range(a + 1, 3))
                for p in pals), 3),
      "| min tiles per colour", min(np.bincount(l, minlength=3).min() for _, l in objects))
print("   max before noise under (1.25,1,0.7):", round(max(pals.max(), GREY) * 1.25, 4),
      "| min before noise under x0.6:", round(pals.min() * 0.6, 4))
print("   occluded share of object: min", round(min(checks["occluded share"]), 3), "max",
      round(max(checks["occluded share"]), 3), "| grey pixels in clutter scenes:",
      sum(checks["grey in clutter"]), "| min tiles changed (C5):", checks["rearranged min changed"],
      "| twins: counts kept", all(np.array_equal(np.bincount(objects[i][1], minlength=3),
                                                np.bincount(twins[i][1], minlength=3)) for i in range(12)),
      "min changed", min(int((twins[i][1] != objects[i][1]).sum()) for i in range(12)))

Output (NumPy 2.3.5, SciPy 1.16.3; deterministic, identical on two runs; about 1 second):

Experiment A: 24 objects, 72 queries per condition; rank-1 accuracy (mean rank of the true model)
descriptor                           C0          C1          C2          C3          C4          C5
RGB hist, segmented model   1.000 ( 1.0) 1.000 ( 1.0) 1.000 ( 1.0) 0.000 (15.1) 0.083 ( 7.0) 1.000 ( 1.0)
RGB hist, whole image       1.000 ( 1.0) 1.000 ( 1.0) 1.000 ( 1.0) 0.000 (14.8) 0.083 ( 6.2) 1.000 ( 1.0)
rg hist                     1.000 ( 1.0) 1.000 ( 1.0) 1.000 ( 1.0) 1.000 ( 1.0) 0.042 (10.8) 1.000 ( 1.0)
colour moments              1.000 ( 1.0) 0.583 ( 3.3) 0.069 (12.3) 0.125 ( 6.4) 0.417 ( 2.2) 1.000 ( 1.0)
colour layout               1.000 ( 1.0) 0.750 ( 1.8) 1.000 ( 1.0) 0.083 ( 9.1) 0.500 ( 3.2) 0.597 ( 2.6)
ratio hist                  1.000 ( 1.0) 0.792 ( 1.4) 0.167 ( 8.5) 0.958 ( 1.0) 1.000 ( 1.0) 0.986 ( 1.0)

Experiment B: 12 objects + 12 rearranged twins, 72 queries (new noise only)
RGB hist, segmented model   rank-1 0.472  mean rank 1.53
RGB hist, whole image       rank-1 0.431  mean rank 1.57
rg hist                     rank-1 0.528  mean rank 1.47
colour moments              rank-1 0.556  mean rank 1.44
colour layout               rank-1 1.000  mean rank 1.00
ratio hist                  rank-1 1.000  mean rank 1.00

Checks
K0 C0 rank-1 = 1 for every descriptor: True
K1 noise-free rg hist, intensity x0.6, L1 diff: 0.0
K2 noise-free ratio hist, illuminant, L1 diff: 0.0 (max |LoG log| diff 5.1e-05)
K3 noise-free rearrangement ( 13 tiles changed): RGB hist L1 diff 0.0 | moments max diff 1.3e-13
K4 palette range 0.103 0.746 | min palette distance 0.152 | min tiles per colour 2
   max before noise under (1.25,1,0.7): 0.9325 | min before noise under x0.6: 0.0617
   occluded share of object: min 0.297 max 0.297 | grey pixels in clutter scenes: 0 | min tiles changed (C5): 6 | twins: counts kept True min changed 6

The base condition and the checks come out as designed. Every descriptor puts the correct model first for all 72 queries of C0, so the objects are distinguishable by every descriptor when nothing changes. On noise-free images the rg histogram is exactly unchanged by an intensity change, the ratio histogram by a change of light colour, and the RGB histogram and colour moments by a rearrangement of tiles; the log-Laplacians differ by about $5 \times 10^{-5}$ under the colour change because SciPy’s truncated Gaussian-derivative kernel does not sum exactly to zero, too little to move a value across a bin boundary here.

The plan for this example, written before it was run, stated six hypotheses. Their outcomes, read from the printed table:

• Occlusion (C1). Held: the three histograms keep rank-1 accuracy of at least 0.9 (all three print 1.000), and colour moments (0.583) and colour layout (0.750) score lower than every histogram. The ratio histogram, which the hypothesis did not cover, prints 0.792.
• Clutter (C2). Failed in two of its four parts. It held that the segmented-model RGB histogram keeps at least 0.9 (it prints 1.000) and that colour moments fall to 0.5 or below (0.069). It failed in that the segmented model did not beat the whole-image model (both print 1.000, mean rank 1.0), and in that colour layout did not fall to 0.5 or below (it prints 1.000). The ratio histogram, not covered by the hypothesis, prints 0.167.
• Intensity change (C3). Held: the rg histogram (1.000) and the ratio histogram (0.958) keep at least 0.95, and both RGB histograms (0.000), colour moments (0.125) and colour layout (0.083) fall to 0.5 or below.
• Light colour change (C4). Held: the ratio histogram keeps at least 0.95 (1.000), and the rg histogram (0.042), both RGB histograms (0.083), colour moments (0.417) and colour layout (0.500) are at or below 0.5. Colour layout sits exactly at the 0.5 bound.
• Rearrangement (C5). Held: both RGB histograms, the rg histogram and colour moments keep at least 0.95 (all 1.000), colour layout falls below 0.8 (0.597), and the ratio histogram falls below its C0 value (0.986 against 1.000).
• Twins (experiment B). Held for five descriptors and failed for one. Both RGB histograms (0.472 and 0.431), the rg histogram (0.528) and colour moments (0.556) stay at or below 0.7, and colour layout reaches 1.000. The prediction that the ratio histogram would fall between the two groups failed: it prints 1.000, the same as the layout.

The RGB and rg rows read as van de Sande et al.’s table predicts: the RGB histograms collapse under both illumination changes, and the rg histogram survives the intensity change and fails the colour change. Of the six descriptors, only the ratio histogram, which the table does not cover, survives both. Its 0.958 under C3, below its 1.000 under C4, has a likely reason in the construction (our reading; the output does not test it): the noise is added after the light, so dimming every channel by 0.6 raises the noise of $\log \rho$, which is about $\sigma / \rho$, by a factor of $1/0.6$ in all three channels, while the colour change lowers only the blue channel (by 0.7) and raises the red.

Experiments A and B together show invariance as a choice. The rearranged objects of C5 and the twins of B are the same kind of image: the same colours on the same areas, in another arrangement. The histograms and moments treat them as the same object, which is right in C5 and wrong in B, where their rank-1 accuracies (0.431 to 0.556) are close to the 0.5 that choosing at random between an object and its twin would give. The colour layout treats them as different, which is wrong in C5 (0.597) and right in B (1.000). Which behaviour is correct depends on whether the arrangement is a nuisance, as for the shirt thrown on the floor that Funt and Finlayson give as a typical object of Swain’s database, or part of the identity. The ratio histogram separates the twins, which follows from its construction: rearranging tiles changes which colours meet and along how much boundary, and those boundaries are what it counts. In our reading the same change is why its C5 score is 0.986 rather than 1.000.

Two failed parts of the clutter hypothesis concern the background. In our reading, the whole-image RGB model loses its grey background bins against every cluttered query by about the same amount, since all models share the same grey background, so the ranking is still decided by the object’s colours, as with the segmented model; the layout’s background is the same grey in every model, so replacing it with random blocks adds a similar amount to the distance to every model. Neither explanation is tested by the printed output. The ratio histogram’s low C2 score (0.167) follows, in our reading, from the many new colour boundaries between background blocks, which outnumber the object’s own boundaries: by the construction of the intersection, these counts can only raise the scores of the models whose boundary bins they happen to share, while the loss of near-zero counts from the grey background, which every model has, lowers the scores of all models; Funt and Finlayson’s normalization by the larger total does not help here, because every image in this example has the same number of pixels and so the same total. Its 0.792 under occlusion is likewise read, without a test, as the bar removing some of the object’s boundaries and adding new ones.

Common Misconceptions

• “A colour histogram is invariant to lighting.” It is invariant to where colours are, not to what colour they are. Under van de Sande et al.’s analysis an RGB histogram has none of the five illumination invariances; in the example both RGB histograms fall to 0.000 under a 40% drop in intensity.
• “More invariance is always safer.” Each invariance discards information. Van de Sande et al. found the colour-invariant RGB-SIFT behind less invariant colour SIFT variants when only the number and direction of white lights changed, and the example’s twins show a histogram unable to tell apart two objects that differ only in arrangement.
• “Histogram intersection handles clutter by itself.” Normalizing by a segmented model’s count keeps unmatched background from lowering the correct score, but the background still raises other models’ scores, and with unsegmented models Funt and Finlayson found the opposite failure, chance matches to models with few counts.
• “Chromaticity solves illumination.” Normalized rg removes a common gain. A change in the light’s colour moves the chromaticities themselves; in the example the rg histogram drops from 1.000 to 0.042 under a yellowish light.

Where It Is Used

• Content-based image retrieval. Early retrieval systems, as image retrieval describes from Smeulders et al.’s review, described whole images by colour, texture and shape features compared with histogram distances; global vectors are still what large collections index, now usually learned (the deep global descriptors in image retrieval and visual place recognition).
• Object recognition by colour. Swain and Ballard’s colour indexing identifies objects from a database by colour alone, and Funt and Finlayson’s ratio histograms extend it to scenes whose illumination changes in intensity and colour.
• Tracking. Colour histograms, weighted by a spatial kernel, are the appearance model of mean-shift tracking and of other object tracking methods.
• Scene recognition and nonparametric methods. GIST classifies scenes, as scene recognition describes, and global descriptors retrieve the nearest neighbours that nonparametric scene parsing transfers labels from (k-nearest neighbours).
• Indexing at scale. Collections of global vectors are compressed and searched with the methods of approximate nearest neighbor search; aggregated local descriptors such as the bag of visual words, VLAD and its trained variant NetVLAD produce global vectors from local features, as bag of visual words and visual place recognition describe.