音视频之H.265/HEVC变换编码

H.265/HEVC系列文章：

1、音视频之H.265/HEVC编码框架及编码视频格式

2、音视频之H.265码流分析及解析

3、音视频之H.265/HEVC预测编码

4、音视频之H.265/HEVC变换编码

一、离散余弦变换：

DCT原理及特点：

一维DCT解析例子：

二维DCT：

DCT基图像：

图像DCT变换：

整数DCT的推导：

H.265/HEVC中的整数DCT：

二、离散正弦变换：

DST原理：

H.265/HEVC中的整数DST：

三、变换结构：

变换单元（TU）:

一、离散余弦变换：

DCT原理及特点：

傅里叶变换表明，任何信号都能表示为多个不同振幅和频率的正弦波或余弦波信号的叠加。如果采用的是余弦函数，则信号分解过程成为余弦变换(Cosine Transform);若输入信号是离散的，则称之为离散余弦变换(Discrete Cosine Transform,DCT)。

数学上共存在8种类型的 DCT其一维形式如下所示：

在以上8类DCT中，前4类对应于偶数阶的实偶DFT，后4类对应于奇数阶的实偶 DFT,且在实际应用中,后4类使用较少。在前4类DCT中，I类DCT应用最为广泛，尤其是在图像、音视频编码等多媒体信号处理领域，其逆变换对应于Ш类DCT。为了便于叙述，下文中的DCT均指Ⅱ类 DCT。

DCT 提供了一种在频域中处理和分析信号的方法。由DCT定义可知，当k=0时，不论n取何值，式中所有余弦项都为cos0，即为1，因此 X(0)正比于信号 x(n)的平均值，称之为信号的“直流”(Direct CurrentDC)分量。当k>0时，X(k)反映了信号x(n)在不同频率上的变化情况称之为信号的“交流”(Altermate Current，AC)分量。随着k的增大，余弦函数值的变化越来越快，所表示的频率也越来越高。此外，需要注意的是，DCT系数有可能取负值。例如，对于DC系数，当x(n)平均值小于零时，就会取负值;对于AC系数，若x(n)和某一基函数频率相同，但相位上相差半个周期时，该系数为负值。

一维DCT解析例子：

Ⅱ类 DCT解析，下面给定两个一维8点序列x1(n)和x2(n)，分别对二者做I类DCT(结果保留整数)。

当K = 0时：

当K = 1时：

序列x(n)的 DCT 结果为：

同(1)的计算过程，可得序列x(n)的DCT 结果:

从以上两个序列DCT结果可以看出，序列x1(n)各元素幅值差异较大,相邻元素间相关性较弱,其DCT结果能量分布较为分散。而序列x2(n)各元素幅值差异极小，相邻元素间相关性较强，其DCT结果大部分能量集中于DC系数上，AC系数幅值非常小。需要指出的是，序列x2(n)与图像、视频信源特征较为相似，因此采用DCT可以使信号能量集中于少数几个系数中，便于进行信源压缩，如量化、熵编码等。

二维DCT：

图像、视频编码主要使用二维DCT。

DCT基图像：

图5.1给出了二维8x8DCT基图像，其中左上角小图像表示水平和垂直空间频率均为零时的基图像，在任一方向上都没有灰度值的变化;

其余小图像分别对应于不同水平和垂直空间频率的基图像，如基图像右下角小图像对应于最高的水平和垂直频率，这里像素灰度在水平和垂直方向发生连续变化;又如基图像右上角小图像对应于最高水平频率和零垂直频率，而左下角则对应于最高垂直频率和零水平频率。简而言之，离散余弦变换可以解释为:将任一8x8像素块表示为图5.1所示的64个基图像的加权和，其权值即为对应位置的 DCT系数。

由之前例5-1中的分析可知，对于灰度值缓慢变化的像素块来说，经过 DCT 后绝大部分能量都集中在左上角的低频系数中;相反，如果像素块包含较多细节纹理信息，则较多能量分散在高频区域。实际上，大多数图像包含更多的低频分量，并且可以利用人眼对图像高频细节相对不敏感的特性，对高能量的低频系数进行较为精细的量化和处理，而对低能量的高频系数进行粗略的量化或掩盖。这样可以较好地压缩图像，而不会造成明显的主观质量下降。

