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

Timothy B. Terriberry tterribe at vt.edu
Sun Dec 7 13:56:10 PST 2003

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

```