基于霍夫变换的HEVC标准中帧内预测模式快速确定方法

技术领域

本发明涉及到视频编码领域中目前国际上最新的压缩标准HEVC中加快其运行速度的方法，尤其涉及一种采用霍夫(Hough)变换等技术加快其帧内编码块的最优编码模式的确定的方法。

背景技术

HEVC(High Efficiency Video Coding)是目前最新的国际视频编码标准。它是由ISO/IEC移动图像专家组(MPEG)和ITU-T视频编码专家组(VCEG)联合制定的。它是继H.264/AVC之后的高性能视频编码标准。它的编码效率比H.264提高了50％以上。HEVC仍然采用预测加变换的混合编码框架，该框架中的技术较之前的技术比较来看，虽然大致的编码框架内容及流程并没有过多的改变，但是为了提高视频编码效率，HEVC标准中也加入了许多新的技术。

在H.264视频编码标准中，宏块(Micro Block，MB)是编码的最基本的单元。但在HEVC编码标准中，由于高清视频的普及，对达到2K、4K的超清视频，如果再采用这样固定大小的编码块的话，很难适应高清视频的需求。因此，HEVC没有继续采用MB的概念，而是采用更加灵活方式进行块结构表示：编码单元(CUcoding unit)、预测单元(PU prediction unit)、变换单元(TU transform unit)。CU是最基本的分割单元，其最大编码尺寸是64×64，最小编码尺寸是8×8。PU是一个携带与预测过程相关信息的基本单元，PU尺寸小于或等于CU尺寸。一个CU可以包含一个或多个不同尺寸的预测单元PU，一个PU包含若干变换单元TU，TU是一个基于变换以及量化的基本单元。HEVC采用四叉树结构进行编码单元的划分。

HEVC为了克服了H.264/AVC中预测模式个数少、预测精度不高、不准确等缺点，HEVC大大增加了可采用的预测模式的数量。HEVC帧内预测共有35种预测模式，其中模式0表示使用平面(Planar)方式预测，模式1表示使用直流(DC)方式预测，模式2至34表示使用各种角度进行预测。

在HEVC的参考模型HM4.0中帧内模式的决策过程分为三个阶段。首先，对适合不同尺寸PU的模式集进行粗选，计算所有可能预测模式的率失真代价(Rate-Distortion Cost，Rd-Cost)，并将其按照代价递增顺序排列，Rd-Cost值最小的一组预测模式即是粗选子集，这个过程叫做粗选模式确定(RMD)过程。这里，计算失真时，仅考虑预测残差的失真，而不是编解码后的失真。其次，验证当前块左侧和上侧参考块的帧内预测模式是否包含在粗选子集中，若不在，则将其加入子集。最后，对粗选子集中的预测模式进行率失真优化，代价最小的模式即为最优预测模式，这个过程叫做码率和失真度优化(RDO)过程。这里，RDO过程中需要计算每个候选模式的编解码之后的失真，因此其计算量很大。由于HEVC中具有很多可选的帧内预测的模式，其帧内模式的确定过程具有很大的计算复杂度，非常耗时。

综上所述，随着HEVC中帧内可选预测模式数量上的增加，虽然提高了预测精度和编码效率，但同时也大大增加了HEVC的编码复杂度。因而，帧内最优预测模式的确定时间被大大地增加了。

本发明力求在保持预测精度的基础上，减少HEVC中帧内预测模式的确定时间。由于图像块中的直线的边缘信息能给我们带来块中像素的走势的方向，本发明将利用这一启发式信息来简化和进一步地减少候选的帧内预测模式。

发明内容

有鉴于现有技术的上述缺陷，本发明提出了一种基于Hough变换的快速帧内模式的确定的新方法。为实现在减少计算量的同时尽可能地保持预测的精度的目的，本发明将首先对图像进行边缘检测，然后采用Hough变换搜寻为直线的边缘，接下来确定当前图像预测单元PU内的直线边缘的角度，利用统计直方图确定当前PU最有可能的预测方向，并根据此方向确定最有可能的候选的预测模式，以在粗选模式确定(RMD)过程RMD和码率和失真度优化(RDO)过程中减少要检测的候选模式，大大地减少计算量，并同时对当前PU尽可能地选择好的预测模式。其特征在于，对于视频图像中的每个帧内预测单元PU，所述方法包括：

