I would try to maximize the delta(PSNR) per frame, as a first cut. There are also good perceptual difference metrics. I don't know what algorithm to use. Maybe just the absolute difference on each pixel. Or, you could think of groups of colors to enhance if you're willing to grow the size of the image.