IPB

Welcome Guest ( Log In | Register )

3 Pages V  < 1 2 3 >  
Reply to this topicStart new topic
Vorbis development, status & patent issues, PART 2 - Technical discussion
Ivan Dimkovic
post Sep 26 2003, 09:21
Post #26


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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


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 smile.gif But whatever method they invented, they probably filed a patent application for it smile.gif
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 09:31
Post #27





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



QUOTE (Ivan Dimkovic @ Sep 26 2003, 10:21 AM)
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.

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)?
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 09:48
Post #28


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



I think it was:

QUOTE
5853
Michael J. Smithers,Brett G, Crockett,Louis D. Fielder,
Two methods of coding and delivering ultra-high quality audio are presented. Both methods are video frame synchronous and editable at common video frame rates (23.98, 24, 25, 29.97 and 30 frames per second) without the use of sample rate converters. The first is an ultra-high quality audio coder that exceeds 4.8 on the ITU-R 5 point audio impairment scale at a data-rate of 256 kbps per channel and at up to three generations of encoding/decoding. The second is an enhanced method of video frame synchronous PCM packing. Specifically the problem of transmitting 48 kHz audio in 29.97 Hz frames is examined.
Ultra High Quality, Video Frame Synchronous Audio Coding


But don't take my word for it smile.gif
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 09:49
Post #29





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



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

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

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

QUOTE
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 smile.gif . Or am I missing something here?

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.
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 09:57
Post #30





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



QUOTE (Ivan Dimkovic @ Sep 26 2003, 10:48 AM)
I think it was:

QUOTE

5853
Michael J. Smithers,Brett G, Crockett,Louis D. Fielder,
Two methods of coding and delivering ultra-high quality audio are presented. Both methods are video frame synchronous and editable at common video frame rates (23.98, 24, 25, 29.97 and 30 frames per second) without the use of sample rate converters. The first is an ultra-high quality audio coder that exceeds 4.8 on the ITU-R 5 point audio impairment scale at a data-rate of 256 kbps per channel and at up to three generations of encoding/decoding. The second is an enhanced method of video frame synchronous PCM packing. Specifically the problem of transmitting 48 kHz audio in 29.97 Hz frames is examined.
Ultra High Quality, Video Frame Synchronous Audio Coding


But don't take my word for it smile.gif

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.
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 10:04
Post #31


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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 smile.gif

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.
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 10:12
Post #32





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



QUOTE
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 smile.gif

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

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


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.

QUOTE
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, 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 wink.gif ?

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

This post has been edited by petracci: Sep 26 2003, 10:16
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 10:38
Post #33


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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)!:

QUOTE
/* build the window : we ensure that when the windows overlap
    their squared sum is always 1 (MDCT reconstruction rule) */

    /* XXX: merge with output */
    {
        int i, next_block_len, block_len, prev_block_len, n;
        float *wptr;

        block_len = s->block_len;
        prev_block_len = 1 << s->prev_block_len_bits;
        next_block_len = 1 << s->next_block_len_bits;

        /* right part */
        wptr = window + block_len;
        if (block_len <= next_block_len) {
            for(i=0;i<block_len;i++)
                *wptr++ = s->windows[bsize][i];
        } else {
            /* overlap */
            n = (block_len / 2) - (next_block_len / 2);
            for(i=0;i<n;i++)
                *wptr++ = 1.0;
            for(i=0;i<next_block_len;i++)
                *wptr++ = s->windows[s->frame_len_bits - s->next_block_len_bits][i];
            for(i=0;i<n;i++)
                *wptr++ = 0.0;
        }

        /* left part */
        wptr = window + block_len;
        if (block_len <= prev_block_len) {
            for(i=0;i<block_len;i++)
                *--wptr = s->windows[bsize][i];
        } else {
            /* overlap */
            n = (block_len / 2) - (prev_block_len / 2);
            for(i=0;i<n;i++)
                *--wptr = 1.0;
            for(i=0;i<prev_block_len;i++)
                *--wptr = s->windows[s->frame_len_bits - s->prev_block_len_bits][i];
            for(i=0;i<n;i++)
                *--wptr = 0.0;
        }
    }


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

This post has been edited by Ivan Dimkovic: Sep 26 2003, 10:50
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 10:49
Post #34





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



QUOTE
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?
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 10:53
Post #35


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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 smile.gif