步骤一，对当前PU，判断其尺寸是否为4×4。如是，则进行步长为1的模式亚采样，并直接跳到步骤八。否则，利用Canny算子对当前PU进行运算。

步骤二，根据Canny算子的运算的结果，用形态学的方法对边缘进行细化。

步骤三，选择合适的阈值进行PU中边缘点的提取和连接。

步骤四，对当前PU，利用Hough变换检测直线边缘像素点，即，保留处于某一直线上的边缘点，去除处于曲线上的边缘点。

步骤五，对各直线边缘，确定其与水平方向上的角度差θ，和其正切值tanθ。

步骤六，根据各帧内预测模式的预测角度的正切值的范围，和检测出的当前PU中各直线边缘的正切值，用统计直方图确定当前PU中落在每一个范围内的直线边缘像素点之和。

步骤七，根据此统计直方图，确定直方图中的直线边缘像素之和最大的几个预测模式。

步骤八，根据当前PU的尺寸，和得到的统计直方图，确定进入模式粗选过程RMD的候选的帧内模式。

步骤九，根据RMD过程，和当前PU的尺寸，确定进入模式精选过程RDO的候选的帧内模式。

步骤十，根据RDO的结果，确定当前PU的优化的帧内预测模式。

进一步地，所述步骤一中，对4×4的块进行模式亚采样。在HEVC参考模型HM4.0中对于4×4PU适合的帧内预测模式共19种，方向性预测模式分别为：7、14、6、13、1、12、5、11、4、15、8、16、2、17、9、18、10。对4×4的块进行模式亚采样只保留一半的模式，即选择模式7、6、1、5、4、8、2、9、10。

Canny算子边缘检测步骤如下：首先应用高斯滤波器平滑图像，在3×3邻域内求有限差分均值计算灰度梯度的幅值和方向。

进一步地，在所述步骤二中，采用形态学的方法对检测出的宽度粗的边缘进行细化，即，进行形态学的腐蚀运算，其腐蚀的模板元素为

$>\left(\begin{array}{ccc}0& 1& 0\\ 1& 1& 1\\ 0& 1& 0\end{array}\right)$>

进一步地，所述步骤三中，采用阈值T_h进行边缘点提取。采用迭代法选取最佳阈值。迭代法实现步骤如下：

求出图像当前PU中最小值Z_min、最大值Z_max，则初始阀值T₀=(Z_min+Z_max)/2。

根据阀值T_k(k为迭代次数)将图像分割成边缘区域和非边缘区域，计算两部分的平均值Z_O、Z_B，即

$>Z_O=\underset{i=0}{\overset{T_k}{\Sigma }}{h}_i·i/\underset{i=0}{\overset{T_k}{\Sigma }}{h}_i$>

$>Z_B=\underset{j=T_k+1}{\overset{255}{\Sigma }}{h}_j·j/\underset{j=T_k+1}{\overset{255}{\Sigma }}{h}_j$>

这里，h_i和h_j分别表示边缘和非边缘区域的像素点的值。计算出Z_O、Z_B后，用式子

T_k+1=(Z_O+Z_B)/2

来计算出新阀值T_K+1。

若T_k+1=T_K，即T_k为所求阈值，则算法到此结束，否则转到步骤(2)。迭代计算直至收敛于某个稳定的阈值，此阈值即为最终结果T_h。

这里，采用双阈值方法从候选边缘点中检测和连接最终边缘。在边缘点的提取时，所采用的阈值为T_h，边缘点的连接时采用的阈值应当比T_h小，以连接边缘。本发明中在边缘点的连接时采用的阈值为T_h/2。即，经第一和第二步处理后，值大于T_h的像素点为边缘点。然后以这些边缘点为种子，寻找与其相邻的值大于T_h/2的像素点，加为边缘像素点。然后，重复这一过程，直到PU中所有的像素点都扫描过一遍。

表18×8、16×16、32×32尺寸PU的各个预测模式的预测角度、边界角度范围和正切范围

表2 64×64尺寸PU的各个预测模式的预测角度、边界角度范围和正切范围

