Moderator comment
Currently the Vorbis patent issue covers these threads:
Vorbis development, status & patent issues PART 1 - NON-technical discussion
Vorbis development, status & patent issues PART 2 - Technical discussion (This thread)
/Moderator comment

By looking at this:
http://www.xiph.org/archives/vorbis-dev/20...2/index.html#83
it seems that Xiph (at least in 2000) was open to the idea of disclosing the patent research.
Is this position changed now, or does it still stand?

Fair enough, let's start a scientific discussion.

You have mentioned a patent on switched MDCT filterbanks with overlap and add. It is a scientific fact that Vorbis uses a similar method.

Now, does this prove whether or not Vorbis infringes on this patent? No. One has to look at the specific claims in the patent, and the specific methods used by Vorbis. Unless somebody brings credible evidence that there is a specific claim in the patent that Vorbis specifically infringes, I must assume that Monty is aware of this patent (he'd be a fool not to be aware of it, since it is so blatantly similar), and determined that it does not apply to Vorbis, since I am unfortunately not qualified to make such a determination myself.

I would like to hear Monty and/or Jack's opinion about this, but they are currently not available for comment. However, at least Jack will be at the Monthly Meeting.

I am sorry if I personally insulted anyone, that was not my intention. I happen to be a strong believer in the need for patent-free technology, and I do apologize if my passion for this cause has gotten the best of me.

Ok, Great :-)



It has been brought:

US 5,214,742

Page 7 (Claims)

Claim 1, maybe 2 , Claim 3, Claim 4, 5, 6, maybe 7, 8, 9

They might look pretty much applicable in Vorbis IMHO, at least by brief looking at block.c and window.c in Vorbis CVS.



Great!



Well, being a believer is one thing - it interferes with science a lot But certainly is a virtue, no matter how good is the cause

One more thing - the claims are not related to any specific windowing function, claim 1 states that resultant of the window function equals 1, and does not state any specific window function - SIN, SIN^2, KBD and any other satisfy this. And I believe that Vorbis window function also satisfies this, otherwise it wouldn't be perfect-reconstruction filterbank.

Claim 1 from patent US5214742:


Then block.c in Vorbis source code does overlap/add and windowing from line 722 to 758 (latest CVS nightly).

etc...

And of course it does MDCT. Now the only possibility I see that this doesn't infringe the patent is if the window does not behave as claimed in the patent.

Menno

1.3. High-level Decode Process

It seems that the Vorbis specification itself gives the answer about the window function, see 1.3.2.3.

Menno

Ok, so we have a pretty clear basis for a serious scientific discussion, eh c_haese?

I've already said everything I'm qualified to say. When there are details, you'll hear about them then.

Well, at least there is a nice bunch of factual data about US5214742 that needs to be proven as not relevant - altough I believe that most claims of the patent are probably met in a nice way

Of course... there might be some hidden catch and really the way to avoid it - and I really think that Xiph guys thought about how to avoid that one, but let's wait the official response and a nice and polite scientific discussion, if someone decides to answer in a scientific not the personal way like done by now.

Everyone interested can view the patent:

http://ep.espacenet.com/ and type the US5214742 in the "View the patent application" box

Vorbis code that deals with MDCT overlap/add and switching is in files: block.c and window.c IMHO

I followed your link to the actual patent and would like to share my views on the patent.

Claim 1 does not claim the "windowing/overlap-add" method but an improvement where the length of the window is selected based on a function of signal amplitude changes. By choosing a different window length selection algorithm, one could prevent infringing the patent.

Claim 4 is IMO more difficult to circumvent, since it seems to describe how to obtain transition windows.

I saw that Bernd Edler is the inventor here, since I will see him in November, I could ask for his opinion on this (he is familiar with the Vorbis codec).

Claim 1 says:



Yes, I stand corrected -

Regarding the switching criteria - it is pretty much general, as it just says that the switching is based on signal amplitude change - PE method falls to this category as well, and most methods degrade to this basic claim, no matter what kind of switching criteria they use - it is always matter of energy (amplitude) change.

First of all, do you also think that claim 1 is about the switching and not the windowing/overlap-add?

As for the switching selection, you could do it based on coding results, so compare the number of bits used when a long window was selected with the number of bits used when 2 short windows are selected (for the case where the short window is half the length of the long window). This is not nearly as efficient as most functions of energy change, but IMO different and not falling under claim 1.

