导语：

在互联网如此发达的今天，用户已经有各种不限流量的套餐，当你看着高清《创造101》的小姐姐们时，当你户外直播不亦乐乎时，当你和恋人视频特效美颜时，背后的企业都是一把辛酸泪：主子们，我们的流量要钱啊！！！

这样一场流量节省的战役摆在了视频类APP面前，而能看到有两个主战场学术界和工业界展开被经常拿来各种厮杀：

一是高清低码——在保证画质的前提下拼命压缩视频内容来降低传输带宽；

一是视频超分辨率——用小分辨率来减少传输带宽。

但，这不是全部

有另一个处女之地如珠穆朗玛峰一样美丽又遥远：帧率上采样，也称之为倍帧。

帧率上采样：即利用视频帧间的相关性，对视频进行插帧，可以理解为在两帧之间产生一帧或多帧。

这个有多厉害你造吗？

比如：假设视频当前是30帧每秒，可以先把帧率降到15帧，经过网络传输后再通过帧率上采样把帧率上升到30帧每秒，这样就无缝将传输内容减少了一半！

如果视频超分辨率是对视频进行空域上的压缩，那帧率上采样就是对视频进行时域上的压缩，两个都能达到大幅降低带宽的作用，但目前大多数人都关注点都在超分辨率技术上，为何不Pick一下帧率上采样呢？

接下来我们将为大家详细讲解帧率上采样技术。

先看段直接征率翻倍的视频：

再看一段场景切换频繁、运动特别大的视频（先丢弃一半的帧数，再把丢弃的一半用技术恢复）：

前沿

考虑到帧率上采样在各方的应用：

视频技术朝着更高分辨率，更高帧率方向发展，对高帧率视频需求越来越大；

激增的适配数据的存储和传输，对基础设施带来巨大挑战，直接前端隔帧丢弃一帧，末端插值回来这一帧，直接减少服务器存储压力；

接下来，我们将详细讲解我们的技术方案：

运动估计

运动估计是利用当前帧和之前的帧计算出画面中各点的运动矢量。由于单个像素值信息在时域上的相关性不高，几乎不可能找到每一个像素在相邻帧的运动矢量。通常的做法是将画面分隔成宏块，假设宏块内每个像素的运动方向都一致，以一个运动矢量代表整个宏块的运动方向和距离。这样在相邻两帧之间寻找每个宏块的对应关系要相对容易的多。

单向运动估计

运动估计分为两种：单向运动估计和双向运动估计。单向运动估计是以当前的块为参考，在前一帧中寻找匹配的块（图1）。

当前帧中的块 与最匹配的块 的位移（像素单位）为运动向量v。 因为是单向搜索，插值帧的位置在当前帧与前一帧之间，所以实际运动向量为 ，见图2。

块匹配

块匹配算法：计算两个块之间的MAD(Mean Absolute Difference)值：

Bij为第i行第j列，v为块Bij的运动向量，s属于块Bij内所有点的集合， b为块边长（单位像素）。 我们根据MAD值来确定宏块之间的匹配度。通过搜索不同的运动向量v, 将计算出MAD值最小的一个运动向量作为块Bij的预测运动向量。这里的匹配计算取YUV中的Y分量灰度值。

运动向量搜索

搜索最佳匹配块的方法有全搜索法，三步搜索法，新三步搜索法，四步搜索法， 钻石搜索法等。这里离我们采用效率和精确度最优是钻石搜索法。 钻石搜索模型： 大钻石模型有9个点，小钻石模型有5个点，每个点代表1个像素。见图3：

在传统搜索技术基础上，我们做了一些优化策略：

1） 追加小钻石（提前终止策略）

如果motion activity为1或以下则追加小钻石搜索。 如果小钻石搜索求得最小MAD值记为中心且小于等于第一次大钻石的cost则小钻石最小MAD值的点为最匹配点，结束搜索。若最小点的MAD值大于第一次大钻石搜索的cost则继续下一步。motion activity 代表当前块所处区域估算的运动跃度， 共分4级：0，1，2，3。motion activity 参考当前块B的邻块中的运动向量求得。参考的邻块运动向量C(candidates)分为两类：空域邻块向量 和时域邻块向量 。因为空域邻块的相关性时域邻块要强所以首选参考空域邻块 。但是在从上到下， 从左到右的计算顺序下， 当前帧中B右边和下边的块的运动向量还没计算出来所以用前一帧的运动向量时域邻块 代替，见图

