RLE Compression using Hilbert curves

In my last post, I had a look at space-filling curves, and in particular at Hilbert curves. These are curves that fill a higher-dimensional region, for example the unit square.

These curves are interesting as they preserve spatial locality. This means that two points that are close to each other along the curve will also be close to each other in the two-dimensional square. However, the reverse is not always true: two pixels that are close in the square might be far apart along the curve's path.

Run-Length Encoding

RLE is a very simple data compression algorithm, which is usually applied to images.

Given an input string, the algorithm replaces consecutive occurrences of the same characters with a pair of values: the number of times the character repeats, and the character itself. For example,

This works fairly well for grayscale, low-resolution images, but is ineffective for more complex data.

Hilbert-RLE

The most straightforward way to run RLE on an image is to scan its pixels row by row, treating the image as a single array. RLE will only work well if the image has long horizontal stretches of the same color. If the image has vertical patterns, the performance will be unoptimal.

Instead of doing this, I wanted to try to order the pixels in the order defined by a Hilbert curve. This way, two adjacent pixels in the ordering are also spatially close in the image, contrary to the naive implementation where this is only true horizontally (and at the wrap at the end of a line).

Some tests

For these tests, the images are square, and their side length is a power of 2. This way, a Hilbert curve of a certain order will perfectly cover all pixels. The images are also converted to grayscale.

Remarks

Hilbert-RLE often provides a significant improvement for images where the patterns are not strictly horizontal. Naive RLE compresses very effectively images that have strong horizontal patterns.
Hilbert-RLE also looks very robust to rotation.