专利摘要

本发明公开了一种基于贝叶斯决策的HEVC块划分快速方法。本发明首先利用基于平均灰度差值的场景变换检测将视频序列分成在线学习阶段和快速划分阶段。其次对于在线学习阶段和发生场景变换的视频帧，在每一个划分深度，分别提取CU的Jinter和Jintra为特征值，以此建立混合高斯模型，模型的具体参数根据以K‑Means算法初始化的EM算法确定；对于处于快速划分阶段的待划分的CU，提取其特征值，根据混合高斯模型求出是否划分的条件概率，最后利用最小风险的贝叶斯公式求出风险较小的决策，作为当前CU是否划分的判断依据。本发明降低了算法复杂度，能大幅度减少编码时间。

权利要求

1.一种基于贝叶斯决策的HEVC块划分快速方法，其特征在于将CU划分操作看作二分类问题，即W＝{ω_N，ω_P}，其中ω_N表示当前CU不继续划分，ω_p表示当前CU继续划分，并采用最小风险贝叶斯决策来解决二分类问题，具体实现步骤如下：

步骤1、离线学习得到损失函数C_NP和C_PN以及先验概率P(ω_N)和P(ω_P)；

步骤2、对于传入的图片序列，判断其是否处于在线学习阶段或者场景是否发生了变化，若当前帧处于在线学习阶段或者是场景变换帧，根据HM标准算法对其进行深度划分，提取并存储每个深度的特征值，跳转到步骤7；否则执行步骤3；

步骤3、判断图片是否为快速划分阶段的第一帧图像，若不是，执行步骤4；否则提取在线学习阶段或场景变换帧存储的特征值，并基于特征值建立混合高斯模型，模型的统计参数用以K-Means算法初始化的EM算法来估计；

步骤4、提取当前CU的特征值，求得p(X|ω_R)R∈{N,P}；

提取待划分的CU的特征值X，根据所处深度求得在同深度的混合高斯分布上的函数值，即p(X|ω_N)和p(X|ω_P)；

步骤5、决定是否划分当前CU，若划分，对每一个Sub-CU执行步骤1-步骤5所述过程；否则不划分当前CU，跳到步骤6；

针对当前CU划分的判断如下：计算比较 和 大小，若 较大，将当前CU划分为四个Sub-CU，并对每一个Sub-CU执行步骤1-5；

步骤6、对该CU进行编码，若当前帧图像CU已经划分完成，执行步骤7；否则，对下一个CU执行步骤1-6所述过程；

步骤7、对下一帧图像执行2-7步骤所述过程，直至编码完所有的视频帧。

2.根据权利要求1所述的一种基于贝叶斯决策的HEVC块划分快速方法；其特征在于步骤1具体过程如下：

提出将错误决策带来的率失真性能的下降作为贝叶斯风险函数，建立基于最小风险的贝叶斯决策模型，以降低错误决策带来的率失真性能损失，完全率失真代价函数如下式所示：

J_FRD＝(SSE_luma+ω_chroma×SSE_chroma)+λ_mode×B_mode

其中，SSE_luma，表示亮度的原始图像块和重建图像块之间的像素差误差平方和；SSE_chroma表示色度信号的原始图像块和重建图像块之间的像素差误差平方和，ω_chroma为色度分量的权重系数，λ_mode是拉格朗日乘数，B_mode是对当前编码模式时所需要的比特数；

对于64×64，32×32，16×16大小的CU，分别通过离线学习训练得到损失矩阵C，损失矩阵定义如下式所示：

$C=\left(\begin{array}{cc}{C}_{NN}& C_{NP}\\ C_{PN}& C_{PP}\end{array}\right)$

此处C_PN和C_NP定义如下：

$C_{PN}=\frac{J_{FRD,P}-J_{FRD,N}}{J_{FRD,N}}$

$C_{NP}=\frac{J_{FRD,N}-J_{FRD,P}}{J_{FRD,P}}$

J_FRD，N和J_FRD，P分别是当前待划分CU不继续划分和继续划分成四个子块对应的完全率失真代价；C_NP表示假设ω_N为真，即率失真结果为“不划分”时判断假设ω_P成立，即对CU采取“划分”决策时所带来的风险代价；C_PN表示假设ω_P为真，对CU采取“不划分”决策时所带来的风险代价；C_NP和C_PN大于等于0，当决策是正确的时候(C_NN或C_PP)，决策的损失值为0；

先验概率P(ω_R)是通过统计当前深度下，作出ω_R决策的CU占所有CU的比重得到的，即

P(ω_R)＝当前深度属于ω_R的CU数/当前深度CU总数；

其中R为N或者P。

3.根据权利要求2所述的一种基于贝叶斯决策的HEVC块划分快速方法；其特征在于步骤2具体实现如下：

