What is the Asymmetric numeral systems (ANS)?
Widely used, data compression is a coding operation necessary to reduce the size of data transmission or storage. This computer operation consists in transforming a given series of bits into a series of shorter bits that can render the same information, or related information, by using a decompression algorithm. There are therefore two main families of compression algorithms: lossless compression algorithms that restore after decompression a series of bits strictly identical to the original. And the lossy compression algorithms that restore a sequence of bits that is more or less close to the original depending on the desired quality. The former are used for archives, executable files or texts, while the latter are useful for images, sound and video.
For lossless data compression, we mainly distinguish between entropy coding (Huffman coding and arithmetic coding mainly) and algorithmic coding. Arithmetic coding allows equivalent or better compression (as the case may be) than that of Huffman coding, but it was little used because its implementation was too complex, and therefore expensive in terms of calculation. This is where the ANS comes in.
Asymmetric numeral systems (ANS) is a family of entropy encoding methods introduced by Jarek Duda, a researcher at Jagiellonian University, which has been used in data compression since 2014 due to improved performance compared to previously used methods. ANS combines the compression ratio of arithmetic coding with a processing cost similar to that of Huffman coding.
With these benefits, the ANS has been rapidly adopted by technology companies. For example, it has been used in Facebook's ZStandard compression algorithm. Apple has also incorporated it into its LZFSE compression algorithm. Google did the same, using this technique not only in its Draco 3D graphics compression library, but again for its image format for the Web called Pik. All this was possible because Jarek Duda decided to put his work in the public domain.
But as we reported a year ago now, Google seeks to patent a method of video compression based on the ANS, which has infuriated the researcher of the Jagiellonian University. "A great way to thank a poor academic from a multi-billion dollar company that advocates" Do not be evil, "said Jarek Duda. He criticizes Google for having exploited his work for free and benefited from his help to finally want to patent what he considers his work. "At one point, they gave me hope for collaboration with my university, then radio silence ... probably because of this patent process," he said. According to Jarek, if this patent is granted to Google, people will be afraid to use the ANS for image and video compression for the next 20 years, which could paralyze the method as was the case with the arithmetic coding.
Versions of both parties and what the European Patent Office thinks
What Google wants to patent is the use of the ANS method for video compression. So the question is whether Google's extra work is significant enough to be considered an invention. In Google's opinion, yes. The Mountain View firm rejects the idea that it is trying to patent the work of Jarek Duda. A spokesman for the company would have argued that the academic has just proposed a theoretical concept that is not directly patentable, while his lawyers seek to patent a specific application of this theory that reflects the additional work of engineers from Google.
Of course, Jarek Duda is not of this opinion. The researcher believes that this "invention" of Google is a simple application of the ANS to a conventional video decoding pipeline. This assertion would be based on the fact that the compression of images and videos basically works in the same way as the compression of text. If so, then ANS algorithms could be used to encode image data from a video as easily as a chain of alphanumeric symbols.
The most efficient video compression schemes represent video frames as blocks of pixels and use mathematical transformations to represent these blocks using symbols that can be efficiently compressed. The only significant innovation of Google, according to Duda, would be the use of ANS to code these symbols.
But Duda goes further by explaining that he had even suggested the exact technique that Google is trying to patent in an exchange in 2014 with company engineers. We can also see in a Google Groups discussion that Jarek Duda proposed to discuss with Google on this topic: "I would like to propose a discussion on the possibility of applying [ANS] in video compression as VP9 - it should to be more than 10 times faster than arithmetic coding, offering a similar compression ratio, "he wrote.
Based on all this, the researcher believes that Google's work is not an innovation in itself; an opinion shared by the European Patent Office (EPO). In a preliminary ruling in February, the EPO refutes the fact that Google's work is an "invention". The European Patent Office believes that the information provided by Duda in the 2014 discussion cited "would allow a qualified person to achieve [what Google has done] without having to apply creative skills. "
Jarek Duda wants Google to recognize him as the original inventor and legally guarantee that the patent is available to all, or better yet, renounce patenting the use of ANS for video compression. Google is therefore wrong to be granted the patent, but it is not yet the final decision of the EPO. And a decision is also expected from the USPTO side, the US Patent Office.
