Reexecuting it all is the simplest strategy if you don't need to undo often or the performance is acceptable anyway.
But in general, every command would generate an "undo record" with information to undo it.
In case of the brightness/contrast change you can do that by undoing in the naive way and then storing the difference between the "naively undone" image and the origignal version, compressed, in the undo record.
In general the undo record will only be large if you lose a lot of information, and then there won't be as much information left to lose and thus the next undo records won't be able to be so large, so overall the total size of the compressed current image and undo record will amortize and be in the range of the size of the original image plus the command description.
For example, once you turn the image fully grey, then all per-pixel transformations will be either be reversible or the undo record will compress to the effect on one pixel since it's the same for all the image.
This doesn't hold however if you also have operations that create information (e.g. something that draws a pseudorandom image with you then adjust contrast on, resulting in a pseudorandom undo record that you can't compress with standard techniques): in that case I think reexecuting the command history is the only space-efficient solution that doesn't require coding for the specific application.
This "undo record" sounds like (essentially) the same thing as storing the (compressed) diff from the current state to the prior state which you were arguing against. If you have an operation that is changing a lot and isn't reversible, either you are reexecuting from the beginning of time (which particularly for image editing would be ridiculous: even a single operation on the image is often annoyingly slow, much less suddenly doing tons as you rapidly make changes and then undo back through them) or you are storing checkpoints at some frequency in the form of diffs on the full serialized state (which seems to be what you are returning to re-suggest anyway).
But in general, every command would generate an "undo record" with information to undo it.
In case of the brightness/contrast change you can do that by undoing in the naive way and then storing the difference between the "naively undone" image and the origignal version, compressed, in the undo record.
In general the undo record will only be large if you lose a lot of information, and then there won't be as much information left to lose and thus the next undo records won't be able to be so large, so overall the total size of the compressed current image and undo record will amortize and be in the range of the size of the original image plus the command description.
For example, once you turn the image fully grey, then all per-pixel transformations will be either be reversible or the undo record will compress to the effect on one pixel since it's the same for all the image.
This doesn't hold however if you also have operations that create information (e.g. something that draws a pseudorandom image with you then adjust contrast on, resulting in a pseudorandom undo record that you can't compress with standard techniques): in that case I think reexecuting the command history is the only space-efficient solution that doesn't require coding for the specific application.