数据压缩实验之 JPEG原理分析及JPEG解码器的调试

文章目录

1.实验名称

JPEG原理分析及JPEG解码器的调试

2.实验目的

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

3.主要设备

安装Windows和Visual Studio软件的个人计算机

4.实验内容

4.1 JPEG文件格式

依次 文件格式 标记代码 具体字段
SOI(图像开始) 0xFFD8 -----------------------------------
APP0(应用程序保留标记0) 0xFFE0 数据压缩实验之 JPEG原理分析及JPEG解码器的调试
DQT(定义量化表) 0xFFDB 数据压缩实验之 JPEG原理分析及JPEG解码器的调试
SOF0(帧图像开始) 0xFFC0 数据压缩实验之 JPEG原理分析及JPEG解码器的调试
DHT(定义哈夫曼表) 0xFFC4 数据压缩实验之 JPEG原理分析及JPEG解码器的调试
SOS(扫描开始) 0xFFDA 数据压缩实验之 JPEG原理分析及JPEG解码器的调试
EOI(图像结束 2字节) 0xFFD9 -------------------------------------

根据上表,用FlexHEX打开一张JPG格式的图片,并用红笔标注出每个标记代码:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
依次验证每一字段,发现的确如此。

4.2 JPEG编解码原理

4.2.1 编码流程

数据压缩实验之 JPEG原理分析及JPEG解码器的调试
①零偏置
目的:保证输入图像的采样有近似地集中在零附近的动态范围。
实现方法:对于灰度级是 2 n 2^n 2n的像素,通过减去 2 n − 1 2^{n-1} 2n−1,将无符号的整数值变成有符号数.

② 8 ∗ 8 8*8 8∗8 DCT变换
目的:实现能量集中和去相关,便于去除空间冗余,以达到压缩图像数据的目的。
实现方法:首先对图像进行 8 ∗ 8 8*8 8∗8的分块(若图像的宽高不是8的倍数,可对图像进行补0,补至8的倍数),之后进行DCT(离散余弦变换)变换,经DCT变换后, 8 ∗ 8 8*8 8∗8的图像块将变为 8 ∗ 8 8*8 8∗8的DCT系数块。
DCT变换计算公式:数据压缩实验之 JPEG原理分析及JPEG解码器的调试
其中
数据压缩实验之 JPEG原理分析及JPEG解码器的调试

③量化
利用人眼对高频细节不甚敏感的特性,对高频的AC分量进行粗量化,对低频的DC分量进行细量化。
利用人眼对色度细节不甚敏感的特性:对色度分量进行粗量化,对亮度分量进行细量化。

JPEG算法提供了两张标准的量化系数矩阵:
标准亮度量化表
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
标准色差量化表
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
④编码
对DC系数:差分编码
由于直流系数 F(0,0)反映了该子图像中包含的直流成分,通常较大,又由于两个相邻的子图像的直流系数通常具有较大的相关性,所以对 DC 系数采用差值脉冲编码(DPCM),即对本像素块直流系数与前一像素块直流系数的差值进行无损编码。

对AC系数:游程编码
首先对AC系数的之字形扫描
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
出现很多连零,使用游程编码。最后如果都是零,给出EOB (End of Block)即可。

⑤Huffman编码

Huffman编码几乎是所有压缩算法的基础,它的基本原理是根据数据中元素的使用频率,调整元素的编码长度,以得到更高的压缩比。JPEG *采用了四张 Huffman 码表:亮度 DC、亮度 AC、色度 DC、色度 AC,即分别对图像的亮度和色度,直流和交流数据进行编码处理。

JPEG建立Huffman表的方法:

第一个码字必定为0.
如果第一个码字位数为1,则码字为0
如果第一个码字位数为2,则码字为00
以此类推
从第二个码字开始:
如果它和它前面的码字位数相同,则当前码字为它前面的码字加1;
如果它的位数比它前面的码字位数大,则当前码字是前面的码字加1后再在后边添若干个0,直至满足位数长度为止。
直流系数权值就是解码时再需要读入的bit位数。
交流系数权值的高4位表示当前数值前面有多少个连续的零,低4位表示该交流分量数值的二进制位数,也就是接下来需要读入的位数。

4.2.2 解码流程

数据压缩实验之 JPEG原理分析及JPEG解码器的调试

5.实验步骤

5.1 逐步调试JPEG解码器程序

5.1.1 理解程序设计的整体框架

1.读取文件
在主函数main函数中,打开输入输出文件,并解析了输出格式:

int main(int argc, char *argv[])

整个JPEG解码过程,由下面的covert_one函数实现:

int convert_one_image(const char *infilename, const char *outfilename, int output_format)

2.解析 Segment Marker(tinyjpeg_parse_header中)
解析文件头:

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

解析DQT:

static int parse_DQT(struct jdec_private *priv, const unsigned char *stream)

解析SOF:

