【数据压缩】JPEG原理分析及JPEG解码器的调试

掌握JPEG编解码系统的基本原理。初步掌握复杂的数据压缩算法实现，并能根据理论分析需要实现所对应数据的输出。

JPEG编码过程如上图所示。解码是编码的逆过程。

• 灰度级是$2^n$减去的像素$2^{n?1}$，将无符号的整数值变成有符号数。
  对于n=通过减去128，将0-255值域， 转换值域-128~127之间的值。
• 目的：大大降低3位10进制像素绝对值的概率，提高编码效率。

对于每个单独的彩色图像重量，将整个重量图像分成8×8图像块，这些图像块中的每个都使用自己的离散余弦变换单独编码，并在变换后去除重量之间的相关性。
正交变换的本质可以看作是基底函数的分解，如下图所示。

通过系数加权，它们可以组合成任何84个余弦函数×8的图像。我们需要做的是计算每个余弦波的系数。左上角全白是直流系数，即DC交流系数是其他系数AC系数。从左上角到右下角，从低频部分到高频部分。由于高频余弦波对图像的贡献不大，通过去除高频部分来压缩图像空间。去除高频部分的过程称为量化。

• 根据系数量化步距①位置，②颜色分量 来确定。
• 由于人眼对亮度信号比对色差信号更敏感，因此使用了亮度量化值和色差量化值两种量化表。
• 根据人眼的视觉特点(对低频敏感，对高频不敏感)，对低频分量和高频分量进行详细量化。
• 在JPEG在标准中，不同的压缩机将根据感觉使用不同的量化表。我们需要做的是将每个系数除以相应的量化值，然后四舍五入到最接近的整数。
  建议量化表如下图所示，基于人类生理感知阈值实验。
  
• 真正的量化表=缩放因子×缩放因子由质量因子决定，质量因子越高越接近原图，压缩率越小。
  质量因子≤ 50：缩放因子= 50 / 质量因子;
  质量因子> 50：缩放因子 = 2 – 质量 因子/ 50

• 8×8图像块经过DCT变换后得到的DC直流系数有两个特点：
  ? 系数值较大
  ? 相邻8×8图像块的DC系数值变化不大：冗余值变化不大：

根据这一特点，JPEG该算法使用差分脉冲调制编码(DPCM)技术，对相邻图像块之间量化DC系数的差值DIFF进行编码： D I F F k = D C k ? D C k ? 1 D I F F_{k}=D C_{k}-D C_{k-1} DIFFk=DCspan class="" style="top: -2.55em; margin-left: -0.07153em; margin-right: 0.05em;">k​−DCk−1​
之后，对DIFF进行Huffman编码。

• 由于经DCT变换后，系数大多数集中在左上角，即低频分量区，因此采用Z字形按频率的高低顺序读出，可以出现很多连零的机会。可以使用游程编码。尤其在最后，如果都是零，给出EOB (End of Block)即可，如下图所示。
  
• 游程编码在JPEG和MPEG编码中规定为：(run, level)
  ➢ 表示连续run个0，后面跟值为level的系数
  ➢ 如：0，2，0，0，3，0，-4，0，0，0，-6，0，0，5，7
  ➢ 表示为(1, 2)， (2, 3) ，…
• 编码：
  ➢ Run: 最多15个，用4位表示RRRR；
  ➢ Level：类似DC，分成16个类别，用4位表示SSSS表示类别号，类内索引；
  ➢ 之后对(RRRR, SSSS)联合用Huffman编码；
  ➢ 对类内索引用定长码编码。

对DIFF用Huffman编码：分成类别，类似指数Golomb编码
➢ 类别ID：一元码编码
➢ 类内索引：采用定长码

例：DC=8，上一DC=5，则DIFF=8-5=3，类别ID=2，类内索引=3，则码流=10011。

对于任何一个RLE的数据对，都可以表示成(RRRR,SSSS)的形式。其中前面的0-16采用自然码RRRR，后面的SSSS则是与DC一致的Huffman分组的编码方式，存储索引。放到码流里的是其组内编码。

