23 ms·

QOI: Lossless Image Compression in O(n) Time

• formerly_proven 5y ago
  This is pretty neat. A lot like the filtering done in PNG, just without slapping zlib on the result. As far as SIMD goes, I agree with the author and don't see much potential, as instructions are variable-length and most instructions encode deltas. It's probably quite close to optimal by just letting the CPU figure it out on the micro-level. If each line were encoded independently they could be en- and decoded in parallel (once you add a skip instruction to tell where the next line starts, this does preclude streaming of intra-line output though). The hit to compression ratio should be small as long as images are wide enough for the color buffer reset to not matter.
• junon 5y ago
  To answer the author's question: No, SIMD would not help with this. This is neat. I wonder if the author would be willing to write a Kaitai Struct definition for it. Something else interesting: QOI is 1,2,2 letters off from PNG. I'm quite certain this is an accident but it's interesting nonetheless.
  • jiggawatts 5y ago
    I suspect SIMD would help with the encoding. The lookup table is small enough to fit into 8 AVX2 registers, so instead of hashing, you could use direct lookup, which would improve compression ratio further (a little bit).
    • junon 5y ago
      Yes encoding might benefit of course, I was more considering decoding speed I suppose.
      • jiggawatts 5y ago
        There are some clever tricks that can be pulled with the latest instructions sets like AVX-512. The registers are huge and the instructions available are so varied that there are clever ways to use them in "off label" ways to implement lookup tables and bit-level parsers.
        • junon 5y ago
          AVX-512 is deprecated and will be removed from future chips, so that's probably not as useful as one might think.
          • jiggawatts 5y ago
            I doubt that. What would be hilarious is if AMD's upcoming Zen 4 supported it consistently, but not all Intel CPU models did.
    • Const-me 5y ago
      > The lookup table is small enough to fit into 8 AVX2 registers Indeed. > so instead of hashing, you could use direct lookup However, I don’t think that part gonna work. See the code using that table: https://github.com/phoboslab/qoi/blob/master/qoi.h#L324-L328 https://github.com/phoboslab/qoi/blob/master/qoi.h#L324-L328 SIMD registers aren’t indexable (at least not on AMD64), the register needs to be known to the compiler. Lanes within each register aren’t indexable either. The insert and extract instructions are encoding lane index in the code. There’re workarounds for this one, like abusing vpshufb or vpermd, but with that amount of overhead I doubt SIMD will deliver any profit at all.
      • deleted 5y ago
        [deleted]
• haxiomic 5y ago
  This is impressive, I was curious if it was just better on simpler images with many duplicate pixels but it's nice to see it working well with photography too e.g. https://phoboslab.org/files/qoibench/images/wallpaper/EwZDbLoWQAEskRq.png https://phoboslab.org/files/qoibench/images/wallpaper/EwZDbL... decode ms encode ms decode mpps encode mpps size kb libpng: 148.4 3995.5 55.88 2.08 12223 stbi: 161.0 1858.3 51.50 4.46 19199 qoi: 60.8 95.6 136.49 86.78 12868 I'm interested if there's a standardized benchmark used in the academic literature this could be tested against In any case the results are impressive enough that this will 100% be used in projects I work on! Many thanks to the author for their work <3
  • orlp 5y ago
    When I download that PNG file it is 10785 KB. If I re-encode it using FLIF 0.4 (to my knowledge still the best off-the-shelf lossless image compression) it is 7368 KB. That's 57% of the size of qoi, quite a lot smaller. You pay for it in encode/decode time though.
    • fastball 5y ago
      Interestingly I actually managed to shave 400kb off of that PNG by just running it through some PNG optimizers. Not great savings but were still some to be had!
    • minus7 5y ago
      FLIF has been superseded[1] by JPEG XL, which, in my very limited testing, performed better (speed and compression-wise; libjxl) than FLIF. Interesting though that FLIF 0.4 was released 3 days ago. I haven't checked out that new release (and won't), but the previous one wasn't great code and was a pain to use (ended up using its CLI instead of the lib). We ended up going back to PNG because of interoperability and speed. I haven't looked at libjxl's API yet. Edit: 8605KB in 11.5s with libjxl, so it's not actually better than FLIF 0.4 (7368KB in 23.9s) [1]: https://flif.info/#update https://flif.info/#update
