视频技术快览 0x1 - 视频编码

# 视频编码原理

视频编码是对一帧帧图像来进行的。一般彩色图像的格式是 RGB 的，即用红绿蓝三个分量的组合来表示所有颜色。但是，RGB 三个颜色是有相关性的，为了去掉这个相关性，减少需要编码的信息量，通常会把 RGB 转换成 YUV，也就是 1 个亮度分量和 2 个色度分量。

另外，人眼对于亮度信息更加敏感，而对于色度信息稍弱，所以视频编码是将 Y 分量和 UV 分量分开来编码的。

对于每一帧图像，又是划分成一个个块来进行编码的，这一个个块在 H264 中叫做宏块，而在 VP9、AV1 中称之为超级块，其实概念是一样的。宏块大小一般是 16x16（H264、VP8），32x32（H265、VP9），64x64（H265、VP9、AV1），128x128（AV1）这几种。H264、H265、VP8、VP9 和 AV1 都是市面上常见的编码标准。

# 数据冗余

• 空间冗余
  • 一帧图像中，相邻像素之间的相关性
  • 如将一帧图像划分成一个个 16x16 的块之后，相邻的块很多时候都有比较明显的相似性
• 时间冗余
  • 相邻帧之间的相关性
  • 如一个帧率为 25fps 的视频中前后两帧图像相差只有 40ms，两张图像的变化是比较小的，相似性很高
• 视觉冗余
  • 人眼对于图像中高频信息的敏感度是小于低频信息的
  • 去除图像中的一些高频信息，人眼看起来跟不去除高频信息差别不大
• 信息熵冗余
  • 信息熵冗余是指信源发出的信息中存在的冗余
  • 如下面文本中的“我”，出现了 3 次，但是只需要出现一次就可以了，这就是信息熵冗余
    • 我是一个好人，我喜欢学习，我喜欢编程

# 视频编码过程

对于一个 YUV 图像，把它划分成一个个 16x16 的宏块（以 H264 为例），Y、U、V 分量的大小分别是 16x16、8x8、8x8。这里只对 Y 分量进行分析（U、V 分量同理）。假设 Y 分量这 16x16 个像素就是一个个数字，从左上角开始之字形扫描每一个像素值，则可以得到一个“像素串”。

行程编码

将 “aaaabbbccccc” 压缩成 “4a3b5c”，字符串由 13 个字节压缩到 7 个字节，这个叫做 行程编码。

但是，如果字符串是 “abcdabcdabcd” 的话，那么编码之后就会是 “1a1b1c1d1a1b1c1d1a1b1c1d”。字符串的大小从 13 字节变成了 25 字节，还变大了。

所以如果想要达到压缩的目的，必须要使得编码前的字符串中出现比较多连续相同的字符。

对于图像块也是一样的，需要使得扫描出来的“像素串”，也尽量出现连续相同的像素值，最好是一连串数字很小（比如 0）的“像素串”，因为 0 在二进制中只占 1 个位就可以了。

如何做到将这串像素值变成有很多 0 的“像素串”呢？

• 首先，通过减少图像块的空间冗余和时间冗余来接近这个目标
  • 图像内部相邻宏块之间有很多相似性，并且两张图像之间也有很多相似性
  • 可以在编码的时候进行帧内预测和帧间预测
    • 帧内预测：在当前编码图像内部已经编码完成的块中找到与将要编码的块相邻的块
      • 一般就是即将编码块的左边块、上边块、左上角块和右上角块，通过将这些块与编码块相邻的像素经过多种不同的算法得到多个不同的预测块
      • 然后再用编码块减去每一个预测块得到一个个残差块
      • 最后，取这些算法得到的残差块中像素的绝对值加起来最小的块为预测块
        • 得到预测块的算法为帧内预测模式
        • 由于这个残差块中像素的绝对值之和最小，这个残差块的像素值经过扫描之后的“像素串”就比直接扫描编码块的“像素串”中的像素值更接近 0

    

    • 帧间预测
      • 在前面已经编码完成的图像中，循环遍历每一个块，将它作为预测块，用当前的编码块与这个块做差值，得到残差块，取残差块中像素值的绝对值加起来最小的块为预测块，预测块所在的已经编码的图像称为参考帧
        • 预测块在参考帧中的坐标值 (x0, y0) 与编码块在编码帧中的坐标值 (x1, y1) 的差值 (x0 - x1, y0 - y1) 称之为运动矢量
        • 参考帧中去寻找预测块的过程称之为运动搜索

如何得到连续的 0 像素？

• 通过预测得到的残差块的像素值相比编码块的像素值，去除了大部分空间冗余信息和时间冗余信息，这样得到的像素值更小
  • 但是目标不只是将像素值变小，而是希望能出现连续的 0 像素