Yes I agree, it is related to improvement based on switching ot short blocks.



Can be done like that - I am not a vorbis expert but it seems they do switching based on envelope band energy level difference (envelope.c) if that is actually used for window switching, and I don't know that - anyway that is not patented as far as it can't be interpreted as "signal amplitude".

But the claim 4 is kinda hard to avoid. Same for claim 6.

Yes, Claim 4 is not easy to avoid. Claim 6 points back to Claim 2, where again the issue of changing signal amplitudes is mentioned.

Hmm, but Claim 4 points back to Claim 3, which points back to...etc,etc.

If presented with the vorbis code (and possibly an explanation of its operation) and a certain patent, I would find it very hard to make any judgement still, due to the language used in patent documents.

Wouldn't all claims have to apply to make Vorbis infringing on this patent? Otherwise I could patent a piece of software, state in claim 1 that it is a method to be performed by an electronic computing device, and *BAM* I've patented all computer software ever written and ever to be written in one fell swoop, regardless of whether the other claims apply.

I'm not a patent laywer, I just posted some interesting findings regarding this patent and vorbis code - I think vorbis developers know how they avoided it, so they can certainly shed some light on the issue.



No, all claims must not be prior-art so your claim is pointless

Actually, the way patents work is that to infringe on a patent, you need to infringe on *any* of the claims. However, to infringe on a claim, you have to do something that fits the *totality* of the claim. In this case, I would say that Vorbis doesn't infringe on claim 1, due to the "as a function of signal amplitude changes" (which probably needs to be there because there would likely be prior art for the general case). If Vorbis doesn't infringe on 1, then it automatically doesn't infringe on the others because all the others include 1.

Now, why would they bother making all the other claims dependent on 1 if the fact of not infringing on 1 prevents infringement on the others? The reason is that in probably think 1 may have prior art, in which case, the other claims are still valid (provided there's no prior art on them). Otherwise, prior art on 1 would have totally invalidated the patent. Anyway, the result is still that if Vorbis doesn't infringe on 1, it's safe from 5,214,742.

Very interesting. So, if Vorbis does switching based on envelope band energy level difference, and it can't be interpreted as "signal amplitude change" -based method, then it indeed looks like Vorbis is clear with this patent.

Maybe somebody can elaborate and confirm the switching method Vorbis is based on.

If Vorbis is clear on this, then at least one of the FhG claims is countered succesfully.

I took a deeper look at the patent - It seems that this patent does not talk about switching criteria at all - they just state 'signal amplitude change' as a condition for switching to the short blocks, which is met in every codec, regardless of the actual switching method - otherwise there would be no point in window switching at all (if energy level is the same).

On page 6 they suggest that signal amplitude change of a given magnitude could be used as a trigger - but they do not state whether this is in time or freq domain - it can be both.

Window switching criteria can be either time-domain energy diff, freq domain energy diff (vorbis is using this, right?), perceptual entropy change (like MP3/AAC) or LPC predction error (Twin VQ, for example) - but I think MP3 and AAC and TwinVQ reference this patent as relevant, and it is in patent portfolio, and they do not use strict "signal amplitude change" in time domain as someone would initially think. No matter how the blocks are compared (time E, freq E, PE (THR/E), or LPC prediction error), window switch is always a result of signal amplitude change IMHO.

I mean - in my opinion, the purpose of the Claim 1 is only to faciliate the need for the window switching from long to short blocks, in case of signal amplitude change - not to elaborate the exact switching method - because the patent itself is about MDCT switched filterbank and not about the switching methods / threshold estimations. That's why they stated "signal amplitude change" only, because this is the reason for block switching in any case - no matter how you look at the signal as I already explained in my previous post.

Elaborate methods for block switching are covered in some later patents from Johnson (M/S psychoacoustic model patent - PE based switching) and Herre/Brandenburg (patent covering time-domain block switching only, dating from 1998 IIRC). Dolby AC3 uses other time-domain block switching method which might be patented but I am not sure.

No matter what the purpose of it is, it gives an interesting loop hole out of the patent. Just make sure that the block switching is not a function of amplitude changes, by for example introducing a tiny amount of randomness in the algorithm.

Not that vorbis does this, but I hope they do avoid it somehow... will be interesting to hear the result of that meeting if they address this patent issue seriously.

I think this patent is closely related (or follows from) Edler's article "Codierung von Audiosignalen mit überlappender Transformation und adaptiven Fensterfunktionen"

In that article, I see 3 innovations. First, the use of different window lengths for an overlapping transform. Then, the method of creating transition windows. And last, the steering mechanism for the adaptation of the window length. In the article, the steering mechanism is clearly based on time-domain changes in signal amplitude.

For the patent, they probably tried to incorporate as many options for switching as they could get away with.



In the examples you give (so basically all current standards ) I can agree with your last statement.

However, the example I gave previously where you adapt the window lengths based on the actual coding results is different IMO.

E.g. incorporating the rate in the switching selection could lead to situations where you do switch when a high rate is available, but do not switch when a low rate is available, even if signal amplitude change tells you that you should switch. And although those methods might be computationally complex, I do see these as a next step in future codecs.

Well, that is used in some of the codec implementations - i.e., if the bit reservoir is near 0, and there would be a high bit loss by using short blocks coder can stick to long blocks and, say, activate TNS if such tool is available (although, TNS will be automatically activated for pre-echo clips)

Also, alternative approach would be to measure the TNS gain / savings, to see if there is a real need for short blocks after the TNS, then measure bit cost and decide whether to switch to short blocks.

Or, third method would be to code both ways (long and short) - and to measure NMR to see if short blocks yielded in signal quality increase (analysis-by-synthesis)


First two methods are different from suggested approach in the patent, but somehow I think that the "function of signal amplitude change" is always incorporated in them - because any pre-echo measurement deals with short-term amplitude change? I dunno if it is legally possible to use this as an argument, probably not - as that would be too general for my taste

Third method would use different kind of switching criteria (NMR) but for good pre-echo performance, you would have to have third psychoacosutic model based on very short blocks (like ITU-R BS.1387 / Advanced Model) in order to screen for time-tomain artifacts.

Next time, let me read both your posts before I try to respond B)

