音视频编解码之路：JPEG 编码

本文首发于音视频编解码之路：JPEG 编码

前言

本篇是新开坑的 音视频编解码之路 的第一篇，这个系列次要通过书籍、网上的博文 / 代码等渠道，整顿与各编码协定相干的材料和本人的了解，同时手撸下对应格局的“编解码器”，造成对真正编解码器的原理的根底意识，从而后续能够进一步钻研真正意义上的编解码器如 libx264 的逻辑与优化。

之前在查找编解码的学习材料时，看到了韦神的经验之谈，因而就以 JPEG 的编码来开篇吧。

本篇整体脉络来自于手动生成一张 JPEG 图片，不过针对文章中的诸多细节做了补充和材料汇总，另外把代码也用 C ++ 和 OOP 的形式批改了下。范例工程位于 avcodec_tutorial。

编码步骤

根本零碎的 JPEG 压缩编码算法一共分为 10 个步骤：

1. 色彩模式转换
2. 分块
3. 离散余弦变换（DCT）
4. 量化
5. Zigzag 扫描排序
6. DC 系数的差分脉冲调制编码（DPCM）
7. DC 系数的两头格局计算
8. AC 系数的游程编码（RLE）
9. AC 系数的两头格局计算
10. 熵编码

接下去咱们将逐个介绍上述的各个步骤，并在其中交叉波及的一些概念与理论代码。

色彩模式转换

JPEG 采纳的是 YCbCr 色彩空间，这里不再赘述为啥抉择 YUV 等等反复较多的内容，之前没有接触过的能够看下一文读懂 YUV 的采样与格局和其余材料来补补课。

色彩模式从 RGB 转为 YUV 的过程中能够把采样也一起做了，这里 Demo 采样依照 YUV444 也就是全采样不做额定解决的形式简略实现，代码如下：

uint8_t bound(uint8_t min, int value, uint8_t max) {if(value <= min) {return min;}
    if(value >= max) {return max;}
    return value;
}

bool JpegEncoder::rgbToYUV444(const uint8_t *r, const uint8_t *g, const uint8_t *b,
                              const unsigned int &w, const unsigned int &h,
                              uint8_t *const y, uint8_t *const u, uint8_t *const v) {for (int row = 0; row < h; row++) {for (int column = 0; column < w; column++) {
            int index = row * w + column;
            // rgb -> yuv 公式
            // 这里在实现的时候踩了个坑
            // 之前间接将 cast 后的值赋值给了 y /u/ v 数组，y/u/ v 数组类型是 uint8，计算出来比方 v 是 256 间接越界数值会被转成其余如 0 之类的值
            // 导致最初色彩成果谬误
            int yValue = static_cast<int>(round(0.299 * r[index] + 0.587 * g[index] + 0.114 * b[index]));
            int uValue = static_cast<int>(round(-0.169 * r[index] - 0.331 * g[index] + 0.500 * b[index] + 128));
            int vValue = static_cast<int>(round(0.500 * r[index] - 0.419 * g[index] - 0.081 * b[index] + 128));
            // 做下边界容错
            y[index] = bound(0, yValue, 255);
            u[index] = bound(0, uValue, 255);
            v[index] = bound(0, vValue, 255);
        }
    }
    return true;
}

分块

因为前面的 DCT 变换须要对 8×8 的子块进行解决，因而在进行 DCT 变换之前必须把源图像数据进行分块。源图象通过下面的 色彩模式转换 、 采样 后变成了 YUV 数据，所以须要别离对 Y U V 三个重量进行分块。具体分块形式为由左及右，由上到下顺次读取 8×8 的子块，寄存在长度为 64 的数组中，之后再进行 DCT 变换。

因为这个分块机制的起因，有些素材的宽高如果不是 8 的倍数的话，都须要在解决的时候进行补齐。

bool JpegEncoder::yuvToBlocks(const uint8_t *y, const uint8_t *u, const uint8_t *v,
                              const unsigned int &w, const unsigned int &h,
                              uint8_t yBlocks[][64], uint8_t uBlocks[][64], uint8_t vBlocks[][64]) {int wBlockSize = w / 8 + (w % 8 == 0 ? 0 : 1);
    int hBlockSize = h / 8 + (h % 8 == 0 ? 0 : 1);
    for (int blockRow = 0; blockRow < hBlockSize; blockRow++) {for (int blockColumn = 0; blockColumn < wBlockSize; blockColumn++) {
            int blockIndex = blockRow * wBlockSize + blockColumn; // 以后子块下标
            uint8_t *yBlock = yBlocks[blockIndex];
            uint8_t *uBlock = uBlocks[blockIndex];
            uint8_t *vBlock = vBlocks[blockIndex];
            for (int row = 0; row < 8; row++) {for (int column = 0; column < 8; column++) {
                    int indexInSubBlock = row * 8 + column; // 块中数据地位
                    int realPosX = blockColumn * 8 + column; // 在残缺 YUV 数据中的 X 地位
                    int realPosY = blockRow * 8 + row; // 在残缺 YUV 数据中的 Y 地位
                    int indexInOriginData = realPosY * w + realPosX; // 在原始数据中的地位
                    if (realPosX >= w || realPosY >= h) {
                        // 补齐数据
                        yBlock[indexInSubBlock] = 0;
                        uBlock[indexInSubBlock] = 0;
                        vBlock[indexInSubBlock] = 0;
                    } else {yBlock[indexInSubBlock] = y[indexInOriginData];
                        uBlock[indexInSubBlock] = u[indexInOriginData];
                        vBlock[indexInSubBlock] = v[indexInOriginData];
                    }
                }
            }
        }

    }
    return true;
}

