加权多视图聚类方法应用于快速帧间模式决策的HEVC改进算法

刘子龙，罗小龙

(上海理工大学 光电信息与计算机工程学院，上海 200444)

1 引 言

随着超高清影音享受的消费升级，视频传输的数据量急剧增大.人们对于低延时的视频传输需求也与日俱增，Joint Collaborate Team on Video Coding(JCT-VC)已经提出了新一代的高效率视频编码标准(High Efficiency Video Coding，HEVC)[1].在保证视频质量大致相同的前提下，该标准与其上一代压缩标准H.264/AVC相比，压缩率提高了2倍.这主要借助其混合编码框架来实现，并引入许多更加灵活的新方法.为进一步减少时空冗余，编码冗余和视觉冗余，HEVC将通过四叉树划分得到的编码树单元(CTU)作为独立的编码单元.目的是一个CTU可以被编码成不同的块，以适应不同的视频内容.对每个不同深度的编码单元(CU)而言，都可以结合各自不同的最佳预测单元(PU)和变换单元(TU)实现编码.通过率失真(RD)代价遍历计算所有可能的CU，PU和TU组合，其中RD代价值最小的组合即为最佳组合.显而易见，该策略极大地增加了计算复杂度，使其无法在低延时的视频传输中应用.

因此，为解决这个难点，本文引入机器学习方法，用聚类方法去代替耗时的预测编码模式遍历选择.减少帧间预测候选模式数量，从而降低复杂度.本文主要贡献在于探索多视图聚类方法，在视频帧间编码中的应用.

2 研究现状

为解决这一难题，许多快速编码算法已经被提出.有的学者在文献[2]中提出基于解码辅助的HEVC帧间预测算法，并结合绝对双向预测差之和与模板匹配运算，帮助合并模式决策和帧间模式决策.在文献[3]中作者提出提前选中跳过(SKIP)模式的快速帧间模式决策算法，具体通过使用SKIP模式，合并(Merge)模式，帧间2Nx2N的PU模式的率失真代价值来判断.在文献[4]中，作者提出基于分层分类的HEVC帧间编码算法，用来降低复杂度.

近来，诸多学者还通过引入机器学习的方法来降低HEVC编码复杂度.在文献[5]中，降维和分类技术，包括逐步回归，随机森林，变量选择，主成分分析，多项式分类器，被用于快速CU分割.在文献[6]中提出基于RD代价优化的模糊支持向量机快速CU决策算法，其中多级分类的级联过程指的是CU划分.在文献[7]中提出应用支持向量机(SVM)在减少计算复杂度的同时维持较高的编码质量.主要通过减少CU尺寸划分决策和PU模式决策的计算量来达到目的.

同样，深度学习在提高压缩效率方面也取得了显著的成果.在文献[8]中，考虑到只有时间信息被CNN利用去进行帧间预测，这无疑降低了它的预测精度.所以学者提出基于时空信息的帧间预测神经网络.该神经网络结构主要由一个全链接网络和一个CNN组成.在文献[9]中，基于CNN的快速CU模式决策算法被提出，用于HEVC帧间预测编码.

已知，HEVC支持4种CU模式：64×64，32×32，16×16，8×8.每种CU模式又对应11种候选PU模式：跳过模式(2N×2N)，2种帧内模式(2N×2N，N×N)以及8种帧间模式(2N×2N，2N×N，N×2N，N×N，nL×2N，nR×2N，2N×nU，2N×nD).每种PU模式都会进行复杂和耗时的运动估计和运动补偿.通过实验可以证明，视频序列中存在大量时域冗余且对同一物体而言，相邻帧间的变化很小.尤其对于运动缓慢相对静止的物体或纹理平滑的背景区域而言，几乎没有变化.所以如果我们可以识别出它们的类别信息，那么待编码块通过复用邻近帧的同类已编码块的CU和PU模式信息，就可以大大减少最佳CU和PU模式的选择匹配过程，从而显著提升编码效率.

由于HEVC编码的高分辨率视频信息是未处理的无标签信息，且本身数据量较大.使用单一视图聚类方法，难免陷入“管中窥豹，盲人摸象”的境地，很难达到预期分类效果.因此，本文引入多视图聚类的方法来解决之一难题.视频流中包含着某一特定物体在不同时间下的状态，包括不同的运动姿态，由光线等环境因素引起的不同明暗变化，近远景切换导致的多角度刻画等等.以上各帧中反应同一物体的每个不同特征称为一个视图.将表达同一实例的不同视图进行归类分析，使学到的信息更完整，即为对无标签数据的无监督多视图聚类学习.该方法已被广泛应用于医学影像辅助诊断，自然语音处理，视频监控和人脸识别等领域.文献[10-12]HEVC帧间预测的第一帧只能采用帧内预测，这样的设定无疑为多视图聚类提供了便利条件.由于CU划分模式只有4种，在划分过程中，不可避免的会包含其他类别的部分信息，对最终的聚类结果造成干扰.为此本文又引入特征选择以及赋予不同权重值的方法，辅助聚类实现.

在文献[13]中，提出了基于多视图聚类的HEVC快速帧内模式决策算法.主要应用无监督的加权多视图聚类方法，来减少帧内预测候选模式数量.但该方法只利用了空域相关性，并未考虑时域相关性.且特征选择条件单一，其聚类算法计算量也相对较大.本文针对以上3点，都做出了不同程度的合理优化.

3 本文算法的提出

