视频编码原理简介

要彻底理解视频编码原理，看书都是虚的，需要实际动手，实现一个简单的视频编码器：

知识准备：基本图像处理知识，信号的时域和频域问题，熟练掌握傅立叶正反变换，一维、二维傅立叶变换，以及其变种，dct 变换，快速 dct 变换。

来自知乎问题：http://www.zhihu.com/question/22567173/answer/73610451

第一步：实现有损图像压缩和解压

参考 JPEG原理，将 RGB->YUV，然后 Y/U/V 看成三张不同的图片，将其中一张图片分为 8×8 的 block 进行 dct 变换（可以直接进行二维 dct 变换，或者按一定顺序将 8×8 的二维数组整理成一个 64 字节的一维数组），还是得到一个 8×8 的整数频率数据。于是表示图像大轮廓的低频信号（人眼敏感的信号）集中在 8×8 的左上角；表示图像细节的高频信号集中在右下角。

接着将其量化，所谓量化，就是信号采样的步长，8×8 的整数频率数据块，每个数据都要除以对应位置的步长，左上角相对重要的低频信号步长是 1，也就是说 0-255，是多少就是多少。而右下角是不太重要的高频信号，比如步长取 10，那么这些位置的数据都要 /10，实际解码的时候再将他们 x10 恢复出来，这样经过编码的时候 /10 和解码的时候 x10，那么步长为 10 的信号 1, 13, 25, 37 就会变成规矩的：0, 10, 20, 30, 对小于步长 10 的部分我们直接丢弃了，因为高频不太重要。

经过量化以后，8×8 的数据块左上角的数据由于步长小，都是比较离散的，而靠近右下角的高频数据，都比较统一，或者是一串 0，因此图像大量的细节被我们丢弃了，这时候，我们用无损压缩方式，比如 lzma2 算法（jpeg 是 rle + huffman）将这 64 个 byte 压缩起来，由于后面高频数据步长大，做了除法以后，这些值都比较小，而且比较靠近，甚至右下部分都是一串 0，十分便于压缩。

JPEG 图像有个问题就是低码率时 block 边界比较严重，现代图片压缩技术往往要配合一些 de-block 算法，比如最简单的就是边界部分几个像素点和周围插值模糊一下。

做到这里我们实现了一个同 jpeg 类似的静态图片有损压缩算法。在视频里面用来保存I帧数据。

第二步：实现宏块误差计算

视频由连续的若干图像帧组成，分为 I 帧，P 帧，所谓 I 帧，就是不依赖就可以独立解码的视频图像帧，而 P 帧则需要依赖前面已解码的视频帧，配合一定数据才能生成出来。所以视频中 I 帧往往都比较大，而 P 帧比较小，如果播放器一开始收到了 P 帧那么是无法播放的，只有收到下一个I帧才能开始播放。I 帧多了视频就变大，I 帧少了，数据量是小了，但视频受到丢包或者数据错误的影响却又会更严重。

那么所谓运动预测编码，其实就是 P 帧的生成过程：继续将图片分成 16×16 的 block（为了简单只讨论 yuv 的 y 分量压缩）。I 帧内部单帧图片压缩我们采用了 8×8 的 block，而这里用 16×16 的 block 来提高帧间编码压缩率（当然也会有更多细节损失），我们用 x, y 表示像素点坐标，而 s,t 表示 block 坐标，那么坐标为（x, y）的像素点所属的 block 坐标为：

s = x / 16 = x >> 4 
t = y / 16 = y >> 4

接着要计算两个 block 的相似度，即矢量的距离，可以表示为一个 256 维矢量（16×16）像素点色彩距离的平方，我们先定义两个颜色的误差为：

PixelDiff(c1, c2) = (c1- c2) ^ 2

那么 256 个点的误差可以表示为所有对应点的像素误差和：

BlockDiff(b1, b2) = sum( PixelDiff(c1, c2) for c1 in b1 for c2 in b2)

代码化为：

int block_diff(const unsigned char b1[16][16], const unsigned char b2[16][16]) { 
    int sum = 0; 
    for (int i = 0; i < 16; i++) { 
         for (int j = 0; j < 16; j++) { 
              int c1 = b1[i][j]; 
              int c2 = b2[i][j]; 
              sum += (c1 – c2) * (c1 – c2); 
         } 
    } 
    return sum; 
}