• mattashii 5y ago
  Nice stuff! But I was confused by the following: QOI_RUN8 { u8 tag : 3; // b010 ... QOI_RUN16 { u8 tag : 3; // b011 I think there might be a bug lurking in those tag values. EDIT: Wow, I'm blind. Those 3s were bits consumed by the tag, not tag values...
  • formerly_proven 5y ago
    The :3 means how wide the field is. Instructions are byte-aligned, but bit-packed.
• j-pb 5y ago
  > To keep things O(n) when encoding, there's only one lookup into this array. The lookup position is determined by a “hash” of the rgba value (really just r^g^b^a). Is a bit imprecise. The algorithm would still be O(n) even with a linear search through the "seen pixel array", as it is bounded by 64 length and therefore a constant factor that gets eaten by the Big-O notation. Because of this hash the algorythm seems to do something else than first described though. Instead of "a running array of the 64 pixels it previously encountered", it's actually the previous 64 pixel _values_ previously encountered, which allows for much bigger jumpback. By deterministically computing this array during execution it itself seems to act as a kind of compressed jumpback table, allowing for approximated arbitrary jumpback with just 6 bit. Quite impressive! Edit: I think there might be an interesting tweak that could increase the effectiveness of the hashing technique used. If one were to walk and store the pixels in a Z-Curve order, the runtime would stay the same but the locality of the color value pool, might be increased.
  • tda 5y ago
    I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format
    • mkl 5y ago
      https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve Related to this method, it's sometimes used for texture mapping on GPUs.
    • j-pb 5y ago
      After making the edit, I saw that someone made the same suggestion on twitter! Hilbert curves have slightly better locality than Z-curves, but Z-Curves are trivial to produce. If you have a N dimensional space over unsigned integers, then you can place each point on a one dimensional Z-Curve by interleaving their bits into a new integer. So for any point (X, Y) in the X-Y coordinates of an image the Z-Curve coordinate is X_1,Y_1,X_2,Y_2... Which can be achieved with a bunch of bit shifts and masks, (or a bunch of wires if you happen to use it in an FPGA ^^')
• janandonly 5y ago
  Waawh, one would think (certainly, I personally thought) that all the _simple_ compression algorithms would have been discovered and build by now...
  • rowanG077 5y ago
    Interesting I have the opposite view. From intuition I would think there is an unbounded set of simple compression algorithms. You can probably make much more effective simple compression algorithms by making basic assumptions about the type of image.
    • EmilioMartinez 5y ago
      This is patently so. Taken to absurd proportions, you can compress a specific rendition of the Mona Lisa with just one bit. 1 means Mona, and 0 is undefined behaviour.
      • FooBarBizBazz 5y ago
        Taking this a step further: 0 means that all subsequent bits contain an arbitrary PNG. Now your algorithm encodes any image, and still does Mona Lisa in one bit.
        • selcuka 5y ago
          It's also almost as effective as PNG (plus one bit) for non-Mona Lisa images.
      • mijoharas 5y ago
        Are we about to talk about Kolmolgorov complexity? you're damn right that we're about to talk about Kolmolgorov complexity! :) [0] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
  • vintermann 5y ago
    Well, this is a combination of simple approaches which have all been used before, though put together in a nice way. And it's not benchmarked against modern formats like lossless webp or jpeg-xl.
• lifthrasiir 5y ago
  tl;dr: 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats) 010xxxxx - repeat the last pixel x+1 times 011xxxxx xxxxxxxx - repeat the last pixel x+33 times 10rrggbb - copy the last pixel and adjust RGB by (r-1, g-1, b-1) 110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7) 1110rrrr rgggggbb bbbaaaaa - copy the last pixel and adjust RGBA by (r-15, g-15, b-15, a-15) 1111RGBA [rrrrrrrr] [gggggggg] [bbbbbbbb] [aaaaaaaa] - copy the last pixel and replace RGBA if each bit flag is set So it is essentially the PNG filter limited by Sub, but offers better delta coding and a larger history window. My guess is that it might not work well if the image has a strong vertical gradient (which would need the vertical context), but nevertheless it's pretty impressive that this simple coding is not as inefficient at all.
  • mkl 5y ago
    You might be able to do better compression by traversing the pixels in Hilbert [1] order or Z [2] order, to take into account vertical neighbours as well as horizontal. It might cost time or space though, as you couldn't stream the pixels through it anymore - you'd need them all in memory. [1] https://en.wikipedia.org/wiki/Hilbert_curve https://en.wikipedia.org/wiki/Hilbert_curve [2] https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
    • nightcracker 5y ago
      You could still stream the pixels, you'd just have to stream them in Z order. This may seem pedantic, but this applies to any mismatch between the order in which you store pixels and the order in which the format stores pixels. E.g. some file formats may be row-major, others column-major, some block-based (like JPEG) or a fancy interleaving scheme (like Adam7). Some might store the channels interleaved, others separate the channels. If any of these choices doesn't match the desired output format, it breaks streaming.
      • akx 5y ago
        And formats like BMP are stored upside down...
• pantulis 5y ago
  This is as cool as it gets. I have a honest question about the source code, a lot of time since I coded anything meaningful in C, but I remember the header files did not have that much code on it, while here I see most of the code is in the header file. Why is this the case? Inline compilation? What are the advantages?
  • ur-whale 5y ago
    Packing the entire library in a header file is a somewhat recent and much welcome trend. See for example: https://github.com/nothings/stb https://github.com/nothings/stb https://github.com/nothings/single_file_libs https://github.com/nothings/single_file_libs
    • mkl 5y ago
      I wouldn't call it recent. Boost has been doing it since it was started in the late 1990s.
      • ChrisMarshallNY 5y ago
        The original C++ templates used to be entirely contained in the headers. I assume that is no longer the case, but it has been a long time, since I wrote C++. When I was writing template SDKs, the headers were pretty much the entirety of the library.
      • flohofwoe 5y ago
        Boost or C++ stdlib headers are different than STB-style single-file-libraries though in that the implementation code is inline and needs to be parsed each time the header is included.
      • tommiegannert 5y ago
        Boost did it because C++ template definitions must be in headers. That seems unrelated to this idea that C code using it is equally reasonable. That's a developer choice.
  • 5y ago
• Ono-Sendai 5y ago
  Very cool. Typo: "I barely understand how Huffman Coding and DTC works" I guess you mean DCT? (discrete cosine transform) One other thought: To make it so that compression and decompression can be multithreaded, you might want to 'reset' the stream every N rows. (i.e. break any RLE runs, start from a colour literal). This would allow a bunch of threads to start at different places in the image, in parallel. There would be some small cost to compression ratio but might be worth it.
  • phoboslab 5y ago
    Thanks, fixed! I'll probably investigate "resetting" the stream to allow for multithreaded en-/decode when I try to roll this into a video codec.
    • mkl 5y ago
      Even better might be breaking it into tiles, so you get some vertical locality happening as well as horizontal. It would be interesting to know which strategy is used for each pixel. Have you tried making maps of that with four different colours? Particularly interesting would be how much the cache is used and also how often it replaces a colour that it could have used later. Maybe there's a better colour hash. BTW you might want to change "(really just r^g^b^a)" to "(really just (r^g^b^a)%64)".
      • iainmerrick 5y ago
        I really like the trick of caching previously-seen pixels by value rather than position. Very nifty! I was thinking this would combine well with progressive rendering (i.e. store pixels in mipmap-style order) so the cache is warmed up with spread of pixels across the image rather than just scanline order. That doesn’t make it parallelizable in the way tiling does, though, hmm. Another tweak that would probably help is having the file specify a rotation (or even a full mapping table) for each component of the hash, so a clever encoder can pick values that minimise collisions. (A fast encoder can just use all-zeroes to get the same behaviour as before.)
    • 5y ago
• dexen 5y ago
  I am in awe with how the post neatly interleaves the why and the how. Having recently implemented L4 decompressor (itself a rather reasonable and "lightweight" standard), I like the QOI even better. Hoping to see the video decoder author mentions as possibility!