分块后的后果相似上面这样，假如源图像像素宽高为 64×64，色彩转换并分块后将变成 YUV 三个通道，且每通道按 8 ×8 进行拆分：

DCT

JPEG 里要对数据压缩，就须要先要做一次 DCT 变换。数学方面的细节不是目前的重点，只须要晓得这个变换是将数据域从时（空）域变换到频域，把图片里点和点间的法则出现进去，是为了更不便后续的压缩的。

先贴一下公式，对数学原理感兴趣的话能够扩大看看 JPEG 编码 & 算术编码、LZW 编码等材料：

DCT 变换与图像压缩、去燥外面还讲到了为什么 JPEG 抉择 DCT 而不抉择 DFT 的起因。

再贴一下代码：

/********* 内部逻辑 *********/
bool JpegEncoder::blocksFDCT(const uint8_t (*yBlocks)[64], const uint8_t (*uBlocks)[64], const uint8_t (*vBlocks)[64],
                             const unsigned int &w, const unsigned int &h,
                             int yDCT[][64], int uDCT[][64], int vDCT[][64]) {int wBlockSize = w / 8 + (w % 8 == 0 ? 0 : 1);
    int hBlockSize = h / 8 + (h % 8 == 0 ? 0 : 1);
    int blockSize = wBlockSize * hBlockSize;
    std::shared_ptr<JpegFDCT> fdct = std::make_shared<JpegFDCT>();
    for (int blockIndex = 0; blockIndex < blockSize; blockIndex++) {uint8_t *yBlock = yBlocks[blockIndex];
        uint8_t *uBlock = uBlocks[blockIndex];
        uint8_t *vBlock = vBlocks[blockIndex];
        for (int i = 0; i < 64; i++) {yDCT[blockIndex][i] = yBlock[i] - 128;
            uDCT[blockIndex][i] = uBlock[i] - 128;
            vDCT[blockIndex][i] = vBlock[i] - 128;

            yDCT[blockIndex][i] = yDCT[blockIndex][i] << 2;
            uDCT[blockIndex][i] = uDCT[blockIndex][i] << 2;
            vDCT[blockIndex][i] = vDCT[blockIndex][i] << 2;
        }
        fdct->fdct2d8x8(yDCT[blockIndex]);
        fdct->fdct2d8x8(uDCT[blockIndex]);
        fdct->fdct2d8x8(vDCT[blockIndex]);
    }
    return true;
}