用平均灰度差值来衡量视频运动的剧烈程度，即是否发生场景变换，视频序列中相邻两帧在相同位置上的像素点的平均灰度差值计算如下式所示：

$G=\frac{1}{P·Q}\underset{i=0}{\overset{P-1}{\Sigma }}\underset{j=0}{\overset{Q-1}{\Sigma }}|G_n(i,j)-G_{n-1}(i,j)|$

式中，P、Q为图像宽度和高度，G_n(i，j)为第n帧像素点(i，j)处的灰度值，G_n-1(i，j)为第n-1帧像素点(i，j)处的灰度值；若没有场景切换，G通常比较小；若发生场景变换，G通常急剧增大；

若G大于检测阈值，则认为场景发生变换，否则，认为场景没有变化，即

λ_sc为检测阈值，其值常为经验值，用于判断是否发生场景变换；检测阈值设为9，即当G>9时认为发生场景变换，否则没有发生场景变换。

4.根据权利要求3所述的一种基于贝叶斯决策的HEVC块划分快速方法；其特征在于步骤3具体的实现过程如下：

设每个CU的观测信息用n维特征向量X＝[x₁，x₂，x₃…x_n]来描述，p(X|ω_R)，R∈{N，P}，是ω_R状态下观察特征向量X的条件概率密度；状态ω_R的后验概率p(ω_R|X)可以由贝叶斯公式求得

$p\left({\omega }_R\right|X)=\frac{p\left(X\right|{\omega }_R)P\left({\omega }_R\right)}{P\left(x\right)},R\in \{N,P\}$

引入损失函数C_RQ，表示率失真优化结果为决策R，错误地归类为决策Q情况下的风险；考虑风险的情况下的贝叶斯规则变为：

R_N(ω_N|X)＝C_NNp(X|ω_N)P(ω_N)+C_PNp(X|ω_P)P(ω_P)

R_P(ω_P|X)＝C_PPp(X|ω_P)P(ω_P)+C_NPp(X|ω_N)P(ω_N)

R_R(X)为条件风险，表示了特征值X被判为ω_R类时损失的均值，C_NP表示假设ω_N为真，即率失真结果为“不划分”时判断假设ω_P成立，即对CU采取“划分”决策时所带来的风险代价；

为了保证期望风险最小，须保证做每一个决策时，都使得条件风险最小，这样的决策被称为最小风险贝叶斯决策，决策的规则如下：若R_N(ω_N|X)<R_P(ω_P|X)，则ω＝ω_N，决策为ω_N，表示对当前CU采取“不划分”的决策；否则对当前CU采取“划分”的决策；

3-1.特征提取和选择

从观测值中提取特征向量J_inter和J_intra，由下式获得：

J_LRD＝SAD+λ_pred×B_pred

J_inter＝argminP∈Inter{J_LRD(P)}

J_intra＝argminP∈Intra{J_LRD(P)}

此处λ_pred是拉格朗日乘数，B_pred对当前预测模式下所有信息；进行编码时所需要的比特数，P表示PU的候选划分；

特征向量X从在线学习阶段的图片中获得，如果训练图片是I帧，特征向量的维度就降到1，X＝J_intra，因为I帧的只能采用帧内预测模式；

3-2.在线学习的概率密度分布函数

根据R_N(ω_N|X)和R_P(ω_P|X)的值来确定是否划分当前待划分CU；由最小风险贝叶斯公式可知，要比较R_R(ω_R|X)的大小，需要先求得p(X|ω_N)P(ω_N)和p(X|ω_P)P(ω_P)的值；

每个划分深度的“划分”或者“不划分”情况下，似然函数都服从二维高斯随机分布，即p(X|ω_R)由两个独立概率的高斯概率密度函数加权和近似表示，因此有：

$\begin{array}{c}p\left(X\right|{\omega }_i,{\theta }_i)=\frac{1}{\sqrt{2{\mathrm{\pi \sigma }}_i}}\exp (-\frac{1}{2{\sigma }_i^2}{\left(X-{\mu }_i\right)}^2)\\ i=1,2\end{array}$

其中i为混合高斯模型中第i个单高斯模型；每个高斯模型的参数为θ_i＝(μ_i，σ_i)，μ_i和σ_i表示类ω_i的特征向量的均值向量和方差，特征向量X的混合概率函数为

$p\left(X\right|\Theta ,P)=\underset{i=1}{\overset{2}{\Sigma }}P\left({\omega }_i\right)p\left(X\right|{\omega }_i,{\theta }_i)$

其中Θ＝(θ₁,θ₂)是混合高斯模型的分布参数集，P＝(p(ω₁),p(ω₂))是对应的高斯模型的先验概率集；混合高斯模型的参数由以K-Means算法初始化的EM算法确定。

