Third time's a harm? Microsoft tries to get twice-rejected encoding patent past skeptical examiners

In June, 2019, Microsoft applied for a US patent covering enhancements to a data encoding method known as rANS, one of several variants in the Asymmetric Numeral System (ANS) family that form the foundation of data compression schemes used by Apple, Facebook, Google, various other companies, and open source projects. Its US …

[Anonymous Coward]

The patent system is thoroughly broken.

It's incredibly unlikely that there are a thousand things in a given year that are innovative enough to be worthy of a patent. But with the current system hundreds of thousands are granted.

Most of these "inventions" are utterly trivial.

It needs to be stopped. Perhaps a thousand is a good number, prohibit governments from granting more than 1000 patents per year, and grant all of them on the last day of the year after ranking all the potential patents.

Or just destroy the whole thing. The system as it exists is an utter failure, no patents at all would be better for society than what we have now.

[Doctor Syntax]

A simple solution. Challenge to granted patents is taken out of patent offices' hands but any patent successfully challenged by negligence of a patent office results in the office being responsible for all the challengers' costs and damages resulting from any lost income.

Just watch the number of successful patent applications fall.

[gobaskof]

1000 patents is still 1000 too many

Even when there were few patents they got in the way, just look at the steam era. James Watt, was an incredible engineer who gave us separate condensers, governors, double acting engines, parallel motion linkages etc. He turned steam engines from a niche inefficient pumping machine into machines that powered the industrial revolution. But Watt refused to licence his patents, slowing the innovation of others. To avoid cross licencing with others he had to circumvent the already emerging patent landscape. For example he created complex and inefficient schemes to turn linear motion into rotary motion because the crank was patented. Efficiency of steam engines hardly improved in the later years of Watts monopoly, and then increased by a factor of 5 in the following 30 years or so. Not to mention the vast increase in the availability of steam engines once Watts monopoly was broken.

Yes we need a way to reward true innovation, and James Watt was truly innovative. But patents are awful at this. This is why in the years following the Watt era the greatest engineers of the next generation (including Isambard Kingdom Brunel) campaigned to end patents entirely. The problem is not just the number of patents. It is assertions that innovation comes as single leaps of brilliance rather than the result collective work, and that people would stop being innovative without the reward of a monopoly. 16 years of monopoly stifled innovation in the 1700s (well more if you include patenting further incremental improvements afterwards). With the pace of innovation today 20 years of monopoly, even for the best of ideas, it patently absurd.

[SloppyJesse]

Re: 1000 patents is still 1000 too many

... "20 years of monopoly, even for the best of ideas, it patently absurd."

Oh, I see what you did there.

[Drat]

Patents are used to create nation state commercial advantage but each states patent office granting generously to local companies/inventors, then due to the globalisation this can cause ripples in all other markets. It is a bit of a battle, why make your own patent authority more rigorous when your overseas competitors make theirs more lenient for their own local businesses.

Getting rid of the whole patent system might make people less willing to share ideas and breakthroughs. Perhaps a better solution would be to have one global patenting authority that can offer the required amount of rigour on examination (and thus reduce the number of spurious patents) and at the same time reduce drastically the costs of patenting?

[sgp]

I don't buy that. Sharing ideas is fundamental to all and any science we have. As said in a comment earlier, there is not one invention or breakthrough idea where a lightbulb just appears above the inventor's head.

[Andy the ex-Brit]

Yes, this

Just a couple of years ago, a high level technical manager called me in his office to solve a technical problem that caused us warranty issues. He described the problem. I'm an engineer with expertise in related devices. I thought about it for less than ten seconds and made a recommendation.

"We can't do that. [Competitor] has patented it."

[Anonymous Coward]

Prior Art.

That is all.

[Eclectic Man]

Re: Prior Art.

It should be, except the US patent office granted a patent on Basmati rice:

https://www.theguardian.com/world/2000/jun/25/anthonybrowne.theobserver

"The battle over who controls the world's food supplies has escalated dramatically with the Indian government launching a legal challenge in the United States against an American company which has been granted a patent on the world-renowned basmati rice.

It is thought to be the first time a government in a developing country has challenged an attempt by a US company to patent - and thus control the production of - staple food and crops in what campaigners dub the 'rush for green gold'.