图像DCT变换：

图5.2为图像Lena(512x512)，分别对该图像做 2x2、4x4、8x8和16x16DCT，并计算原始图像与不同变换尺寸所得DCT系数熵的比值，此处像素与 DCT系数都作为独立同分布信源:

原始图像熵为：

同理可得：

其比值(Ratio)分别为1.9325、2.7630、3.3581和3.4325，如图5.3所示。

图5.3给出了DCT去相关性能与变换大小的关系。从图中可以看出随着变换尺寸的增大，DCT去相关性能越来越好，但提升幅度逐渐变缓。考虑到 DCT的计算复杂度会随着变换尺寸的增大而大幅提高，综合考虑性能与复杂度,许多较早的图像与视频编码标准(如JPEG、H.261、H.263.MPEG-1、MPEG-2、MPEG-4等)都采用8x8DCT作为其变换编码方案。然而，DCT也有其缺点，余弦函数的存在使得DCT过程必须使用浮点数，这样不可避免地会带来舍入误差以及编/解码端正反变换失配的问题。针对上述问题，从H.264/AVC 标准开始采用整数 DCT，这一新的技术不但解决了舍入误差以及编解码失配的问题，而且整型数的使用使得 DCT 的运行速度大为提高。

整数DCT的推导：

如上所述，最初的视频编码标准大都采用8x8DCT作为基本变换。而上一代视频编码标准H.264/AVC首次采用整数DCT,最初的3个档次(基本档次 Baseline Profile、主档次 Main Profile 和扩展档次 ExtendedProfile)仅使用了 4x4 整数 DCT,后来的高档次 HighProfile 中增加了 8x8整数 DCT 作为可选变换块大小。

下面以 4x4 DCT为例推导 H.264/AVC 中的4x4整数 DCT 变换矩阵维 4x4 DCT 公式如下:

记括号中的部分为Z(m,l)，则上式可分解为以下两式:

可以看出，二维 DCT可以分解成两个一维DCT，即先对像素块的行(或列)做一维 DCT，再对列(或行)做一维DCT。现将一维DCT写成如下矩阵相乘形式：

其中，X代表原始像素块，Y表示变换后的DCT系数矩阵，变换矩阵A可由下式定义：

存在“1”、“2”元素，因此变换过程仅需要加法、移位操作即可，从而大幅提高了计算速度。同时，与浮点DCT相比，整数DCT所有的操作都是针对整型变量的，这样做避免了精度损失，也能够消除编解码器中反变换不匹配的问题。

H.265/HEVC中的整数DCT：

H.265/HEVC 沿用了H.264/AVC 所采用的整数DCT技术，但其变换矩阵与 H.264/AVC 相比有所不同。另外，H.265/HEVC使用了4种不同尺寸的整数 DCT,分别为4x4、8x8、16x16和32x32。下面以 H.265/HEVC中4x4 整数 DCT 变换矩阵为例，说明其与H.264/AVC的区别。

类似于上述整数DCT的推导过程，可以得到：

可以用标量数乘的形式来表示。综上，H.265/HEVC中4x4整数DCT公式为:

H.265/HEVC 中还使用了3种更大尺寸的整数DCT:8x8、16x16和32x32，这3种整数DCT推导方法与4x4基本相同，唯一的区别在于矩阵元素整数化时放大的倍数不同(不同大小的变换对应的修正矩阵元素也不同)。下面给出H.265/HEVC中8x8整数 DCT的变换矩阵，16x16、32x32变换矩阵参见H.265/HEVC 标准。

可以看出，8x8整数DCT变换矩阵第0、2、4、6行前4个元素恰好组成了4x4整数DCT矩阵。事实上，类似的规律也存在于其他大小的变换矩阵中。例如，32x32矩阵偶数行(首行为第0行)前一半元素可组成16x16变换矩阵，32x32矩阵第0、4、8、12、16、20、24、28行前8个元素可组成8x8变换矩阵等。这些规律得益于不同大小的变换矩阵在整数化时放大的倍数满足一定条件，使得放大后各个矩阵元素值大小相同。该条件可具体描述为:NxN的变换矩阵整数化时放大倍数为。此外，利用该规律还可以开发出具有统一形式的整数DCT蝶形算法。