• ZRL：表示16个0
• 0，2，0，0，3，0，-4，0，0，0，-6，0，0，5，7,…

JPEG 在文件中以 Segment 的形式组织，它具有以下特点：

• 均以 0xFF 开始，后跟 1 byte 的 Marker 和 2 byte 的 Segment length（包含表示Length 本身所占用的 2 byte，不含“0xFF” + “Marker” 所占用的 2 byte）；
• 采用 Motorola 序（相对于 Intel 序），即保存时高位在前，低位在后；
• Data 部分中，0xFF 后若为 0x00，则跳过此字节不予处理；

SOI，Start of Image，图像开始
APP0，Application，应用程序保留标记0
DQT，Define Quantization Table，定义量化表
SOF0，Start of Frame，帧图像开始
DHT，Define Huffman Table，定义哈夫曼表
SOS，Start of Scan，扫描开始 12字节
EOI，End of Image，图像结束 2字节

• SOI ,Start of Image， 图像开始
  标记代码 2字节 固定值0xFFD8
• EOI，End of Image， 图像结束 2字节
  标记代码 2字节 固定值0xFFD9

标记代码 2字节 固定值0xFFE0
包含9个具体字段：

• 数据长度 2字节 9个字段的总长度
• 标识符 5字节 固定值0x4A46494600，即字符串“JFIF0”
• 版本号 2字节 一般是0x0102，表示JFIF的版本号1.2
• X和Y的密度单位 1字节 只有三个值可选　0：无单位；1：点数/英寸；2：点数/厘米
• X方向像素密度 2字节 取值范围未知
• Y方向像素密度 2字节 取值范围未知
• 缩略图水平像素数目 1字节 取值范围未知
• 缩略图垂直像素数目 1字节 取值范围未知
• 缩略图RGB位图 长度可能是3的倍数 缩略图RGB位图数据

• 标记代码 2字节 固定值0xFFDB
• 包含9个具体字段：
  ａ．数据长度 2字节 字段ａ和多个字段ｂ的总长度
  ｂ．量化表 数据长度-2字节
  a) 精度及量化表ID 1字节
  高4位：精度，只有两个可选值 0：8位；1：16位　
  低4位：量化表ID，取值范围为0～3
  b) 表项 (64×(精度+1))字节
  例如8位精度的量化表,其表项长度为64×（0+1）=64字节
• 本标记段中，字段ｂ可以重复出现，表示多个量化表，但最多只能出现4次。

• 标记代码 2字节 固定值0xFFC0
• 包含9个具体字段：
  ａ．数据长度 2字节 ①~⑥六个字段的总长度
  ｂ．精度 1字节 每个数据样本的位数
  通常是8位，一般软件都不支持 12位和16位
  ｃ．图像高度 2字节 图像高度（单位：像素）
  ｄ．图像宽度 2字节 图像宽度（单位：像素）
  ｅ．颜色分量数 1字节 只有3个数值可选
  　　1：灰度图；3：YCrCb或YIQ；4：CMYK
  　　而JFIF中使用YCrCb，故这里颜色分量数恒为3
  ｆ．颜色分量信息 颜色分量数×3字节（通常为9字节）
  a)颜色分量ID 1字节
  b)水平/垂直采样因子 1字节
  高4位：水平采样因子　低4位：垂直采样因子
  c) 量化表 1字节 当前分量使用的量化表的ID

• 标记代码 2字节 固定值0xFFC4

• 包含2个具体字段：
  ａ． 数据长度 2字节
  ｂ．huffman表 数据长度-2字节

• 表ID和表类型 1字节
  高4位：类型，只有两个值可选　0：DC直流；1：AC交流
  低4位：哈夫曼表ID，注意，DC表和AC表分开编码

• 不同位数的码字数量 16字节

• 编码内容 16个不同位数的码字数量之和（字节）
  本标记段中，字段ｂ可以重复出现（一般4次），也可以只出现1次。

