Similarity and Distance Measures

A similarity measure scores how alike two objects are, and a distance measure (or dissimilarity) scores how different they are. In computer vision the objects are usually vectors computed from images: local feature descriptors such as SIFT, color or gradient histograms, binary codes, and global embeddings. Every nearest-neighbor search, descriptor match, retrieval ranking and tracker association step rests on one of these functions, and the choice changes which neighbor comes first. This article covers the common measures, which of them are true metrics, and when each applies; learning a measure from labeled data is the subject of metric learning.

Definition

A distance (dissimilarity) $d(x, y)$ is a function of two objects that is small when they are alike and grows as they differ. A similarity $s(x, y)$ runs the other way: it is large for alike objects. A distance that satisfies four axioms (non-negativity, zero only for identical objects, symmetry and the triangle inequality, defined below) is a metric. Many useful measures are not metrics: the squared Euclidean distance, the χ² histogram distance and the Kullback–Leibler divergence all break at least one axiom, and they are still used because they rank neighbors well or are cheap to compute.

Intuition

A measure encodes an assumption about which differences matter. The Euclidean distance weighs every coordinate equally. The cosine similarity compares only direction, so a descriptor and a scaled copy of it count as identical. The Mahalanobis distance discounts directions in which the data vary a lot. Most histogram measures compare bin $i$ of one histogram only with bin $i$ of the other, so a slightly brightened picture, whose intensities all move into the next bin, can look completely different; the earth mover’s distance asks how far the mass has to move, and calls it close. No measure is right in general; the right one encodes the invariances the task needs.

Formal Definition

Metric axioms

A function $d$ on a set $X$ is a metric if, for all $x, y, z \in X$,

$$d(x, y) \ge 0, \qquad d(x, y) = 0 \iff x = y, \qquad d(x, y) = d(y, x), \qquad d(x, z) \le d(x, y) + d(y, z).$$

A pseudometric allows $d(x, y) = 0$ for $x \ne y$. The triangle inequality is the axiom that matters most in practice: it gives lower bounds such as $d(q, x) \ge |d(q, p) - d(p, x)|$, which let a search skip candidates without computing their distance, a use in retrieval that Rubner, Puzicha, Tomasi and Buhmann (2001) point out.

Minkowski (ℓp) distances

For vectors $x, y \in \mathbb{R}^d$,

$$d_p(x, y) = \lVert x - y \rVert_p = \Big( \sum_{i=1}^{d} |x_i - y_i|^p \Big)^{1/p} .$$

$p = 2$ is the Euclidean distance, $p = 1$ the Manhattan or city-block distance, and the limit $p \to \infty$ the largest coordinate difference (Chebyshev). For $p \ge 1$ each is a metric. For $0 < p < 1$ the formula still defines a dissimilarity but not a metric: for $x = (0, 0)$, $y = (1, 1)$ and $z = (1, 0)$, $d_{1/2}(x, y) = 4$ while $d_{1/2}(x, z) + d_{1/2}(z, y) = 2$ (our example). The squared Euclidean distance, which k-means and the mean squared error use, is not a metric either, since cutting a straight path at its midpoint halves the sum of the squared lengths; it ranks neighbors exactly as the Euclidean distance does.

The value of $p$ matters in high dimensions, where pairwise distances concentrate (described in the embeddings article). Aggarwal, Hinneburg and Keim (2001) analyzed the contrast between the nearest and farthest neighbor under the ℓp distances, assuming data with independently distributed coordinates, and found that it shrinks faster for larger $p$: in their analysis ℓ1 gave more contrast than ℓ2, and they proposed fractional distances with $p < 1$, which, as the example above shows, are not metrics despite their name.

Cosine similarity, angle and dot product

$$s_{\text{dot}}(x, y) = x^\top y, \qquad \cos(x, y) = \frac{x^\top y}{\lVert x \rVert_2 \, \lVert y \rVert_2}, \qquad \theta(x, y) = \arccos \cos(x, y).$$