Basmati rice, sought-after for its fragrant taste, was developed by Indian farmers over hundreds of years, but the Texan company RiceTec obtained a patent for a cross-breed with American long-grain rice."

AlthoughI believe that was overturned after due consideration.

[bombastic bob]

Re: Prior Art.

YES. This is EXACTLY what I was thinking!

[IGotOut]

Jpg xl?

Interesting idea, but how many people actually use jpg2000 which already does much the same thing? Anyone? Come on, must be someone out there.

[Ken Hagan]

Re: Jpg xl?

I thought jpeg2000 was never used because the patent position was unclear, so I'm not sure what your point is. It sounds like there is prior art here, in the form of the actual inventor who wants it to be public, so if MS are allowed to kill it with legal FUD then we are all the losers.

[Shardik]

Re: Jpg xl?

You’ll find it in the CCTV arena - notably Avigilon use it extensively.

[Steve Davies 3]

Just when many were thinking...

that Microsoft had turned over a new leaf and was being more friendly towards Open Source software...

Then we get this.

Prior Art should work but you never know the USPTO. As they are apparently strapped for cash (fill in the blanks here).

[Anonymous Coward]

Re: Just when many were thinking...

The USPTO collects more fees for continued prosecution than it does for allowance. (But until recently, they were not even allowed to keep the money.)

[Norman Nescio]

JPEG XL

JPEG XL really, really needs to be patent/royalty free, because it is a very well thought out upgrade to the ubiquitous JPEG. Not least, it allows lossless conversion/transfer from the original JPEG format into the new JPEG XL format (obviously the original JPEG was not lossless), while decreasing the file size, which seems a bit like magic.

It incorporates techniques from FLIF* (now to be deprecated in favour of JPEG XL), which allow progressive downloads, so you download only as much of the data as needed to produce an image in the size and resolution you require: i.e. you can use the same source file to deliver a thumbnail or a highly detailed multi-mega-pixel image.

When I last looked JPEG XL had not gone though all the necessary committees, but the file format is agreed (frozen), so it won't change.

Rent-seekers on this incredibly useful image format upgrade should be extremely strongly discouraged by all legal means necessary.

ISO/IEC JPEG WHhitepaper on JPEG XL

Reference Software

Cloudinary Blog (Jon Sneyers): How JPEG XL Compares to Other Image Codecs

72 Slide presentation (Google Drive) - JPEG XL "The next-generation “Alien Technology from the Future” (Last updated Feb 26, 2021)

*The FLIF developer says: "All the good stuff from FLIF went into JPEG XL. In lossless compression, jxl is slightly better than FLIF, while it decodes faster. I stopped working on FLIF and I think JPEG XL can do everything FLIF can do and more."

[Wade Burchette]

Re: JPEG XL

I wonder how JPEG XL compares to HEIF, which Apple uses by default on their devices and which seems to be gaining support from other companies too.

[DS999]

Re: JPEG XL

HEIF/HEIC is based on the HEVC codec which is part of the h.265 standard. If you already have an HEVC license, which is pretty much de rigueur on modern devices that do high resolution video, HEIF/HEIC is free, so there's little incentive to adopt JPEG XL. That's doubly true if Microsoft succeeds in patenting it.

[Anonymous Coward]

Re: JPEG XL

If you are paying for a codec like HEVC in your GPU (which when I am watching Netflix is indistinguishable to any other codec they could use) then how is HEIC free?

Where is the money that pays for the license coming from?

[DS999]

Re: JPEG XL

If you are paying for a codec like HEVC in your GPU (which when I am watching Netflix is indistinguishable to any other codec they could use) then how is HEIC free?

I thought it was pretty obvious from my post, but I guess not. HEIC/HEIF is basically a single frame HEVC video (i.e. key frame) If you are licensed for HEVC patents (i.e. using an OS or device that includes legally licensed HEVC capability) then that OS/device is also fully licensed to use HEIC/HEIF.

So for Apple, who pays for an HEVC license in the iPhone already (though the net cost is probably zero or even negative since they are also one of the larger members of the HEVC patent pool) it was "free" to use HEIC/HEIF for better photo compression. "Free" in terms of "they didn't have to pay any addition license fees above what they already pay for HEVC".