• jiggawatts 5y ago
  I know you don't like "design by committee" and overly complex formats. Also, the compression algorithm itself is somewhat independent of the "container format" that it's used with. However, if I may make a suggestion: If you do end up rolling your own container format for any reason, always include a way to store the colour space of the image! Treating RGB images as arrays of bytes without further tags is like treating char* as "text" without specifying the code page. It could be UTF8. Or Latin-1. Or something else. You don't know. Other people don't know. There's often no way to tell. Similarly with colour spaces: sRGB, Display P3, and Adobe RGB are just close enough to be easily confused, but end up looking subtly wrong if mixed up.
  • cyber_kinetist 5y ago
    I think the author's intending to use this only as a data packing format (ex. for app/game development) and not a general-purpose exchange format. If all you want to do is pack image/texture data for your game then I totally get why they assume RGBA8 storage and leave out metadata such as color space information.
    • pornel 5y ago
      I know games tend to assume color spaces from context, and do other hacky things like reusing alpha for height maps or RGB for vector coordinates. But this approach is a source of endless conflict with image processing tooling, because nobody except the game author knows what the channels mean. Game developers keep complaining about image processing tools doing anything other than bytes-in-bytes-out on that data (e.g. clearing "unused" alpha or treating RGB as human-perceptible colors), because it breaks the unstated assumptions.
      • dv_dt 5y ago
        Yup embed enough metadata so you can actually nicely automate/integrate doing the right thing with tooling.
    • zcw100 5y ago
      I wonder if color profiles will be important to images used for AI. Right now, as far as I can tell, people generally ignore details like that but I wonder if someday people are going to say, "oh wait, we've been completely ignoring color profiles. We could have been using that" or "we didn't realize how ignoring that messed things up"
• giorgioz 5y ago
  >I can almost picture the meeting of the Moving Picture Experts Group where some random suit demanded there to be a way to indicate a video stream is copyrighted. And thus, the copyright bit flag made its way into the standard and successfully STOPPED MOVIE PIRACY BEFORE IT EVEN BEGAN. This bit made me laugh out loud :D
  • ur-whale 5y ago
    > This bit made me laugh out loud :D Yeah, it's funny, until you actually go read the MPEG spec. documentation. Then any and all inklings of laughter will very quickly evaporate.
    • h4kor 5y ago
      What does it say about these bits? I'm currently tinkering around with mp3s and wondered how many "useless" bits are in each frame. I wonder if they are ever used to trace distributors of pirated music, similar to yellow dots in printers.
      • gnramires 5y ago
        He might be referring to the hundreds of pages (and very complicated implementations, usually of encoders) video formats have. People think of technology as a straight line moving forward. But it's perhaps better to imagine like species in nature. It's just everything getting bigger. The smallest ant or bacteria evolves to better adapt to its niche, as the largest elephant or whale will develop adaptations (sometimes getting physically larger, depending on the environmental changes). The rule is that many scales have a role or niche. I think technology is similar.
  • barrkel 5y ago
    I rather wonder if things like this are used to encode a proof of intent. If something is marked as copyrighted, it may be trivial to remove the mark, but at least you had to remove the mark, and that's evidence of intent rather than ignorance.
• zosoworld 5y ago
  I'm wondering how scalable would this be for hyperspectral images, with 25 channels for example. I'm guessing it's just repeating the processing for RGB channels but for 25?
  • jameshart 5y ago
    Very much the kind of expert group design-by-committee type of requirement that this simple compression scheme was designed not to handle. Since this scheme works primarily on exact cross-channel pixel matches, no. No it won’t work well for 25 channel images. Which is a good thing. Most people are not trying to encode 25 channel hyperspectral data and if they are they can use their own format designed well for that purpose (or a committee-derived format that handles it adequately). Or they can split the 25 channels across 7 4 channel images and encode them using this.
    • zosoworld 5y ago
      I did not try to imply that this should contemplate the other use case, but I was wondering whether the compression percentage would scale up with more channels that might not be related in the same way RGB are (as in luminance, for example). This effort really makes me want to try to do something similar for the other use case, and see how well it fares compared to the convoluted standards that are used for this topic. Thank you for your insight!
• pedrocr 5y ago
  These kinds of formats have been somewhat explored by camera makers for their raw formats. Since the computing resources in the cameras can be quite limited there are a few formats that try to occupy this space of simplicity with still some tricks for compression. Samsung's various SRW encodings remind me most of this: https://github.com/pedrocr/rawloader/blob/a59bb78d156277781ad404d0c783edc4a0abce3d/src/decoders/srw.rs https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a...
  • formerly_proven 5y ago
    Lossy RAW is sometimes even simpler than that. E.g. Nikon's old compression was just remapping values in a log-like fashion, which reduced resolution in the brightest few stops[1] to save a few bits per sample. [1] Perception is pretty logarithmic as usual, so for a 14-bit readout, half the values represent the brightest stop and a little bit, the other half holds the other 12+ stops.
    • pedrocr 5y ago
      The simplest form is just to pack 10 or 12 bit values. There's all kinds of variations of that: https://github.com/pedrocr/rawloader/blob/a59bb78d156277781ad404d0c783edc4a0abce3d/src/decoders/packed.rs https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a... There are a few formats that use a curve and less bits. They do become lossy and doing dithering on decompress is useful to avoid banding. The Nikon one you mention was only used very early and is decoded by decode_8bit_wtable() in that file. It's just looking up the 8 bit value in the table and then adding some randomness to prevent the banding.
  • IshKebab 5y ago
    Yeah I don't think there are any new ideas here. RLE, differential encoding and dictionary encoding have all existed for decades. The interesting thing is that it comes close to PNG.
• nightcracker 5y ago
  QOI_DIFF24 { u8 tag : 4; // b1110 u8 dr : 5; // 5-bit red channel difference: -15..16 u8 dg : 5; // 5-bit green channel difference: -15..16 u8 db : 5; // 5-bit blue channel difference: -15..16 u8 da : 5; // 5-bit alpha channel difference: -15..16 } It bothers me more than it should that the 5-bit signed differences aren't -16..15 matching two's complement but -15..16 instead.
  • selcuka 5y ago
    Who knows? Maybe it's the result of a heuristic that achieves a slightly better compression ratio.
  • hoseja 5y ago
    Yes, this is baffling. Wonder if the format could still be amended to fix this?
  • phoboslab 5y ago
    I should probably fix that. Is there a clever way to unpack a 5bit signed int other than treating it as unsigned and subtracting 16?
    • adgjlsfhk1 5y ago
      That seems easiest.
      • wizzwizz4 5y ago
        Especially since your compiler will make it a super magical optimised version.
    • benlivengood 5y ago
      You'll have to shift the values around anyway, so: int intermediate = byte_or_word << N; // N chosen to put the five bits in the highest positions in the int. int value = intermediate >> bits_per_int - 5; Instead of masking rely on arithmetic shift right to keep the sign bit.
• ur-whale 5y ago
  Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
  • WithinReason 5y ago
    All lossless compression algos do badly on noisy images
  • deleted 5y ago
    [deleted]
  • EmilioMartinez 5y ago
    Notably, pixel similarity along a particular order. If I understood correctly something like a vertical rainbow would compress significantly different than the same picture rotated.
  • makapuf 5y ago
    Noisy but around recurring or slighly different pixels would achieve a 1:4 compression rate
• KaiserPro 5y ago
  > The basic ideas for video compression in MPEG are ingenious, even more so for 1993, but the resulting file format is an abomination. can confirm. Although the worst part is the documentation is in engineering english, so its quite hard to understand. MPEG2 is actually not as bad as you'd imagine. MPEG4 is.
• willvarfar 5y ago
  Yummy :) Makes me want to experiment too. Is there some easy corpus with nice categorization of types (drawing, painting, photo, comic, clip art etc) so we can all easily compare?
