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.
- The Arithmetic version is 6% smaller than the Huffman version (231k vs 246k).
- 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 jpegclub.org
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.
- The data is transformed using the Discrete Cosine Transform or (DCT). This step is lossless.
- The data is chopped, removing the least significant bits. This step is lossy.
- 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: http://en.wikipedia.org/wiki/Arithmetic_coding#US_patents. 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.
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!