The dot product grows with the lengths of both vectors; it is the score a linear classifier or a softmax layer gives to a class weight vector. It is not derived from any metric: a vector $y = 2x$ scores higher against $x$ than $x$ does against itself (our observation). The cosine similarity divides out the lengths and lies in $[-1, 1]$, or in $[0, 1]$ for non-negative vectors such as histograms. Its complement $1 - \cos$, often called the cosine distance, is not a metric; the angle $\theta$, the great-circle distance between the directions on the unit sphere, is. For $\ell_2$-normalized vectors the dot product equals the cosine, and the squared Euclidean distance equals $2 - 2\cos$, so all three rank neighbors identically; the embeddings article derives this and discusses when to normalize.

The normalized cross-correlation of two image patches is the cosine similarity of the patches after subtracting each one’s mean, which is why the feature descriptors article can treat it as a Euclidean distance between normalized patches.

Mahalanobis distance

$$d_M(x, y) = \sqrt{(x - y)^\top M \, (x - y)} ,$$

with $M$ symmetric positive definite, usually the inverse of a covariance matrix, $M = \Sigma^{-1}$. Mahalanobis (1936) introduced it as a distance between the means of two populations with a common dispersion matrix; the Gaussian distribution article gives the point-to-distribution form. Writing $M = L^\top L$ gives $d_M(x, y) = \lVert Lx - Ly \rVert_2$: a Euclidean distance after a linear map, which for $L = \Sigma^{-1/2}$ is the whitening described in the embeddings article. With $M$ positive definite $d_M$ is a metric, with $M$ positive semidefinite a pseudometric. Learning $M$ from pairs labeled similar and dissimilar is the classical form of metric learning.

Hamming distance

For binary strings $a, b \in \{0, 1\}^D$ the Hamming distance counts differing bits, an XOR followed by a population count (the feature descriptors article gives the formula). It is a metric. For codes written as $\pm 1$ vectors it is a function of the dot product, $d_H(a, b) = (D - a^\top b)/2$ (our derivation), so Hamming ranking is dot-product ranking on such codes. Calonder, Lepetit, Strecha and Fua (2010) proposed comparing their BRIEF binary descriptors this way instead of with the ℓ2 norm. Exact nearest-neighbor matching of 512 keypoints took them 2.19 to 8.16 ms for 16- to 64-byte BRIEF descriptors against 28.3 ms for 64-dimensional SURF, on a 2.66 GHz x86-64 machine and without the POPCNT bit-count instruction. Binary hash codes for large-scale retrieval are compared the same way.

Histogram measures

For two histograms $h$ and $k$ with $B$ bins, normalized to sum to 1 unless stated otherwise, the common bin-by-bin measures are:

$$\begin{aligned} \cap(h, k) &= \frac{\sum_i \min(h_i, k_i)}{\sum_i k_i} && \text{histogram intersection (a similarity)} \\ \chi^2(h, k) &= \frac{1}{2} \sum_i \frac{(h_i - k_i)^2}{h_i + k_i} && \chi^2 \text{ distance} \\ \mathrm{BC}(h, k) &= \sum_i \sqrt{h_i k_i}, \qquad d_{\mathrm{Hel}}(h, k) = \sqrt{1 - \mathrm{BC}(h, k)} = \tfrac{1}{\sqrt{2}} \big\lVert \sqrt{h} - \sqrt{k} \big\rVert_2 && \text{Bhattacharyya coefficient, Hellinger distance} \\ \mathrm{KL}(h \,\|\, k) &= \sum_i h_i \log \frac{h_i}{k_i} && \text{Kullback-Leibler divergence} \end{aligned}$$

