Tag: near-duplicate detection

  • Video Deduplication: Near-Duplicate Detection for Training Data

    Web-scale video collections are full of copies: re-uploads, mirrored and cropped versions, compilations that stitch together other people's clips, and reaction videos with the original running in a corner. Exact duplicates are easy to remove. Near-duplicates decide how much of your training budget goes to the same footage seen ten times. This guide builds a layered video deduplication pipeline (exact hashes, perceptual frame hashes, audio fingerprints, embedding search with FAISS) and covers thresholds, clustering, which copy to keep, and cost at scale.

    TL;DR

    • Layer cheap before expensive: video ID and sha256 → perceptual hashes on sampled frames → audio fingerprints → embedding nearest-neighbor search → video-level verification.
    • Match at frame or segment level, decide at video or clip level. Compilations and reaction videos only share part of their content with the source.
    • Calibrate thresholds on labeled pairs before you delete anything.
    • Cluster with care: similarity edges can chain unrelated videos into one giant cluster.
    • Keep the best copy by explicit rules (license, original uploader, resolution) and record the cluster ID so takedowns propagate to every copy.
    • Search your evaluation sets too, with a looser threshold.

    Why duplicates hurt

    Duplicates do three kinds of damage:

    • Wasted compute and skewed weighting. A viral clip with 40 re-uploads is effectively upweighted 40x.
    • Memorization. In Extracting Training Data from Diffusion Models, Carlini et al. extracted near-copies of training images from Stable Diffusion and Imagen. They focused their search on duplicated training examples because, citing prior work, those are orders of magnitude more likely to be memorized. For text, Lee et al. report that deduplicated training data made models emit memorized text about ten times less often and reach the same or better accuracy in fewer steps.
    • Evaluation contamination. Lee et al. also found train-test overlap affecting over 4% of the validation sets of standard text datasets. Many video benchmarks come from YouTube too, so a re-upload of a benchmark clip silently inflates your scores.

    Removal also tends to be cheap in accuracy terms: SemDeDup reports removing 50% of a LAION subset via embedding-based semantic dedup with minimal performance loss. That is image-text data; measure on your own video set.

    The duplicate taxonomy

    Different copies need different detectors. No single method catches all of them.

    Duplicate type What changes Catches it Misses it
    Same video listed twice Nothing Video ID —
    Byte-identical file Nothing sha256 —
    Re-upload / re-encode Codec, bitrate, resolution, small trims pHash/dHash on sampled frames, audio fingerprint sha256, video ID
    Mirrored copy Horizontal flip pHash of the flipped query, embeddings Plain pHash
    Cropped / letterboxed / watermarked Borders, overlays, aspect ratio Embeddings, crop-resistant hashing, copy-detection descriptors Plain pHash on large crops
    Compilation Segments of many sources concatenated Frame-level matching with per-segment coverage Whole-video embeddings
    Reaction video Source shrunk into a picture-in-picture, new audio on top Copy-detection descriptors, sometimes audio fingerprint pHash, whole-frame embeddings

    Layer 1: exact deduplication

    Start with the free wins. Dedup source lists on the platform video ID before you download anything. Overlapping playlists, search queries and public datasets like Panda-70M and HD-VILA often reference the same YouTube IDs (see downloading Panda-70M, HD-VILA and InternVid). Every ID you drop here saves bandwidth, storage and all downstream compute.

    After download, sha256 each file and keep the digest in your manifest. It catches byte-identical copies and doubles as an integrity check, but misses the same video in two formats, let alone a re-encode.

    Layer 2: perceptual hashes on sampled frames

    A perceptual hash maps visually similar images to similar bit strings, so the Hamming distance between hashes approximates visual difference. The Python imagehash library implements average, perceptual (phash, DCT-based), difference (dhash), wavelet and crop-resistant hashing. With the default hash_size=8, phash and dhash produce 64-bit hashes, and subtracting two hashes returns the Hamming distance.

    Sample frames at a fixed rate rather than extracting codec keyframes. Different encodes of the same video place I-frames at different positions. Fixed-rate sampling keeps the frame timelines of two copies roughly aligned.

    mkdir -p frames/VIDEO_ID
    ffmpeg -hide_banner -loglevel error -i VIDEO_ID.mp4 \
      -vf "fps=1,scale=256:-2" -q:v 3 frames/VIDEO_ID/%06d.jpg

    Then hash every frame, index the hashes in a FAISS binary index (Hamming distance, IndexBinaryFlat), and query with both the original and the mirrored frame:

    from collections import Counter, defaultdict
    from pathlib import Path
    
    import faiss
    import imagehash
    import numpy as np
    from PIL import Image, ImageOps
    
    MAX_HAMMING = 8      # starting point for 64-bit pHash; calibrate on labeled pairs
    MIN_STD = 10.0       # skip near-uniform frames (black, white, solid title cards)
    
    def bits(h):
        return np.packbits(h.hash.flatten())          # 64 bits -> 8 uint8
    
    codes, mirrored, owners = [], [], []
    for p in sorted(Path("frames").glob("*/*.jpg")):
        img = Image.open(p).convert("L")
        if np.asarray(img).std() < MIN_STD:
            continue
        codes.append(bits(imagehash.phash(img)))
        mirrored.append(bits(imagehash.phash(ImageOps.mirror(img))))
        owners.append(p.parent.name)                  # folder name = video ID
    
    codes = np.stack(codes)
    index = faiss.IndexBinaryFlat(64)
    index.add(codes)
    
    frames_per_video = Counter(owners)
    hits = defaultdict(set)                           # (a, b) -> frames of a matched in b
    for queries in (codes, np.stack(mirrored)):
        D, I = index.search(queries, 10)
        for qi in range(len(queries)):
            a = owners[qi]
            for dist, j in zip(D[qi], I[qi]):
                if j >= 0 and dist <= MAX_HAMMING and owners[j] != a:
                    hits[(a, owners[j])].add(qi)
    
    coverage = {pair: len(s) / frames_per_video[pair[0]] for pair, s in hits.items()}
    for (a, b), c in sorted(coverage.items(), key=lambda kv: -kv[1])[:20]:
        print(f"{a} -> {b}: {c:.0%} of {a}'s frames matched")

    Three details matter more than the hash choice:

    • Filter low-information frames. Black frames, fades and solid title cards hash almost identically across unrelated videos and generate false matches.
    • Coverage is asymmetric. If 90% of A's frames match B but only 5% of B's match A, A is likely a clip lifted from B, or B is a compilation containing A. Keep both directions.
    • pHash breaks under heavy crops and picture-in-picture. crop_resistant_hash helps with crops but is much slower. For reaction videos, use embeddings or a copy-detection model.

    Exhaustive binary search is popcount over 8 bytes per frame, so it is fast. At hundreds of millions of frames, switch to IndexBinaryIVF or IndexBinaryHash, documented on the same wiki page.

    Layer 3: audio fingerprints

    Re-uploads often keep the original audio even when the picture is cropped, flipped or overlaid. Chromaprint, the fingerprinting library behind AcoustID, ships a command-line tool, fpcalc. It decodes audio through FFmpeg, so it reads the audio track of a video file directly. According to its source, -length defaults to 120 seconds, and a value of 0 removes the limit. -raw outputs the uncompressed fingerprint as 32-bit integers, and -json makes it machine-readable. The current release on the project page is 1.6.2.

    fpcalc -raw -json -length 0 VIDEO_ID.mp4

    To compare two fingerprints, slide one against the other and measure the fraction of differing bits at the best offset:

    import json
    import subprocess
    
    import numpy as np
    
    def raw_fp(path):
        out = subprocess.run(["fpcalc", "-raw", "-json", "-length", "0", path],
                             capture_output=True, text=True, check=True).stdout
        return np.array(json.loads(out)["fingerprint"], dtype=np.uint32)
    
    def bit_error_rate(a, b, max_offset=300, min_overlap=100):
        best = 1.0
        for off in range(-max_offset, max_offset + 1):
            x, y = a[max(off, 0):], b[max(-off, 0):]
            n = min(len(x), len(y))
            if n < min_overlap:
                continue
            diff = np.unpackbits((x[:n] ^ y[:n]).view(np.uint8)).sum()
            best = min(best, diff / (32 * n))
        return best   # 0.0 = identical; independent random bits would sit near 0.5

    Offsets are in fingerprint items, not seconds. This brute-force alignment verifies candidate pairs; it is not a search method. To find candidates at scale, put the 32-bit items in an inverted index and only align pairs that share many items. Chromaprint was built to identify music, so treat matches on speech-only or ambient audio with more suspicion, and skip near-silent tracks: silence matches silence.

    Layer 4: embedding-based near-duplicate search

    Embeddings catch what hashes miss: crops, letterboxing, color grading and overlays. The standard recipe is to embed sampled frames with a CLIP-family encoder, normalize, and search neighbors by cosine similarity. Carlini et al. found near-duplicates among 160 million training images the same way, comparing CLIP embeddings instead of pixels.

    OpenCLIP loads both CLIP and SigLIP checkpoints (for example ViT-SO400M-14-SigLIP-384). FAISS turns inner product into cosine similarity once vectors are L2-normalized, as described in its metric notes:

    import faiss
    import numpy as np
    import open_clip
    import torch
    from PIL import Image
    
    device = "cuda" if torch.cuda.is_available() else "cpu"
    model, _, preprocess = open_clip.create_model_and_transforms(
        "ViT-B-32", pretrained="laion2b_s34b_b79k")
    model = model.to(device).eval()
    
    @torch.no_grad()
    def embed(paths, batch=256):
        out = []
        for i in range(0, len(paths), batch):
            x = torch.stack([preprocess(Image.open(p).convert("RGB"))
                             for p in paths[i:i + batch]]).to(device)
            out.append(model.encode_image(x).float().cpu().numpy())
        return np.ascontiguousarray(np.concatenate(out), dtype="float32")
    
    X = embed(frame_paths)              # frame_paths: list of sampled frame files
    faiss.normalize_L2(X)
    
    index = faiss.index_factory(X.shape[1], "IVF4096,Flat", faiss.METRIC_INNER_PRODUCT)
    index.train(X)                      # use "Flat" instead for small sets
    index.add(X)
    index.nprobe = 16
    S, I = index.search(X, 20)          # S = cosine similarity, I = neighbor ids

    Practical notes:

    • Search twice. Run a coarse pass on one pooled (mean) embedding per clip to find candidates, then verify at frame level, as in the pHash coverage logic above.
    • Semantic similarity is not duplication. Two news segments from the same studio, or two playthroughs of the same game level, embed very close together. Require temporal consistency (many frames matching at a stable time offset) before calling something a copy.
    • For reaction videos and heavy edits, use a copy-detection descriptor. Meta's SSCD is trained for image copy detection rather than semantics. The 2023 Video Similarity Challenge paper provides a benchmark and baselines for detecting and temporally localizing copied segments between videos.

    Thresholds: calibrate, then audit

    Every threshold here (Hamming distance, bit error rate, cosine similarity, frame coverage) trades precision against recall. The values in the code above are starting points. To set them:

    1. Sample candidate pairs in bands around each threshold, for example cosine 0.85–0.90, 0.90–0.95 and 0.95+.
    2. Have a person label each pair: same footage, same footage with heavy edits, or different.
    3. Pick the threshold where precision is acceptable for deletion. Report it with a confidence interval, not a point estimate. Our post on dataset audits with Wilson intervals covers the sample sizes.

    Use two thresholds: a strict one for deleting within your training set, and a looser one for flagging overlap with evaluation sets, where a miss costs more than a false alarm.

    From pairs to clusters

    Turn verified pairs (for example, coverage of 0.8 or more) into duplicate groups with union-find, also called disjoint-set, over the edges. Then watch for chaining. If A matches B and B matches C, all three land in one cluster even when A and C share nothing. Compilations act as bridges that can link dozens of unrelated sources. If one cluster has thousands of members, inspect it. Common fixes are to keep compilations from creating edges (handle them at segment level instead), to require mutual coverage, or to cluster first and dedup within clusters, which is the approach SemDeDup takes with k-means.

    Choosing which copy to keep

    Within each cluster, rank members with explicit, deterministic rules and keep the top one:

    1. License and provenance: prefer copies with a clear license (see Creative Commons videos for AI training) and the original uploader's channel over re-uploaders.
    2. Earliest upload date as a proxy for the original.
    3. Highest resolution and bitrate, no letterboxing.
    4. Fewest overlays: lower OCR text area, no burned-in watermark.
    5. Tie-break on video ID so reruns produce the same answer.

    For compilations, drop the duplicated segments and keep any unique ones, which requires the temporal localization from the frame-level step. Store dup_cluster_id, dup_role (kept or dropped) and the matched segments as columns, alongside the other curation scores described in video data curation filters. Never delete the evidence. Thresholds will change.

    What it costs at scale

    The arithmetic is dominated by how many vectors you store. Take an example corpus of 1,000,000 videos averaging 8 minutes, sampled at 1 frame per second:

    • Frames: 1,000,000 × 480 s × 1 fps = 480 million.
    • 64-bit pHash: 480M × 8 bytes = 3.84 GB. Fits in RAM on one machine.
    • 512-d float32 embeddings (ViT-B-32): 480M × 512 × 4 bytes = ~983 GB, which is the 4*d bytes per vector listed for flat indexes in the FAISS index overview.
    • One embedding per 5 seconds instead: 96M vectors × 2,048 bytes = ~197 GB flat. With IndexIVFPQ at 64 bytes of code plus 8 bytes of ID, that becomes 96M × 72 bytes = ~6.9 GB, at some loss of accuracy. Rerank the candidates with exact vectors.
    • All-pairs comparison of 96M vectors: 96M² / 2 ≈ 4.6 quadrillion pairs, which is why approximate nearest-neighbor search is required.

    Encoder throughput depends on model, resolution, batch size and decoding, so benchmark it on your hardware. Video decoding is often the bottleneck, so reuse the frames you already extract for shot detection and quality filters. And dedup IDs before download: every duplicate you skip is bandwidth you don't pay for (see bandwidth for large-scale video downloads).

    Compliance

    YouTube's Terms of Service restrict automated access and downloading. Copyright and licensing apply to every copy, and a re-upload's license may not reflect the original creator's. Faces and voices can be personal data under GDPR. Use your duplicate clusters to honor takedown and opt-out requests across every copy and derived clip, not just the one ID named in the request. Get legal review for your jurisdiction and use case.

    If you'd rather not run this yourself

    Corpora's fully managed option collects YouTube video, audio, subtitles and metadata and delivers them deduplicated, with sha256 checksums and manifests, to S3, GCS, Azure Blob or private object storage, with a free sample batch to run your own acceptance tests. For the questions to ask any data vendor about dedup and contamination, see the video training data buying checklist, or contact us.

    FAQ

    What is the difference between exact and near-duplicate video deduplication?

    Exact deduplication matches identical identifiers or bytes (video ID, sha256). Near-duplicate detection matches content that looks or sounds the same after re-encoding, cropping, flipping or editing. It uses perceptual hashes, audio fingerprints or embeddings.

    Is pHash or dHash better for video frames?

    Both tolerate re-encoding and resizing, and both break under heavy crops and picture-in-picture. In imagehash, phash thresholds low-frequency DCT coefficients of a downscaled grayscale frame, while dhash compares adjacent pixels, which is simpler and cheaper. Benchmark both on labeled pairs from your own data.

    What cosine similarity threshold should I use for CLIP-based deduplication?

    There is no universal value. It depends on the encoder, the frame sampling and whether you compare frames or pooled clips. Label pairs in similarity bands, pick the band where precision is acceptable, and require temporal consistency across several frames before treating a pair as a copy.

    How do I check my training set for benchmark contamination?

    Index your training frames, then query with frames from every evaluation video using a looser threshold than you use for training dedup. Also check exact IDs, since many benchmarks are built from YouTube. Record matches as a column so you can exclude them and report the overlap.