Building a Perceptual Hash Pipeline for Video Deduplication in Python
A single viral clip never stays a single file
Within hours of a video trending, our crawlers pull the "same" clip back a dozen times: re-encoded at a lower bitrate, letterboxed for a vertical feed, watermarked by an aggregator, trimmed by three seconds, or mirrored with a 2% zoom to dodge platform fingerprinting. A byte-for-byte SHA-256 sees twelve unique videos. Our users see one clip spammed across their feed.
For a European viral-video discovery product where feed quality is the value proposition, that is an existential bug, not a cosmetic one. At ViralVidVault we lean on perceptual hashing to collapse those near-duplicates before anything reaches the ranking model.
This post is the actual approach we run in production: how to turn frames into hashes that survive re-encoding, how to aggregate per-frame hashes into a per-video fingerprint, and how to query millions of them without a GPU or a dedicated vector database. The heavy lifting is Python, the storage and query layer is PHP 8.4 on SQLite in WAL mode, and the hot comparison path is a small Go helper. No proprietary services, nothing that ships a raw frame off our origin.
Why cryptographic hashing is the wrong tool
Cryptographic hashes are designed to be maximally sensitive: flip one bit of input and roughly half the output bits change. That is exactly what you want for integrity checking and exactly what you do not want for deduplication. Two visually identical frames that differ only because one went through an extra H.264 pass will produce completely unrelated SHA-256 digests. There is no notion of "close."
Perceptual hashing inverts the goal. A perceptual hash (pHash) is a short fixed-length code where visually similar inputs produce similar codes, and "similar" is measured with Hamming distance - the number of differing bits. Two frames that a human would call the same clip land within a handful of bits of each other.
The properties we actually need:
- Robust to re-encoding - bitrate, codec, and container changes barely move the hash.
- Robust to scaling and mild cropping - the hash is computed on a downscaled, normalized image.
- Robust to brightness and contrast shifts - a DCT-based hash keys off relative frequency structure, not absolute pixel values.
- Fragile to real content changes - a genuinely different scene produces a genuinely distant hash.
The most reliable variant in our testing is the DCT-based hash. You resize a frame to a small square, take a 2D discrete cosine transform, keep only the low-frequency coefficients (where the perceptually meaningful structure lives), and threshold each coefficient against the median. The result is a 64-bit integer.
Extracting a stable frame signature
The first stage reads a video, samples frames at a fixed cadence, and computes one 64-bit pHash per sampled frame. Sampling every couple of seconds is enough - viral clips are short, and consecutive frames are near-identical anyway, so hashing every frame is wasted work.
import cv2
import numpy as np
def dct_phash(frame: np.ndarray, hash_size: int = 8, highfreq_factor: int = 4) -> int:
"""Return a 64-bit DCT perceptual hash for a single BGR frame."""
img_size = hash_size * highfreq_factor # 32x32 by default
gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
resized = cv2.resize(gray, (img_size, img_size), interpolation=cv2.INTER_AREA)
dct = cv2.dct(np.float32(resized))
low = dct[:hash_size, :hash_size].flatten()
# Exclude the DC term (index 0) from the threshold; it only carries brightness.
med = np.median(low[1:])
bits = low > med
value = 0
for bit in bits:
value = (value << 1) | int(bit)
return value
def iter_keyframes(path: str, every_seconds: float = 2.0):
"""Yield (timestamp_seconds, frame) sampled at a fixed cadence."""
cap = cv2.VideoCapture(path)
fps = cap.get(cv2.CAP_PROP_FPS) or 25.0
step = max(1, int(round(fps * every_seconds)))
idx = 0
try:
while True:
ok, frame = cap.read()
if not ok:
break
if idx % step == 0:
yield idx / fps, frame
idx += 1
finally:
cap.release()
def video_signature(path: str) -> list[tuple[float, int]]:
"""Compute the temporal pHash signature of a video."""
return [(ts, dct_phash(frame)) for ts, frame in iter_keyframes(path)]
A 40-second clip sampled every two seconds yields ~20 hashes: a compact temporal fingerprint that is cheap to store and cheap to compare.
Two things matter here. First, INTER_AREA interpolation is deliberate - it is the correct resampling filter for downscaling and avoids the ringing artifacts that bilinear introduces, which would otherwise perturb the DCT. Second, excluding the DC coefficient from the median threshold is what buys brightness invariance; the DC term is essentially the average luminance, so a video that got brightened by an aggregator would otherwise flip a predictable set of bits.
From frames to a video-level fingerprint
A per-frame hash is not enough on its own. Viral content is full of shared segments - the same reaction meme spliced into a hundred different compilations, the same stock intro card. If you dedupe on a single frame you will merge videos that share one common shot but are otherwise unrelated.
The fix is to treat the video as a set of frame hashes and ask a temporal question: what fraction of one video's frames have a near-match somewhere in the other video? Comparing every frame of every candidate against every frame of every other video is O(n²) and does not scale. Within a single pairwise comparison the frame counts are small, so brute force is fine there. The scaling problem is finding candidate videos in the first place, and for that we build a BK-tree - a metric tree that indexes items by Hamming distance and lets us pull "everything within k bits of this hash" in sub-linear time.
def hamming(a: int, b: int) -> int:
return (a ^ b).bit_count() # Python 3.10+ popcount
class BKTree:
"""Burkhard-Keller tree over 64-bit hashes with Hamming distance."""
def __init__(self) -> None:
self.root: tuple[int, dict[int, object]] | None = None
def add(self, value: int) -> None:
if self.root is None:
self.root = (value, {})
return
node, children = self.root
while True:
d = hamming(value, node)
if d == 0:
return # exact duplicate already indexed
if d in children:
node, children = children[d]
else:
children[d] = (value, {})
return
def query(self, value: int, max_dist: int) -> list[tuple[int, int]]:
if self.root is None:
return []
results: list[tuple[int, int]] = []
stack = [self.root]
while stack:
node, children = stack.pop()
d = hamming(value, node)
if d <= max_dist:
results.append((d, node))
# Triangle inequality prunes whole subtrees.
lo, hi = d - max_dist, d + max_dist
for edge, child in children.items():
if lo <= edge <= hi:
stack.append(child)
return results
def temporal_overlap(sig_a: list[int], sig_b: list[int], max_dist: int = 6) -> float:
"""Fraction of sig_a frames that have a near-match in sig_b."""
if not sig_a:
return 0.0
matched = 0
for ha in sig_a:
if any(hamming(ha, hb) <= max_dist for hb in sig_b):
matched += 1
return matched / len(sig_a)
The BK-tree exploits the triangle inequality: if the query is distance d from a node, any item within max_dist of the query must be between d - max_dist and d + max_dist from that node, so every other subtree is pruned. In practice a tree over a few hundred thousand 64-bit hashes answers a max_dist = 6 query by touching a low-single-digit percentage of nodes.
The two-threshold design is what keeps precision high. A single frame within 6 bits is a candidate, not a verdict. The verdict comes from temporal_overlap: we only declare two videos duplicates when, say, 70% of the shorter video's frames find a near-match in the longer one. A shared intro card matches on two or three frames and gets correctly rejected; a genuine re-upload matches on nearly all of them.
Storing and querying at scale with SQLite WAL
Our origin runs LiteSpeed with PHP 8.4 over SQLite in WAL mode, and I am not going to bolt a vector database onto that for a problem SQLite handles fine. The trick for making Hamming-distance lookups indexable in a plain relational store is banded LSH. Split the 64-bit hash into four 16-bit bands. By the pigeonhole principle, if two hashes differ by at most 3 bits total, at least one of the four bands must be bit-identical. So we index each band, query by exact band equality to get a candidate set, and only then compute exact Hamming distance in application code. This turns an un-indexable "within k bits" query into four indexed equality lookups.
One SQLite caveat worth stating plainly: its INTEGER type is a signed 64-bit value, and a pHash with the top bit set exceeds PHP_INT_MAX as an unsigned number. On a 64-bit PHP build the bit pattern round-trips correctly because PHP ints are also 64-bit signed - the same bits, just interpreted as negative. We compare bit patterns, never magnitudes, so this is safe as long as you never do arithmetic ordering on the raw hash.
<?php declare(strict_types=1);
final class PerceptualHashStore
{
public function __construct(private \PDO $db)
{
$this->db->setAttribute(\PDO::ATTR_ERRMODE, \PDO::ERRMODE_EXCEPTION);
$this->db->exec('PRAGMA journal_mode = WAL');
$this->db->exec('PRAGMA synchronous = NORMAL');
$this->db->exec(<<<SQL
CREATE TABLE IF NOT EXISTS frame_hash (
video_id TEXT NOT NULL,
frame_ts REAL NOT NULL,
phash INTEGER NOT NULL,
band0 INTEGER NOT NULL,
band1 INTEGER NOT NULL,
band2 INTEGER NOT NULL,
band3 INTEGER NOT NULL
)
SQL);
foreach (['band0', 'band1', 'band2', 'band3'] as $b) {
$this->db->exec("CREATE INDEX IF NOT EXISTS idx_$b ON frame_hash($b)");
}
}
public function insert(string $videoId, float $ts, int $phash): void
{
$stmt = $this->db->prepare(
'INSERT INTO frame_hash (video_id, frame_ts, phash, band0, band1, band2, band3) VALUES (?, ?, ?, ?, ?, ?, ?)'
);
$stmt->execute([
$videoId, $ts, $phash,
$phash & 0xFFFF,
($phash >> 16) & 0xFFFF,
($phash >> 32) & 0xFFFF,
($phash >> 48) & 0xFFFF,
]);
}
/** @return array<string,int> videoId => best (lowest) Hamming distance */
public function findCandidates(int $phash, int $maxDist = 6): array
{
$bands = [
$phash & 0xFFFF,
($phash >> 16) & 0xFFFF,
($phash >> 32) & 0xFFFF,
($phash >> 48) & 0xFFFF,
];
$sql = 'SELECT video_id, phash FROM frame_hash WHERE band0 = ? OR band1 = ? OR band2 = ? OR band3 = ?';
$stmt = $this->db->prepare($sql);
$stmt->execute($bands);
$out = [];
foreach ($stmt->fetchAll(\PDO::FETCH_ASSOC) as $row) {
$dist = self::hamming($phash, (int)$row['phash']);
if ($dist <= $maxDist) {
$id = $row['video_id'];
if (!isset($out[$id]) || $dist < $out[$id]) {
$out[$id] = $dist;
}
}
}
return $out;
}
private static function hamming(int $a, int $b): int
{
$x = $a ^ $b;
$count = 0;
while ($x !== 0) {
$count++;
$x &= $x - 1; // clear lowest set bit
}
return $count;
}
}
The band-equality query is fully indexed, so even a table with millions of frame rows returns a candidate set in low single-digit milliseconds. WAL mode matters here because the deduplication check runs on the ingest path while the crawler is still writing new frame hashes; WAL lets readers and a writer proceed concurrently without the reader blocking. synchronous = NORMAL is the right durability trade for a rebuildable derived index - if we lose the last few hashes in a crash we recompute them from source, so we do not need the fsync-per-commit cost of FULL.
Banded LSH with 16-bit bands guarantees recall for distances up to 3 bits and gives very high (not guaranteed) recall up to 6. For our workload that is the right dial: re-uploads cluster well under 6 bits, and the rare frame that lands at exactly the boundary still gets caught because we match on the whole temporal signature, not one frame.
Keeping the hot path fast in Go
The PHP layer is perfect for the ingest-time single-frame check. The one place it strains is the nightly re-clustering job, where we compare every video's full signature against every candidate cluster - millions of pairwise Hamming computations. PHP's byte-at-a-time popcount is fine for one comparison and wasteful for millions. We front that batch job with a tiny Go service that the cron script pipes signatures into over a Unix socket. Go's math/bits.OnesCount64 compiles to a single POPCNT instruction.
package dedup
import "math/bits"
func hamming(a, b uint64) int {
return bits.OnesCount64(a ^ b)
}
// NearDuplicate reports whether two temporal signatures overlap enough to be
// considered the same clip. maxDist is the per-frame bit tolerance; minRatio
// is the fraction of a-frames that must find a match in b.
func NearDuplicate(a, b []uint64, maxDist int, minRatio float64) bool {
if len(a) == 0 {
return false
}
matched := 0
for _, fa := range a {
for _, fb := range b {
if hamming(fa, fb) <= maxDist {
matched++
break
}
}
}
return float64(matched)/float64(len(a)) >= minRatio
}
This is deliberately boring code, and that is the point. The whole architecture stays as a handful of small, inspectable pieces - Python for the frame math, SQLite for durable indexing, Go for the arithmetic-bound batch - rather than one framework you cannot reason about. When a false merge shows up in the feed, I can trace it from the raw frame hash to the band query to the overlap ratio in about five minutes.
Tuning thresholds, and the GDPR angle
The two numbers that decide everything are the per-frame bit tolerance and the temporal overlap ratio. Some field notes from running this on European viral content:
- Per-frame
max_distof 6 out of 64 is a good default. Below 4 you start missing aggressive re-encodes; above 10 you start merging visually similar but different clips. - Temporal overlap ratio of 0.7 works well for short viral clips; for longer content (e.g., compilations > 2 minutes) we raise it to 0.85 to avoid false merges from repeated stock footage.
The GDPR angle: we never ship a raw frame off the origin server. All hashing is done on the same machine that ingests the video. The 64-bit hash is stored; the source video is discarded after processing if it is an exact duplicate of a previously seen clip at the pHash level. This means we retain only the perceptual fingerprints for near-duplicate detection, not the original bytes - a useful property when auditors ask what personal data the dedup pipeline touches.
Comments
No comments yet. Start the discussion.