[vorbis-dev] Tarkin at last

Jonathan Blow jon at bolt-action.com
Thu Jan 4 15:37:39 PST 2001

Lourens Veen wrote:

> I need to read up on zero-tree packing, unless someone could give an
> short explanation here?

As I understand it, the 2D case is basically a quadtree with 1 bit
per node.  You go down to the image-resolution (bottom level of
quadtree) and all the slots with negligible coefficients get 0s,
all others get 1s.  Then you build the successive higher levels
of the tree: anyone with all 0 children gets a 0, all others get
1s.  The idea is that you end up with some 0s pretty high in
the tree which allows you to prune large subtrees.

Now when you come to save this thing to a file, there are some
tricks to reduce the number of bits that you write that I don't
really remember but they are kind of clever.  So you don't
actually write out this quadtree in the obvious dumb way.

But the basic idea is that you write out the quadtree first,
then you write out only the nonzero coefficients.  When it's
time to read the file, you first read the tree, then you know
exactly how many coefficients to read and where each one goes.


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

More information about the Vorbis-dev mailing list