2）邻块参考

因为宏块相对于画面中的运动物体来说一般比较小，一个物体包含多个宏块的几率很大，所以宏块周围的邻块的运动向量有相当大的参考价值。同一帧内块与块之间的相关性比帧与帧之间的相关性大。首先参考已经计算出的3个空域邻块：左边，上边，右上。右下角没有空域邻块的地方用时域邻块代替：右边，下边，左下。这6个邻块的运动向量组成一个运动向量候选表(MVCI)。候选表的大小可以减少到3个或增加到8个，取决于计算速度。

双向运动估计

双向运动估计的提出就是为了避免重叠和空洞问题的出现。但它不能解决重叠和 空洞的问题。计算运动向量时参考块和搜索块同时移动，但它们之间的运动向量二分之一处的坐标不变。这样计算出的运动向量实际上是以插值帧为基准，能保证插值帧中每个16×16宏块中都能分配到唯一的插值块从而避免出空洞和重叠的块。双向运动估计是目前学术界比较流行的一种算法，但是它在使用原始的参考帧和搜索帧进行运动估计的前提下只能达到2个像素精度。也就是说双边运动估计只能计算出最小2像素的运动幅度。小于2像素的运动在双向运动估计结果中就会出现误差而且插值帧精度只能达到1像素。1像素的误差在插值帧中会导致撕裂和抖动，图像分辨率越低越明显。

双向运动估计的第二个问题就在边界块的计算上。由于搜索过程以运动向量的一半位置为基准，参考块和搜索块同时移动，所以基准位置不能超过图像边界向内缩小p（搜索距离)的范围。否则参考或搜索块会超出图像边界从而取不到样本。

计算边界块时一般的做法是在上下边界只对运动向量进行水平移动，在左右边界只对运动向量进行垂直移动，而对于四角块就只能计算[0，0]位置，也就是不能搜索。

这对于画面内有目标进出的场景边界运动向量大部分会出错。尽管有论文提出了解决办法：当参考块或搜索块超出边界时将超出的部分截掉，只取没超出的部分计算MAD值。也就等于变相地将图像边界扩大了。但是最大也只能扩大16-1像素，出界的块只保留1像素的宽度，这样MAD的可信度也急剧下降，没有解决根本问题。

双向运动估计的最大问题在于计算出运动向量不可靠，尽管MAD值很低。下图则举出了同样的当前块位置处可以搜索到的其他匹配的参考块和搜索块位置。4个运动向量的参考块和搜索块都在背景上，所以匹配度MAD值都非常低，甚至比真实运动向量处的MAD值还低。由于双向搜索没有固定的搜索模板，只要在参考块移动的距离与搜索块移动的距离方向相反、大小相同的前提下找到两个一样的块就完成任务。所以双向搜索在搜索过程中很有可能搜到MAD值非常低但完全错误的运动向量。

白色方框为当前待搜索块，红色方框为参考块，绿色方框为搜索块。绿色箭头分别表示搜索块和参考块的运动向量。

对搜索位置的MAD值非常低，参考块（红色）和搜索块（绿色）几乎一样都在背景上，但都与真实运动方向相差甚远。

单向双边运动估计

单向运动估计和双向运动估计都有一个缺陷，就是画面边界块的搜索。当运动物体移入画面边界时，边界块就搜索不到匹配的块。当画面出现整体移动时，画面移动的反方向边界块搜索不到匹配块。但是运动物体移入画面是可以搜索到的。下图说明了遮挡的问题，下图 (a)是以当前帧为参考在前一帧搜索，下图(b)是以前一帧为模板在当前帧搜索。白色方块为当前块，绿色方块为搜索到最匹配的块，红色方块为搜索过程中不匹配的位置。可以看出(a)的前一帧中由于白色块所处的位置被遮挡，所以搜索的错误的位置（绿色块），虽然两个块的MAD值很低，但实际上白色块中的内容并没有移动。（b)中将参考帧和搜索帧调换后白色方块所处位置为足球，在当前帧中可以计算出足球的真实运动向量。