• 标记代码 2字节 固定值0xFFDA

• 包含2个具体字段：
  ａ．数据长度 2字节 ａ~ｄ两个字段的总长度
  ｂ．颜色分量数 1字节 应该和SOF中的字段⑤的值相同，即：1：灰度图是；3： YCrCb或YIQ；4：CMYK。
  ｃ．颜色分量信息
  a) 颜色分量ID 1字节
  b) 直流/交流系数表号 1字节
  高4位：直流分量使用的哈夫曼树编号
  低4位：交流分量使用的哈夫曼树编号
  ｄ．压缩图像数据
  a)谱选择开始 1字节 固定值0x00
  b)谱选择结束 1字节 固定值0x3F
  c)谱选择 1字节 在基本JPEG中总为00

（1）读取文件
（2）解析segmentmarker：依次解析出SOI、APP0、DCT、SCF0、DHT、SOS、EOI
解析SOI
解析APP0

• 检查标识“JFIF”及版本
• 得到一些参数

解析DCT

• 得到量化表长度（可能包含多张量化表）
• 得到量化表的精度
• 得到及检查量化表的序号（只能是 0-3）
• 得到量化表内容（64 个数据）

解析SCF0

• 得到每个 sample 的比特数、长宽、颜色分量数
• 得到每个颜色分量的 ID、水平采样因子、垂直采样因子、使用的量化表序号（与 DQT 中序号对应）
• 解析 DHT

解析DHT

• 得到 Huffman 表的类型（AC、DC）、序号
• 依据数据重建 Huffman 表

解析SOS

• 得到解析每个颜色分量的 DC、AC 值所使用的 Huffman 表序号（与 DHT 中序号对应）

（3）依据每个分量的水平采样、垂直采样因子计算MCU（微控制单元，即RAM，即要开辟的图像内存）的大小，并得到每个MCU中８＊８宏块的个数。
（４）对每个MCU解码：对每个宏块进行huffman解码得到DCT系数，进行IDCT得到变换之前的数据。
（５）解析到EOI，解码结束
（６）将得到的Ｙ、Cb、Cr转换成需要的色彩空间并保存。

逐步调试JPEG解码器程序。将输入的JPG文件进行解码，将输出文件保存为可供YUVViewer观看的YUV文件。
输入文件如下。

工程中有三个头文件：stdint.h、tinypeg.h、tinyjpeg-internal.h以及三个.c文件：jidctflc.c、loadjpeg.c、tinyjpeg.c。

创建一个快速查找表用于快速解码，如果查找失败则用慢速查找表。目的是加快解码过程。

struct huffman_table
{ 
        
  /*快速查表，用HUFFMAN_HASH_SIZE个比特可以快速找到符号，如果符号<0，那么需要查看慢速查找表 */
  short int lookup[HUFFMAN_HASH_SIZE];
  /* 给出码字长度，输出权值对应的码长 */
  unsigned char code_size[HUFFMAN_HASH_SIZE];
  /*给出在慢速查找表中没有出现的码字，计算256值是否足以存储所有值*/
  uint16_t slowtable[16-HUFFMAN_HASH_NBITS][256];
};

用于存储一个MCU块的信息，每处理一个新的MCU块后，信息都会更新。用它来保存一些解码过程中需要用到的信息，如量化表、前一个直流的值和当前MCU的DCT块从而使解码更加简单。

struct component 
{ 
        
  unsigned int Hfactor; /* 水平采样情况 */
  unsigned int Vfactor; /* 垂直采样情况 */
  float *Q_table;		/* 指向量化表 */
  struct huffman_table *AC_table; /* 指向直流huffman_table */
  struct huffman_table *DC_table; /* 指向交流huffman_table */
  short int previous_DC;	/* 前一个直流系数 */
  short int DCT[64];		/* DCT系数 */
#if SANITY_CHECK
  unsigned int cid;
#endif
};

