J40: Independent, self-contained JPEG XL decoder(github.com)
github.com
J40: Independent, self-contained JPEG XL decoder
https://github.com/lifthrasiir/j40
47 comments
Are you familiar with JPEG2000? I looked at this diagram of JPEG XL and was overwhelmed at the complexity, it seems more complex than J2K baseline:
https://en.wikipedia.org/wiki/File:JPEG_XL_codec_architectur...
...and I say this as someone who has written PNG, GIF, and JPEG (baseline sequential) decoders, and didn't think J2K would fit in 5kLoC either.
https://en.wikipedia.org/wiki/File:JPEG_XL_codec_architectur...
...and I say this as someone who has written PNG, GIF, and JPEG (baseline sequential) decoders, and didn't think J2K would fit in 5kLoC either.
I think the exact code for features in that diagram does fit in 5K lines of code. More specifically an entropy coder is less than 1K LoC, the modular mode and transform is probably 1.5K LoC, the entirety of VarDCT is probably 2K LoC. The problem is that JPEG XL has a lot of other features to make it viable as a long-term format, and I greatly underestimated that complexity at the beginning.
Since the library is distributed as an 8k long header file, doesn't compilation times explode?
Most lines of j40.h are only enabled with `#define J40_IMPLEMENTATION`, which should be defined only once.
Hm, yes, but it still 8k source and, afaik, it will be needlessly recompiled whenever the object file that includes it is modified.
Including j40.h more than once does nothing. So it can only affect the preprocessing phase, but windows.h is multiple times larger than J40 (even after `#define WIN32_LEAN_AND_MEAN`) and if you can `#include <windows.h>` anywhere J40 can't be a real problem.
First, very good job to have created such a simple lib without dependency!
Looking at the code example, I was wondering if the 'oops' error check wouldn't be doable at a frame level, or even have some recoverable errors for within a frame?
When loading that kind of objects (image, vidéos,...) It is always annoying when libs have an all of nothing behavior.
Looking at the code example, I was wondering if the 'oops' error check wouldn't be doable at a frame level, or even have some recoverable errors for within a frame?
When loading that kind of objects (image, vidéos,...) It is always annoying when libs have an all of nothing behavior.
J40 is indeed designed with a possibility of partial decoding in mind, but both the API and the internal architecture is currently less prepared for such use cases.
Which part was hardest to implement so far?
Modular predictors (`j40__modular_channel` and related functions in J40). The JPEG XL specification was written after the reference implementation, and there are lots of bugs especially in that part of specification. There are also a significant number of bugs in DCT-like transformations, but those bugs are relatively isolated while modular predictors can wreck the entire image. Those bugs are being reported to the spec editors, so later implementations will have a much easier time.
I really appreciate the work that must have gone into narrowing down those bugs. There's a reason for the insistence on multiple independent implementations for new standards; the Internet owes you one.
Where could one go to read more about the mathematics behind the format, its compression techniques, etc? I remember reading that jpeg 2000 is based on wavelets. Is this the case for jpeg xl?
There are multiple strategies working in tandam.
At the very bottom the entropy coding uses a hybrid of LZ77, Huffman coding and multi-symbol rANS. This is complemented with context modeling which should be pretty familiar to anyone knows Brotli.
For the lossless (modular) mode the main strategy involves finding a good decision tree to compute a prediction for each pixel, which can be learned for each instance (thus named "meta-adaptive"). This mode allows for a number of additional transformations, some of which also function as a progressive encoding.
For the lossy (VarDCT) mode the actual transformation is a (vast) superset of the original JPEG, but a lot of more transformations---mostly related to DCT---are available and there are tons of contexts for each coefficient that can be exploited. Not exactly specific to JPEG XL, but libjxl also features a very good psychovisual model to optimize the resulting visual quality.
Besides from those main modes, there are additional whole-image transformations, color transformations (images can use an absolute color space named XYB when they are allowed to be lossy) and image features. Lastly, images can have multiple frames, some of which are animated and some of which can be merged together when the frame duration is zero, with fully configurable blending modes.
At the very bottom the entropy coding uses a hybrid of LZ77, Huffman coding and multi-symbol rANS. This is complemented with context modeling which should be pretty familiar to anyone knows Brotli.
For the lossless (modular) mode the main strategy involves finding a good decision tree to compute a prediction for each pixel, which can be learned for each instance (thus named "meta-adaptive"). This mode allows for a number of additional transformations, some of which also function as a progressive encoding.
For the lossy (VarDCT) mode the actual transformation is a (vast) superset of the original JPEG, but a lot of more transformations---mostly related to DCT---are available and there are tons of contexts for each coefficient that can be exploited. Not exactly specific to JPEG XL, but libjxl also features a very good psychovisual model to optimize the resulting visual quality.
Besides from those main modes, there are additional whole-image transformations, color transformations (images can use an absolute color space named XYB when they are allowed to be lossy) and image features. Lastly, images can have multiple frames, some of which are animated and some of which can be merged together when the frame duration is zero, with fully configurable blending modes.
The current limitation is probably a good feature to have for a Web-oriented format:
> Crop retangles are currently ignored and can reveal a frame larger than the actual image.
People unaware of lossless cropping may end up posting images that still contain private information they wanted to cut off. If JPEG XL ever makes it to browsers, I hope they won't support cropping, so that people will spot the problem right away, rather later when trolls find it.
> Crop retangles are currently ignored and can reveal a frame larger than the actual image.
People unaware of lossless cropping may end up posting images that still contain private information they wanted to cut off. If JPEG XL ever makes it to browsers, I hope they won't support cropping, so that people will spot the problem right away, rather later when trolls find it.
I'd like to note that "crop rectangles" here refer to the region of the virtual image canvas, whose size is recorded in the image header, where each frame gets decoded. So here what's being cropped is an image canvas, not a frame.
Your point still stands in the sense that, if those rectangles exceed the canvas extent, the surplus will be indeed discarded. I believe the current libjxl doesn't produce such image anyway (why do you keep a portion of image to be discarded?) but it is still something to note.
Your point still stands in the sense that, if those rectangles exceed the canvas extent, the surplus will be indeed discarded. I believe the current libjxl doesn't produce such image anyway (why do you keep a portion of image to be discarded?) but it is still something to note.
> why do you keep a portion of image to be discarded?
I can't speak to the context of the feature in JXL, but this is very very common in mobile image editor metadata formats, so that users can later "undo" a crop they did, because no data is actually lost. Both iOS and Android support this for all images cropped on device.
I can't speak to the context of the feature in JXL, but this is very very common in mobile image editor metadata formats, so that users can later "undo" a crop they did, because no data is actually lost. Both iOS and Android support this for all images cropped on device.
Ah, excellent. I was hoping to integrate JPEG XL into a future C project and was facing the prospect of reimplementing it/translating the standard implementation.
Seriously though, this is going to be HUGE for image editors. A format that finally supports both layers and animation.
Seriously though, this is going to be HUGE for image editors. A format that finally supports both layers and animation.
Here's the nice thing about DLL files, your code can stay C. You just make calls to another library, and it doesn't matter which language was used to build that DLL.
So you get to use LibJXL as long as you have a working DLL file.
(For non-Windows, substitute the appropriate file type for libraries)
So you get to use LibJXL as long as you have a working DLL file.
(For non-Windows, substitute the appropriate file type for libraries)
For those unfamiliar with the format, like me:
“JPEG XL, next generation image compression standard with 60% better compression efficiency than JPEG. The draft predicts that the standard will outperform the still image compression performance shown by HEVC HM, Daala and WebP and unlike previous attempts to replace JPEG, it provides transport options and more efficient lossless recompression storage for traditional images.”
https://en.m.wikipedia.org/wiki/JPEG_XL
“JPEG XL, next generation image compression standard with 60% better compression efficiency than JPEG. The draft predicts that the standard will outperform the still image compression performance shown by HEVC HM, Daala and WebP and unlike previous attempts to replace JPEG, it provides transport options and more efficient lossless recompression storage for traditional images.”
https://en.m.wikipedia.org/wiki/JPEG_XL
I'll add "Royalty-free format with an open-source reference implementation". In other words there's a chance this will see real adoption unlike the many previous attempts to build a JPEG v2.
> outperform the still image compression performance shown by HEVC HM, Daala and WebP
Naw, the real competitor is AVIF which recently got desktop and iOS Safari support. Chrome and Firefox have supported AVIF since forever and Safari was the final holdout.
> outperform the still image compression performance shown by HEVC HM, Daala and WebP
Naw, the real competitor is AVIF which recently got desktop and iOS Safari support. Chrome and Firefox have supported AVIF since forever and Safari was the final holdout.
The thing about AVIF is that it's genuinely heavier processor-wise (software decoding) or requires more hardware circuitry than JXL (hardware decoding). It's better than nothing and since AV1 was finalised a few years ago it's definitely helpful (JXL has been just finalised), but it's worse than WebP in lossless encoding (so stick to WebP for that) and may affect battery life in devices with a WebM hardware decoder but don't have any AV1 circuitry.
AFAIK nobody decodes still images using video hardware acceleration. HW supports only one stream at a time and has a setup latency. Browsers decode images in parallel and want them ASAP.
AVIF does very well in almost-lossless encoding of the kinds of images you'd use lossless formats for. You can beat any lossless format with imperceptibly small amount of loss.
True lossless is needed for authoring, but not for typical Web distribution. People think lossy can't be used for icon-like images, because they associate lossy with JPEG-like distortions, but it's possible to do lossy compression using other methods that preserve razor-sharp edges.
AVIF does very well in almost-lossless encoding of the kinds of images you'd use lossless formats for. You can beat any lossless format with imperceptibly small amount of loss.
True lossless is needed for authoring, but not for typical Web distribution. People think lossy can't be used for icon-like images, because they associate lossy with JPEG-like distortions, but it's possible to do lossy compression using other methods that preserve razor-sharp edges.
> lossy compression using other methods that preserve razor-sharp edges
Examples? I've never seen lossy compressed icons that didn't look like crap, but what you describe should be possible in theory.
Examples? I've never seen lossy compressed icons that didn't look like crap, but what you describe should be possible in theory.
AVIF is the example. It supports palette-based blocks in addition to classic DCT with sophisticated deringing. There's also https://pngquant.org (palette may seem banal, but it is a type of vector quantization) and https://github.com/richgel999/rdopng
rdopng looks awesome, I wasn’t aware of it, thanks.
The format claims to be "royalty-free" but standard itself is not free.
Also it seems it has unresolved patent issue: https://www.theregister.com/2022/02/17/microsoft_ans_patent/
While the software patent is a spicy issue, Jon Sneyers once noted that Microsoft may be in a deep trouble if they actually exercise that patent because of both Google's and Cloudinary's defensive patents [1].
[1] https://twitter.com/jonsneyers/status/1526598054685642753
[1] https://twitter.com/jonsneyers/status/1526598054685642753
Could someone ELI5 the following?
1. Weren't "ideas" not supposed to be patentable, but only actual implementations? Given that, how can an algorithm be patented?
2. Wasn't prior art supposed to invalidate a patent? If the algorithm was already used in JPEG-XL, then clearly Microsoft isn't the first to discover it, and hence should not be able to patent it, right? Or if the algorithm in JPEG-XL is considered different, then there's no infringement by definition, right? So what's the issue?
1. Weren't "ideas" not supposed to be patentable, but only actual implementations? Given that, how can an algorithm be patented?
2. Wasn't prior art supposed to invalidate a patent? If the algorithm was already used in JPEG-XL, then clearly Microsoft isn't the first to discover it, and hence should not be able to patent it, right? Or if the algorithm in JPEG-XL is considered different, then there's no infringement by definition, right? So what's the issue?
This is a huge powergrab by our industry - it is the only industry in the world that gets both patent and copyright protection. Think about it, you can patent a car engine, but you cannot get copyright on it. You get copyright on a book, but you can't patent a book.
Also that's mostly US. By contrast, in Europe, software is generally not patentable.
Also that's mostly US. By contrast, in Europe, software is generally not patentable.
The schematics, engineering drawings, 3d models, CAD files, process documentation etc for making a car engine (or anything else) are all copyright protected. So how exactly is software special?
that's very different - does not stop me copying a car engine and selling my knockoff.
I can buy a car engine, modify it and sell my modification.
Supplimentary documentation, and schematics are a separate matter - but engine itself is not protected. Software itself is protected, you can do nothing..
I can buy a car engine, modify it and sell my modification.
Supplimentary documentation, and schematics are a separate matter - but engine itself is not protected. Software itself is protected, you can do nothing..
One is theory, second is practice. Here is some discussion about this patent:
https://encode.su/threads/3863-RANS-Microsoft-wins-data-enco...
https://encode.su/threads/3863-RANS-Microsoft-wins-data-enco...
1. In patent law an idea is a creation that has been imagined but not yet prototyped, produced, or manufactured and they can be patented. Products with usefulness are patentable. Including algorithms used in software, and process (act or method of doing something)
2. In the US prior 2013 that was often the case. In 2013 US switched from first-to-invent to first-to-file system to be more compatible with the rest of the world.
2. In the US prior 2013 that was often the case. In 2013 US switched from first-to-invent to first-to-file system to be more compatible with the rest of the world.
That is a common misunderstanding of first-to-file. Under first-to-file, prior art is absolutely still a defense, and much easier to prove than under first-to-invent. If you publicly disclose something before someone who invented, but did not disclose, the same thing, your publication counts as prior art. It is much easier (read: cheaper) to demonstrate that "X document was published on Y website on Z date" than it is to start doing discovery to compare private lab notebooks or whatever to decide who really invented the thing first.
First-to-file is mostly about simplifying the complicated litigation edge cases where two people claim to have invented, but not disclosed, the same thing during the (US-specific) one-year grace period they have to file a patent on it.
Prior art may still not invalidate the patent, though. Usually the patent holder will argue that their patent differs from the prior art in some respect (you can often find these arguments in the patent's file wrapper at http://patentcenter.uspto.gov/). But that narrows the scope of the patent, and being your own prior art is a pretty good defense against infringement.
First-to-file is mostly about simplifying the complicated litigation edge cases where two people claim to have invented, but not disclosed, the same thing during the (US-specific) one-year grace period they have to file a patent on it.
Prior art may still not invalidate the patent, though. Usually the patent holder will argue that their patent differs from the prior art in some respect (you can often find these arguments in the patent's file wrapper at http://patentcenter.uspto.gov/). But that narrows the scope of the patent, and being your own prior art is a pretty good defense against infringement.
Shades of LizardTech v. ERM I hope not.
That was a US filed in 1999, decided 2005 patent case over mid 90s use of discrete wavelet transforms in image storage, and the progressive loading of very large images rather than the prior full scanline by scanline loading of the dialup era ...
[0] https://en.wikipedia.org/wiki/LizardTech,_Inc._v._Earth_Reso....
Court cases over patents on mathematical techiques and their implemantations really pisses me off .. being called as an expert witness even more so - it's more excruciating than teaching first year engineering students linear algebra . . . (I'll let myself out).
That was a US filed in 1999, decided 2005 patent case over mid 90s use of discrete wavelet transforms in image storage, and the progressive loading of very large images rather than the prior full scanline by scanline loading of the dialup era ...
[0] https://en.wikipedia.org/wiki/LizardTech,_Inc._v._Earth_Reso....
Court cases over patents on mathematical techiques and their implemantations really pisses me off .. being called as an expert witness even more so - it's more excruciating than teaching first year engineering students linear algebra . . . (I'll let myself out).
Editors wanted to make the standard freely available (one of them even wrote an open letter [1]) but for now it is paywalled. I personally worked with a recent community draft which was circulated in the JPEG XL discord.
[1] https://twitter.com/jonsneyers/status/1420765059739914243
[1] https://twitter.com/jonsneyers/status/1420765059739914243
"JPEG XL discord" - man I feel like I'm really getting old and falling out of the loop. Discord to me is that young people/gamers walled garden platform, for voice chat and sharing meme gifs.
Discord has replaced many forums, sadly. They're even rolling out a special forum feature right now that (obviously) can't be indexed by Google.
Public post-based discussion is moving to quick chats in private servers. It started out with Slack spaces but has moved to Discord because of Slack's inferior UX/UI/business model.
This makes taking part in a community a lot easier as you can actually talk to the people working on the stuff you're excited about, like you could with good ol' IRC except you don't need to log in at the exact right time to send them a message. Some open source projects opt to use Matrix rather than Discord or Slack, which is an open standard but the problems still remain.
Especially, finding a solution to an obscure error message can be a real challenge if you don't want to join some random chat room full of existing conversations to ask the question yourself, even if ten or twenty people before you already did the same. I much prefer the forums for this type of stuff but most of the world seems to disagree.
Public post-based discussion is moving to quick chats in private servers. It started out with Slack spaces but has moved to Discord because of Slack's inferior UX/UI/business model.
This makes taking part in a community a lot easier as you can actually talk to the people working on the stuff you're excited about, like you could with good ol' IRC except you don't need to log in at the exact right time to send them a message. Some open source projects opt to use Matrix rather than Discord or Slack, which is an open standard but the problems still remain.
Especially, finding a solution to an obscure error message can be a real challenge if you don't want to join some random chat room full of existing conversations to ask the question yourself, even if ten or twenty people before you already did the same. I much prefer the forums for this type of stuff but most of the world seems to disagree.
> It started out with Slack spaces but has moved to Discord because of Slack's inferior UX/UI/business model.
Having never used Slack, this statement astonishes me. It is difficult for me to imagine a worse UX/UI than Discord is.
Having never used Slack, this statement astonishes me. It is difficult for me to imagine a worse UX/UI than Discord is.
If you don't pay Slack, they limit everything, including search, to 10,000 messages.
This is particularly bad for projects with a high-traffic general chat, and low-traffic chats which are topic-oriented, because the 10k limit is per 'server' not per chat, anything low traffic ends up having little to no history visible.
This is particularly bad for projects with a high-traffic general chat, and low-traffic chats which are topic-oriented, because the 10k limit is per 'server' not per chat, anything low traffic ends up having little to no history visible.
My time with Slack is mostly over but it always surprised me with how popular it still is. I've always found Slack to be slower on my machines despite both Discord and Slack being Electron based. Slack has some serious memory usage bugs every now and then and lacked many features built into Discord for years now.
Discord copied the channel system Slack uses but allows for fast and easy switching between workspaces. Slack lacks that, there's a dropdown somewhere but every workspace asks me to create a separate account rather than giving me the option to reuse an existing one, even when I enter the same email address I've used elsewhere.
Slack got off to a good start but it's like they stopped innovating at some point. I don't remember any new feature they've added that other chat apps don't already have.
Discord is also free with paid features per account (that most people don't really need imo) whereas Slack keeps your messages hostage if you don't pay (you van only scroll back a certain number of messages but once you start paying you can read them again).
Their model is clearly oriented at businesses paying subscription costs per user within their organisation. Discord's allows for much more organic server creation because anyone can join for free and only those who need the extra features need to pay.
One benefit of Slack is that it gives some kind of guarantee in regards to data processing. Discord isn't business oriented so its setup isn't great for companies who don't want their data to leak. Last time I checked, Slack's guarantees were a lot stronger than Discord's.
This can lead to pretty funny hybrid use. I've seen people have digital meetings over Discord (because Discord's voice and video channels are excellent) with Slack open for sharing text, documents, and all other kinds of attachments. Using Discord is probably against company policy (mandating stuff like Google Meet or Zoom) but the Discord UX is so much easier than many competitors. Its performance is also pretty good! During COVID lockdown my university gave some lectures over Discord when the dedicated video lecturing system (set up for a few small lectures a week rather than hundreds of people joining tens of lectures around the clock during working hours) got overloaded and went down hard. It took the university weeks to get enough capacity for their streaming setup and switching to Discord took one suggestion and an hour or so of setting up for every teacher.
I think the difference between Discord and all other companies is that Discord is clearly targeting normal user adoption, luring people in with easy to use features and tools, whereas its competitors target corporate contracts, locking down a whole group of users at once that don't really have a say in their messaging platforms.
I don't think Discord cares much about the business market but with a few small adjustments (i.e. only accepting accounts with a certain email suffix into a certain server, allowing an organisation to pay for Discord for all users within a guild) I bet they could start competing with Slack quite easily.
Discord copied the channel system Slack uses but allows for fast and easy switching between workspaces. Slack lacks that, there's a dropdown somewhere but every workspace asks me to create a separate account rather than giving me the option to reuse an existing one, even when I enter the same email address I've used elsewhere.
Slack got off to a good start but it's like they stopped innovating at some point. I don't remember any new feature they've added that other chat apps don't already have.
Discord is also free with paid features per account (that most people don't really need imo) whereas Slack keeps your messages hostage if you don't pay (you van only scroll back a certain number of messages but once you start paying you can read them again).
Their model is clearly oriented at businesses paying subscription costs per user within their organisation. Discord's allows for much more organic server creation because anyone can join for free and only those who need the extra features need to pay.
One benefit of Slack is that it gives some kind of guarantee in regards to data processing. Discord isn't business oriented so its setup isn't great for companies who don't want their data to leak. Last time I checked, Slack's guarantees were a lot stronger than Discord's.
This can lead to pretty funny hybrid use. I've seen people have digital meetings over Discord (because Discord's voice and video channels are excellent) with Slack open for sharing text, documents, and all other kinds of attachments. Using Discord is probably against company policy (mandating stuff like Google Meet or Zoom) but the Discord UX is so much easier than many competitors. Its performance is also pretty good! During COVID lockdown my university gave some lectures over Discord when the dedicated video lecturing system (set up for a few small lectures a week rather than hundreds of people joining tens of lectures around the clock during working hours) got overloaded and went down hard. It took the university weeks to get enough capacity for their streaming setup and switching to Discord took one suggestion and an hour or so of setting up for every teacher.
I think the difference between Discord and all other companies is that Discord is clearly targeting normal user adoption, luring people in with easy to use features and tools, whereas its competitors target corporate contracts, locking down a whole group of users at once that don't really have a say in their messaging platforms.
I don't think Discord cares much about the business market but with a few small adjustments (i.e. only accepting accounts with a certain email suffix into a certain server, allowing an organisation to pay for Discord for all users within a guild) I bet they could start competing with Slack quite easily.
Nowadays Discord is used for all sort of things. If you don't want to join the Discord server, you may reach editors and they are probably willing to hand out the most recent draft.
Thanks for this, this must be a huge amount of work. A bicephal codec like JPEG XL is very intimidating to implement.
Indeed. I worked on J40 for last 4 months of my unemployment (and I'm available for work wink), and it took one or two months to get each major feature---modular and VarDCT---working.
Hire this man.
As you can see it is only mature in the sense that it implements a large subset of the specification, and it has tons of rough edges (I know, I know, proper tests and fuzzing are in progress). I also didn't expect this to weigh more than 5K LoC, so my hope is to produce a parallel Rust version in the future.