【视频编码】视频编码中拉格朗日乘子法的简单理解
目录
- 1.问题的定义
- 2.问题的求解
- 3.实际应用
拉格朗日乘子法在诸多领域都有着重要的应用，通过使用拉格朗日乘子法，能够求解一些不易于解析的约束性问题，这在视频编码领域中也有重要的应用。
1.问题的定义
在视频编码器中，有些工具用来优化编码质量，而有些工具用于提升编码速度。在相同的码率（Bitrate）下，每增加一项工具都会对编码器的编码质量（PSNR）产生影响。这自然的衍生了一个问题，在给定码率的情况下，如何使得编码质量最优，即编码损失（Distortion）最小，这就是率失真优化（Rate Distortion Optimization，RDO）的问题，能够用一个约束性公式可以描述：
min
D
(
B
)
B
∈
S
,
s
.
t
.
R
(
B
)
<
R
c
(1)
\mathop{\min D(B)}\limits_{B \in S},s.t.R(B) <R_c \tag{1}
B∈SminD(B),s.t.R(B)<Rc(1)
其中，D表示编码损失distortion，B表示使用的工具情况（或者说编码模式），R表示码率，
R
c
R_c
Rc表示限制的码率。我们的目的是，给定码率，找到一个最优的
B
B
B，使得
D
(
B
)
D(B)
D(B)最小，记最优
B
=
B
∗
B=B^*
B=B∗。由视频编码中质量和码率之间的关系可知，一般情况下，码率越高，质量也越好，所以如果码率取最大值
R
c
R_c
Rc，损失也应该最小（至少是最小损失附近），即最优的
B
B
B为
B
∗
B^*
B∗，有
R
(
B
∗
)
=
R
c
R(B^*)=R_c
R(B∗)=Rc，最优的
B
∗
B^*
B∗对应于最小的损失。
2.问题的求解
B B B通常是由一系列编码器内部的模式组成的，即 B = { b 1 , b 2 , . . . , b n } B=\{b_1,b_2,...,b_n\} B={b1,b2,...,bn}。先考虑最简单的情况，只有一个模式，即 B = { b 1 } B=\{b_1\} B={b1}，此时能够根据 R R R的限制条件，求解出最佳的 B ∗ B^* B∗，因为这是一个一元函数，很容易求解。
假设现在
B
B
B由两个模式共同影响，即
B
=
{
b
1
,
b
2
}
B=\{b_1,b_2\}
B={b1,b2}。令
f
(
b
1
,
b
2
)
=
D
(
b
1
,
b
2
)
f(b_1,b_2)=D(b_1,b_2)
f(b1,b2)=D(b1,b2)，
g
(
b
1
,
b
2
)
=
R
(
b
1
,
b
2
)
−
R
c
g(b_1,b_2)=R(b_1,b_2)-R_c
g(b1,b2)=R(b1,b2)−Rc。由前述可知，当
g
(
b
1
,
b
2
)
=
0
g(b_1,b_2)=0
g(b1,b2)=0时取得最佳的模式，根据这个等式可以获得
b
1
b_1
b1和
b
2
b_2
b2的关系，记为
b
2
=
T
(
b
1
)
b_2=T(b_1)
b2=T(b1)，此时有
f
(
b
1
,
b
2
)
=
f
(
b
1
,
T
(
b
1
)
)
f(b_1,b_2)=f(b_1,T(b_1))
f(b1,b2)=f(b1,T(b1))，这样就变成了一个一元函数，一元函数的极值点位于导数为零的点，对
f
f
f进行求导，有
d
f
(
b
1
,
b
2
)
d
b
1
=
∂
f
∂
b
1
+
∂
f
∂
b
2
d
b
2
d
b
1
=
0
(2)
\frac{df(b_1,b_2)}{db_1}=\frac{\partial f}{\partial b_1}+\frac{\partial f}{\partial b_2}\frac{db_2}{db_1}=0 \tag{2}
db1df(b1,b2)=∂b1∂f+∂b2∂fdb1db2=0(2)
如果上式成立，则对应的
b
1
b_1
b1和
b
2
b_2
b2就是最佳模式。
由隐函数求导公式可知
d
b
2
d
b
1
=
−
∂
g
∂
b
1
∂
g
∂
b
2
(3)
\frac{db_2}{db_1}=-\frac{\frac{\partial g}{\partial b_1}}{\frac{\partial g}{\partial b_2}} \tag{3}
db1db2=−∂b2∂g∂b1∂g(3)
因此，有
d
f
(
b
1
,
b
2
)
d
b
1
=
∂
f
∂
b
1
−
∂
f
∂
b
2
∂
g
∂
b
1
∂
g
∂
b
2
=
0
(4)
\frac{df(b_1,b_2)}{db_1}=\frac{\partial f}{\partial b_1}-\frac{\partial f}{\partial b_2}\frac{\frac{\partial g}{\partial b_1}}{\frac{\partial g}{\partial b_2}}=0 \tag{4}
db1df(b1,b2)=∂b1∂f−∂b2∂f∂b2∂g∂b1∂g=0(4)
简化(4)中的公式，有
d
f
(
b
1
,
b
2
)
d
b
1
=
f
b
1
−
f
b
2
g
b
1
g
b
2
=
0
(4)
\frac{df(b_1,b_2)}{db_1}=f_{b_1}-f_{b_2}\frac{g_{b_1}}{g_{b_2}}=0 \tag{4}
db1df(b1,b2)=fb1−fb2gb2gb1=0(4)
令
λ
=
−
f
b
2
g
b
2
\lambda = -\frac{f_{b_2}}{g_{b_2}}
λ=−gb2fb2，有
{
f
b
2
+
λ
∗
g
b
2
=
0
f
b
1
+
λ
∗
g
b
1
=
0
g
(
b
1
,
b
2
)
=
0
(5)
\left\{ \begin{matrix} f_{b_2} + \lambda * g_{b_2} = 0 \\ f_{b_1} + \lambda * g_{b_1} = 0 \\ g(b_1,b_2) = 0 \end{matrix} \right. \tag{5}
⎩
⎨
⎧fb2+λ∗gb2=0fb1+λ∗gb1=0g(b1,b2)=0(5)
根据公式(5)，能够求解出对应的
b
1
b_1
b1和
b
2
b_2
b2。如果将公式(5)进行抽象化，获得
D
+
λ
∗
R
=
C
(6)
D + \lambda * R = C \tag{6}
D+λ∗R=C(6)
其中，C为一个常数。如果此时再构建一个R-D曲线的话，那么这个R-D曲线与斜率为
−
λ
-\lambda
−λ的直线的切点就是最佳R-D点，这个最佳R-D点对应的模式就是最佳的模式。
3.实际应用
在RDO实际应用于编码器时，通常决定的是某一个模块，例如帧内预测选择何种模式，可能是16x16，也可能是4个8x8，或者是SKIP模式。评判如何选择最佳模式的方式就是
J
=
D
+
λ
∗
R
J = D + \lambda * R
J=D+λ∗R
哪一种模式带来的
J
J
J最小（最接近于C），说明最接近于上述的切点。
需要注意的是，上述第2节中只讨论了2种模式的情况，如果是更多的模式，再依次类推即可。实际上，RDO过程中有很多子任务互不影响，是可以单独拆解的。