I agree that if the requirement requires overlay onto an HD signal, then an Arduino isn't going to cut it. I designed the Video Experimenter shield for Arduino, but this only works for a composite video signal. It uses an LM1881 sync separator chip to detect the timing of the video signal, then in Arduino code you can overlay low-res monochrome pixels onto the video. It works well for many applications, but is decidedly low-tech!