static int parse_SOF(struct jdec_private *priv, const unsigned char *stream)//基线余弦变换

解析DHT:

static int parse_DHT(struct jdec_private *priv, const unsigned char *stream)//解析Huffman码表

建立量化表:

static void build_quantization_table(float *qtable, const unsigned char *ref_table)

重建 Huffman 表 :

static void build_huffman_table(const unsigned char *bits, const unsigned char *vals, struct huffman_table *table)//创建码表

解析SOS:

static int parse_SOS(struct jdec_private *priv, const unsigned char *stream)

3.依据每个分量的水平、垂直采样因子计算 MCU 的大小,得到每个 MCU 中 8 ∗ 8 8*8 8∗8宏块个数
4.对每个 MCU 解码(依照各分量水平、垂直采样因子对 MCU 中每个分量宏块解码)

static void decode_MCU_1x1_3planes(struct jdec_private *priv)
static void decode_MCU_1x1_1plane(struct jdec_private *priv)//采样格式为1:1:1
static void decode_MCU_2x1_3planes(struct jdec_private *priv)

等类似的函数。
对一个 8 ∗ 8 8*8 8∗8的彩色分量单元进行解码:
5.解完所有 MCU,解码结束

5.1.2 理解三个结构体的设计目的

jdec_private结构体: 通过阅读代码注释,可发现该结构体指示了解码过程中的码流参数(开始、结束位置,持续时间),量化表,霍夫曼码表以及图像数据(宽高比),y、u、v分量,最小单元MUC和中间变量等。

struct jdec_private
{
  /* Public variables */
  uint8_t *components[COMPONENTS];
  unsigned int width, height;	/* Size of the image */
  unsigned int flags;

  /* Private variables */
  const unsigned char *stream_begin, *stream_end;
  unsigned int stream_length;

  const unsigned char *stream;	/* Pointer to the current stream */
  unsigned int reservoir, nbits_in_reservoir;

  struct component component_infos[COMPONENTS];
  float Q_tables[COMPONENTS][64];		/* quantization tables */
  struct huffman_table HTDC[HUFFMAN_TABLES];	/* DC huffman tables   */
  struct huffman_table HTAC[HUFFMAN_TABLES];	/* AC huffman tables   */
  int default_huffman_table_initialized;
  int restart_interval;
  int restarts_to_go;				/* MCUs left in this restart interval */
  int last_rst_marker_seen;			/* Rst marker is incremented each time */

  /* Temp space used after the IDCT to store each components */
  uint8_t Y[64*4], Cr[64], Cb[64];

  jmp_buf jump_state;
  /* Internal Pointer use for colorspace conversion, do not modify it !!! */
  uint8_t *plane[COMPONENTS];

};

struct component 结构体: 由代码可知,Hfactor和 Vfactor 用于说明水平与垂直的采样情况, Q_table指向该component所对应的量化表; AC_tableDC_table用于指向对DC分量与AC分量进行霍夫曼解码时所需的码表;previous_DC是用于保存前一个块的DC值,用于DPCM解码;**DCT[64]**则是相应一个块的DCT系数矩阵,故用于参与霍夫曼解码,反量化,IDCT 以及彩色空间变换

struct component 
{
  unsigned int Hfactor;
  unsigned int Vfactor;
  float *Q_table;		/* Pointer to the quantisation table to use */
  struct huffman_table *AC_table;
  struct huffman_table *DC_table;
  short int previous_DC;	/* Previous DC coefficient */
  short int DCT[64];		/* DCT coef */
#if SANITY_CHECK
  unsigned int cid;
#endif
};

struct huffman_table结构体: 该结构体创建一个查找表用于解码,若码长大于9,则由slowtable处理。

struct huffman_table
{
  /* Fast look up table, using HUFFMAN_HASH_NBITS bits we can have directly the symbol,
   * if the symbol is <0, then we need to look into the tree table */
  short int lookup[HUFFMAN_HASH_SIZE];
  /* code size: give the number of bits of a symbol is encoded */
  unsigned char code_size[HUFFMAN_HASH_SIZE];
  /* some place to store value that is not encoded in the lookup table 
   * FIXME: Calculate if 256 value is enough to store all values
   */
  uint16_t slowtable[16-HUFFMAN_HASH_NBITS][256];
};

5.1.3 理解在视音频编解码调试中TRACE的目的和含义

TRACE的目的:随着文件的解析,输出中间过程中的某些变量,或者错误信息到txt文件。
在tinyjpeg.h中,令TRACE=1,即打开TRACE,令TRACE=0,即关闭TRACE。

#define TRACE 1

Trace打开的时候,就可以进行上述说明的信息的输出,Trace关闭的话,就是直接跳过这些代码的编译,不进行上说说明信息的输出。
在代码中寻找到以下格式的段便可编辑TRACE:

#if TRACE
.............
..............

#endif

