[theora-dev] What sort of math i required?

[Timothy B. Terriberry]

Martin Jeppesen wrote:
> Do you know where I can read about entropy-coding? I have searched Google and found this presentation,
> which is very illustrative with examples:

http://datacompression.info/index.shtml has links to most everything 
useful on the web. Most of it is introductory, but as I said, Theora 
doesn't get that sophisticated. Just Huffman and RLE, for the most part. 
This is, however, something that can be addressed without losing the 
ability to losslessly transcode. Of course, you may also run into patent 
issues.

> Wavelets you say? I have choosen a course on wavelets next semester. It
 > have rumours of being tough. The book that I have bought for the
 > course is "A First Course on Wavelets" ISBN 0-8493-8274-2. Do you think
 > I will be able to use this knowledge to code compression algorithms?

A general knowledge of wavelets is certainly useful, but not directly 
applicable. Tarkin was supposed to be Xiph's foray into a wavelet-based 
video codec, but it has been mostly dormant for the past year or more. 
Also, not everyone believes that wavelets are the way to go.

Wavelets could almost certainly provide better compression than the 
vanilla DCT Theora uses, but also carry an increased computational cost. 
They'd also break backwards compatibility.

 > An advanced linear algebra course sounds interesting indeed! Can you
 > give an example where linear algebra is heavily used in Theora?

I recently developed a border padding algorithm that uses a Cholesky 
decomposition to extract a well-behaved set of DCT basis functions that 
are linearly independent over the domain of pixels inside the border, 
which can then be used to select pixel values for pixels outside the 
image border that introduce as many zero coefficients as possible into 
the DCT transform of the block. A very similar process is behind Monty's 
declipping algorithm in postfix, though he does it with a QR decomposition.

The DCT is just a linear transformation. As is the discrete Fourier 
transform. The usefulness of a more abstract view of linear algebra is 
when you realize that the continuous Fourier transform is, too.

>>>        However, there is also more math involved in encoding when you
>>> cover topics such as data rate control and psycho-visual models.
> Have this been documented yet?

Not outside my (reasonably well-commented) source code for my 
experimental encoder. It's also nowhere near ready for prime time yet.

> Do you know titles of this specialized domain that you speak of?

Specialized topics include, but are not limited to, rate control (and 
rate/distortion optimization), motion compensation, quantization (vector 
and otherwise), postprocessing (deblocking and deringing), video 
standards (color spaces, pixel formats, interlacing, etc.).

Don't be put off by the wide variety of topics. You can certainly 
contribute and be useful before you've mastered all of these, and 
hands-on experience is often the best kind.

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