BD-Rate

背景

全称 Bjøntegaard-Delta rate，用于评价不同的视频编码器RD（率-Rate，失真-Distortion）性能
是 Gisle Bjøntegaard 等人在 H.264 标准开发过程中提出的

分类

通常分为：

1. BD-PSNR
   反映相同码率下平均 PSNR(dB) 差值
2. BD-BR（BD-BitRate）
   反映相同 PSNR 下平均的码率变化比例（%）

测试点的选取

由于测试的工作量比较大，通常只选用4个典型的 QP 值，H.26X 中常采用的是：

• 22
• 27
• 32
• 37

其他编码算法由于量化方法的不同会选择不同的 QP 值，但为了方便比较通常要求器码率画着 PSNR 变化范围相近。

Calc Steps

• 过程中的 log 变换的原因涉及统计学知识，增加数据的线性关系

BD-PSNR

1. 取积分区间: (minBitRate, maxBitRate)
   1. minBitRate: max(min(anchor), min(testCase))
   2. maxBitRate: min(max(anchor), max(testCase))
2. 码率以 10 为底取对数，以做 log 变换
3. 三次函数曲线拟合（拟合方法见“多项式插值”小节）
4. 将「3’」的函数在「1’」区间上积分
5. 积分差值除以积分区间，以取平均，得到 BD-PSNR

BD-BR (BD-BitRate)

1. 取积分区间: (minPSNR, maxPSNR)
   1. minBitRate: max(min(anchor), min(testCase))
   2. maxBitRate: min(max(anchor), max(testCase))
2. 码率以 10 为底取对数，以做 log 变换
3. 三次函数曲线拟合（拟合方法见“多项式插值”小节）
4. 将「3’」的函数在「1’」区间上积分
5. 积分差值除以积分区间，以取平均
6. 对数反变换（将「5’」的平均值作为 10 的幂），得到testCase（被测编码器）相对于基准编码器（anchor）的倍数
7. 「6’」减 1 得到变化率

多项式插值（函数图像拟合）

Lagrange 插值容易严重 overshoot，目前的版本中通常采用形状保持的分段三次 Hermite 插值法（SPPCHIP）。

Linear

• 完美区间单调性
• 不平滑

Lagrange

相当于 p = 0 的 Hermite

• 非常平滑
• 严重 overshoot $$P(x) = \sum_{i=0}^{n-1}a_ix^i=a_0+a_1x+... a_{n-1}x^{n-1}$$

Hermite

$$\begin{aligned} P^{(j)}(x_k) = y_k^{(j)}, \\ k=1,2,...,n, \\ j=0,1,...,p. \end{aligned}$$

CHIP

形式

三次 Hermite 插值多项式 （Cubic Hermite Interpolation Polynomial, CHIP），一阶可导

n = 2, p = 1 的 Hermite

设已知两点 $(x_0, x_1)$ 和 $(x_1, y_1)$，$x_0<x_1$，假设其一阶导数存在 $d_0, d_1$

$$P(x) = a_0+a_1x+a_2x^2+a_3x^3, x\epsilon[x_0, x_1].$$

则

$$P(x_0) = a_0+a_1x_0+a_2{x_0}^2+a_3{x_0}^3=y_0$$ $$P(x_1) = a_0+a_1x_1+a_2{x_1}^2+a_3{x_1}^3=y_1$$ $$P'(x_0) = a_1+2a_2x_0+3a_3{x_0}^2=d_0$$ $$P'(x_1) = a_1+2a_2x_1+3a_3{x_1}^2=d_1$$

令

$$\begin{aligned} h=x_1-x_0, \\ s=x-x_0,\\ \delta=\frac{y_1-y_0}{x_1-x_0} \end{aligned}$$

可得

$$\begin{aligned} P(x) &= H_1(x)y_0+H_2(x)y_1+H_3(x)d_0+H_4(x)d_1 \\ &=\frac{h^3-3hs^2+2s^3}{h^3}y_0+\frac{3hs^2-2s^3}{h^3}y_1+\frac{s(s-h)^2}{h^2}d_0+\frac{s^2(s-h)}{h^2}d_1 \\ &=y_0+sd_0+s^2\frac{3\delta-2d_0-d_1}{h}+s^3\frac{d_0-2\delta+d_1}{h^2} \\ &=y_0+sd_0+s^2c_0+s^3b_0 \end{aligned}$$

H 为三次 Hermite 基函数。

$$\begin{aligned} P'(x) = d_0+2sc_0+3s^2b_0, \\ P''(x) = 2c_0+6sb_0, \\ \int_m^nP(x)dx = (sy_0+\frac{1}{2}s^2d_0+\frac{1}{3}s^3c_0+\frac{1}{4}s^4b_0+C)|_{m-x_0}^{n-x_0} \end{aligned}$$

单调性

需要保证 $[x_0, x_1]$ 两点间的函数图像单调

$d_0, d_1$ 是两端点处的导数

=> 单调必要条件： $d0, d1, \delta$ 同号

如果 $\delta=0$, 单调充要条件 $d_0=d_1=0, P(x)$ 是常数

如果 $\delta\neq0$,

$$P'(x) = d_0+2s\frac{3\delta-2d_0-d_1}{h}+3s^2\frac{d_0-2\delta+d_1}{h^2}$$

