How does the h.264 encoder determine where to put i-frames?

Question

I'm reading a bit on I-frames and their counterparts, P-frames and B-frames. I understand the usage. I-frames are the key to the compression and following P and B-frames can use the data in I-frames to save on bits.

However, what I would find interesting is knowing how the encoder determines which frames should be I-frames and which should be P's and B's and pull their data from them. How does the encoder decide which frames will be I-frames?

---

Side thoughts (you don't have to answer, but these are interesting and useful to me in the future): Are I-frames easier, as in faster, to find and extract than say extracting every 30th frame? If a video is a slide show with audio and no slide animations, are I-frames likely to coincide with slide changes? Would compression be better on a video made from slides images rather than the same images taken in via stream in real time?

Answer 1

This is a complex topic, with the exact algorithm unique to each encoder.

Below is a pseudocode explanation from a x264 developer. B-frames aren't accounted for, but basic logic should be similar.

encode current frame as (a really fast approximation of) a P-frame and an I-frame.

if ((distance from previous keyframe) > keyint) then
    set IDR-frame
else if (1 - (bit size of P-frame) / (bit size of I-frame) < (scenecut / 100) * (distance from previous keyframe) / keyint) then
    if ((distance from previous keyframe) >= minkeyint) then
        set IDR-frame
    else
        set I-frame
else
    set P-frame

encode frame for real.

scenecut is the scene change threshold value. 0 means current frame is identical to previous frame, and 100 means it is completely different.

keyint is the maximum permitted distance between two keyframes; minkeyint is the minimum.

IDR (instantaneous decoder refresh) frames are keyframes such that no future frame requires to refer to a frame earlier than the IDR-frame for decoding. Not necessarily true for plain I-frames.