/********* DCT 逻辑 *********/
JpegFDCT::JpegFDCT() {
    int i, j;
    float factor[64];

    // 初始化 fdct factor
    const float AAN_DCT_FACTOR[DCT_SIZE] = {
            1.0f, 1.387039845f, 1.306562965f, 1.175875602f,
            1.0f, 0.785694958f, 0.541196100f, 0.275899379f,
    };
    for (i = 0; i < DCT_SIZE; i++) {for (j = 0; j < DCT_SIZE; j++) {factor[i * 8 + j] = 1.0f / (AAN_DCT_FACTOR[i] * AAN_DCT_FACTOR[j] * 8);
        }
    }
    for (i = 0; i < 64; i++) {mFDCTFactor[i] = float2Fix(factor[i]);
    }
}
int JpegFDCT::float2Fix(float value) {return static_cast<int>(value * (1 << FIX_Q));
}
void JpegFDCT::fdct2d8x8(int *data8x8, int *ftab) {
    int tmp0, tmp1, tmp2, tmp3;
    int tmp4, tmp5, tmp6, tmp7;
    int tmp10, tmp11, tmp12, tmp13;
    int z1, z2, z3, z4, z5, z11, z13;
    int *dataptr;
    int ctr;

    /* Pass 1: process rows. */
    dataptr = data8x8;
    for (ctr = 0; ctr < DCT_SIZE; ctr++) {tmp0 = dataptr[0] + dataptr[7];
        tmp7 = dataptr[0] - dataptr[7];
        tmp1 = dataptr[1] + dataptr[6];
        tmp6 = dataptr[1] - dataptr[6];
        tmp2 = dataptr[2] + dataptr[5];
        tmp5 = dataptr[2] - dataptr[5];
        tmp3 = dataptr[3] + dataptr[4];
        tmp4 = dataptr[3] - dataptr[4];

        /* Even part */
        tmp10 = tmp0 + tmp3;  /* phase 2 */
        tmp13 = tmp0 - tmp3;
        tmp11 = tmp1 + tmp2;
        tmp12 = tmp1 - tmp2;

        dataptr[0] = tmp10 + tmp11;  /* phase 3 */
        dataptr[4] = tmp10 - tmp11;

        z1 = (tmp12 + tmp13) * float2Fix(0.707106781f) >> FIX_Q; /* c4 */
        dataptr[2] = tmp13 + z1;  /* phase 5 */
        dataptr[6] = tmp13 - z1;

        /* Odd part */
        tmp10 = tmp4 + tmp5;  /* phase 2 */
        tmp11 = tmp5 + tmp6;
        tmp12 = tmp6 + tmp7;

        /* The rotator is modified from fig 4-8 to avoid extra negations. */
        z5 = (tmp10 - tmp12) * float2Fix(0.382683433f) >> FIX_Q;  /* c6 */
        z2 = (float2Fix(0.541196100f) * tmp10 >> FIX_Q) + z5;     /* c2-c6 */
        z4 = (float2Fix(1.306562965f) * tmp12 >> FIX_Q) + z5;     /* c2+c6 */
        z3 = tmp11 * float2Fix(0.707106781f) >> FIX_Q;            /* c4 */

        z11 = tmp7 + z3;        /* phase 5 */
        z13 = tmp7 - z3;

        dataptr[5] = z13 + z2;  /* phase 6 */
        dataptr[3] = z13 - z2;
        dataptr[1] = z11 + z4;
        dataptr[7] = z11 - z4;

        dataptr += DCT_SIZE;     /* advance pointer to next row */
    }

    /* Pass 2: process columns. */
    dataptr = data8x8;
    for (ctr = 0; ctr < DCT_SIZE; ctr++) {tmp0 = dataptr[DCT_SIZE * 0] + dataptr[DCT_SIZE * 7];
        tmp7 = dataptr[DCT_SIZE * 0] - dataptr[DCT_SIZE * 7];
        tmp1 = dataptr[DCT_SIZE * 1] + dataptr[DCT_SIZE * 6];
        tmp6 = dataptr[DCT_SIZE * 1] - dataptr[DCT_SIZE * 6];
        tmp2 = dataptr[DCT_SIZE * 2] + dataptr[DCT_SIZE * 5];
        tmp5 = dataptr[DCT_SIZE * 2] - dataptr[DCT_SIZE * 5];
        tmp3 = dataptr[DCT_SIZE * 3] + dataptr[DCT_SIZE * 4];
        tmp4 = dataptr[DCT_SIZE * 3] - dataptr[DCT_SIZE * 4];

        /* Even part */
        tmp10 = tmp0 + tmp3;  /* phase 2 */
        tmp13 = tmp0 - tmp3;
        tmp11 = tmp1 + tmp2;
        tmp12 = tmp1 - tmp2;

        dataptr[DCT_SIZE * 0] = tmp10 + tmp11;  /* phase 3 */
        dataptr[DCT_SIZE * 4] = tmp10 - tmp11;

        z1 = (tmp12 + tmp13) * float2Fix(0.707106781f) >> FIX_Q; /* c4 */
        dataptr[DCT_SIZE * 2] = tmp13 + z1;  /* phase 5 */
        dataptr[DCT_SIZE * 6] = tmp13 - z1;

        /* Odd part */
        tmp10 = tmp4 + tmp5;  /* phase 2 */
        tmp11 = tmp5 + tmp6;
        tmp12 = tmp6 + tmp7;

        /* The rotator is modified from fig 4-8 to avoid extra negations. */
        z5 = (tmp10 - tmp12) * float2Fix(0.382683433f) >> FIX_Q;  /* c6 */
        z2 = (float2Fix(0.541196100f) * tmp10 >> FIX_Q) + z5;     /* c2-c6 */
        z4 = (float2Fix(1.306562965f) * tmp12 >> FIX_Q) + z5;     /* c2+c6 */
        z3 = tmp11 * float2Fix(0.707106781f) >> FIX_Q;            /* c4 */

        z11 = tmp7 + z3;  /* phase 5 */
        z13 = tmp7 - z3;

        dataptr[DCT_SIZE * 5] = z13 + z2; /* phase 6 */
        dataptr[DCT_SIZE * 3] = z13 - z2;
        dataptr[DCT_SIZE * 1] = z11 + z4;
        dataptr[DCT_SIZE * 7] = z11 - z4;

        dataptr++;  /* advance pointer to next column */
    }

    ftab = ftab ? ftab : mFDCTFactor;
    for (ctr = 0; ctr < 64; ctr++) {data8x8[ctr] *= ftab[ctr];
        data8x8[ctr] >>= FIX_Q + 2;
    }
}

