They took a still image and added moving objects to it, but I don't know if they can apply the technique to videos yet (although I'm sure that's coming).

Trust me, that's a trivial extension. It's more time-consuming to do these things on video, but on the other hand one can also extract a ton more information from the scene if the camera or objects within its purview are in motion.

There is a company which puts ads on objects in videos. Seems like a step in the right direction.

This could be a huge step for augmented reality if the process can be applied in real-time without any user input. It could improve on other research that's already out there like this one: http://www.youtube.com/watch?v=XCEp7udJ2n4

I've seen videos of this already. I think Maya was the software?