Perceptual hashing

Deep dive

How it works

In: decoded image, hash type, distance threshold t · Out: 64- or 256-bit hash; for matching, the ids of stored hashes within t bits · State: none for hashing; matching keeps a hash list and an index · Cost: one pass over the pixels plus a few thousand multiply-adds; compare = XOR + popcount

1. Decode and convert to grayscale (luma); colour is dropped.
2. Downscale with an area (box-like) filter so every source pixel counts: 32x32 for pHash, 9x8 for dHash, 64x64 for PDQ.
3. aHash: bit = pixel above the grid mean. dHash: bit = pixel brighter than its right neighbour.
4. pHash: 2-D DCT-II of the 32x32 grid, keep the 8x8 low-frequency corner, bit = coefficient above the median. The DC term (overall brightness) is excluded, so a brightness shift moves few bits.
5. PDQ: 64x64 downscale (Jarosz filter), DCT, 16x16 low-frequency block, bit = above the median: 256 bits, plus a 0-100 quality score from image gradients.
6. Video: PDQ per sampled frame; TMK+PDQF condenses frame features into a fixed-length summary compared by cosine similarity.
7. Compare: popcount(a ^ b) <= t.
8. Search a list: scan, or split hashes into m blocks; a pair within r bits has a block within r/m bits, so index blocks exactly and verify candidates (code on the SimHash page).

Operational process (known-item matching):

1. Hash list: one entry per confirmed item (hash, category, source, owner, review date); hashes, not images, are what industry programmes exchange.
2. Hash each upload on the transcoded copy and look it up.
3. Bands: distance at or near 0 follows policy automatically; a middle band goes to human review; above that no match.
4. Review outcomes are labels: a false positive removes or excludes the list entry, and the labelled pairs re-tune the threshold.
5. Keep an audit log and an appeal path; retention and reporting duties for sensitive lists are for counsel to decide.

Code

use std::f32::consts::PI;
use std::time::Instant;

struct Img { w: usize, h: usize, px: Vec<f32> } // grayscale 0..255, row-major

fn rnd(mut s: u64) -> f32 { // stateless hash -> [0,1)
    s ^= s >> 33; s = s.wrapping_mul(0xff51afd7ed558ccd); s ^= s >> 33;
    (s >> 40) as f32 / (1u64 << 24) as f32
}

/// Synthetic "photo": gradient + sines + blobs from a seed; same seed, other size = resized copy.
fn scene(seed: u64, w: usize, h: usize) -> Img {
    let p: Vec<f32> = (0..32).map(|i| rnd(seed * 97 + i)).collect();
    let px = (0..w * h).map(|i| {
        let (u, v) = ((i % w) as f32 / w as f32, (i / w) as f32 / h as f32);
        let mut s = 128.0 + 160.0 * ((p[0] - 0.5) * u + (p[1] - 0.5) * v);
        for k in 0..4 {
            let (fx, fy) = (1.0 + 4.0 * p[2 + 3 * k], 1.0 + 4.0 * p[3 + 3 * k]);
            s += 40.0 * (2.0 * PI * (fx * u + fy * v) + 6.0 * p[4 + 3 * k]).sin();
            let (cx, cy, r) = (p[14 + 3 * k], p[15 + 3 * k], 0.05 + 0.15 * p[16 + 3 * k]);
            s += 160.0 * (p[26 + k] - 0.5) * (-((u - cx).powi(2) + (v - cy).powi(2)) / (r * r)).exp();
        }
        s.clamp(0.0, 255.0)
    }).collect();
    Img { w, h, px }
}

