Rate Distortion Optimization

搜索时，一个不可避免的问题就是如何对mv进行比较，从而得到最优

对于同一压缩算法来说，码率越高表示图像质量越好、失真越小，但是码率越高要求更大的存储空间，也会增加网络传输的压力。因此在码率与失真中找出平衡点，使压缩效果最优，这种方法叫做R-D Optimization（码率失真优化）

典型的高码率下，码率与失真关系（R-D关系式）为

$R(D) = {alpha}{ln(frac{delta^2}{D})}$

$R$为码率，$alpha$为系数，$delta^2$为方差，$D$为失真。

方差越大，意味着图像细节越多，因此码率也会越大；失真越大，意味着图像由于压缩所损失的细节越多，那么码率越小。

R-D曲线

R与D好比鱼与熊掌，取一方，必然会舍去另一方，两者不可能都取得最佳，因此如何取舍，就需要权衡利弊。最好的方法，就是看哪个权重大，哪个的比例就大，权重小的比例小，这就是拉格朗日方法。

拉格朗日代价函数为：

$J = D + lambda_{MODE} cdot R$

要使得代价最小，那么在其导数为0处有最小值：

$frac{dJ}{dR} = frac{dD}{dR} + lambda_{MODE} = 0$

现假设D与R的权重比为$lambda_{MODE}$，并假设上方点A为根据上方结论得到的最佳位置，那么点A处有斜率：

$k = -lambda_{MODE} = frac{dD}{dR}$

又因为可以通过对R-D关系式求导，然后整理得：

$frac{dD}{dR} = -frac{D}{alpha}$

因此，在R-D最优点处有：

$lambda_{MODE} = frac{D}{alpha}$

另外，在典型的高码率下，失真近似满足公式：

$D = frac{ ( 2 cdot QUANT )^2}{12}$

把D代入上述公式，得到：

$lambda_{MODE} = frac{1}{3alpha}cdot QUANT^2$

即：

$lambda_{MODE} = zetacdot QUANT^2$

最终可以通过函数拟合得到$zeta = 0.85$，在h.264中，当存在B帧编码时$zeta = 0.68$，则有：

$egin{align*}
lambda_{MODE}
&= 0.68cdot QUANT^2 \
&= 0.68 cdot (2^frac{QP - 12}{6})^2 \
&= 0.68cdot 2^frac{QP - 12}{3}
end{align*}$

注：QP在这里减去12是因为在h.264早期只有40个QP，而现在有52个QP

由于上面计算的时候用的是$delta^2$（方差），即SSD，但是实际上h.264计算用的是

$egin{align*}
SAD &= sum_{(x,y)in A}left | s[x,y] - s'[x,y] ight | \
SSD &= sum_{(x,y)in A}left | s[x,y] - s'[x,y] ight |^2
end{align*}$

那么

$lambda_{MOTION} = sqrt{lambda_{MODE}}$

为了方便计算，在一般h.264的编码器中采用的都是

$D = SAD$

而R则需要知道当前所选择的mv与ref所占用的bit，而这些都是可以事先计算出来的，在JM中不同的mv与ref所占的bit都在编码前被初始化了，用数组存储起来。mv与ref采用的都是哥伦布编码。

$R = Bit_{mv} + Bit_{ref}$