• Histogram intersection, which Rubner et al. (2000, 2001) credit to Swain and Ballard (1991), matches an image’s color histogram against a model’s; the image histogram article describes their system. When both histograms have the same total, $1 - \cap$ equals half the ℓ1 distance between the normalized histograms, since $\min(a, b) = (a + b - |a - b|)/2$; Rubner, Tomasi and Guibas (2000) cite Swain and Ballard for this equivalence.
• χ² comes from the χ² test statistic for whether two samples come from one distribution. The form above, with the factor $\tfrac{1}{2}$, is the one Rubner et al. (2001) and Belongie, Malik and Puzicha (2002) use; other authors drop the factor, so values from different papers can differ by 2. It is symmetric but violates the triangle inequality (Rubner et al., 2001, Table 1). Belongie et al. compared their shape-context descriptors, log-polar histograms of the positions of other contour points, with it.
• The Bhattacharyya coefficient is the cosine of the angle between the vectors $\sqrt{h}$ and $\sqrt{k}$, which are unit vectors. Comaniciu, Ramesh and Meer (2003) tracked objects by maximizing it between a target’s kernel-weighted color histogram and those of candidate windows, and used $\sqrt{1 - \mathrm{BC}}$ as their distance because, as they show in an appendix, it is a metric, unlike the Bhattacharyya distance $-\ln \mathrm{BC}$. That metric is the Hellinger distance. Arandjelović and Zisserman (2012) called $\mathrm{BC}$ the Hellinger kernel and turned it into a Euclidean distance with RootSIFT: ℓ1-normalize each SIFT descriptor and take element-wise square roots, after which the squared Euclidean distance between descriptors is $2 - 2\,\mathrm{BC}$. The square root reduces the weight of large bins relative to small ones. Since the comparison is still Euclidean, k-means vocabularies and nearest-neighbor search work unchanged; with their tf-idf baseline, mean average precision on Oxford 105k rose from 0.515 to 0.581 (their Table 1).
• The Kullback–Leibler divergence is not symmetric and becomes infinite when $k_i = 0$ where $h_i > 0$. The Jeffrey divergence, the same sum taken from each histogram to their mean $(h + k)/2$, is symmetric and finite, and Rubner et al. (2001) note that it is sometimes called the Jensen–Shannon divergence; neither satisfies the triangle inequality (their Table 1).

Bin-by-bin measures ignore which bins are neighbors. Rubner et al. (2000) point out two consequences: the measures are sensitive to where the bin boundaries fall, and coarse bins lose discriminative power while fine bins split similar features into bins that are never compared. Cross-bin measures use a ground distance $d_{ij}$ between the centers of bins $i$ and $j$; the quadratic-form distance $\sqrt{(h - k)^\top A (h - k)}$, with $A$ a bin-similarity matrix, has the same form as a Mahalanobis distance.

Earth mover’s distance

The earth mover’s distance (EMD) treats one histogram as piles of earth and the other as holes, and measures the least work, mass times ground distance, needed to fill the holes. Rubner, Tomasi and Guibas (2000) defined it for signatures, sets of cluster centers $p_i$ with weights $w_{p_i}$, which include histograms as a special case. With flows $f_{ij} \ge 0$ from $p_i$ to $q_j$,

$$\mathrm{EMD}(P, Q) = \frac{\sum_{i,j} d_{ij} f_{ij}}{\sum_{i,j} f_{ij}}, \qquad \sum_j f_{ij} \le w_{p_i}, \quad \sum_i f_{ij} \le w_{q_j}, \quad \sum_{i,j} f_{ij} = \min\Big( \sum_i w_{p_i}, \sum_j w_{q_j} \Big),$$

where the flows minimize the numerator. Computing it is the transportation problem of linear programming (the Monge–Kantorovich problem). Rubner et al. credit the idea in vision to Peleg, Werman and Rom, who posed it as a matching problem between pixel “pebbles”; solving the transportation problem instead lets clustered mass move together. Its properties, as Rubner et al. state them:

• It is a metric when the ground distance is a metric and the two signatures have equal total weight. When the totals differ, the smaller signature is matched to part of the larger, which supports partial matching (an object against a cluttered image) but is not a metric.
• For one-dimensional histograms of equal total, the match distance, the ℓ1 distance between the cumulative histograms, is a special case of it. For normalized histograms with ground distance $|c_i - c_j|$ between bin centers, the EMD equals the 1-Wasserstein distance between the two distributions, and so the match distance times the bin width, which the code below checks against SciPy.
• It is expensive: they solved it with the transportation simplex method and note an $O(n^3 \log n)$ bound for signatures of $n$ clusters with a minimum-cost-flow formulation. For equal weights and a ground distance induced by a norm, the distance between the two centers of mass is a lower bound that let their system skip many EMD computations.

The Chamfer distance article covers distances between point sets, including the EMD between point clouds of equal size. The Fréchet Inception Distance is the squared 2-Wasserstein distance between two Gaussians, in closed form.

Properties

