5 ms·

Lossless Image Compression in O(n) Time (2021)

107 points by marcodiego 4y ago

lifthrasiir 4y ago
This is about the QOI format, in case you can't recognize from the original title. Past discussions: QOI: Lossless Image Compression in O(n) Time (2021-11-24, 293 comments) https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 The QOI File Format Specification (2021-12-20, 54 comments) https://news.ycombinator.com/item?id=29625084 https://news.ycombinator.com/item?id=29625084 QOI – The “Quite OK Image Format” for fast, lossless image compression (2021-12-23, 103 comments) https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 QOI – The Quite OK Image Format (2022-04-02, 97 comments) https://news.ycombinator.com/item?id=30885668 https://news.ycombinator.com/item?id=30885668 [after the official domain has been set up]
CJefferson 4y ago
I think almost all compression systems are O(n). All the standard stream compressors are (gz, bz2, 7zip, zstd). I’d have to check png and jpg to make sure they don’t do any non-O(n) global reasoning, but I would be surprised. I think the author is trying to capture an idea of “simple”, but has misidentified that as O(n). Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).
- sgtnoodle 4y ago
  You could say his algorithm is 0(n) while others are O(n*m) where m is the size of the window. The window size happens to be a constant in practice, but parameterizing it does seem reasonable from a comparison standpoint. His algorithm works like other algorithms with a window size of 64, but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all.
  - RaisingSpear 4y ago
    > but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all. Most other compression implementations also use a hash table, at least on the faster settings. They may switch to something like a hash chain on slower settings, but that doesn't really change asymptotic complexity as it just evaluates more matches. I don't think any implementation does a straight linear search across the window, as that's just stupidly slow, though maybe a "give me the best compression, I don't care about speed" compressor might.
  - xxs 4y ago
    >He is using a hash table rather than a linear search after all. LZW uses a hash table too (traditionally with a prime based capacity)
- dataflow 4y ago
  > Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n). I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.
  - selcuka 4y ago
    > flip through all possible states of those n bits How do you do that in one pass?
    - dataflow 4y ago
      By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
    - fdupress 4y ago
      Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).
  - CJefferson 4y ago
    Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space. You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
  - aardvark179 4y ago
    If it has a fixed upper bound on memory usage then it can’t store all the input to iterate through all the possible bit patterns, at least not for arbitrarily large inputs.
- vintermann 4y ago
  The bzip2 algorithm is, as I recall, quadratic in block size. But that's because of the implementation, ways to do the BWT transform in linear time has been found since. And also, bzip2 doesn't let you choose very big block sizes anyway, it could have supported far larger ones with the memory modern computers have (as opposed to when it was first implemented)
  - AbrahamParangi 4y ago
    Sure but n^2 in block size is still linear in data length.
chapliboy 4y ago
I love the qoi format. I mostly adopted it for the wasm context. While porting to wasm, using something like stb_image became a little complicated, so I wrote a png-qoi converter, and then use the qoi assets in the game. Writing a qoi decoder is a fun exercise, though i think most languages have their implementations already.
ibnbutlAn 4y ago
"stupidly simple" is my favorite kind of software complexity.
pornel 4y ago
QOI is confusing simple with primitive. It's worsening compression only due to trauma of using dependencies in C. I strongly disagree with characterization that JPEG is overcomplicated, especially in a controlled situation where you only need to support files you encode yourself (as is the case with QOI), and not edge cases like Adobe's CMYK extension. JPEG's design is brilliant for the level of compression it's capable of. libjpeg API is crufty, and C dependencies are a pain, but you can use other implementations and languages.
- wolletd 4y ago
  I'm working at a small company that does computer vision and image processing stuff, doing a lot with embedded systems. At some point, I was asked to write code to save images on live systems to be downloaded and used for... CV stuff. Also, the images had to be (although weakly) encrypted for IP reasons. The issue being that those cameras run at 200fps when there's anything of interest and use their compute to do image processing. The flash memory used also isn't made for this kind of write speed. All that is to say: JPEG is insanely efficient. It takes a moment to compress the image, but only encrypting 10% of the data saves a lot more and the flash memory can keep up way longer than with raw images. I had to generate some difference images though to convince some CV and management people that we don't need raw images. If our analysis results would depend on a dozen pixels not being off 1-2 gray values, it's broken. There's more noise in every single image than JPEG-induced errors.
  - brucethemoose2 4y ago
    > 200 fps TBH that sounds like a job for a video codec.
- SkeuomorphicBee 4y ago
  JPEG's design is brilliant, that is very true, but it also complicated. It uses a lot of CPU cycles to calculate the FFTs of the signal, and that is where the simplicity of QOK shines, by operating on the signal itself (instead of expensively transforming it to frequency space) it can be order(s) of magnitude faster. The discussion is not about the quality of the API, but the amount of work an actual machine will have to do to compress/decompress.
vintermann 4y ago
It's arguably not really image compression, but pixel sequence compression. It doesn't seem to exploit that images are two-dimensional at all.
- mackman 4y ago
  I think using the same algorithm but swizzling the pixels might help (process them in Z curve order).
  - fps-hero 4y ago
    It may help to a limited extent with compression, but the window size is so small it is hardly worth it. I imagine a huge part of the speed of the algorithm is how cache friendly it is. Worse is better sometimes.