JPEG 里是对每 8×8 个点作为一个单位解决的，上述代码就是对咱们方才所划分好的各个 8×8 的子块进行 DCT 变换。首先咱们看到在进行变换前须要将矩阵中的每个数值减去 128，而后再一一带入 DCT 变换公式，这是因为 DCT 公式所承受的数字范畴是 -128 到 127 之间，其目标在于使像素的绝对值呈现 3 位 10 进制的概率大大减少。其余局部的解决逻辑临时没有去深究。

假设有一个 8 ×8 的图像数据如下图所示：

那么在减去 128 之后，将变成：

再通过 DCT 变换，最终将变成DCT 系数矩阵：

对应于 u =0，v= 0 的系数，称做直流重量，即 DC 系数，即位于矩阵的最左上角，上图是 -415 的地位
对于除 DC 系数意外的矩阵中的其余 63 个则称为是交换系数（AC）

DCT 输入的频率系数矩阵中最左上角的直流（DC）系数幅度最大，以 DC 系数为出发点向下、向右的其它 DCT 系数，离 DC 重量越远，频率越高，幅度值越小，即图像信息的大部分集中于直流系数及其左近的低频频谱上，离 DC 系数越来越远的高频频谱简直不含图像信息，甚至于只含杂波。这个点从数据上的了解能够看下 JPEG 压缩原理与 DCT 离散余弦变换中量化与反量化局部。

对于图像频率能够扩大看下图像上的频率指的是什么。

量化

量化是对通过 FDCT（解码为 IDCT）变换后的频率系数进行量化，是一个将信号的幅度离散化的过程，量化过程实际上就是对 DCT 系数的一个优化过程，它是利用了人眼对高频局部不敏感的个性来实现数据的大幅简化。在这个过程实际上是简略地把频率畛域上每个成份，除以一个对于该成份的常数，且接着四舍五入取最靠近的整数，这就是整个过程中的次要有损运算。

从后果来看，这个过程常常会把很多高频率的成份四舍五入而靠近 0，且剩下很多会变成小的正或正数。而整个量化的目标正是减小非“0”系数的幅度以及减少“0”值系数的数目，量化是图像品质降落的最次要起因，量化表也是管制 JPEG 压缩比的要害。

因为人眼对亮度信号比对色差信号更敏感，因而应用了两种量化表：亮度量化值和色差量化值。

将后面所失去的 DCT 系数矩阵与上图中的亮度 / 色度量化矩阵进行相除并四舍五入后可失去：

总体来说这个过程就相似于是一个空间域的低通滤波器，对 Y 重量采纳细量化，对 UV 采纳粗量化，对低频细量化，对高频粗量化。对于滤波器感兴趣的话能够扩大看看这篇文章：常见低通、高通、带通三种滤波器的工作原理

JPEG 压缩比例，就是通过管制量化的多少来管制。比方，下面的量化矩阵，如果咱们把矩阵的每个数都 double 一下，那是不是会呈现更多的 0 了？说不定都只有 DC 系数非 0，其余都是 0，如果是这样那编码时就能够更省空间了，N 个 0 只有一个游程编码搞定，数据量超小。但也意味着，复原时，会带来更多的误差，图像品质也会变差了。

尽管量化步骤除掉了一些高频量，也就是损失了高频细节，但事实上人眼对高空间频率远没有低频敏感，所以解决后的视觉损失很小。另一个重要起因是所有图片的点与点之间会有一个色调过渡的过程，大量的图像信息被蕴含在低频率中，通过量化解决后，在高频率段，将呈现大量间断的零。对于这部分能够扩大浏览下为什么说图像的低频是轮廓，高频是噪声和细节以及图像压缩中，为什么要将图像从空间域转换到频率域

/********* 内部逻辑 *********/
bool JpegEncoder::fdctToQuant(int yDCT[][64], int uDCT[][64], int vDCT[][64],
                              const unsigned int &w, const unsigned int &h) {int wBlockSize = w / 8 + (w % 8 == 0 ? 0 : 1);
    int hBlockSize = h / 8 + (h % 8 == 0 ? 0 : 1);
    int blockSize = wBlockSize * hBlockSize;
    std::shared_ptr<JpegQuant> quant = std::make_shared<JpegQuant>();
    for (int blockIndex = 0; blockIndex < blockSize; blockIndex++) {int *yBlock = yDCT[blockIndex];
        int *uBlock = uDCT[blockIndex];
        int *vBlock = vDCT[blockIndex];
        quant->quantEncode8x8(yBlock, true);
        quant->quantEncode8x8(uBlock, false);
        quant->quantEncode8x8(vBlock, false);
    }
    return true;
}