You argue that the actual patent is only about window switching, and that claim 1 tries to clarify why you should switch (and why this patent is of any use).

My view is that the patent comprises 3 innovations as stated in my previous post:

1 - The window switching for overlapped transforms
2 - The method of obtaining transition windows
3 - The use of (time-domain) signal amplitude changes as a steering mechanism



This shows that it is/was allowed to make a patent of different steering mechanisms. Unfortunately, it does not offer us a solution for who is right.

If I am correct in saying that the actual steering mechanism is part of the patent, then different mechanisms are also patentable. If you are correct in saying that there is no claim in the patent on an actual steering mechanism, then there is still room for patenting specific steering mechanisms.

How is this all important for Vorbis? From your explanation of the way a patent works, Vorbis is either safe from the patent (my view) or not (your view).

I can obviously not say that either of us is right, only that I can understand that after reading this particular patent, one might have the idea that one could come up with a time-varying overlapped transform coder that is safe from this patent.

There are many of similar patents out there. For each of these, a detailed study/investigation has to be made to see where the loopholes are. As a programmer/researcher/developer, I would not be bothered by this, but as a company offering its customer "patent-free" solutions, I would make sure that I can provide a basis for my claims.

Doesn't Parseval's Theorem say that frequency domain energy is equal to time domain energy?

Even if Vorbis does the energy calculation in the frequency domain on a specific frequency band, there are ways to do the exact same in the time domain, making it a direct function of the amplitude changes. A frequency domain representation is just a different way of presenting the signal, it is still the same signal.

I find the statement "function of changes in signal amplitude" a bit strange. A signal itself is fully defined by it's amplitude changes, meaning that every method of using the signal for the switching is covered, unless you use just 1 sample . Or am I missing something here?

Menno

IIRC, on last AES conference in Amsterdam Dolby presented variable-length overlapped transform codec that uses MDCT (I think) - the purpose of this codec was to perfectly match the NTSC/PAL timing frame-by-frame, which wasn't quite possible with today's codecs. Perfect timing was needed because in case of cut/copy operations small "click" artifacts appeared due to discontinuities.

I can't remember which method they used, because I didn't buy the paper But whatever method they invented, they probably filed a patent application for it

Is that the 114th convention? I'm searching the proceedings, but am unable to find it. Do you have some more info (e.g. author, session)?

I think it was:



But don't take my word for it

Yes, but it says nothing about the distribution of energy.