说明书

技术领域

本发明属于高清数字视频压缩编解码技术领域，尤其涉及一种基于贝叶斯决策的HEVC(High Efficiency Video Coding，高效视频编码)块划分快速方法。

背景技术

在数字视频应用产业链的快速发展中，面对视频应用不断向高清晰度、高帧率、高压缩率方向发展的趋势，上一代视频压缩标准协议H.264/AVC的局限性不断突显。因此，由国际电信组织(ITU-T)和运动图像专家组(MPEG)联合成立的组织JCT-VC提出了下一代视频编解码标准——H.265/HEVC。其目标是在相同的图像质量前提下，压缩率比H.264/AVC高档次提高一倍。

HEVC在编码原理和基本结构方面没有突破，和H.264/AVC基本一致，即预测加变换的分块编码方式；在编码细节上和H.264/AVC也很接近，包含帧内预测、帧间预测、运动估计与补偿、正交变换、量化、环路滤波、熵编码和重建等编解码模块。但是，和H.264/AVC相比较，HEVC几乎在每一个编码环节上都采取了重要的改进措施，如帧内预测支持35种模式、帧间预测引入Merge模式、变换量化支持高达32×32变换单元、熵编码采用CABAC(Context Adaptive Binary Arithmetic Coder，基于上下文的自适应二进制算术编码)算法、新引入的自适应样点补偿环路滤波等等。

HEVC编码器采用了编码树单元(CTU，Coding Tree Unit)、编码单元(CU，Coding Unit)、预测单元(PU，Prediction Unit)、变换单元(Transform Unit，TU)结构，使得HEVC能够对不同分辨率和应用环境的视频进行编码。HEVC编码时，一幅图像可以被划分为多个互不重叠的CTU，每个CTU划分为一个或者多个CU；在进行帧内或者帧间预测编码时，一个CU可以选择划分为一个或者多个PU；在变换、量化操作时，一个CU可以划分成一个或者多个TU。

CU是HEVC编码的基本单元，采用递归的划分方式。HEVC支持8×8、16×16、32×32、64×64这4种尺寸的CU，对应的划分深度分别为3、2、1、0。

PU是HEVC预测的基本单元，规定了CU的预测模式，所有与预测相关的编码数据都由PU传输的。对于一个尺寸为2N×2N的CU，其帧内PU的可选模式有2种：2N×2N和N×N；帧间PU的可选模式有8种，其中包括4种对称模式：2N×2N、2N×N、N×2N、N×N以及4种非对称模式：2N×nD、2N×nU、nR×2N、nL×2N。当编码时采用Merge时，残差信息是不需要被编码的，此时采用的PU模式为2N×2N skip模式，PU划分模式如图1所示。

TU是HEVC变换和量化的基本单元，其尺寸大小也是灵活变化的，以四叉树形式进行递归分割。当CTU尺寸为64×64时，各个CU中TU的四叉树递归划分如图2所示，其中CU的划分用实线表示，TU的划分用虚线表示，编码顺序用字母编号表示。

与其他的国际编码标准类似，HM编码器对于块尺寸的决策也是基于率失真优化(Rate-Distortion Optimization，RDO)的，在HEVC标准编码算法中，CU的划分流程简述如下：

(1)设置当前CU的深度为零；

(2)计算在当前划分深度下Skip模式的率失真代价(Rate-Distortion Cost，RD Cost)J_skip，并且更新当前最佳的划分模式(BestCuMode＝Skip)和最小的率失真代价(MinRDcost＝J_skip)；

(3)计算在当前划分深度下Merge_2Nx2N模式的率失真代价J_{merge_2Nx2N}，并与之前得出的最小的率失真代价做比较，若J_{merge_2Nx2N}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Merge_2Nx2N)和最小的率失真代价(MinRDcost＝J_{merge_2Nx2N})；

(4)计算在当前划分深度下Inter_2Nx2N模式的率失真代价J_{Inter_2Nx2N}，并与之前得出的最小的率失真代价做比较，若J_{Inter_2Nx2N}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_2Nx2N)和最小的率失真代价(MinRDcost＝J_{Inter_2Nx2N})；

(5)若当前CU的深度是编码器允许的最大划分深度，而且CU的尺寸比8×8大，则求Inter_NxN模式的率失真代价J_{lnter_NxN}，并与之前得出的最小的率失真代价做比较，若J_{lnter_NxN}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_NxN)和最小的率失真代价(MinRDcost＝J_{Inter_NxN})，若不满足上述CU深度和尺寸要求，则跳过步骤5；

(6)计算在当前划分深度下Inter_2NxN模式的率失真代价J_{Inter_2NxN}，并与之前得出的最小的率失真代价做比较，若J_{inter_2NxN}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_2NxN)和最小的率失真代价(MinRDcost＝J_{Inter_2NxN})；

