[vorbis-dev] another entropy coder that might be very useful

[Sebastian Gesemann]

Hi Yann,

On Tue, 27 Apr 2004, Yann Guidon wrote:

> Hallo !
:)

> Obviously, you didn't read the article completely.
You got me!

> However (warning : side note !),
> i have the gut feeling that a BWT
> (that's another more complex permutation)
> will give interesting results before a 3R step.
> First, the "permutation overhead" is only log2(n)

Actually, the BWT is a well-defined bijective transform.
No side information is needed to restore the original order.

> instead of O(log2(n!)) so we only need 6 bits
> for the "precursor pointer" (or "primary index") of a 64-samples block.
> Furthermore, it has the property of grouping most high
> values at the beginning, while leaving contiguous
> zeros at the end, and 3R LOVES that :-)

Are we discussing a "3R general purpose compressor" or does
it still have something to do with Vorbis ?

IMHO the BWT is only a good idea if there's strong correlation
between successive (discrete) symbols in the data like letters in 
english text for example. Because of the MDCT coefficients' nature
(they're mostly *uncorrelated*) it does not make much sense to use
a BWT.

I've the impression that you're tinkering around general-purpose
compression algos thinking they could be useful for Vorbis.
IMHO it's important to first understand the nature of data you
want to store compactly.

> [...]
> Compared to common pyramidal methods,
> which are usually transforms (the difference channel
> must be entropy coded by a backend algorithm
> such as Huffman or arithcodes), 3R is an encoder,
> it outputs a compacted bitstream (but it does not
> harm to preprocess the data with filters etc.).
> [...]

I'm not following you. 

> [...]
> For example, if the input data is /dev/random,
> 3R will add an overhead of 1 bit per data.
> Huffman would probably not be much better,
> it would try to optimise code lengths where
> it is not useful because we know that the
> entropy is 8b/value.
> Rice codes would
> add log2(8)=3 bits par value. [All numbers
> are means/averages]

How can you expect a decent performance of rice
codes if you try to compress uniformly distributed
random bytes ? What's the point ?

[snipped a lot]

> I turned the problem and the numbers around
> and around my head for a long while until what
> i call today 3R appeared slowly. Then, nothing.
> RR came only recently when decided to write the article.
> 
> By extension, 3R represents an interesting
> complexity / efficiency compromise when
> one has to encode small datasets with large variance,
> like FFT power spectra of distinct sounds for example.
> Or when small coefficient tables must be embedded
> in files, it can then beat Rice encoding and some data
> (could be JPEG quantisation tables) are too
> small for huffman to be viable.

Rice coding is just one tool that can be used in
conjunction with others to build a coding system that
suits your type of data. I've absolutely no idea
how you're able to compare 3R to "Rice coding".
Rice coding is a simple method that matches a certain
distribution model without exploiting inter symbol
correlations.

>> Perhaps I missed something.
> yup, but read the whole text and the small code examples
> (and particularly http://f-cpu.seul.org/whygee/ddj-3r/3r_simple.c ).

Hmm... Sorry... To be honest: I'm currently not convinced that
it is of use for any Xiph CoDec. Among other things the Vorbis I
format is already frozen.

> "even if it is not as efficient, it is Free and this reason is a good 
> enough to use it."

Uhhh...

> Plus, i love the simplicity of the 3R method.

Is it ? :-P
;)

>> [description of Vorbis' residue vectors' sample distribution]
> First, i think that a BWT might help, but i have to investigate
> that independently.

I don't want to sound rude, but you're obviously not that
experienced in the field of "source coding".
(see note on BTW above)

[huge portions snipped]

Wow...
I dont't wanna know how much time you spent on writing all
this. I appreciate your efforts... but IMHO... you should have
focused your energy on different things like understanding
Vorbis first and how the entropy coding layer currently works.

I once had a discussion with a guy who wanted to implement
a video codec with superior effeciency compared to DivX and
stuff... First, he said that he has some fresh new ideas with
which he could revolutionize the video compression world. Then
he came up with transforming RGB data to HSL and
one-dimensional Fourier transforms. He even didn't know WHY
he used the HSL colorspace and a Fourier transform. (At least
he could not answer that properly.)
In another reply he said that his sheme still needs some
optimization because the compressed version is 4 times larger
than the original.

Funny story, isn't it ?

(I hoping that you don't count this story as an insult to your
intellect or take it personally. It's just that the field of
lossy audio/video coding is very far from being trivial enough
to come up with a superior sheme within a few hours.)

<p>Greets,
Sebastian


--
PGP-Key-ID (long): 572B1778A4CA0707

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