有了这个 block 求差的函数，我们就可以针对特定 block，搜索另外若干个 block 中哪个和它最相似了（误差最小）。

第三步：实现运动预测编码

根据上面的宏块比较函数，你已经可以知道两个 block 到底像不像了，越象的block，block_diff 返回值越低。那么我们有两帧相邻的图片，P1，P2，假设 P1 已经完成编码了，现在要对 P2 进行 P 帧编码，其实就是轮询 P2 里面的每一个 block，为 P2 中每一个 block 找出上一帧中相似度最高的 block 坐标，并记录下来，具体伪代码可以表示为：

unsigned char block[16][16]; 
for (int t = 0; t <= maxt; t++) { 
    for (int s = 0; s <= maxs; s++) { 
         picture_get_block(P2, s * 16, t * 16, block); // 取得图片 P2 的 block 
         int x, y; 
         block_search_nearest(P1, &x, &y, block); // 在P1中搜索最相似的block 
         output(x, y);  // 将P1中最相似的block的左上角像素坐标 (x, y) 输出 
    } 
}

其中在 P1 中搜索最相似 block 的 block_search_nearest 函数原理是比较简单的，我们可以暴力点用两个 for 循环轮询 P1 中每个像素点开始的 16×16 的 block（速度较慢），当然实际中不可能这么暴力搜索，而是围绕 P2 中该 block 对应坐标在 P1 中位置作为中心，慢慢四周扩散，搜索一定步长，并得到一个：按照一定顺序进行搜索，并且在一定范围内最相似的宏块坐标。

于是 P2 进行运动预测编码的结果就是一大堆 (x,y) 的坐标，代表 P2 上每个 block 在上一帧 P1 里面最相似的 block 的位置。反过来说可能更容易理解，我们可以把第三步整个过程定义为：

怎么用若干 P1 里不同起始位置的 block 拼凑出图片 P2 来，使得拼凑以后的结果和 P2 最像。

拼凑的结果就是一系列 (x,y) 的坐标数据，我们继续用 lzma2 将它们先压缩起来，按照 vcd 的分辨率 352 x 240，我们横向需要 352 / 16 = 22 个 block，纵向需要 240 / 16 = 15 个 block，可以用 P1 中 22 x 15 = 330 个 block 的坐标信息生成一张和 P2 很类似的图片 P2′ ：

for (int t = 0; t < 15; t++) { 
    for (int s = 0; s < 22; s++, next++) { 
         int x = block_positions[next].x;   // 取得对应 P1上的 block像素位置 x 
         int y = block_positions[next].y;   // 取得对应 P1上的 block像素位置 y 
         // 将 P1位置(x,y)开始的 16 x 16 的图块拷贝到 P2’的 (s * 16, t * 16)处 
         CopyRect(P2′, s * 16, t * 16, P1, x, y, 16, 16); 
    } 
}

我们把用来生成 P2 的 P1 称为 P2 的 “参考帧”，再把刚才那一堆 P1 内用来拼成 P2 的 block 坐标称为 “运动矢量”，这是 P 帧里面最主要的数据内容。但是此时由 P1 和这些坐标数据拼凑出来的 P2，你会发现粗看和 P2 很象，但细看会发现有些支离破碎，并且边缘比较明显，怎么办呢？我们需要第四步。

第四步：实现P帧编码

有了刚才的运动预测矢量（一堆 block 的坐标），我们先用 P1 按照这些数据拼凑出一张类似 P2 的新图片叫做 P2’，然后同 P2 上每个像素做减法，得到一张保存 differ 的图片：

D2 = (P2 – P2′) / 2

误差图片 D2 上每一个点等于 P2 上对应位置的点的颜色减去 P2’ 上对应位置的点的颜色再除以 2，用 8 位表示差值，值是循环的，比如 -2 就是 255，这里一般可以在结果上 + 0x80，即 128 代表 0，129 代表 2，127 代表 -2。继续用一个 8 位的整数可以表示 [-254, 254] 之间的误差范围，步长精度是 2。

