LLM & VLM courseBlog
209Track 8: Video and multimodal systems · session 9 of 21

Video fingerprinting and near-duplicate detection

Video fingerprinting finds the same footage after crops, re-encoding, logos, speed changes and cuts, even when only a few seconds are copied. This session builds the full pipeline: perceptual hashes and learned frame descriptors, the frame similarity matrix and how to find a copied segment in it (Hough voting, dynamic programming, ViSiL), and how VSC22 measures detection, localization and robustness.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: BeginnerBefore this: Session 169 (vision applications: SSCD and micro-AP) and session 201 (video as data); basic PyTorch

What you will learn

  • What counts as a copy (same source footage) and how it differs from semantic similarity, with the VSC22 benchmark as the reference setting
  • How perceptual hashes (aHash, pHash, PDQ, TMK+PDQF) work, what edits they survive, and why random collisions matter at video scale
  • Learned frame descriptors (SSCD at 1 frame per second), the problem of low-information frames, and score normalization
  • Why global video vectors dilute partial copies, what chamfer similarity keeps and loses, and why a copy is a line in the similarity matrix
  • How to localize copies with temporal Hough voting over slopes and with dynamic-programming alignment, and how ViSiL learns to read the matrix
  • How to evaluate: micro-AP versus mAP, the VSC22 localization precision and recall, and per-edit robustness tests

Why this matters

A video is removed from a platform because it shows violence. Ten minutes later it comes back: cropped, mirrored, with a logo in the corner, re-encoded at a lower quality, played 1.25 times faster, and cut into the middle of a longer video. A person sees at once that it is the same footage. A computer must see it too, among hundreds of millions of uploads per day. This is video copy detection, also called video fingerprinting or near-duplicate video detection.

The task is narrow on purpose. We do not ask “are these two videos about the same thing?” (that is retrieval by meaning, the topic of session 208). We ask “do these two videos share the same original footage, after edits?” Two different videos of the same bicycle race are not copies. A cropped, darkened screen recording of one of them is.

The same machinery runs in many places:

  • Content moderation. Match uploads against a bank of footage that was already removed, so a viral harmful video is stopped quickly and fewer human moderators must watch it again. The 2023 Video Similarity Challenge paper names this, misattribution and copyright protection as its use cases [Certain].
  • Copyright. Find copies of films, sports broadcasts or news footage on video-sharing sites.
  • Deduplication. Remove repeated videos from search results and recommendations, and from training sets. Deduplicated training data reduces memorization and overfitting [Certain, as cited by the VSC22 paper]; for text, see session 34.
  • Provenance. Find the original source of a clip that is shared with a misleading caption.

The previous image session, session 169, built image copy detection with the SSCD descriptor and the micro-AP metric. Video adds two new problems. First, time: the copy may be a 6-second piece of a 60-second video, sped up, with other footage around it. We must find where it is, not only whether it is there. Second, scale: one hour of video is 3,600 frames even at 1 frame per second, so every frame-level error is multiplied by thousands.

What counts as a copy

The copy detection literature uses a strict definition: two images are copies if they come from the same 2-D image source [Certain, SSCD]. For video, the VSC22 paper says copy detection decides whether two videos “are derived from the same original source” [Certain]. Around this definition there are weaker relations. FIVR-200K, a retrieval benchmark, separates duplicate scenes, complementary scenes (the same moment filmed by another camera) and incident scenes (the same event, not the same moment) [Certain]. A copy detector must say “yes” to the first and “no” to the others.

Pair of videosCopy?What it tests
Same file, re-encoded at a lower bitrate and resizedYesThe easy case; even a perceptual hash works
Cropped, mirrored, color-filtered, with text or emoji on topYesSpatial invariance of the frame descriptor
Played at 1.5× speed, or with every other second removedYesTemporal alignment that allows a slope
A 6-second piece inside a 3-minute compilationYes (partial copy)Localization; global video vectors fail here
Shown inside a screenshot of a phone, or in a grid with three other videosYesThe copy covers only part of each frame
Another camera at the same concert, same minuteNoHard negative: same scene and time, different source
Another video of a cat playing pianoNoSame meaning; a semantic embedding says “similar”

The VSC22 benchmark (DVSC23 dataset, from Meta AI and partners) is built exactly around this list. It uses Creative Commons videos from YFCC100M, removes natural copies with several copy detectors plus human labels, and then creates copies with the AugLy library [Certain]. Edits include brightness, color jitter, grayscale, emoji and text overlays, frame effects, horizontal and vertical stacking, blur, noise, pixelization, encoding quality, blending two videos, crop, padding, rotation, flip, aspect ratio, rescale, speed change and “time decimation” (keep evenly spaced pieces) [Certain]. Some edits appear only in the validation and test splits, so that a model cannot simply memorize the training edits [Certain].

Most queries are distractors with no copy at all, as in a real upload stream. The train split has 8,404 queries, of which 6,475 are distractors (77%), and 40,311 reference videos; the test split has 8,015 queries (6,175 distractors) searched against the 40,318 validation references [Certain]. Each split also contains 500 hard negative pairs that human raters judged to be similar scenes from different videos [Certain].

The pipeline at a glance

Every serious system has the same stages. Figure 1 shows them. The first stages are cheap and run on every frame of every video. The later stages are expensive and run only on a few candidate pairs.

decode1 frame/s,resize framedescriptorshash or SSCD index searchk-NN per frame(FAISS) candidatevideo pairsscore = max alignmentmatrix S = QR⊤→ segments decidethreshold,review every frame of every video (cheap, offline for references)only candidate pairs (expensive) VSC22 detection track (VCD)fixed rules: ≤ 512 dims, ≤ 1 descriptor per second,inner product, pair score = max frame similarity VSC22 localization track (VCL)any method within a time limit; output(query span, reference span, score)
Figure 1. The stages of a video copy detection system. The descriptor and the index decide which pairs are even looked at; the alignment stage decides where the copy is and how sure we are. The two VSC22 tracks cover the two halves [Certain: the paper says its detection track models the first, search step of a large-scale system, and the localization track the end-to-end task].

Perceptual hashes: a compact fingerprint per frame

The oldest tool is the perceptual hash. A cryptographic hash such as SHA-256 changes completely when one pixel changes, so it finds only exact file copies. A perceptual hash is designed to change a little when the image changes a little. It turns a frame into a short string of bits, for example 64 or 256, and two frames are compared by counting the bits that differ, the Hamming distance:

\[ d_H(\mathbf{h}, \mathbf{h}') = \sum_{b=1}^{B} \mathbb{1}\big[h_b \ne h'_b\big], \qquad \text{match} \iff d_H(\mathbf{h}, \mathbf{h}') \le \tau \tag{209.1} \]
Read the symbols
\(\mathbf{h}, \mathbf{h}' \in \{0,1\}^B\)
the hashes of two frames, \(B\) bits each
\(\mathbb{1}[\cdot]\)
1 if the condition is true, else 0
\(\tau\)
the match threshold, in bits

Counting different bits is one XOR and one “popcount” instruction per 64 bits, so hashes are extremely cheap to store and compare.

Three classic hashes, each made from a small gray version of the frame:

  • aHash (average hash): shrink to 8×8, set a bit to 1 where the pixel is brighter than the mean. 64 bits.
  • dHash (difference hash): set a bit to 1 where a pixel is brighter than its right neighbor.
  • pHash (perceptual hash, Zauner 2010): take the discrete cosine transform (DCT), which describes the image as a sum of cosine waves of rising frequency, keep only the lowest frequencies, and compare each coefficient with their median. The common open-source version resizes to 32×32 and keeps the top-left 8×8 coefficients [Likely]:
\[ C = D\,X\,D^\top, \qquad h_{uv} = \mathbb{1}\big[\,C_{uv} \gt \operatorname{median}\{C_{u'v'} : u', v' \lt 8\}\,\big], \quad u, v \lt 8 \tag{209.2} \]
Read the symbols
\(X\)
the 32×32 gray frame
\(D\)
the DCT matrix, \(D_{kn} = \cos\!\big(\pi k (2n+1) / 64\big)\); row \(k\) is a cosine of frequency \(k\)
\(C_{uv}\)
how strongly the frame contains the 2-D pattern of vertical frequency \(u\) and horizontal frequency \(v\)

Low frequencies describe the coarse layout of light and dark, which survives resizing, compression, small noise and mild color changes. Because each bit compares two numbers, a global change of brightness or contrast cancels out.

Meta’s open-source PDQ hash is a stronger relative of pHash: it computes a 64×64 luminance downsample, a 16×16 block of DCT coefficients, and a median threshold, giving 256 bits [Certain]. It also outputs a 0–100 quality score that is near 0 for featureless frames such as solid colors, and it can compute the hashes of the 8 rotations and flips of a frame cheaply [Certain]. The PDQ documentation suggests starting with a match threshold of 31 bits or less [Certain]. For video, TMK+PDQF resamples a video to 15 frames per second and 64×64 pixels, computes PDQ without the final binary step (PDQF, 256 floats per frame), and summarizes the whole video in a fixed-size hash: a 1 KB time average (“level 1”) and 256 KB of Fourier-weighted averages (“level 2”) [Certain]. Its authors are honest about the limit: it targets whole videos that are nearly identical and “would not detect those two minutes of footage embedded within, say, an hour-long video” [Certain].

Figure 2. A perceptual hash lab. The frame is a synthetic 32×32 gray image (smooth blobs, fixed seed). aHash: 8×8 block means compared with their mean. pHash: formula (209.2). Bits are drawn dark for 1; a red outline marks a bit that the edit flipped. The readout also gives the smallest distance from the original to 20 unrelated synthetic frames, which is what a false match would need to beat.
How to read Figure 2

Start with the default, a 10% center crop. aHash moves by 5 bits, pHash by 12. That looks like aHash is more robust, but look at the unrelated frames: one of them is only 11 bits from the original under aHash, while the closest unrelated frame under pHash is 24 bits away. What matters is the gap between the copy and the nearest non-copy: 6 bits for aHash, 12 bits for pHash. With \(\tau = 10\), aHash matches and pHash misses; raise \(\tau\) to 14 and pHash matches while aHash also accepts the unrelated frame. Now try the edits one by one: brightness and blur change almost nothing (each bit compares two numbers), noise moves a few bits, a logo of 6 px moves pHash by 12 bits, a 30% crop moves it by 28 bits, and a mirror flips 32 of the 64 pHash bits: no threshold can survive that, which is why PDQ also hashes the flipped versions.

How often do random hashes collide?

If the bits of two unrelated hashes were independent fair coins, the distance would follow a binomial distribution with mean \(B/2\), and the chance of a false match would be

\[ p_{\text{FP}} = P\big(d_H \le \tau\big) = \frac{1}{2^B} \sum_{k=0}^{\tau} \binom{B}{k} \tag{209.3} \]

This is a best case, because real frames are not random: similar scenes, black frames and title cards have similar hashes. The PDQ documentation reports that distances between random pairs average 128 bits but range from about 90 to 160 [Certain], a wider spread than independent bits would give. Still, (209.3) shows why the length of the hash matters at video scale:

\[ \E[\text{false frame matches per query}] = T_q \cdot N \cdot T_r \cdot p_{\text{FP}} \tag{209.4} \]
Read the symbols
\(T_q, T_r\)
frames per query video and per reference video
\(N\)
the number of reference videos
\(p_{\text{FP}}\)
the chance that one unrelated frame pair passes the threshold
Worked example: one minute of video against a million videos

A 60-second query at 1 frame per second is compared with \(N = 10^6\) reference videos of 60 seconds. That is \(60 \cdot 10^6 \cdot 60 = 3.6 \times 10^9\) frame pairs per query. To expect fewer than one false frame match, we need \(p_{\text{FP}} \lt 2.8 \times 10^{-10}\).

A 64-bit hash with \(\tau = 10\): \(p_{\text{FP}} = 1.0 \times 10^{-8}\) under the random-bit model, so about 36 false frame matches per query, even in this best case. A 256-bit hash with \(\tau = 31\): \(p_{\text{FP}} = 8.3 \times 10^{-38}\), essentially zero. Real systems are much worse than these numbers, because real hashes are correlated; that is why one frame match is never a decision, and why the next sections look at sequences of matches.

Learned frame descriptors

Hashes fail on the hard edits of Figure 2: crops, overlays, flips, screenshots, grids. Modern systems use a neural network that maps each frame to a vector, trained so that edited copies land close together. The standard choice is SSCD, the self-supervised copy descriptor from session 169: a ResNet-50 with GeM pooling, trained with InfoNCE on strong copy-like augmentations plus a KoLeo entropy term that spreads descriptors evenly [Certain]. For a video, we decode some frames per second and embed each one:

\[ \mathbf{q}_i = \frac{f(x^{q}_i)}{\lVert f(x^{q}_i) \rVert}, \quad \mathbf{r}_j = \frac{f(x^{r}_j)}{\lVert f(x^{r}_j) \rVert}, \qquad S_{ij} = \mathbf{q}_i^\top \mathbf{r}_j \tag{209.5} \]
Read the symbols
\(x^q_i, x^r_j\)
frame \(i\) of the query video and frame \(j\) of a reference video
\(f\)
the frame descriptor network (SSCD, or a ViT trained the same way)
\(S \in \R^{T_q \times T_r}\)
the frame similarity matrix: one cosine similarity per (query frame, reference frame) pair; in matrix form \(S = Q R^\top\)

The VSC22 baseline is exactly this: SSCD (ResNet-50, 512 dimensions, trained on DISC21) at one frame per second, short edge resized to 320 pixels, center crop [Certain]. The winning teams also used frame-level descriptors trained like SSCD (WeChat CV used a ViT); the paper notes that all top teams used a frame-level extractor first and none needed a video-level descriptor [Certain].

Why not a semantic model such as CLIP? Because it is trained to put two different cat videos close together. That is right for search and wrong here; it produces confident false copies. A copy descriptor should be invariant to edits and sensitive to the source.

Two lessons from the VSC22 baseline

Low-information frames. Black frames, solid colors and fades have almost no content. After L2 normalization their descriptors still have length 1 and match each other with high similarity. On the VSC22 test set, the plain SSCD baseline reached a detection µAP of 0.010: it failed completely because of these spurious matches [Certain]. Keeping the descriptor unnormalized (so empty frames get a small norm and a small inner product) raised it to 0.464 [Certain]. PDQ’s quality score solves the same problem for hashes.

Score normalization. Subtract from each similarity how similar the query frame is to a background set that has no copies (the training references):

\[ \tilde{S}_{ij} = S_{ij} - \beta \, \mathbf{q}_i^\top \mathbf{b}^{(k)}(\mathbf{q}_i), \qquad k = 1,\ \beta = 1.2 \tag{209.6} \]
Read the symbols
\(\mathbf{b}^{(k)}(\mathbf{q}_i)\)
the \(k\)-th nearest neighbor of query frame \(i\) in the background set
\(\beta\)
how much of that background similarity is removed

A black frame is close to many background frames, so its scores drop a lot; a distinctive frame keeps its scores. With L2 normalization plus score normalization the baseline reached 0.605 µAP, the best of the four variants [Certain]. The baseline stores the correction in the lowest-variance dimension of the 512-d descriptor, so a plain inner-product index still works [Certain].

How much space does it take?

At 1 descriptor per second, 512 float32 numbers are \(512 \cdot 4 = 2{,}048\) bytes per second, or 7.37 MB per hour of video; one million hours is 7.37 TB. Compressed with product quantization to 64 bytes per vector (session 151), it is 230 KB per hour. A 256-bit PDQ hash per second is 32 bytes, or 115 KB per hour. TMK+PDQF is 256 KB per video whatever its length [Certain], which is cheap for long videos but cannot localize.

Algorithm 1: index references and find candidate pairs (VSC22 detection track style)
  1. input: reference videos, frame descriptor \(f\), background set, \(\beta\), number of neighbors \(k\)
  2. offline, for each reference video do
  3.   decode at 1 frame/s; drop or down-weight low-quality frames // black frames, fades
  4.   \(\mathbf{r}_j \leftarrow f(x_j)\); add \((\mathbf{r}_j, \text{video id}, t_j)\) to an inner-product index (FAISS)
  5. online, for each query video do
  6.   embed its frames the same way; apply score normalization with the background set // formula (209.6)
  7.   for every query frame, search the top-\(k\) reference frames
  8.   group hits by reference video; pair score \(\leftarrow\) the maximum frame similarity // as in the VSC22 detection track
  9. return (query, reference, score) triples above a loose threshold \(\rightarrow\) candidates for alignment

From frame matches to video matches

We now have, for a candidate pair, the matrix \(S\). How do we turn \(T_q \times T_r\) numbers into one decision and a time span? Three simple ideas, from weakest to strongest.

1. Global descriptor. Average all frame vectors into one video vector and compare: \(s_{\text{glob}} = \cos(\bar{\mathbf{q}}, \bar{\mathbf{r}})\). It is cheap and fits any vector index, but it mixes copied and non-copied content. Suppose the query has a fraction \(\rho\) of copied content, the rest averages to a vector \(\mathbf{u}\) of the same length as the copied part \(\mathbf{c}\), orthogonal to it, and the reference is all copied content. Then

\[ s_{\text{glob}} = \frac{\rho}{\sqrt{\rho^2 + (1 - \rho)^2}} \tag{209.7} \]

A 10-second copy inside a 60-second query (\(\rho = 1/6\)) gives \(s_{\text{glob}} = 0.196\); the same copy filling half the query gives 0.707. The copy is diluted by everything around it. The VSC22 paper says this directly: video-level methods are less effective for partial copies because aggregation “is polluted by clutter and irrelevant content” [Certain]. There is a second, quieter problem: averages of many frames all drift toward the average frame of the whole dataset, so unrelated videos also get high global similarity (you will see 0.70 in Figure 3).

2. Chamfer similarity. For each query frame take its best reference frame, then average. This is the similarity version of the chamfer distance, and ViSiL uses it at two levels [Certain]:

\[ \operatorname{CS}(q, r) = \frac{1}{T_q} \sum_{i=1}^{T_q} \max_{j} S_{ij}, \qquad \operatorname{SCS}(q, r) = \tfrac12\big(\operatorname{CS}(q, r) + \operatorname{CS}(r, q)\big) \tag{209.8} \]

It no longer averages vectors before comparing them, so a good frame match is not blurred. But it ignores order: a query whose frames each resemble some reference frame, in random order, scores as high as a true copy. And it is still an average over all query frames, so a short copy is still diluted.

3. Temporal alignment. A true copy has a shape in \(S\): a line of high values. If the copy is at the same speed, the line is a diagonal \(j = i + b\). At speed \(a\) (the query plays \(a\) seconds of reference per second) the line has slope \(a\): \(j = a\,i + b\). Random matches, black frames and similar scenes make isolated bright cells or bright blocks, not long lines. Finding the line gives both the decision (is there a long enough line?) and the localization (where does it start and end, in both videos?).

frame similarity \(S_{ij}\)true copied frame pairsalignment path and box (formula 209.9)
Figure 3. A synthetic 40-second query against a 60-second reference, one descriptor per second, 32 dimensions. Each video is made of shots (4–10 s); frames in a shot share a base vector plus noise, and all videos share a small common component (as real descriptors do). Query seconds 12 onward show the reference, starting at the chosen reference time and speed, with edit noise \(\sigma\); the rest of the query is other footage. The readout compares four video-level scores for the copied reference and for an unrelated reference.
How to read Figure 3

At the default (16 s copy, speed 1, \(\sigma = 0.5\)) the copy is a clear diagonal from (query 12, reference 20) to (27, 35), and the alignment box matches it exactly. Compare the scores: global 0.801 against 0.697 for the unrelated reference, a small gap; the max frame similarity separates them (0.963 vs 0.633) but would also fire on a single lucky frame; the alignment score is 5.36 against 0.03. Shrink the copy to 4 s: the global score falls to 0.688, close to the unrelated 0.630, while alignment still finds the exact 4-second box (score 1.40). Switch to 2× speed: the line gets steeper and the path follows it with the (1, 2) move. Raise \(\sigma\) to 2: the line fades and alignment finds only part of it. Switch to “unrelated reference” to see what a negative pair looks like: bright blocks where shots happen to look alike, but no long line.

Dynamic programming: the best path through the matrix

A simple and strong way to find the line is a local alignment by dynamic programming, the same idea as the Smith–Waterman algorithm for DNA. Each cell collects the best path that ends there. A step may go diagonally (same speed), or skip one frame on either side (speed 2 or 0.5); a pure vertical or horizontal step (a pause or a dropped frame) costs a penalty. Each visited cell adds its similarity minus a threshold, so weak cells cost points and a path survives only while it keeps meeting strong cells:

\[ A_{ij} = \max\Big(0,\ \max_{(\delta_i, \delta_j, \pi) \in \mathcal{M}} \big(A_{i - \delta_i,\, j - \delta_j} - \pi\big)\Big) + S_{ij} - \theta, \qquad A_{ij} \leftarrow \max(A_{ij}, 0) \tag{209.9} \]
Read the symbols
\(A_{ij}\)
the score of the best path that ends at cell \((i, j)\); 0 means “no path ends here”
\(\mathcal{M}\)
allowed moves \((\delta_i, \delta_j)\) with their penalty \(\pi\): diagonal \((1,1)\), speed-up \((1,2)\) and slow-down \((2,1)\) are free; a pause \((1,0)\) or \((0,1)\) costs \(\gamma\)
\(\theta\)
the similarity a cell needs to add to the path (0.6 in Figure 3)
\(\gamma\)
the penalty for a pause or a skipped frame (0.3 in Figure 3)

The best path ends at the cell with the largest \(A_{ij}\); follow the back-pointers to its start. Its score is the video-level confidence, and its first and last cells give the copied span in both videos. The cost is \(O(T_q T_r |\mathcal{M}|)\) per candidate pair, which is why it runs only after the index has picked candidates. Published methods of this family include DP alignment (Chou et al., 2015), the Temporal Network of Tan et al. (2009), which builds a graph of frame matches and finds the longest path with network flow, and is the localization method of the VSC22 baseline [Certain].

Temporal Hough voting

A faster idea: let every good frame match vote for the line it lies on, and look for the line with the most votes. This is the Hough transform from line detection in images, applied to time [Certain: temporal Hough voting is a classic video copy localization method]:

\[ H(a, b) = \sum_{(i, j) \in \mathcal{K}} S_{ij} \; \mathbb{1}\big[\operatorname{round}(j - a\,i) = b\big], \qquad (a^*, b^*) = \argmax_{a, b} H(a, b) \tag{209.10} \]
Read the symbols
\(\mathcal{K}\)
the kept matches: for each query frame its best reference frame, if \(S_{ij} \ge \theta\)
\(a\)
a candidate speed (slope), from a small set such as {0.5, 1, 1.5, 2}
\(b\)
the offset: where query time 0 lands in reference time

With only \(a = 1\) this is a histogram of offsets \(\Delta = j - i\): every copied frame votes for the same \(\Delta\). It costs one pass over the matches. The winning team of VSC22 used a related robust line fit, RANSAC, on its strongest correspondences to estimate “the linear temporal transformation” [Certain]. Figure 4 runs the voting step by step.

similaritytrue copybest match per query framewinning vote and box
Figure 4. Temporal Hough voting on a small synthetic pair (same descriptor model as Figure 3). The query has dark frames at its start and end, and the reference begins with two dark frames, like a fade-in. Use the toggle to switch between a same-speed copy and a 2× speed copy, then step through. Step 5 drops frames whose descriptor norm before L2 normalization is below 1, the same idea as PDQ’s quality score and the “no L2 norm” fix of the VSC22 baseline.
How to read Figure 4

At 1× speed, step 2 keeps 12 matches; 4 are dark frames that match the dark reference frame 0 with similarity about 0.95, as high as the true copies. Step 3: the 8 copy frames all vote for \(\Delta = 5\) (total weight 7.18), the dark frames spread over \(\Delta = -15, -14, -1, 0\), so the peak is right and step 4 gives the exact box (query 4–11, reference 9–16). Now switch to 2× speed and go back to step 3: the copy votes spread over \(\Delta = -1, \dots, 6\), and at step 4 the winner is \(\Delta = -1\), a wrong box made of dark frames and two copy frames. Dropping dark frames (step 5) does not fix it; there is still no peak. Only voting on the slope too (step 6) finds the line \(j = 2i - 5\) with weight 7.24, the true copy.

Algorithm 2: localize copies in one candidate pair
  1. input: frame descriptors \(Q\) (query) and \(R\) (reference), thresholds \(\theta\), \(\gamma\), quality threshold, slopes \(\mathcal{A}\)
  2. \(S \leftarrow Q R^\top\) // formula (209.5); optionally score-normalized (209.6)
  3. mask rows and columns of low-quality frames (small norm, low PDQ quality)
  4. fast path: for each query frame keep its best reference frame if \(S_{ij} \ge \theta\); vote \(H(a, b)\) for \(a \in \mathcal{A}\) // (209.10)
  5.   inliers \(\leftarrow\) kept matches with \(|j - a^* i - b^*| \le 1\); box \(\leftarrow\) their span in both videos
  6. or precise path: run the alignment recursion on \(S\); back-track from the best cell // (209.9)
  7. score each box (for example the max \(S_{ij}\) inside it, as the VSC22 baseline does); remove the inliers and repeat to find further copied segments
  8. return a list of (query span, reference span, score)

Learning the alignment: ViSiL

Hand-made rules (lines, penalties, thresholds) cannot cover every pattern: a copy with a pause, a slow-motion part, a looped GIF, a scene that repeats. ViSiL (Kordopatis-Zilos et al., ICCV 2019) learns to read the similarity matrix [Certain]. It has two levels, and both use chamfer similarity.

Frame level. Instead of one vector per frame, ViSiL keeps a 3×3 grid of region vectors per frame (R-MAC on the four residual blocks of a ResNet-50, 3,840 channels), PCA-whitened and weighted by a small attention vector [Certain]. Two frames are compared region by region:

\[ \operatorname{CS}_f(d, b) = \frac{1}{N^2} \sum_{u=1}^{N^2} \max_{w \in [1, N^2]} \mathbf{d}_u^\top \mathbf{b}_w \tag{209.11} \]
Read the symbols
\(\mathbf{d}_u, \mathbf{b}_w\)
region vectors of frames \(d\) and \(b\); there are \(N^2 = 9\) regions per frame
\(\max_w\)
each region of one frame looks for its best region in the other frame, so a shifted or cropped object can still match

Video level. The \(T_q \times T_r\) matrix of \(\operatorname{CS}_f\) values goes into a small four-layer CNN (3×3 convolutions with 32, 64 and 128 channels, two 2×2 max-pools, then a 1×1 convolution to one channel) [Certain]. The CNN treats the matrix as an image and learns what a copy looks like (diagonals, broken diagonals) and what noise looks like. Its output is clipped by a hard tanh to [−1, 1] and summarized again with chamfer similarity:

\[ \operatorname{CS}_v(q, p) = \frac{1}{X'} \sum_{i=1}^{X'} \max_{j \in [1, Y']} \operatorname{Htanh}\!\big(S^{v}_{ij}\big) \tag{209.12} \]

It is trained on VCDB (528 videos with 9,000 copied segment pairs) with triplets: an anchor video, a positive (an annotated copy, or a synthetic one made with color, geometric and temporal edits such as fast-forward and slow motion), and a hard negative [Certain]. The loss is a triplet margin loss plus a penalty on CNN outputs outside the clipping range:

\[ \mathcal{L} = \max\big\{0,\ \operatorname{CS}_v(v, v^-) - \operatorname{CS}_v(v, v^+) + \gamma\big\} + r \sum_{i,j} \Big( \big|\max\{0, S^v_{ij} - 1\}\big| + \big|\min\{0, S^v_{ij} + 1\}\big| \Big) \tag{209.13} \]
Read the symbols
\(v, v^+, v^-\)
anchor, positive (relevant) and negative video
\(\gamma\)
the margin; ViSiL uses \(\gamma = 0.5\) [Certain]
\(r\)
the weight of the range penalty; \(r = 0.1\) [Certain]

Results on FIVR-200K (225,960 videos, 100 queries), duplicate-scene retrieval mAP: ViSiL 0.892, against 0.775 for DP alignment and 0.724 for Temporal Networks run on the same features [Certain]. In the ablation, the learned CNN on the matrix gave the largest single gain on the duplicate-scene task (+0.024 mAP) [Certain]. Note the metric: this is per-query mAP for retrieval, not the detection µAP below; ViSiL’s authors list copy detection and localization as future work [Certain]. Later systems such as the VSC22 winner train a similar matrix-reading CNN as a filter: it decides whether a candidate pair is a copy before the expensive alignment [Certain].

Evaluation: detection, localization and robustness

Detection: micro-AP over all queries

A copy detector gives (query, reference, score) triples and, in production, one threshold decides for all queries. So VSC22, like the ISC21 image challenge, uses micro-AP: pool the predictions of all queries, sort them by score, and compute one precision–recall curve [Certain]:

\[ \mu\text{AP} = \sum_{i=1}^{M} P(i)\,\big(R(i) - R(i-1)\big), \qquad P(i) = \frac{\text{TP}(i)}{i}, \quad R(i) = \frac{\text{TP}(i)}{N_{\text{pos}}} \tag{209.14} \]
Read the symbols
\(M\)
the number of predicted pairs, over all queries, sorted by score
\(\text{TP}(i)\)
true copy pairs among the first \(i\) predictions
\(N_{\text{pos}}\)
all true copy pairs in the ground truth

Every prediction for a distractor query is a false positive, and a query whose wrong candidates have high scores pushes them above other queries’ true copies. Per-query mAP hides both effects: it skips queries with no copy and only looks at the order inside each query. On VSC22, submissions scored 9.4 points higher with mAP than with µAP on average; for the SSCD baseline the gap was 22.2 points [Certain]. A big gap means the scores are badly calibrated across queries.

Localization: precision and recall of time spans

For localization, a ground-truth copy is a box in a 2-D plane: the x-axis is reference time and the y-axis is query time. A prediction is also a box. VSC22 measures, after the first \(i\) predictions, the lengths of the projections of the boxes onto each axis (the union of all intervals), for ground truth (\(L_g\)), predictions (\(L_p\)) and their overlap (\(L_o\)) [Certain]:

\[ P(i) = \sqrt{\frac{L^{x}_{o}(i)\, L^{y}_{o}(i)}{L^{x}_{p}(i)\, L^{y}_{p}(i)}}, \qquad R(i) = \sqrt{\frac{L^{x}_{o}(i)\, L^{y}_{o}(i)}{L^{x}_{g}\, L^{y}_{g}}} \tag{209.15} \]

These go into (209.14) in place of the counting definitions. The square root is the VSC22 change to the VCSL metric, “to make the measure less strict” [Certain]. A box that is too large loses precision; a box that is too small loses recall; a second, wrong box adds to \(L_p\) and lowers precision for everyone after it.

ground truth boxpredicted box (overlap shaded)wrong box
Figure 5. The VSC22 localization metric (209.15) for one query–reference pair with one true copied segment: reference 40–60 s, query 10–30 s. Move the edges of the predicted box. The wrong box covers reference 5–15 s and query 45–55 s; when it is added, the readout also gives the µAP (209.14) of the ranked list of two boxes.
How to read Figure 5

The default box (reference 42–66, query 12–34) overlaps the truth by 18 s on each axis. It is 24 s and 22 s long, so precision is \(\sqrt{18 \cdot 18 / (24 \cdot 22)} = 0.783\) and recall is \(\sqrt{18 \cdot 18 / (20 \cdot 20)} = 0.900\). Without the square root (VCSL) they would be 0.614 and 0.810. Set the box to 40–60 and 10–30: both become 1. Now add the wrong box: precision drops to 0.546 because \(L_p\) grows to 34 and 32 s, while recall stays 0.900. With the good box ranked first, µAP is 0.705; rank the wrong box first and it drops to 0.491. Scores matter, not just boxes.

Worked example: the VSC22 leaderboard

Phase 2 (the final test set) results, µAP in % [Certain]: WeChat CV 87.2 (detection) and 91.5 (localization); Friendship First 85.1 and 77.1; LINE CVL 83.6 and 70.4; the SSCD + Temporal Network baseline 60.5 and 44.1. In Phase 1, 48 teams submitted to the detection track and 18 to localization; each test-time submission had to run within 10 seconds per query video on 6 vCPUs and one V100 GPU [Certain].

Read the numbers. Every team except the winner scored lower on localization than on detection: finding the exact span is harder than saying “copy somewhere”. The winner is the exception because it filtered candidate pairs with a CNN on the similarity matrix and estimated the temporal transform robustly [Certain]. The baseline loses 16 points between the tracks: its boxes are not precise.

Robustness tests: which edits break what

VSC22 also reports accuracy per edit type for the top three teams [Certain]. Easiest: temporal edits such as speed change and multiple copies, because all methods use frame descriptors and alignment. Hardest: edits that mix frames from several videos (the “rooms” grid, blending, horizontal and vertical stacking) and edits that add or remove image area (overlay onto a screenshot, crop). More edits per video made localization harder [Certain]. Two teams detected grids explicitly and embedded each cell separately [Certain]. Two teams also trained a classifier to detect edited queries; the paper warns that this exploits a dataset bias (all copied queries were edited) and would fail in real use [Certain].

In your own system, build the same table: for each edit type and strength, recall at the operating threshold, plus the false-positive rate on distractors. Keep some edit types out of training and test on them, as VSC22 does, so you measure generalization and not memorization of your augmentations.

EditPerceptual hash (pHash, PDQ)Learned frame descriptor (SSCD-style)Temporal stage
Re-encode, resize, mild color changeRobustRobust—
Logo, text, emojiSmall ones only (Figure 2)Robust if trained with overlays—
Crop, padding, aspect ratioBreaks quicklyMostly robust—
Mirror, rotationBreaks (PDQ: hash all 8 flips/rotations)Robust if in augmentations—
Speed change, time decimationFrames still matchFrames still matchNeeds slopes or DP moves
Short copy inside a long videoFrames match; whole-video hashes (TMK) failFrames match; global averages failNeeds localization
Grids, screenshots, blendingFailsHard; embed regions or detect the layout—
Black frames, fades, title cardsFalse matches; use the quality scoreFalse matches; norm or score normalizationRemoves isolated matches

Code: hashing, the similarity matrix, alignment and the metrics

The code runs on a CPU in about a second. It uses random tensors instead of a trained network, because the point is the logic: pHash with a DCT matrix, the frame similarity matrix, global and chamfer scores, Hough voting, DP alignment, µAP and the localization precision/recall.

import math, torch
import torch.nn.functional as F
torch.manual_seed(0)

# 1) perceptual hash (pHash-style): 32x32 gray -> 2D DCT -> 8x8 low frequencies -> median threshold
def dct_matrix(n=32):
    k = torch.arange(n)[:, None].float(); i = torch.arange(n)[None, :].float()
    return torch.cos(math.pi * k * (2 * i + 1) / (2 * n))           # (n, n), row k = frequency k

D32 = dct_matrix(32)
def phash(img):                                                    # img: (H, W) gray in [0, 1]
    x = F.interpolate(img[None, None], size=(32, 32), mode="bilinear", align_corners=False)[0, 0]
    c = (D32 @ x @ D32.T)[:8, :8].flatten()                        # 64 low-frequency coefficients
    return c > c.median()                                          # 64 bits (bool), formula (209.2)

def hamming(a, b):
    return int((a != b).sum())                                     # formula (209.1)

base = F.avg_pool2d(torch.rand(1, 1, 128, 128), 9, 1, 4)[0, 0]    # smooth random "frame"
base = (base - base.min()) / (base.max() - base.min())
h0 = phash(base)
edits = {"brighter": (base + 0.1).clamp(0, 1),
         "crop 10%": base[6:-6, 6:-6],
         "flip":     base.flip(-1),
         "other":    torch.rand(128, 128)}
print({k: hamming(h0, phash(v)) for k, v in edits.items()})

# 2) frame descriptors at 1 fps and the similarity matrix S = Q R^T, formula (209.5)
d = 32
def video(T, shot=6):                                              # shots: frames share a base vector
    base = torch.randn(T // shot + 1, d).repeat_interleave(shot, 0)[:T]
    return base + 0.5 * torch.randn(T, d)

ref = video(60)
query = video(40)
query[12:28] = ref[20:36] + 0.5 * torch.randn(16, d)               # 16-s copy: query 12..27 = ref 20..35
Q, R = F.normalize(query, dim=-1), F.normalize(ref, dim=-1)
S = Q @ R.T                                                        # (40, 60) cosine similarities

glob = F.normalize(Q.mean(0), dim=0) @ F.normalize(R.mean(0), dim=0)
chamfer = S.max(dim=1).values.mean()                               # formula (209.8)
print(S.shape, round(glob.item(), 3), round(S.max().item(), 3), round(chamfer.item(), 3))

# 3) temporal Hough voting on the offset j - i, formula (209.10) with slope 1
best_val, best_j = S.max(dim=1)
keep = best_val >= 0.6
offsets = best_j[keep] - torch.arange(40)[keep]
votes = torch.zeros(120).index_add_(0, offsets + 60, best_val[keep])
delta = int(votes.argmax()) - 60
inl = keep & ((best_j - torch.arange(40) - delta).abs() <= 1)
qi = torch.nonzero(inl).flatten()
print("offset", delta, "query", (qi.min().item(), qi.max().item()),
      "ref", (best_j[inl].min().item(), best_j[inl].max().item()))

# 4) DP local alignment with speed-tolerant moves, formula (209.9)
def dp_align(S, theta=0.6, gap=0.3):
    X, Y = S.shape
    D = torch.zeros(X, Y); back = {}
    moves = [(1, 1, 0.0), (1, 2, 0.0), (2, 1, 0.0), (1, 0, gap), (0, 1, gap)]
    for i in range(X):
        for j in range(Y):
            m, arg = 0.0, None
            for di, dj, pen in moves:
                if i - di >= 0 and j - dj >= 0 and D[i - di, j - dj] - pen > m:
                    m, arg = D[i - di, j - dj].item() - pen, (i - di, j - dj)
            v = m + S[i, j].item() - theta
            if v > 0:
                D[i, j] = v; back[(i, j)] = arg
    i, j = divmod(int(D.argmax()), Y); end = (i, j); path = [end]
    while back.get(path[-1]) is not None:
        path.append(back[path[-1]])
    qs = [p[0] for p in path]; rs = [p[1] for p in path]
    return round(D.max().item(), 2), (min(qs), max(qs)), (min(rs), max(rs))

print(dp_align(S))
print(dp_align(Q @ F.normalize(video(60), dim=-1).T))              # unrelated reference

# 5) micro-AP over pooled (query, reference, score) predictions (209.14), and VCL precision/recall (209.15)
def micro_ap(scores, is_true, n_pos):
    order = torch.argsort(torch.tensor(scores), descending=True)
    t = torch.tensor(is_true, dtype=torch.float)[order]
    prec = t.cumsum(0) / torch.arange(1, len(t) + 1)
    return (prec * t).sum().item() / n_pos

print(round(micro_ap([0.9, 0.8, 0.7, 0.6, 0.5], [1, 0, 1, 0, 1], n_pos=4), 4))

def vcl_pr(gt, pred):                                              # boxes: (ref0, ref1, q0, q1)
    ox = max(0, min(gt[1], pred[1]) - max(gt[0], pred[0]))
    oy = max(0, min(gt[3], pred[3]) - max(gt[2], pred[2]))
    lp = (pred[1] - pred[0]) * (pred[3] - pred[2]); lg = (gt[1] - gt[0]) * (gt[3] - gt[2])
    return round(math.sqrt(ox * oy / lp), 3), round(math.sqrt(ox * oy / lg), 3)

print(vcl_pr((40, 60, 10, 30), (42, 66, 12, 34)))

Output (PyTorch 2.8, CPU):

{'brighter': 2, 'crop 10%': 12, 'flip': 30, 'other': 36}
torch.Size([40, 60]) 0.427 0.965 0.594
offset 8 query (12, 27) ref (20, 35)
(4.96, (12, 27), (20, 35))
(0.0, (0, 0), (0, 0))
0.5667
(0.783, 0.9)

Read it line by line. The hash moves 2 bits for a brightness change, 12 for a 10% crop, 30 for a mirror, and 36 for an unrelated image: a mirror looks almost like a different image. In the matrix, the global score (0.427) and chamfer (0.594) are moderate, while both Hough voting (offset 8) and DP alignment find the exact copy: query 12–27, reference 20–35. Against an unrelated reference, no cell is strong enough to start a path (score 0.0; the box (0, 0) is just the empty default). The µAP of five pooled predictions with four true pairs is \((1 + \tfrac23 + \tfrac35)/4 = 0.5667\) (one true pair is never found), and the localization precision/recall match Figure 5.

Where this is used

ApplicationWhat is matchedTypical approach
Blocking re-uploads of removed contentUploads against a bank of banned videosFrame descriptors at about 1 fps, ANN index, alignment, high-precision threshold, human review for borderline scores
Hash sharing between companiesKnown harmful media across platformsCompact, open hashes (PDQ for frames, TMK+PDQF for whole videos) that can be shared without sharing the media
Copyright and broadcast monitoringFilms, sports and news footage in uploads and streamsPartial-copy localization; often combined with audio fingerprints [Likely]
Training-data deduplicationVideo–text pretraining sets against themselves and against benchmarksFrame descriptors + clustering; also removes test-set leakage (session 187)
Search and recommendationResults of one query or one feedCollapse near-duplicates to one item to improve diversity
Provenance and fact-checkingA viral clip against archivesFind the earliest source and the original context
Video-RAG and long-video systemsRepeated clips and replays in an archiveDeduplicate before indexing, so retrieval does not return the same footage five times (session 210)

Common mistakes

  • Using a semantic embedding (CLIP) as a copy detector. It puts different videos of the same topic close together. Use a copy descriptor, or at least verify with alignment.
  • One global vector per video for partial copies. A short copy is diluted (209.7), and averages of all videos drift together. Keep frame-level descriptors for localization.
  • Deciding on one frame match. At video scale, false frame matches are certain (209.4). Require a temporally consistent sequence.
  • Ignoring low-information frames. Black frames, fades and title cards match everything; the plain VSC22 baseline had µAP 0.010 because of them. Use a quality score, unnormalized norms or score normalization.
  • Assuming speed 1. Offset-only voting fails on sped-up copies (Figure 4). Vote on slopes, use DP moves, or fit a line robustly.
  • Reporting mAP for a detection product. mAP ignores distractor queries and calibration. Report µAP and the precision and recall at your operating threshold.
  • Testing only on the training edits. Hold out edit types; check per-edit recall, as in VSC22’s analysis.
  • Not re-checking the threshold when the database grows. False matches grow with the number of reference frames; a threshold tuned on 40k videos is too loose for 40 million.

Interview questions

What is the difference between video copy detection and video retrieval by meaning?basic
Copy detection asks whether two videos come from the same original footage, after edits (crop, re-encode, speed change, overlay). Retrieval by meaning asks whether they show the same kind of content (“a cat playing piano”). A copy detector should give a low score to two different cat videos; a semantic retrieval model should give them a high score. So they need different descriptors (copy descriptors like SSCD vs CLIP-like embeddings) and different metrics (detection µAP with one global threshold vs per-query ranking).
How does a perceptual hash such as pHash work, and what does it fail on?basic
Shrink the frame to a small gray image (32×32), take a 2-D DCT, keep the 8×8 lowest-frequency coefficients, and set each bit to 1 if its coefficient is above the median (209.2). Compare hashes by Hamming distance (209.1). It survives resizing, compression, mild noise and brightness changes because it keeps only coarse structure and compares numbers with each other. It fails on crops, padding, mirrors, rotations, large overlays, grids and screenshots, and it cannot separate similar-looking unrelated frames well. PDQ (256 bits, quality score, dihedral hashes) improves on it.
Why does averaging frame embeddings into one video vector fail for partial copies?core
The copied part is mixed with everything else. In a simple model where the non-copied part averages to a vector of the same length, orthogonal to the copied part, the cosine is \(\rho / \sqrt{\rho^2 + (1-\rho)^2}\) for a copied fraction \(\rho\) (209.7): 0.196 for 10 s inside 60 s. Also, averages of many frames all move toward the dataset mean, so unrelated videos get high similarity too. The VSC22 paper notes that all top teams used frame-level descriptors for this reason.
What is chamfer similarity, and what does it ignore?core
For each item of one set, take its maximum similarity to the other set, then average (209.8). ViSiL uses it between regions of two frames and between frames (after a CNN) of two videos. It avoids averaging vectors before comparing, so strong local matches are kept. It ignores order (shuffled frames score the same), is not symmetric (SCS averages both directions), and still averages over all query frames, so a short copy is diluted.
How do you find the copied segment and handle a speed change?core
Compute the frame similarity matrix \(S = QR^\top\). A copy is a line \(j = a i + b\) of high values. Either vote: each strong best match votes for \((a, b)\) over a small set of slopes (209.10), then the inliers give the start and end in both videos; or align with dynamic programming using moves (1,1), (1,2), (2,1) and penalized pauses (209.9), and back-track the best path. Offset-only voting (\(a = 1\)) fails at 2× speed, because the offset changes every frame (Figure 4). Learned methods (ViSiL, the VSC22 winner’s CNN filter) read the matrix like an image.
Why do black frames break a copy detector, and how do you fix it?core
After L2 normalization, a black or solid-color frame still has a unit descriptor, and all such frames point the same way, so they match each other with high similarity. In a large database every video with a fade has them. VSC22’s plain SSCD baseline scored µAP 0.010 on the test set for this reason. Fixes: drop frames with a low quality score (PDQ has one), keep descriptor norms so empty frames get small inner products (0.464), or apply score normalization against a background set (0.605 with L2 normalization).
Why does VSC22 use micro-AP instead of mAP?core
Copy detection is a decision with one threshold for all queries, and most queries are distractors. Micro-AP pools all (query, reference, score) predictions into one ranked list (209.14), so false positives on distractor queries count, and scores must be comparable across queries. mAP averages per-query AP over queries that have a positive, so it ignores distractors and calibration. On VSC22 submissions scored 9.4 points higher on mAP; the baseline’s gap was 22.2 points, which shows its poor calibration.
How is localization scored in VSC22?advanced
Each true copied segment is a box in (reference time, query time). For the top \(i\) predicted boxes, project all ground-truth, predicted and overlap boxes onto each axis and measure the length of the union of intervals. Precision is \(\sqrt{L^x_o L^y_o / (L^x_p L^y_p)}\) and recall \(\sqrt{L^x_o L^y_o / (L^x_g L^y_g)}\) (209.15); then µAP is computed as usual over the ranked boxes. The square root, added to VCSL’s definition, makes the measure less strict. Extra wrong boxes increase \(L_p\) and reduce precision; boxes that are too small reduce recall.
Explain ViSiL in a few sentences.advanced
ViSiL keeps a 3×3 grid of region features per frame (R-MAC from intermediate ResNet-50 layers, whitened, attention-weighted). The similarity of two frames is the chamfer similarity of their region-to-region dot products (209.11). The matrix of frame similarities between two videos goes through a four-layer CNN that learns temporal patterns such as diagonals; its hard-tanh output is reduced by chamfer similarity to one video score (209.12). It is trained with a triplet loss with margin 0.5 plus a penalty on outputs outside [−1, 1] (209.13). On FIVR-200K duplicate-scene retrieval it reached 0.892 mAP vs 0.775 for DP and 0.724 for Temporal Networks on the same features. It is expensive per pair, so it is used as a re-ranker.
A 64-bit hash and threshold 10 look fine in a test of 1,000 videos. What happens at a million?advanced
False frame matches grow with the number of frame pairs (209.4). Even with ideal independent bits, \(p_{\text{FP}} = 1.0 \times 10^{-8}\), so a 60-s query against \(10^6\) 60-s references (3.6 × 10⁹ pairs) gives about 36 false frame matches per query; real hashes are correlated and do worse. Remedies: longer hashes (256-bit PDQ), stricter thresholds, requiring temporally consistent sequences instead of single frames, quality filtering, and re-tuning the threshold on a held-out set at the real database size.
Design a system that blocks re-uploads of a banned video.advanced
Offline: for each banned video, decode at about 1 fps, drop low-quality frames, embed with a copy descriptor (SSCD-style, trained with crop, overlay, flip, screenshot and grid augmentations), score-normalize against a background set, and add to an ANN index; optionally also store PDQ hashes for sharing. Online: embed the upload the same way, search per frame, group hits by banned video, and keep candidates with a loose threshold. For each candidate run alignment (Hough with slopes, or DP) to find the copied span and a confidence. Block automatically above a high-precision threshold; send the middle range to human review with the matched time spans shown. Handle grids and screenshots by also embedding detected sub-regions. Measure with µAP and per-edit recall on held-out edits, with many distractor uploads, and re-tune thresholds as the bank grows. Run audio fingerprinting in parallel for audio-only copies.

Exercises

  1. A 2-hour film is indexed at 1 descriptor per second with 512 float32 values. How many megabytes is that? How many with 256-bit hashes per second?
  2. Using (209.3), compute \(p_{\text{FP}}\) for a 64-bit hash with \(\tau = 5\). How many false frame matches per query in the worked example?
  3. Using (209.7), what fraction \(\rho\) of copied content gives a global cosine of 0.5?
  4. In Figure 3, set the speed to 0.5×. Which move of \(\mathcal{M}\) does the path need, and why does a pause cost a penalty?
  5. A query is a copy at 1.5× speed: query frame \(i\) shows reference frame \(1.5 i + 7\). Which \((a, b)\) bin wins in (209.10)? What would offset-only voting see?
  6. Ground truth: reference [10, 30] s, query [0, 20] s. Prediction: reference [15, 35], query [5, 25]. Compute precision and recall with (209.15).
  7. Why does score normalization (209.6) help black frames more than distinctive frames?
Answerscheck
1. \(7{,}200 \cdot 2{,}048 = 14{,}745{,}600\) bytes \(= 14.7\) MB; hashes: \(7{,}200 \cdot 32 = 230{,}400\) bytes \(= 0.23\) MB. 2. \(p_{\text{FP}} = 4.5 \times 10^{-13}\); \(3.6 \times 10^9 \cdot 4.5 \times 10^{-13} = 0.0016\) false frame matches per query, under the random-bit model; the price is lower recall on edited copies. 3. \(\rho / \sqrt{\rho^2 + (1-\rho)^2} = 0.5\) gives \(3\rho^2 = (1-\rho)^2\), so \(\rho = 1/(1 + \sqrt{3}) = 0.366\). 4. At 0.5× each query second shows half a reference second, so the reference index advances by 1 every other query frame: the path uses (1, 1) and (2, 1) moves (and sometimes (1, 0)). A pure vertical or horizontal step means one video stands still; a free one would let paths run along the bright blocks of static shots, so it is penalized. 5. \(a = 1.5\), \(b = 7\): all copy frames vote for the same bin. With \(a = 1\) the offset is \(j - i = 0.5 i + 7\), which grows by 1 every two frames, so the votes spread over many bins and no clear peak appears. 6. Overlap: reference 15–30 (15 s), query 5–20 (15 s); predicted lengths 20 and 20; truth 20 and 20. Precision \(= \sqrt{15 \cdot 15 / 400} = 0.75\), recall 0.75. 7. A black frame is very close to many background frames, so its background similarity is high and a large amount is subtracted; a distinctive frame is far from the background, so little is subtracted and its true matches stay high.

Key takeaways

  • Copy detection asks “same source footage?”, not “same meaning?”. Real benchmarks (VSC22) are mostly distractors, with synthetic edits and partial copies.
  • Perceptual hashes (pHash, PDQ) are tiny and fast, survive re-encoding and mild edits, and break on crops, flips, overlays and grids. Judge them by the gap between copies and the nearest non-copy, not by the raw distance.
  • At video scale, single-frame matches are never enough (209.4): false frame matches are certain. Require temporal consistency and filter low-information frames.
  • Learned frame descriptors (SSCD-style, about 1 per second) plus score normalization are the base of every strong VSC22 system; the plain baseline failed (µAP 0.010) until black frames were handled.
  • Global video vectors dilute partial copies (209.7). Chamfer similarity keeps strong matches but ignores order. A copy is a line in \(S = QR^\top\): find it with Hough voting over slopes (209.10), DP alignment (209.9), or a learned reader such as ViSiL (209.11–209.13).
  • Evaluate with micro-AP over all queries (209.14) and box-projection precision/recall for localization (209.15), plus a per-edit robustness table with held-out edit types.

Key formulas

\[ d_H = \sum_b \mathbb{1}[h_b \ne h'_b], \quad p_{\text{FP}} = 2^{-B}\sum_{k \le \tau}\binom{B}{k}, \quad \E[\text{FP}] = T_q N T_r\, p_{\text{FP}} \]
\[ S = QR^\top, \quad \operatorname{CS} = \frac{1}{T_q}\sum_i \max_j S_{ij}, \quad H(a, b) = \sum_{(i,j) \in \mathcal{K}} S_{ij}\,\mathbb{1}[\operatorname{round}(j - a i) = b] \]
\[ \mu\text{AP} = \sum_i P(i)\,\Delta R(i), \quad P = \sqrt{\frac{L^x_o L^y_o}{L^x_p L^y_p}}, \quad R = \sqrt{\frac{L^x_o L^y_o}{L^x_g L^y_g}} \]

References for this session

  1. Pizzi et al. (2022). A Self-Supervised Descriptor for Image Copy Detection
  2. Kordopatis-Zilos et al. (2019). ViSiL: Fine-grained Spatio-Temporal Video Similarity Learning
  3. Pizzi et al. (2023). The 2023 Video Similarity Dataset and Challenge
  4. Pizzi et al. (2022). A Self-Supervised Descriptor for Image Copy Detection
  5. Kordopatis-Zilos et al. (2019). ViSiL: Fine-grained Spatio-Temporal Video Similarity Learning
  6. Pizzi et al. (2023). The 2023 Video Similarity Dataset and Challenge
  7. Douze et al. (2021). The 2021 Image Similarity Dataset and Challenge
  8. Johnson et al. (2017). Billion-scale similarity search with GPUs
  9. Kordopatis-Zilos, Papadopoulos, Patras & Kompatsiaris (2019). FIVR: Fine-grained Incident Video Retrieval
  10. He et al. (2022). A Large-scale Comprehensive Dataset and Copy-overlap Aware Evaluation Protocol for Segment-level Video Copy Detection
  11. Meta (Facebook) ThreatExchange (2019). The TMK+PDQF video-hashing and PDQ image-hashing algorithms
  12. Zauner (2010). Implementation and Benchmarking of Perceptual Image Hash Functions
  13. Papakipos & Bitton (2022). AugLy: Data Augmentations for Robustness
  14. Tan, Ngo, Hong & Chua (2009). Scalable detection of partial near-duplicate videos by visual-temporal consistency
  15. Kordopatis-Zilos, Tzelepis, Papadopoulos, Kompatsiaris & Patras (2022). DnS: Distill-and-Select for Efficient and Accurate Video Indexing and Retrieval