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}{3\alpha}\cdot QUANT^2$

即：

$\lambda_{MODE} = \zeta\cdot QUANT^2$

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

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

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

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

$\begin{align*}
SAD &= \sum_{(x,y)\in A}\left | s[x,y] - s'[x,y]\right | \\
SSD &= \sum_{(x,y)\in A}\left | s[x,y] - s'[x,y]\right |^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}$