Google plans to patent compression algorithm already in public domain

[LigH]

arsTechnica: Inventor says Google is patenting work he put in the public domain (https://arstechnica.com/tech-policy/2018/06/inventor-says-google-is-patenting-work-he-put-in-the-public-domain/)

Jarek Duda invented a highly speed optimized kind of Arithmetic Coding named Asymmetric numeral systems (https://en.wikipedia.org/wiki/Asymmetric_numeral_systems) (ANS).

Google now wants to file patents for using this algorithm specifically in video coding. Even though they promise to "license on permissive royalty-free terms", and claim they don't want to patent the generic algorithm, just the specific use in video codecs, Duda questions their motives and their rights (knowing the algorithm in PD as "prior art" and lacking "invention" for just describing a specific use of a generic algorithm).

[nevcairiel]

This topic is about a year old, arstechnica is just behind the times

https://news.ycombinator.com/item?id=14751977

[Ghitulescu]

Yes, it is possible (for Google to patent it).

However, they can sue smb. for infringements only for the "video" part.

Second however: if the examiner at USPTO would consider that inherently the generic algorithm would be practically tailored for video applications he might refuse it for obviousness. For instance, if the algorithm public papers disclose potential uses in video, then it may also be killed with novelty. It would pay for Duda to file a reasoned document before USPTO - I do not know how these things work there but it may be something he can use to draw the attention to his rights before the patent will be issued. If issued, it will then be costly to combat.

[blurred]

While nobody doubts that Google has no problem eating real inventors for breakfast, this patent situation brings important questions regarding the future of video/image compression:
1) Can Google's competition now safely consider ANS for image/video compression, e.g. MPEG for h.266?
2) Is it technically a good idea: first switching from binary CABAC to e.g. 16 size alphabet in AV1? If so, which entropy coder would be more appropriate for such 16 size alphabet?

For AV1 there has finally won daala range coder - using 16 multiplications per symbol (by CDF for all symbols), and so turning out ~7x slower in software than better compression obtained by rANS: https://sites.google.com/site/powturbo/entropy-coder
In contrast, rANS uses only one multiplication per symbol (by f[s] = CDF[s+1] - CDF[s]), being much faster at least in software (more energy efficient in hardware), but requiring additional buffer for encoding (e.g. once per thousand/million of views of youtube/netflix video). Also 16 size alphabet is used for example in Dropbox DivANS: https://blogs.dropbox.com/tech/2018/06/building-better-compression-together-with-divans/

Here is one discussion which can be summarized that Google behaves like dog in the manger: showed lack of competence to use rANS savings, and tries to patent it so that competition also cannot - https://encode.ru/threads/1890-Benchmarking-Entropy-Coders?p=56945&viewfull=1#post56945
Here is another: https://forum.doom9.org/showthread.php?p=1845147#post1845147