Measure	Compares	Metric?	Typical vision use
Euclidean (ℓ2)	real vectors	yes	SIFT matching, embedding retrieval
Squared Euclidean	real vectors	no (same ranking as ℓ2)	k-means, losses
Manhattan (ℓ1), ℓ∞	real vectors	yes	histogram comparison
ℓp, $p < 1$	real vectors	no	high-dimensional search (proposed)
Dot product	real vectors	no (a similarity)	classifier scores, unnormalized retrieval
Cosine similarity / $1 - \cos$	directions	no	normalized embeddings, CLIP-style retrieval
Angle	directions	yes	unit-sphere embeddings
Mahalanobis	real vectors	yes if $M$ positive definite	whitened descriptors, tracking gates
Hamming	binary codes	yes	BRIEF and ORB matching, hash codes
1 − intersection	histograms	yes for equal totals (= ℓ1/2)	color indexing
χ²	histograms	no	texture and shape-context histograms
Hellinger	histograms	yes	RootSIFT, histogram tracking
Bhattacharyya distance $-\ln \mathrm{BC}$	histograms	no	distribution comparison
KL divergence	histograms	no (not symmetric)	information-theoretic comparison
EMD	histograms, signatures	yes for metric ground distance and equal mass	color and texture retrieval

Monotone transforms preserve rankings, not properties. Squaring a distance, or replacing a similarity $s$ by $2 - 2s$, leaves every nearest-neighbor list, and so Recall@K, unchanged, but changes thresholds, averages and the metric axioms: a verification threshold set on cosine similarity must be converted when a system switches to Euclidean distance.

Invariances are built in. Cosine similarity ignores a vector’s scale, Hamming distance sees only which bits differ, histogram measures ignore where pixels are, and the Mahalanobis distance is unchanged by any invertible linear transform of the data once $\Sigma$ is re-estimated (our observation). Each invariance also discards information that another task may need.

Empirical comparisons favor no single measure. Rubner et al. (2001) compared nine families of measures on color and texture histograms for classification, retrieval and unsupervised segmentation, and found none best overall. In their classification experiments with large samples per histogram, χ² and the divergence measures (Kullback–Leibler and Jeffrey) did best, ℓ1 was best among the heuristic measures, and ℓ2 and ℓ∞ were consistently worse. With small samples, measures that use ground-distance information did better, the EMD in particular, which they attribute to its binning adapted to each image. For unsupervised segmentation of texture images, χ² on adaptive multivariate histograms had the lowest median error, 6.6% against 10.8% for the Kolmogorov–Smirnov statistic (their Table 2). In the color-retrieval experiments of Rubner et al. (2000) on 20,000 Corel images, the EMD on signatures retrieved the most relevant images for both query sets, but on coarse histograms of the horse queries χ² and the Jeffrey divergence beat the EMD on histograms; the EMD on histograms did better with finer bins.

Examples

The script below renders $64 \times 64$ grayscale scenes (intensities in $[0, 1]$) of random rectangles at two gray levels plus noise, and compares intensity histograms with the measures above. A query scene is compared with two candidates: the same scene with every pixel brightened by 0.06, an exposure change, and a different layout that shares the darker level but replaces the brighter one by a level 0.26 higher. The comparison is repeated at 8, 16 and 32 bins, and the 16-bin ranking is repeated for 20 more random scenes. The EMD uses the bin centers as ground positions and is checked against scipy.stats.wasserstein_distance. A second part tests the triangle inequality on a black-to-white triple: a uniform dark image, a uniform bright image, and an image that is half of each. It uses NumPy 2.3.5 and SciPy 1.16.3 and runs in under a second.

import numpy as np
import scipy
from scipy.stats import wasserstein_distance

rng = np.random.default_rng(0)
H = W = 64

def scene(levels, rng):
    """64x64 grayscale image in [0, 1]: random rectangles, each painted with one of
    `levels` (chosen at random), plus Gaussian noise of standard deviation 0.01."""
    img = np.full((H, W), levels[0])
    for _ in range(40):
        y, x = rng.integers(0, H - 8, 2)
        h, w = rng.integers(6, 20, 2)
        img[y:y + h, x:x + w] = rng.choice(levels)
    return np.clip(img + 0.01 * rng.standard_normal((H, W)), 0, 1)

def hist(img, bins):
    """Intensity histogram on [0, 1], normalized to sum 1, and the bin centres."""
    h, edges = np.histogram(img, bins=bins, range=(0, 1))
    return h / h.sum(), (edges[:-1] + edges[1:]) / 2