/********* 量化逻辑 *********/
void JpegQuant::quantEncode8x8(int *data8x8, bool luminance) {for (int i = 0; i < 64; i++) {if (luminance) {data8x8[i] /= STD_QUANT_TAB_LUMIN[i];
        } else {data8x8[i] /= STD_QUANT_TAB_CHROM[i];
        }
    }
}

Zigzag 扫描排序

量化后的数据，有一个很大的特点，就是直流重量绝对于交换重量来说要大，而且交换重量中含有大量的 0。这样，对这个量化后的数据如何来进行简化，从而再更大程度地进行压缩呢？

这就呈现了“Z”字形编排的想法，次要思路就是从左上角第一个像素开始以 Z 字形进行编排：

至于为什么应用 Zigzag 进行扫描排序，我 集体认为 次要是因为图像信息的大部分集中于直流系数及其左近的低频频谱上，离 DC 系数越来越远的高频频谱简直不含图像信息，因而通过该形式能够将更多的高频数据排序到一起，以便于后续的 游程编码 (RLE：Run Length Coding) 对它们进行编码。大家能够对照下面量化后的矩阵看下应用 ZigZag 排序与不应用的话 0 数据的连续性上的差别。

/********* 内部逻辑 *********/
bool JpegEncoder::quantToZigzag(int yQuant[][64], int uQuant[][64], int vQuant[][64],
                                const unsigned int &w, const unsigned int &h) {int wBlockSize = w / 8 + (w % 8 == 0 ? 0 : 1);
    int hBlockSize = h / 8 + (h % 8 == 0 ? 0 : 1);
    int blockSize = wBlockSize * hBlockSize;
    std::shared_ptr<JpegZigzag> zigzag = std::make_shared<JpegZigzag>();
    for (int blockIndex = 0; blockIndex < blockSize; blockIndex++) {int *yBlock = yQuant[blockIndex];
        int *uBlock = uQuant[blockIndex];
        int *vBlock = vQuant[blockIndex];
        zigzag->zigzag(yBlock);
        zigzag->zigzag(uBlock);
        zigzag->zigzag(vBlock);
    }
    return true;
}

/********* 排序逻辑 *********/
void JpegZigzag::zigzag(int *const data8x8) {int temp[64];
    for (int i = 0; i < 64; i++) {temp[i] = data8x8[ZIGZAG_INDEX[i]];
    }
    for (int i = 0; i < 64; i++) {data8x8[i] = temp[i];
    }
}

DC 系数的 DPCM

8×8 图像块通过 DCT 变换之后失去的 DC 直流系数有两个特点，一是系数的数值比拟大，二是相邻 8×8 图像块的 DC 系数值变动不大。依据这个特点，JPEG 算法应用了差分脉冲调制编码 (DPCM) 技术，对相邻图像块之间量化 DC 系数的差值 (Delta) 进行编码。

DC(0)=0
Delta = DC(i)  - DC(i-1)

此局部代码混淆在最初熵编码的整个流程中，截取局部代码：

...
// DC 系数的差分脉冲调制编码（DPCM）diff = block[0] - dc;
dc = block[0];
code = diff;
// 对 code 做两头格局计算
...

DC 系数的两头格局计算

JPEG 中为了更进一步节约空间，并不间接保留数据的具体数值，而是将数据依照位数分为 16 组，保留在表外面。这也就是所谓的 变长整数编码 VLI。即，第 0 组中保留的编码位数为 0，其编码所代表的数字为 0；第 1 组中保留的编码位数为 1，编码所代表的数字为 -1 或者 1 ……，如上面的表格所示，这里，暂且称其为 VLI 编码表：

如果 DC 系数差值为 3，通过查找 VLI 能够发现，整数 3 位于 VLI 表格的第 2 组，因而，能够写成（2）（3）的模式，这里的 2 代表前面的数字（3）的编码长度为 2 位，该模式称之为 DC 系数的两头格局。

对于 VLI 能够扩大浏览下可变长度整数的编码，这类思维外围就是用较小的空间存储小数字，而用较大的空间存储大数字，采纳这种算法来对整数进行编码是有意义的，它能够节俭存储数据须要的空间或者传输数据时所需的带宽。