(7)计算在当前划分深度下Inter_Nx2N模式的率失真代价J_{Inter_Nx2N}，若J_{Inter_Nx2N}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_Nx2N)和最小的率失真代价(MinRDcost＝J_{Inter_Nx2N})；

(8)计算当前CU是否需要计算AMP模式的率失真代价，如果BestCuMode＝Inter_2Nx2N或者BestCuMode＝Inter_2NxN，Test_Hor条件为真，否则Test_Hor为假；如果BestCuMode＝Inter_2Nx2N或者BestCuMode＝Inter_Nx2N，Test_Ver条件为真，否则Test_Ver为假。

(9)如果Test_Hor条件为真，继续下一步；否则，跳转到步骤12；

(10)计算在当前划分深度下Inter_2NxnU模式的率失真代价J_{Inter_2NxnU}，若J_{Inter_2NxnU}<M inRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_2NxnU)和最小的率失真代价(MinRDcost＝J_{Inter_2NxnU})；

(11)计算在当前划分深度下Inter_2NxnD模式的率失真代价J_{Inter_2NxnD}，若J_{Inter_2NxnD}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_2NxnD)和最小的率失真代价(MinRDcost＝J_{Inter_2NxnD})；

(12)若Test_Ver条件为真，继续下一步；否则，跳转到步骤15；

(13)计算在当前划分深度下Inter_nLx2N模式的率失真价J_{Inter_nLx2N}，若J_{Inter_nLx2N}＜MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_nLx2N)和最小的率失真代价(MinRDcost＝J_{Inter_nLx2N})；

(14)计算在当前划分深度下Inter_nRx2N模式的率失真代价J_{Inter_nRx2N}，若J_{Inter_nRx2N}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Inter_nRx2N)和最小的率失真代价(MinRDcost＝J_{Inter_nRx2N})；

(15)计算在当前划分深度下Intra_2Nx2N模式的率失真代价J_{Intra_2Nx2N}，若J_{Intra_2Nx2N}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝Intra_2Nx2N)和最小的率失真代价(MinRDcost＝J_{Intra_2Nx2N})；

(16)若CU的当前划分深度为编码设置的所允许的最大深度，计算lntra_NxN其率失真代价J_{lntra_NxN}，若J_{lntra_NxN}<MinRDcost，更新当前最佳的划分模式(BestCuMode＝lntra_NxN)和最小的率失真代价(MinRDcost＝J_{lntra_NxN})；

(17)若CU的当前划分深度比PCM模式允许的最大划分深度要小，计算PCM模式的率失真代价J_PCM，若J_PCM＜MinRDcost，则更新当前最佳的划分模式(BestCuMode＝PCM)和最小的率失真代价(MinRDcost＝J_PCM)；

(18)若BestCuMode为Skip模式或者CU的当前尺寸不大于编码配置中设置的所允许的最小尺寸，跳转到步骤19；否则，当前CU将被划分成四个子块，每个子块的深度比当前块大1。然后对每一个Sub-CU迭代(1)-(18)的算法步骤，分别求出子块的MinRDcost，累加后令为J_sub-CU。

(19)比较划分前和划分成子块后的率失真代价，若MinRDcost<J_Sub-CU，当前划分深度下的CU不继续分割，更新最小的率失真代价(MinCucost＝MinRDcost)；否则当前CU划分为四个Sub-CU，并且更新MinCuCost＝J_Sub-CU。

由上述的CU尺寸决定的算法步骤可知，编码器要决定一个CTU的四叉树划分方式，不仅要确定CU的划分深度，还要遍历某一深度下所有可能的PU、TU划分方，最后从中选择出RD Cost最小的编码模式以及对应的划分深度，因此HEVC块划分过程的计算复杂度极高。

发明内容

本发明针对上述现有技术中存在的技术问题，根据视频序列在时空域的相关性，提出了一种基于贝叶斯决策的HEVC块划分快速方法。在本发明中，将CU划分操作看作二分类问题，即W＝{ω_N，ω_P}，其中ω_N表示当前CU不继续划分，ω_p表示当前CU继续划分，并采用最小风险贝叶斯决策来解决二分类问题。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1、离线学习得到损失函数C_NP和C_PN以及先验概率P(ω_N)和P(ω_P)。

在利用最小错误率的贝叶斯决策准则做决策时，若CU的划分结果决策错误，即贝叶斯决策对当前深度CU是否划分的判断与标准算法的结果不同，就会引起率失真性能下降。同时，对于尺寸和特征值不同的CU，错误的决策结果引起的率失真性能下降的程度也不同。因此，本发明提出将错误决策带来的率失真性能的下降作为贝叶斯风险函数，建立基于最小风险的贝叶斯决策模型，以降低错误决策带来的率失真性能损失，完全率失真代价函数如下式所示：

