[nitrogen]

If you could point to a region of the image where the corruption begins, you would reduce the number of possible images significantly.

[porges]

That sounds plausible. Another idea: choose a section of "bad image" and a section of "good image" which should have similar colours and then generate mutations of the corrupted DCT square until you have a close match between the two areas.

[aninhumer]

Given that we're assuming some kind of correctness metric for the final image, could we not also use this metric to locate the start of the corruption?