Compression - Rate Distortion Optimization

Author

Rate Distortion Optimization

shwet

2006-12-06, 3:55 am

HI! I have completed with motion estimation algorithms.So, further i
want to work on Rate distortion Optimization. I have went through many
documents. But i have the doubt regarding Lagranges value used here.In
different documents,different formulus or some constant values are used
for this multiplier.
So, please let me know the correct value for lagranges multiplier.

Thomas Richter

2006-12-06, 3:55 am

shwet wrote:
> HI! I have completed with motion estimation algorithms.So, further i
> want to work on Rate distortion Optimization. I have went through many
> documents. But i have the doubt regarding Lagranges value used here.In
> different documents,different formulus or some constant values are used
> for this multiplier.
> So, please let me know the correct value for lagranges multiplier.

This question cannot be answered, there is no "correct multiplier".
Lagrangian optimization is a mathematical framework to optimize a
functional under constraints.

The general outline of the method is as follows: You have a functional
D over a function space l (say, D = distortion, l = video sequences,
functional = something that maps a video into a number, say
"distortion"), and a second functional R over the same space l (say,
"Rate").

The goal is to optimize D under the constraint of given R.

The mathematical algorithm how to perform this is:

1) Create a new functional J := D + \lambda R, where \lambda is
a new free variable, called the Lagrangian multiplier.

2) Find the optimal value of J, neglecting the constraint. This
will give solutions parameterized by \lambda, let's call them
R_opt(\lambda), D_opt(\lambda), and solutions to the problem
l_opt(\lambda)

3) Adjust \lambda such that R_opt(\lambda) = target R. Call this
\lambda lambda_opt.

4) Now insert \lambda_opt back to get D(\opt) and l_opt(\lambda).

The "art" is now (and that's what you need to do) is to find the
proper functionals in your application.

Greetings,
Thomas

shwet

2006-12-06, 3:55 am

Thank ypu,

I got the solution to my problem. But plz go through this and
answer.......

Here is what i have understood after going through different Documents,

Rate Constrained Motion Estimation.
Integer-pixel motion search as well as fractional sample search is
performed by minimizing
D1(m) + =CE=BBd * R(m - pmv)
mv - Motion vector containing spatial displacement and picture
reference parameter
pmv - Predictor for motion vector
=CE=BBd - Lagrange parameter for motion estimation
D1 - Sum of absolute differences (luminance)
R - Number of bits associated with motion information

Rate Constrained Mode Decision.
For given values of Q and =CE=BBM, minimize
D2 (m |Q) + =CE=BBm R(M |Q)
m - Evaluated macroblock mode out of a set of possible modes.
Q - Value of quantizer control parameter for transform coefficients.
=CE=BBm - Lagrange parameter for mode decision.
D2 - Sum of squared differences (luma & chroma).
R - Number of bits associated with header, motion, transform
coefficients.

Relation between lagranges value and QP.

1) For H.263 / MPEG-4p2:

=CE=BBm =3D 0.85 Qp^2
=CE=BBd =3D sqrt (=CE=BBm)

2) For H.264/AVC
Qp =3D 2^(QP=E2=88=9212) / 6
=CE=BBm =3D 0.85* 2^(QP=E2=88=9212) /3
=CE=BBd =3D sqrt (=CE=BBm)

So, My question is whether i should adjust QP so as to vary lambda
value for getting Target Bit rate? ANd H.264 what accepted Target Bit
rate in case of video conferencing??

Thomas Richter

2006-12-11, 6:57 pm

shwet wrote:

> Here is what i have understood after going through different Documents,
>
> Rate Constrained Motion Estimation.
> Integer-pixel motion search as well as fractional sample search is
> performed by minimizing
> D1(m) + λd * R(m - pmv)
> mv - Motion vector containing spatial displacement and picture
> reference parameter
> pmv - Predictor for motion vector
> λd - Lagrange parameter for motion estimation
> D1 - Sum of absolute differences (luminance)
> R - Number of bits associated with motion information

Here \lambda defines the trade-off between the motion information
quality improvement, defined by D1, and the rate required to encode
the motion vectors. In the setup I gave, \lambda encodes the
tradeoff of quality improvement vs. output rate.

> Rate Constrained Mode Decision.
> For given values of Q and λM, minimize
> D2 (m |Q) + λm R(M |Q)
> m - Evaluated macroblock mode out of a set of possible modes.
> Q - Value of quantizer control parameter for transform coefficients.
> λm - Lagrange parameter for mode decision.
> D2 - Sum of squared differences (luma & chroma).
> R - Number of bits associated with header, motion, transform
> coefficients.

Again, tradeoff between quantization and mode vs. the rate to
encode this information.

> Relation between lagranges value and QP.
>
> 1) For H.263 / MPEG-4p2:
>
> λm = 0.85 Qp^2
> λd = sqrt (λm)

No. You just quote a blank formula. What you see here
is not a "solution" to the optimization problem. Instead,
this is a heuristic that works well for most cases.

> 2) For H.264/AVC
> Qp = 2^(QP−12) / 6
> λm = 0.85* 2^(QP−12) /3
> λd = sqrt (λm)

Same kind of stuff. This is not an answer, this is a
"rule of thumb".

> So, My question is whether i should adjust QP so as to vary lambda
> value for getting Target Bit rate?

No, you have different functionals here. The lambda value here does
not encode the constraint of the output rate vs. the quantizer, but
the constraint of placing additional information in the stream (motion
vectors) vs. the quality improvement.

Example: If you want to encode optimally, you can either increase the
number of bits for the quantizer (making it finer) and thus lowering the
artefacts due to motion. If you follow this all the way, you arrive at
no bits for motion vectors and all bits for residuals, and basically
have something like "motion JPEG". This is \lambda->infinity (Rate of
motion vectors must be zero). The other extreme is to invest all data
into the motion vectors and nothing into the residual, and you do not
care how much rate this costs. This is lambda = 0. Clearly, neither is
optimal. You want to find a lambda value and quantizer parameters such
that the rate becomes minimal for given distortion. The formuli above
give you *approximations* people found by experimenting (or so I guess)
because a closed solution to this functional problem seems to be
unlikely for me.

> ANd H.264 what accepted Target Bit
> rate in case of video conferencing??

I don't understand your question, sorry.

So long,
Thomas

Sponsored Links