def measures(p, q, centres):
    nz = (p + q) > 0
    bc = np.sum(np.sqrt(p * q))                        # Bhattacharyya coefficient
    width = centres[1] - centres[0]
    emd = np.abs(np.cumsum(p - q)).sum() * width       # 1D EMD = L1 between CDFs x bin width
    assert np.isclose(emd, wasserstein_distance(centres, centres, p, q))
    return {"L1": np.abs(p - q).sum(),
            "L2": np.sqrt(((p - q) ** 2).sum()),
            "1-intersect": 1 - np.minimum(p, q).sum(),
            "chi2": 0.5 * np.sum((p[nz] - q[nz]) ** 2 / (p[nz] + q[nz])),
            "Hellinger": np.sqrt(max(1 - bc, 0)),
            "-ln BC": -np.log(bc) if bc > 0 else np.inf,
            "EMD": emd}

def vector_measures(p, q):
    """Measures that treat the histograms as plain vectors."""
    cos = p @ q / (np.linalg.norm(p) * np.linalg.norm(q))
    return {"squared L2": ((p - q) ** 2).sum(),
            "1 - cos": 1 - cos,
            "angle (rad)": np.arccos(np.clip(cos, -1, 1))}

# Example 1: an exposure change against a different scene.
def candidates(rng):
    query = scene([0.28, 0.64], rng)
    brighter = np.clip(query + 0.06, 0, 1)    # same scene, every pixel +0.06
    other = scene([0.28, 0.90], rng)           # new layout; one level shared, one moved by 0.26
    return query, brighter, other

print("NumPy", np.__version__, "SciPy", scipy.__version__)
query, brighter, other = candidates(rng)
print("seed 0: distance from the query to its brighter copy / to the other scene (* = brighter copy ranks first)")
print(f"{'':12s}" + "".join(f"{str(b) + ' bins':>18s}" for b in (8, 16, 32)))
table = {}
for bins in (8, 16, 32):
    pq, c = hist(query, bins)
    m_b, m_o = measures(pq, hist(brighter, bins)[0], c), measures(pq, hist(other, bins)[0], c)
    for k in m_b:
        table.setdefault(k, []).append(f"{m_b[k]:.3f}/{m_o[k]:.3f}{'*' if m_b[k] < m_o[k] else ' '}")
for k, cells in table.items():
    print(f"{k:12s}" + "".join(f"{cell:>18s}" for cell in cells))

wins = {}
c = hist(query, 16)[1]
for seed in range(1, 21):                      # 20 more scenes, 16 bins
    q, b, o = (hist(im, 16)[0] for im in candidates(np.random.default_rng(seed)))
    m_b, m_o = measures(q, b, c), measures(q, o, c)
    for k in m_b:
        wins[k] = wins.get(k, 0) + (m_b[k] < m_o[k])
print("seeds 1-20, 16 bins, brighter copy ranked first: " + ", ".join(f"{k} {v}/20" for k, v in wins.items()))