People need to remember that there's no such thing as a truly free image compression algorithm, or at least there is no guarantee it will remain free, unless it is so old that all patents potentially used in it have expired. All newer schemes are vulnerable to someone coming along claiming their patent is used in the implementation of a particular scheme, which has happened in the past (remember Compuserve and GIF, Nokia and VP9 and there are other examples)

Of course HEVC is not immune to this, but its use is now widespread enough that most patent owners who think HEVC infringes on them will have already come out of the woodwork. For something with very little adoption like JPEGXL, there is always a risk of someone appearing on the scene claiming their patent is being infringed - being open source is no defense if infringement is proven in court. What's more, the patent owners have incentive to hang back and wait to see if a codec becomes widely adopted before pouncing. Unlike with trademarks there is nothing preventing you from being aware your patents are being infringed and waiting to file until a time of your choosing.

[Anonymous Coward]

Re: JPEG XL

"If you already have an HEVC license, which is pretty much de rigueur on modern devices that do high resolution video, HEIF/HEIC is free"

Translation: if you pay for an HEVC license, you can use it.

While I do expect HEVC to be widely adopted, it is likely to take 5+ years before it reaches a level where it could be used. But I maybe being optimistic.

[Anonymous Coward]

Re: JPEG XL

"it is a [completely unnecessary] upgrade to the ubiquitous JPEG"

Anyone who has an internet connection that can play video has no problem with the size of JPEGs. If you want good quality, don't compress your image at all. Only content providers have a reason to push this patented crap.

[Norman Nescio]

Re: JPEG XL

"it is a [completely unnecessary] upgrade to the ubiquitous JPEG"

As an 'end-user', you are completely correct.

However, if you are serving images from a central server, saving storage and bits/second adds up. The average individual doesn't care, but an organisation curating a large set of images can save on storage costs; and if serving images out to a large number of viewers, can benefit from the bandwidth savings - a per cent or so on a bottom line of millions of dollars/pounds/euros is worth having.

You don't have to stop using JPEG. There are, however, features of JPEG XL which might be of interest to others.

• You can transcode existing JPEG files reversibly to JPEG XL without any generation loss. JPEG XL files are smaller, as JPEG XL stores the JPEG data more efficiently
• A lot of work has gone into removing JPEG artefacts (which show up badly in JPEG at high compression levels) suck as blockiness and colour-banding
• The maximum bit depth is 24-bit (integer) or 32-bit (float), with up to 4,100 channels.
• JPEG XL is not so cpu intensive as the video-codec based still image compressors.
• JPEG XL allows animation (like GIF) - but if you want to encode video, it is better to use a dedicated video-codec, as JPEG XL doesn't try to work in that space - no inter-frame prediction, for example.

So JPEG XL offers the same, or better capabilities as JPEG, GIF, and PNG. No-one is going to force you to change, but some people might like the ability to choose and benefit from some of the optimisations and development in image compression technologies since JPEG.

It's absolutely fine that you don't want to use JPEG XL. You have that choice, and choice is good. The problem is that Microsoft's move to patent software in this area could well remove the ability to choose for many people (at least until the patents expire), and give Microsoft a revenue stream founded on work that was intended to be open and royalty free for all.

If JPEG fits your use case, that is great, and no-one is saying you can't continue to use it. JPEG XL might fit other people's use-cases better, and I think giving people the ability to choose to use it is a good thing.

NN

[Anonymous Coward]

Re: JPEG XL

I don't mind using JPEG XL. I don't want to be forced to pay a license for JPEG XL hardware that will get baked into the GPU decoder.

Fortunately, like all of the other image formats (AVIF/HEIC/WebP) this is dead on arrival.

[needmorehare]

Are you saying I could...

Repack all my thousands of JPEG photos with this new compression algorithm with zero loss of detail compared to the original JPEGs? As in pixel-for-pixel identical but smaller file size? That would be awesome.

[Anonymous Coward]

Re: Are you saying I could...

I think just repacking a JPEG will end up the roughly same size. You'd have to use new compression algorithms to get a smaller image.

[Norman Nescio]

Re: Are you saying I could...

Repack all my thousands of JPEG photos with this new compression algorithm with zero loss of detail compared to the original JPEGs? As in pixel-for-pixel identical but smaller file size?

Yes.

