Re: the basic idea of my codec

Pikatu wrote:
> 
> The enthropy encoder is very difficult to follow if you don't know the
> algorithm.
> 
> Can you give some hints on the structure of the code starting from the call
> to wavelet_3d_buf_encode_coeff in tarkin.c

I have only unfinished test code so far, and I am writing it for my own 2D
framework where I work with images. It is much easier to develop the algorithms
in 2D, and I don't know if a 3D transform is going to be used in the end anyway.

After transformation, the coefficients are quantized using a uniform scalar
quantizer. This sets many coeffs to zero. There is a "significance map" for
each subband pyramid with an entry for each coefficient that tells if it is
zero or not. The map is encoded separately using one algorithm and only
the non-zero coefficients are encoded conventionally.

My approach is to remove the constraint that the encoded significance-map
would have to be exact. It must be a superset of the actual map, however.
There will be remaining "residual" zero coefficients to be encoded together
with the non-zero.

We can view a significance map as a (number of) trees, with each leaf being
a zero-coefficient with only zero-coefficients as children. (i.e a "zerotree")
Start with the prediction that each non-zero coefficient has only non-zero
parents. If that is true, then we have to encode only the *topology* of the
tree. I measured the accuracy of this prediction to be around 90% (!) overall
in a couple of hundred test images, transformed with the (4,2) filter.
Filters with better energy compaction could yield better results.

Now, 90% is far from good enough, but I use topology as a starting point.
How to encode the tree: Encode the depth of the leftmost leaf, remove that
path from the tree and then recurse on each remaining subtree in order.
To increase prediction accuracy, I have inserted symbols for the most common
cases of internal zero-nodes. The symbols are supposed to be adaptively
huffman-encoded. I am not finished with that part, but I think that it
should be possible to take advantage of similarities both across and
within subbands. A range-coder would be even better. Has anyone
written one yet?

Note that I still don't know if the algorithm is competitive or not
because my code is not finished yet!
It may turn out to have been just a waste of time. ;-)

Btw, I have still not found the paper about the "Tetrary Tree" that
Maciek Urbanski mentioned.
Could someone please give me the name of that paper or of one of the authors?

Johan


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