The greatest failure of our patent system was…

Arithmetic encoding patents in JPEG images.

To be clear, I strongly oppose software, semiconductor design, and business method patents. That’s a longer discussion. So I was looking at how much time/money/innovation we actually lose from patents. IMO, the most damaging set of patents to the world are the ones covering Arithmetic Coding in the JPEG format.

As an example, check out this image.

Here are two links for larger versions. Can you see both in your browser?
Huffman Compressed
Arithmetic Compressed

These two images are the same except that:

  1. The Arithmetic version is 6% smaller than the Huffman version (231k vs 246k).
  2. Your browser probably can’t display the Arithmetic version.

In fact, you can’t display the Arithmetic version in any broswer that I’ve tried, including IE and Firefox. You also can’t load them in Photoshop CS 5.1 or the windows photo viewer. The only program I could find to read them is JpegCrop which you can find at

So, what’s the deal? If you have a JPEG that looks identical but is magically smaller, why aren’t we using it? Simple: Patents. What’s even worse, no one has actually gained from this patent. Rather, everyone lost, including you. And you are continuing to lose every day by paying more for bandwidth and waiting longer for pages to load.

1: Remember GIF? It was killed because of patents.
Ready for a trip down memory lane? Remember the early days connecting to the internet? You know, using your 3200 baud modem to surf AOL/Prodigy/CompuServe?

Back then, GIF was the standard for storing lossless images online. But then came Unisys. Unisys realized that you couldn’t write a GIF reader/writer without infringing on their patent. So they started suing people, and it was a huge mess. Check out the wikipedia entry.

Ultimately, Unisys tried to go after developers after-the-fact. I don’t think they actually made much money in the long run. But they did manage to show us the danger of software patents.

There doesn’t seem to be much long term harm though. As a result, the PNG format came about. It was modified just enough to not infringe on patents, and its compression was just as good as GIF. So while the transition was a pain, eventually we got a format that was just as good for lossless images.

2: JPEG and Arithmetic/Huffman Coding.
Here’s where everything went awry. JPEG came out around 1990 as a standard for lossy images. As a quick background, there are 3 steps to JPEG compression.

  1. The data is transformed using the Discrete Cosine Transform or (DCT). This step is lossless.
  2. The data is chopped, removing the least significant bits. This step is lossy.
  3. The resulting data is compressed using either Huffman coding or Arithmetic coding. This step is lossless.

So whether you use Huffman or Arithmetic coding has no effect on the actual resulting image. They should be pixel-accurate (unless I’m missing something). All that changes is the size. Arithmetic coding is basically “just better”. It gets better compression ratios. It’s not a lot better, but 6% improvement with no downside is pretty good.

But there is a downside, and that is patents. You can find a quick list at wikipedia: As a result of having these patents, the guys who made the format were scared to use Arithmetic encoding in JPEG. So while it’s part of the official format, most image readers and writers only support Huffman coding.

3: Aftermath.
Thanks to these patents, we pay for this every day. Every time you download a JPEG on your smart phone today or over a 1200 baud modem in 1993, it takes 6% longer and consumes 6% more bandwidth. Btw, that 6% is my experience. If someone has better numbers, please share. That’s for every person on the planet who is online. When you add that up, that is HUGE!

On top of that, those patents have now expired, but due to inertia we can’t really go back. Photoshop CS 5.1 doesn’t open them. Chrome/Firefox/IE don’t open them. Due to the difficulty of changing formats, we seem to be stuck with Huffman coding for the near future.

But the worst thing? No one benefits from this. In the Unisys case, they tried to sue, and for better or for worse they seem to have made some money. But to my knowledge no one who owned the Arithmetic Encoding patents actually made large sums of money enforcing it. So this innovation that could have had a huge aggregate impact on the world is basically unused. Sure, arithmetic encoding is used in other places, just not for the images that we download every day. And even though the patents have expired, we still aren’t using it for JPEG. That sucks.