The white paper, linked to above, on page 2 says:

In terms of compression performance, key results are:

• Lossless JPEG transcoding reduces JPEG size by around 16% to 22%.

It uses the Google Brunsli jpeg repacker algorithm.

A medium level description of how it achieves this is in this conference presentation:

SPIE Optical Engineering + Applications, 2019, San Diego, California, United States: JPEG XL next-generation image compression architecture and coding tools

Search for "4.13 JPEG recompression" on the page

The legacy JPEG format has been thoroughly explored^18,19 over the years and most of its inefficiencies are addressed in the JPEG XL recompression format:

• more robust DC coefficient prediction is used

• AC0x and ACx0 coefficients are predicted on the base of neighboring blocks

• Huffman entropy encoding is replaced with ANS and Binary Arithmetic coding

• frequently used ICC profiles, Huffman code tables, and quantization tables are encoded as template parameters

• context modeling is used to separate entropy sources

• similar to the approach described in Section 4.8, DCT coefficients are reordered in a such way that more blocks have longer series of zeros at the end. The index of last non-zero coefficient is encoded explicitly, which is more efficient than limited RLE.

Those improvements enable 16% size savings on average in a corpus of 100 000 random images from the Internet. For larger photographic images, the savings are in the range 13%–22%, depending on the JPEG encoder and quality settings.

If you want very low level details, look at "Annex M - Lossless JPEG1 recompression" on page 127 of this document (labelled as page 135 if you follow the internal link in the contents)

arxiv - Draft International Standard - JPEG XL Image Coding System

NN

[RichardBarrell]

Re: Are you saying I could...

Simplifying a bit, JPEG has three important stages:

1. DCT (almost lossless)

2. quantisation (very lossy: this step is where you discard information on purpose to make the file smaller)

3. entropy coding (this step is lossless)

The entropy coding algorithms in JPEG aren't state-of-the-art, so if you swap out just that step for a more up-to-date alternative, you can get a somewhat smaller file with exactly the same meaning.

[Anonymous Coward]

There is a reason that JPEG is still around...

...JPEG does what people need.

There are too many file formats to count, but if your only selling point is "I do a thing xx% better than the file format everyone uses" then you don't get traction.

That's why h264, JPEG, PNG, WAV don't go obsolete - the replacements don't solve a problem that most people have (with a possible exception of 4k video).

If JPEG XL comes with incompatibility with existing software, and patent worries.... ...then the better solution is to just buy a bigger SD card. Isn't it something silly like $1 for 10 Gb these days?

[Martin an gof]

Re: There is a reason that JPEG is still around...

But h.264 supplanted MPEG2 essentially on the basis of n% better encoding. MPEG can be used for HD video, in much the same way that h.264 can be used for 4k, it just makes sense to use something more efficient. Generally speaking, all it takes is one standards body to give it the nod and, hey presto, everyone begins using it.

The downside is the more onerous en/decoding. Grief, remember when it was only possible to watch a DVD on your computer if you had a separete MPEG graphics card capable of overlaying video on your normal card's output?

Then graphics cards were developed which were powerful enough to do the decoding themselves, first with the aid of dedicated chippery, then in the GPU, and now MPEG decoding is achievable in software even on the lowliest CPU, while it also decodes the audio and looks after your desktop.

