[theora-dev] [OT] Just saying hi!

[Dan Miller]

Excellent overview.  As to the original question (how do we *know* a codec is patent-free), the simple answer is, we never really do.  Unfortunately, the situation is this:  Xiph does its best to put out a codec that does not infringe on anyone's patent claims.  However it is not feasible to check all relevant  patents, and even if they could, there are patents not yet issued (and therefore not accessible under US law for the most part).  Furthermore, experts can and do differ on interpreting claims and priorities of patents.  In fact there is extensive litigation on patents all the time over conflicting interpretations of claims.  The results of litigation (if it goes to trial), and even the results of settled actions, can have a huge effect on the perceived validity or lack thereof of specific patents.  No one assumes that the patent examiner did a perfect job in finding all prior art, or interpreting it correctly (nor should they; examiners are underpaid and overworked).

The fact that On2 has some patents (issued and pending) covering VP3 is actually a good thing, because it lessens the field of potential claims by 3rd parties.  Another point of reference is that On2/Duck has been developing its codec technology for 10 years, and has never, to my knowledge (I've been CTO since its inception, and CEO for two years during 1999-2000) received any correspondence indicating a challenge to its IP (Intellectual Property) from any 3rd party seeking patent royalties or attempting to interfere with the sale of On2's products in any way.

While there are indeed patents that seem to claim rather fundamental aspects of video coding, many experts in the field feel that most of these patents are over-reaching and would not stand up to a serious court challenge.  This fact is known to the patent-holders, who are very careful not to seek to enforce their patents unless they are reasonably sure they will win the fight, as if the patent is found lacking in court it becomes essentially worthless.  For the most part, these patents are part of the pool of MPEG patents administered by Dolby and MPEG-LA (strength in numbers -- the whole issue of whether creating such a patent pool is even legal under antitrust law is another discussion).  I am not aware of any case where these patents were used to claim infringement or demand royalties _except_ to extract royalties from users of the MPEG specifications.  In other words, for the most part the patent holders seem interested in going after MPEG users, not creators or users of non-MPEG codecs such as VP3 (this would seem to make MPEG-based technologies like DivX and Xvid more likely targets for action than Theora).  This could of course change, but it appears to have been the strategy so far.  After all, it doesn't make sense to sue someone unless you expect to make some money, and most of the users of open-source multimedia software are unwilling and/or unable to pay licensing fees -- they'll just move on to another technology (that's why they came here in the first place).  They're just not an attractive target for this sort of litigation.

I hope this helps clear the air somewhat.  I know that engineers and others would rather hear some sort of blanket assurance that there could never be a problem with patent-free software, but the fact is that the system is rigged so as to make such a claim impossible to make in good faith.  In the US in particular (I'm not as familiar with the European or Asian systems, though I suspect things are similar), anyone can file a patent for relatively little money, get it issued with only rudimentary research into its validity, and sit around waiting for someone to make some money who they can claim is infringing their patent.  It happens all the time, in every industry (see for example http://www.stblaw.com/FSL5CS/memos/memos1218.asp).

-dbm

> -----Original Message-----
> From: Mike Melanson [mailto:melanson at pcisys.net]
> Sent: Wednesday, February 26, 2003 10:16 AM
> To: theora-dev at xiph.org
> Subject: Re: [theora-dev] [OT] Just saying hi!
> 
> 
> On Wed, 26 Feb 2003, Christoph Lampert wrote:
> 
> > I guess there is no documentation of the current status of Theora 
> > and it's basic (technical) concepts, is there? Because 
> reading sources is
> > okay, but sometimes a few explanations make it much easier. 
> 
> 	I'm working on a description for the VP3 decode system as I
> develop a fresh decoder implementation for the ffmpeg project
> (ffmpeg.sf.net). Here is what I can tell you about the decode process
> (from which you can make educated guesses about the encode process):
> 
> * decoding a VP3 frame:
>   * decode frame header (keyframe, quantization level, version #)
>   * unpack superblock/macroblock/fragment encoding data
>   * unpack encoding mode information for encoded blocks
>   * unpack motion vectors
>   * unpack DC coefficients for all coded fragments
>   * unpack 1st AC coefficients for all coded fragments
>   * unpack 2nd AC coefficients for all coded fragments
>   *  ...
>   * unpack 63rd AC coefficients for all coded fragments
>   * reconstruct frame, which entails:
>    * prediction for the DC coefficient
>    * calculating relevant motion vector, if applicable
>    * IDCT to obtain fragment or fragment diff
>    * apply diff to motion block, if applicable
> 
> That's basically how decoding works. Note that I still haven't gotten
> heavy into the interframe coding process, so I might have some details
> confused on the motion prediction stuff.
> 
> > I'm particularly interested in how you manage to keep 
> everything free of
> > patents, in particular since I know that there are patents 
> (claimed) on
> > such trivial stuff like motion vector prediction and 
> decision when to
> > encode and when to skip a block. 
> 
> 	I often wonder the same. So here are some observations on things
> that probably set this algorithm apart:
> 
> * You probably noticed that the algorithm encodes all the DC 
> coeffs, then
> all the 1st AC coeffs, etc. MPEG certainly doesn't do that and I don't
> know of any other coding methods that do.
> 
> * Block coding: In addition to 8x8 blocks (fragments) and 16x16
> macroblocks, VP3 also uses superblocks which are 32x32, 
> encapsulating 4
> macroblocks. The order of unpacking the fragments is also 
> fairly unique.
> 
> * DC prediction: On2 used to be Duck and if you are familiar 
> with their
> algorithms (Duck Truemotion variants and the DK ADPCM 
> codecs), you know
> that they are huge DPCM fanatics. To that end, there seems to be a lot
> that goes on for DC prediction. I know that MPEG uses some DC 
> prediction,
> but I don't think it's anywhere near this level. A fragment 
> can predict DC
> using DC elements from the left, up-left, up, and up-right 
> fragments, if
> present and coded in the current frame. Additionally, there 
> is some more
> code that is effectively disabled that does a special search through
> previous fragments to the up and left of the current fragment 
> looking for
> *some* block that has been coded in this frame from which DC can be
> predicted. Aggressive strategy.
> 
> * Golden frame: VP3 calls its keyframes "golden frames". The 
> codec needs
> to maintain the last golden frame in addition to the previous decoded
> frame since motion vectors can be predicted from either.
> 
> 	If I have gotten anything wrong about anything stated above,
> please yell very loudly right now. But I hope this helps.
> 
> 	Thanks...
> --
> 	-Mike Melanson
> 
> 
> 
> 
> --- >8 ----
> List archives:  http://www.xiph.org/archives/
> Ogg project homepage: http://www.xiph.org/ogg/
> To unsubscribe from this list, send a message to 
> 'theora-dev-request at xiph.org'
> containing only the word 'unsubscribe' in the body.  No 
> subject is needed.
> Unsubscribe messages sent to the list will be ignored/filtered.
> 
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'theora-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.