本文沿袭文献[13]的基本思路，在文献[14]的基础上，通过加权多视图聚类算法的提出，以特征值的选择作为辅助，不仅使相关运动实例的视图获得更大的权重，还可以辅助聚类算法更好的实现.在文献[7]的基础上，新增了合并标签(Merge Flag)，与原有的运动矢量(Motion Vector)，跳过标签(SKIP Flag)和率失真优化比率(RDO ratio)共同作为本文的特征值，用于PU模式决策.更进一步的突出与其相关的聚类信息，用以实现快速帧间模式决策选择.算法的核心思想是探索视频帧间结构信息和相应模式决策的相关性.

核心算法是基于一种快速和高效的基于核的K均值聚类算法[13]，核函数如公式(1)所示：

(1)

(2)

其中j=1，…，Nk=1，…，K；Nk代表第k个聚类中的数据个数.

因为对于特定核函数，相对应的非线性映射φ是无法明确计算的.为了计算公式(1)中的欧几里德平方距离，文献[13]中引入核矩阵的方法来计算距离.为提高计算速度，本文采用文献[14]的方法，通过条件正定核函数简化欧几里德平方距离：

(3)

为了将该算法更好的应用于多视图聚类中，借鉴参考文献[13]的研究思路，提出加权多视图聚类算法.通过为视图增加权重，剔除完全无信息量的视图并自动根据视图信息量的重要性，成正比的为其赋予不同大小的权重值.具体推导过程如下：

(4)

(5)

(6)

限制条件：

结合公式(3)和公式(4)，公式(5)可重写如下：

(7)

(8)

为更进一步提高该算法在HEVC帧间模式预测中的表现，在进行多视图学习的同时，还引入了特征选择算法.本文主要选取合并标签，运动矢量，跳过标签和率失真优化比率这4个特征值：

(9)

其次为了在运行编码决策时最小化率失真性能下降，还需引入以下损失函数：

(10)

在编码过程中，对于给定的带有特征向量x的PU，通过下式计算它每个候选模式的得分：

(11)

然后通过上文所提到的多视图聚类算法目标函数，预测得分最低的模式.

4 实验验证

本次试验中使用的HM参考软件版本为16.8，因为本文目标是通过多视图聚类的机器学习方法，来预测编码模式从而降低延时.所以采用统一配置：低延时编码—编码帧只有第一帧是帧内方式编码，并作为及时解码刷新(Instantaneous Decoding Refresh，IDR)帧和一系列后续的普通P和B帧(Generalized P and B Picture，GPB)组成，因为编码帧序列维持不变，所以减少了延时.其他所有的环境设置都遵守官方初始化的HM测试状态进行.实验所用CPU是Inter Core I5-4200，2.80GHz×4核，8GB运行内存搭载Windows 10操作系统.

官方测试序列中5类共20条测试序列被用来衡量所提算法的优劣，详情见表1.编码复杂度由平均编码时间节省(TS)参数来衡量，因HM16.8统计的编码时间精确到了毫秒级，所以每次测试结果都略有不同，所以采用测试3次求平均值的方法，具体参见公式(12).

表1 测试序列属性

(12)

量化步长(QP)分别选取22，27，32和37.编码视频质量通过BDBR参数来衡量.

本文算法对上述视频序列处理的过程中，对关键物体的多视图信息进行了准确的提取.现将部分提取结果展示在图1中.

图1 部分多视图提取结果

几个典型相关算法的编码表现对比，在表2中呈现.为了更进一步对比，每一类的平均表现和所有测试序列的平均表现，本文分别做出统计.对比的算法有文献[4]—基于分层分类的HEVC帧间编码算法；文献[7]—支持向量机算法；文献[13]—基于多视图聚类的HEVC快速帧内模式决策算法.

分析表2中每一类的平均表现可得，大部分算法都可以在E类实现最大的时间节约.因为E类序列大部分是简单纹理内容和缓慢移动的物体.所以各种算法都可以在E类实现更大的CU划分策略，也就意味着可节省更多的时间.而D类恰恰相反，一是因为该类大部分都是复杂文理内容和快速移动的物体.还有一个不容忽视的原因，是该类本身的分辨率最小，所以HEVC原本的编码时间与其他类相比就是最短，自然各种算法的节约时间有限.

表2 典型相关算法实验对比结果

分析表2中总的平均表现，文献[13]获得了最快的压缩速度，分别比文献[4，7]和本文所提算法提高了8.751%；24.505%和13.841%，但它的码率损耗比它们分别多出0.048%；1.323%和1.143%．所以综合来看，文献[13]并没有很明显得优势.况且文献[13]是全帧内预测模式，本身相对于帧间预测模式就会节省更多的编码时间.本文所提算法的压缩速度虽然排名第3，分别比文献[4，7，13]提高了-5.09%；10.664%和-13.841%；但码率损耗分别比它们节省1.095%；-0.18%和1.143%.综合来看，本文所提算法获得了较好的效果，达到优于同目标各类算法的目的.当然，实验结果再一次证实——更多编码时间的节省是以牺牲视频压缩质量为代价的.

5 结 论

本文提出将加权多视图聚类方法用于HEVC帧间模式预测的想法，主要通过将一种快速和高效基于核的K均值聚类算法扩展到多视图情况下，并通过不同权重值量化视图信息的重要性.再结合合并标签，运动矢量，跳过标签和率失真优化比率的特征选择，进一步优化无监督机器学习得到的各类性能指标.从而更全面的学习视频帧间的时间相关性，达到减少帧间预测候选模式数量的目的，显著降低视频编码的复杂度，大大减少视频传输的延迟.经过理论分析和数学推导，证明本文所提算法可以有效降低编码计算复杂度；之后经过实验的进一步验证，得出可以节省高达36.690%的编码时间，但只造成0.278%的码率增加.并且通过与同类型和同目标算法的横向比较，也证实所提算法的综合优势明显，达到预期目标.