• wongarsu 5y ago
  Is it just me, or is the compression algorithm not really less than the one in PNG? I will grant the author that if you don't need features like support for color spaces, different bit depths or interlacing you can skip the entire container format. But for reference this is the core part of png: For each scanline write one byte for the chosen filter method, then $width pixels. There are five filter types. In type 0, write the pixels unmodified. In type 1, write the difference to the previous pixel. In type 2, write the difference to the above pixel. In type 3, write the difference to the average of the above and left pixel. In type 4, write the difference to the Paeth predictor (a simple function calculated from the above, left and left above pixel). Then compress everything with deflate. Obviously by modern standards that isn't performant, not least because deflate sucks by modern standards. But it's simple, can be implemented in a couple lines of C (if you pull in deflate as dependency), and if you don't do exhaustive searches for the best compression it can certainly run in O(n)
  • gpvos 5y ago
    The 64-pixel lookback makes it a bit similar to LZ-style compression like Deflate, but the latter is not O(n) because it can recognize multi-pixel sequences. QOI is just a slightly beefed up run-length encoding.
  • deleted 5y ago
    [deleted]
• londons_explore 5y ago
  This is a great project, but personally I feel that there are lots of uses for uncompressed images (ie. random access, ready to render straight away), and lots of uses for well compressed lossless, but little use for 'slightly compressed' images. The normal argument for 'slightly compressed' images is that they can be decompressed with very few CPU cycles, but the reality is that with modern platforms lossless image en/decoding is done in hardware and therefore pretty much 'free', as long as you pick lossless h264, lossless webp or lossless hevc. All of those things will also give much smaller file sizes. In the few places where hardware decode isn't a thing (eg. the memory-constrained 8 bit microcontroller decoding the boot screen for your IoT toaster), there usually isn't a need for losslessness.
  • iainmerrick 5y ago
    “Slightly compressed” is heavily used in 3D graphics -- see ETC2, DXT, etc. It’s useful because the size savings apply in memory, because decompression is so cheap it can be done on the fly. It has to be lossy because you want a guaranteed fixed-rate compression ratio (eg 4x) and there’s no way to do that losslessly.
• carrolldunham 5y ago
  Could a hash collision make it inexact? so not guaranteed lossless?
  • phoboslab 5y ago
    No, the encoder checks if the color at the hashed value really matches before storing the QOI_INDEX. There's probably better ways to hash it, but this just seemed "good enough".
  • deleted 5y ago
    [deleted]
• lam0x86 5y ago
  Looks like PCX on steroids
• dbrgn 5y ago
  Looks nice! Did you try fuzzing your implementation (e.g. with AFL++ or libfuzzer)? Codecs and especially decoders written in C that handle untrusted binary data are quite worthwhile targets for fuzzing.
• SkeuomorphicBee 5y ago
  Really cool encoding, it is a bit incredible that such simple rules can archive such good results. It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet). Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I have yet another different vertical locality suggestion to try: While encoding/decoding keep a ring buffer the size of one full line of the image, storing each encoded/decoded bit there. Then add a variation of method #3 (The difference to the previous pixel) which instead encodes the difference to the pixel above the current (the last pixel from the ring buffer). Maybe, due to the limited "tag" space it would not be worth it to implement it for DIFF8, but only for DIFF16 (taking one bit from red to the additional tag bit) and DIFF24 (I'm not sure which bit I would steal there). Edit: Also, when thinking about video encoding in the future you may want to keep a ring buffer fitting the full last frame of video. And then temporal locality is probably even more important, so then you may want to change the tags to encode more commands relating to the pixel from the previous frame.
  • tda 5y ago
    nice idea, I think it is somewhat more in line with the keep it simple option, as I e.g. have no idea what a hilbert curve for an arbitrary size rectangle looks like. And you still get compression for x and y directions (though no run length encoding the vertical, perhaps a further addition). I quite like this approach of defining a few compression methods, see which one works best, and apply that one. I used a similar strategy for time series compression where I would take a chunk of data, apply z few different compression algorithms on it (RLE, delta RLE, etc) and just keep which ever one was smallest. Of course here it is done on a per pixels basis, and I used arbitrary size chunks. The latter is trivial to parallelize. Same could be applied here though, split the image in half and compress both parts independently
  • gfody 5y ago
    having done my own experiments with indexed pallets I suspect method #2 is responsible for most of the compression here. most photographs only have half a million distinct colors and it drops considerably as you focus in on an area. if you're willing to relax the single-pass requirement, partitioning the whole image by pallet similarly to how one encodes high-color images into multi-framed gifs can yield surprisingly good compression.
• blondin 5y ago
  this is so satisfying to see. kudos to developer!
• makapuf 5y ago
  Would be interesting to try to use it as is but in a lossy way
  • andrewla 5y ago
    Very much this -- it will unfortunately have a horizontal bias if done naively, but I've been exploring the space of doing lossy preprocessing to improve image compression, but the layered heuristics in png make this difficult. This format is simple enough that we have a number of approximation heuristics -- find the closest color in the last 64, use a smaller delta, or preserve one or two channel colors in the next pixel.
