# Theora: Thusnelda project update 20080724

## Overview

This update is short and sweet.

Two weeks ago saw completion of the Thusnelda encoder's
long-term code refactoring to allow motion vector analysis, mode
selection, transformation, quantization and tokenization to be
done block-by-block in a single pass. The point of this
refactoring was to allow rate-distortion optimization of each
individual token as a block is coded (each token relies on
preceeding tokens) without requiring multiple passes though
cache-busting amounts of auxiliary data.

As of this past week, token optimization is operational.

## Token optimization

The idea behind token optimization is simple. As with all other
aspects of rate-distortion optimization, we seek to minimize the expression:

distortion + lambda * bit_cost

With respect to token optimization, this is evaluated for each
individual token to be written to the bitstream. The challenge is
to efficiently evaluate the expression on the fly in the context
of subsequent tokens. Because any change to the current token
affects the coding of subsequent token, each optimization must
evaluate the provisional bit costs of several possible choices and
outcomes.

Theora's token structure as constructed can gain cost benefits
only from 'demoting' tokens, that is, reducing the coefficient
values being coded either to a smaller value (potentially allowing
use of a shorter or combined token) or to zero (possibly extending
zero or EOB runs). Token demotion can be evaluated recursively,
however, analysis of recursive optimization yields negligable
results for the cost gain. Therefore, despite the complicated
token and coding structure, a fast constrained greedy optimization
process yields nearly optimal results. The computational overhead
of optimization is under 10%.

## Bitrate reduction examples

We turn once again to our test clip from the Matrix. The stills
are closeups from frames 49, 2119 and 2209. The link leads to the
actual encoded clip.

**Mainline Theora test clip @ 580kbps**

**Unoptimized Thusnelda test clip @ 580kbps**

Encoded with internal qi=30

**Test clip with SKIP, AC and DC token optimization @ 580kbps**

Encoded with internal qi=50, skip lambda=5, token lambda=16

**Low bitrate example @ 240kbps**

Encoded with internal qi=19, skip lambda=16, token lambda=32

### Effect of high SKIP lambda: 470 kbps

Encoded with internal qi=50, skip lambda=20, token lambda=16

(Demonstrating the potential usefulness of adaptive SKIP weighting)

test50-skip20-acdc16.ogg

### Effect of high token lambda: 540kbps

Encoded with internal qi=50, skip lambda=5, token lambda=128

(Due to nonrecursive optimization, the demotion process quickly saturates)

test50-skip5-acdc128.ogg

Monty