一种面向并行视频编码的动态slice控制方法

摘要

本发明提出一种面向并行视频编码的动态slice控制方法。该方法在编码过程中，根据已编码帧的slice并发状态构建的马尔可夫链模型来预测当前待编码帧的slice并发状态，从而确定当前待编码帧的slice的数目，再根据在同一场景中的已编码帧的加权编码时间来预测当前帧的计算复杂度，将相应数目的分配单元分配给各个slice，使每个slice的编码时间近似相等，平衡slice之间的计算复杂度。实验结果显示，本发明提出的方法与传统的基于H.264的固定slice并行编码方法相比，编码速度提高了30%，且具有相近的视频压缩效率。

说明书

技术领域

本发明涉及计算机视频编码领域，具体涉及一种面向并行视频编码的动态slice控制方法。

背景技术

多核处理器在计算机市场的盛行，使得拥有4核CPU的个人计算机变得非常普遍。这也 使得像视频会议这样的实时应用在个人计算机上的并行化更加可行。并行视频编码方法大致 可以分为3类：基于帧的并行编码方法、基于片（slice）的并行编码方法和基于宏块的并行 编码方法（参考文件1：C.MeenDerinck,A.Azevedo,M.Alvarez,et.al.,“Parallel Scalability of  H.264,”Proc.of 1th Workshop on Programmability Issues for Multi-Core Computers,2008）。基于 帧的并行编码方法常用于离线式视频编码，并不适用于在线视频会议等实时视频编码，因为 在这种场景中，在当前帧被编码的时候其后续帧往往还获取不到。基于宏块的并行编码方法 利用同一帧中宏块的并行性，可用于实时视频编码，然而基于宏块的并行方法并行粒度非常 小，故用于同步的开销较大。基于slice的并行编码方法是以上两种的折中，同步开销小，同 时其也能适用于实时视频应用，是目前编码器中普遍采用的方法。

传统的基于slice的并行视频编码方法中，每帧的slice数目是固定的（往往等于CPU核 数），每个slice包含的宏块数也是相等的。这种固定slice的并行方法有两个缺点。首先，在 实际编码过程中，由于某些CPU资源被其他应用程序占用，使得当前编码帧的某些slice没 有分配到CPU资源，同一帧内的多个slice可能不会同时开始编码。这样将导致这些没有分 配到CPU资源的slice不能立刻开始编码，可能需要等到其他slice编码完成之后才能开始， 因而增加了编码端其他slice的等待时间。其次，同一帧图像内的不同位置的纹理和运动复杂 度是不同的。比如，视频会议的视频序列往往在图像中间部分有较大的运动，而在顶部和底 部有着相对较小的运动。因而将宏块均匀分配给slice，会使得slice的编码时间不均匀，这也 会增加slice线程间的相互等待时间。目前，还没有人提出针对第一个问题的有效解决方案， 对于第二个问题，已有学者提出了一些解决算法。F.H.Seitner等人提出一种方法，当一个线 程完成其slice的编码后，将不会等待其他线程，而是开始编码下一帧的一个独立slice（参考 文件2：F.H.Seitner,M.Bleyer,R.M.Schreier and M.Gelautz,“Evaluation of Date-parallel  Splitting Approaches for H.264 Decoding,”Proc.of the 6th International Conference on Advances  in Mobile Computing and Multimedia,2008）。该方法实际上引入了基于帧的并行方法来提高编 码器的并发性，但并不适用于实时视频编码。N.Zhang等人（参考文件3：K.Ba,X.Jin and S. Goto,“A Dynamic Slice-resize Algorithm for Fast H.264/AVC Parallel Encoder,”Proc.of  International Symposium on Intelligent Signal Processing and Communication Systems,pp.1-4, 2010）和K.Ba等人（参考文件4：K.Ba,X.Jin and S.Goto,“A Dynamic Slice-resize Algorithm  for Fast H.264/AVC Parallel Encoder,”Proc.of International Symposium on Intelligent Signal  Processing and Communication Systems,pp.1-4,2010）提出一种使用之前一帧的编码时间平衡 各编码线程的计算复杂度的方法。然而对于有着频繁场景切换的视频序列，该方法由于会出 现错误的预测，效果并不好。B.Jung等人提出一种两阶段的自适应的slice大小选择方案（参 考文件5：B.Jung and B.Jeon,“Adaptive Slice-level Parallelism for H.264/AVC Encoding Using  Pre Macroblock Mode Selection,”Journal of Visual Communication and Image Representation,pp. 558-572,2008），该方法在预处理阶段，首先估算各个宏块的计算复杂度，然后才进入真正的 编码阶段，为每个slice进行编码。这种方法往往能准确预测该帧的计算复杂度，但该方法的 预处理阶段也增加了额外的编码开销。