所以这里需要进行两次单向搜索，一次正向一次反向。正向搜索就是以当前帧为参考帧，以前一帧为搜索帧。以当前帧为模板在前一帧搜索最匹配的块。反向搜索是以前一帧为参考帧，以当前帧为搜索帧。以前一帧为模板在当前帧搜索最匹配的块。单向双边运动估计就是进行正反两次搜索，计算出两组运动向量最后插值出两幅插值帧。将这两幅插值帧加全合并得到最终的插值帧，这样就可以弥补单项搜索中遮挡引起的运动估计错误问题。

运动向量修正

由于复杂的模板纹理或相似的内容(如文字)都会导致搜索表面内有多个谷点。 快速搜索算法的前提是搜索表面有唯一的下降谷点，这样传统钻石搜索才能向MAD值最小的谷点移动。改进型钻石搜索中的邻块参考和扩展搜索都是为了解决非单一谷点的问题。但只能解决大部分情况，不能保证所有块的运动向量最终都能搜索到全局最优点。另外，以基于灰度值的模板匹配方法求出的MAD值有时也不能准确表示两个块的相似度。所以需要对计算出的运动向量进行修正。

插值

固定网络插值FGI（Fix Grid Interpolation)

插值的方法一共试验了两种：移动块插值和固定网格插值。传统的插值方法移动块插值，是将参考块和搜索块以一定的比例加权合并后插值到计算出的运动向量的二分之一处。这种插值方法插出的图像最接近真实的运动位置，但是插值帧也会出现空洞和重叠问题。固定网格插值是从计算出的运动向量的二分之一处采样，再插值带当前块对应的位置中。固定网格插值法插出的插值帧每一个像素都有且唯一的数据填充，不存在空洞和重叠问题。插值所用的样本块并不是当初计算运动估计是所用的参考块，所以在运动物体边界处会出现拉伸变形的现象。但在同一运动物体内部并没有影响。

固定网格插值能保证插值帧中每个像素都有值。要相邻两个块的运动向量不相同，插值出的图像就会有块效应，即块与块之间过渡不平滑。固定网格插值产生的块效应可以用块重叠运动补偿OBMC来消除。移动块插值将采取另外的方法消除块效应。

移动块插值SBI(shifted Block Interpolation)

移动块插值是将每个块找到的最匹配的搜索块放入运动向量的一半处进行插值。由于每个块的运动向量不可能完全相同，每个块插值的位置就不是整体的平移，这就会产生有的像素被多个插值块覆盖（重叠） ， 有点像素完全没有插值块（空洞）。

重叠插值

重叠部分像素需要进行高斯加权累加计算，样本块中的像素匹配值越高分配到的权重越大。首先计算样本块的匹配度，这里使用AD（Absolute Difference)值作为匹配度的参考，假设原始块边长为16，扩展倍数为2，块MB内每个像素s的AD值为：

其中MBref为参考块，MBsearch为搜索块，算出AD(s)后再按高斯分布分配权值：

这里μ固定取0，σ的最佳值为10（可调整）。取σ=10时两个像素间灰度值差超过30时权重几乎降为0,也就是说灰度差超过30的像素不会被累积到插值帧中，灰度差越低，像素值对插值帧贡献越大。

最终求加权累加插值像素ws (Weighted Sum)的方法如下：

I为重叠次数， MBinterpolate为待插值块。待插值块的采样方法将会在后面介绍。重叠次数I是未知的，直到所有块的加权累加过程都计算完后才知道插值帧中像素s处一共被多少个块所覆盖。累加过程中每个重叠的高斯权重和sum(w_overlap)不等于。所以最后还要对结果进行归一化处理：

空洞插值

为了减少空洞的面积，插值时把采样块的尺寸扩大，以n倍原始块边长的大小采样（最佳倍数n=2，如果原始块边长为16那么采样边长为32，也就是说采样块各边向外扩展1/2)。扩展后插值重叠面积增加，两个块之间小于16像素宽度的空洞都会被填充。