J_FRD＝(SSE_luma+ω_chroma×SSE_chroma)+λ_mode×B_mode

其中，SSE_luma表示亮度的原始图像块和重建图像块之间的像素差误差平方和；SSE_chroma表示色度信号的原始图像块和重建图像块之间的像素差误差平方和，ω_chroma为色度分量的权重系数，λ_mode是拉格朗日乘数，B_mode是对当前编码模式时所需要的比特数。

对于64×64，32×32，16×16大小的CU，分别通过离线学习训练得到损失矩阵C，损失矩阵定义如下式所示：

此处C_PN和C_NP定义如下：

J_FRD，N和J_FRD，P分别是当前待划分CU不继续划分和继续划分成四个子块对应的完全率失真代价。C_NP表示假设ω_N为真，即率失真结果为“不划分”时判断假设ω_P成立，即对CU采取“划分”决策时所带来的风险代价；C_PN表示假设ω_P为真，对CU采取“不划分”决策时所带来的风险代价。C_NP和C_PN大于等于0，当决策是正确的时候(C_NN或C_PP)，决策的损失值为0。

先验概率P(ω_R)是通过统计当前深度下，作出ω_R决策的CU占所有CU的比重得到的，即

P(ω_R)＝当前深度属于ω_R的CU数/当前深度CU总数；

其中R为N或者P；

步骤2、对于传入的图片序列，判断其是否处于在线学习阶段或者场景是否发生了变化，若当前帧处于在线学习阶段或者是场景变换帧，根据HM标准算法对其进行深度划分，提取并存储每个深度的特征值，跳转到步骤7；否则执行步骤3。

场景变换是为了判断视频图像运动的剧烈程度，当视频序列出现场景变换时，一般来说即表明视频的内容发生了剧烈变动，相邻的视频帧之间将失去时间上的相关性(视频在切换处的时域冗余消失)。在这种情况下，基于贝叶斯决策的块划分快速算法并不适用，因为一旦场景发生变换，判断是否进行划分的阈值就会变化，基于离线统计和在线学习的贝叶斯决策将不能根据提取到的特征值作出正确决策。故本发明提出了基于场景变换检测的在线学习阶段和快速划分阶段交替机制。对于序列前N帧和场景变换后前N帧，都要重新提取特征值建立新的混合高斯模型。

由于图像灰度值在编码当前帧之前就可以通过简单计算得出，若相邻图像处于同一场景，相邻帧相关性较强，灰度值相差不大；反之，发生场景变换时相邻图像帧在相同位置上像素点的灰度值通常相差较大。

2-1.用平均灰度差值来衡量视频运动的剧烈程度，即是否发生场景变换，视频序列中相邻两帧在相同位置上的像素点的平均灰度差值计算如下式所示：

式中，P、Q为图像宽度和高度，G_n(i，j)为第n帧像素点(i，j)处的灰度值，G_n-1(i，j)为第n-1帧像素点(i，j)处的灰度值。若没有场景切换，G通常比较小。若发生场景变换，G通常急剧增大。

综上所述，可以设置一个用于判断是否发生场景变换的检测阈值，若G大于检测阈值λ_sc，则认为场景发生变换，否则，认为场景没有变化；λ_sc为检测阈值，其值常为经验值。阈值的大小决定场景变换的正确率，过大会导致漏检而过小则会导致误检，因此λ_sc取值应合理。本发明将在线学习阶段的帧数设置为6，阈值设为9，即当G>9时认为发生场景变换，否则没有发生场景变换。一旦场景发生变换，就须要重新估计特征向量的统计参数。

步骤3、判断图片是否为快速划分阶段的第一帧图像，若不是，执行步骤4；否则提取在线学习阶段或场景变换帧存储的特征值，并基于特征值建立混合高斯模型，模型的统计参数用以K-Means算法初始化的期望最大化(EM)算法来估计。

设每个CU的观测信息用n维特征向量X＝[x₁，x₂，x₃…x_n]来描述，p(X|ω_R)，R∈{N，P}，是ω_R状态下观察特征向量X的条件概率密度。状态ω_R的后验概率p(ω_R|X)可以由贝叶斯公式求得

为了衡量错误的决策带来的风险，本发明引入损失函数C_RQ，表示率失真优化结果为决策R，错误地归类为决策Q情况下的风险。考虑风险的情况下的贝叶斯规则变为：

R_N(ω_N|X)＝C_NN p(X|ω_N)P(ω_N)+C_PNp(X|ω_P)P(ω_P)

R_P(ω_P|X)＝C_PPp(X|ω_P)P(ω_P)+C_NP p(X|ω_N)P(ω_N)

