That's what the Burrows–Wheeler transform does for text. A similar approach could work for images.

It's a good point. PNG uses DEFLATE internally for the compression, it would be interesting to see what would happen if you used bzip2 instead, which uses the Burrows-Wheeler transform.

To me the whole experiment suggests otherwise:

it shows that naturally occurring images are organized by having similar rows and columns close to each other, which is - by default - good for most compression algorithms that prefer regularities/similarities to be as local as possible.

edit: but it can be good for other cases, where there are no good-enough default orders. For example "customer - product bought" matrix (binary matrix, customer rows, product columns: X customer bought Y product = 1, otherwise =0 ).

Here the order of rows/columns are not predefined, and ordering by similar customers and products the compression of the matrix could be improved. Finding these similarities also can be a good starting point for some recommendation/collaborative filtering engine.

IIRC the HDF5 data storage format compresses per-bit (e.g. all LSB's together) instead of per pixel when compressing image data, and tests on our data sets have shown tvis significantly improves compared to ZIP compression for instance.