进一步地，在步骤六中，对直线边缘角度的正切值的统计范围如表1和表2所示。例如，如表1所示，对于候选模式7，其角度正切值的统计范围为(-0.7417，-1.1033]。即，初始的此范围内的直线像素点值置0，C₇=0，然后如果有直线边缘的角度的正切值落在此范围，则C₇=C₇+a_i，其中a_i是此条直线上在当前PU中的所有像素点数。对所有的候选模式都进行此处理，则得到了所要的各模式的统计直方图。因为模式0、模式3是非方向性预测模式，故未被统计在表1、表2中，它们都被作为候选模式进入到RDO的粗选。

表3HM4.0各PU尺寸中进入到RMD粗选过程的候选的预测模式的个数

表4本发明各PU尺寸中进入到RMD粗选过程的候选的预测模式的个数

进一步地，步骤八的过程如表4所示。例如，对于16×16尺寸的PU，将选择5个在以上统计直方图中值最大的候选模式。从表3和表4的对比中，可以看出本发明大大减少了进入到RMD粗选过程的候选的模式的数目。这样，可以大大地减少计算量，加速HEVC标准的运行速度。

表5HM4.0各PU尺寸中进入到RDO精选过程的候选的预测模式的个数

表6本发明各PU尺寸中进入到RDO精选过程的候选的预测模式的个数

进一步地，步骤九的过程如表6所示。例如，对于16×16尺寸的PU，将选择在RMD过程中最优的3个候选模式进入到最终的RDO的选择过程中。从表5和表6的对比中，可以看出本发明大大减少了进入到RDO精选过程的候选的模式的数目。这样，可以大大地减少计算量，加速HEVC标准的运行速度。

综上所述，本发明提出了一种国际上目前最新编码标准HEVC中的帧内预测的新方法，以提高其运行速度。该方法的创新点在于：利用Canny算子进行边缘检测，并利用Hough变换进行直线边缘检测，以根据这些启发式信息，提取出当前预测单元最可能的边缘走向。然后，根据这些边缘走向来选择和减少需要检测的候选的预测模式。以此，来大大减少HEVC的编码的计算复杂度，提高其运行速度。

以下将结合附图对本发明的构思、具体结构及产生的技术效果作进一步说明，以充分地了解本发明的目的、特征和效果。

附图说明

图1是HEVC标准中的帧内预测模式的示意图；

图2是本发明所提出的新方法的流程图；

图3是本发明所提出的方法和原有方法(HM4.0)对视频测试序列Party Scene(832×480p分辨率)的码率和失真度性能曲线比较图；

图4是本发明所提出的方法和原有方法(HM4.0)对视频测试序列Slide Editing(720p分辨率)的码率和失真度性能曲线比较图，

图5是本发明所提出的方法和原有方法(HM4.0)对视频测试序列Kimonol(1080p分辨率)的码率和失真度性能曲线比较图；

图6是本发明所提出的方法和原有方法(HM4.0)对视频测试序列SteamLocomotiveTrain(4k×2k分辨率)的码率和失真度性能曲线比较图；

具体实施方式

下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

从附图1中可以看出原有的HEVC的帧内预测具有很多候选模式，确定较优化的模式具有较大的计算复杂度。

本发明利用C++语言在HEVC的HM4.0的程序的基础上，利用OpenCV函数库，对所提出的方法进行了实现和实验。

如附图2所示，本发明的降低其帧内预测的计算复杂度的方法包括如下步骤：

步骤一，对当前PU，判断其尺寸是否为4×4。如是，则进行步长为1的模式亚采样，并直接跳到步骤八。否则，利用Canny算子对当前PU进行运算。对于4×4大小的PU，因为其尺寸太小，从中提取出的直线边缘方向和预测模式的方向的相关性不是特别大，因此直接跳到步骤八。对于尺寸大于4×4大小的PU，从中提取出的直线边缘方向和预测模式的方向的相关性是很大的，因此可以用来确定要检测的候选模式。在OpenCV中通过函数cvCanny访问Canny算子进行边缘检测，其函数调用原型为void cvCanny(const CvArr*image，CvArr*edges，doublethreshold1，double threshold2，int aperture_size=3)。函数cvCanny采用Canny算法搜索输入图像的边缘而且输出图像中标识的这些边缘。

步骤二，根据Canny算子的运算的结果，用形态学的方法对边缘进行细化。即用如下