• sbrki 5y ago
  Very nice. Regarding the comments about complexity of existing formats - I agree, with the exception of PNG. In terms of complexity, QOI is very similar to PNG filtering phases, i.e. when you strip primary compression phase (Huffman coding) from PNG. Also, I admire how the author combined a lot of common and cool tricks into QOI: - Block tags form a sort of a prefix code, making it easy to differentiate block types with differing sizes - Look-back array is used (common trick from LZW family) - Delta-coding is used when storing pixel diffs - In the end, if nothing else works, full pixel value is written Also, the fact that everything is byte aligned is very appreciated. This is a breath of fresh air and really impressive how good performance (both processing and size reduction) this gets with so little (very readable!) C.
  • superjan 5y ago
    Traditional compression research usually prioritized compression ratio, so more images would fit on your floppy disks and were faster to download over 28.8k modems. It usually means increased complexity. Png has it’s own story as it’s #1 design goal was to avoid techniques that were patented at the time. So they combined a simple set of prepasses with zip/gzip compression. There were better techniques known at the time, but the idea was that combining simple, and known patent-free solutions was the safest way to achieve a free format.
    • BlueTemplar 5y ago
      The most important is probably the difference between lossy and lossless compression... (The GP-mentioned Bink is lossy ! Then he also for some reason uses a picture tending towards photo realistic which does NOT play well with lossless !)
      • superjan 5y ago
        Yeah there’s a difference in techniques used for lossy vs lossless. But my point was that in compression research, runtime performance was much less important than compression performance, that was no different for lossy compression.
• yboris 5y ago
  Obligatory comment about the new file format that's going to replace jpegs: JPEG XL https://jpegxl.info/ https://jpegxl.info/ It also has lossless setting (in addition to being better at compression when you want a lossy format).
  • sedatk 5y ago
    JPEG XL also claims to be better than modern formats like WebP, AVIF, and HEIC. https://cloudinary.com/blog/time_for_next_gen_codecs_to_dethrone_jpeg https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...
• adgjlsfhk1 5y ago
  Why not separate the format for RGB vs RGBA based on a header? Since images will never have both RGB and RGBA pixels, you would be able to get an extra few percent encoding by using different (and conflicting) tags for the two types of images. For example you could have QOI_COLOR_RGB which would use a 5 byte tag and QOI_DIFF24_RBG could store 7 bit differences for 2 colors and 6 bit differences for the other color. For RGBA, you could do something similar for the two tags that are RGB specific.
  • HanClinto 5y ago
    Or even based on a #define if one didn't want to check a bit flag every time you need to encode a full pixel. Would not be difficult to have two versions of the library -- one for RGB, and one for RGBA.
• tonmoy 5y ago
  I am not familiar with image encodings, but isn’t the idea of complexity relative? For example getting rid of Hoffman encoding and byte aligning everything may be less complex for computers, but when making energy and area efficient hardware, we may not care that much about some of these things?
  • selcuka 5y ago
    For a small number of operations, sure, but when you need to compress a million, or a billion images, the performance optimisations quickly add up.
• khitchdee 5y ago
  This algo would work well for computer generated synthetic images, not as well for scanned images.
  • ripdog 5y ago
    Which is why the author is positioning it as an alternative to PNG, not JPEG.
• nathias 5y ago
  Very cool.
• WaitWaitWha 5y ago
  I am going to be the fly in this ointment. I appreciate the premise to develop this, and the science that comes with it. I cannot tell if the author is writing in jest or serious when he is rude to the historical work that was done before him, yet relies on. It comes across as hubris with no floor to hold him up. Today's genius is often questioned and found to be a fool of tomorrow, and a bit of grace goes a long way.
  • kortex 5y ago
    Have you seen codecs? I've recently been exploring this space and there is not one corner of this universe that isn't a lurking Lovecraftian horror. Un-compressed formats like BMP are sane I guess but most of those are wrapped in crufty, sparsely documented container formats. Ogg is decent but even it takes quite the deep dive to even begin wrangling it.
• deleted 5y ago
  [deleted]
• stillicidious 5y ago
  > I want to preface this article by saying that I have no idea what I'm doing Instant hire!
• benlivengood 5y ago
  I wonder if the author tried making pixel diffs capable of using lookback. They'd be one byte longer but would possibly happen a lot more often than full pixel values. It's also reminiscent of the delta blocks from MPEG. If anything I would trade the 5-bit run for delta-from-lookup on a whim (the cases where the ratio between short runs vs. exact lookback is extreme seems like it might only happen for pinstripe patterns). I should probably implement the change and test it before posting...
  • adgjlsfhk1 5y ago
    The hard part here is figuring out which pixel to diff to. You would almost certainly have to look at all 64 pixels which would be a lot slower. That said, you can probably get noticably better compression from it.
    • benlivengood 5y ago
      I think O(log(M)) where M is the number of remembered pixels. Index them by their (R,G,B,A) quad and do a range lookup sequentially by pixel, since any valid pixels would be within the same range as earlier potential matches.