该结构体是解码过程中频繁用到的东西，起到整合基本信息、连接各个部分的作用。它用于存储图像的基本信息和各通道信息。包含了前两个结构体的内容。由于是采用指针方式，并不占用额外的空间。

struct jdec_private
{ 
        
  /* 公有变量 */
  uint8_t *components[COMPONENTS];
  unsigned int width, height;	/* 图像大小 */
  unsigned int flags;

  /* 私有变量 */
  const unsigned char *stream_begin, *stream_end;
  unsigned int stream_length;

  const unsigned char *stream;	/* 指向当前流的指针 */
  unsigned int reservoir, nbits_in_reservoir;

  struct component component_infos[COMPONENTS];	/* 各通道信息 */
  float Q_tables[COMPONENTS][64];		/* 三通道量化表 */
  struct huffman_table HTDC[HUFFMAN_TABLES];	/* 直流huffman tables */
  struct huffman_table HTAC[HUFFMAN_TABLES];	/* 交流huffman tables */
  int default_huffman_table_initialized;
  int restart_interval;
  int restarts_to_go;				/* 剩余MCU */
  int last_rst_marker_seen;			/* Rst marker每次递增 */

  /* IDCT之后用于存储每个component的临时空间 */
  uint8_t Y[64*4], Cr[64], Cb[64];

  jmp_buf jump_state;
  /* 内部指针用于颜色空间转换，请勿修改!!! */
  uint8_t *plane[COMPONENTS];

};

打开输入输出文件，初始化jdec结构体，获得文件参数信息，主要调用tinyjpeg_parse_header()解码jpeg图像，最后调用write_yuv()*写入yuv文件。

int convert_one_image(const char *infilename, const char *outfilename, int output_format)
{ 
        
  FILE *fp;
  unsigned int length_of_file;
  unsigned int width, height;
  unsigned char *buf;
  struct jdec_private *jdec;
  unsigned char *components[3];

  /* Load the Jpeg into memory */
  fp = fopen(infilename, "rb");
  if (fp == NULL)
    exitmessage("Cannot open filename\n");
  length_of_file = filesize(fp);
  buf = (unsigned char *)malloc(length_of_file + 4);
  if (buf == NULL)
    exitmessage("Not enough memory for loading file\n");
  fread(buf, length_of_file, 1, fp);
  fclose(fp);

  /* Decompress it */
  jdec = tinyjpeg_init();
  if (jdec == NULL)
    exitmessage("Not enough memory to alloc the structure need for decompressing\n");

  if (tinyjpeg_parse_header(jdec, buf, length_of_file)<0)
    exitmessage(tinyjpeg_get_errorstring(jdec));

  /* Get the size of the image */
  tinyjpeg_get_size(jdec, &width, &height);

  snprintf(error_string, sizeof(error_string),"Decoding JPEG image...\n");
  if (tinyjpeg_decode(jdec, output_format) < 0)
    exitmessage(tinyjpeg_get_errorstring(jdec));

  /* * Get address for each plane (not only max 3 planes is supported), and * depending of the output mode, only some components will be filled * RGB: 1 plane, YUV420P: 3 planes, GREY: 1 plane */
  tinyjpeg_get_components(jdec, components);

  /* Save it */
  switch (output_format)
   { 
        
    case TINYJPEG_FMT_RGB24:
    case TINYJPEG_FMT_BGR24:
      write_tga(outfilename, output_format, width, height, components);
      break;
    case TINYJPEG_FMT_YUV420P://输出格式为yuv420
      write_yuv(outfilename, width, height, components);
      break;
    case TINYJPEG_FMT_GREY://输出格式为灰度图
      write_pgm(outfilename, width, height, components);
      break;
   }

  /* Only called this if the buffers were allocated by tinyjpeg_decode() */
  tinyjpeg_free(jdec);
  /* else called just free(jdec); */

  free(buf);
  return 0;
}

控制指针移动，解析JPEG头文件，调用parse_JFIF()