• 利用人眼的视觉敏感性的特点，人眼对高频信息不太敏感，所以可以去除一些高频信息
• 其次，通过变换量化来进一步接近这个目标
  • 为了分离图像块的高频和低频信息，需要将图像块变换到频域，常用的变换是 DCT 变换（离散余弦变换）
    • 在 H264 里面，如果一个块大小是 16x16 的，一般会划分成 16 个 4x4 的块（当然也有划分成 8x8 做变换的，我们这里以 4x4 为例），然后对每个 4x4 的块做 DCT 变换得到相应的 4x4 的变换块
    • 变换块的每一个“像素值”称为系数。变换块左上角的系数值就是图像的低频信息，其余的就是图像的高频信息，并且高频信息占大部分
      • 低频信息表示的是一张图的总体样貌，一般低频系数的值也比较大
      • 高频信息主要表示的是图像中人物或物体的轮廓边缘等变化剧烈的地方，高频系数的数量多，但高频系数的值一般比较小

    

  • 做完了 DCT 变换之后，低频和高频信息就分离开来了，由于低频信息在左上角，其余的都是高频信息，那么如果对变换块的像素值进行“之字形”扫描，这样得到的像素串，前面的就是数值比较大的低频系数，后面就是数值比较小的高频部分
  • 人眼对高频信息不太敏感，如果通过一种手段去除掉大部分高频信息，也就是将大部分高频信息置为 0，但又不太影响人的观感，是不是就可以达到最初的目标，即可以得到有一连串 0 的像素串
  • 让变换块的系数都同时除以一个值，这个值称为量化步长 QStep（QStep 是编码器内部的概念，用户一般使用量化参数 QP，QP 和 QStep 一一对应），得到的结果就是量化后的系数
    • QStep 越大，得到量化后的系数就会越小，相同的 QStep 值，高频系数值相比低频系数值更小，量化后就更容易变成 0，就可以将大部分高频系数变成 0

有损编码

解码的时候，会将 QStep 乘以量化后的系数得到变换系数，很明显这个变换系数和原始没有量化的变换系数是不一样的，这就是常说的有损编码。而到底损失多少呢？

由 QStep 来控制，QStep 越大，损失就越大。QStep 跟 QP 一一对应，也就是说确定了一个 QP 值，就确定了一个 QStep。所以从编码器应用角度来看，QP 值越大，损失就越大，从而画面的清晰度就会越低。同时，QP 值越大系数被量化成 0 的概率就越大，这样编码之后码流大小就会越小，压缩就会越高。

视频编码过程

为了能够在最后熵编码的时候压缩率更高，希望送到熵编码（以行程编码为例）的“像素串”，是一串含有很多 0，并且最好连续为 0 的“像素串”。

为了达到这个目标，先通过帧内预测或者帧间预测去除空间冗余和时间冗余，从而得到一个像素值相比编码块小很多的残差块。之后再通过 DCT 变换将低频和高频信息分离开来得到变换块，然后再对变换块的系数做量化。由于高频系数通常比较小，很容易量化为 0，同时人眼对高频信息不太敏感，这样就得到了一串含有很多个 0，大多数情况下是一串含有连续 0 的“像素串”，并且人的观感还不会太明显。这样，最后熵编码就能把图像压缩成比较小的数据，以此达到视频压缩的目的。

# 编码器

标准越新，最大编码块就越大，块划分的方式也越多，编码模式也就越多。因此压缩效率也会越高，但是带来的编码耗时也越大。所以在选择编码器的时候需要根据自己的实际应用场景来选择，同时还需要考虑专利费的问题。还有一个就是考虑有没有硬件支持的问题。

# H264

# 帧类型

在 H264 中，帧类型主要分为 3 大类，分别是 I 帧、P 帧和 B 帧。

从左向右，第一个 B 帧参考第一个 I 帧和第一个 P 帧，第一个 P 帧只参考第一个 I 帧（箭头是从参考帧指向编码帧）。

错误传递

由于 P 帧和 B 帧需要参考其它帧。如果编码或者解码的过程中有一个参考帧出现错误的话，那依赖它的 P 帧和 B 帧肯定也会出现错误，而这些有问题的 P 帧（B 帧虽然也可以用来作为参考帧，但是一般用的比较少）又会继续作为之后 P 帧或 B 帧的参考帧，错误会不断的传递，为了避免错误的不断传递，就有了一种特殊的 I 帧叫 IDR 帧，也叫立即刷新帧。

H264 编码标准中规定，IDR 帧之后的帧不能再参考 IDR 帧之前的帧。这样，如果某一帧编码错误，之后的帧参考了这个错误帧，则也会出错。此时编码一个 IDR 帧，由于它不参考其它帧，所以只要它自己编码是正确的就不会有问题。之前有错误的帧也不会再被用作参考帧，这样就截断了编码错误的传递，且之后的帧就可以正常编 / 解码了。

# GOP

从一个 IDR 帧开始到下一个 IDR 帧的前一帧为止，这里面包含的 IDR 帧、普通 I 帧、P 帧和 B 帧，称为一个 GOP（图像组）。

