How Video Compression Works

How video compression works, and why that glitch happens.

Videos are too big

A video is a bunch of photos. Store it as full photos back to back and it would get ridiculously big. Take the 1920 x 1080 60FPS videos we watch on YouTube all the time, uncompressed close to 7GB a minute. On YouTube it's at most about 40MB a minute. Almost 200 times smaller and we barely notice. What happened?

So we encode

Raw video is too big, so almost every video gets compressed to some degree. That's video encoding, and the algorithms are amazingly sophisticated and beautiful.

Encoding saves space by finding redundancy. Picture a singer standing still, singing. Only the mouth moves. Background and body don't. Why resend the black background pixels and the singer's body every frame? You don't. They repeat.

Video repeats in space and in time. Cutting repetition in space is intra-frame coding (inside one frame). Cutting it in time is inter-frame coding (across frames). Under the hood you get the Discrete Cosine Transform for shrinking neighboring pixel data, motion-vector prediction, in-loop filtering, and more.

Intra-frame coding

Make each photo smaller!

A photo is a bunch of pixels. If we can cut the information about repeating pixels inside one image, we cut spatial redundancy. One of the simplest ways is averaging. Leave a pixel empty, keep the ones around it, and at playback fill the gap with the average of its adjacent pixels.

Fun part, adjacent doesn't mean up, down, left, right. Pixels are stored left to right, top to bottom. Averaging all four sides means waiting for the right and bottom pixels, then coming back. Too slow for playback. So intra-frame coding keeps the upper-left, upper, upper-right, and left pixels and averages from those when it hits a gap.

Inter-frame coding

Don't resend what you already sent. Recycle it!

Remember school award ceremonies before the holidays? Same award, 30 people. If the principal read every certificate out loud, how long and boring and painful would that be? They don't. They say "same as above" and move on. Saying "same as the last person" is all it takes, and we get our holiday afternoon back. The principal just did inter-frame compression.

Video is the same. Many videos have similar frames back to back, so a frame can be described by the frames before and after it, or skipped altogether. That cuts temporal redundancy.

#1. I-Frame, the reference

An I-Frame (Intra-coded picture) is basically a photo. Everything in an I-Frame is new information, and it's the reference for describing the frames around it.

#2. P-Frame, only the change

A P-Frame (Predicted Picture) sits between I-Frames and holds only the change from the previous frame. Anything shared gets pulled from the frame before. The picture shows it better.

The arrows are motion vectors, which show the change. A P-Frame also carries transform values to correct the prediction, and sometimes brand-new image data. It's about half an I-Frame's size. In real encoding, of course, the encoder doesn't compare every pixel. It splits the frame into blocks called macroblocks, or coding tree units in HEVC, the latest video codec, and compares those.

#3. B-Frame, saving data

A B-Frame (Bidirectionally Predicted Picture) sits between I-Frames and P-Frames and builds its picture from the I-Frames or P-Frames both before and after it. Sounds like a P-Frame, so why bother? Size. Because a B-Frame uses data from both sides, it can leave out that much more. A B-Frame is only about 25% the size of a P-Frame.

Like a P-Frame, a B-Frame uses motion vectors and transform values for prediction correction. B-Frames refer to I-Frames and P-Frames, but in recent codecs like HEVC and VVC, a B-Frame can also refer to other B-Frames.

Why ghosting happens

Trouble starts when the packet with an I-Frame gets lost. The reference the surrounding P-Frames and B-Frames depend on is gone. A good streaming app uses all sorts of algorithms to detect packet loss early and ask for the packets again. But if the server is unstable or the app is poorly made, it won't notice the lost I-Frame.

Then, with the I-Frame gone and only the following P-Frames and B-Frames arriving, their changes get applied to the wrong I-Frame.

A picture is worth a thousand words

Still not clicking? Easier to see it. With a video library like FFmpeg you can deliberately corrupt a video file's frame data. This kind of art is called datamoshing.

I used Python and FFmpeg to damage the I-Frames in a music video and force the ghosting.

• Every I-Frame got overwritten with the frame before it, probably a P-Frame or B-Frame. So no new information ever comes from an I-Frame. The scene stays put but the people still move, because the changes (P-Frames and B-Frames) were applied to the wrong reference (I-Frame).
• Sometimes part of the screen looks clean for a moment. A P-Frame can carry new data too. But since the I-Frames, which are all new data, were deleted, the whole screen never comes back clean, even when parts briefly do.
• It breaks into big, obvious squares, not fine sand. Compression runs per macroblock (coding tree unit), a bundle of pixels, not per pixel. When this happens during a broadcast, people usually call it a "pixelated video".

Watch it knowing there are no I-Frames and the relationship between I-Frames, P-Frames, and B-Frames gets much clearer. I'll cover how to break a video with FFmpeg some other time.

---

• If you find an error in this post, please send it to mail@chosunghyun.com.
• An earlier version said "However, to prevent the error from getting bigger, B-Frames do not refer to other B-Frames. They only refer to I-Frames or P-Frames." That was wrong. In codecs like HEVC and VVC, B-Frames can reference other B-Frames. Thank you so much for reporting it. Credit: (anonymous)