发明内容

本发明的目的是为了解决上述现有固定slice的并行编码方法的两个缺点。本发明提出一种动态slice控制方法，旨在提高基于slice的并行视频编码方法的性能。

本发明提出的一种面向并行视频编码的动态slice控制方法，具体包括如下步骤：

步骤一：利用由已编码帧的slice并发状态构建的马尔可夫链模型来预测当前待编码帧的 slice并发状态，从而确定待编码帧中slice的数目。

设编码器的状态有两种：状态A表示所有编码线程都同时分配到了CPU，状态B表示至 少有一个编码线程在编码开始时未分配到CPU；编码器的状态构成了马尔科夫链，并且编码 器在下一个时间点t_i+1的状态只受当前时刻t_i的影响。当前帧的slice的数目S根据下式确定：

$S=\left(\begin{array}{c}M,\mathrm{ifE}\left(A\right)\le E\left(B\right)\\ M-1,\mathrm{otherwise}\end{array}\right)$

M表示当前CPU最大可用核数；E(A)和E(B)分别表示当前帧分别处于前一帧为状态A 和状态B时的期望并行编码时间，根据下式确定：

E(X)＝P_ZA·T(X|A)+P_ZB·T(X|b)

P_XY代表由状态X向状态Y的转移概率，设编码第一帧前的初始状态为状态A，初始的 转移概率P_AB和P_AA均为0.5；T(X|Y)表示当前帧的实际状态是Y，而假设其状态为X时该帧 的并行编码时间，X，Y∈{A，B}。

步骤二：为步骤一得到的S个slice分配分配单元。具体是：首先检测当前帧是否有场景 切换，若有，设置已编码帧的数量和加权SAD值SAD_w均为0，并将分配单元平均分配给当 前帧的各slice；若没有，计算当前帧每个slice的平衡预测编码时间t_p(s)，然后按照时间复杂 度给各个slice分配相应数目的分配单元，使得每个slice的编码时间都近似等于t_p(s)。

所述的平衡预测编码时间t_p(s)根据下式确定：

