RLE Image Compression using 3 Colours


(Josh Goebel) #21

Picking black as the variable run length color (I hard coded it just to see if it would help) this results in 318 bytes vs 349, a 31 bytes savings for image 3. 245 vs 283 for image 2. Both my run lengths are variable so add an extra byte in the header to keep track of that. Defaulting to 0 would probably work well for a lot of images even without a palette.


(Simon) #22

These are good numbers but they fall short of the Cabi version which I cannot fathom as the savings on grey should outweigh the addiitional bits added.


(Josh Goebel) #23

It sounded like a good idea when I suggested it but remember that just switching from a 1 bit to 2 bit [uncompressed] stream DOUBLES the amount of data you’re compressing… so the algorithm improvement needs to be at LEAST twice as effective as the original just to pay back that penalty - before it could even begin to actually save space.

So it’s actually pretty impressive that we can even get close. Really you could double the “original size” and you’d see our compression ratio is actually a LOT tighter than either of the others (if you say we are processing a 2bit stream).

Update:

I think what might be best is to stick with a B/W encoding but find an escape code to say “stream of 20 dithered pixels”. You just want to avoid embedding that boolean for EVERY single run (which as we already see it’s almost impossible to pay back). So what I’d suggest trying is periodic escape bit:

- The header includes a byte that tells how many "runs" before an escape bit is found (the encoder would try many possibilities)
- This allows you to only encode 1/5 or 1/10 or 1/20th as many escape bits as you otherwise might doing it EVERY time  
- An escape bit of 0 does nothing (just a nod to continue, all is well)
- An escape bit of 1 switches to 2 bit encoding:
-- 00 Black
-- 01 Grey
-- 02 White
-- 03 Return to 1 bit encoding

Of course the encoder would have to be analyzing the stream to decide when switching encoding modes for a sequence would prove optimal. Theoretically this would have all the benefits of encoding 1 bit data (no doubling of the data set) but allow you to switch to 2-bit encoding ONLY when it was needed. Of course because the escape bit is only periodic you’d miss some opportunities, but the ones you catch should pay for themselves.

For a pure RLE algorithm I can’t see how this wouldn’t pay for itself provided the periodic escape bit doesn’t eat into that savings too much. Encoding dither is like the WORST case scenario for pure RLE.

I asked the author of ArdBitmap if there is a reason he/she hasn’t posted the source code for the encoder, but I haven’t heard back yet.

Read the decoder. Looks like a modified form of https://en.wikipedia.org/wiki/Elias_gamma_coding. The nice thing about black and white is you can avoid encoding the colors at all… you can just record the run lengths and toggle the color at the end of each run. So your data stream looks like:

8 pixels, 5 pixels, 2 pixels, 1 pixel, etc.

Therefor a run of 1, 0, 1, 0, 1 looks like 0b11111. Making dither no more expensive than raw data. BUT still more expensive than it would be if you could RLE encode it with an escape sequence.

Ok actually I think it’d be pretty hard to beat Elias Gamma unless you have LARGE swaths of dither (a lot more than image 3). The problem is for dithered areas you need to escape, run length, escape… The escape code means you have to limit the max run length… so if you limited it to say 15 that’d mean more runs… and the longer runs you allow the longer your escape code becomes… so pretty soon (not capping run length) it takes you 10-12 bits just to say “here is a sequence of grey”, not even counting the run length… although actually if you assume the run length has to be large to even justify it then you can save a lot of space encoding the run length… so actually…

If the author opens up the source to ArdBitmap and it’s legible I might try and add this and see if it helps.


(Ignacio Viña) #24

Sorry. I didn’t release a legible code of the encoder but I think that @zeduckmaster did inside its image converter:

The algorithm is RLE with variable size. The fundamental improvement over codi is because it has several ways to read the pixel array and choose the best one.


(Josh Goebel) #25

Yours seems to be the smallest (in terms of output) so I wanted to start with your code and add the escaping I mentioned above and see how it turned out. Didn’t want to reimplement it from scratch or start with a different algorithm entirely.

I’ll just do the math instead. :slight_smile: Just looking at image 3… the longest run of black (vertically) seems to be 65px… which would take 11 bits to encode (5 for the size, then 6 to encode the value). So to escape a run of grey we’d need a 6 bit intro (we’re using 6 0s in a row as our escape sequence since no run is that long), followed by an encoded length number. You’d assume a minimum length of 6 or 7… so the length number you encoded would the additive run length, not absolute.

Example:

escape,length
000000,1 - 1 + 6 = 7 grey/hatch
000000,010 - 2 + 6 = 8 grey/hatch
000000,011 - 3 + 6 = 9 grey/hatch
etc

There are two runs of 23-24 length grey… so those would get encoded as:

000000,000010010,1 = 18 + 6 = 24 grey/hatch, next is white
000000,000010001,0 = 17 + 6 = 23 grey/hatch, next is black
etc.

16 bits to encode 23/24 bits of data. That’s a win. 0.666 ratio. But when all is said and done I think we’d be talking a few bytes of savings for something like Image 3. The real win would be if your image had a background hatch or something.

This is with elias gamma encoding. ArdBitmap seems to be doing just that but reverses the role of the 1 and 0 in the encoding process. So if you had several long runs of “grey” 10+ pixels long or so you’d start to see this payoff. The decoder would grown slightly in size but shouldn’t be too bad.

Edit: Actually you might need one bit after to tell it which color to go back to (black or white) before it picks up the normal Elias Gamma encoding again.


(Josh Goebel) #26

Could you elaborate on that?


(Ignacio Viña) #27

I mean the direction to scan the bits(pixels) inside every byte of the image array.

This is a sketch I did in the past about the algorithm. I hope it helps.


(Josh Goebel) #28

So zig mode switches the scanning order every byte? What cases is that trying to optimize for?


(Ignacio Viña) #29

Zig-zag mode works better a lot of times because the last bit (pixel) of each byte is adjacent to the first bit of the next byte


(Josh Goebel) #30

Oh, interesting. I think I know what you mean (about how the actual hardware works). Just seems like more of a decoding concern. I think the encoder would most often do best with RLE in “visual order” and then the decoder is responsible for getting the bits in the correct order for display.


(Simon) #31

Oh … I had this idea that zig zag might read the pixels diagonally and therefore pick up on hatching or dithering as one continuous run of colour.


(Josh Goebel) #32

Oh, I see… and does it typically help?


(Simon) #33

Well I don’t know … I guess if your image had a lot of cross-hatching it would. For other graphics it may improve or reduce the compression depending on the amount of vertical or horizontal lines in the image.


(Josh Goebel) #34

AFAIK the algorithm only works vertically so it could totally miss optimization opportunities that only presented themselves horizontally. Really to get the best compression you’d want to do a 90 degree rotation and test the compression there as well and then save whichever compressed better.