JPEG XL only needs a couple of things: decoding support in image 'using' applications, and a couple of phone and camera manufacturers to switch to the format for storage. People will begin using it, probably without realising (like Apple's new format) and quite honestly, without caring, unless something breaks.

M.

[sgp]

Re: There is a reason that JPEG is still around...

The driving force behind h264 replacing MPEG2 as per your example was streaming. If you are YouTube or Netflix then having the most optimal codecs makes sense. At the same time, most consumer devices nowadays are more than capable to do the number crunching.

[Martin an gof]

Re: There is a reason that JPEG is still around...

Streaming? Really? I would have considered the advent of HD video in the form of BluRay / HDDVD the initiator, given that they were being developed for several years before Netflix launched streaming services, and at the point that Netflix launched streaming (2006 according to Wikipedia, the same year that consumer BluRay and HDDVD products became available), most people had network connections which would have struggled to support streaming (I think 2006 was the year when my 512k ADSL was upgraded to ADSL "Max", and I had friends still relying on 33k6 and 56k modems, though admittedly not for very long after this point).

h.264 also enabled solid state camcorders which IIRC also became available around 2006. According to Wikipedia, YouTube didn't begin HD streaming using h.264 until late 2008. At this point camcorders were still the "thing to have" - cameraphones were still limited, at best, to VGA resolution. I had a Sony k800i back in 2006 or 2007, widely regarded as one of the best cameraphones of the era, yet it only recorded video at QCIF resolution. h.264 enabled affordable high definition camcorders using robust SD (or MS or CF) cards, which quickly pushed all preceding analogue and digital tape formats out of the market and also sounded the death-knell for hard disc-based camcorders.

To make one of these things useful to consumers, video software on the desktop and consumer playback devices simply had to support h.264.

In other words, a couple of standards bodies mandated h.264 for "consumer" devices, and the rest (e.g. streaming) followed on, or at least, that's the way I've always looked at it.

M.

[Anonymous Coward]

Re: There is a reason that JPEG is still around...

MPEG2 wasn't quite good enough for 1080p video. It has fixed block sizes of 16x16 pixels, so when the resolution increased it was working on screen areas that were too small.

Having said that: Blu-ray (h264) never fully killed off DVD (mpeg2) because it was % better and $5 more. So kind of a good example of not being "better enough" for the consumer market to upgrade.

It can be argued that JPEG, PNG, h264, and 640k are good enough for anyone. We are very definitely in the area of diminishing returns now... Any form of patent cost will kill the viability of a new format.

[Martin an gof]

Re: There is a reason that JPEG is still around...

I've done HD in MPEG2 - for some years I had an ION-based Atom-powered machine playing videos. To start with these were DVD quality, and it managed to play two different videos in two instances of VLC on two separate screens quite happily (one screen was 1280x1024, the other 1920x1080, only one video had sound), but when we started receiving HD videos it couldn't cope with h.264. Atom on the official Intel GMA platform was barely capable of one SD video in my limited experience.

Instead I re-coded the things into MPEG2 and it was fine. Not efficient in terms of storage, but much easier on the processor. Eventually the machine was upgraded to an AMD A8 with integrated graphics which is quite happy to decode two h.264s simultaneously.

M.

[Claverhouse]

Oh God, Oh Microsoft...

[Anonymous Coward]

MS has money to burn

Of course, they may eventually be allowed claims so narrow as to be useless in practice but frightening enough to send "friendly letters".

[Anonymous Coward]

Re: MS has money to burn

'frightening enough to send "friendly letters"' => not useless

[Mathman]

Nope

This seems like a fundamental misunderstanding of the patent system. A granted patent means very little. Hobbyists and academics are free to do what they like as long as it's for experimental research. And commercial companies would need to be sued, at which point there is an opportunity to examine the legality of the granted patent in a legal setting. In reality a small company would simply point to prior art and if it's clearly a non inventive patent that is already seen in the prior art, the patent owner is likely to back down rather than face an expensive court case they are likely to lose.

[drgeoff]

Re: Nope

" ....point to prior art and if it's clearly a non inventive patent that is already seen in the prior art .."

In which case the patent should never have been granted.

[Anonymous Coward]

Re: Nope

What will happen is you get sued and go to your lawyer, you pay your lawyer. Then you can spend more money and go to court a couple of years later and maybe win.... More likely the patent owner will offer you a licence at a price that is annoying, but preferable to going through to the hassle.

So - your theoretical result only applies if someone like Microsoft, Google or Apple decides to invalidate the patent, rather than paying the owner to go away. It's not something that most companies would do.

In any case, if there is a patent on code you effectively can't distribute it under the GPL, as the GPL requires you are required to license the patent for everyone.

[SImon Hobson]

Re: Nope

As AC says, that is not how it works. I vaguely recall reading that it will cost at least $1/4m - yes, a quarter of a million $ to defend a patent infringement case IF YOU WIN ! And just because there's obvious prior art doesn't guarantee a win.

So yes, if the target is a big outfit, then (eventually, it'll take years) the patent would get invalidated. For most small businesses, that's not something they could support - so the trolls offer them a licence fee they can stomach and laugh all the way to the bank. Of course, that licence fee then goes into suing the next victim - armed with "X agrees it's valid, they've taken out a licence".

Of course, if you do try and defend the infringement accusation, then you also risk losing. In which case, anything you did after being told that you infringed - such as continuing to ship product - could be classed as deliberate infringement and ... kerching, punitive damages on top of what was already claimed.

Sadly, ditching patents (and copyright) altogether would be no less bad than what we currently have. Consider a world where you could spend possibly years researching and developing ${something} - safe in the knowledge that anyone can come along and simply take what you've done and use it for nothing. There's no incentive to invest in real development work when you can simply "steal" everyone else's. So it would largely stop - or be confined to larger businesses who might have the clout to stop others stealing their efforts (probably by dirty tricks), or you'll see more and more "sealed units" that you can't get into and see what is going on.

Such a situation would particularly hit the stereotypical "garden shed boffin" as they'd have no way of monetising anything they developed. At present, they can get a patent and then licence/sell it to someone who has the ability to get it to market as a product. Without that ability, as soon as their development became public knowledge, then businesses would simply use it without paying anything.

[Eclectic Man]

Re: Nope

"Such a situation would particularly hit the stereotypical "garden shed boffin" as they'd have no way of monetising anything they developed."

Sadly even 'great' inventors can lose out on their first invention.

Trevor Bayliss made virtually nothing from his clockwork radio (designed so that people with intermittent electricity supply could still listen to announcements).

(Sir) James Dyson made nothing out of the revolutionary 'ball barrow'.

The inventor of an amazing heat-resistant paint called 'starlight' and demonstrated on BBC's Tomorrow's World program* was so concerned that he'd be ripped off that he died without licensing it. The recipe is held by surviving members of the family, but are still too scared of being ripped off to market it.

*A raw egg was painted with it, and then subjected to the heat from a blowtorch live on air. After about a minute of heating the egg was broken open and shown to be completely raw.

[Anonymous Coward]

Re: Nope

You obviously know nothing about the mathematics of leverage and the power of monopoly. Long long before Adam Smith. Kings and popes monetized their power by handing out monopolies for salt, the right to trade, or selling indulgences. Control of all means of trade was the key to power, and power meant control of all means of trade. It is a pronounced local minima system, and far from optimal.

[gobaskof]

Re: Nope

"Hobbyists and academics are free to do what they like as long as it's for experimental research." - Very much depends on the country and the type of patent. Perhaps you have misunderstood some of the fundamentals yourself?

[Eclectic Man]

Further news

Apgoosoft Corp is now applying to patent Pythagoras' Theorem, claiming that the ability to make right angled triangles makes the creation of previously patented rectangles(TM) too easy and it should receive a royalty from all manufacturers of rectangular objects or anything which contains a right angle. The US Patent and Trademarks Office has yet to comment...

[unbender]

Re: Further news

These triangles of yours - do they have rounded corners?

Asking for a litigious fruity friend.

[ThatOne]

Innovation and access to MONEY! LOTS OF MONEY!

> "The Patent Office is supposed to promote innovation and access to knowledge"

The US Patent Office is only there to create tools for Patent Trolls to do business with. As the article already said, the Patent Office's only concern is to increase fee collection patent application, so anything goes. The number of patents disrespecting the requirements of novelty/innovation and lack of prior art are astounding: If you pay enough, you can patent about anything.

I wonder why nobody hasn't patented fire or the wheel yet, they'd be good moneymakers...

[DJV]

I wonder why nobody hasn't patented fire or the wheel yet

I quite like the idea of tying all the idiots in the US Patent Office to a large wooden wheel and setting fire to it - would that be close enough?

[MrBanana]

Prior misdemeanours

Microsoft has previous history in the art of pushing their own version of standards on the world. How many ISO committee members were "encouraged" by Microsoft to sign off on their interpretation of the Open Document Format, when it had blatant flaws in it that benefited only Microsoft.

[Pinjata]

Arithmetic compression in JPEG is another example

The original JPEG standard support arithmetic compression that IBM patented. This patent has expired now but because of the patent pretty much no software support arithmetic compression. IMHO a major historical blunder that should be used to highlight the problems with software patents.

All existing JPEG (Huffman encoded) can be transcoded losslessly to arithmetic compression resulting in approx. 9% smaller file sizes.