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

http://en.wikipedia.org/wiki/Graphics_Interchange_Format#Unisys_and_LZW_patent_enforcement

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

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!

26 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:

    * http://ieeexplore.ieee.org/iel5/83/4711346/04682736.pdf?arnumber=4682736
    * http://ieeexplore.ieee.org/iel5/4378863/4379219/04379276.pdf?arnumber=4379276

    Here’s the patent:

    http://appft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PG01&p=1&u=%2Fnetahtml%2FPTO%2Fsrchnum.html&r=1&f=G&l=50&s1=%2220090317012%22.PGNR.&OS=DN/20090317012&RS=DN/20090317012

    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:

    http://ieeexplore.ieee.org/ielx5/5075165/5090078/05090215.pdf

    And here is the patent:

    http://www.google.com/patents?id=7JKaAAAAEBAJ&printsec=abstract&zoom=4#v=onepage&q&f=false

    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)


  15. Hi, nice blog!

    A few comments:

    1) to consider how much we “lose from patents” you should probably consider how much we gain, too, and then look at the net.

    2) Patent trolling is not unique to sw, semiconductors, or business patents. Perhaps we should abolish the entire patent system?

    3) You argue that arithmetic encoding has potentially earth-shaking benefits/value… but the inventors of this amazing technique shouldn’t have been allowed to patent it so that the jpeg group could do whatever they wanted. Clearly no money could have been offered since bandwidth has no economic value… Hmm.

    4) SW patents do not prevent technology from becoming part of standards. Look at qr codes. The patent system basically gives inventors an opportunity to profit from their inventions, or not.

    Just to be clear, I’m not necessarily for or against sw patents. I’m an independent researcher and have filed and prosecuted patents covering my own inventions. Until you’ve done that, believe me, you really have no clue just how f’ed up the USPTO is. I usually don’t bother to comment on the all-too-ubiquitous ’sw patents are evil’ meme. But I like your blog.


  16. Foodborne sickness is an situation of problem for all age groups. turn out to be unwell from foodborne bugs every single yr, and about five,000 of those instances are fatal. CDC studies in 2009 discovered that kids youthful than 4 experience food-related bacterial infection at a fee four.five instances that knowledgeable by adults twenty to 49..
    meilleurs chaussures de running http://www.couleurs-et-matieres.fr/nike-lunar.asp?id=meilleurs-chaussures-de-running


  17. 888 On this planet develop, just about every item has turn into extravagant. In the meantime, he’s also doing the job along with the sweatshop, authentic louis vuitton ties run by Chinese bosses, louis vuitton agendas and organizerslouis vuitton handbags in usa that manufacture the counterfeit merchandise for his sales power.
    hollister outlet stores http://www.bwhgolf.com/hollisteroutlet.htm


  18. louis vuitton sacs femme…

    茅tait si passionn茅 vif sur aide autres et donner nouveau 脿 soci茅t茅 . Elle avait exp茅riment茅 une mani猫re de m茅thode de juste capturer les coeurs de autres individus autres gens avec son personnage stimulant et a 茅t茅 le plus de loin le plus m猫re et femme…


  19. ajfkegjmnjdhbnft, Zolpidem, QRrPulT, [url=http://karenectoninteriors.com/portfolio/]Ambien online[/url], UFDOyzt, http://karenectoninteriors.com/portfolio/ Ambien no prescription us, VXTNZYy.


  20. louis vuitton wallet epi leath cheap louis vuitton replica louis vuitton mens belt new louis vuitton millionaire sunglasses outlet louis vuitton original replica louis vuitton outlet sale,up to 60% off favorite mm louis vuitton neverfull free louis vuitton catalog request hot selling replica louis vuitton backpack for cheap with safe and fast delivery louis vuitton official online store louis vuitton online sale louis vuitton outlet clearance sale online,enjoy the best quality http://www.mytoyology.com louis vuitton replica belts for men multiply louis vuitton stylish laptop bag designs louis vuitton outlet louis vuitton shoes sale buy very really cheap louis vuitton bags alekspeck.com elihornby.com/vintage-louis-vuitton-purses-c-4.html
    red bottom shoes


  21. So is actually truth which usually your girl’s dieter appearances as a result photo shop? never. As can be viewed undoubtedly clearly in it your own photograph, Aishwarya’s take on one is the most willowy compared to what it was a few months within. she will be however already lost a great deal of kilograms, understanding that television shows in their own take on,
    nike jordans price tag http://www.belasantacatarina.com.br/airmax95.asp?p=9074
    nike jordans price tag


  22. s le crocochangements ructural, les perspectives à long terme pour le rand reste faible. Toutefois, dans les circonstances actuelles,Photos jordan pas cher femme de l’action de solidarité d’étudiants de l’ULB avec les travailleurs d’Arcelor, le court terme l’orientation future du rand est très incertain, car il dépend de nombreux


  23. Hey There. I found your weblog the usage of msn. That is an extremely smartly written article.

    I’ll make sure to bookmark it and come back to read more of your useful
    information. Thank you for the post. I will definitely comeback.


  24. This I soon found out with the aid of a German deck hand. To my great disgust,coach outlet store, I ascertained that my ticket only permitted me to claim a place on the lower deck quarter occupied by the deck hands, including a sooty, bare, rough bunk. Made wise by my railroad experience,oakley prescription sunglasses, I laid in a good supply of bread and meat, and betook myself and my bag,oakleys sunglasses, with anything but a light heart,coach handbags outlet online, to the boat.. We were goi


  25. authentic Louis Vuitton M91996 cheap nike Air Jordan 18 shoes replica Michael Kors Hamilton Slouchy Medium Louis Vuitton Tambour babyliss silky smooth 8663du new arrival louis vuitton keepall sale outlet cheap louboutin black friday lv Monogram Sunshine Express North South M40795 Louis Vuitton Zippy Wallet Red Chiefs Eric Berry Jersey china Air Jordan IV Retro Laser on sale Louis Vuitton Joey Wallet replica louis vuitton monogram canvas galliera gm Michael Kors Large Logo Leopard Satchels buy louis vuitton galliera pm bag christian louboutin Tabacco 100mm red soled shoes win appeal replica Michael Kors Smooth Shiny Logo louis vuitton monogram theda pm real louis vuitton bags damier
    lv North South M40797


  26. hello!,I like your writing so so much! share we keep up a correspondence
    more about your article on AOL? I require an expert in this space to solve my problem.
    Maybe that is you! Having a look forward to see you.

    Feel free to visit my page Canada Immigration Lawyers (http://Www.Google.Ca)


Leave a Reply