R_R(X)为条件风险，表示了特征值X被判为ω_R类时损失的均值，C_NP表示假设ω_N为真，即率失真结果为“不划分”时判断假设ω_P成立，即对CU采取“划分”决策时所带来的风险代价。

为了保证期望风险最小，须保证做每一个决策时，都使得条件风险最小，这样的决策被称为最小风险贝叶斯决策，决策的规则如下：若R_N(ω_N|X)<R_P(ω_P|X)，则ω＝ω_N，决策为ω_N，表示对当前CU采取“不划分”的决策；否则对当前CU采取“划分”的决策。

3-1.特征提取和选择

如上所述，需要从观测值中提取特征向量来使得决策合理，为了反映视频的时空特征，我们选取特征向量为J_inter和J_intra，由下式获得：

J_LRD＝SAD+λ_pred×B_pred

J_inter＝argminP∈Inter{J_LRD(P)}

J_intra＝argminP∈Intra{J_LRD(P)}

此处λ_pred是拉格朗日乘数，B_pred对当前预测模式下所有信息(如划分方式、模式信息、变换系数等等)进行编码时所需要的比特数，P表示PU的候选划分。特征值提取的计算复杂度是几乎可以忽略不计的，因为率失真代价的信息可以直接从编码过程中获得。

特征向量X从在线学习阶段的图片中获得，如果训练图片是I帧，特征向量的维度就降到1，X＝J_intra，因为I帧的只能采用帧内预测模式。

3-2.在线学习的概率密度分布函数

为了将贝叶斯决策应用到快速CU划分算法，需要在每次在线学习阶段估计特征向量的统计参数。在提出的方法中，我们根据R_N(ω_N|X)和R_P(ω_P|X)的值来确定是否划分当前待划分CU；由最小风险贝叶斯公式可知，要比较R_R(ω_R|X)的大小，需要先求得p(X|ω_N)P(ω_N)和p(X|ω_P)P(ω_P)的值。

每个划分深度的“划分”或者“不划分”情况下，似然函数都服从二维高斯随机分布，即p(X|ω_R)可以由两个独立概率的高斯概率密度函数加权和近似表示，因此有：

其中i为混合高斯模型中第i个单高斯模型。每个高斯模型的参数为θ_i＝(μ_i，σ_i)，μ_i和σ_i表示类ω_i的特征向量的均值向量和方差，特征向量X的混合概率函数为

其中Θ＝(θ₁,θ₂)是混合高斯模型的分布参数集，P＝(p(ω₁),p(ω₂))是对应的高斯模型的先验概率集。混合高斯模型的参数由以K-Means算法初始化的EM算法确定。

步骤4、提取当前CU的特征值，求得p(X|ω_R)，R∈{N,P}。

提取待划分的CU的特征值X，根据所处深度求得在同深度的混合高斯分布上的函数值，即p(X|ω_N)和p(X|ω_P)。

步骤5、决定是否划分当前CU，若划分，对每一个Sub-CU执行步骤1-步骤5所述过程；否则不划分当前CU，跳到步骤6。

计算比较 和 大小，若 较大，将当前CU划分为四个Sub-CU，并对每一个Sub-CU执行步骤1-5；否则，不划分当前CU。

步骤6、对该CU进行编码，若当前帧图像CU已经划分完成，执行步骤7；否则，对下一个CU执行步骤1-6所述过程。

根据基于贝叶斯的块划分快速算法编码当前CU，再对下一个CU遍历步骤1-6。若当前图像帧内所有的CU都已经完成划分，则执行步骤7。步骤7、对下一帧图像执行2-7步骤所述过程，直至编码完所有的视频帧。

对于新传入的一帧图像，同样用基于贝叶斯的块划分快速算法处理，直至编码完所有的视频帧。

至此，整个基于贝叶斯决策的HEVC块划分快速方法结束，针对某一深度CU的划分。

有益效果

本方法优点如下：

(1)本发明通过贝叶斯决策来对当前深度CU的划分方式做快速决策，降低了CU划分算法复杂度，能大幅度减少HEVC编码时间。

(2)本发明采用了基于平均灰度差值的场景变换检测机制，确保了方法的稳定性和准确性。

(3)采用本发明的实验结果表明，与HM13.0原有算法相比，本发明公布方法减少了44.5％的编码时间，而编码比特率BD-Rate仅增加0.94％。

附图说明

图1：H.265/HEVC PU的划分模式。

图2：CU、TU的四叉树划分。

图3：在线学习阶段和快速划分阶段交替示意图。

图4：基于贝叶斯决策的HEVC块划分快速算法总流程。

具体实施方式

以People on street等16个序列的块划分过程为例，对提出的发明方法进行详细说明。

基于贝叶斯决策的HEVC块划分快速算法的步骤如下：