$>\left(\begin{array}{ccc}0& 1& 0\\ 1& 1& 1\\ 0& 1& 0\end{array}\right)$>

模板元素对宽度大于3的边缘进行形态学中的腐蚀操作。

步骤三，选择合适的阈值进行PU中边缘点的提取和连接。这里，采用阈值T_h进行边缘点的提取，并用迭代法选取最佳阈值。迭代法的实现步骤如下：

求出图像当前PU中最小值Z_min、最大值Z_max，则初始阀值T₀=(Z_min+Z_max)/2。

根据阀值T_k(k为迭代次数)将图像分割成边缘区域和非边缘区域，计算两部分的平均值Z_O、Z_B，即

$>Z_O=\underset{i=0}{\overset{T_k}{\Sigma }}{h}_i·i/\underset{i=0}{\overset{T_k}{\Sigma }}{h}_i$>

$>Z_B=\underset{j=T_k+1}{\overset{255}{\Sigma }}{h}_j·j/\underset{j=T_k+1}{\overset{255}{\Sigma }}{h}_j$>

这里，h_i和h_j分别表示边缘和非边缘区域的像素点的值。计算出Z_O、Z_B后，用式子

T_k+1=(Z_O+Z_B)/2

来计算出新阀值T_K+1。

若T_k+1=T_K，即T_k为所求阈值，则算法到此结束，否则转到步骤(2)。迭代计算直至收敛于某个稳定的阈值，此阈值即为最终结果T_h。

这里，采用双阈值方法从候选边缘点中检测和连接最终边缘。在边缘点的提取时，所采用的阈值为T_h，边缘点的连接时采用的阈值应当比T_h小，以连接边缘。本发明中在边缘点的连接时采用的阈值为T_h/2。即，经第一和第二步处理后，值大于T_h的像素点为边缘点。然后以这些边缘点为种子，寻找与其相邻的值大于T_h/2的像素点，加为边缘像素点。然后，重复这一过程，直到PU中所有的像素点都扫描过一遍。

步骤四，对当前PU，利用Hough变换检测直线边缘像素点，即，保留处于某一直线上的边缘点，去除处于曲线上的边缘点。OpenCV中通过函数cvHoughLines2进行直线段的检测。cvHoughLines2的函数调用原型是CvSeq*cvHoughLines2(CvArr*image，void*line storage，int method，double rho，double theta，int threshold，doubleparam1，double param2)。本发明将参数method设置成CV_HOUGH_PROBABILISTIC表示选择概率霍夫变换，进行直线段的检测。threshold为阈值参数，如果相应累计值大于它，函数会返回这个线段。param1表示最小线段长度，param2表示在同一条直线上进行线段连接的最大间隔值。

步骤五，对各直线边缘，确定其与水平方向上的角度差θ，和其正切值tanθ。

步骤六，根据各帧内预测模式的预测角度的正切值的范围，和检测出的当前PU中各直线边缘的正切值，用统计直方图确定当前PU中落在每一个范围内的直线边缘像素点之和。对直线边缘角度的正切值的统计范围如表1和表2所示。例如，如表1所示，对于候选模式7，其角度正切值的统计范围为(-0.7417，-1.1033]。即，初始的此范围内的直线像素点值置0，C₇=0，然后如果有直线边缘的角度的正切值落在此范围(-0.7417，-1.1033]中，则C₇=C₇+a_i，其中a_i是此条直线上在当前PU中的所有像素点数。对所有的候选模式都进行此处理，则得到了所要的各模式的统计直方图。因为模式0、模式3是非方向性预测模式，故未被统计在表1、表2中，它们都固定作为候选模式进入到RDO的粗选。

步骤七，根据此统计直方图，确定直方图中的直线边缘像素之和最大的几个预测模式。

步骤八，根据当前PU的尺寸，和得到的统计直方图，确定进入模式粗选过程RMD的候选的帧内模式。进一步地，对某一尺寸的PU，其选择的进入RDO检测的候选的预测模式的数目如表6所示。例如，对于16×16尺寸的PU，将选择5个在以上统计直方图中值最大的候选模式。从表3和表4的对比中，可以看出本发明大大减少了进入到RMD粗选过程的候选的模式的数目。这样，可以大大地减少计算量，加速HEVC标准的运行速度。

