QOI - Interesting new lossless image compression algorithm

[Uncwilly]

I ran across this video which talks about a very recent image compression algorithm (QOI)
https://youtu.be/EFUYNoFRHQI?t=1410
The video is mainly about PNG, but the section that I linked to is about how QOI can produce similar lossless compression and do so about 20 to 50 times faster.

[retina]

I all for faster processing, and I like the idea of going back to basics and exploiting simplicity. So good job to the QOI dev.

If it was for video I can see the smaller time factor being a huge advantage. Is there really a big time bottleneck for still image compressing?

[Uncwilly]

Originally Posted by retina

Is there really a big time bottleneck for still image compressing?

I foresee that it might be useful in applications where power or processor time is limited. For example on a spacecraft. Power is a big factor. Also time can be a factor during imaging. If you can process the image about as fast as you can read the sensor, you can compress on the fly and store more images in the same space. Or if you can shoot a picture, compress, and shoot the next target faster, you can build a mosaic in less time, giving you more time for more science.

[LaurV]

"Electric" power is not scarce, on a spaceship. It is plenty. Solar, atomic (thermal), etc.

"Propulsion" power is scarce. There is enough power to drive the computers, but unfortunately this can't be used to move the ship, mostly to rotate it in place (gyroscopes and fly wheels). But to move it, the actual tech is still to throw something, or somebody back...

On topic: The compression stuff is not new, mathematical model is from the 70's or so, and I used similar methods long time ago. A pH Controller for aquarium hobbyists I personally developed 8-9 years ago (which still sells, and it is a good product, if you have one, you can see my name there if you know what buttons to touch, and when) stores the bitmaps EXACTLY in the way described! (plus additional tricks, because only ONE bitmap has 320x240x3 bytes when uncompressed, i.e. about 230kB, and the WHOLE available flash memory in that controller, i.e. for code, data, images, tables for pH and temperature compensation, etc, is just 128kB ). The customer provided bitmaps with "gradients" (water, shades, etc) to be shown in different cases during the normal function of the device, error states, etc, and when you see color gradients, the "difference to former pixels" comes to mind immediately, when you try to compress it in such a way to be able to decompress in just 2 or 4 KILOBYTES of RAM that the MCU has (i.e. you can not use Lempel-Ziv, Roshal, or large dictionaries - plus, careful with the copyrights!). Note that I compressed all those pictures in about 60k, while the available tools in the computer (non-lossless jpg compression) would not be able to make them shorter than ~40k total, so my performance was unexpectedly good. The compression was done in the computer, and included many hours of trials and image changes (to make the gradients manageable), so it was not "lossless" compression, I had to change the pictures to make them more compressible. The device has only to decompress them when it displays them. But the way they are compressed, includes the modes described in the QOI video.

[Uncwilly]

Originally Posted by LaurV

"Electric" power is not scarce, on a spaceship. It is plenty. Solar, atomic (thermal), etc.

Electric power is a thing. On Mars the Insight mission is solar powered and they are going to have to choose which instruments to shut down because the solar panels are getting covered by dust. Lack of power is what killed Spirit and Opportunity. Voyager is RTG powered and the camera system was the first to be turned off. Power management is real for missions. The Ingenuity helicopter can only fly so much, then recharge before it send data to the rover. Even the atomic powered rovers have to limit what they are doing because of electrical power.

The compression was done in the computer, and included many hours of trials and image changes (to make the gradients manageable), so it was not "lossless" compression, I had to change the pictures to make them more compressible. The device has only to decompress them when it displays them. But the way they are compressed, includes the modes described in the QOI video.

So, a bespoke solution for a limited data set where human time is expendable can come up with high compression. That is not news. You did it one off. Why not share the methodology so we all could have benefited from it over the years?

[LaurV]

Originally Posted by Uncwilly

So, a bespoke solution for a limited data set where human time is expendable can come up with high compression. That is not news. You did it one off. Why not share the methodology so we all could have benefited from it over the years?

Indeed, a limited set of data, which I still had to "arrange". I mean, the compression effectively was lossless, but the images were not what the customer provided, they were "touched" at pixel level, to make them more compressible, and still looking as much as possible nice, and as much as possible the same with the images the customer provided. In this respects, even if the compression was lossless, the initial information (provided by the customer) is lost by editing. I never claimed else, and never claimed that is "news". Read again.

OTOH, in about 40 years of playing with keyboards, I never needed a method to "compress fast". But this of course, may be due to my particular activity line, and, not in the last case, the age. Long time ago we stored files on floppies, and the storage was extremely limited. Also, sending data was slow, like 9600 bauds modems, etc (I have seen the times of the 2400 bauds, but at the time I wasn't programming anything), so there was a "big" requirement to compress data well, i.e. reduce the size of the data as much as possible, without losing bits. I remember spending hours with early versions of LZEXE, RAR, etc, to fit files on floppies (even with "extended" format - we had some tools that could format 1.44 floppies to larger capacity, like 1.6 or 1.8, or so, I don't remember exact). We would "xor" files with other strings and/or cut them in pieces and re-pack them many times with available tools to save some kilobytes, and then boast to friends, haha. Stupid kids. I made my first compression program years later.

