How to efficiently implement undo history for images

Question

I'd like to implement an undo/redo history for an image viewing/editing program I'm writing.

If we were talking about undoing text, it could probably be fairly straightforward to just keep the current text and put inverse deltas in the history, similar to how version control systems work. But for images, it's a little bit more hairy than that.

Let's say my program has two operations: negating an image, and converting it to grayscale. Negating an image is reversible, while grayscale conversion is not. That means that you can't just keep the latest image and reverse the operations, because not all can be reversed. There's an answer here which explains this situation.

The alternative is to store the entire image in memory with each change, but that can be expensive, especially for larger images. One solution I can think of is to combine both approaches and save the whole image for irreversible operations, but otherwise store only the operation in memory. For example:

1. Negate image (undo operation: negate image)
2. Rotate 90 degrees clockwise (undo operation: rotate 90 degrees anticlockwise)
3. Convert to grayscale (undo operation: load image from memory before this operation)
4. Negate image (undo operation: negate image)

Is there any better way to implement this? Also, what is a reasonable way to keep memory consumption within reasonable levels when the operations become numerous?

Answer 1

You said it: if the functions you apply are not invertible (onto and one-to-one) then you'll need to keep more information than just the function used and its input parameters. This is a mathematical fact unfortunately, so you cannot get around it.

1. Invert - Is a bijection, so you only need to store that you inverted the image on the stack
2. Grayscale - Is onto, but not one-to-one, so you'll need to store extra information along with the function used.

Here are a few things you can do to conserve memory:

1. Store only two original colors of the three. The grayscale formula is output=0.21 R + 0.71 G + 0.07 B. Since you'll know the output, you only need to store the red and blue channels in memory, and ignore the green. This is an analog to the YCbCr colorspace. You'll have the grayscale, and only need to store the Cb and Cr images in memory.

2. Compression. Lossless compression is possible with images if you store them in the png format or jpeg format with 100% quality. Depending on the language, you should be able to write to a byte array in memory after conversion. Depending on the image, this could be significant savings.

3. Saving to temporary disk space. People don't want their computer to crash by taking up memory, and loading images is fast from disk these days. All OS offer application-level temporary space. Just make sure you read from the disk into a large buffer instead of reading one byte at a time, and read the entire contents into memory before doing processing. This will make reading the images from the disk super fast.