/// Box filter: each output pixel is the mean of the source rectangle it covers.
fn box_down(im: &Img, ow: usize, oh: usize) -> Vec<f32> {
    let mut out = vec![0.0; ow * oh];
    for oy in 0..oh {
        let (y0, y1) = (oy * im.h / oh, ((oy + 1) * im.h / oh).max(oy * im.h / oh + 1));
        for ox in 0..ow {
            let (x0, x1) = (ox * im.w / ow, ((ox + 1) * im.w / ow).max(ox * im.w / ow + 1));
            let s: f32 = (y0..y1).map(|y| im.px[y * im.w + x0..y * im.w + x1].iter().sum::<f32>()).sum();
            out[oy * ow + ox] = s / ((y1 - y0) * (x1 - x0)) as f32;
        }
    }
    out
}

/// pHash: 32x32 -> DCT-II -> 8x8 low-frequency corner -> bit = coefficient > median of the 63 non-DC ones.
fn phash(im: &Img) -> u64 {
    const N: usize = 32;
    let g = box_down(im, N, N);
    let b: Vec<f32> = (0..8 * N).map(|i| ((PI / N as f32) * ((i % N) as f32 + 0.5) * (i / N) as f32).cos()).collect(); // DCT-II basis
    let mut rows = [[0f32; 8]; N]; // separable: only the 8 needed frequencies per axis
    for y in 0..N { for u in 0..8 { rows[y][u] = (0..N).map(|x| g[y * N + x] * b[u * N + x]).sum(); } }
    let mut f = [0f32; 64];
    for v in 0..8 { for u in 0..8 { f[v * 8 + u] = (0..N).map(|y| rows[y][u] * b[v * N + y]).sum(); } }
    let mut ac = f[1..].to_vec(); // DC only encodes overall brightness
    ac.sort_by(|a, b| a.partial_cmp(b).unwrap());
    (1..64).fold(0u64, |h, i| h | ((f[i] > ac[31]) as u64) << i) // bit 0 (DC) stays 0
}

/// dHash: 9x8 grid, bit = pixel brighter than its right neighbour.
fn dhash(im: &Img) -> u64 {
    let g = box_down(im, 9, 8);
    (0..64).fold(0u64, |h, i| { let k = i / 8 * 9 + i % 8; h | ((g[k] > g[k + 1]) as u64) << i })
}

fn dist(a: u64, b: u64) -> u32 { (a ^ b).count_ones() }

fn main() {
    let a = scene(1, 256, 192);
    let resized = scene(1, 150, 113);
    let edited = Img { px: a.px.iter().enumerate().map(|(i, &v)| // +20 brightness, noise, 16 grey levels
        (((v + 20.0 + 12.0 * (rnd(i as u64 + 7) - 0.5)).clamp(0.0, 255.0) / 16.0).round() * 16.0).min(255.0)).collect(), ..a };
    for (name, f) in [("phash", phash as fn(&Img) -> u64), ("dhash", dhash)] {
        let d_unrel: Vec<u32> = (2..22).map(|s| dist(f(&a), f(&scene(s, 256, 192)))).collect();
        let (d_same, d_res, d_edit) = (dist(f(&a), f(&scene(1, 256, 192))), dist(f(&a), f(&resized)), dist(f(&a), f(&edited)));
        let lo = *d_unrel.iter().min().unwrap();
        println!("{name}: same {d_same}, resized {d_res}, edited {d_edit}, 20 unrelated {lo}..{}", d_unrel.iter().max().unwrap());
        assert!(d_same == 0 && d_res <= 8 && d_edit <= 8 && lo > 12);
        let (n, t, mut acc) = (5000, Instant::now(), 0u64);
        for _ in 0..n { acc = acc.wrapping_add(f(std::hint::black_box(&a))); }
        println!("{name}: {:.0} hashes/s (256x192 input, decode excluded, {acc:x})", n as f64 / t.elapsed().as_secs_f64());
    }
}

Measured on this Mac (Apple M4 Pro), release build: pHash distances same 0, resized 6, brightness+noise+16-level 4, 20 unrelated scenes 22 to 42; dHash 0, 5, 0, 14 to 55. Over 8 runs: pHash 68,000 to 95,000, dHash 145,000 to 170,000 hashes/s (machine not idle, load average about 8).

