Vorbis dev - Apr 2004 - another entropy coder that might be very useful

Hello,

I want to let you know about an algo that will soon be published
and that may be of interest to Vorbis (and other Ogg projects) :

http://f-cpu.seul.org/whygee/ddj-3r/ddj-3r.tgz

this is the archive of the article i submitted.
It describes the "Recursive Range Reduction" algorithm
(3R for short) and uses only a few basic computer
principles (a binary tree being the most complex structure).
Really, it's so simple that i wonder why nobody uses it.

It is quite efficient (compared to other classical methods)
for reducing the size of histograms
(my first intent) but also DCT, FFT, Huffman tables ...
It is a low complexity (add/sub, shift, masks ...)
code that works well on small datasets that have
some kind of correllation that is not easily modelised.
Depending on the type of data (large variance and
grouped chunks), it can be used to compress/pack
as little as 4 or 8 values, sometimes beating Rice and Huffman codes.

It requires O(N) temporary storage for compression
(usually N plus a stack in log2(N)), and it can be modified
for in-place decompression. I have tried to illustrate its operation
with simple, non-optimised code, which has a lot
of headroom for adaptation (i design most algos
with DSPs/uCs/ASICs/FPGA in mind)

It is new so many optimisations, heuristics and applications
remain to be invented and implemented, i hope that
it will be useful for the next version of Vorbis, speex etc.
One of the most promising use is as a "baseline JPEG"
replacement, as it can do the zigzag+RLE+entropy coding
in a single, tunable, step. As it is low-CPU, it is good
for low-power video as well. And it is patent-free AFAIK !
(so no worries about
http://yro.slashdot.org/article.pl?sid=04/04/24/1621203
http://yro.slashdot.org/article.pl?sid=04/04/24/1621203 )

I have no time to look closely at the Vorbis source code,
so i won't hack&patch it. However i encourage
everybody to look at the 3R algorithm and use it in Ogg projects.

Have fun,
YG

--- >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@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.

Hello, Yann !

Thanks for showing interest in optimizing Vorbis.

<p>On Mon, 26 Apr 2004, Yann Guidon wrote:
> Hello,
> 
> I want to let you know about an algo that will soon be published
> and that may be of interest to Vorbis (and other Ogg projects) :
> 
> http://f-cpu.seul.org/whygee/ddj-3r/ddj-3r.tgz
(Note for other users: This archive does not contain a
subdirectory)

Correct me, if I'm wrong. As I understand your algorithm,
you suggest to sort all samples first, do some "folding" by adding
a certain value to all samples so that they are positive, compress
the sorted list of positive interegs with your RR algorithem and
store some side-info about the permutation so that the original
order can be restored.

I don't see why this should be superior (in terms of compression
efficiency and speed) to the entropy coding layer which is
currently used. I also doubt that the RR step for coding the sorted
list of positive integers is near optimal.

Perhaps I missed something. It would be nice of you if you can
enlighten us. Did you successfully used this sheme as replacement
for JPEG's entropy coding layer ? Or was it still theory ?

You might want to compare it to
http://www.xiph.org/ogg/vorbis/doc/vorbis-spec-res.html
It's a detailed describtion of how the residue vectors are coded.
After the "floor-curve-subtraction" and quantization step the
samples are mostly uncorrelated signed integers (*) with varying
variance (higher variance in the low-freq part with some amplitude-
peaks (tonals) and lower variance in higher frequency regions due
to higher quantization.

(* quantization and coding can be done simultaneously by VQ, but
currently it's like scalar quantization to integers and coding them
in groups with a specific set of codebooks)
> I have no time to look closely at the Vorbis source code,
You don't have to. I would suggest to inform yourself first about
how the residue coding is done in Vorbis by checking the link I
gave above.

<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@xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is
needed.
Unsubscribe messages sent to the list will be ignored/filtered.