I am not so sure about your first statement (naturally, I agree with your 2nd). I think it is very important in which domain you perform an operation. Take quantization for instance, a key issue in subband/transform coding is to be able to control the spread of quantization noise over the frequency spectrum. There might be ways to accomplish the same in a time-domain representation, but they are -in general- more complex.

If a method for doing this operation in the time-domain was patented, then I thnik that an operation in the frequency domain that obtains the same result is still patentable (i.e. there is an innovation).


No, I think that you're on the spot.

First of all, it is my view that the patent is (a.o.t). about changes in time-domain signal amplitude.

Secondly, there are switching algorithms based on (combinations of) rate, distortion and coding delay imaginable (and implemented) that obtain different switching results for different constraints.

What I am trying to say is that a switching mechanism based on a "function of changes in signal amplitude" will always give you the same switching result, independent of desired quality/bit rate. A function of (combinations of) rate, distortion and coding delay might give you different switching results each time a constraint is changed, even if the signal stays the same.

That's the one, very interesting, I completely missed that one.

It does look like a different switching scheme, since they change the amount of overlap.

I think we got into one very serous discussion right now, because this patent is applicable to many other codecs, some of them - not that open

It would be very interesting for the audio coding society to see what is the real influence of this patent to MDCT window switched codecs - I think the best way would be to call Mr. Edler to participiate as he is the principal inventor of the window-switched filterbank.

If patent proves to be applicable to Vorbis/WMA/... it will be quite problematic to avoid it in any further "free" codec. Otherwise, it would be a clear sign that it is possible to write audio coding-decoding system that works in MDCT domain without infringing some of the "unavoidable" patents.

Yes, or I'd rather say that is might be applicable (and probably is).



I will see Mr. Edler end of november, but I could also send a mail. I know he's rather busy and he might mot have time to answer before november anyway.



Yes, and it would be very valuable to have a list of these "unavoidable" patents and study their possible loopholes. But I assume thatthey have this list at Vorbis development ?

As for WMA, I have the idea that they do something different than window switching. See patent US6115689.

http://cvs.sourceforge.net/viewcvs.py/ffmp...=1.18&view=auto

Code took from the relevant .c file - please see copyright note for the project (link above)!:



I dunno about the patent - will take some time to analyse it carefully, but the provided ffmpeg code that is claimed to decode WMA smells like a MDCT block-switched coder with overlapped sine windows (as it could be seen in the code).

Seems that you're correct. But will the ffmpeg decoder also handle WMA9-coded fragments?

Actually, I never tried that FFMPEG code, so I am not sure. But considering the fact that MS announced plans to open WMV/WMA specifications, I am sure they probably reworked all of the code to avoid any legal problems they might have.


It is also funny how FFMPEG used some of the Vorbis code for decoding WMA streams

If they paid for licensing that patent on window-switching (or any other patent which they use), would that allow them to open up the specs?



The LSP-to-curve code? I wonder if MS patented the idea of floor coding in general or only a specific way of coding the masking curve. Again a question for Vorbis (and probably a patent) that they should consider (or have considered, in which case it would be nice to know about it).

Of course But... well, I think further elaborate on this is just not for public forum.... Discussion about who paid and who did not paid for somethign is somewhat tricky, and I feel that I am in no legal posistion to comment on that



That is also interesting, would be worth trying digging in all NTT and Microsoft patents regarding this, since they are the only companies dealing with VQ / floor coding.

recently, the official ffmpeg homepage had been closed to protest against software patents. so, they might suffer from legal problems.

regarding wma9,
afaik, it isn't supported by wmadec.c. only older versions, pre-wma9, are supported (0x160 & 0x161, that is, wmav1 & wmav2)


edit : typo

Actually, none of these patents are "software" patents (common misconception), and they are registered in USA, Japan and all EU countries more than 10 years ago - so they were "valid" even before EU adopted policy of accepting software patents.

The thing is, which is core of this discussion - is that adaptive window switched MDCT filterbanks didn't exist 20 years ago - they were result of work of H.Malvar, J. Princen, A. Bradley and, finally, B. Edler (dynamic switching) in late 80's.

yes, but I'm not going to do that

But seriously, there must be so many patents out there that potentially cover aspects of the vorbis codec. I can see that it would cost an immense amount of time (and probably money) to investigate these all, but that does not free one from the responsability for providing facts to support one's claims.


I do not claim otherwise. But I would like to see evidence from Vorbis that this is the case.