与H.264/AVC相比，H.265/HEVC在整数DCT方面有较大改进，主要表现在以下几个方面。

H.265/HEVC 采用了更多、更大尺寸的变换。由于H.265/HEVC主要面对的是高分辨率视频，与标清视频相比，高分辨率视频在相同大小的区域内包含了更多的像素，因此像素间的相关性变得更强，此时采用更大尺寸的变换能够提高压缩性能。H.265/HEVC 提供了最大为32x32的4种大小的整数DCT,并且允许根据视频内容自适应地选择变换尺寸。
H.265/HEVC中的整数DCT更接近于传统的浮点DCT。H.264/AVC 中4x4整数 DCT矩阵在整数化时放大了2~3.16倍(1、3 行放大了2倍，2、4行放大了3.16倍)，而H.265/HEVC 4x4整数 DCT矩阵在整数化时放大了128倍。因此H.265/HEVC 整数 DCT 矩阵保留了更多精度，更接近于浮点DCT，能够获得更好的性能。
H.265/HEVC 不同大小的变换形式较为统一[例如，所有大小变换矩阵第一行(零频)元素都为64等]。这得益于在整数化 DCT矩阵时，不同大小的矩阵放大倍数不同，且满足一定规律。利用这一特征，可为不同大小的整数 DCT 设计出具有统一形式的快速蝶形算法。此外，与H.264/AVC 相比，H.265/HEVC各元素放大倍数相同，因此在量化时对所有元素的缩放倍数都相同:而H.264/AVC的量化过程需要根据不同系数的位置做不同程度的比例缩放。

二、离散正弦变换：

DST原理：

类似于前文的叙述，在信号分解过程中，若采用正弦函数作为基函数，则该分解称为正弦变换(SineTransform)。若输入信号是离散的，则称之为离散正弦变换(DiscreteSineTransform，DST)。与 DCT类似，也存在以下8种类型的 DST。

在上述8类DST中，前4类对应于偶数阶的实奇DFT，后4类对应于奇数阶的实奇 DFT。H.265/HEVC使用的是Ⅶ类DST，记为DST-ⅦI。其二维形式为:

H.265/HEVC中的整数DST：

H.265/HEVC标准规定，在帧内4x4式亮度分量残差编码中使用4x4 整数 DST，而在帧内其他模式、帧间所有模式，以及所有色差分量的残差编码中一律使用整数DCT。这主要是由于帧内预测利用周围已重构块边缘像素预测当前块的方法使得帧内预测残差具有如下特征:距离预测像素越远，预测残差幅度越大。而DST的基函数能够很好地适应这一特征。实验结果表明，使用4x4 整数 DST能使帧内编码性能提高0.8%左右，而编码复杂度基本保持不变。

下面给出H.265/HEVC中4x4整数 DST矩阵的推导过程。二维4x4DST-Ⅶ公式为:

三、变换结构：

变换单元（TU）:

变换单元(Transform Unit，TU)是H.265/HEVC中变换、量化与编码的基本单位。H.265/HEVC 突破了以往标准中对变换尺寸的限制，可支持 4x4、8x8、16x16和32x32 四种大小的TU。此外，H.265/HEVC 还定义了编码单元CU和预测单元PU，并规定CU可以以四叉树(Quad-Tree)的形式划分TU，可划分的层级由当前CU的大小与头信息中规定的最大和最小TU尺寸决定,并且在同一个CU中允许选择不同的组合。编码器可根据视频内容自适应地选择划分方式，例如，在平坦区域和内容缓慢变化的区域可以使用较大的TU，在纹理细节区域可选择较小的TU，具体来说，最优划分方式可用率失真优化(RDO)准则确定。图5.4 给出了一个 32x32 CU 划分为多层不同大小 TU 的四叉树结构。

H.265/HEVC标准突破了之前标准对预测块、变换块大小关系的限制。由于其PU和TU直接由CU划分得到，因此二者大小没有确定的关系。一个PU可能包含多个TU，一个TU也可能跨越多个PU，但二者大小都必须小于CU。需要注意的是，对于帧内编码，由于相邻PU之间存在依赖关系(已编码的PU须用于预测与之相邻的PU)，因此一个PU可包含一个或多个 TU，但一个 TU 最多只能对应一个 PU。

