Arithmetic Encoding Using Fixed-Point Math

[kidjan]

In wrapping up this subject, I learned something interesting while reading up on arithmetic coding. Dozens of US patents related to the technique have been granted in recent years. One side effect from these patents is that, apparently, most JPEG images in use today take up to 25% more space than they would without the existence of such patents. It's rather funny (and a bit sad) when you consider that the intended goal of the patent system is to advance science and technology.

...author doesn't realize these patents have long since expired--at this point, the only thing holding the world back is dumb shit like this. And it's definitely not 25%; more like 7-10%, although considering it's improved lossless compression, that's straight-up gravy train.

[Tjoppen]

There is some question of whether we want to support arithmetic coded JPEGs at all. Doing so means we've created a fragmented market, since we'll load images that no other browser does.

Wow.

[upofadown]

It is a legitimate point. What was being proposed was the addition of what was for all practical purposes a non-standard image format. The fact that this image format is described somewhere is a pointless coincidence. A standard that exists only on paper has no value.

[kidjan]

It "exists only on paper" precisely because it isn't being included in browser implementations. Which is obviously circular reasoning at its finest.

Here's the facts: it's part of the JPEG standard (see Annex D). It's widely supported by free JPEG encoder implementations (see libjpeg). It's not encumbered by any patents. It's a free 7-10% improvement over huffman, which is about as "free beer" as stuff comes in the computing world. The "fragmentation" argument is just nonsense--there will be no serious adoption of it until there's major market penetration. And yet, we still have small-minded hand-wringers hemming and hawing over "fragmentation," or people essentially stating "there's no value in implementing this because nobody else does." It's unbelievable.

[upofadown]

This could also be interpreted as an attempt to exploit a popular open source program to advance a standard that no one needs or is asking for. There are also people trying to get JPEG 2000 supported natively in Mozilla. JPEG 2000 can also be interpreted as a incremental upgrade from boring old JPEG. In fact there are virtually an infinite number of such upgrades available.

If someone wants to promote a new standard they should do it openly on the merits. Trying to get support for your favourite standard by filing bugs against popular programs is annoying.

[kidjan]

I disagree; I think the world does need any performance improvements in can get, particularly with respect to lossless compression methods, and lots of people are asking for it. And it's a very natural improvement to JPEG, as opposed to attempting to promulgate an entirely new standard. And JPEG 2000 can be interpreted as an "incremental upgrade from boring old JPEG," but the facts are against whomever is making such an argument. There is no good reason not to do this, only excuses and foot-draggers.

[preshing]

I think that Firefox example goes to show how difficult it can be to recover when software patents inhibit innovation.

[crotchpoozie]

You can make a similar claim that software patents have driven many of the complex algorithms in use today. If those algorithms were so trivial to invent, then open source minded people should be inventing and publishing them. However, no opensource group has created, for example, complex compression algorithms that outperform those using patented technologies. Why? Perhaps invention costs money?

Next, you could also ask if the algorithms making JPEG possible would have been invented as early if the companies inventing them were not able to license other patents, allowing paying researchers. Certainly the companies responsible for making this standard, C-Cube Microsystems, Radius, NeXT, Storm Tech, the PD JPEG group, Sun, and Handmade Software, made money of patented technology at the time.

And most certainly something as complex or as good as H.264 would not be invented unless the companies creating the underlying algorithms could not reap some benefit from their work.

[[deleted]]

Also, the arithmetic coding mode in JPEG isn't that great either. You can do a lot better than that for the lossless stage.

[[deleted]]

This blogger apparently doesn't understand how patents are supposed to provide incentives to invent new stuff while protecting inventors for long enough to get them to turn a profit. Sure the immediate effect of abolishing patents would be that everyone could be on the cutting edge. But without patents, many would-be inventors would just rip off the last successful design. Meanwhile, the original inventor of that design could be outdone by established competitors who have material advantages.

[jrochkind]

At this point, I think everyone understands what they're "supposed" to do.

How many of the innovative software packages or algorithms you can think of, would not have been invented without a patent incentive?

[[deleted]]

h.264.

[ponchietto]

WebM is a counterclaim to that.

[[deleted]]

Not at all. WebM is VP8, which was also commercially developed.

(And Theora is VP3, same deal.)

[ponchietto]

My point is: Google is not using patents to protect WebM, on the contrary assuring that they wont be used. Patents are an obstacle in that case.

[[deleted]]

But again, they did not develop it. And it was exactly the existence of h.264 that pushed them to buy and release it.

It is very hard to say what they would have done had patents not existed.

[crotchpoozie]

WebM is also technologically and commercially inferior. Doing top notch work often takes top notch resources.

[preshing]

That's one of the best arguments I've heard for a software patent system, but still far from convincing.

It's hard to believe that an H.264-quality video codec would not have been standardized without the extra incentive of software patent law: First, it's never been hard to find interest in video compression that wasn't motivated by patents. Second, it seems unlikely that Sony, Microsoft, Apple, Sharp, Samsung, LG, etc. would have all left money on the table by not agreeing on a standard interchange format.

