Using Arduino to control video

could it be Mpeg 4

For a microcontroller (without a DSP), that would probably be one of the worst formats, because decoding it is both memory and processor intensive.