Complexity and constants

• Hash: O(W x H) downscale (each pixel read once), then 32x32x8 + 8x8x32 multiply-adds for the separable DCT. Compare: 1 to 4 words of XOR + popcount.
• Memory: 8 B per pHash, 32 B per PDQ; 100M PDQ hashes = 3.2 GB (arithmetic).
• Brute-force scan, measured on this Mac (Apple M4 Pro), one thread, 10M random 256-bit hashes (320 MB): 16.9 ms per query, 0.59 G compares/s, memory-bandwidth bound.
• Block split pays only when the per-block radius r/m is small (Norouzi et al.: multi-index hashing; a BK-tree is the alternative). PDQ's suggested threshold, 31 of 256 bits, is wide, so large lists are scanned or use a binary Faiss index.

Efficiency

• Cost: measured on this Mac (Apple M4 Pro), one thread, decode excluded, 256x192 input: pHash about 70,000 to 95,000/s (about 10 to 14 µs), dHash about 145,000 to 170,000/s. Real photos have far more pixels, so downscale and JPEG decode (not measured here) dominate. Compare: nanoseconds. Bound: decode and memory bandwidth.
• Levers:
  • decode JPEG at reduced size (1/2, 1/4, 1/8 scaling in common JPEG decoders) — skips most of the decode (gain not measured) — JPEG sources.
  • hash from the thumbnail path you already compute — no second decode — when thumbnails are generated anyway.
  • SIMD popcount scan or a binary Faiss index — PDQ README: Faiss matching "proven up to 4000 images/sec" — large lists.
  • block-split or multi-index tables — sub-linear for small radii (Norouzi et al.) — small thresholds.
• Naive → standard → state of the art:
  • full decode, compare to every entry · O(n) per upload
  • 64/256-bit hash, popcount scan, review band · 16.9 ms per 10M entries per core (measured above)
  • reduced-size decode, index, classifier and review on top · sub-linear lookup; review capacity becomes the cost

Implementation notes

• Use one pipeline for hashing and the list: the PDQ README warns that different image libraries give different hashes for the same image and tests ports against reference byte arrays.
• Store algorithm name and version with every hash; different algorithms are not comparable.
• Choose t on labelled pairs from your own data: count false positives and negatives per distance, pick what review can absorb. PDQ's README suggests starting at distance <= 31 and discarding quality <= 49, then tuning. TMK+PDQF's README suggests 0.7 for both stages and 0.9 or higher for near-exact; it is weak on short clips.
• Drop low-quality hashes (flat images): they collide with unrelated ones.

Pitfalls

• A fixed distance is not a fixed false-positive rate: ten times more list entries means about ten times more chance matches at the same threshold.
• Hashes find look-alikes, not meaning: plain skies and stock layouts can match; allow review and removal.
• A mistaken list entry harms real users; keep each entry's source and owner.
• Large crops and rotations reduce match rates, and a hash only finds listed items: use it as one layer beside classifiers, user reports and review.

Variants and alternatives

In production

• Meta open-sourced PDQ and TMK+PDQF in 2019 for sharing photo and video hashes across companies.
• Microsoft PhotoDNA (developed with Dartmouth College in 2009, donated to NCMEC, per Microsoft) is used by organisations worldwide.

Implementations

Sources

• Christoph Zauner, Implementation and Benchmarking of Perceptual Image Hash Functions, Master's thesis, Hagenberg, July 2010. pdf
• Meta, PDQ and TMK+PDQF algorithm description (hashing.pdf) and reference code. pdf · code
• Mohammad Norouzi, Ali Punjani, David J. Fleet, Fast search in Hamming space with multi-index hashing, CVPR 2012, pp. 3108-3115. doi
• Microsoft, PhotoDNA. page
• Neal Krawetz, Kind of Like That (difference hash), The Hacker Factor Blog, 2013. post