Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

QOI: Lossless Image Compression in O(n) Time

phoboslab.org

Post reply on HN
Print view View original

231–240 of 303 posts

Re: QOI: Lossless Image Compression in O(n) Time

#231

Post by HanClinto »

adgjlsfhk1 wrote: post #80

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. F…

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.

Re: QOI: Lossless Image Compression in O(n) Time

#232

Post by em3rgent0rdr »

dylan604 wrote: post #211
em3rgent0rdr wrote: post #204

Earlier quoted context omitted.

That metadata could be stored in the filename to keep it out of the actual file.

No, the filename is the worst place to put metadata. Nobody can control what will happen to a file name.

well nobody can control what will happen to a file's content either if you want to be pedantic.

If are worried about dumb users renaming it...I think most users know to not change things after a '.', so could just put the colorspace code there. And then could put another '.QOI' to end the filename.

If want to keep cruft out of the file itself, then putting it in the filename works.

Re: QOI: Lossless Image Compression in O(n) Time

#233

Post by kortex »

jiggawatts wrote: post #23

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 treat…

Since we are talking container formats, I would recommend something in the IFF/RIFF family (which includes "true" Four-byte-type IFFs like RIFF, WAV, WEBP, and variants like PNG, MOV, MP4). They are about as simple as you can get as a container format. It has its limitations but it's basically the simplest "boxed" format you can implement - Type-Length-Value.

I would absolutely recommend basing on some sort of container format (vs "raw" data structures), it makes it really easy to add functionality without breaking backwards compatibility.

Basically all container formats follow this idea of "collection of boxes" pattern. The IFF series are box-length based. Ogg uses capture patterns but no explicit box size (I think). The former means you have to know the box size ahead of time (or seek back and write it in), the latter is better for streaming, but harder to seek (without indexes).

Re: QOI: Lossless Image Compression in O(n) Time

#234

Post by dekhn »

spc476 wrote: post #195
cornstalks wrote: post #178

Earlier quoted context omitted.

> When I say (255, 0, 0), I expect the display to show me its best approximation of red. Which red? There isn't a single, true "red". And different materials produce different reds (my work's Sony BVM-X300's reddest red is going to look way different than your monitor's red). Not all displays use only RGB color primaries, too. For example, at Dolby's office in San Francisco they have a projector in their theater that…

And the red in my left eye isn't the same as the red in my right eye. Yes, when the lighting conditions are just right , I see different hues out of each eye [1]. I have to wonder how one would (or should?) correct for that in an image file format. [1] I think from a stupid thing I did as a kid.

took me a while to notice that I perceive color and light intensity differently in my two eyes. I think this is actually pretty natural (IE, it happens commonly?). Either way, I can also see polarization (haidinger's brush) which confused me a bunch when I was trying to explain what I saw and everybody else thought I was crazy).

Re: QOI: Lossless Image Compression in O(n) Time

#235

Post by khoobid_shoma »

sbrki wrote: post #75

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 w…

Yeah, really nice and efficient C programming with a great idea!

Re: QOI: Lossless Image Compression in O(n) Time

#237

Post by dylan604 »

em3rgent0rdr wrote: post #232
dylan604 wrote: post #211

Earlier quoted context omitted.

No, the filename is the worst place to put metadata. Nobody can control what will happen to a file name.

well nobody can control what will happen to a file's content either if you want to be pedantic. If are worried about dumb users renaming it...I think most users know to not change things after a '.', so could just put the colorspace code there. And then could put another '.QOI' to end the filename. If want to keep cruft out of the file itself, then putting it in the filename works.

you're talking apples and kumquats. changing the name of the file (metadata in and of itself) does not affect the file at all. changing the contents of the file will have affects on the file. some changes might not negatively affect the file (like adding metadata when none was present) if the format allows for it. you can know the file will no longer be the same by running a hash on it. name changes will not affect the hash.

also, changing the name of a file is not like, uncommon. if it is an image sequence, some people prefer an underscore before the frame number, some prefer a dot, and some even prefer a space. some places have strict file naming policies, and file names will be modified to comply.

anyone depending on crucial information to be preserved in a filename is just a Sisyphean effort of control.

Re: QOI: Lossless Image Compression in O(n) Time

#238

Post by [deleted] »

wongarsu wrote: post #48

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,…

[deleted]

Re: QOI: Lossless Image Compression in O(n) Time

#239

Post by sedatk »

yboris wrote: post #79

Obligatory comment about the new file format that's going to replace jpegs: JPEG XL https://jpegxl.info/ It also has lossless setting (in addition to being better at compression when you want a lossy format).

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_deth...

Re: QOI: Lossless Image Compression in O(n) Time

#240

Post by hackerfactor1 »

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 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.)

Post reply on HN