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.