Rate-distortion optimisation

Hi all,

Could someone please help me figure out how to use rate-distortion
optimisation?

I'm working on a video codec at the moment and, from what I
understand, the modes on encoding are decided on the
sum-of-absolute-difference (SAD) value, which is effectively a measure
of the distortion, and the number of bits required to encode the
residual. These two values are summed, one being weighted by a lambda,
and the best mode is decided based on that which minimises the result.

The reason, I am told, the summation of distortion and bit-rate is
used is so the encoder can make a trade-off between image quality and
bit-rate. So, for example, if the encoder encountered a highly complex
macroblock that would suffer from a great deal of distortion if it
used the same quantisation parameter as before, it could lower the
quanisation value to allow for a trade of in distortion, even though
it would require more bits to encode.

The question I have is that I'm not really sure where this lambda
value comes from. I've read a couple of papers on the codec in
question (H.264) and they suggest a empirically derived formula
dependent on the quantisation parameter for calculating it. The
difficulty I am having in understanding this is how can one calculate
the lambda value if the quantisation parameter is not fixed and on
what basis is the quantisation parameter changed based on the outcome
of the encoding process.

I apologise for the admittadly vague question, but I'm really having
difficulty understanding exactly what rate-distortion optimisation in
video codecs is trying to achieve.

Thanks,

Stephen Henry

Hi,

> I'm working on a video codec at the moment and, from what I
> understand, the modes on encoding are decided on the
> sum-of-absolute-difference (SAD) value, which is effectively a measure
> of the distortion, and the number of bits required to encode the
> residual. These two values are summed, one being weighted by a lambda,
> and the best mode is decided based on that which minimises the result.

Right.

> The question I have is that I'm not really sure where this lambda
> value comes from.

It comes from the Lagrangian optimization. You need to optimize
distortion under the constraint of given output rate. This can
be reformulated mathematically as finding the optimium of the
functional

J(lambda)	=	D + lambda(R - R_target)

That is, you add the constraint with a Lagrangian multiplier, then
maximize/minimize J parametrically in lambda and finally tune lambda
to fit the constraint.

> I've read a couple of papers on the codec in
> question (H.264) and they suggest a empirically derived formula
> dependent on the quantisation parameter for calculating it. The
> difficulty I am having in understanding this is how can one calculate
> the lambda value if the quantisation parameter is not fixed and on
> what basis is the quantisation parameter changed based on the outcome
> of the encoding process.

You typically don't "calculate" lambda. Rather, you have a control
loop that "finds" the right lambda. Lambda can be understood (from
the above formula) as the "critical slope" of the R/D curve. What
you need to find is a slope such that the resulting output rate
fits the target rate. That is, you built up a control loop that
varies lambda (e.g. by a bisection algorithm), then finds the
optimal quantization parameters in terms of this lambda, then computes
the rate in terms of this lambda, and then checks whether this rate
is too large or too small. Then adapt lambda and repeat the process
until the rate fits. Realistically --- that is in Video compression ---
you don't requantize the given frame. Rather, you could assume that
the next frame as "similar" characteristics, accept the rate overflow
or underflow and "fix" this problem for the next frame by modifying
lambda correctly.

> I apologise for the admittadly vague question, but I'm really having
> difficulty understanding exactly what rate-distortion optimisation in
> video codecs is trying to achieve.

Well, basically "finding an optimum under a constraint". Maybe a good
starter, if I may suggest that, would be a math book covering
Lagrangian optimization.

So long,
Thomas

> Well, basically "finding an optimum under a constraint". Maybe a good
> starter, if I may suggest that, would be a math book covering
> Lagrangian optimization.
>
> So long,
> 	Thomas

Thank you for your reply Thomas,

One of the problems of not really knowing about the subject is that
it's hard to know where to find a suitable reference discussing it.
I've got a few good math books, although general engineering math
books and I'll have a look at them.

Thanks again,

Stephen