Sounds like you're trying to implement an Ambilight. If so, I recall seeing a thread on that, too. For that, you basically want something to average the whole frame down to something like 3x3 pixels, and then send those colors to the lamps.
I don't know if you can sample video on the Arduino itself, especially if you're talking about faster HD rather than slow NTSC. One issue is when there's a tiny little spot of yellow in a big blue scene, you don't want the tiny yellow pixel to be chosen for the ambilight. That's why the other sources downsample to get good dominant colors. So, if you're playing video from your PC instead of a dedicated player, these solutions sample the PC's video output and talk to the Arduino Ambilight circuits directly.