步骤九，根据RMD过程，和当前PU的尺寸，确定进入模式精选过程RDO的候选的帧内模式。进一步地，对某一尺寸的PU，其选择的进入RDO检测的候选的预测模式的数目如表6所示。例如，对于16×16尺寸的PU，将选择在RMD过程中最优的3个候选模式进入到最终的RDO的选择过程中。从表5和表6的对比中，可以看出本发明大大减少了进入到RDO粗选过程的候选的模式的数目。这样，可以大大地减少计算量，加速HEVC标准的运行速度。

步骤十，根据RDO的结果，确定当前PU的优化的帧内预测模式。

本发明按照通用的测试环境，对所提出的方法进行了测试。编码格式为全I帧结构，测试QP点为37、32、27、22，使用自适应二进制算术编码CABAC(Context-based Adaptive Binary Arithmetic Coding)对视频序列进行熵编码。考虑到HEVC未来会广泛应用到高分辨率视频序列中，测试主要以高清和标清测试序列为主，主要有25601×600p、1920×1080p、1280×720p和832×480p，共4种尺寸的视频测试序列。这里主要从所提出的新方法带来的编码时间的减少及所付出的相应代价来考虑该方法的性能。性能指标主要由BD-PSNR/Rate、ΔB、ΔP及ΔT等参数来具体地表达所提出方法的性能。

表7本发明所提出的方法的实验测试结果

实验结果如表7所示，所有数据结果中若为正数，则表示此指标下本发明的方法相对于原方法其数值是增长的，若为负数，则表示此指标下，本发明的方法相对于原方法其数值是降低的。测试性能的指标的定义如下：

(1)节省的编码时间ΔT，即

$>\mathrm{\Delta T}=\frac{T_{\mathrm{proposed}}-T_{\mathrm{HM}4.0}}{T_{\mathrm{HM}4.0}}$>

其中，T_HM4.0表示使用HM4.0现有算法的编码时间，T_Proposed是文中所提算法的编码时间。获得同等编码效率条件下ΔT越大，表示编码端计算复杂度降低越多，所提出的方法的性能越好。

(2)所提出的方法与HM4.0帧内预测算法码率差值ΔB，即

$>\mathrm{\Delta B}=\frac{B_{\mathrm{Proposed}}-B_{\mathrm{HM}4.0}}{B_{\mathrm{HM}4.0}}$>

其中，B_HM4.0表示现有HM4.0方法的编码码率，B_Proposed是本发明所提出方法的编码码率。ΔB越小，表示提出的方法与HM4.0现有方法的编码性能越接近。

(3)所提出的方法与HM4.0帧内预测方法亮度分量的峰值信噪比(PeakSignal to Noise Ratio，PSNR)的差值ΔP，即

ΔP=P_Proposed-P_HM4.0

其中，P_HM4.0表示HM4.0现有方法的亮度分量的峰值信噪比PSNR，P_Proposed是本发明所提出方法的亮度分量的PSNR。ΔP越小，表示提出的方法与HM4.0现有方法的编码性能越接近。

BD-Rate表示同样峰值信噪比(PSNR)下，码率的增加值。BD-PSNR表示同样码率下，PSNR的减少值。

从实验结果表7中能够看出，所提出的方法只有极小的峰值信噪比(PSNR)的降低及极小的码率增加，因此其具有较好的性能。同时，由此表可以看出，本发明所提出的方法相对于HM4.0里的标准方法可节省最小16.15％、最大可达到32.73％的编码时间。

由实验结果得到的对所提出方法和原方法(HM4.0)对不同分辨率下的视频测试序列的码率和失真度(Rate-Distortion)的曲线如图3、4、5、6所示。这些图的横坐标为码率，单位为每秒需传输的千个比特数(kbps)。这些图的纵坐标为峰值信噪比(PSNR)，单位为dB。从这些图中，可以看出本发明所提出的方法和原方法的码率和失真度的两条曲线基本上相同。由此，可以说明所提出的方法保持了预测模式的精度，在相同的码率的条件下，没有恶化或比较大地降低失真度。

从表7和图3、4、5、6中，可以看出，所提出的方法相对于原有的方法，可平均节省23％的编码时间。同时，其码率和PSNR的波动较小，相对于节省的计算代价而言，性能上的降低几乎可以忽略。可见，本发明所提出的方法具有较好的性能。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。