没看懂，略～

1. 如果 $d_0-2\delta+d_1=0$

   • P(x) 为二次或线性函数

   • P‘(x) 为线性函数或常数 => 导数（d）单调

     => $min{d_0, d_1}\leq P’(x)\leq max{d_0, d_1}$

     然后看不懂了…d0 d1 同号不是已知条件啊

2. 如果 $d_0-2\delta+d_1\neq0$

   • P’(x) 为二次函数

     当 $\delta>0$ 且 $d_0+d_1-2\delta<0$ 时，$\because$ P’(x) 开口向下，且 $0\leq min{d_0, d_1}\leq P’(x) \therefore$ P(x) 单增

     当 $\delta<0$ 且 $d_0+d_1-2\delta>0$ 时，$\because$ P’(x) 开口向上，且 $P’(x)\leq max{d_0, d_1}\leq 0 \therefore$ P(x) 单减

     ？？？？为什么能直接用 d0 d1 同号这个条件，其他情况呢？

PCHIP

分段三次 Hermite 插值多项式 （Piecewise Cubic Hermite Interpolation Polynomial, PCHIP），一阶可导，不一定二阶可导

• 样点一阶导数存在

SPPCHIP

形状保持的分段三次 Hermite 插值多项式（Shape-Preserving Piecewise Cubic Hermite Interpolation Polynomial, SPPCHIP），是在保持区间单调性的同时，使得样点处的一阶导数连续，从而使得插值后的曲线更加平滑。

样点斜率是于左右相邻点的两个斜率加权调和平均值，且保证单调。

令

$$\begin{aligned} h_k = x_{+1}-x_k, \\ s_k = x-x_k, \\ \delta_k = \frac{y_{k+1}-y_k}{x_{k+1}-x_k} \end{aligned}$$

非边界点 $d_k, k=2,3,…,n-1$ 一阶导数

1. $\delta_{k-1}\times\delta_k\leq0$ 时，$d_k=0$ 是局部极值点

2. $\delta_{k-1}\times\delta_k>0$ 时，$d_k$ 为这俩的加权调和平均

   $$\begin{aligned} \frac{w_1+w_2}{d_k}=\frac{w_1}{\delta_{k-1}}+\frac{w_2}{\delta_{k}}, \\ w_1=2h_k+h_{k-1}, \\ w_2=h_k+2h_{k-1} \end{aligned}$$

边界点 $d_1, d_n$ 的一阶导数

$$d_k=\frac{(2h_p+h_q)\delta_p-h_p\delta_q}{h_p+h_q}, \\ if d_k \delta_p 异号 => d_k=0; \\ else if \delta_p \delta_q 异号 且 |d_k|>|3\delta_p| => d_k=2\delta_p$$

$d_1 的 p q 取前两个, d_n 的 p q 取最后两个$​

Spline

分段三次样条插值

• 比 SPPCHIP 更加平滑，又不会像 Lagrange 严重 overshoot
• 但是区间不一定单调

Spline 与 PCHIP 区别

• Spline 更平滑，二阶导数连续
• 如果数据的函数足够平滑，Spline 更精确
• 如果数据不平滑，PCHIP 不会 overshoot 且更少出现震荡
• PCHIP 使用成本更低

Expand

ROC (Receiver Operating Characteristic)

用来比较不同分类器的相关性能

横坐标 FPR (costs)，纵坐标 TPR (benefits)

ROC Curve 越接近左上角，分类器性能越好，意味着分类器在假阳率很低的同时获得了很高的真阳率

AUC (Area Under the Curve of ROC)

• ROC 曲线下的面积

• BD-Rate 相当于 AUC

物理意义

任取一对（正、负）样本，正样本的 score 大于负样本的 score 的概率。

References

• BD-rate https://xjsxjtu.github.io/2017-04-17/RD-rate/#%E7%AE%97%E6%B3%95
• 【机器学习笔记】：一文让你彻底理解准确率，精准率，召回率，真正率，假正率，ROC/AUC https://zhuanlan.zhihu.com/p/46714763
• 机器学习算法常用指标总结 https://tianchi.aliyun.com/forum/postDetail?postId=79707
• BD-rate计算原理 https://blog.csdn.net/weixin_42348033/article/details/104892903
• 多项式插值之Lagrange、PCHIP与Spline以及BD-Rate和BD-PSNR的计算 https://blog.csdn.net/qq_33552519/article/details/102742715
• ROC及AUC计算方法及原理 https://blog.csdn.net/yinyu19950811/article/details/81288287
• 客观编码效率指标 https://wangwei1237.gitbook.io/digital_video_concepts/shi-pin-zhi-liang-du-liang/4_2_0_videoqualityevaluationmethodsandmetrics/4_2_2_0_objectivevideoqualityevaluationmethodsandmetrics/4_2_2_9_objectivecodingefficiencymetrics
• 在统计学中为什么要对变量取对数？ https://www.zhihu.com/question/22012482/answer/21357107

Example Code

我的 TypeScipt 实现：(YoungSx/bjontegaard.js)[https://github.com/YoungSx/bjontegaard.js]

Changelog

• 20210722: BD-PSNR 计算步骤有误，之前多出了类似 BD-BR 的后续步骤，现已修改