IMO, this is a fundamental failure of the patent system. There is nothing wrong with companies like IBM filing for patents. They need to do that to prevent other companies from patenting IBMs idea and then suing IBM! And to my knowledge they never threatened to enforce it. Rather, these companies used the patent system in the most ideal, benign way, and the net result is that everyone loses. That’s why I think that the Arithmetic Coding patents are the greatest fundamental failure of our patent system ever in the software world. But if you have a better example, please share!

14 Responses to “The greatest failure of our patent system was…”

  1. Aren’t Arithmetic Encoding patents almost expired?
    Would be nice to be able to finally use these …
    We don’t have software patents here in Europe, but considering Europe isn’t isolated in softwareland, it doesn’t do us much good 🙁

  2. Actually, they are expired. So to support them, all you have to do is download libjpeg and enable one #define.

    The hard part though is that every application from needs to update their code, including cell phones. And developers won’t feel the need to do that until there are a lot of images in the wild with arithmetic encoding. Which won’t happen until applications support them. Classic chicken and egg.

  3. Interesting article!
    Can I be sued for using a patented rendering technique even if I didn’t knew that the technique was patented?

  4. Hi Tiago. To answer your question: Definitely.

  5. Mm, Thats weird, i could load it just fine with Chromium, im using Archlinux if that matters(maybe it is enabled by default here).

    Anyway, about Tiago’s question, if you’re in other country can you still get sued?

  6. Interesting. Maybe it works fine in Chromium but not in Chrome?

  7. Probably is time to file bug reports at major browsers for not following JPEG specs and make them advertise the arithmetic coding support by sending the HTTP header:

    Accept-Encoding: gzip,deflate,jpeg

    That way servers could start to send the arithmetic encoded jpegs now. This was the way that gzip compression was introduced. I did not have to wait 10 years to start to using it.

  8. Let’s do it. I’ll write a strongly worded email to their support staff…surely they will take action immediately. (-:

  9. OK, I have a better example: a JPEG 30% file size reduction without perceptual degradation and fully compatible with existing JPEG decoders.

    Here’s the papers:


    Here’s the patent:

    The fact is two years later there are still no such JPEG encoders on the market.

    Compared with this, 7% is peanuts.

  10. Nemo: Wow, nice find. Now I’m even more depressed…

  11. Unfortunately, that’s a loophole in the patent system: having a patent without any obligation of putting the patented product on the market or the method being applied on the industry.

    Trademark law is not so dumb, because a trademark can be revoked, if a competitor proves that it hasn’t been used for five years (at least in my country and probably in the EU, because these kind of laws is quite uniform).

  12. It’s actually worse than that. It’s not a loophole–that’s the expected behavior. The ideal is that you have an army of individual inventors, and then they sell the idea for someone to actually build it.

    And that’s actually a good thing in many cases. If you can think of a better contraption to peel onions, there is nothing wrong with filing a patent and then licensing that patent to a company to actually build it. If you were to bar non-practicing entities from enforcing patents that would cause lots of problems for physical goods.

    The one major major problem that I keep going back to is the cost of defending against patent infringement. In the tech world, I hear that it costs between $2m and $5m to defend. So if the patent troll asks for $1m, you are better off just paying them off because even if you are right you lose $2m to $5m. The troll gets paid which then makes the problem worse.

    That’s why cops don’t negotiate with kidnappers…if they were to start paying them off then you kidnapping would become profitable and and kidnapping would skyrocket.

  13. I have a special treat for you.

    An even better (worse) example: a JPEG 40-45% file size reduction without perceptual degradation by using the algorithm mentioned in post 9 adapted for arithmetic encoding:

    Here’s the paper:

    And here is the patent:

    Oh, the joys of patents funded by public money, whose products never come to the market.

  14. I find the Arithmetic jpeg works in Chrome, though perhaps it was updated between the time this blog post was written and my comment.

    However, living in Europe I believe we don’t have software patents (though I’m not sure if that’s a per-country basis or EU specific)