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

[Holger Waechtler]

Christoph Lampert wrote:
> 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). 

btw, do you know Ulrich Graef's paper dense coding algorithm and paper? 
(IIRC the paper's title was "Dense Coding, a Fast Alternative to 
Arithmetic Coding")

As far I know it's much faster than arithmetic coding and achieves 
almost the same efficience and it's not too hard to make it adaptive.

Holger

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