四、哈达玛变换：

原理及特点：

沃尔什-哈达玛变换(Walsh-Hadamard Transform，WHT)是广义傅里叶变换的一种，其变换矩阵是一个的矩阵，称为哈达玛矩阵。

其推导定义为：

Hadamard变换及其矩阵有以下几个特性：

Hadamard 矩阵元素都为土1，且其特征值也只包含士1。
Hadamard 矩阵为正交、对称矩阵，相应的Hadamard 变换为正交变换。
Hadamard 矩阵奇数行(列)偶对称，偶数行(列)奇对称。
Hadamard 变换满足帕斯瓦尔(Parseval)定理(即变换前后能量守恒)。

与离散余弦变换相比，哈达玛变换仅含有加(减)法运算，而且可用递归形式快速实现;另外，其正向变换与反向变换具有相同的形式，因此其算法复杂度较低，且容易实现。

在上一代标准H.264/AVC中,哈达玛变换被用于亮度分量帧内16x16模式DC系数以及色度分量DC系数的变换，以达到进一步去除相关性的目的。编码器须将Hadamard 变换的结果经编码后写入码流传给解码器;同时，解码器也需要进行相应的逆过程。因此，H.264/AVC标准详细规定了这些步骤的实现方法以及相应的语法语义。

哈达玛变换的应用：

H.264/AVC标准规定了Hadamard变换的使用方法以及相对应的语法元素,而在新一代标准 H.265/HEVC中,由于熵编码是以 TU为单位的(一个 TU 仅包含一个 DC 系数)，且较大 TU的使用同样具有去除相关性的作用，因此标准未使用 Hadamard 变换。

在图像、视频处理领域，Hadamard变换常用于计算残差信号的SATD。SATD(SumofAbsolute Transformed Difference)是指将残差信号进行 Hadamard 变换后再求各元素绝对值之和。设某残差信号方阵为X，则 SATD 为：

其中M为方阵的大小，H为归一化的MxM Hadamard矩阵。具体应用参见下例。

Hadamard变换的例子：

给定以下4x4残差矩阵X，分别对其做 Hadamard 变换以及DCT，求该残差的SAD和SATD，并与DCT系数绝对值之和做比较。

计算可得，残差SAD为114，SATD为98，所有DCT系数绝对值之和为96。观察可知，残差 SATD与其经 DCT后各系数绝对值之和十分接近，这说明SATD能在一定程度上反映残差在频域中的大小，且其性能接近于视频编码中实际使用的 DCT,相比之下SAD 仅能反映残差在空域上的大小。考虑到Hadamard变换复杂度远小于DCT,同样小于整数DCT，因此 SATD 广泛应用于视频编码中的快速模式选择。

与之前的标准相比,H.265/HEVC采用了更多的编码技术来提高压缩效率。例如在帧内编码中，H.265/HEVC规定了5种不同大小的帧内预测块，每种大小又包含 17~35种模式。若所有模式都使用式(5-7)来计算率失真代价，则其计算复杂度会非常高。

式中SSD(s,c)表示原始像素与重构像素误差的平方和，表示表示编码当前模式下所有信息(包括划分方式、预测式编号、残差系数等)所需要的比特数。为减小模式选择的复杂度,H.265/HEVC官方测试软件HM使用了一种更加简单的方法计算率失真代价，如式(5-8)所示:

式中，SATD(S,P)即为残差的 SATD，仅为编码当前模式所需的比特数。这种方法省去了 DCT、量化、反量化、反变换以及编码过程，极大地减小了复杂度。此外，为了控制编码效率的损失，HM首先使用式(5-8)从所有模式中预先选出少数几种可能最优的模式，再用式(5-7)从预选的几种模式中选择最优的模式。

HM 在帧间编码亚像素精度运动估计过程中也使用了SATD，如式(5-9)所示:

式中，SATD(S,p)是预测误差的 SATD，表示编码运动信息(如运动向量MV、参考图像等)所需的比特数。与整像素运动估计相比，亚像素运动估计各个搜索点匹配误差相差不会太大，此时需要考虑各个点对应残差在变换域的特征，而SATD恰好能够满足需求。因而，在亚像素精度运动估计时，采用SATD作为预测误差衡量准则能够使编码性能获得一定的提高。