到 GOP 的大小是由 IDR 帧之间的间隔来确定的，而这个间隔叫做关键帧间隔。关键帧间隔越大，两个 IDR 相隔就会越远，GOP 也就越大；关键帧间隔越小，IDR 相隔也就越近，GOP 就越小。

GOP 越大，编码的 I 帧就会越少。相比而言，P 帧、B 帧的压缩率更高，因此整个视频的编码效率就会越高。但是 GOP 太大，也会导致 IDR 帧距离太大，点播场景时进行视频的 seek 操作就会不方便。

尤其在 RTC 和直播场景中，可能会因为网络原因导致丢包而引起接收端的丢帧，大的 GOP 最终可能导致参考帧丢失而出现解码错误，从而引起长时间花屏和卡顿。总之，GOP 不是越大越好，也不是越小越好，需要根据实际的场景来选择。

# Slice

图像内的层次结构就是一帧图像可以划分成一个或多个 Slice，而一个 Slice 包含多个宏块，且一个宏块又可以划分成多个不同尺寸的子块。Slice 其实是为了并行编码设计的，在机器性能比较高的情况下，就可以多线程并行对多个 Slice 进行编码，从而提升速度。

# H264 码流结构

# 码流格式

• Annexb 格式
  • 使用起始码来表示一个编码数据的开始，其本身不是图像编码的内容，只是用来分隔用的
  • 起始码有两种，一种是 4 字节的“00 00 00 01”，一种是 3 字节的“00 00 01”
  • 注意，为了避免和图像编码数据冲突，H264 会将图像编码数据中的下面的几种字节串做处理
    • “00 00 00”修改为“00 00 03 00”
    • “00 00 01”修改为“00 00 03 01”
    • “00 00 02”修改为“00 00 03 02”
    • “00 00 03”修改为“00 00 03 03”

    

• MP4 格式
  • 没有起始码，而是在图像编码数据的开始使用了 4 个字节作为长度标识，用来表示编码数据的长度

  

# NALU

为了能够将一些通用的编码参数提取出来，不在图像编码数据中重复，H264 设计了两个重要的参数集：

• SPS（序列参数集）
  • 主要包含的是图像的宽、高、YUV 格式和位深等基本信息
• PPS（图像参数集）
  • 主要包含熵编码类型、基础 QP 和最大参考帧数量等基本编码信息

H264 的码流主要是由 SPS、PPS、I Slice、P Slice 和 B Slice 组成的。

如何在码流中区分这几种数据？

为了解决这个问题，H264 设计了 NALU（网络抽象层单元）。SPS 是一个 NALU、PPS 是一个 NALU、每一个 Slice 也是一个 NALU。每一个 NALU 又都是由一个 1 字节的 NALU Header 和若干字节的 NALU Data 组成的。而对于每一个 Slice NALU，其 NALU Data 又是由 Slice Header 和 Slice Data 组成，并且 Slice Data 又是由一个个 MB Data 组成。

# NALU Header

• F：forbidden_zero_bit
  • 占 1bit，禁止位，H264 码流必须为 0
• NRI： nal_ref_idc
  • 占 2bits，可以取 00 ～ 11，表示当前 NALU 的重要性
  • 参考帧、SPS 和 PPS 对应的 NALU 必须要大于 0
• Type： nal_unit_type
  • 占 5bits，表示 NALU 类型

  

NALU 类型只区分了 IDR Slice 和非 IDR Slice，至于非 IDR Slice 是普通 I Slice、P Slice 还是 B Slice，则需要继续解析 Slice Header 中的 Slice Type 字段得到。

# 常见工程问题

# 多 Slice 时如何判断哪几个 Slice 是同一帧的？

在 H264 码流中，帧是以 Slice 的方式呈现的，或者可以说在 H264 码流里是没有“帧“这种数据的，只有 Slice。

Slice NALU 由 NALU Header 和 NALU Data 组成，其中 NALU Data 里面就是 Slice 数据，而 Slice 数据又是由 Slice Header 和 Slice Data 组成。在 Slice Header 开始的地方有一个 first_mb_in_slice 的字段，表示当前 Slice 的第一个宏块 MB 在当前编码图像中的序号：

• 如果 first_mb_in_slice 的值等于 0，就代表了当前 Slice 的第一个宏块是一帧的第一个 宏块，也就是说当前 Slice 就是一帧的第一个 Slice
• 如果 first_mb_in_slice 的值不等于 0，就代表了当前 Slice 不是一帧的第一个 Slice
• 使用同样的方式一直往下找，直到找到下一个 first_mb_in_slice 为 0 的 Slice，就代表新的一帧的开始，那么其前一个 Slice 就是前一帧的最后一个 Slice 了

# 如何从 SPS 中获取图像的宽高？

在编码器编码的时候会将分辨率信息编码到 SPS 中。在 SPS 中有几个字段用来表示分辨率的大小。可以解码出这几个字段并通过一定的规则计算得到分辨率的大小。