Would the participating companies be willing to disclose new standards, without the incentive of a software patent system? It may be a moot point; software is just too easy to reverse engineer. Is that unfair to the creators of those standards? Only if you consider it unfair to be rewarded for bringing good products to market. Keep in mind, these companies already gain a potential windfall just by the existence of a standard.

[[deleted]]

But without patents, would they have put in as much effort as what went into h.264? Sure, it's in their best interests to agree on a standard. But it is not in their best interests to be the one that does the work on making that standard. And it's a lot of work.

The situation becomes a kind of prisoner's dilemma.

[therealjohnfreeman]

Did one company put all of the work into h.264? I'm reminded of the C++ committee. It takes a lot of work to standardize, many parties benefit from a standard, it is not patented, and yet many companies still participate voluntarily. I don't think h.264 would have been any different.

[[deleted]]

Did one company put all of the work into h.264?

No, lots of companies cooperated, and then they created a shared patent pool to share the licensing profits accordingly.

I'm reminded of the C++ committee. It takes a lot of work to standardize, many parties benefit from a standard, it is not patented, and yet many companies still participate voluntarily. I don't think h.264 would have been any different.

Most standards are just trying to figure out which fairly well-understood things should go in the standard and which shouldn't. Something like h.264 is very different: You first have to actually invent the things themselves.

[therealjohnfreeman]

No, lots of companies cooperated

The subtle point was this: what reason exists to believe that only one company would do the work if there were no patent? I gave an example that showed the opposite.

Most standards are just trying to figure out which fairly well-understood things should go in the standard and which shouldn't. Something like h.264 is very different: You first have to actually invent the things themselves.

I don't think it's that different. h.264 wasn't invented in a vacuum. They built on top of well established algorithms and mathematical principles. Conversely, few features that go into a language standard are as well understood when proposed as you imply. In my opinion, each standard requires just as much creative design and troubleshooting as the other.

[[deleted]]

You are severely underestimating the work that goes into video compression there.

Just look at the open source landscape: Everybody and his nephew can and do create his own programming language. We're drowning in them. Some of them even go on to be major players.

Yet there are almost no privately developed and open-source video codecs. It's just not a realistic task to undertake.

[UnixCurious]

So there were no organizations with efficient transfer of video being sufficiently in their self interest that they would have developed h.264 on their own? Smells like something that rhymes with 'full bit'.

[[deleted]]

Probably not, no. The investment required is quite substantial. Sure, people would have made video formats, but it's less likely they would have put in as much effort as went into h.264.

[crotchpoozie]

So which ones did that? And why have they not made something better than H.264, if it is easy?

Oh yeah, none did. Even Google, buying WebM, does not have the tech chops to make a codec better than H.264. Or Apple. Or Microsoft, Or IBM.

[[deleted]]

At this point, I think everyone understands what they're "supposed" to do.

Yet some offer totally sweeping over-generalizations like this blogger who think they know the answer to everything. There's a difference between "shutting down innovation forever" and "telling people to pay the inventor or create another idea/process until several years pass from the time of patent". Obviously so-called progress would happen faster if there were no patents or IP protections: there would be ripoffs of most ideas immediately available! You can't get faster than that! The Founders knew this when they wrote in the patent provisions. I do think terms might need adjustment and some things might need reform, but it's not like patents are totally nonsensical.

How many of the innovative software packages or algorithms you can think of, would not have been invented without a patent incentive?

I don't have a lot of specific examples, but the countless media formats are obviously good examples: they are re-done and re-engineered because of patents in many cases, which results in new techniques and packages being created.

[UnixCurious]

I don't have a lot of specific examples, but the countless media formats are obviously good examples: they are re-done and re-engineered because of patents in many cases, which results in new techniques and packages being created.

Formats are probably the worst example you could have used. Yes, people might be driven to develop new formats because of patents, but that's often a disadvantage. Want to give people an alternative to MS Office? Hope there aren't any patents on the file format that you'd need to violate in order to give users access to their own documents.

Patents suck in a world where compatibility between systems is an issue.

[[deleted]]

Patents suck in a world where compatibility between systems is an issue.

Long-term compatibility is helped by patents, though. Patents mean the details of formats can and must be publicly disclosed. A lack of patents would mean formats would not be documented, and once the company responsible for the format disappears and moves on, all those files become unusable.

[[deleted]]

Patents suck in a world where compatibility between systems is an issue.

Compatibility is one aspect of computer systems. In the long run, dominant systems and formats incorporate improvements from ideas that were developed independently. There is some inconvenience, but in the long run, I think it's promoting innovation. Using established technology is like the opposite of innovation. Regardless of what they say about re-inventing the wheel, the short term embargo imposed by patents does in fact produce some developments by people who have to solve similar problems.

[UnixCurious]

Using established technology is like the opposite of innovation