按照第三步实现的逻辑，P2’ 其实已经很像 P2 了，只是有些误差，我们将这些误差保存成了图片 D2，所以图片 D2 中，信息量其实已经很小了，都是些细节修善，比起直接保存一张完整图片熵要低很多的。所以我们将 D2 用类似第一步提到的有损图片压缩方法进行编码，得到最终的 P 帧数据：

Encode(P2) = Lzma2(block_positions) + 有损图像编码（D2）

具体在操作的时候，D2 的图像块可以用 16×16 进行有损编码，因为前面的运动预测数据是按 16×16 的宏块搜索的，而不用象 I 帧那样精确的用 8×8 表示，同时保存误差图时，量化的精度可以更粗一些用不着象 I 帧那么精确，可以理解成用质量更低的 JPEG 编码，按照 16×16 的块进行编码，加上误差图 D2 本来信息量就不高，这样的保存方式能够节省不少空间。

第五步：实现GOP生成

通过前面的代码，我们实现了 I 帧编码和 P 帧编码，P 帧是参考 P1 对 P2 进行编码，而所谓 B 帧，就是参考 P1 和 P3 对 P2 进行编码，当然间隔不一定是 1，比如可以是参考 P1 和 P5 对 P2 进行编码，前提条件是 P5 可以依赖 P1 及以前的数据进行解码。

不过对于一个完整的简版视频编码器，I 帧和 P 帧编码已经够了，市面上任然有很多面向低延迟的商用编码器是直接干掉 B 帧的，因为做实时传输时收到 B 帧没法播放，之后再往后好几帧收到下一个 I 或者 P 帧时，先前收到的 B 帧才能被解码出来，造成不少的延迟。

而所谓的 GOP (Group of picture) 就是由一系列类似 I, P, B, B, P, B, B, P, B, B P 组成的一个可以完整被解码出来的图像组，而所谓视频文件，就是一个接一个的 GOP，每个 GOP 由一个 I 帧开头，然后接下来一组连续的 P 或者 B 构成，播放时只有完整收到下一个 GOP 的 I 帧才能开始播放。

最后是关于参考帧选择，前面提到的 P2 生成过程是参考了 P1，假设一个 GOP 中十张图片，是 I1, P1, P2, P3, P4, … P9 保存的，如果 P1 参考 I1，P2 参考 P1, P3 参考 P2 …. P9 参考 P8 这样每一个 P 帧都是参考上一帧进行编码的话，误差容易越来越大，因为 P1 已经引入一定误差了，P2 在 P1 的基础上误差更大，到了 P9 的话，图片质量可能已经没法看了。

因此正确的参考帧选择往往不需要这样死板，比如可以 P1-P9 全部参考 I1 来生成，或者，P1-P4 参考 I1 来生成，而 P5-P9 则参考 P5 来生成，这样步子小点，误差也不算太离谱。

第六步：容器组装

我们生成了一组组编码过的 GOP 了，这时候需要一定的文件格式将他们恰当的保存下来，记录视频信息，比如分辨率，帧率，时间索引等，就是一个类似 MP4（h.264 的容器）文件的东西。至此一个简单的小型编码器我们已经完成了，可以用 SDL / DirectX / OpenGL 配合实现一个播放器，愉快的将自己编码器编码的视频播放出来。

第七部：优化改进

这时候你已经大概学习并掌握了视频编码的基础原理了，接下来大量的优化改进的坑等着你去填呢。优化有两大方向，编码效率优化和编码性能优化：前者追求同质量（同信噪比）下更低的码率，后者追求同样质量和码率的情况下，更快的编码速度。

有这个基础后接下来可以回过头去看 JPEG 标准，MPEG1-2 标准，并阅读相关实现代码，你会发现简单很多了，接着肯 H.264 代码，不用全部看可以针对性的了解以下 H.264 的 I 帧编码和各种搜索预测方法，有 H.264 的底子，你了解 HEVC 和 vpx 就比较容易了。

参考这些编码器一些有意思的实现来改进自己的编码器，试验性质，可以侧重原理，各种优化技巧了解下即可，本来就是 hack 性质的。

有卯用呢？首先肯定很好玩，其次，当你有需要使用并修改这些编码器为他们增加新特性的时候，你会发现前面的知识很管用了。

那么上面说了一通，可能有朋友会问光代码和文字不太真切，能否补充几张图片？
今天我们演示一下，欢迎继续阅读：

如何写一个视频编码器（演示篇）