$t_p\left(s\right)=\frac{\left({\Sigma }_{j=1}^R{t}_p(f_K\right[j\left]\right)}{S},s\in [1,S]$

K表示当前帧为第K帧，R表示分配单元的个数，t_p(f_K[j])表示当前帧中的第j个分配单 元的预测编码时间，t_p(f_K[j])＝t_w(j)，j∈[1，R]，t_w(j)为当前帧之前的K-1个已编码帧的第j 个分配单元的编码时间的加权平均值，如果当前帧有场景切换或者当前帧是第1帧，则t_w(j)的 值设置为0。

步骤三：编码当前帧，然后更新转移概率P_XY和加权平均值t_w(j)，结束当前帧的编码，利 用更新的相关参数开始进行下一帧的编码。

本发明方法的优点和积极效果在于：本发明在编码过程中动态地确定slice的数目，并平 衡了slice之间的计算复杂度，提高了编码效率。在机器忙碌的时候，本发明方法与固定slice 的方法相比，编码速度可以平均提升30%，同时率失真性能几乎没有变化。

附图说明

图1是本发明动态slice控制方法的整体步骤流程图；

图2是本发明的编码器状态转换图；

图3是本发明中同一场景中的8个连续帧的每个分配单元的编码时间图；

图4是本发明中同一场景中的8个连续帧的分配单元的SAD（Sum of Absolute Difference， 绝对残差和）值图；

图5是本发明实施例中加速比与CPU核数关系曲线对比图；

图6是本发明实施例中的率失真曲线对比图。

具体实施方式

下面将结合附图和实施例对本发明的技术方案作进一步的详细说明。

本发明提出一种面向并行视频编码的动态slice控制方法，通过计算设备处于两种不同状 态（空闲/忙）下编码器所需的编码时间的期望值，来确定当前帧的slice数量。该方法基于马 尔可夫链模型。本发明还通过预测待编码帧中每个分配单元的编码时间来为每个slice分配相 应数目的分配单元，从而平衡同一帧内各个slice的编码复杂度。实验结果显示，本发明方法 与传统的基于H.264的固定slice并行编码方法相比，编码速度提高了30%，且具有相近的视 频压缩效率。

本发明提出的一种面向并行视频编码的动态slice控制方法，整体步骤如图1所示，下面 对各步骤进行具体说明。

步骤一：利用由已编码帧的slice并发状态构建的马尔可夫链模型来预测当前待编码帧的 slice并发状态，从而确定待编码帧中slice的数目。

设编码器的状态有两种：状态A表示所有编码线程都同时分配到了CPU，状态B表示至 少有一个编码线程在编码开始时未分配到CPU。

设视频序列中的每一帧的开始编码时间为一个离散的时间点(t₀，t₁，...，t_N-1)，其中N表示 已编码的帧数。在t_i时刻，编码器的状态将会是状态A和状态B中的一种。同时，假设编码 器在下一个时间点t_i+1的状态只受当前时刻t_i的影响，而独立于任何之前的时间点所处的状态。 编码器的状态构成了马尔科夫链，其状态转移过程如图2所示。其中P_XY代表由状态X向状态 Y的转移概率，X，Y∈{A，B}。

由于前一帧的编码状态在编码当前帧之前是已知的，因而只要知道此刻的状态转移概率， 那么当前帧位于各个状态的概率便可知道。本发明方法将计算每种状态转移发生的频率，并 将它们作为实际的转移概率，比如P_XY被设置为编码过程中编码器从状态X转移到状态Y的 频率。由于一个状态转移的发生频率在编码过程中会改变，因此P_XY的值也会随着编码的进行 而动态地更新，在每编码完一帧后，统计所有已编码帧的状态来更新P_XY。

令T(X|Y)为当前帧的实际状态是Y，而假设其状态为X时该帧的并行编码时间。设当前 CPU最大可用核数为M，即当前帧最多可分为M个slice，编码当前帧的非并行时间为T_f， 即当前帧的每个slice依次编码完成所需要的总时间为T_f。在本发明方法中，假设每次最多只 有一个slice编码线程分配不到CPU。理想情况下，每个slice的编码时间都是相同的，由于 本发明方法平衡了slice之间的计算复杂度，所以这一点可以得到大概的保证。T(X|Y)， X，Y∈{A，B可由下式计算得到：

T(A|A)＝T_f/M                           （1）

T(A|B)＝2·T_f/M                        （2）

T(B|B)＝T(B|A)＝T_f/(M-1)               （3）

式（2）对应一个slice的编码线程未被分配到CPU，从而不得不等到任何一个其他slice 的编码线程结束后才能开始。

假设之前一帧的状态为Z，Z∈{A，B}，令E(X)为待编码帧处于状态X时的期望并行编码 时间。E(X)可由下式计算得到：

E(X)＝P_ZA·T(X|A)+P_ZB·T(X|B)               （4）

将上述式（1）、（2）、（3）代入（4）中可得到编码时间的期望值。slice的数目S则可以 由下式来决定：

$S=\left(\begin{array}{c}M,\mathrm{ifE}\left(A\right)\le E\left(B\right)\\ M-1,\mathrm{otherwise}\end{array}\right)---\left(5\right)$

如图1所示，步骤一中首先根据上面的公式确定待编码帧分别处于状态A和状态B时的 期望并行编码时间E(A)和E(B)，然后根据式（5）来确定slice的数目S。本发明方法中编码 第一帧前的初始状态为A，初始状态转移概率P_AB和P_AA均为0.5。

步骤二：根据步骤一中确定的slice的数目，根据在同一场景中的已编码帧的加权编码时 间来预测当前帧的计算复杂度，将相应数目的分配单元分配给各个slice，使每个slice的编码 时间近似相等。

在确定了slice的数目之后，开始考虑平衡slice的编码复杂度，这部分对应图1中的步 骤二。为方便说明，本发明引入分配单元的概念，分配单元是分配给每个slice的最小编码单 元，其大小可以为一个宏块或者一个宏块行或两个以上的多个宏块行。在本发明中，将分配 单元设为一个宏块行。图3显示了同一场景中的8个连续帧的每个分配单元的编码时间，其 中，横坐标代表分配单元号，纵坐标为对应的编码时间。可以看到，同一场景中时域相邻的 分配单元的编码时间是类似的。本发明正是利用这一点，来预测待编码帧中每个分配单元的 编码时间。

假设在同一场景中的K-1个已编码帧f₁，f₂，...，f_K-1，以及一个待编码帧f_K，每帧有R个分 配单元。令t(f_i[j])为第i帧的第j个分配单元的实际编码时间，其中i∈[1，K-1]，j∈[1，R]。 为了平衡slice之间的复杂度，先探测当前帧是否发生场景切换，然后再确定每个slice的边 界。场景切换是指当前帧包含的纹理信息与前一帧有着很大的不同。

对于如何高效地检测视频序列中的场景切换，目前有学者已经进行了大量工作。本发明 方法使用一种简单的基于SAD的方法来检测场景切换。现有方法的研究表明，在同一场景中 的连续两帧的SAD值与其他任何连续两帧的SAD值相近。图4显示了所有分配单元的SAD 值，其中，横坐标代表分配单元号，纵坐标为相邻两帧的分配单元之间的SAD值。第i帧和 第i-1帧之间的SAD值SAD(i)由式（6）定义：

SAD(i)＝∑|p_i(r)-p_i-1(r)|               （6）

其中，p_i(r)表示第i帧光栅顺序为r的像素的像素值。

然后，定义一个加权SAD值SAD_w，该值初始为0，在编码完一帧后的步骤三中对它进行 更新。

如果SAD(i)大于α·SAD_w，则认为当前帧相比之前的帧为不同的场景，检测到场景切换。 这里α是一个预先定义的系数，实验结果表明该值设为1.3时效果最好，因此本发明实施例中 将α设置为1.3。如果在当前帧检测到了场景切换，清除已完成编码的帧的信息，并设置已编 码帧数（K-1）和加权SAD值SAD_w均为0，并为当前帧的slice平均分配分配单元。如果在 当前帧未检测到场景切换，使用以下方法来为该帧的slice分配分配单元。

令t_p(f_K[j])为在当前第K帧中的第j个分配单元的预测编码时间。t_p(f_K[j])的值由下式得到：

t_p(f_K[j])＝t_w(j)，j∈[1，R]                     （7）

其中t_w(j)为当前帧之前的K-1个已编码帧的第j个分配单元的编码时间的加权平均值。如 果当前帧包含一个新的场景或者当前帧是第1帧，则已编码帧的数量为0，此时t_w(j)的值被 设置为0。t_w(j)的值在编码完当前第K帧之后的步骤三中更新，如下式所示：

t_w(j)＝0.5*t_w(j)+0.5*t(f_K[j])               （8）

当前帧每个slice的平衡预测编码时间t_p(s)由下式计算得出：

$t_p\left(s\right)=\frac{\left({\Sigma }_{j=1}^R{t}_p(f_K\right[j\left]\right)}{S},s\in [1,S]---\left(9\right)$

然后，按照时间复杂度给各个slice分配相应数目的分配单元，使得每个slice的编码时间 都近似等于t_p(s)。

步骤三：编码当前帧，更新步骤一和步骤二中使用的相关参数，至此结束了当前帧的编 码，可利用更新的相关参数开始进行下一帧的编码。重复执行步骤一到三，可完成整个视频 的编码。

表1展示几种方法编码速度的比较结果，速度由每帧的平均编码时间来表示。除了本发 明提出的方法（Proposed）和固定slice方法（F.S.）的编码时间，非并行编码时间（N.P.）也 在表中给出。可以看到，本发明提出的方法相对于固定slice方法平均可以提升编码速度30%。

表1编码时间比较

图5展示了本发明的方法与参考方法的加速比，其中，横坐标为CPU核数，纵坐标为加 速比（Speed-ip ratio）。图中的虚线Ideal表示理想的加速比，即每一帧的slice的个数等于 CPU的核数。F.S.’表示的实线为在测试机器空闲的时候用F.S.方法得到的加速比。Proposed 表示的实线和F.S.表示的实线分别是本发明提出的方法和F.S.方法在测试机器忙碌的情况下 的加速比。从图中可以看出，在机器忙碌的时候，本发明的方法相比F.S.方法有着更高的加 速比。

如图6所示，还测试了本发明方法的率失真性能，其中，横坐标表示编码码率(Biterate， 单位kbps)，纵坐标表示亮度峰值信噪比（Peak Signal-to-Noise Ratio,PSNR），图6中给出了 对两个视频序列Vidyo1和ShuttleStart进行编码得到的率失真曲线。实线表示在测试机器空 闲的时候进行编码，虚线表示在测试机器忙碌的时候进行编码。由图6所示的测试结果，证 明了本发明的方法相比F.S.方法只有着很微小的率失真性能差异。