This post has been edited by Ivan Dimkovic: Sep 26 2003, 10:54
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 11:01
Post #36





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



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


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?

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


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).
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 11:06
Post #37


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



QUOTE
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?


Of course smile.gif 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 smile.gif

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


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.
Go to the top of the page
+Quote Post
DSPguru
post Sep 26 2003, 11:15
Post #38


BeSweet Developer


Group: Developer
Posts: 235
Joined: 14-December 01
From: sitting on top of a supercompact cardinal
Member No.: 643



QUOTE (Ivan Dimkovic @ Sep 26 2003, 16:53 PM)
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.

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

This post has been edited by DSPguru: Sep 26 2003, 11:18


--------------------
DSPguru's Webpage - home of BeSweet & The OggMachine.
BeSplit - 7kb of A loseless AC3/AAC/MP3/MP2/WAV Cutter :)
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 11:21
Post #39


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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


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.
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 12:01
Post #40


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



QUOTE
e.g. if the complete technological details were publicly available more than 20 years ago, then this technology is patent free. If there was a patent before, it has now expired. If there was a (same, similar or encompassing) patent filed more recently, then it doesn't cover this technology.


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.
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 12:18
Post #41





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



QUOTE
Ivan Dimkovic
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.


yes, but I'm not going to do that laugh.gif

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.

QUOTE
2Bdecided
But this doesn't mean that there's no such thing as patent free.

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?
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 26 2003, 12:34
Post #42


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



QUOTE
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...
Go to the top of the page
+Quote Post
petracci
post Sep 26 2003, 14:18
Post #43





Group: Members
Posts: 95
Joined: 18-December 01
Member No.: 678



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


Well, at least I got that part right biggrin.gif

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


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.
Go to the top of the page
+Quote Post
danchr
post Sep 27 2003, 11:09
Post #44





Group: Members
Posts: 487
Joined: 6-April 03
From: Århus, Denmark
Member No.: 5861



QUOTE (DSPguru @ Sep 26 2003, 12:15 PM)
QUOTE (Ivan Dimkovic @ Sep 26 2003, 16:53 PM)
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.

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

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 smile.gif You may already have known this, though...

Just my 0,02kr. (no € yet). Very interesting disussion, BTW!
Go to the top of the page
+Quote Post
c_haese
post Sep 29 2003, 22:17
Post #45


Xiph.org Ogg Traffic editor


Group: Developer
Posts: 72
Joined: 7-July 02
Member No.: 2500



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

This post has been edited by c_haese: Sep 29 2003, 22:18
Go to the top of the page
+Quote Post
menno
post Sep 30 2003, 14:03
Post #46


Nero MPEG4 developer


Group: Developer (Donating)
Posts: 1218
Joined: 11-October 01
From: LA
Member No.: 267



QUOTE (c_haese @ Sep 29 2003, 10:17 PM)
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. */

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
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Sep 30 2003, 23:09
Post #47


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



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.

This post has been edited by Ivan Dimkovic: Sep 30 2003, 23:09
Go to the top of the page
+Quote Post
JohnV
post Oct 1 2003, 09:00
Post #48





Group: Developer
Posts: 2797
Joined: 22-September 01
Member No.: 6



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)


--------------------
Juha Laaksonheimo
Go to the top of the page
+Quote Post
jmvalin
post Oct 1 2003, 23:26
Post #49


Xiph.org Speex developer


Group: Developer
Posts: 473
Joined: 21-August 02
Member No.: 3134



QUOTE (Ivan Dimkovic @ Sep 30 2003, 05:09 PM)
Consider this like a pure technical question called:

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

...

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.

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?
Go to the top of the page
+Quote Post
Ivan Dimkovic
post Oct 2 2003, 09:21
Post #50


Nero MPEG4 developer


Group: Developer
Posts: 1466
Joined: 22-September 01
Member No.: 8



QUOTE (jmvalin @ Oct 1 2003, 10:26 PM)
QUOTE (Ivan Dimkovic @ Sep 30 2003, 05:09 PM)
Consider this like a pure technical question called:

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

...

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.

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 smile.gif

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.

This post has been edited by Ivan Dimkovic: Oct 2 2003, 11:43
Go to the top of the page
+Quote Post

3 Pages V  < 1 2 3 >
Reply to this topicStart new topic
1 User(s) are reading this topic (1 Guests and 0 Anonymous Users)
0 Members:

 



RSS Lo-Fi Version Time is now: 16th April 2014 - 14:56