How JPEG actually works (2006) | Hacker News Reader

How JPEG actually works (2006)

blogs.msdn.microsoft.com

144 pointsramijames24 comments

For those interested in writing their own JPEG decoder (a highly recommended exercise --- it doesn't take all that long, actually) I suggest these two detailed articles:

https://www.impulseadventure.com/photo/jpeg-decoder.html

https://www.impulseadventure.com/photo/jpeg-huffman-coding.h...

Of course, there are also plenty of other "write a JPEG decoder/encoder tutorial" articles out there, of varying quality --- which if anything proves that it's not actually so hard. The standard contains a surprisingly simple and elegant flowchart description of the Huffman encoder/decoder.

The more modern JPEG 2000 encoding based on wavelets can be pushed much farther before visible artifacts appear, and includes a surprisingly efficient lossless mode. Of course, all this improvement is rather moot until common applications actually support it.

That was 12 years ago, and J2K is still pretty much unknown outside of niche applications. I'm not sure what they mean by "surprisingly efficient lossless mode", but decoding J2K is slower than regular JPEG by at least an order of magnitude if not more. The lack of articles about how to write decoders/encoders, or even just how it works in detail, is another sign of its relative obscurity. I've been studying the standard on and off for a few months, intending to write an article or even a decoder, but haven't gotten around to it yet. It is certainly an order of magnitude more complex.

> That was 12 years ago, and J2K is still pretty much unknown outside of niche applications.

It’s big in digitized documents and medical space where the superior compression has real benefits. One under-appreciated benefit is that the combination of progressive decoding and tiling is perfect for deep zoom services since you don’t want to precompute thousands of tiles per image when your library size is millions of images.

The big problem with JPEG 2000 as I see it was a lack of openness: for a long time, a copy of the spec cost non-trivial money and there was no standard test suite so compatibility was a constant problem. This meant that there was no good open source library and thus that most users had a bad experience relative to other formats. This changed over the last few years and OpenJPEG has become competitive on quality and speed but I’m afraid the damage may have been fatal.

One of the things which makes me sad about that is that it’d be great for progressive images on the web with an extension to srcset to specify the byte ranges for each size, avoiding the need to cache duplicate variants. Unfortunately the lack of high quality libraries and adoption probably means that window has passed, although it would be interesting to see how well a Web Assembly version performs.

Surprisingly efficient as for the size of the resulting binary compared to the original, not efficient as in time or cycle efficiency.

> decoding J2K is slower than regular JPEG by at least an order of magnitude if not more

True, but I'm sure it doesn't even hold a candle to the challenge of real-time decoding of modern video codecs.

Is it just a chicken-and-egg problem with hardware support, that prevents formats like FLIFF [0] from seeing adoption?

[0] http://flif.info/

I believe digital cinema packages use invidually-compressed jpeg2000 frames, so thats a fairly widespread usage.

PDF uses jpeg2k, but I don't know of anything else that does. (Archive.org is using both jpeg2k and jbig in their pdfs.)

Yes, the PDFs on archive.org are the first thing to come to mind (and my first exposure to J2K) --- not all of them use it, but you can identify them by the surprisingly long time it takes to render each page.

It is a shame how quickly the internet loses content. The first few experiments linked in the document lead to 404 pages, even an inline image is 404'ing.

It would have been great if the author of the MSFT article maybe included screenshots or something to preserve the referenced content.

I know the waybackmachine exists, but 2006 doesn't feel that long ago even though it really was.

Archive.org has the experiment link (Standford page), but misses quite a few images in it. https://web.archive.org/web/20070101025129/http://www.stanfo...

Coincidentally, another link on the HN front page is about the image quality of JPEG vs. JPEG 2000 vs. JPEG XR vs. WebP vs. BPG: https://news.ycombinator.com/item?id=17587684 ; https://bellard.org/bpg/ ; http://xooyoozoo.github.io/yolo-octo-bugfixes/

Looks promising, but image format is one of the slowest adapted standards on the Internet. How's the encode/decode speed?

Isn't there another format recently, FLIF?

I want to use images to encode HTML or other arbitrary binary data, in a way that I call Fondant.

https://news.ycombinator.com/item?id=17461955

I made a checkerboard pattern of 8x8 pixels, but I still lose data to colour bleeding when re-encoding (e.g. upload to Facebook or Save to Camera Roll on the iPhone).

Is there some way I can use the "lossless" entropy coding to avoid this problem?

You can perturb the input of the DCT so that a specific IDCT implementation will generate the desired output. This technique applied to JPEG has been known for a few years:

https://www.virusbulletin.com/virusbulletin/2015/03/script-l...

In general signal-processing terms, this is known as preemphasis/equalisation --- since the communications channel will distort the signal in a known way, by sending a signal distorted appropriately in the opposite direction, it will arrive "undistorted" at the destination.

You can also consider using ECC codes, so that any small errors introduced can be corrected.

Will that work for redistribution? I hope that users could save and re-share the photo many times and let it still be loadable.

To be truly resilient against any kind of (potentially unknown, even) lossy image compression, you would need to add a lot of redundancy. QR Codes are pretty much that, but their data needs to survive being “transmitted” through a blurry photo with arbitrary lighting, rotation and perspective, so they likely have a lot more redundancy than you realistically need. (EDIT: You might hit the limit where you need QR Code levels of efficiency relatively quickly, depending on the number of steps and how aggressive each recompression is.)

If saving and sharing can mean changing the image dimensions however, you of course need redundancy by that factor.

But yeah, that’s why we don’t choose lossy compression algorithms for binary data. If every bit counts, there is no entropy you can lose (though a lossless algorithm might find a more efficient representation, so to speak).

QR codes have a maximum size of 7,089 numerical digits - not enough to transmit a program or song. I'd be hoping to move about 5 MB.

Facebook, which was the use case you mentioned upthread, doesn't store 5MB images. You'd have to design for way less than 5MB, I should imagine.

That was kind of my point, was it not? QR Code might or might not have too much redundancy (depending on how resilient you want to be against what amount of sharing), but the general principle stands.

Lossy compression removes information by design, you want to keep all bits of information, therefore you have to represent your information in a redundant (and therefore inefficient, by density) way.

My thoughts exactly: "Just don't go sending JPEGs into space and expect aliens to see them the same way."

Instead of a wall of text, these Computerphile videos clear the topic pretty well:

https://www.youtube.com/watch?v=n_uNPbdenRs

https://www.youtube.com/watch?v=Q2aEzeMDHMA

I can read that "wall of text" in 2 minutes while you waste 20 minutes watching those videos.

With 90% of the video being the image of some guy talking in a colloquial way and wicked cool camera zooms for impact.

And the rest are visualizations that do more than a text only article ever could.

Sometimes a video is easier to digest after having read and coded all day/week.

Reply on news.ycombinator.com