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

Thu Apr 29 11:18:05 PDT 2004

Hi Yann,

<p>S>> IMHO the BWT is only a good idea if there's strong correlation
S>> between successive (discrete) symbols in the data like letters
S>> in english text for example.
Y> My "challenge" here is that the "only" is probably too
Y> conservative. I would like to verify (if not proove) that BWT
Y> can also have some benefit on some kinds of signals. If you know

Good luck!

Y> papers that investigate that, please give me a pointer.

Sorry, don't know.

Y> I have only found papers where BWT is applied on alphabets/symbol
Y> streams, they proove without a doubt that BWT can extract
Y> intersymbol correllations.

This is the only thing it does.

Y> [...]
Y> Finally, some of my experimental tests using bzip2 on
Y> preprocessed signals (bytestreams generated out of
Y> raw CD tracks) show that it can achieve very good
Y> performance. So this motivates my investigations.
Y> I think it applies to time-domain as well as frequency-domain.
Y> In the other (example) case of encoding the spectrum of a square
Y> signal, where the spectrum shows equally spaced peaks,
Y> the BWT should be able to catch these repetitions,

I don't think so.

S>> Because of the MDCT coefficients' nature
S>> (they're mostly *uncorrelated*) it does not make much sense
S>> to use a BWT.
Y> (M)DCT is several dB better than FFT to decorrellate
Y> signals, i know. But then, you say yourself "mostly uncorrelated",
Y> and compression is about finding correlation.

Because of the time frequency duality, correlated MDCT coefficients
would imply a non-flat signal shape (in time domain). This is usually
not the case because in case of transients Vorbis switches to short
transforms, in case "smooth" signal parts (flat energy distribution
in time) Vorbis makes use of long transforms. - I rest my case. ;)

Y> i've "tinkered" with several transforms, including DCT and FFT
Y> (for example, loot at http://f-cpu.seul.org/whygee/dct_fc0/dct_fc0.html )
Y> and due to my interest in lossless compression, i apreciate the BinDCT
Y> family of transforms (and the principle can be extended to "binFFT"
Y> easily). Ouch, sorry for this digression.

Since you are more insterested in lossless compression you could try
to use 3R as entropy coding variant for the prediction residual in
FLAC. Its format allows other coding shemes to be added. FLAC is also
not as complicated as Vorbis. But note: The LPC residual isn't much
correlated either.

S>> I've the impression that you're tinkering around general-purpose
S>> compression algos thinking they could be useful for Vorbis.
Y> why not ? :-)

Because they are too stupid and not specialized enough in doing
what I expect them to do for Vorbis & co. => inferior compression
efficiency.

Y> i'm not a Vorbis guru, that's why i am triyng to discuss about this
Y> subject.

I wouldn't call myself a guru either. (Though I already did private
research on the video/audio coding topic for the last 6 years.)

S>> IMHO it's important to first understand the nature of data you
S>> want to store compactly.
Y> of course.

But general purpose compression shemes DON'T understand.
You can feed'em with anything, they try to do their job
and fail to compete with FLAC for WAVs for example.

Y> unfortunately, Vorbis is far from easy to understand
Y> and there's a huge (mind)gap between lossy and lossless
Y> algorithms. And i think that 3R is useless for FLAC
Y> (and i don't like LPC either)

Keep in mind that FLAC and Vorbis are specialized compression
shemes. First they try to drastically reduce correlations via
LPC or MDCT and then to code the decorrelated samples
compactly somehow. (Of cource, the MDCT's purpose is not only
decorrelation. It also enables us to shape the quantization
noise in a time/frequency varying manner) - The BWT for
example won't have any purpose inbetween there...

Y> 3R is not much more complicated than Rice, doesn't need
Y> explicit statistical modeling (and a few other things). So,
Y> it can be worth using it instead of Rice/Gamma/Elias codes (or
Y> others) "in certain situations" (that remain to be found).

I would say 3R is already a general purpose compression sheme
which automatically tries to decorrelate the data and code it
efficiently. It's not a small & simple building block like
Rice coding is (for one purpose).

S>> Hmm... Sorry... To be honest: I'm currently not convinced
S>> that it is of use for any Xiph CoDec. Among other things the
S>> Vorbis I format is already frozen.
Y> who knows if it can't help anyway ?

I don't. - Not for sure - You could try to convince us with
a superior FLAC/Vorbis variant featuring your 3R sheme.

Y> i know that a wavelet-based Vorbis was in the air, for example.
Y> So there may still be places in Xiph world for 3R.

It may be. But I don't think it is. That's my point. I guess the
only thing you can do about this is providing some kind of proof
that 3R performs better than Rice coding for FLAC for example.
>From what I've read/seen I'm not convinced.

Y>>> "even if it is not as efficient, it is Free and this reason is
Y>>> a good enough to use it."
S>> Uhhh...
Y> don't tell me you love proprietary architectures ;-)

No, I don't. Usually I choose one of the "better"
alternatives. But it does not mean that I support
anything just because it is free.
To have a free codec like Vorbis that performs
so well in comparison to MP3 is a good thing.
No doubt.

Y> i've never said i'm a compression specialist.
Y> i've worked in many areas of data processing, from transistor
Y> to high-level applications (including some DSP, scientific
Y> computing and other funny electronics stuffs). So my knowledge
Y> is more "general culture" than "mastering". But, like
Y> any domain, there's still room for enhancements
Y> so i don't hesitate if i know that i can (try to) develop
Y> a new method/algo/approach. Then, i can know
Y> if it's valid only if i test it.

I encourage you to do so.

Y> i guess that the whole Vorbis documentation (and we know
Y> that Vorbis is not perfectly documented) is at least 10x larger
Y> than the article i wrote. Vorbis is much more sophisticated than 3R.
Y> So please excuse me if i don't have the time to understand
Y> all Vorbis' subtleties.

I guess if you are not able to convince people (who are involved in
how Vorbis works) of the features of 3R and want Vorbis to use 3R,
you're on your own. Knowledge of how Vorbis works is then required.

S>> [...]
S>> Funny story, isn't it ?
Y> this happens a lot, as can be seen on comp.compression.

Yeah, it's pretty annoying.

Y> Now, our real issue is to see where it can be used,
Y> besides the applications i have in mind.

Ok, go ahead, do further research.

Y> you see, i'm not Jules Gilbert, and if you take
Y> some tens of minutes to read the article then read
Y> and compile the code, you'll see predictable results.

I may be igrorant... or I may have just as little time
to do that as you have to read the Vorbis spec.
You have to convince people that it's worth the effort.
Yes, you are already trying to so. As for me, you did not
succeed until now. (The chance is low that it will change.)
But wait! ... WHO cares about what I think ?

Y> Now, i have to remark that the tutorial URL you
Y> gave me didn't explain anything useful or answered
Y> my questions. It simply doesn't deal with what i expected.

Heheh... :-)
That's exactly what I thought when I looked at
your 3R-documentation. ;-)

<p>Warning: This is probably my last reply to this thread
because I think we're kinda going around in circles and
would waste both our time.

<p>Gruss,
Sebastian

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