int tinyjpeg_parse_header(struct jdec_private *priv, const unsigned char *buf, unsigned int size)
{ 
        
  int ret;

  /* Identify the file */
  if ((buf[0] != 0xFF) || (buf[1] != SOI))//jpeg文件以SOI标识符为起点
    snprintf(error_string, sizeof(error_string),"Not a JPG file ?\n");

  priv->stream_begin = buf+2;//后移指针，跳过标识符
  priv->stream_length = size-2;//数据流长度（去除标识符后）
  priv->stream_end = priv->stream_begin + priv->stream_length;//定位到数据流末端

  ret = parse_JFIF(priv, priv->stream_begin);

  return ret;
}

在到达SOS之前，循环调用parse_SOF()、parse_DQT()、parse_SOS()、parse_DHT()、parse_DRI()。

static int parse_JFIF(struct jdec_private *priv, const unsigned char *stream)
{ 
        
  int chuck_len;
  int marker;
  int sos_marker_found = 0;
  int dht_marker_found = 0;
  const unsigned char *next_chunck;

  /* Parse marker */
  while (!sos_marker_found)
   { 
        
     if (*stream++ != 0xff)//获取0xFF之后的字节，确定标识符类型
       goto bogus_jpeg_format;
     /* Skip any padding ff byte (this is normal) */
     while (*stream == 0xff)
       stream++;

     marker = *stream++;
     chuck_len = be16_to_cpu(stream);
     next_chunck = stream + chuck_len;
     switch (marker)
      { 
        
       case SOF:
	 if (parse_SOF(priv, stream) < 0)
	   return -1;
	 break;
       case DQT://量化表
	 if (parse_DQT(priv, stream) < 0)
	   return -1;
	 break;
       case SOS:
	 if (parse_SOS(priv, stream) < 0)
	   return -1;
	 sos_marker_found = 1;
	 break;
       case DHT:
	 if (parse_DHT(priv, stream) < 0)
	   return -1;
	 dht_marker_found = 1;
	 break;
       case DRI:
	 if (parse_DRI(priv, stream) < 0)
	   return -1;
	 break;
       default:
#if TRACE
	fprintf(p_trace,"> Unknown marker %2.2x\n", marker);
	fflush(p_trace);
#endif
	 break;
      }

     stream = next_chunck;
   }

  if (!dht_marker_found) { 
        
#if TRACE
	  fprintf(p_trace,"No Huffman table loaded, using the default one\n");
	  fflush(p_trace);
#endif
    build_default_huffman_tables(priv);
  }

#ifdef SANITY_CHECK
  if (   (priv->component_infos[cY].Hfactor < priv->component_infos[cCb].Hfactor)
      || (priv->component_infos[cY].Hfactor < priv->component_infos[cCr].Hfactor))
    snprintf(error_string, sizeof(error_string),"Horizontal sampling factor for Y should be greater than horitontal sampling factor for Cb or Cr\n");
  if (   (priv->component_infos[cY].Vfactor < priv->component_infos[cCb].Vfactor)
      || (priv->component_infos[cY].Vfactor < priv->component_infos[cCr].Vfactor))
    snprintf(error_string, sizeof(error_string),"Vertical sampling factor for Y should be greater than vertical sampling factor for Cb or Cr\n");
  if (   (priv->component_infos[cCb].Hfactor!=1) 
      || (priv->component_infos[cCr].Hfactor!=1)
      || (priv->component_infos[cCb].Vfactor!=1)
      || (priv->component_infos[cCr].Vfactor!=1))
    snprintf(error_string, sizeof(error_string),"Sampling other than 1x1 for Cr and Cb is not supported");
#endif

  return 0;
bogus_jpeg_format:
#if TRACE
  fprintf(p_trace,"Bogus jpeg format\n");
  fflush(p_trace);
#endif
  return -1;
}

parse_SOF()、parse_DQT()、parse_SOS()、parse_DHT()、parse_DRI()分别用于解析各字段。

在此函数中，对每个块的水平和垂直采样情况进行解析，计算MCU。同时对不同MCU进行处理。