What is the best routine for graphics compression?

The place for codemasters or beginners to talk about programming any language for the Spectrum.
Joefish
Manic Miner
Posts: 618
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Wed Oct 02, 2019 11:20 am

Generic byte packers aren't always the best at compressing graphics though. If you can take advantage of some knowledge of how graphics data is more likely to repeat, then you can optimise the compressor to pack that data. Einar's re-arranges a staggered Spectrum screen to line-by-line order to bring potential repetitions closer together, which makes them easier for an LZ77-type algorithm to compress. My alogrithm pre-processes the graphics to turn common repetitions into zeroes, which my packing routine can optimise above all other values, a bit like a RLE algorithm would do.
0 x

Joefish
Manic Miner
Posts: 618
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Wed Oct 16, 2019 7:28 pm

Hmm. Just been meddling with a screen compressor that gives some really good results on the selection of screens I was using. It gets Einar's Cobra pic down to just 1945 bytes. But try it on that pack of Russian screens and it's not so good. It 'compresses' MAC's Phantis screen 'down' to only 7123 bytes! :lol: (that's more than it was originally, in case you didn't notice)

But on a couple of examples like that BatmanTheCapedCrusader I get 4957 bytes compared to 5457 (I think) for RCS + ZX7
It works best on patches of colour and lines - multiple levels of stipple and colour changes just make it worse. It might be good for something like that Hobbit update.

I should probably tweak the algorithm so it just stops trying when faced with too much changing data... :geek:
0 x

catmeows
Berk
Posts: 34
Joined: Tue May 28, 2019 11:02 am

Re: What is the best routine for graphics compression?

Post by catmeows » Thu Oct 17, 2019 9:00 am

How it works ?
Honestly - a decent benchmark suite of screens would really help. And I don't mean just full size screens but also in-game illustrations, for example from Case of missing swan and even smaler examples, something of size 6*6 chars like pictures from Rychle Sipy.
0 x

Joefish
Manic Miner
Posts: 618
Joined: Tue Nov 14, 2017 10:26 am

Re: What is the best routine for graphics compression?

Post by Joefish » Thu Oct 17, 2019 11:24 am

Well, with smaller graphics there's the question of whether you're expecting to compress the data that makes up a small graphic, and what order the bytes for that are in, or whether you mean to paste the graphic onto an otherwise empty screen and compress the whole screen. As they're different tasks. A whole screen has a fixed format that you can exploit. Maybe known sized graphics have formats that are exploitable too. But arbitrary data of variable length is something different.

My 'MiniDict' technique is to XOR each attribute with the one before, which turns repetitions into zeros.

I then XOR each pixel line with the one above, which again reduces blocks of pixels to just lines and dots around the edges. (What it's not good at is stipples).

Then I do a frequency analysis of what's left, and pick out the 16 most commonly used bytes (other than 0). Again, this takes advantage of the dots that are left by the XOR process.

The encoding is a bitstream as follows:

16 x bytes - common byte mini-dictionary
0 bit -> 0 byte
1,0 bit -> read next four bits, look up byte in mini-dicitonary
1,1 bit -> read next 8 bits as literal byte

I've just added a refinement that after six 0 bits, it then either flags a 1 to continue otherwise it contains a binary number of how many more zero bytes to skip. This helps it skip over large blank areas of the screen. I can post some code later. But it actually runs on a Speccy. Or at least, in an emulator.
0 x

Post Reply