Approaches to re-encoding image sets using frequency-domain differences, along with corresponding approaches to reversing the re-encoding of the image sets. For example, a re-encoding tool computes frequency-domain differences between (a) quantized coefficients for a block from encoded data in a first format and (b) quantized coefficients for a prediction of the block. The re-encoding tool entropy codes the frequency-domain differences, producing encoded data in a second format for the compressed images. Such re-encoding can significantly reduce storage cost for previously compressed images, compared to the storage cost for the previously compressed images in the first format, without hurting image quality. Subsequently, the previously compressed images in the first format can be recovered from the encoded data in the second format. Or, the encoded data in the second format can be decoded to reconstruct the images.