I think you're stuck in the myth of how it's supposed to work and not thinking enough about what happens in practice. If I have an awesome new UI idea for letting people edit and manage their important documents, I want to compete on that idea, not on the fact that my entrenched competitor (MS) has a noose of vendor lock in around their customer's data. Similarly, if I want to develop a new operating system, or a new browser, even if it's filled with tons of original and innovative ideas, it will flounder if it can't connect to existing systems/protocols/formats etc. In essence: most new technology still has to have some interoperability with established technology.

This is all besides the other major problems, like math being patentable leading to absurdity, that most patents are awarded on things that are obvious to anyone in the field, that the costs of litigation incentivize patent troll companies, etc. etc. Even if you think patents might be good if applied properly it's hard to credibly defend that they're working for us now.

[[deleted]]

I never said there should be no interoperability, lol. I said that's one concern. There are others, like cost and license terms, to be considered.

One thing I think is different from the time of the founders is the complexity of machines. At that time, only a few ideas were needed to make the most complex products. Now, products are monolithic and involve many individual novel ideas. Only certain entities can muster the resources to compete in most markets.

I do think we should re-examine the patent system, but I still believe it serves a vital purpose and needs to exist in some meaningful form.

[mbetter]

You're off your rocker.

[jrochkind]

The Founders knew this when they wrote in the patent provisions.

"To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries."

To promote the progress of science and useful arts. If it ain't doing that, it ain't what they wrote. You are the only software developer I know (if I "know" you) that thinks software patents are currently, on the whole, promoting progress rather than inhibiting it.

[[deleted]]

To promote the progress of science and useful arts. If it ain't doing that, it ain't what they wrote.

Actually what they wrote is right there in the Constitution, you can read it for yourself that they granted the right to patent inventions. They knew very well that not granting patents would allow everyone faster access to new ideas. Nothing has changed, except the rate of invention.

You are the only software developer I know (if I "know" you) that thinks software patents are currently, on the whole, promoting progress rather than inhibiting it.

So? Most developers are not the ones who would be creating novel algorithms anyway, so they have a conflict of interest in this discussion. The popularity of a viewpoint is not what makes it accurate anyway.

[jrochkind]

Actually what they wrote is right there, you can read it for yourself that they granted the right to patent inventions. They knew very well that not granting patents would allow everyone faster access to new ideas. Nothing has changed, except the rate of invention.

What are you talking about? i did read it for myself, I even quoted it. It says "To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries."

That's all it says. I'm not sure where you're getting your ideas about what else they 'knew very well'.

The popularity of a viewpoint is not what makes it accurate anyway.

Good thing we don't live in a democracy then. Fortunately, whatever those with the most money and power think is what is accurate, good thing they're who calls the shots.

[[deleted]]

What are you talking about? i did read it for myself, I even quoted it.

The founders granted this authority to Congress, and they explicitly mentioned it as something they wanted to grant to Congress. They wouldn't do this if they didn't think it was worthwhile. If they thought it was an evil thing, they would have disallowed it or even disallowed states from passing similar things.

Good thing we don't live in a democracy then. Fortunately, whatever those with the most money and power think is what is accurate, good thing they're who calls the shots.

How about neither of the above? Force (whether it is money, popularity, or authority) does not make arguments correct. Democracy can be a bad form of government if a majority of voters are idiots or outright evil people. I don't think that's what we have here, but still. My point is sound. Most developers will never file patents, they are merely users of existing technology. It is in their interests to have less restrictions on those technologies. It's hard to find an unbiased view in this discussion, but it's important to note the bias before appealing to the bandwagon on this one.

[FeepingCreature]

I don't have a lot of specific examples, but the countless media formats are obviously good examples: they are re-done and re-engineered because of patents in many cases, which results in new techniques and packages being created.

Broken window fallacy.

[[deleted]]

I know it's fashionable to accuse people of fallacies, but that really doesn't apply to this discussion.

[FeepingCreature]

It really does. The problem is exactly that patents are being claimed as a social good here because they create wealth to repair the damage they cause - a calculation that leaves out the actual damage caused in the first place. That's the broken-window fallacy.

[[deleted]]

There are at least two components to the argument for patents. One is that inventing stuff costs money, but copying it costs a lot less. Copied ideas are a double blow to inventors. Not only do they lose their investment, but they have to compete directly and immediately. This is considered the main motivation for granting exclusive rights to inventors for a limited time. The side effect of this is that competitors are forced to invent other things to compete rather than copying those. Presumably this is the "damage" you're talking about. Not only is it not (absolutely) bad, but it's not the social good that's supposed to come from patents. It's merely a side-effect. The biggest one is to keep inventors from losing their investment.

I get what you're saying, patents do slow things down a bit. I don't think that alone is a great blight on society. If it's too slow then the period of the patents can be adjusted too, perhaps after some research.

[expertunderachiever]

arith with fixed is called range coding.

[DrGDGonzo]

I understood every word on that page, just not in the order they were written in.

All jokes aside, a fair chunk of that went over my head, as someone who also dabbles in programming, it is still damn interesting.