• st_goliath 5y ago
  Out of curiosity, I modified the benchmark program to simply toss the pixel data into lz4/lz4hc for comparison (patch file: https://paste.debian.net/1220663/ https://paste.debian.net/1220663/). I'm actually quite impressed how the resulting size is a little bit smaller than lz4hc (actually not even that far away from libpng), while the encoding speed is quite close to lz4, despite seemingly not having as many hacks and tweaks under the hood to get there. So the encoder is IMO doing amazingly well actually. However, the decoding speed of liblz4 is off by roughly an order of magnitude. But again, liblz4 probably benefits from decades of tweaking & tuning to get there. It would be interesting how much performance could be gotten out of the qoi decoder. Here are the totals I get for the "textures" benchmark samples: decode ms encode ms decode mpps encode mpps size kb libpng: 2.2 32.4 58.67 3.94 160 stbi: 2.1 17.0 61.50 7.49 228 qoi: 0.7 0.7 191.50 170.54 181 lz4: 0.1 0.6 1226.06 206.40 258 lz4hc: 0.1 70.9 1029.26 1.80 200 And for the "wallpaper" samples. The spreads seem to be a bit more in favor of qoi here: decode ms encode ms decode mpps encode mpps size kb libpng: 131.9 2287.1 66.63 3.84 8648 stbi: 147.5 1177.1 59.55 7.46 12468 qoi: 56.3 56.5 156.13 155.60 9981 lz4: 14.3 53.1 614.53 165.50 18019 lz4hc: 13.9 1901.7 630.94 4.62 12699
  • eisbaw 5y ago
    What about qoi followed by lz4?
  • willvarfar 5y ago
    I believe (from quick code inspection) that the symmetry in encode/decode performance for QOI is because it has to generate the hash-table on decode too. Normal fast encoders use some kind of hash table or search to find matches, but encode the offset of the match in the source rather than in the table. QOI is encoding the offset into the table, which gives much shorter offsets but means the decoder has to maintain the table too. (The slow PPM compressors etc do maintain the same table in both encoder and decoder, and have symmetrical encode/decode performance too. See http://www.mattmahoney.net/dc/text.html http://www.mattmahoney.net/dc/text.html) Its not really in the spirit of of QOI to add the complexity, but I'd imagine allowing the encoder to specify how big the hash table was would be only a small tweak, and encoding literal blocks instead of pixel-by-pixel will improve handling input that QOI can't compress better. I would be curious to know if planar helps or hinders. Perhaps even see what QOI makes of YUV etc. And I want to see 'heat maps' of encoded images, showing how cheap and expensive parts of them are, and which block type gets used. Yeah, going a bit beyond the spirit of QOI :D And from looking at the code I'm a bit confused how 3-channel is handled for literals because the alpha still looks like it gets encoded. Would have to walk through the code to understand that a bit better. Is it going to deref off the end of the source RGB image? Etc. (People interested in compression may be interested in the go-to forum for talking about it https://encode.su/threads/3753-QOI-(Quite-OK-Image-format)-lossless-image-compression-to-PNG-size https://encode.su/threads/3753-QOI-(Quite-OK-Image-format)-l...)
• eisbaw 5y ago
  I'd like to see this in xpra. Does anybody have an idea if QOI+lz4 would improve compression ratio further?
• rocqua 5y ago
  I immediately thought of a use-case for (a modified version of) this: raw compression in cameras. Currently Sony has two options. Uncompressed raw that is huge, or lossy compressed raw that is half the size. They probably chose those options because throughput when shooting quickly matters a lot, so something like PNG would slow down shooting too much. I imagine a blazingly fast halfway decent compression algorithm would be great. It might even speedup shooting by needing to write fewer bytes. But in general people taking star pictures will love having compression without it being lossy. For reference an uncompressed raw file for 44MP is about 90MB. That starts filling up drive space rather fast.
  • w-m 5y ago
    I don't think this method fits camera raws particularly well. The real world is noisy, so it becomes very unlikely that you would ever hit the two most compressible methods of QOI, (1) pixel value repeat or (2) index into one of the previous 64 pixels. QOI works really well for 8-bit screenshots, with lots of pixel-values repetitions. No such luck in noisy 14-bit real-world images. Also, this format was designed to be as simple as possible, and is byte-aligned, only handles 8-bit RGBA. You would need a different design for 12/14-bit RGB or RGBG (Bayer).
• wwalexander 5y ago
  Are there compression algorithms that take longer than O(n)? My impression is that even two-pass encoding is O(n) with a large constant factor in front of it, but I’ve never actually thought this much about it.
  • selcuka 5y ago
    Some LZ variants such as LZ77 and LZW are O(n), but LZH, for example, is O(n*logn) because of Huffman encoding. I agree that O(n) is not revolutionary, but the simplicity of this algorithm makes it faster to execute.
    • eutectic 5y ago
      Isn't the log factor only in the alphabet size?
• jiri 5y ago
  This code is nice for RGB, but what about YUV420 format? There should be even more efficient way to store image in YUV420 (takes half bytes than RGB 888), and most images (JPEGs, direct cameras output in Android etc) are already in YUV420. I wonder if auther has tried YUV420 already and failed for any reason ...
• kortex 5y ago
  Super cool work! I was also mucking around with codecs last week. I got some surprisingly good results from delta encoding each channel separately and then zstandard compression. Dirt simple, crazy fast. One trap to be aware of when profiling image codecs is not knowing the provenance of the test images. Many images will have gone through one or more quantization steps. This can lead to impressive compression ratios, but if you compare with the results on raw, unquantized imagery, it's less of a slam dunk. That said, PNG is a really low bar to clear, both in terms of speed and compression ratio. Even really image-naive compression algorithms tend to be within a factor of 2 in resulting compressed size. You tend to get diminishing returns. 10% vs 20% is twice as efficient, but starting with a 10MB file, 1 vs 2 MB file sizes isn't a huge delta. (yes I know there are domains where this matters, don't @ me).
  • simcop2387 5y ago
    > Super cool work! I was also mucking around with codecs last week. I got some surprisingly good results from delta encoding each channel separately and then zstandard compression. Dirt simple, crazy fast. My understanding is that this is one of the techniques that png uses (though not zstd) for doing it's xompression too. Along with I think some different strides down the image and some other stuff but I don't fully understand everything it tries. That's what optipng and friends play with for parameters to find the best settings for decomposing the image for compression. If you look at what jpeg and similar codecs do they nearly take a DC offset out of the image because that difference then greatly reduces the range of values you have to encode which means that you need fewer bits to do so. Combine that with range or arithmatic coding and you can get decent efficency for very little work. Then with lzw, zstd, etc. You can get lots of other patterns taken out and compressed. Lossy codecs try to take out the stuff we won't see with our eyes so that the set of values to be encoded need fewer bits and it'll also make more patterns appear that can be exploited too
    • kortex 5y ago
      Yeah, my technique was equivalent to filter mode 0 (the only mode), filter type 1 (sub pixel to the left). literally array.ravel().diff(prepend=0) in numpy. I think part of the reason png is so slow is that it empirically tests to find the best one. > Compression is further improved by choosing filter types adaptively on a line-by-line basis. I'd be curious to unpack a png and see the statistics of how much each kind is used.
• renonce 5y ago
  So it looks like the algorithm diffs neighbouring pixels, assume that the difference is likely to be small, and encodes the difference in 1, 2, 3 or 4 bytes. It does this without complex things like huffman trees and therefore got a major improvement in performance while approaching the compression ratio of zlib. That's interesting.
• bob1029 5y ago
  This is very impressive work. One thing I did recognize after my last trip into the rabbit hole - JPEG can be the fastest format by orders of magnitude if you are using an appropriate encoder. The project mentions 20x-50x speedups over PNG which are commendable, but once you throw LibJpegTurbo into the mix (it does use SIMD), you will find a substantially different equation on your hands. I can do 1080p 4:4:4 JPEG encodes in ~3ms on my workstation today. I am not saying you should always use jpeg (some people like to keep all their original pixels around), but if you want to go really really fast you should consider it. The latency is so low with this approach that I have been looking at the feasibility of building a streaming gaming platform around it. Current status of that effort is somewhere between "holy shit it actually works" and "maybe?"
  • bno1 5y ago
    Jpeg is not losses though
• dahart 5y ago
  This is pretty neat! The compression rates and encode/decode rates are impressive for such a simple rule set. > SIMD acceleration for QOI would also be cool but (from my very limited knowledge about some SIMD instructions on ARM), the format doesn't seem to be well suited for it. Maybe someone with a bit more experience can shed some light? I don’t know about SIMD encoding, but for decoding at least, the core problem is to make some unit of the image (pixels, scanlines, blocks, etc) independently addressable (readable). The current format is complicated due to pixels of different sizes; there’s no way to know where data for pixel 1000 starts without reading all preceding 999 pixels. You could build a prefix-sum array of pixel indices, but that will fully undermine your compression. One question might be how well does QOI work on independent scan lines or blocks? Is the compression still pretty good if the look-back window is limited in size and restarts every once in a while? To make a GPU capable format, the very first thing you would probably need to do is separate the tag bits from all the other data, so a thread could identify the pixel type by direct lookup into the tag buffer. It then needs to know where to go to find the remaining data, so you’d probably need at least one byte of data that could be used to reliably locate the rest of the data. I don’t see an easy way to make this happen for separate pixels, but it might not be bad if the image is encoded in blocks or scanlines.
  • mmastrac 5y ago
    Wouldn't it make sense to transcode to a GPU-specific lossless, compressed format for rendering?
    • dahart 5y ago
      Yes, totally. Depends on your use case, but there certainly could be good reasons to keep images in compressed form even GPU RAM. It’d be ideal if decode is both random-access and predictable amounts of work per pixel. This format checks the predictable work box, but would need a little design to make it random access.
• javajosh 5y ago
  Very cool - I hope browsers support this soon! Funny meta comment: when I read "offering a 20x-50x speedup in compression and 3x-4x speedup in decompression" I caught myself reacting with disappointment to the "only" 3x-4x speed up. This is funny because 3x improvement is enormous; it's just small compared to 30x. There's a lesson somewhere in there about sharing stats together to achieve an emotional effect.
  • xiphias2 5y ago
    It's trivial to port this to JS / WebAssembly without losing speed (using bytearrays) ..it's a nice afternoon project actually
    • deleted 5y ago
      [deleted]
• kasper93 5y ago
  Neat work. Though I wouldn't be myself if I didn't have few nitpicks ;) - You are mixing lossy and lossless compression in your rant. And you are mixing containers with formats. Thing about lossy compression is that it is by design stupidly slow and complex to produce smallest possible results which has best perceived quality. Compress once and trade time for both image and compression quality. Lossless is not that bad, although your simple solution is well, simple :) - I feel like the benchmark suite is lacking. For better overview you probably should include libpng results with max compression level and lowest compression level. Lossless modes of AVIF and WEBP would be nice. (also could throw similar project to yours like https://github.com/catid/Zpng https://github.com/catid/Zpng) Not saying the benchmark is bad, but IMHO doesn't paint the full picture. From quick test I got significantly better compression on libpng, ofc in expense of time, but you didn't configure libpng for speed either. So we have some results, but they are not really representative imho. - I understand it is pet project, but don't forget about importance of image metadata, like colorspace and so on. - Also keep in mind that compression is easy at the beginning, but the tricky part is how to squeeze more. EDIT: formatting...
  • t0rakka 5y ago
    I wrote a small test bench for my own uses as wanted to compare with different codecs and see how "raw compression" would work, how would QOI+ZSTD combination work and so on. Here's example output.. image: 1502 x 1800 ( 10560 KB ) ---------------------------------------------- encode(ms) decode(ms) size(KB) ---------------------------------------------- qoi: 31.2 21.6 2452 qoi+zstd: 46.7 19.3 1832 zstd: 47.4 8.7 2742 lz4: 14.1 3.0 4108 png: 92.4 18.0 2795 zpng: 24.1 13.3 1394 jpg: 2.7 1.8 517 <-- lossy webp: 199.6 19.1 227 <-- lossy
• SavantIdiot 5y ago
  What I like about this approach is that it requires zero differential calculus. People forgot that Radix2 DCTs come from a century's worth of advanced math in the S domain. This approach is applied-computer-science based, I can get my head around that a lot better than a Laplace/Z transform. But what shocks me is how did absolutely no-one apply such a naive RLE in the 30 years of internet image formats? Is this a case of "man reinvents wheel again because why do research" or is this exceptional?
  • Trixter 5y ago
    RLE on runs of deltas is in very many compression schemes; it's a common technique (probably so common that many authors don't deem it worth mentioning). Lossless video codecs in particular (huffyuv, lagarith, utcodec, etc.) have had this going back 20 years at least.
    • michael-ax 5y ago
      definitely ubiquitous. we applied rle encoding for time-series and triac control systems 43 years ago after getting some guidance from a mainframe guy - but since RLE is practical so that we even use it to give direction to people on the street, its probably so old that its even found its way into the way our genes are encoded. :D
  • a_e_k 5y ago
    > But what shocks me is how did absolutely no-one apply such a naive RLE in the 30 years of internet image formats? Off the top of my head, both PCX [0] and TGA [1] use similarly naive RLE as their compression method. And while they also offer fancier compression methods, BMP [2], TIFF [3], and OpenEXR [4] all offer RLE modes as well. [0] https://en.wikipedia.org/wiki/PCX https://en.wikipedia.org/wiki/PCX [1] https://en.wikipedia.org/wiki/Truevision_TGA https://en.wikipedia.org/wiki/Truevision_TGA [2] https://en.wikipedia.org/wiki/BMP_file_format https://en.wikipedia.org/wiki/BMP_file_format [3] https://en.wikipedia.org/wiki/TIFF https://en.wikipedia.org/wiki/TIFF [4] https://en.wikipedia.org/wiki/OpenEXR https://en.wikipedia.org/wiki/OpenEXR
• makapuf 5y ago
  for a good simple and fast image compressor look at DXT (decoded natively by graphics cards). No benchmarks for encoder performance though.
  • rasz 5y ago
    Dont you mean Apple Quicktime Road Pizza? S3 ripped off main method (https://en.wikipedia.org/wiki/Apple_Video#Four_color_mode https://en.wikipedia.org/wiki/Apple_Video#Four_color_mode), patented it, and 10 years later successfully sued Apple for using it.
• ErikCorry 5y ago
  I like the small size of the decoder state - not much more than 256 bytes. I haven't found a way to decode GIF with less than about 16k of mutable state. PNG is similar though you can use the decoded image if it's available.
• Animats 5y ago
  Lossless avoids all those issues around human perception. Also, if you're storing game assets, some of what you're storing as images is not really imagery. It may be normals or height fields, which lossy image compression messes up. The code is interesting, in that it iterates over the output array, not the input. This helps prevent write buffer overflows. It has read buffer overflows, though. You can craft a compressed file which, when decompressed, will contain info from elsewhere in memory.
  • account42 5y ago
    Where do you see a read buffer overflow?
    • Animats 5y ago
      That would be telling.
      • account42 5y ago
        Or you could be wrong.
        • Animats 5y ago
          It checks for running out of input but, at line 460, will read three bytes beyond the end of the buffer for suitably constructed input. This is technically wrong, but hard to exploit. Amusingly, if you run out of input too soon, the last pixel is replicated to fill the buffer. So you don't get random memory contents in the output, which would be more exploitable. [1] https://github.com/phoboslab/qoi/blob/master/qoi.h https://github.com/phoboslab/qoi/blob/master/qoi.h
          • deleted 5y ago
            [deleted]
          • account42 5y ago
            I still don't see it. Note that there is 4 bytes of padding at the end of the image data to simplify the bounds check in the decoder. Those 4 bytes are subtracted from the chunks_len that the pixel start bound check compares against. So you could craft an image where the last pixel runs into that padding (which the encoder won't produce since it always pads with the full 4 bytes) but not one where the pixel data is read from outside the image buffer beyond the padding.
• a_e_k 5y ago
  QOI_DIFF16 { u8 tag : 3; // b110 u8 dr : 5; // 5-bit red channel difference: -15..16 u8 dg : 4; // 4-bit green channel difference: -7.. 8 u8 db : 4; // 4-bit blue channel difference: -7.. 8 } I'd think that the extra bit ought to be given to green, since that tracks most closely with luminance. That would make this somewhat analogous to the RGB565 layout for 16-bit pixels (https://en.wikipedia.org/wiki/High_color#16-bit_high_color https://en.wikipedia.org/wiki/High_color#16-bit_high_color).
• themeiguoren 5y ago
  This is sweet, I love things that are both performant and not totally black magic. > Seeing how every change I made affected the compression ratio was quite exciting. I’m curious, do you have a rough breakdown of how much each of the techniques bought you?
• hackerfactor1 5y ago
  There are a lot of better-than-JPEG and better-than-PNG solutions out there. Speed: If the benchmarks are correct, then this is exceptional, especially considering that the file size is only slightly larger than PNG. I can think of a couple of ways they could reduce the file size by probably around 10%-20% without sacrificing speed, but this is good enough to get attention. The biggest speed loss for PNG comes from zlib. PNG without zlib is very fast -- probably comparable to QOI. If QOI use bz2 or even zlib on top of the current encoding scheme, then it would be slower, but I bet it would also be smaller than PNG. The biggest issue isn't making a better/faster picture format. Rather, the biggest issues are adoption, metadata, and variable color support. Until web browsers and smartphones natively support the format, it's only good for a proof-of-concept or for niche applications. (Don't get me wrong -- online games could benefit from something like this.) Wide-spread consumer adoption will also need support for metadata. EXIF, IPTC, XMP, ICC Profiles, etc. This is easy enough to add. I hope the author choose something simple, like a tag-length-data. The tag just identifies it as a meta block. The data should begin with a text string and "\n" that defines the type of data, followed by the binary data. The "length" includes the size of the data + string + 1 for "\n". Also, be aware that some metadata is larger than 65535 bytes, so the length should support large data blocks. The algorithm as currently defined only supports 8-bits per channel and 3 or 4 channels (RGB or RGBA). For widespread adoption, it should support: - 8-bit Grayscale (1 byte per pixel) - 16-bit Grayscale (2 bytes per pixel) - 8-bit Grayscale + Alpha (2 byte per pixel) - 16-bit Grayscale + Alpha (4 bytes per pixel) - 8-bit and 16-bit RGB (24 and 48 bytes per pixel) - 8-bit and 16-bit RGBA (32 and 64 bytes per pixel) - 8-bit and 16-bit CMYK (for the printing industry) - 8-bit YUV (for cameras; most also support 16-bit YUV, but it's rarely ever seen) I don't think the algorithm will change for these, but the file format will need a header that defines the color space and color depth. The source code is also problematic. For example, the .h (header) file contains functions. Not function definitions, but actual functions. E.g.: https://github.com/phoboslab/qoi/blob/master/qoi.h https://github.com/phoboslab/qoi/blob/master/qoi.h All functions (qoi_encode, qoi_decode, etc.) are completely included in this header file. It should be in a .c file (not .h) and compiled into a library (libqoi). Although C does permit you to put functions in header files, it is REALLY REALLY REALLY bad form and strongly discouraged. (This is a really bad programming practice. When I was in school, doing this sort of thing would be an immediate homework failure even if the code works.)
• daneel_w 5y ago
  This scheme is strikingly similar to the Commodore Amiga's HAM (hold-and-modify) display mode. https://en.wikipedia.org/wiki/Hold-And-Modify https://en.wikipedia.org/wiki/Hold-And-Modify
• josephernest 5y ago
  Very cool and impressive! Do you have benchmarks on what it does in the worst case? Let's say a 1000x1000 pixels image of RGB noise? The bitmap should be 24 bit * 1Mpixels = 3MB. What's the size, compressed as PNG, and compressed as QOI?
• peter_d_sherman 5y ago
  My new favorite image compression/decompression format! A+ for simplicity, readability, and security/code auditability!
• williamaadams 5y ago
  Just came here to say, good job. I was doing my own run-length encoding thing using the TGA format, but this is nicer. It's good enough that I am able to run a little screencast thing using it.
• Rounin 5y ago
  By the way, this image format can match PNG in terms of size if combined with another form of lossless compression, so if we allow for that extra complexity, something like QOI + Zstandard could possibly compete with PNG in terms of both size and speed.
• makapuf 5y ago
  A pure go version: https://github.com/xfmoulet/qoi https://github.com/xfmoulet/qoi
• sjoruk 5y ago
  I really like the format, good job. I've been working on a rust implementation: https://github.com/steven-joruk/qoi https://github.com/steven-joruk/qoi