// 接上一章节最初传入其 Code 可进行 DC 系数的两头格局计算
// 这里 category 的命名如果感觉不好了解能够进一步去看下
// https://sce.umkc.edu/faculty-sites/lizhu/teaching/2018.fall.video-com/notes/lec04.pdf 第 16 页
void HuffmanCodec::categoryEncode(int &code, int &size) {unsigned absc = abs(code);
    unsigned mask = (1 << 15);
    int i = 15;
    if (absc == 0) {
        size = 0;
        return;
    }
    while (i && !(absc & mask)) {
        mask >>= 1;
        i--;
    }
    size = i + 1;
    if (code < 0) {code = (1 << size) - absc - 1;
    }
}

AC 系数的 RLE

游程编码 RLC（Run Length Coding）是一种比较简单的压缩算法，其根本思维是将反复且间断呈现屡次的字符应用 （间断呈现次数，字符） 来形容，从而来更进一步升高数据的传输量，举例来说，一组数据 ”AAAABBBCCDEEEE”，由 4 个 A、3 个 B、2 个 C、1 个 D、4 个 E 组成，通过 RLC 可将数据压缩为 4A3B2C1D4E（由 14 个单位转成 10 个单位）。简而言之，其长处在于将重复性高的数据量压缩成小单位，然而，其毛病在于─若该数据呈现频率不高，可能导致压缩后果数据量比原始数据量大，例如：原始数据 ”ABCDE”，压缩后果为 ”1A1B1C1D1E”（由 5 个单位转成 10 个单位）。

然而，在 JPEG 编码中，RLC 的含意就同其原有的意义略有不同。在 JPEG 编码中，假如 RLC 编码之后失去了一个（M,N）的数据对，其中 M 是两个非零 AC 系数之间间断的 0 的个数（即，行程长度），N 是下一个非零的 AC 系数的值。采纳这样的形式进行示意，是因为 AC 系数当中有大量的 0，而采纳 Zigzag 扫描也会使得 AC 系数中有很多间断的 0 的存在，如此一来，便非常适合于用 RLC 进行编码。

举个例子来解释一下，假如有以下数据：

• 57, 45, 0, 0, 0, 0, 23, 0, -30, -8, 0, 0, 1, 000…

通过 0 RLC 之后：

• (0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)

留神，如果 AC 系数之间间断 0 的个数超过 16，则须要用一个扩大字节 (15,0) 来示意 16 间断的 0。这是因为前面 huffman 编码的要求，每组数字前一个示意 0 的数量的必须是 4 bit，因而只能是 0~15，所以，如果有这么一组数字：

• 57, 十八个 0, 3, 0, 0, 0, 0, 2, 三十三个 0, 895, EOB

咱们理论这样编码：

• (0,57) ; (15,0) (2,3) ; (4,2) ; (15,0) (15,0) (1,895) , (0,0) 留神 (15,0) 示意了 16 个间断的 0。

EOB：EOB 是一个完结标记, 示意前面都是 0 了。咱们用 (0,0) 示意 EOB，然而，如果这组数字不以 0 完结, 那么就不须要 EOB。

/********* RLE 的数据 *********/typedef struct {unsigned runlen   : 4;    unsigned codesize : 4;    unsigned codedata : 16;} RLEITEM;// AC 系数的游程长度编码（RLE）// AC 系数的两头格局计算    // rle encode for acfor (i = 1, j = 0, n = 0, eob = 0; i < 64 && j < 63; i++) {if (du[i] == 0 && n < 15) {n++;} else {code = du[i]; size = 0;        // AC 系数的两头格局计算        categoryEncode(code, size);        rlelist[j].runlen   = n;        rlelist[j].codesize = size;        rlelist[j].codedata = code;        n = 0;        j++;        if (size != 0) {eob = j;}    }}// 设置 eobif (du[63] == 0) {rlelist[eob].runlen   = 0;    rlelist[eob].codesize = 0;    rlelist[eob].codedata = 0;    j = eob + 1;}

AC 系数的两头格局计算

以 DC 系数的两头格局计算 中的 编码表 以及 AC 系数的 RLE 中所举例的 RLC 后的数据为例：

(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)

咱们只解决每对数据中左边的那个数，对其进行 VLI 编码：查找下面的 VLI 编码表，能够发现，57 在第 6 组当中，因而能够将其写成 (0,6),57 的模式，该模式便称之为 AC 系数的两头格局。

同样的 (0,45) 的两头格局为 (0,6),45；(1,-30) 的两头格局为 (1,5),-30。

该局部在下面章节中已有波及，就不贴代码了。

熵编码

在失去 DC 系数的两头格局和 AC 系数的两头格局之后，为进一步压缩图像数据，有必要对两者进行熵编码，通过对呈现概率较高的字符采纳较小的 bit 数编码达到压缩的目标。JPEG 规范具体规定了两种熵编码方式：Huffman 编码和算术编码。JPEG 根本零碎规定采纳 Huffman 编码。