计算：

# 如何计算得到 QP 值？

在 PPS 中有一个全局基础 QP，字段是 pic_init_qp_minus26。当前序列中所有依赖该 PPS 的 Slice 共用这个基础 QP，且每一个 Slice 在这个基础 QP 的基础上做调整。在 Slice Header 中有一个 slice_qp_delta 字段来描述这个调整偏移值。更进一步，H264 允许在宏块级别对 QP 做更进一步的精细化调节。这个字段在宏块数据里面，叫做 mb_qp_delta。

计算：

# 帧内预测

一般来说，一幅图像中相邻像素的亮度和色度信息是比较接近的，并且亮度和色度信息也是逐渐变化的，不太会出现突变，即图像具有空间相关性。帧内预测就是利用这个特点来进行的，通过利用已经编码的相邻像素的值来预测待编码的像素值，最后达到减少空间冗余的目的。

# 不同块大小的帧内预测模式

视频编码是以块为单位进行的。在 H264 标准里面，块分为宏块和子块。宏块的大小是 16 x 16（YUV 4:2:0 图像亮度块为 16 x 16，色度块为 8 x 8）。

在帧内预测中，亮度宏块可以继续划分成 16 个 4 x 4 的子块。因为图像中有的地方细节很多，需要划分成更小的块来做预测会更精细，所以会将宏块再划分成 4 x 4 的子块。

帧内预测是根据块的大小分为不同的预测模式的，亮度块和色度块的预测是分开进行的。主要有以下原则：

• 宏块大小是 16 x 16，其中亮度块为 16 x 16，色度块为 8 x 8
• 帧内预测中亮度块和色度块是分开独立进行预测的
• 16 x 16 的亮度块可以继续划分成 16 个 4 x 4 的子块

# 4x4 亮度块的帧内预测模式

4 x 4 亮度块的帧内预测模式总共有 9 个，其中有 8 种方向模式和一种 DC 模式，且方向 模式指的是预测是有方向角度的。

• Vertical 模式
  • 当前编码亮度块的每一列的像素值，都是复制上边已经编码块的最下面那一行的对应位置的像素值
  • Vertical 模式得到的预测块同一列中的像素值都是一样的，该模式得到的块就叫做 Vertical 预测块
  • 该模式只有在上边块存在的时候才可用，如果不存在则该模式不可用

  

  

• Horizontal 模式
  • 当前编码亮度块的每一行的像素值，都是复制左边已经编码块的最右边那一列的对应位置的像素值
  • Horizontal 模式得到的预测块同一行的像素值都是一样的，该模式得到的块就叫做 Horizontal 预测块
  • 该模式只有在左边块存在的时候才可用，如果不存在则该模式不可用

  

  

• DC 模式
  • 当前编码亮度块的每一个像素值，是上边已经编码块的最下面那一行和左边已编码块右边最后一列的所有像素值的平均值
  • DC 模式预测得到的块中每一个像素值都是一样的，该得到的块就叫做 DC 预测块
  • 根据上边块和左边块是不是存在，该模式下预测块像素的计算方法分为以下四种情况

  

  

• Diagonal Down-Left 模式
  • Diagonal Down-Left 模式是上边块和右上块（上边块和右上块有可能是一个块，因为可能是一个 16 x 16 的亮度块）的像素通过插值得到
  • 如果上边块和右上块不存在则该模式无效

  

  

• Diagonal Down-Right 模式
  • Diagonal Down-Right 模式需要通过上边块、左边块和左上角对角的像素通过插值得到
  • 如果这三个有一个不存在则该模式无效

  

  

• Vertical-Right 模式
  • Vertical-Right 模式是需要通过上边块、左边块以及左上角对角的像素插值得到的
  • 必须要这三个都有效才能使用，否则该模式无效

  

  

• Horizontal-Down 模式
  • Horizontal-Down 模式需要通过上边块、左边块以及左上角对角的像素插值得到
  • 必须要这三个都有效才能使用，否则该模式无效

  

  

• Vertical-Left 模式
  • Vertical-Left 模式是需要通过上边块和右上块（上边块和右上块有可能是一个块，因为可 能是一个 16 x 16 的亮度块）最下面一行的像素通过插值得到
  • 如果这两种块不存在则该模式不可用

  

  

• Horizontal-Up 模式
  • Horizontal-Up 模式是需要通过左边块的像素通过插值得到的
  • 如果左边块不存在，则该模式不可用

  

  

# 16x16 亮度块的帧内预测模式

16 x 16 亮度块总共有 4 种预测模式。它们分别是 Vertical 模式，Horizontal 模式、DC 模式和 Plane 模式。

Plane 模式，相比前面三种模式稍微复杂一些，但是基本原理都差不多。Plane 预测块的每一个像素值，都是将上边已编码块的最下面那一行，和左边已编码块右边最后一列的像素值经过下面公式计算得到的。

# 8x8 色度块的帧内预测模式