deleted 4y ago
[deleted]
hendry 4y ago
I think this is the same approach as https://tools.suckless.org/farbfeld/faq/ https://tools.suckless.org/farbfeld/faq/ i.e. removing compression from image formats
- lifthrasiir 4y ago
  Farbfeld is based on two faulty assumptions: 1. That an image is expected to be decompressed as a whole, and 2. That an efficient (de)compression is possible with generic compression algorithms. Both are false. Even PNG does its own filtering, a pretty rudimentary model but much better than just DEFLATE. QOI is much better in this regard because it has a (fixed and also rudimentary) model; it was a clear demonstration that modeling is much important than entropy coding.
codetrotter 4y ago
> With some more work, QOI could serve as the basis for a lossless video codec, suitable for screencasts and the like. For me, an interesting use-case would be streaming webcam video from my Raspberry Pi. I have some Raspberry Pi Compute Module 4, and some Raspberry Pi Camera Module 3. Along with some various USB webcams. I would love to be able to stream video from my RPi CM 4 with the camera 3 modules connected, at the highest possible resolution and frame rate. Beyond that I would like to stream to many clients at once without too much overhead. But the initial goal would be to get something with top resolution and frame rate even for just 1 client. And for that this kind of thing sounds interesting.
- olabyne 4y ago
  Check what Vigibot is doing with their client. Using h264_omx, the raspberry Pi is fairly capable of streaming 720p at <50ms latency
  - elcritch 4y ago
    RPi4 processors have hardware h264 encoding built-in. Ffmpeg / gstreamer tools support it.
    - codetrotter 4y ago
      And yet CM4 is noticeably laggy and drops frames when I try to stream video using fmpeg or cvlc. And I am left wondering why.
SanderNL 4y ago
Seeing as simple image decoders are still producing CVEs I think it’s worth considering vastly more stupid approaches that get us 80% of the way with 20% of the trouble.

107 points by marcodiego 4y ago

This is about the QOI format, in case you can't recognize from the original title. Past discussions: QOI: Lossless Image Compression in O(n) Time (2021-11-24, 293 comments) https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750 The QOI File Format Specification (2021-12-20, 54 comments) https://news.ycombinator.com/item?id=29625084 https://news.ycombinator.com/item?id=29625084 QOI – The “Quite OK Image Format” for fast, lossless image compression (2021-12-23, 103 comments) https://news.ycombinator.com/item?id=29661498 https://news.ycombinator.com/item?id=29661498 QOI – The Quite OK Image Format (2022-04-02, 97 comments) https://news.ycombinator.com/item?id=30885668 https://news.ycombinator.com/item?id=30885668 [after the official domain has been set up]

CJefferson 4y ago

I think almost all compression systems are O(n). All the standard stream compressors are (gz, bz2, 7zip, zstd). I’d have to check png and jpg to make sure they don’t do any non-O(n) global reasoning, but I would be surprised. I think the author is trying to capture an idea of “simple”, but has misidentified that as O(n). Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n).

sgtnoodle 4y ago
You could say his algorithm is 0(n) while others are O(n*m) where m is the size of the window. The window size happens to be a constant in practice, but parameterizing it does seem reasonable from a comparison standpoint. His algorithm works like other algorithms with a window size of 64, but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all.
- RaisingSpear 4y ago
  > but does so more efficiently from an algorithmic point of view. He is using a hash table rather than a linear search after all. Most other compression implementations also use a hash table, at least on the faster settings. They may switch to something like a hash chain on slower settings, but that doesn't really change asymptotic complexity as it just evaluates more matches. I don't think any implementation does a straight linear search across the window, as that's just stupidly slow, though maybe a "give me the best compression, I don't care about speed" compressor might.
- xxs 4y ago
  >He is using a hash table rather than a linear search after all. LZW uses a hash table too (traditionally with a prime based capacity)
dataflow 4y ago
> Any algorithm which operates in a single pass on a stream of data and has a fixed upper memory usage is O(n). I think you oversimplified in the other direction? An algorithm can make 1 pass over data (say it's n bits), then flip through all possible states of those n bits, taking exponential time. Or if you consider that to violate having a "fixed" upper bound (not sure this is meaningful in any useful sense, especially given it would probably need at least log(n) bits to know how far it's read its input), consider that it can even loop infinitely if it wants to.
- selcuka 4y ago
  > flip through all possible states of those n bits How do you do that in one pass?
  - dataflow 4y ago
    By not reading the input again and just keeping the n-bit counter in unrelated memory, since the actual input is kind of irrelevant for this, only its size. Again, may or may not apply depending on what precisely they meant by a "fixed" additional amount of memory...
  - fdupress 4y ago
    Hash the input (O(n)), search for a second preimage (very much not O(n) if you use a cryptographic hash).
- CJefferson 4y ago
  Many stream-based compressors don't track how far they have read into their input, they just keep reading bytes, and writing out bytes. Things like zlib can be set up with a fixed sized buffer, and don't go allocating extra memory, so they definately can't start using arbitary extra space. You are right an algorithm doesn't have to be O(n), as it could enter an infinite loop and never finish.