More recently, moving to "production", and "microcontrollers", the requirement was to store the available data (image, sound, etc), in very limited memory available (kilobytes), and to be able to decompress it fast when requested (like to show it on screen, or to play an alarm warning sound, etc), sometimes using only tens or hundreds of bytes available RAM. Good luck to decompress jpg or png in 200 bytes of RAM. Using a smaller, cheaper MCU in the schematic, 50 cents instead of 3-dollars (for one with more memory and resources) would make the bosses/customers happy and (rarely) result in small financial gains (bonuses, etc). Think about producing 100k or 500k, or more pieces...

But to compress the data, nobody cared, in my line of job, I mean, I could use the company's severs to crunch (cook/prepare) the data for hours, haha.

About making the algorithms available, I never thought about keeping them secret. I would boast about them on all the web if they would have any worth and if customers would allow publishing things about their products. I always considered I only did few tricks, of which I was happy for a while, not a big deal, not something to interest somebody so much. I have made occasionally products in sensoric industries from which the customers made patents later, but I never applied by myself for such a patent; however, I have patented some shit involuntarily because other people put my name on the paper but I never made any money from any patent. I am for "open" stuff.

[M344587487]

Surreal seeing a separate niche interest of mine overlap here. QOI boils down to being a bytewise per-pixel encoder with half a dozen ops:

• RLE
• Indexing
• Diff from previous pixel ops
• Fallback to storing the pixel as-is

Its simplicity comes from reading each pixel once so it's streamable, the reference for the diff ops being the previous pixel, and the index being simple and small. Bytewise means a speedy implementation is trivial and a bonus benefit is that an encoded file is pretty well aligned so is still compressible by a generic compressor.

Originally Posted by Uncwilly

I foresee that it might be useful in applications where power or processor time is limited. For example on a spacecraft. Power is a big factor. Also time can be a factor during imaging. If you can process the image about as fast as you can read the sensor, you can compress on the fly and store more images in the same space. Or if you can shoot a picture, compress, and shoot the next target faster, you can build a mosaic in less time, giving you more time for more science.

QOI is a good proof of concept but IMO (not to take anything away from it) it didn't have enough time in the oven to hit the (an) optimal average case, which is a shame as it's become pretty widely supported in libraries that deal with multiple image formats. Within the family of QOI variants (encodings that are QOI with tweaks, retaining fixed, bytewise, streaming and a handful of fixed op characteristics) there exist encodings which are more efficient space-wise with only slight relative downsides. The main issue is inefficient use of opcode space, RLE uses nearly 1/4 of the available opcodes which is far too much (on average, there are outliers), same for (to a lesser degree in general) indexing using 1/4 of the opcode space. There is also no diff op for RGBA so certain types of RGBA image (with complex alpha) perform poorly, but this is more of a design decision as most images do not fit in this category. Finally using the previous pixel as a reference is simple but inefficient, if instead the average of the previous pixel and pixel above were used (which is still simple) there is a noteworthy efficiency increase for little more than the cost of an extra addition and shift each iteration.

Going beyond the average case there's a number of modifications to the fixed bitsream format that can be done to specialise for a particular use case:

• Adding RGBA diff ops if the expected input is RGBA with complex alpha
• Adding more diff ops in general to increase granularity, a bytewise encoding means there are many available op+data lengths and fleshing them out increases space efficiency at the expense of encode time (extra ops to check against)
• Tweaking RLE and index sizes to better fit expected input
• Getting rid of index ops entirely if this is used as a preprocessor to a compressor. Index ops actually hurt overall efficiency as it feeds the compressor essentially garbage, and the preprocessor is taking longer too thanks to lookups for the indexing
• Eliminate alpha entirely if input is purely RGB
• Eliminating RLE and indexing entirely eliminates all but local context, a much simpler faster encoder for its own sake or to enable parallel processing

That's why I think QOI is interesting more as a proof of concept than THE format to use (again, unless interoperability or library support is important). For specialist applications where compute resources truly are tight you'd likely use a specialist or even generic variant that better fits available resources. The resources to transmit an extra 10% of data from mars are likely much more valuable than the meager extra resources needed to compress the data that much better.

Originally Posted by retina

I all for faster processing, and I like the idea of going back to basics and exploiting simplicity. So good job to the QOI dev.

If it was for video I can see the smaller time factor being a huge advantage. Is there really a big time bottleneck for still image compressing?

Lossless video is a potential application with some adaptations but is unlikely to be as efficient for a few reasons. One of the key things that makes QOI as efficient as it is for images is the LUMA op, which essentially gives more bits to the green channel and represents blue and red in relation to green (aka in result it's a poor mans lossless RGB to YCbCr-like transformation). Most video is YCbCr so the transformation has already been done by default. Another reason is that a lot of lossless video, even good chunks of source material, are 4:2:0. Half of the data is thrown away (3/4 of Cb and 3/4 of Cr) which doesn't fit well with QOI's per-pixel design. There's probably a reasonable design that encodes per 4x2 block (or whatever is needed to neatly cover the different popular subsampling types) but AFAIK no one's come up with one publically. If we ignore/assume subsampling and transformation is solved, a QOI-like could easily be used to make a simple I-frame-only lossless format. Certain things like index context (and entropy coding context if used as an additional layer) could be retained over multiple frames, a chunk of frames where such context is retained could be considered to be an I frame followed by P frames. Beyond that I don't think much can be done without going beyond the scope of "simple" or "qoi-like", but it's open to interpretation.