# Example 2: the triangle inequality on a dark image, a bright image and their mixture.
dark, bright = np.full((H, W), 0.2), np.full((H, W), 0.8)
mixed = np.where(np.arange(W) < W // 2, 0.2, 0.8)[None, :].repeat(H, 0)   # left half dark
P, R, Q = (hist(im, 16)[0] for im in (dark, bright, mixed))
c = hist(dark, 16)[1]
print("\ntriangle inequality d(dark, bright) <= d(dark, mixed) + d(mixed, bright)?")
def all_measures(p, q):
    return {**measures(p, q, c), **vector_measures(p, q)}
for k in all_measures(P, R):
    d_pr, d_pq, d_qr = all_measures(P, R)[k], all_measures(P, Q)[k], all_measures(Q, R)[k]
    print(f"  {k:12s} {d_pr:6.3f} <= {d_pq + d_qr:6.3f}  {'holds' if d_pr <= d_pq + d_qr + 1e-12 else 'VIOLATED'}")

NumPy 2.3.5 SciPy 1.16.3
seed 0: distance from the query to its brighter copy / to the other scene (* = brighter copy ranks first)
                        8 bins           16 bins           32 bins
L1                0.050/0.733*      1.921/0.733       1.950/0.733 
L2                0.034/0.456*      0.999/0.456       0.790/0.397 
1-intersect       0.025/0.366*      0.961/0.366       0.975/0.366 
chi2              0.013/0.332*      0.929/0.332       0.967/0.332 
Hellinger         0.113/0.575*      0.921/0.575       0.972/0.576 
-ln BC            0.013/0.402*      1.886/0.402       2.904/0.402 
EMD               0.003/0.097*      0.062/0.099*      0.060/0.100*
seeds 1-20, 16 bins, brighter copy ranked first: L1 0/20, L2 0/20, 1-intersect 0/20, chi2 0/20, Hellinger 0/20, -ln BC 0/20, EMD 20/20

triangle inequality d(dark, bright) <= d(dark, mixed) + d(mixed, bright)?
  L1            2.000 <=  2.000  holds
  L2            1.414 <=  1.414  holds
  1-intersect   1.000 <=  1.000  holds
  chi2          1.000 <=  0.667  VIOLATED
  Hellinger     1.000 <=  1.082  holds
  -ln BC          inf <=  0.693  VIOLATED
  EMD           0.562 <=  0.562  holds
  squared L2    2.000 <=  1.000  VIOLATED
  1 - cos       1.000 <=  0.586  VIOLATED
  angle (rad)   1.571 <=  1.571  holds

With 8 bins, 0.125 wide, the two gray levels were chosen so that the 0.06 shift keeps them in their bins, and every measure finds the brightened copy closer. With 16 or 32 bins the shift carries almost all the mass out of its bin: the bin-by-bin measures see nearly disjoint histograms, near their maximum values (2 for ℓ1, 1 for χ², Hellinger and one minus intersection), and rank first the different scene, which shares one of the query’s levels exactly. The EMD sees mass moved about 0.06 in intensity against about 0.1 for the other scene, and ranks the brighter copy first at every bin count and in all 20 further scenes, where every bin-by-bin measure ranked it second. This is the bin-boundary sensitivity Rubner et al. describe: the bin-by-bin answer depends on whether a shift crosses a boundary, not on its size. Whether the brighter copy should rank first depends on the task: yes for recognizing a scene under a lighting change, no for retrieving images by exposure. In the 8-bin row the Hellinger distance is the largest of the small values only because it takes the square root of $1 - \mathrm{BC}$, about 0.013 here; the square root changes values, not rankings.

The triangle test agrees with the table above. ℓ1, ℓ2, intersection, the EMD and the angle meet the bound with equality and the Hellinger distance with room to spare, while χ², the Bhattacharyya distance (infinite between histograms with no common bin), the squared Euclidean distance and the cosine distance make the detour through the half-and-half image shorter than the direct path. A search that prunes candidates with the triangle inequality could discard true neighbors with these four.

Common Misconceptions

• “Cosine distance is a metric.” $1 - \cos$ violates the triangle inequality, as the example shows; the angle between the vectors, or the Euclidean distance between their normalized versions, is the metric version with the same ranking.
• “χ² and Euclidean distance differ only in scale.” χ² divides each squared difference by the bin’s total mass, so a difference in a sparse bin counts for more than the same difference in a full one; it also violates the triangle inequality.

Where It Is Used

• Descriptor matching. Real-valued descriptors such as SIFT are matched by Euclidean distance, binary ones such as BRIEF and ORB by Hamming distance; feature matching covers the matching strategies.
• Histogram comparison. Color indexing with histogram intersection, object tracking with the Bhattacharyya coefficient, shape contexts and texture with χ², and color and texture retrieval with the EMD.
• Embedding retrieval and verification. Embeddings are ranked by cosine similarity or Euclidean distance, usually after ℓ2 normalization; image–text retrieval does so across modalities with models such as CLIP. Approximate nearest-neighbor search makes such rankings fast over millions of vectors, and metric learning and the triplet loss train embeddings for a chosen measure.
• Tracking association. Data association gates detections with the Mahalanobis distance from a Kalman filter’s prediction, and DeepSORT adds the cosine distance between appearance embeddings.
• Evaluation. Many evaluation metrics are distances between an output and a reference: the mean squared error between images, the Chamfer distance between point clouds, and learned perceptual distances such as LPIPS.