熵编码的介绍能够扩大浏览下三分钟学习 | 熵编码，简略说 熵编码就是在信息熵的极限范畴内进行编码，即无损压缩。

Huffman 编码：对呈现概率大的字符调配字符长度较短的二进制编码，对呈现概率小的字符调配字符长度较长的二进制编码，从而使得字符的均匀编码长度最短。Huffman 编码的原理能够扩大浏览下算法科普：乏味的霍夫曼编码。

Huffman 编码时 DC 系数与 AC 系数别离采纳不同的 Huffman 编码表，对于亮度和色度也采纳不同的 Huffman 编码表。因而，须要 4 张 Huffman 编码表能力实现熵编码的工作，等到具体 Huffman 编码时再采纳查表的形式来高效地实现。然而，在 JPEG 规范中没有定义缺省的 Huffman 表，用户能够依据理论利用自由选择，也能够应用 JPEG 规范举荐的 Huffman 表，或者事后定义一个通用的 Huffman 表，也能够针对一副特定的图像，在压缩编码前通过收集其统计特色来计算 Huffman 表的值。

联合 Huffman 编码以及上述的 DPCM、RLE 以及对应的两头格局，参照VLI 编码表，咱们再来整体地通过一个例子解释下数据最终压缩后的样子：

假设通过 RLE 之后有如下 AC 数据：

(0,57) ; (0,45) ; (4,23) ; (1,-30) ; (0,-8) ; (2,1) ; (0,0)

只解决每对数左边的那个：

• 57 是第 6 组的, 理论保留值为 111001 , 所以被编码为 (6,111001)
• 45 , 同样的操作, 编码为 (6,101101)
• 23 -> (5,10111)
• -30 -> (5,00001)
• -8 -> (4,0111)
• 1 -> (1,1)

最初，最开始的那串数字就变成了：

• (0,6), 111001 ; (0,6), 101101 ; (4,5), 10111; (1,5), 00001; (0,4) , 0111 ; (2,1), 1 ; (0,0)

括号里的数值正好合成一个字节，前面被编码的数字示意范畴是 -32767..32767。合成的字节里，高 4 位是前续 0 的个数，低 4 位形容了前面数字的位数。

再进一步通过 Huffman 查找失去如果 (0,6) 的 huffman 编码为 111000，那么最终编码的数据便是：

• 111000 111001

最初看下 DC 的编码，假如 DC 的 diff 值是 -511，编码为 (9, 000000000)，如果 9 的 Huffman 编码是 1111110，那么在 JPG 文件中, DC 的 2 进制示意为 1111110 000000000，最终加上下面 AC 的第一个数据，编码为：

• 1111110 000000000 111000 111001 …