步骤1、离线学习得到损失函数C_NP和C_PN以及先验概率P(ω_N)和P(ω_P)。

根据以下公式分别对64×64，32×32，16×16大小的CU通过离线学习训练得到损失矩阵C以及先验概率：

J_FRD＝(SSE_luma+ω_chroma×SSE_chroma)+λ_mode×B_mode

其中，SSE_luma，SSE_chroma表示亮度和色度信号的原始图像块和重建图像块之间的像素差误差平方和，ω_chroma为色度分量的权重系数，λ_mode是拉格朗日乘数，B_mode是对当前编码模式时所需要的比特数。J_FRD，N和J_FRD，P分别是当前待划分CU不继续划分和继续划分成四个子块对应的完全率失真代价。

先验概率P(ω_R)是通过统计当前深度下，作出ω_R决策的CU占所有CU的比重得到的，即

P(ω_R)＝当前深度属于ω_R的CU数/当前深度CU总数

步骤2、对于传入的图片序列，判断其是否处于在线学习阶段或者是否场景发生了变化，若当前帧处于在线学习阶段或者是场景变换帧，根据HM标准算法对其进行深度划分，提取并存储每个深度的特征值，跳转到步骤7；否则执行步骤3。

利用视频序列中相邻两帧在相同位置上的像素点的平均灰度差值衡量视频运动剧烈程度，计算如下式所示：

式中，P、Q为图像宽度和高度，G_n(i，j)为第n帧像素点(i，j)处的灰度值，G_n-1(i，j)为第n-1帧像素点(i，j)处的灰度值。若没有场景切换，G通常比较小。若发生场景变换，G通常急剧增大。一旦场景发生变换，就须要重新估计特征向量的统计参数。依据下式判断视频帧是否发生场景变化：

场景变换是为了判断视频图像运动的剧烈程度，当视频序列出现场景变换时，一般来说即表明视频的内容发生了剧烈变动，相邻的视频帧之间将失去时间上的相关性(视频在切换处的时域冗余消失)。在这种情况下，基于贝叶斯决策的块划分快速算法并不适用，因为一旦场景发生变换，判断是否进行划分的阈值就会变化，基于离线统计和在线学习的贝叶斯决策将不能根据提取到的特征值作出正确决策。故本发明提出了基于场景变换检测的在线学习阶段和快速划分阶段交替机制。示意图如图3所示。对于序列前N帧和场景变换后前N帧，都要重新提取特征值建立新的混合高斯模型。

步骤3、判断图片是否为快速划分阶段的第一帧图像，若不是，执行步骤4；否则提取在线学习阶段或场景编码帧存储的特征值，基于这些数据建立混合高斯模型，模型的统计参数用以K-Means算法初始化的EM算法来估计。

假设每个CU的观测信息用n维特征向量X＝[x₁，x₂，x₃…x_n]来描述，我们选取特征向量为J_inter和J_intra，由下式获得：

J_LRD＝SAD+λ_pred×B_pred

J_inter＝argminP∈Inter{J_LRD(P)}

J_intra＝argminP∈Intra{J_LRD(P)}

此处λ_pred是拉格朗日乘数，B_pred对当前预测模式下所有信息(如划分方式、模式信息、变换系数等等)进行编码时所需要的比特数，P表示PU的候选划分。

特征向量X从在线学习阶段的图片中获得，如果训练图片是I帧，特征向量的维度就降到1，X＝J_intra，因为I帧的只能采用帧内预测模式。

每个划分深度的“划分”或者“不划分”情况下，似然函数都服从二维高斯随机分布，即p(X|ω_R)可以由两个独立概率的高斯概率密度函数加权和近似表示，因此有：

其中i为混合高斯模型中第i个单高斯模型。每个高斯模型的参数为θ_i＝(μ_i，σ_i)，μ_i和σ_i表示类ω_i的特征向量的均值向量和方差，特征向量X的混合概率函数为

其中Θ＝(θ₁,θ₂)是混合高斯模型的分布参数集，P＝(p(ω₁),p(ω₂))是对应的高斯模型的先验概率集。

为了得到混合高斯模型的参数，定义对数似然函数为

其中m表示特征向量的维度。参数求解即需要求出模型参数(Θ₀，P₀)使得公式对数似然函数值最大，则混合模型的统计参数估计应该满足下式：

本发明用EM算法对混合高斯模型的统计参数进行估计。采用EM算法将求解分成两个步骤：首先假设高斯模型的参数是已知的，利用参数去估计每个高斯模型的权值；第二步，得到权值之后，再利用高斯模型的权值去估计其参数。

首先假设CU块的特征值的混合高斯模型参数的初始值为Θ⁽⁰⁾，先验概率初始值为P⁽⁰⁾，然后设第t步的混合高斯模型参数估计值为Θ^(t)和P^(t)，则第t+1步的计算过程如下：

