Alternative traversal (Hilbert curve, Z curve, etc)

[nigeltao]

Context: https://github.com/phoboslab/qoi/issues/5

[nigeltao]

Another option is snake curve: left-to-right for even-Y rows and right-to-left for odd-Y rows.

[chocolate42]

Traversal is not something QOI needs to care about, it has the rough concept of locality and rgba but not 2D. Better IMO to pipe the input through a traversal on encode and reverse with a pipe from the decoder if desired. Same goes for other transformations like color space, QOI should be a pure pixel packing algorithm used standalone or as part of a more complicated solution if desired.

[renato-grottesi]

I think this is a great idea. QOI is an image compression algorithm that takes advantage from pixel locality, but it exploits 1D locality while mainly compressing 2D structures. Having the image scanned with a Hilbert pattern that takes into account 2D locality of 8 (or 16) lines at the same time, would surely trigger longer runs of same colored pixels and increase the matches in the hash table of previously seen colors. It may cause data cache misses in the L1/L2 caches in older CPU, so you may want to balance that with some manual pre-caching.

[nigeltao]

I did a quick experiment where the source image is cut into NxN tiles (for N=16 or N=64) and each tile's pixels are adjacent in pixel traversal order: left-to-right top-to-bottom within a tile, and then tiles are traversed left-to-right top-to-bottom.

The compression ratios don't move that much. It's hard to get excited about the extra complexity.

master is commit 2ee2169 (2021-12-11).

        decode ms   encode ms   decode mpps   encode mpps   size kb    rate

## Total for images/icon_512
qoi-master:   1.5         1.3        171.27        198.88        85    8.4%
qoi-tile16:   2.0         1.7        131.17        157.37        83    8.2%
qoi-tile64:   1.9         1.5        138.02        176.36        80    7.9%

## Total for images/icon_64
qoi-master:   0.0         0.0        104.20        100.77         4   28.7%
qoi-tile16:   0.0         0.0         90.63         88.28         4   30.2%
qoi-tile64:   0.0         0.0         92.34         93.98         4   28.7%

## Total for images/photo_kodak
qoi-master:   6.1         6.7         64.95         58.81       671   43.7%
qoi-tile16:   6.6         7.5         59.36         52.61       638   41.6%
qoi-tile64:   6.6         7.2         59.14         54.47       647   42.2%

## Total for images/photo_tecnick
qoi-master:  22.6        26.3         63.73         54.84      2527   44.9%
qoi-tile16:  24.3        29.3         59.25         49.15      2549   45.3%
qoi-tile64:  23.7        29.2         60.87         49.26      2522   44.8%

## Total for images/photo_wikipedia
qoi-master:  17.0        20.2         63.66         53.81      2102   49.6%
qoi-tile16:  18.6        22.5         58.34         48.19      2108   49.8%
qoi-tile64:  18.2        22.5         59.68         48.29      2096   49.5%

## Total for images/pngimg
qoi-master:  16.4        16.7        110.41        108.00      1436   20.3%
qoi-tile16:  20.4        19.3         88.85         93.65      1413   20.0%
qoi-tile64:  19.8        18.5         91.50         97.73      1411   20.0%

## Total for images/screenshot_game
qoi-master:   6.7         6.5         93.95         97.27       519   21.0%
qoi-tile16:   7.8         7.8         80.88         80.79       520   21.1%
qoi-tile64:   7.6         7.3         83.59         87.12       512   20.7%

## Total for images/screenshot_web
qoi-master:  55.7        44.8        145.98        181.17      2649    8.3%
qoi-tile16:  73.5        55.3        110.54        146.90      2653    8.4%
qoi-tile64:  74.6        53.1        108.92        153.15      2600    8.2%

## Total for images/textures_photo
qoi-master:  15.0        16.0         69.87         65.44      1981   48.4%
qoi-tile16:  16.8        18.8         62.24         55.88      1917   46.8%
qoi-tile64:  16.8        18.8         62.39         55.89      1951   47.6%

## Total for images/textures_pk
qoi-master:   0.8         0.8         59.21         57.16        75   43.5%
qoi-tile16:   0.8         0.9         57.87         49.20        74   42.9%
qoi-tile64:   0.8         0.9         56.67         49.78        75   43.5%

## Total for images/textures_pk01
qoi-master:   1.6         1.7         80.68         75.78       178   35.2%
qoi-tile16:   1.8         2.0         73.95         65.57       180   35.6%
qoi-tile64:   1.8         2.0         72.08         66.11       179   35.4%

