8 ms·

Google is trying to patent video compression use of Asymmetric Numeral Systems

116 points by dvfjsdhgfv 9y ago

dvfjsdhgfv 9y ago
Summary from Reddit (https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/ https://www.reddit.com/r/programming/comments/6h08z5/google_...): Asymmetric Numeral Systems ([1]) is entropy coding family currently replacing Huffman and arithmetic coding in data compressors, among others, of Apple, Facebook and Google, thanks to being up to 30x faster [2]. Its author has made it public to prevent pathology of arithmetic coding, which wide use was blocked by patents for many decades ([3], [4]). However, currently others are trying to patent basic applications of ANS – including Google for AV1 video compressor (initially suggested by ANS author, who has helped them for the last 3 years: [5]) in very general patent application, to prevent others from using it in image and video compression – claims and sources: [6] [1] https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems [2] benchmarks: https://sites.google.com/site/powturbo/entropy-coder https://sites.google.com/site/powturbo/entropy-coder [3] https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents [4] Charles Bloom comment: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-patents-are-fucking.html http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa... [5] https://groups.google.com/a/webmproject.org/forum/#!topic/codec-devel/idezdUoV1yY https://groups.google.com/a/webmproject.org/forum/#!topic/co... [6] Google claims and sources: https://encode.ru/threads/2648-Published-rANS-patent-by-Storeleap/page3 https://encode.ru/threads/2648-Published-rANS-patent-by-Stor... Clarification: the "30x speedup" is for decoding of the fastest arithmetic coding (~50 MB/s) vs of ANS (~1500 MB/s) in benchmark [2] for similar compression ratio (better than Huffman, which standard implementation: zlibh from gzip has ~300MB/s). The inventor of ANS is Jarek Duda.
redm 9y ago
The title sounds like Google is doing everyone a favor. From reading the thread on encode.ru it appears to me that Google is patenting it so that they have the patent, not for purely altruistic reasons. If it was for the public good, the patent would be filed via a non-profit that Google can't control.
- ocdtrekkie 9y ago
  Or at least, that Google would pledge all of their patents if their patents had altruistic goals. There is a tiny number of patents they've pledged not to sue offensively for: https://www.google.com/patents/opnpledge/patents/ https://www.google.com/patents/opnpledge/patents/ The fact that they have not pledged most of the rest indicates that someone there is maintaining their ability to offensively sue in the future.
  - ehsankia 9y ago
    Have they ever used their parents offensively ever? The only case I know of is the Waymo one, but that was a special case where they had proof of their data being stolen. The other case would be against Microsoft but IIRC Microsoft was the one who started that case so it was technically "defensive" use.
    - ocdtrekkie 9y ago
      Companies change. You can't assume that a company not offensively using patents today will not offensively use them tomorrow. If based on some misguided belief of corporate altruism (something that very simply does not exist), you grant a company unwarranted rights, they will come back to abuse them later. Even if you have unwavering trust in Larry Page and Sergey Brin's unquestionable morals (I couldn't say this with a straight face, but anyways), the reality is, they will not run the company forever. If you've noticed something about most patent trolls, they're has-beens. When you can't compete, you sue on patents. Right now, as one of the most valuable companies on the planet with multiple products that are monopolies, obviously that does not describe Google today. But it does describe Google at some date in the future. And when Google's profits are crashing, and they're trying to figure out how to stay in business, some business exec is going to realize that treasure trove of patents can solve all their problems...
      - ehsankia 9y ago
        But we don't live in a perfect world. Someone has to hold this patent. If it isn't Google, it'll be someone else. If you can give me any other company which you think is better situated to hold this copyright, go for it. The system is broken, and this is the best we can do right now.
deleted 9y ago
[deleted]
baybal2 9y ago
>The inventor of ANS is Jarek Duda. Google has thrown few grants for ANS research to Jarek and folks of encode.ru community, then patented their research behind their backs Update: they did not, but they did approach Jarek's university with specific interest in that research work, and vaguely expressed interest in funding them. Jarek's stance - "this is my work, not yours, this ends this discussion." Google - "we have grounds to do so, and nothing you do will move us" Update: I put things in a more neutral tone.
- shawn-butler 9y ago
  Can you provide some context or links? This seems to contradict directly with what user SquareWheel writes in another comment and who now seems to have deleted that comment.
  - wolf550e 9y ago
    see https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/diuf90k/ https://www.reddit.com/r/programming/comments/6h08z5/google_... Google promising free license to anyone who implements AV1 would have been ok, if they patented something that is only useful for AV1. But they patented "using ANS for video" so now you can't use ANS in any competing video codec. In my opinion, people absolutely should fight to invalidate this patent using any work that mentions using ANS for video from a year (or more) before the filing.
    - krzyk 9y ago
      I think you can, software patents don't work in EU, you'll have just trouble doing it in the USA.
      - jandrewrogers 9y ago
        This is incorrect, you are conflating algorithm patents and so-called "business method" patents (e.g. "$BUSINESS_ACTIVITY using the computer/internet"). Proper algorithm patents are supported in Europe because they are equivalent to a novel electronic circuit, which is generally viewed as patentable subject matter.
simias 9y ago
Is it too late to consider killing software patents? I guess the battle is over and we just have to bite the bullet and be happy with these half-assed "countermeasures". I'm probably biased because I mostly read about software patent stories on HN and other similar outlets, but it seems like 99.9% of the time they're only used for patent trolling or killing the competition. Patents are supposed to protect the inventors by giving them the time to license and market them before the competition can swoop in and create a similar product without having to pay for the R&D. So do people around here have "success stories" regarding the use of software patents to actually reward creativity instead of just playing the "patent cold war" game?
- rayiner 9y ago
  I think the CMU hard drive patents are a good example: https://www.google.com/patents/US6201839 https://www.google.com/patents/US6201839. But ideally, a patent is never litigated. It simply allows an R&D house to exist as an independent entity without forcing it into becoming a product/manufacturing company. I don't know about SV, but outside SV, investors do care if your tiny little company has defendable IP. I worked at a startup doing cognitive radios. We were an R&D shop only--our competitors were companies like Raytheon and Lockheed-Martin that had manufacturing muscle. We patented everything, and most of it was what you'd call a "software patent" (even though in the long run it would be partially implemented in an FPGA or running on a microcontroller). It was expensive to pay PhDs to spend a year doing Matlab simulations to figure out what algorithms would work.[1] Even more expensive was then spending years testing those in the field (because lots of things that work in simulation fall flat in uncontrolled real-world environments). Copyright was pointless. Writing the code was the easy part. I'm a bit on the fence--I think the problems with patents are overstated, but the benefits often are too. But carving out "software patents" from other kinds of patents strikes me as odd. There is no clean line--it's often easy to take something that might be done by an ASIC and move it into software and vice versa. [1] E.g. one project involved getting disjoint listen-before-talk networks to synchronize their "listening" periods without being able to communicate with each other directly.
- beagle3 9y ago
  Patents are an offensive weapon by design. Getting a patent does not allow you to make a gadget; it allows you to sue someone else so that they cannot make a gadget. It shouldn't be surprising or unexpected or frowned upon that they are used to kill competition - that's basically their raison d'être.
burnt1ce 9y ago
Can someone please summarize the patent?
almonj 9y ago
Intellectual property is one of the worst things ever created, used extensively by that certain group of humans to hold back progress for the entire species. People in the future will view these laws as barbaric and evil. We would probably have advanced space ships, and certainly world peace and material abundance by now if not for people treating abstract ideas as property.
- ue_ 9y ago
  I broadly agree that intellecutal property isn't really property at all, and that copyright laws are unjust indeed, though I think it is hyperbolic to say that we'd have world peace and abundance just by their abandonment. More broadly the concept of property as a whole ought to come into question if we wish to go that far. Proudhon's essay What is Property? and Kropotkin's The Conquest of Bread shed light on this debate, making the case not for the sharing of private property by all but rather the very abolition of the concept itself.
nadim 9y ago
https://www.youtube.com/watch?v=ZQniEobrNU0 https://www.youtube.com/watch?v=ZQniEobrNU0
boxerab 9y ago
A previous post about this on HN: https://news.ycombinator.com/item?id=14583691 https://news.ycombinator.com/item?id=14583691 Link provides steps for people to submit prior art to USPTO for this patent application (patent is not granted yet)
- xiphmont 9y ago
  The patent does not cover rANS. rANS has been independently discovered a few times at this point. The patent filing covers Google's use of it.
rasz 9y ago
So much for publishing your work in hopes of creating prior art and preventing patent takeovers.
- xiphmont 9y ago
  I blogged about this elsewhere. From reading the filing, Google is not patenting his work. They're patenting their specific application of it, and the claims seem to me fairly tightly tailored to AV1.
  - rasz 9y ago
    so 'email .. on a mobile phone' patent? not to mention He was the one helping them with this particular application, and even mentioned it almost 10 years ago in his original paper.
xiphmont 9y ago
I will not repost the entire thing here, as there's a few naughty words born of frustration, and this might well be a family forum for all I know. My take: https://xiphmont.dreamwidth.org/84214.html https://xiphmont.dreamwidth.org/84214.html
- boxerab 9y ago
  Thanks, very interesting take on the matter. Would you mind explaining "...it has to code everything in reverse. The latter especially is a technical showstopper. " ?
gethoht 9y ago
To me what would make the most sense would to have a consortium of companies do this. Imagine Google, Facebook, Amazon, etc. all chipping in in a coordinated effort to prevent trolls from lapping up bullshit patents.

116 points by dvfjsdhgfv 9y ago

Summary from Reddit (https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/ https://www.reddit.com/r/programming/comments/6h08z5/google_...): Asymmetric Numeral Systems ([1]) is entropy coding family currently replacing Huffman and arithmetic coding in data compressors, among others, of Apple, Facebook and Google, thanks to being up to 30x faster [2]. Its author has made it public to prevent pathology of arithmetic coding, which wide use was blocked by patents for many decades ([3], [4]). However, currently others are trying to patent basic applications of ANS – including Google for AV1 video compressor (initially suggested by ANS author, who has helped them for the last 3 years: [5]) in very general patent application, to prevent others from using it in image and video compression – claims and sources: [6] [1] https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems [2] benchmarks: https://sites.google.com/site/powturbo/entropy-coder https://sites.google.com/site/powturbo/entropy-coder [3] https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents https://en.wikipedia.org/wiki/Arithmetic_coding#US_patents [4] Charles Bloom comment: http://cbloomrants.blogspot.com/2015/05/05-21-15-software-patents-are-fucking.html http://cbloomrants.blogspot.com/2015/05/05-21-15-software-pa... [5] https://groups.google.com/a/webmproject.org/forum/#!topic/codec-devel/idezdUoV1yY https://groups.google.com/a/webmproject.org/forum/#!topic/co... [6] Google claims and sources: https://encode.ru/threads/2648-Published-rANS-patent-by-Storeleap/page3 https://encode.ru/threads/2648-Published-rANS-patent-by-Stor... Clarification: the "30x speedup" is for decoding of the fastest arithmetic coding (~50 MB/s) vs of ANS (~1500 MB/s) in benchmark [2] for similar compression ratio (better than Huffman, which standard implementation: zlibh from gzip has ~300MB/s). The inventor of ANS is Jarek Duda.

redm 9y ago

The title sounds like Google is doing everyone a favor. From reading the thread on encode.ru it appears to me that Google is patenting it so that they have the patent, not for purely altruistic reasons. If it was for the public good, the patent would be filed via a non-profit that Google can't control.

ocdtrekkie 9y ago
Or at least, that Google would pledge all of their patents if their patents had altruistic goals. There is a tiny number of patents they've pledged not to sue offensively for: https://www.google.com/patents/opnpledge/patents/ https://www.google.com/patents/opnpledge/patents/ The fact that they have not pledged most of the rest indicates that someone there is maintaining their ability to offensively sue in the future.
- ehsankia 9y ago
  Have they ever used their parents offensively ever? The only case I know of is the Waymo one, but that was a special case where they had proof of their data being stolen. The other case would be against Microsoft but IIRC Microsoft was the one who started that case so it was technically "defensive" use.
  - ocdtrekkie 9y ago
    Companies change. You can't assume that a company not offensively using patents today will not offensively use them tomorrow. If based on some misguided belief of corporate altruism (something that very simply does not exist), you grant a company unwarranted rights, they will come back to abuse them later. Even if you have unwavering trust in Larry Page and Sergey Brin's unquestionable morals (I couldn't say this with a straight face, but anyways), the reality is, they will not run the company forever. If you've noticed something about most patent trolls, they're has-beens. When you can't compete, you sue on patents. Right now, as one of the most valuable companies on the planet with multiple products that are monopolies, obviously that does not describe Google today. But it does describe Google at some date in the future. And when Google's profits are crashing, and they're trying to figure out how to stay in business, some business exec is going to realize that treasure trove of patents can solve all their problems...
    - ehsankia 9y ago
      But we don't live in a perfect world. Someone has to hold this patent. If it isn't Google, it'll be someone else. If you can give me any other company which you think is better situated to hold this copyright, go for it. The system is broken, and this is the best we can do right now.

deleted 9y ago

[deleted]

baybal2 9y ago

>The inventor of ANS is Jarek Duda. Google has thrown few grants for ANS research to Jarek and folks of encode.ru community, then patented their research behind their backs Update: they did not, but they did approach Jarek's university with specific interest in that research work, and vaguely expressed interest in funding them. Jarek's stance - "this is my work, not yours, this ends this discussion." Google - "we have grounds to do so, and nothing you do will move us" Update: I put things in a more neutral tone.

shawn-butler 9y ago
Can you provide some context or links? This seems to contradict directly with what user SquareWheel writes in another comment and who now seems to have deleted that comment.
- wolf550e 9y ago
  see https://www.reddit.com/r/programming/comments/6h08z5/google_is_currently_trying_to_patent_video/diuf90k/ https://www.reddit.com/r/programming/comments/6h08z5/google_... Google promising free license to anyone who implements AV1 would have been ok, if they patented something that is only useful for AV1. But they patented "using ANS for video" so now you can't use ANS in any competing video codec. In my opinion, people absolutely should fight to invalidate this patent using any work that mentions using ANS for video from a year (or more) before the filing.
  - krzyk 9y ago
    I think you can, software patents don't work in EU, you'll have just trouble doing it in the USA.
    - jandrewrogers 9y ago
      This is incorrect, you are conflating algorithm patents and so-called "business method" patents (e.g. "$BUSINESS_ACTIVITY using the computer/internet"). Proper algorithm patents are supported in Europe because they are equivalent to a novel electronic circuit, which is generally viewed as patentable subject matter.

simias 9y ago

Is it too late to consider killing software patents? I guess the battle is over and we just have to bite the bullet and be happy with these half-assed "countermeasures". I'm probably biased because I mostly read about software patent stories on HN and other similar outlets, but it seems like 99.9% of the time they're only used for patent trolling or killing the competition. Patents are supposed to protect the inventors by giving them the time to license and market them before the competition can swoop in and create a similar product without having to pay for the R&D. So do people around here have "success stories" regarding the use of software patents to actually reward creativity instead of just playing the "patent cold war" game?

rayiner 9y ago
I think the CMU hard drive patents are a good example: https://www.google.com/patents/US6201839 https://www.google.com/patents/US6201839. But ideally, a patent is never litigated. It simply allows an R&D house to exist as an independent entity without forcing it into becoming a product/manufacturing company. I don't know about SV, but outside SV, investors do care if your tiny little company has defendable IP. I worked at a startup doing cognitive radios. We were an R&D shop only--our competitors were companies like Raytheon and Lockheed-Martin that had manufacturing muscle. We patented everything, and most of it was what you'd call a "software patent" (even though in the long run it would be partially implemented in an FPGA or running on a microcontroller). It was expensive to pay PhDs to spend a year doing Matlab simulations to figure out what algorithms would work.[1] Even more expensive was then spending years testing those in the field (because lots of things that work in simulation fall flat in uncontrolled real-world environments). Copyright was pointless. Writing the code was the easy part. I'm a bit on the fence--I think the problems with patents are overstated, but the benefits often are too. But carving out "software patents" from other kinds of patents strikes me as odd. There is no clean line--it's often easy to take something that might be done by an ASIC and move it into software and vice versa. [1] E.g. one project involved getting disjoint listen-before-talk networks to synchronize their "listening" periods without being able to communicate with each other directly.
beagle3 9y ago
Patents are an offensive weapon by design. Getting a patent does not allow you to make a gadget; it allows you to sue someone else so that they cannot make a gadget. It shouldn't be surprising or unexpected or frowned upon that they are used to kill competition - that's basically their raison d'être.

burnt1ce 9y ago

Can someone please summarize the patent?

almonj 9y ago

Intellectual property is one of the worst things ever created, used extensively by that certain group of humans to hold back progress for the entire species. People in the future will view these laws as barbaric and evil. We would probably have advanced space ships, and certainly world peace and material abundance by now if not for people treating abstract ideas as property.

ue_ 9y ago
I broadly agree that intellecutal property isn't really property at all, and that copyright laws are unjust indeed, though I think it is hyperbolic to say that we'd have world peace and abundance just by their abandonment. More broadly the concept of property as a whole ought to come into question if we wish to go that far. Proudhon's essay What is Property? and Kropotkin's The Conquest of Bread shed light on this debate, making the case not for the sharing of private property by all but rather the very abolition of the concept itself.

nadim 9y ago

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

boxerab 9y ago

A previous post about this on HN: https://news.ycombinator.com/item?id=14583691 https://news.ycombinator.com/item?id=14583691 Link provides steps for people to submit prior art to USPTO for this patent application (patent is not granted yet)

xiphmont 9y ago
The patent does not cover rANS. rANS has been independently discovered a few times at this point. The patent filing covers Google's use of it.

rasz 9y ago

So much for publishing your work in hopes of creating prior art and preventing patent takeovers.

xiphmont 9y ago
I blogged about this elsewhere. From reading the filing, Google is not patenting his work. They're patenting their specific application of it, and the claims seem to me fairly tightly tailored to AV1.
- rasz 9y ago
  so 'email .. on a mobile phone' patent? not to mention He was the one helping them with this particular application, and even mentioned it almost 10 years ago in his original paper.

xiphmont 9y ago

I will not repost the entire thing here, as there's a few naughty words born of frustration, and this might well be a family forum for all I know. My take: https://xiphmont.dreamwidth.org/84214.html https://xiphmont.dreamwidth.org/84214.html

boxerab 9y ago
Thanks, very interesting take on the matter. Would you mind explaining "...it has to code everything in reverse. The latter especially is a technical showstopper. " ?

gethoht 9y ago

To me what would make the most sense would to have a consortium of companies do this. Imagine Google, Facebook, Amazon, etc. all chipping in in a coordinated effort to prevent trolls from lapping up bullshit patents.