8 x 8 色度块的帧内预测模式跟 16 x 16 亮度块的是一样的，也是总共有 4 种，分别为 DC 模式、Vertical 模式，Horizontal 模式、Plane 模式。与 16 x 16 亮度块不同的是，块大小不同，所以参考像素值数量会不同。

# 帧内预测模式的选择

对于每一个块或者子块，可以得到预测块，再用实际待编码的块减去预测块就可以得到残差块。主要有下面 3 种方案来得到最优预测模式：

1. 先对每一种预测模式的残差块的像素值求绝对值再求和，称之为 cost，然后取其中残差块绝对值之和也就是 cost 最小的预测模式为最优预测模式
2. 对残差块先进行 Hadamard 变换，变换到频域之后再求绝对值求和，同样称为 cost，然后取 cost 最小的预测模式为最优预测模式
3. 以对残差块直接进行 DCT 变换量化熵编码，计算得到失真大小和编码后的码流大小，然后通过率失真优化的方法来选择最优预测模式

预测之后经过 DCT 变换再量化会丢失高频信息。一般来说 QP 越大，丢失的信息越多，失真就越大，但是码流大小也越小；反之，QP 越小，丢失的信息越少，但是码流大小就越大。一般会在失真和码流大小之间平衡，尽量找到在一定码率下，失真最小的模式作为最优的预测模式，这就是率失真优化的思想。

# 帧间预测

实在自然状态下，人或者物体的运动速度在 1 秒钟之内引起的画面变化并不大，且自然运动是连续的。所以前后两帧图像往往变化比较小，这就是视频的时间相关性。帧间预测就是利用这个特点来进行的。通过在已经编码的帧里面找到一个块来预测待编码块的像素，从而达到减少时间冗余的目的。

帧内预测和帧间预测的区别：在帧内预测中，是在当前编码的图像内寻找已编码块的像素作为参考像素计算预测块。而帧间预测是在其他已经编码的图像中去寻找参考像素块的。

帧间预测是可以在多个已经编码的图像里面去寻找参考像素块的，称之为多参考。多参考和单参考（只在一帧图像里面寻找参考像素块）其实底层的原理是一样的，只是多参考需要多搜索几个参考图像去寻找参考块而已。

帧间预测既可以参考前面的图像也可以参考后面的图像（如果参考后面的图像，后面的图像需要提前先编码，然后再编码当前图像）。只参考前面图像的帧称为前向参考帧，也叫 P 帧；参考后面的图像或者前面后面图像都参考的帧，称之为双向参考帧，也叫做B 帧。B 帧相比 P 帧主要是需要先编码后面的帧，并且 B 帧一个编码块可以有两个预测块，这两个预测块分别由两个参考帧预测得到，最后加权平均得到最终的预测块。P 帧和 B 帧的底层逻辑基本是一样的。

# 帧间编码

# 块大小

帧内预测有亮度 16 x 16、亮度 4 x 4 和色度 8 x 8 这几种块。类似地，在帧间预测也一样有不同的块和子块大小。相比帧内预测，帧间预测的块划分类型要多很多。宏块大小 16 x 16，可以划分为 16 x 8，8 x 16， 8 x 8 三种，其中 8 x 8 可以继续划分成 8 x 4，4 x 8 和 4 x 4，这是亮度块的划分。在 YUV 4:2:0 中，色度块宽高大小都是亮度块的一半。

亮度宏块的划分方式如下图所示：

# 参考帧和运动矢量

在帧间预测中，会在已经编码的帧里面找到一个块来作为预测块，这个已经编码的帧称之为参考帧。

在 H264 标准中，P 帧最多支持从 16 个参考帧中选出一个作为编码块的参考帧，但是同一个帧中的不同块可以选择不同的参考帧，这就是多参考。

通常在 RTC 场景中，比如 WebRTC 中，P 帧中的所有块都参考同一个参考帧，并且一般会选择当前编码帧的前一帧来作为参考帧。是因为自然界的运动一般是连续的，同时在短时间之内的变化相对比较小，所以前面的帧通常是最接近当前编码帧的，并且两者的差距比较小。因此，比较容易从前一帧中找到一个跟当前编码块差距很小的块作为预测块，这样编码块减去预测块得到的残差块的像素值很多都是 0，压缩效率就很高。

虽然运动变化比较小，但是还是有变化的：

用运动矢量来表示编码帧中编码块和参考帧中的预测块之间的位置的差值。

比如说上面两幅图像中，小车从前一幅图像中的（32，80）的坐标位置，变化到当前图像（80，80）的位置，向前行驶了 48 个像素。如果选用（32，80）这个块作为当前（80，80）这个编码块的预测块的话，就可以得到全为 0 像素的残差块了,因为小车本身是没有变化的，变化的只是小车的位置。

称（32 - 80， 80 - 80）也就是（-48， 0）为运动矢量。先把运动矢量编码到码流当中，这样解码端只要解码出运动矢量，使用运动矢量就可以在参考帧中找到预测块了，再解码出残差（如果有的话），残差块加上预测块就可以恢复出图像块了。