5.2 改写程序,将输出文件保存为可供YUVViewer观看的YUV文件

write_yuv函数里添加这一段:

  snprintf(temp, 1024, "%s.yuv", filename);//add by chencheng
  fopen_s(&F, temp, "wb");
  fwrite(components[0], width, height, F);
  fwrite(components[1], width * height / 4, 1, F);
  fwrite(components[2], width * height / 4, 1, F);

结果:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
打开output.yuv图像:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试

5.3 改写程序,以txt文件输出所有的量化矩阵和所有的HUFFMAN码表

输出所有的量化矩阵添加的关键代码如下:

  quantity_table = fopen(QUANTITYFILE, "w+");
  if (quantity_table==NULL)
  {
      printf("quantity table file open error!");
  }
  huffman_table = fopen(HUFFMANFILE, "w+");
#if TRACE
  fprintf(p_trace,"< DQT marker\n");
  PrintQtable(table, qi);
  fflush(p_trace);
#endif
static void PrintQtable(float* qtable, int qi)
{
    fprintf(quantity_table, "Qtable[%d]  is:\n", qi);
    int i, j;
    for (i = 0; i < 8; i++)
    {
        for (j = 0; j < 8; j++)
        {
            if (j == 7)
            {
                fprintf(quantity_table, "%10.3f\n", qtable[i * 8 + j]);
            }
            else
            {
                fprintf(quantity_table, "%10.3f\t", qtable[i * 8 + j]);
            }
        }
    }
}

结果:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
输出所有的HUFFMAN码表添加的关键代码:

  if (huffman_table == NULL)
  {
      printf("huffman table file open error!");
  }
fprintf(huffman_table, "val=%2.2x code=%8.8x codesize=%2.2d\n", val, code, code_size);
 fprintf(huffman_table, "Huffman table %s[%d] length=%d\n", (index & 0xf0) ? "AC" : "DC", index & 0xf, count);

结果:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试

数据压缩实验之 JPEG原理分析及JPEG解码器的调试

5.4 改写程序,输出DC图像、某一个AC值图像并分别统计它们的概率分布

tinyjpeg_decode中修改:

  //打开AC、DC文件
  FILE *DCFile = fopen("DC.yuv", "wb");
  FILE *ACFile = fopen("AC.yuv", "wb");
  if (DCFile == NULL)
  {
	  printf("Fail to open DC\n");
	  return 0;
  }
  if (ACFile == NULL)
  {
	  printf("Fail to open AC\n");
	  return 0;
  }
  unsigned char acy = 0;
  unsigned char dcy = 0;
  
  if (setjmp(priv->jump_state))
    return -1;
		 dcy = (unsigned char)((priv->component_infos->DCT[0] + 512) / 4 + 0.5 );
		 fwrite(&dcy, 1, 1, DCFile);
		 acy = (unsigned char)(priv->component_infos->DCT[1] + 128);
		 fwrite(&acy, 1, 1, ACFile);
		 for (int i = 0; i < 256; i++)
		 {
			 if (dcy == i)
				 dcfreq[i]++;
			 if (acy == i)
				 acfreq[i]++;
		 }
       }
     }
  for (int i = 0; i < 256; i++)
  {
	  dcfreq[i] = dcfreq[i] / (priv->width*priv->height / 64);
	  acfreq[i] = acfreq[i] / (priv->width*priv->height / 64);
  }
  //输出概率分布
  FILE *ACfre = fopen("AC频率.txt", "wb");
  if (ACfre == 0)
  {
	  printf("Fail to open AC频率\n");
	  return 0;
  }
  
  fprintf(ACfre, "数值\t概率\n");
  for (int i = 0; i < 256; i++)
  {
	  fprintf(ACfre, "%d\t%f\n", i, acfreq[i]);
  }

  FILE *DCfre = fopen("DC频率.txt", "wb");
  if (DCfre == 0)
  {
	  printf("Fail to open DC频率\n");
	  return 0;
  }
  fprintf(DCfre, "数值\t概率\n");
  for (int i = 0; i < 256; i++)
  {
	  fprintf(DCfre, "%d\t%f\n", i, dcfreq[i]);
  }

 unsigned char uv = 128;
  for (int i = 0; i < priv->width*priv->height / 32; i++)
  {
	  fwrite(&uv, 1, 1, ACFile);
	  fwrite(&uv, 1, 1, DCFile);
  }

结果:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
打开DC.yuv图像
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
使用MATLAB绘制DC图像的概率分布:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试

数据压缩实验之 JPEG原理分析及JPEG解码器的调试
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
打开AC.yuv图像:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试
由DC、AC图像可以看出,DC图像基本保留了原图的细节。
使用MATLAB绘制某一AC值图像的概率分布:
数据压缩实验之 JPEG原理分析及JPEG解码器的调试

上一篇:Vulnhub入门实战1-DC:1


下一篇:二值变量间的相关性分析补充