Near-Duplicate Video Detection at Upload

A cryptographic hash of a video file tells you whether two uploads are byte-identical, which they essentially never are. A perceptual hash tells you whether they look the same, and it survives the exact transformations — re-encoding, rescaling, a change of container — that a re-upload always applies.

What a perceptual hash computes

The most widely implemented perceptual image hash is the DCT hash, usually called pHash after the reference implementation described in Christoph Zauner’s 2010 thesis on robust image hashing. The procedure on a single frame is short enough to state completely.

1. Convert the frame to greyscale and resize it to a small fixed square — 32×32 is the common choice. Both steps are deliberate destruction: colour and fine detail are exactly the things a re-encode changes.
2. Apply a two-dimensional discrete cosine transform. This re-expresses the 32×32 block of pixels as 1,024 coefficients ordered roughly from coarse structure to fine detail.
3. Keep only the top-left 8×8 block of coefficients — the lowest spatial frequencies — and discard the DC term at position (0,0), which carries only overall brightness.
4. Take the median of the remaining 63 coefficients and emit one bit per coefficient: 1 if it is above the median, 0 if below. The result is a 64-bit value.

Two hashes are compared by Hamming distance — the number of differing bits, from 0 to 64. Because the bits are thresholded against their own median, the hash is invariant to any monotonic change in overall brightness, and because everything above the eighth frequency was discarded, it is invariant to a large amount of fine detail.

Why re-encoding does not move the hash

This is the part that looks like a coincidence and is not. A lossy video codec works by transforming blocks of pixels into the frequency domain and quantising the coefficients — coarsely at high frequencies, finely at low ones. That is the compression: the encoder is betting that you will not notice the loss of fine detail, so fine detail is what it throws away first.

The perceptual hash throws away exactly the same thing, and it throws it away first. By the time the DCT hash has kept only the top-left 8×8 coefficients of a 32×32 reduction, everything the encoder degrades has already been discarded from the hash’s input. Re-encoding a 1080p clip at a third of its original bitrate visibly softens the picture and typically leaves the hash of a given frame unchanged or different in one or two bits. The hash and the codec agree about which information matters, so the codec cannot damage the hash without also making the video look obviously wrong.

The same argument explains resolution independence. The hash resizes every input to 32×32 before it does anything else, so a 4K master and a 480p re-upload of the same frame converge to nearly the same input. Scaling, mild sharpening, a change of container from MP4 to WebM and a chroma subsampling change all leave the hash alone for the same reason.

same frame, three encodings, 64-bit DCT hash

  1080p master, 12 Mbit/s     9f2c81b4a0d3e761
  720p re-encode, 2 Mbit/s    9f2c81b4a0d3e763    Hamming distance 1
  480p re-encode, 600 kbit/s  9f2c81b5a0d3e763    Hamming distance 2

typical thresholds on 64-bit hashes
  distance <=  5     near certainly the same frame
  distance  6..10    same shot or a close variant, needs corroboration
  distance > 10      treat as different

The edits that do break it

A perceptual hash is invariant to changes that preserve the image and not to changes that move it. That distinction is sharper than most documentation makes it sound, and it decides what a hash-based deduplication system can and cannot catch.

• Cropping and letterboxing. A 10% crop shifts every pixel and changes the aspect ratio, so the 32×32 reduction samples a different image entirely. The hash changes completely. So does adding black bars, which is why a pipeline should detect and strip uniform borders before hashing.
• Horizontal mirroring. A flipped copy is visually near-identical to a human and has an unrelated hash. The standard defence is to hash the frame and its mirror and index both, doubling the index for complete coverage of one very common evasion.
• Rotation. Same problem, and the same defence at four multiples of ninety degrees. Arbitrary small rotations are not handled by either and need a feature-matching approach instead.
• Large overlays. A small corner watermark perturbs a couple of bits. A full-width banner across the top third changes the low-frequency structure and can move the hash past any usable threshold.
• Speed changes and re-timing. These do not change any individual frame’s hash at all, but they change which frames exist and where, which is a problem for the sequence matching in the next section rather than for the hash.

When crop-invariance is genuinely required, the answer is not a better image hash. It is a descriptor built from local features that survive translation — or a purpose-built video descriptor such as the MPEG-7 Video Signature, which FFmpeg implements as the signature filter and documents in the FFmpeg filters reference. Content-based retrieval over learned embeddings is the other route and tolerates far more editing, at a much higher cost per frame.

From frame matches to a video match

A single matching frame proves very little. Two unrelated news broadcasts share a shot of the same building; two gameplay videos share the same loading screen. The claim you actually want to make is that a run of frames matches in the same order with a consistent time offset.

So the unit of comparison is a sequence. Extract a hash at a fixed rate — one per second is a common choice, or one per shot from keyframe extraction — and the video becomes an ordered string of 64-bit symbols. Matching two videos is then approximate string matching over that sequence, where two symbols are equal if their Hamming distance is under threshold.

upload   h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 h12
known             m1 m2 m3 m4 m5 m6

matched run: upload[3..8] vs known[1..6], offset +2, 6/6 within distance 5

decision inputs
  matched run length        6 hashes  = 6 s of footage at 1 hash/s
  offset consistency        constant +2 throughout
  fraction of the upload    6 / 12    = 50% of the upload is the known clip
  fraction of the known     6 / 6     = 100% of the known clip is present

The last two ratios are what let you distinguish cases that a match-count alone cannot. A trailer is a short run that covers 100% of the trailer and 2% of the film. A re-upload covers close to 100% of both. A compilation covers 100% of several short known clips and a fraction of itself. These call for different actions, and only the ratios tell them apart. A constant offset also rules out coincidental matches: unrelated videos that share three frames will not share them at a consistent lag.

Searching without comparing every pair

The naive comparison does not survive contact with a real corpus. A library of one million videos at twenty hashes each holds 20 million hashes; comparing one new upload against all of them is 20 million Hamming distances, which is cheap, but building the corpus by comparing every pair is on the order of 2×10¹⁴ comparisons, which is not.

The standard fix is banding, the same trick used for locality-sensitive hashing. Split each 64-bit hash into four 16-bit bands. Two hashes within a Hamming distance of 3 must agree exactly on at least one band, by the pigeonhole principle: three differing bits cannot be spread across four bands without leaving one untouched. So index each hash four times, once per band, and a candidate lookup becomes four exact dictionary lookups instead of a scan. Only the candidates that share a band are compared bit by bit.

The generalisation is worth remembering because it sets the design: to guarantee a candidate is found at distance up to d, you need at least d + 1 bands. Eight 8-bit bands guarantee recall up to distance 7 and return more candidates to verify; four bands are cheaper and silently miss matches past distance 3. A BK-tree over the Hamming metric is the other classical structure and gives exact radius-bounded search without the banding parameter, at the cost of poor cache behaviour on large corpora.