[theora-dev] What sort of math i required?

[Christoph Lampert]

On Thu, 11 Dec 2003, Mike Melanson wrote:

> On Thu, 11 Dec 2003, Martin Jeppesen wrote:
> 
> > Why are people still using Huffman? Haven't there come better algorithms
> > since?
> 
> 	Hey, if it works...but there are some alternatives. Most notably,
> there is something called arithmetic coding which offers better
> compression than Huffman. There is placeholder support for it in the JPEG
> spec and probably other specs. The big problem with using it is that
> someone has a patent on it and has not been shy about enforcing it. Oh,
> and arithmetic coding is also really, really slow, on both sides (coding
> and decoding).

CABAC (Context Adaptive Binary Arithmetic Coding) is part of MPEG 4 Visual
Part 10 (aka AVC, aka H.26L, aka H.264). It's about 10 percent more
effective than the also permitted CAVLC (Context-Adaptive Variable Length
Coding).  See here: 

http://bs.hhi.de/~wiegand/csvt_cabac_0305.pdf
 
> 	Off the top of my head, there is something called Rice coding.
> This is still Huffman coding, but in a pattern that follows a certain
> statistical model. I have read that it is used in Meridian Lossless
> Packing (MLP) used to compress DVD audio, as well as in Free Lossless
> Audio Compression (FLAC).
> 
> 	There is also something called Golomb codes. They are used in
> H.264 (from which SVQ3 and probably other methods are derived). I am not
> sure if they are a type of Huffman codes or something different.
> 

AFAIK, Rice is a special form of Golomb (and the most often used): 

http://members.optushome.com.au/emikulic/code/rice/
http://www.tutorgig.com/encyclopedia/getdefn.jsp?keywords=Golomb_coding

Golomb is kind of a very simple way of storing values in variable-length,
with strong preference of small absolute values. It's easy to parse, and
and don't need a lookup table for VLC, on which again there is some kind
of stupid patent (at least on MPEG's 3D run-level-end VLCs). 

 > Does there excist a wavelet codec today?
> 
> 	Intel Indeo Video versions 4 and 5 are supposed to be based on
> wavelet theory (as opposed to earlier versions which were VQ).

RealVideo with Scalable Video Technology is also sometimes assumed to be 
wavelet-based, but as far as I have heard, it's not, but they use
something "fractal". 

Christoph

P.S. For understanding of huffman/cabac/golomb you need some
knowledge about probabitily density functions, but that's more likely to
be taught in computer science "Information theory" than in a maths course
"probabitily theory". 

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