## Total for images/textures_pk02
qoi-master:   4.5         4.5         67.71         67.38       479   40.4%
qoi-tile16:   4.7         5.1         64.52         59.33       477   40.3%
qoi-tile64:   4.8         5.1         63.52         59.39       477   40.2%

## Total for images/textures_plants
qoi-master:   8.6         9.9        123.62        107.79       922   22.2%
qoi-tile16:  10.3        11.7        103.07         91.27       932   22.4%
qoi-tile64:  10.3        11.0        102.94         96.78       921   22.2%

# Grand total for images
qoi-master:   5.1         5.2         91.89         89.38       463   25.6%
qoi-tile16:   5.8         6.0         79.45         76.80       462   25.5%
qoi-tile64:   5.7         5.8         80.99         79.77       459   25.3%

        decode ms   encode ms   decode mpps   encode mpps   size kb    rate

qoi-tile64-2ee2169.h.txt

[renato-grottesi]

Hi @nigeltao ,

I hacked over your hack to try a simple 4x4 Hilbert curve on qoi1 as in the attached qoi.h.txt and I see further improvements. Unfortunately I'm in no position to code more than one hour each day due to paternity duties, but if you can wait, I can try to see if bigger Hilbert tiles could help further with the compression ratio :-)

EDIT: The 8x8 Hilbert curve improves a little bit more:

#define QOI_TILE_SIZE 8
int Xs[] = {0, 0, 1, 1, 2, 3, 3, 2, 2, 3, 3, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 5, 5, 4, 4, 4, 5, 5, 6, 6, 7, 7, 7, 6, 6, 7, 7, 7, 6, 6, 5, 4, 4, 5, 5, 4, 4, 5, 6, 6, 7, 7};
int Ys[] = {0, 1, 1, 0, 0, 0, 1, 1, 2, 2, 3, 3, 3, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 4, 4, 5, 5, 6, 7, 7, 6, 6, 7, 7, 6, 5, 5, 4, 4, 3, 2, 2, 3, 3, 3, 2, 2, 1, 1, 0, 0, 0, 1, 1, 0};

[renato-grottesi]

I left my pc running the bench and I took a look at the results. The Hilbert 8x8 can improve the compression ratio by ~5% for qoi images that were over 1kb, but it looks a bit unpredictable for smaller images (I can take a look at why). The biggest gain I observed was with the images/wallpaper/manouchehr-hejazi-6F0wVthJqL0-unsplash.png image that went down from 30468 to 26258 (86.18%). I then renamed that image to stars.png, compress it with qoi Hilbert, run it through 7z to check the entropy, and it looks like it can even beat png by 25%:

-rw-rw-r-- 1 renato renato 23318021 des.  14 07:55 stars.png
-rw-rw-r-- 1 renato renato 23241929 des.  14 08:02 stars_png.7z
-rw-rw-r-- 1 renato renato 26888881 des.  14 07:56 stars.qoi
-rw-rw-r-- 1 renato renato 17743595 des.  14 08:03 stars_qoi.7z

[renato-grottesi]

Uploading a slightly nicer version of the change that does decode in place without allocating a second temporary buffer: qoi.h.txt

[lurkertech]

Zig zag order might work better than Hilbert (in terms of more runs) and possibly be simpler to implement too:

https://www.google.com/search?q=zig+zag+order&client=firefox-b-d&source=lnms&tbm=isch&sa=X&ved=2ahUKEwjO1oGIzer1AhUFIbcAHbemC24Q_AUoAXoECAEQAw&biw=1376&bih=684&dpr=1.4

[AZMCode]

Has no one coded a zig-zag order yet? I might give it a whirl.

[AZMCode]

This might actually be kind of interesting for another reason: Video Encoding Considering this is a way to perhaps let the algorithm better perform in 2D spaces, perhaps we could treat video as a big 'ol 3D image, with the third axis being how many frames have advanced. Perhaps with chunks along the way to help it deal with the excessively large third axis compared to the other two. I might give it a whirl and compare it to other lossless video codecs.

[AZMCode]

Linking relevant issue: https://github.com/nigeltao/qoi2-bikeshed/issues/37

[AZMCode]

In fact QOI's ability to encode differences between pixels efficiently might make it particularly useful to run the zig-zag not in a 2D plane that is the current frame, but along a line over a pixel's evolution over time, as those changes seem to be quite small in regular video.