扩展部分只用于采样和插值，运动估计部分还是使用原始的块大小，采样和插值方法保持不变。经过试验，n=2时覆盖效果最佳而且运动物体边界处扭曲和重影较小，n>2时重影现象严重。针对视频聊天小幅度运动场景n=2时效果较好。当相邻两个插值块的间隔超过两倍的扩展距离时还是不可避免的会出现空洞，这里加入一个填补空洞的计算。填补空洞的方法分两个部分，帧间填补和帧内填补。帧间填补就是将正向和反向两次运动估计插值出的中间帧进行互补。定义正向运动估计插值帧为IIM,反向运动估计插值帧为IIMR。取IIMR没有,IIM_R有的值填入IIM中，再取IIMR没有，IIM有的值填入IIMR中。

帧内填补是从空洞的边缘像素开始,计算每个空像素周围8个相邻非零像素的均值，然后填入空像素中。从最外层边缘空像素开始，一次计算一圈直到空像素全部填满。

亚像素插值

使用单向双边运动估计计算出的结果是全运动向量是从当前帧到前一帧的距离（或者反过来），中间插值时需要使用半运动向量来移动，即 ，当运动向量为奇数时，半运动向量则出现小数部分。插值前要预先计算好亚像素样点帧，从样点帧中取值插入正像素位置来代替1/2像素的位移。亚像素样点帧分3个：水平方向、垂直方向和对焦方向。计算亚像素的系数参考H.264中的参数。

块重叠运动补偿OBMC(Overlapped Block Motion Compensation)

直接将在前一帧搜索到的最佳匹配块1/2mv的距离复制到插值帧会导致块效应，因为每个块的运动向量有可能不相同，插值后块与块之间不能很好的衔接，特别是在运动物体边界处块效应最明显。采用OBMC方法可以使块与块之间有较为平滑的过渡从而消除块效应。

以16×16大小的块为例，首先计算一个双倍于宏块大小（32×32）的二维上升余弦窗函数数wcos，见下图。wcos的高度为加权系数，范围为[0 1]。

然后将当前待插值块等分成4个子块见 下图，然后每个子块单独进行插值。下面以sbI为例，其他子块按相同方法计算。 为左上子块，参考的邻块为nbleft、nbtopleft、nbtop。每个子块总共需要取4个子块样本：

1.平移至自身mv位置处取样本nbleft ；2.平移至左边邻块nbleft的 位置处取样本sbleft； 3.平移至左上邻块nbtopleft的mv位置处取样本sbtopleft ；4.平移至上边邻块nbtop的mv位置处取样本sbtop 。最后将4个子块样本分别按照在上升余弦窗wcos中对应的位置wcosself，wcosleft，wcostopleft，wcostop加权再求和得到最终的插值子块。

4个子块样本在上升余弦窗中的对应位置各不相同。 使用自身mv取得的样本的权重为wselfsbl=wcos (x=9,…,16,y=9,…,16),见下图(b)。 使用左邻块mv取得的样本权重为wselfsbl=wcos (x=1,…,8,y=9,…,16),见下图(d)。 使用上邻块mv取得的样本权重为wselfsbl=w_cos (x=9,…,16,y=1,…,8),见下图(h)。

子块的4个样本权重中每个像素都满足：

所以加权之后的子块样本不需要归一化，直接将样本中每个像素单独相加即为插值子块。

右上和右邻块，sb3的邻块为左、左下和下邻块，sb4的邻块为下、右下和右邻块。与其对应的样本权重见下图。

结尾

在倍帧领域研究成果和业界冷门的情况下，经过半年的深入优化，我们已经实现了非常好的倍帧效果，对于静止或小运动来说都能做到非常好的插帧效果，大运动也能非常好的适应场景变化。

这一技术后续可以广泛应用于视频应用场景，在传输编码前将帧率进行下采样，经过编码和网络传输后，在接收端再进行帧率上采样，还原原始视频，可以极大的节省网络传输带宽。

当然这一技术目前也存在很多优化的地方，我们也在持续进行优化，后续将会有升级版本进行分享，敬请期待！