- aardvark179 4y ago
  If it has a fixed upper bound on memory usage then it can’t store all the input to iterate through all the possible bit patterns, at least not for arbitrarily large inputs.
vintermann 4y ago
The bzip2 algorithm is, as I recall, quadratic in block size. But that's because of the implementation, ways to do the BWT transform in linear time has been found since. And also, bzip2 doesn't let you choose very big block sizes anyway, it could have supported far larger ones with the memory modern computers have (as opposed to when it was first implemented)
- AbrahamParangi 4y ago
  Sure but n^2 in block size is still linear in data length.

chapliboy 4y ago

I love the qoi format. I mostly adopted it for the wasm context. While porting to wasm, using something like stb_image became a little complicated, so I wrote a png-qoi converter, and then use the qoi assets in the game. Writing a qoi decoder is a fun exercise, though i think most languages have their implementations already.

ibnbutlAn 4y ago

"stupidly simple" is my favorite kind of software complexity.

pornel 4y ago

QOI is confusing simple with primitive. It's worsening compression only due to trauma of using dependencies in C. I strongly disagree with characterization that JPEG is overcomplicated, especially in a controlled situation where you only need to support files you encode yourself (as is the case with QOI), and not edge cases like Adobe's CMYK extension. JPEG's design is brilliant for the level of compression it's capable of. libjpeg API is crufty, and C dependencies are a pain, but you can use other implementations and languages.

wolletd 4y ago
I'm working at a small company that does computer vision and image processing stuff, doing a lot with embedded systems. At some point, I was asked to write code to save images on live systems to be downloaded and used for... CV stuff. Also, the images had to be (although weakly) encrypted for IP reasons. The issue being that those cameras run at 200fps when there's anything of interest and use their compute to do image processing. The flash memory used also isn't made for this kind of write speed. All that is to say: JPEG is insanely efficient. It takes a moment to compress the image, but only encrypting 10% of the data saves a lot more and the flash memory can keep up way longer than with raw images. I had to generate some difference images though to convince some CV and management people that we don't need raw images. If our analysis results would depend on a dozen pixels not being off 1-2 gray values, it's broken. There's more noise in every single image than JPEG-induced errors.
- brucethemoose2 4y ago
  > 200 fps TBH that sounds like a job for a video codec.
SkeuomorphicBee 4y ago
JPEG's design is brilliant, that is very true, but it also complicated. It uses a lot of CPU cycles to calculate the FFTs of the signal, and that is where the simplicity of QOK shines, by operating on the signal itself (instead of expensively transforming it to frequency space) it can be order(s) of magnitude faster. The discussion is not about the quality of the API, but the amount of work an actual machine will have to do to compress/decompress.

vintermann 4y ago

It's arguably not really image compression, but pixel sequence compression. It doesn't seem to exploit that images are two-dimensional at all.

mackman 4y ago
I think using the same algorithm but swizzling the pixels might help (process them in Z curve order).
- fps-hero 4y ago
  It may help to a limited extent with compression, but the window size is so small it is hardly worth it. I imagine a huge part of the speed of the algorithm is how cache friendly it is. Worse is better sometimes.

deleted 4y ago

[deleted]

hendry 4y ago

I think this is the same approach as https://tools.suckless.org/farbfeld/faq/ https://tools.suckless.org/farbfeld/faq/ i.e. removing compression from image formats

lifthrasiir 4y ago
Farbfeld is based on two faulty assumptions: 1. That an image is expected to be decompressed as a whole, and 2. That an efficient (de)compression is possible with generic compression algorithms. Both are false. Even PNG does its own filtering, a pretty rudimentary model but much better than just DEFLATE. QOI is much better in this regard because it has a (fixed and also rudimentary) model; it was a clear demonstration that modeling is much important than entropy coding.

codetrotter 4y ago

> With some more work, QOI could serve as the basis for a lossless video codec, suitable for screencasts and the like. For me, an interesting use-case would be streaming webcam video from my Raspberry Pi. I have some Raspberry Pi Compute Module 4, and some Raspberry Pi Camera Module 3. Along with some various USB webcams. I would love to be able to stream video from my RPi CM 4 with the camera 3 modules connected, at the highest possible resolution and frame rate. Beyond that I would like to stream to many clients at once without too much overhead. But the initial goal would be to get something with top resolution and frame rate even for just 1 client. And for that this kind of thing sounds interesting.

olabyne 4y ago
Check what Vigibot is doing with their client. Using h264_omx, the raspberry Pi is fairly capable of streaming 720p at <50ms latency
- elcritch 4y ago
  RPi4 processors have hardware h264 encoding built-in. Ffmpeg / gstreamer tools support it.
  - codetrotter 4y ago
    And yet CM4 is noticeably laggy and drops frames when I try to stream video using fmpeg or cvlc. And I am left wondering why.

SanderNL 4y ago

Seeing as simple image decoders are still producing CVEs I think it’s worth considering vastly more stupid approaches that get us 80% of the way with 20% of the trouble.