Skip to main content

Notice

Please note that most of the software linked on this forum is likely to be safe to use. If you are unsure, feel free to ask in the relevant topics, or send a private message to an administrator or moderator. To help curb the problems of false positives, or in the event that you do find actual malware, you can contribute through the article linked here.
Topic: Vorbis development, status & patent issues (Read 117238 times) previous topic - next topic
0 Members and 1 Guest are viewing this topic.

Vorbis development, status & patent issues

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?

Vorbis development, status & patent issues

Reply #1
Quote
you are not capable of scientific discussion, and that is what HA forum is about.

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.

Vorbis development, status & patent issues

Reply #2
Quote
Fair enough, let's start a scientific discussion.


Ok, Great :-)

Quote
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.


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.

Quote
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.


Great!

Quote
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.


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

Vorbis development, status & patent issues

Reply #3
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.

Vorbis development, status & patent issues

Reply #4
Claim 1 from patent US5214742:
Quote
1. In a method of transmitting a signal including the steps of dividing the signal into successive, overlapping blocks by means of windows, converting the partial signals contained in the blocks into a spectrum by transformation utilizing window functions within the respective said windows such that the resultant of the window functions in the respective overlapping regions of successive blocks equals 1, subsequently, coding and transmitting the resulting spectra, receiving and decoding the transmitted coded spectra, converting the decoded spectra back into partial signals by transformation, and finally, joining the blocks containing the partial signals in an overlapping manner; the improvement comprising selecting the length of the respective window functions as a function of signal amplitude changes.


Then block.c in Vorbis source code does overlap/add and windowing from line 722 to 758 (latest CVS nightly).
Code: [Select]
    for(j=0;j<vi->channels;j++){
     /* the overlap/add section */
     if(v->lW){
    if(v->W){
  /* large/large */
  float *w=_vorbis_window_get(b->window[1]-hs);
  float *pcm=v->pcm[j]+prevCenter;
  float *p=vb->pcm[j];
  for(i=0;i<n1;i++)
    pcm[i]=pcm[i]*w[n1-i-1] + p[i]*w[i];
    }else{
  /* large/small */
  float *w=_vorbis_window_get(b->window[0]-hs);

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

Vorbis development, status & patent issues

Reply #5
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

Vorbis development, status & patent issues

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

Vorbis development, status & patent issues

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

Vorbis development, status & patent issues

Reply #8
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

Vorbis development, status & patent issues

Reply #9
Quote
There are some importaint points made with references to the real-world code and patent applications - they are not "gee" claims,  they are based on a relevant observations and not made up -  IMHO, they are a nice basis for a good discussion towars ability to make a MDCT window switched codec (like MP3/AAC/Vorbis/WMA actually are) without infringing cited patent.

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).

Vorbis development, status & patent issues

Reply #10
Quote
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 1 says:

Quote
1. In a method of transmitting a signal including the steps of dividing the signal into successive, overlapping blocks by means of windows, converting the partial signals contained in the blocks into a spectrum by transformation utilizing window functions within the respective said windows such that the resultant of the window functions in the respective overlapping regions of successive blocks equals 1, subsequently, coding and transmitting the resulting spectra, receiving and decoding the transmitted coded spectra, converting the decoded spectra back into partial signals by transformation, and finally, joining the blocks containing the partial signals in an overlapping manner; the improvement comprising selecting the length of the respective window functions as a function of signal amplitude changes.


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.

Vorbis development, status & patent issues

Reply #11
Quote
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.

Vorbis development, status & patent issues

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


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

Quote
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.


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.

Vorbis development, status & patent issues

Reply #13
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.

Vorbis development, status & patent issues

Reply #14
Quote
(snip) 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.

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.

Vorbis development, status & patent issues

Reply #15
Quote
Wouldn't all claims have to apply to make Vorbis infringing on this patent


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.

Quote
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.


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

Vorbis development, status & patent issues

Reply #16
Quote
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.

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.

Vorbis development, status & patent issues

Reply #17
Quote
Quote
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.

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.
Juha Laaksonheimo

Vorbis development, status & patent issues

Reply #18
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.

Vorbis development, status & patent issues

Reply #19
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.

 

Vorbis development, status & patent issues

Reply #20
Quote
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.

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.

Vorbis development, status & patent issues

Reply #21
Quote
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).


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.

Quote
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.


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.

Vorbis development, status & patent issues

Reply #22
Quote
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.

Vorbis development, status & patent issues

Reply #23
Quote
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.


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

Quote
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.


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.

Vorbis development, status & patent issues

Reply #24
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