Accelerated access to frames from a compressed digital video stream without keyframes

One or more computer-readable storage media devices, storing and having fixed thereon computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform acts comprising:

• recording a digital video stream having encoded video frames;
• capturing one or more decoder states that represent states of a decoder when decoding one or more associated video frames, wherein the capturing is based at least in part on a frame rate required for accelerated playback;
• creating a state index for the digital video stream, the state index storing the one or more decoder states;
• playing back the digital video stream by using a particular decoder state in the state index to begin decoding at or near a target video frame in the digital video stream from which playback is requested;
• pausing the digital video stream and rendering a video frame to display a lower quality image;
• decoding video frames preceding the video frame to produce a higher quality image;
• and
• substituting the higher quality image for the lower quality image.

A digital video recorder comprising:

• a store configured to receive a digital video stream having encoded video frames;
• a keyframe synthesizer for capturing one or more decoder states that represent states of a decoder when decoding one or more associated video frames;
• a state index for the digital video stream, the state index storing the one or more decoder states;
• a playback decoder to play the digital video stream based at least in part on a particular decoder state in the state index, wherein the playback decoder is configured to:
• pause the digital video stream and render the video frame associated with the particular decoder state such that a lower quality image is depicted;
• decode a series of video frames preceding the video frame associated with the particular decoder state to produce a higher quality image;
• and
• substitute the higher quality image for the lower quality image.