If a respected developer/researcher like Ivan is not certain whether a single patent applies to Vorbis (Ivan, if I misinterpret your postings, please correct me), how can a company be expected to obtain a view on this? Should they just accept the claim?

You are right - I am not sure, of course - I did not take claims from people from big companies for granted, I looked at the patent - and I disclosed my thoughts here.

Unfortunately, as it looks to me - this patent is very hard to avoid, and, like everyone else on this forum I guess, I would really like to see some kind of official Xiph explanation how they manage to avoid this patent in their code.

MP3 itself does not use time-domain energy diff switching method, it does not even use straight MDCT, but still - this patent is in the patent pool... so I dunno...

Well, at least I got that part right



Yes, I would like that as well. But I do think that c_haese has a point here when talking about the validity of patents. Even if Xiph would come with an explanation saying "we avoid patent X because it claims method Y while we use method Z", somebody such as yourself could come in and say "I think that patent X is not about method Y but about method A. Within method A, a method is used that could be method Y but also method Z". The accepted way of determining who is right in the case of patents would be to go to court.

So all Xiph could say is "we think we avoid patents A,B,... because this and this"

Which is off course better that the current situation.

FFmpeg already uses several patented techniques. They have MP2 and MP3 decoders, MPEG-{1,2,4} encoders and decoders, an H.264 decoder and more. So their situation couldn't get much worse; it's already nearly impossible to use FFmpeg commercially without paying someone. The entire project goal seems to be to have as many as possible codecs with a complete disregard to patents You may already have known this, though...

Just my 0,02kr. (no € yet). Very interesting disussion, BTW!

Okay, let's get back to the scientific problem at hand. The patent we're discussing is about window switching, and specifically the method used to determine the window length. After digging through the code for not very long, that task seems to be performed by _ve_envelope_search, which in turn calls on _ve_amp. The comment in front of _ve_amp says this:

/* fairly straight threshhold-by-band based until we find something
that works better and isn't patented. */

(envelope.c, line 87, current CVS)

At the very least this tells me that Monty is aware of the patent problem surrounding the window switching and is employing a specific method to avoid patents. That's probably as official a position as you'll get, at least until the monthly meeting.

Hope this helps,

Carsten Haese.

Edit: typo fixes

Calculating energy is a function of signal amplitude. Whether it's done in time or frequency domain doesn't matter, as it means exactly the same (I explained that before).

The way I understood it, Vorbis tries to work around this patent by not doing something that is before the "improvement" part of the first claim.

Menno

Ok, for those with lmiited ability to read:

Instead making analogies, calling someone good, evil, poor, innocent, etc

Consider this like a pure technical question called:

How can you avoid US Patent #5,214,742 in a MDCT window-switched codec?

And -

- Forget the codec name
- Forget the quantization algorithm (not covered by patent)
- Forget the coding algorithm (not covered by patent)

JUST FILTERBANK and window switching model...

So - we are getting down to elementary technical level, ok?

I hope that we can get back to meaningful discussion which could have some scientific importance.

Thread re-arranged. This thread is now only for technical discussion.
All non-technical posts regarding this issue must go here:
Vorbis development, status & patent issues PART 1 - NON-technical discussion
Clearly non-technical posts in this thread will be either moved or deleted.

Currently the Vorbis patent issue covers these threads:
Vorbis development, status & patent issues PART 1 - NON-technical discussion
Vorbis development, status & patent issues PART 2 - Technical discussion (This thread)

The only technical answer to this question is in Monty's code (envelope.c pointed to by c_haese). Anything more (debating the exact meaning of the words in the patents) is not a technical/scientific discussion but rather a legal one, which I don't think can be answered (without just stating opinions) by anyone on HA (including me). That is, unless you're a patent attorney?

Ah ... so Monty speaks through source code only

Well, the code does not explain how they avoided patent. In fact, cheching the spectral envelope level is analog to checking signal amplitude level in my books (just in frequency instead of time domain) - However it does not violate, one other patent where the change in perceptual entropy (PE) is proposed as a switching mechanism - but the thing with window-switched filterbanks is still in place, IMHO.

Furthermore, this might not be the reason why they claim they avoided the patent at all - but for all of that, we need to hear technical opinion from someone who actually invented Vorbis, because he is the only one who knows how did they avoid patents, right?

Like Danchr said - that is purely a technical discussion, because he used technical (his digital signal processing proficiency), not legal (employing DSP experts and DSP and patent expers + hell load of lawyers), means to avoid the patents.