(1)E步骤(计算期望)：根据当前的混合高斯模型参数第t步迭代的估计值Θ^(t)和P^(t)，计算出在已知当前特征值时，CU的决策属于ω_i的后验概率的估计值：

显然，如果特征值x_m(m＝1,2)的第ω_i类的P(ω_i|x_m,θ_i)≥P(ω_i|x_m,θ_j)，j≠i，则x_m属于第ω_i类的可能性就非常大。

(2)M步骤(最大化期望)：获得每个数据样本属于每个子类的后验概率，这一步利用梯度下降法求解式混合模型的统计参数估计公式。从而得到Θ，P在第k+1步的估计。将对数似然函数分别对Θ和P求导，并带入上式所计算的后验概率，整理后可得：

其中的 表示第k+1步迭代时属于第i类的特征值的概率数目。EM算法通过不断重复迭代E步骤与M步骤改进模型的参数，直至收敛即可得到混合高斯模型的参数。本发明中EM算法的初始值是有K-Means算法确定的，并且采用欧几里得距离为相异度的度量算法，其公式如下：

其中A＝{a₁,a₂,…,a_n}，B＝{a₁,a₂,…,a_n}是两个数据元素项，各自具有n个可度量特征属性。

K-Means算法首先从样本中任意选取k个对象作为初始聚类的中心。接着根据样本与聚类中心之间的相异度判断每一个样本属于哪个簇。然后更新各个簇的聚类中心，重复迭代上述过程，直至准则函数收敛，具体步骤如下所示：

首先随机选取k个簇的初始聚类中心点为 接着重复下面过程直到收敛：

(1)计算每一个条件概率p(X|ω_i)所属的类：

(2)于每一个类j，重新计算该类的质心：

k是聚类的数目，需要在聚类前指定。c⁽ⁱ⁾代表条件概率p(X|ω_i)与k个类中距离最近的那个类，c⁽ⁱ⁾∈{1,2,3,…,k}。质心μ_j表示第j个类的聚类中心位置，重复迭代步骤(1)和步骤(2)直至聚类中心不再变化或者变化很小，在本发明中，取k＝2。

步骤4、提取当前CU的特征值，求得p(X|ω_R)，R∈{N,P}。

提取待划分的CU的特征值X，根据所处深度求得在同深度的混合高斯分布上的函数值，即p(X|ω_N)和p(X|ω_P)。

步骤5、决定是否划分当前CU，若划分，对每一个Sub-CU执行步骤1-5所述过程；否则不划分当前CU，跳到步骤6。

计算比较 和 大小，若 较大，将当前CU划分为四个Sub-CU，并对每一个Sub-CU执行步骤1-5；否则，不划分当前CU。

步骤6、对该CU进行编码，若当前帧图像CU已经划分完成，执行步骤7；否则，对下一个CU执行步骤1-6所述过程。

根据基于贝叶斯的块划分快速算法编码当前CU，再对下一个CU遍历步骤1-6。若当前图像帧内所有的CU都已经完成划分，则执行步骤7。

步骤7、对下一帧图像执行2-7步骤所述过程，直至编码完所有的视频帧。

对于新传入的一帧图像，同样用基于贝叶斯的块划分快速算法处理，直至编码完所有的视频帧。

至此，整个基于贝叶斯决策的HEVC块划分快速方法结束，针对某一深度CU的划分，算法流程图如图4所示。

本发明实验测试环境使用HEVC标准参考代码HM13.0在windows 7系统VS2010编译运行，对16个测试序列进行统计和测试。以全I帧(All Intra,AI)、随机存取(Random Access,RA)、低延迟-P帧(LP)、低延迟-B帧(LB)为编码环境，设置22、27、32、37作为QP值，利用亮度的Bjontegaard-Delta比特率(YBD-rate)将提出的块划分快速算法与HEVC标准块划分算法进行对比，并统计编解码时间，结果如表1所示。

由表1可知本发明提出的算法相较于HM13.0标准算法在AI的配置下平均节省46％以上的编码时间，而BD-Rate只损失了1.08％；RA配置下平均节省了45.9％的编码时间，BD-Rate损失1.12％；LB配置下的编码时间减少了42.8％，而BD-Rate只损失了0.83％；LP配置下平均节省了42.8％的编码时间，BD-Rate损失了0.73％，编码性能下降地微乎其微。

表1基于贝叶斯决策的块划分快速算法与HEVC标准算法效果对比结果

当然，本技术领域中的普通技术人员应当认识到，以上实施例仅是用来说明本发明的，而并非作为对本发明的限定，只要在本发明的范围内，对以上实施例的变化、变型都将落入本发明的保护范围。

一种基于贝叶斯决策的HEVC块划分快速方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。