Keyframe Extraction Algorithms for Long Video

“Extract the keyframes” means two entirely different things depending on who is asking, and the command most people run answers the question they did not ask. Getting the distinction straight is most of the work; the selection algorithms after it are short.

Two unrelated meanings of one word

In a codec, a keyframe is an intra-coded picture — an I-frame, and in H.264 usually an IDR frame, which additionally clears the reference buffer so nothing after it may refer to anything before it. It is decodable on its own. Every other frame is a P-frame, predicted from earlier references, or a B-frame, predicted from references in both temporal directions. A group of pictures runs from one I-frame to the next, and its length is set by the encoder. Nothing in that definition mentions content.

In video summarization, a keyframe is a frame chosen because it represents a stretch of content — the still you would put on a contact sheet. It is a semantic selection, and the frame chosen is usually not an I-frame, because there is no reason for the most representative moment of a shot to coincide with the encoder’s refresh schedule.

Confusing the two produces a specific and common failure: someone runs an I-frame extraction, gets a plausible-looking contact sheet, and ships it as a summarizer. On some files it works by accident. On others it returns frames at fixed two-second intervals with no relationship to anything, and nobody can explain why the quality changed between uploads.

Where I-frames actually sit

Their placement is decided by two encoder mechanisms. The first is a maximum interval: x264 will insert an I-frame at least every keyint frames regardless of content, and its own default is 250. The second is scene-cut detection: the encoder measures how poorly the next frame predicts from the current one and, above a threshold, starts a new group of pictures because coding it as intra is cheaper than coding a hopeless residual. This is the mechanism that makes I-frames land on shot boundaries — not an understanding of editing, just rate-distortion arithmetic that happens to agree with one.

So on a source encode with scene-cut detection enabled, I-frame positions are a genuinely useful cheap proxy for cuts, and decoding only them is dramatically faster than a full decode because you skip the inter-frame reconstruction entirely.

# list frame types with their presentation timestamps
ffprobe -v error -select_streams v:0 -skip_frame nokey \
        -show_entries frame=pict_type,pts_time -of csv=p=0 input.mp4

# decode only the intra frames, keeping their real timestamps
ffmpeg -skip_frame nokey -i input.mp4 -vsync vfr \
       -frame_pts true out_%06d.png

And here is the trap. A file prepared for adaptive streaming is deliberately encoded with a fixed, closed group of pictures so that segments are independently switchable — typically something like -g 48 -keyint_min 48 -sc_threshold 0 at 24 fps, giving an I-frame every two seconds and scene-cut detection turned off entirely. On such a file, extracting I-frames is uniform sampling with extra steps, and it carries no content signal at all. You cannot tell from the pixels which kind of file you have; you check with ffprobe. The FFmpeg documentation covers both flags.

Choosing a representative frame

The semantic problem is: given a shot of N frames, return k frames that best stand for it. Three approaches, in increasing order of what they cost and what they get right.

• Positional. Take the middle frame of each shot. Sounds crude and is a strong baseline, because a shot’s middle avoids the transition blur at both ends. Use it as the control that any cleverer method has to beat.
• Clustering. Embed every frame — a colour histogram, or a vision-model embedding for semantic grouping — run k-means, and return the frame nearest each centroid. Return the medoid, never the centroid: a centroid is an average of vectors and does not correspond to any frame that exists. Choosing k is the real problem, and the usual answers are one per shot, or k set by an explained-variance criterion.
• Greedy coverage. Walk the frames in order, keep the first, and keep each subsequent frame only if its distance to every already-kept frame exceeds a threshold. This is farthest-point selection, it costs O(Nk) instead of a full clustering, it streams — you never hold all frames — and it produces a variable k that adapts to how much the content actually changes. For long video it is usually the right choice.

Greedy selection, worked

Take a ten-second scene at 24 fps — 240 frames — containing a wide establishing view, a slow push in to a table, and a hand entering the frame. Embed every eighth frame, use cosine distance, and set the threshold at 0.15.

kept: frame 1                       (first frame always kept)

frame  33   min distance to kept = 0.04   -> reject
frame  65   min distance to kept = 0.11   -> reject
frame  97   min distance to kept = 0.19   -> KEEP
frame 129   min distance to kept = 0.06   -> reject   (0.06 is to frame 97)
frame 161   min distance to kept = 0.09   -> reject
frame 185   min distance to kept = 0.22   -> KEEP     (hand enters)
frame 217   min distance to kept = 0.05   -> reject

selected: frames 1, 97, 185   -> 3 keyframes from 240

The two properties worth noticing are both consequences of comparing against every kept frame rather than only the previous one. First, the slow push in accumulates: frames 33 and 65 are each close to frame 1, but by frame 97 the accumulated drift has crossed the threshold, so gradual change is captured even though no consecutive pair ever differs much. Second, if the camera pushed back out to the original framing at frame 217, it would be rejected as a near-duplicate of frame 1 rather than kept as a change, which is correct for a contact sheet and wrong if you wanted every distinct camera move logged.

The threshold is the whole tuning surface. Lower it and you get more frames and more redundancy; raise it and you lose short events. Set it by choosing the number of frames you can afford downstream — if a vision model costs you a fixed number of tokens per frame, the budget from the captioning frame arithmetic converts directly into a target k, and you binary-search the threshold on a sample until you hit it.

Where selection goes wrong

• Fades and black frames. A fade to black produces a run of near-identical dark frames whose embeddings cluster tightly, so k-means happily spends a cluster on them and returns a black keyframe. Filter frames whose luminance variance is below a floor before selection; it costs one pass and removes the most visible failure.
• Continuous pans. A slow pan across a landscape is a continuum with no cluster structure at all. k-means will still return k clusters because you asked for k, and the boundaries between them are arbitrary. Greedy coverage degrades more gracefully here: it returns frames at roughly even perceptual spacing, which is the honest answer.
• Static shots with a small moving element. A locked-off camera on a doorway is 99% identical frames plus the two seconds somebody walks through. Global embeddings barely move, so the event is rejected as a near-duplicate. This is the case where frame-level selection is the wrong tool and a detector gating the selection is the right one.
• Encoding noise mistaken for change. On heavily compressed footage, block noise varies frame to frame and inflates low-level distances. If you are selecting on colour histograms rather than learned embeddings, expect the threshold to need retuning per bitrate — another consequence of what compression does to your pipeline.