Techniques and tools for video frame interpolation and motion analysis are described. The techniques and tools may be implemented separately or in combination in software and/or hardware devices for various applications. For example, a media playback device uses frame interpolation and motion analysis in real time to increase the frame rate of streamed video for playback. The device uses feature/region selection in global motion estimation, local motion estimation to correct the global motion estimation at an intermediate timestamp for a synthesized frame, and vector switching in the local motion estimation.