# 运动搜索

通过人眼能够看到小车在两幅图像的位置，所以可以在参考帧中找到一个与当前编码块相似的块作为预测块，但是编码器怎么找到这个预测块呢？这就是运动搜索算法应该解决的问题。

运动搜索的目标就是在参考帧中找到一个块，称之为预测块，且这个预测块与编码块的差距最小。从计算机的角度来说就是，编码块跟这个预测块的差值，也就是残差块的像素绝对值之和最小。

如说当前编码块大小是 16 x 16，那就先去参考帧中找到一个个 16 x 16 的块作为预测块，并用当前编码块减去预测块求得残差块，然后用经常做的绝对值求和操作得到两者之间的差距，最后选择差距最小的预测块作为最终的预测块。

运动搜索的方法就很简单了，就是从参考帧中第一个像素开始，将一个个 16 x 16 大小的块都遍历一遍。总是可以找到差距最小的块，这种方法称之为全搜索算法。

全搜索算法一定可以搜索到最相似的预测块。但是这种方法有一个特别大的缺点就是需要逐个像素去遍历每一个块，非常费时间。由于帧间预测中每一个 16 x 16 的宏块还可以划分成上面讲的多种不同的子块大小，每一个子块也需要做一遍运动搜索。如果采用这种运动搜索算法的话，那编码一帧的时间将会非常长。

常见的快速运动搜索算法：

• 钻石搜索算法（为菱形搜索算法）
  • 以一个菱形的模式去寻找最优预测块
  • 以亮度 16 x 16 的块的运动搜索为例
    • 1. 从搜索的起始点开始，以起始点作为菱形的中心点
      • a. 先以该中心点为左上角像素的 16 x 16 的块作为预测块，求得残差块并求得像素绝对值之和，也就是 SAD
      • b. 之后对菱形 4 个角的 4 个点分别做同样的操作求得 SAD 值
      • c. 得到最小的 SAD 值，最小 SAD 值对应的点就是当前最佳匹配点
    • 1. 如果最佳匹配点是菱形的中心点，那就找到了预测块了，搜索结束
    • 1. 如果最佳匹配点不是菱形的中心点，则用以当前最佳匹配点为中心点的菱形继续搜索，重复之前的步骤直到菱形的中心点为最佳匹配点

    

• 六边形搜索算法
  • 六边形搜索跟钻石搜索差不多，只是搜索模式是六边形的
  • 以亮度 16 x 16 的块为例
    • 1. 从搜索的起始点开始，以起始点作为六边形的中心点。求得中心点作为左上角像素的预测块的 SAD 值。之后对六边形的角上的 6 个点做同样的操作求得 SAD 值。得到最小的 SAD 值，而最小 SAD 值对应的点就是当前最佳匹配点
    • 1. 如果最佳匹配点是六边形的中心点，那就用以该点为中心点的菱形和正方形各进行一次精细化搜索。找到中心点、菱形的 4 个顶点和正方形 4 个顶点中 SAD 最小的点作为最佳匹配点
    • 1. 如果最佳匹配点不是六边形的中心点，则用以当前最佳匹配点为中心点的六边形继续搜索，重复之前的步骤直到中心点为最佳匹配点

    

通过上面的快速搜索算法就能够得到编码块在参考帧中的最佳匹配点，以最佳匹配点为左上角像素的块就是预测块，并且预测块左上角像素在参考帧中的坐标 (x1, y1) 与编码块在当前编码帧中的坐标 (x0, y0) 的差值（x1 - x0, y1 - y0）就是运动矢量。

有了快速运动搜索算法就不需要遍历整个参考帧的像素去寻找预测块了，这样速度可以快很多。但是必须要说明一下，就是快速搜索算法也有一个缺点，它搜索到的预测块不一定是全局最优预测块，也就是说不一定是最相似的块，有可能是局部最优预测块。

但是实验数据表明，快速搜索算法相比全搜索算法压缩性能下降非常小，速度却可以提升十几倍到几十倍。所以总的来说，可以认为快速搜索算法是远好于全搜索算法的，并且一般全搜索算法是不会实际使用的。

# 亚像素插值

为了能够解决这种半个像素或者 1/4 个像素的运动带来的压缩效率下降的问题，通过对参考帧进行半像素和 1/4 像素插值（统称为亚像素插值）的方式来解决。

用插值的方式将半像素和 1/4 像素算出来，也当作一个像素，这样小车向前行驶 48.5 个像素也好，向前行驶 48.25 个像素也好，都是可以通过运动矢量找到比较准确的位置的。

亚像素插值的思想跟前面的插值算法的思想是一样的，都是通过已经有的像素点经过一定的加权计算得到需要求得的像素。先通过整像素插值得到半像素，然后再通过半像素和整像素插值得到 1/4 像素。