/********* 初始化编码表 *********/HuffmanCodec::HuffmanCodec() {    initCoddList(true, true);    initCoddList(true, false);    initCoddList(false, true);    initCoddList(false, false);void HuffmanCodec::initCoddList(bool dc, bool luminance) {int i, j, k;    int symbol;    int code;    uint8_t hufsize[256];    int hufcode[256];    int tabsize;    k = 0;    code = 0x00;    const uint8_t *hufTable;    HUFCODEITEM *codeList;    if (dc && luminance) {hufTable = STD_HUFTAB_LUMIN_DC;        codeList = mCodeListDCLumin;} else if (dc && !luminance) {hufTable = STD_HUFTAB_CHROM_DC;        codeList = mCodeListDCChrom;} else if (!dc && luminance) {hufTable = STD_HUFTAB_LUMIN_AC;        codeList = mCodeListACLumin;} else {hufTable = STD_HUFTAB_CHROM_AC;        codeList = mCodeListACChrom;}    for (i = 0; i < MAX_HUFFMAN_CODE_LEN; i++) {for (j = 0; j < hufTable[i]; j++) {hufsize[k] = i + 1;            hufcode[k] = code;            code++;            k++;        }        code <<= 1;    }    tabsize = k;    for (i = 0; i < tabsize; i++) {symbol = hufTable[MAX_HUFFMAN_CODE_LEN + i];        codeList[symbol].depth = hufsize[i];        codeList[symbol].code = hufcode[i];    }}/********* 编码 *********/bool HuffmanCodec::huffmanEncode(HUFCODEITEM *codeList, int size) {unsigned code;    int len;    if (!mBitStream) {return false;}    code = codeList[size].code;    len = codeList[size].depth;    if (EOF == bitstr_put_bits(mBitStream, code, len)) {return false;}    return true;}

JPEG 文件写入

JPEG 文件大体上能够分成两个局部：标记码 (Tag) 和压缩数据。

罕用的标记有 SOI、APP0、APPn、DQT、SOF0、DHT、DRI、SOS、EOI：

更具体的细节可扩大浏览下 JPEG 文件格式详解。

bool JpegEncoder::writeToFile(char* buffer, long dataLength,                              const unsigned int &w, const unsigned int &h) {FILE *fp = fopen(mOutputPath.data(), "wb");    // SOI    fputc(0xff, fp);    fputc(0xd8, fp);    // DQT    const int *pqtab[2] = {JpegQuant::STD_QUANT_TAB_LUMIN, JpegQuant::STD_QUANT_TAB_CHROM};    for (int i = 0; i < 2; i++) {int len = 2 + 1 + 64;        fputc(0xff, fp);        fputc(0xdb, fp);        fputc(len >> 8, fp);        fputc(len >> 0, fp);        fputc(i, fp);        for (int j = 0; j < 64; j++) {fputc(pqtab[i][JpegZigzag::ZIGZAG_INDEX[j]], fp);        }    }    // SOF0    int SOF0Len = 2 + 1 + 2 + 2 + 1 + 3 * 3;    fputc(0xff, fp);    fputc(0xc0, fp);    fputc(SOF0Len >> 8, fp);    fputc(SOF0Len >> 0, fp);    fputc(8, fp); // precision 8bit    fputc(h >> 8, fp); // height    fputc(h >> 0, fp); // height    fputc(w >> 8, fp); // width    fputc(w >> 0, fp); // width    fputc(3, fp);    fputc(0x01, fp); fputc(0x11, fp); fputc(0x00, fp);    fputc(0x02, fp); fputc(0x11, fp); fputc(0x01, fp);    fputc(0x03, fp); fputc(0x11, fp); fputc(0x01, fp);    // DHT AC    const uint8_t *huftabAC[] = {            HuffmanCodec::STD_HUFTAB_LUMIN_AC, HuffmanCodec::STD_HUFTAB_CHROM_AC};    for (int i = 0; i < 2; i++) {fputc(0xff, fp);        fputc(0xc4, fp);        int len = 2 + 1 + 16;        for (int j = 0; j < 16; j++) {len += huftabAC[i][j];        }        fputc(len >> 8, fp);        fputc(len >> 0, fp);        fputc(i + 0x10, fp);        fwrite(huftabAC[i], len - 3, 1, fp);    }    // DHT DC    const uint8_t *huftabDC[] = {            HuffmanCodec::STD_HUFTAB_LUMIN_DC, HuffmanCodec::STD_HUFTAB_CHROM_DC};    for (int i = 0; i < 2; i++) {fputc(0xff, fp);        fputc(0xc4, fp);        int len = 2 + 1 + 16;        for (int j = 0; j < 16; j++) {len += huftabDC[i][j];        }        fputc(len >> 8, fp);        fputc(len >> 0, fp);        fputc(i + 0x00, fp);        fwrite(huftabDC[i], len - 3, 1, fp);    }    // SOS    int SOSLen = 2 + 1 + 2 * 3 + 3;    fputc(0xff, fp);    fputc(0xda, fp);    fputc(SOSLen >> 8, fp);    fputc(SOSLen >> 0, fp);    fputc(3, fp);    fputc(0x01, fp); fputc(0x00, fp);    fputc(0x02, fp); fputc(0x11, fp);    fputc(0x03, fp); fputc(0x11, fp);    fputc(0x00, fp);    fputc(0x3F, fp);    fputc(0x00, fp);    // data    fwrite(buffer, dataLength, 1, fp);    // EOI    fputc(0xff, fp);    fputc(0xd9, fp);    fflush(fp);    fclose(fp);    return true;}

竣工

到这里咱们编写的 JpegEncoder 就能够将传入的 RGB24 格局的数据压缩编码成 YUV444 的 JPEG 文件了，能够运行 avcodec_tutorial 我的项目，运行后将在你的桌面看到如下内容随机生成的图片：

参考文章

手动生成一张 JPEG 图片

JPEG 繁难文档

JPEG 中的范式哈夫曼编码

JPEG 图像压缩算法流程详解

JPEG 编解码原理及代码调试

JPEG standard

Variable Length Coding (VLC) in JPEG

JPEG 编码 & 算术编码、LZW 编码

图像的时频变换——离散余弦变换

图像上的频率指的是什么

为什么说图像的低频是轮廓，高频是噪声和细节

DCT 变换与图像压缩、去燥

JPEG 压缩原理与 DCT 离散余弦变换

JPEG 规范举荐的亮度、色度 DC、AC Huffman 编码表

一文读懂 YUV 的采样与格局

JPEG 文件格式详解

[数据压缩之游程编码](

本文由博客一文多发平台 OpenWrite 公布！