其中，灰色为整像素点，橙色为水平半像素，黄色为垂直半像素点，绿色为中心半像素点。

半像素点的插值是以 6 个整像素点使用六抽头插值滤波器计算得到的，滤波器权重系数为：(1/32, -5/32, 5/8, 5/8, -5/32, 1/32)。

得到了半像素之后，1/4 像素就比较简单，由整像素和半像素求平均值得到，其插值过程可以通过下图表示：

其中，红色点为 1/4 像素点，具体计算方法如下：

整个半像素和 1/4 像素的插值过程可以通过下图表示：

# 亚像素精度运动搜索

插值得到的小车跟原始的小车的对应像素点的像素值并不是完全一样的，毕竟插值得到的像素点是利用滤波算法加权平均得到的。

因此，半像素插值得到的预测块并不一定就比整像素预测块的残差小。只是多了很多个半像素预测块和 1/4 像素预测块的选择，所以可以在整像素预测块、半像素预测块和 1/4 像素预测块里面选择一个最好的。怎么选择呢？其实是在整像素运动搜索的基础上，再做一次精细化的亚像素运动搜索。

一般亚像素运动搜索的步骤如下：

1. 先通过快速搜索算法进行整像素运动搜索算法得到整像素的运动矢量；
2. 对参考帧进行半像素和 1/4 像素插值；
3. 以整像素运动矢量指向的整像素为起点，进行钻石搜索算法，分别求得中心点以及上、下、左、右四个半像素点对应预测块的残差块，得到 SAD 值。取 SAD 值最小的点为最佳匹配点
4. 以半像素运动搜索的最佳匹配点为起点，分别求得中心点以及上、下、左、右四个 1/4 像素点对应预测块的残差块，得到 SAD 值，并取最小的点为最佳匹配点。

通过上面亚像素搜索算法得到的最佳匹配点就可以得到最后的运动矢量了。

假设整像素运动矢量为 (a0, b0)，半像素最佳匹配点相对于整像素最佳匹配点的运动矢量为 (a1, b1)，1/4 像素最佳匹配点相对于半像素最佳匹配点的运动矢量为 (a2, b2)，则最后运动矢量（a，b）的值的计算方法如下：

# 运动矢量预测

运动矢量跟编码块一样不是直接编码进去的，而是先用周围相邻块的运动矢量预测一个预测运动矢量，称为 MVP。将当前运动矢量与 MVP 的残差称之为 MVD，然后编码到码流中去的。解码端使用同样的运动矢量预测算法得到 MVP，并从码流中解码出运动矢量残差 MVD，MVP + MVD 就是运动矢量了。

以 16 x 16 宏块为例通过下图来描述：

1. 取当前编码宏块的左边块 A、上边块 B、右上块 C。如果右上块不存在或者参考帧与当前编码宏块不同（多参考的时候会存在），则使用左上块 D 替换 C，即 C = D
2. 求得 A、B、C 块的参考帧有多少个与当前编码块的参考帧相同，记为 count
3. 如果 count > 1，则取 A、B、C 块的运动矢量的中值（就是 A、B、C 块运动矢量的 3 个 x 和 3 个 y 分别取中间值作为 MVP 的 x 和 y）
4. 如果 count = 1，则直接将这个块的运动矢量作为 MVP
5. 如果 count = 0，并且 B、C 都不存在，A 存在的话，则直接将 A 的运动矢量作为 MVP
6. 如果上述条件都不满足，则取 A、B、C 块运动矢量的中值

# SKIP 模式

如果运动矢量就是 MVP，也就是说 MVD 为 (0，0)，同时，残差块经过变换量化后系数也都是等于 0，那么当前编码块的模式就是 SKIP。

相比于 SKIP 模式，其它模式要不就是 MVD 不为 0，要不就是量化后的残差系数不为 0，或者两者都不为 0。所以说SKIP 模式是一种特例，由于 MVD 和残差块都是等于 0，因此压缩效率特别高。

图像中的静止部分或者是图像中的背景部分大多数时候都是 SKIP 模式。这种模式非常省码率，且压缩效率非常高。

# 帧间模式选择

编码块帧间模式的选择其实就是参考帧的选择、运动矢量的确定，以及块大小（也就是块划分的方式）的选择，如果 SKIP 单独拿出来算的话就再加上一个判断是不是 SKIP 模式。

# 变换量化

# DCT 变换

DCT 变换(离散余弦变换)，能够将空域的信号（对于图像来说，空域就是平时看到的图像）转换到频域（对于图像来说，就是将图像做完 DCT 变换之后的数据）上表示，并能够比较好的去除相关性。其主要用于视频压缩领域。现在常用的视频压缩算法中基本上都有 DCT 变换。

图片经过 DCT 变换之后，低频信息集中在左上角，而高频信息则分散在其它的位置。通常情况下，图片的高频信息多但是幅值比较小。高频信息主要描述图片的边缘信息。

由于人眼的视觉敏感度是有限的，去除了一部分高频信息之后，人眼看上去感觉区别并不大。因此，可以先将图片 DCT 变换到频域，然后再去除一些高频信息。这样就可以减少信息量，从而达到压缩的目的。

DCT 变换本身是无损的，同时也是可逆的。可以通过 DCT 变换将图片从空域转换到频域，也可以通过 DCT 反变换将图片从频域转回到空域。

一维 DCT 变换公式如下，其中 f(i) 是指第 i 个样点的信号值，N 代表信号样点的总个数。

二维 DCT 变换公式如下，其中 f(i, j) 是指第 (i, j) 位置的样点的信号值，N 代表信号样点的总个数。

一般在编码标准中图像是进行二维 DCT 变换的，因为图像是个二维信号。但是实际上在代码里面经常将二维 DCT 变换转换成两个一维 DCT 变换来进行。

在视频压缩中，DCT 变换是在帧内预测和帧间预测之后进行的。也就是说，DCT 变换其实是对残差块做的。在编码时会将图像划分成一个个宏块，而宏块又可以划分成一个个子块。

通常情况下 DCT 变换是在 4x4 的子块上进行的（也可以在 8x8 子块上进行，但是只有在扩展 profile 才支持），即便预测时并没有对宏块再做划分。也就是说，不管宏块有没有被划分到 4x4 的子块，在做 DCT 变换时，都是在一个个 4x4 块上进行的。

将上面的 DCT 变换公式用在 4x4 的变换块上，则 4x4 的 DCT 变换就可以通过下面的 4x4 的矩阵乘法来表示了。

# Hadamard 变换

DCT 变换的计算过程中涉及到了 cos 函数。那也就是说计算的过程中一定涉及到了浮点运算。而浮点运算计算速度比较慢。

Hadamard 变换可以代替 DCT 变换将残差块快速转换到频域，以便用来估计一下当前块编码之后的大小。

Hadamard 变换的矩阵表示形式：

Hadamard 变换是没有浮点运算的？因此其计算速度很快，并且也能够将图像块从空域变换到频域。因此，可以用它一定程度上粗略的代替 DCT 变换，从而用来简化运算。

# 量化

将图像块变换到频域之后，AC 系数比较多，但是一般幅值比较小。并且，可以去除一些 AC 系数，达到压缩图像的目的，同时人眼看起来差距不大。这个去除 AC 系数的操作就是量化。

量化的操作并不是针对 AC 系数去做的，DC 系数也同样会做量化，只是通常情况下，DC 系数比较大，从而量化后变换为 0 的概率比 AC 系数要小。量化操作其实非常简单，就是除法操作。

在量化过程中，最重要的就是 QStep（用户一般接触到的是 QP，两者可以查表转换）。

其中，在 H264 中 QP 和 QStep 之间的转换表格如下：

通常 QStep 值越大，DC 系数和 AC 系数被量化成 0 的概率也就越大，从而压缩程度就越大，但是丢失的信息也就越多。这个值太大了会造成视频出现一个个块状的效应，且严重的时候看起来像马赛克一样；这个值比较小的话，压缩程度也会比较小，从而图像失真就会比较小，但是压缩之后的码流大小就会比较大。

# H264 中的 DCT 变换和量化

H264 为了减少这种浮点型运算漂移带来的误差，将 DCT 变换改成了整数变换，DCT 变换中的浮点运算和量化过程合并，这样就只有一次浮点运算过程，以此来减少不同机器上浮点运算产生的误差。

# H264 的整数变换和量化

道常规的 DCT 变换的矩阵计算方式如下：

而在 H264 中，将 DCT 变换一步步修改为整数变换。最后 H264 中的 DCT 变换就变成了整数变换。其矩阵的计算方式如下：

将点乘左边的部分取出来，就是 H264 中的整数变换了:

在前面整数变换里，DCT 变换中的点乘部分被拿出来了，这一部分的计算被合并到了 H264 的量化过程中。因此 H264 的量化过程如下所示：

其中，MF 一般都是通过表格查询得到：

# H264 各模式块的 DCT 变换和量化过程

1. 亮度 16x16 帧内预测块 亮度 16x16 块，首先被划分成 16 个 4x4 的小块做整数变换。变换之后将 16 个 4x4 小块的 DC 系数都拿出来，组成一个 4x4 的 DC 块，再对这个 4x4 的 DC 块进行 Hadamard 变换。然后，再总体进行量化操作。

1. 其它模式亮度块 对于除亮度 16x16 帧内预测块之外的其它亮度块，都是直接划分成 4x4 的块进行整数变换，之后再进行量化操作就可以了。

1. 色度块 对于 YUV420 图像，色度块大小是 8x8。我们先将 8x8 色度块划分成 4 个 4x4 的小块做整数变换。变换之后将 4 个小块的 DC 系数拿出来，组成一个 2x2 的 DC 块，再对这个 2x2 的 DC 块进行 Hadamard 变换。最后总体进行量化操作。