目录
一、JPEG格式解析
1.JPEG简介
JPEG 是 Joint Photographic Exports Group 的英文缩写，中文称之为联合图像专家小组。该小组隶属于 ISO 国际标准化组织，主要负责定制静态数字图像的编码方法，即所谓的 JPEG算法。
JPEG图像压缩算法能够在提供良好的压缩性能的同时，具有比较好的重建质量，被广泛应用于图像、视频处理领域，网站上80%的图像都采用了JPEG压缩标准。
2.JPEG编码流程
2.1 颜色模式转换
JPEG 采用的是 YCrCb 颜色空间，而 BMP 采用的是 RGB 颜色空间，要想对 BMP 图片进行压缩，首先需要进行颜色空间的转换。YCrCb颜色空间中，Y 代表亮度，Cr,Cb则代表色度和饱和度(也有人将 Cb,Cr 两者统称为色度)，三者通常以 Y,U,V 来表示，即用 U 代表 Cb，用 V 代表 Cr。RGB 和 YCrCb之间的转换关系如下所示：
Y = 0.299R+0.587G+0.114B
Cb = -0.1687R-0.3313G+0.5B+128
Cr = 0.5R=0.418G-0.0813B+128
转换后可以减少各分量之间的相关性，从而减少数据的冗余。
2.2 采样
人眼对亮度变换的敏感度要比对色彩变换的敏感度高出很多。因此，我们可以认为Y分量要比Cb,Cr 分量重要的多。再此我们使用4:2:0的格式。
2.3 零电平偏置下移
以中间值作为0电平，将所有电平值降低。这样可以将DCT变换后的直流系数降低，从而降低数据量。
2.4 分块
DCT 变换是对 8x8 的子块进行处理的，因此，在进行 DCT 变换之前必须把源图象数据进行分块。源图像中每点的 3个分量是交替出现的，先要把这 3 个分量分开，存放到 3 张表中去。然后由左及右，由上到下依次读取 8x8 的子块，存放在长度为 64 的表中，即可以进行 DCT 变换。
注意：如果原始图片的长宽不是 8 的倍数，都需要先补成 8 的倍数。
2.5 DCT变换
离散余弦变换(DCT for Discrete Cosine Transform)是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(DFT for Discrete Fourier Transform),但是只使用实数。在图像编码中，图像以矩阵形式存储，是一个二维数组，对图像进行二维DCT，可以将时域图像转为频域能量分布图，实现能量集中从而去除空间冗余。
JPEG 的编码过程需要进行正向离散余弦变换，而解码过程则需要反向离散余弦变换。
DCT变换前后对比
2.6 量化
残差信号经过DCT后，变换系数往往具有较大的动态范围。因此对变换系数进行量化可以有效的减小信号的取值空间，进而获得更好的压缩效果。
2.7 直流：DPCM
经过DCT变换后，DC系数数值较大且相邻分块的数值差别不大，因此使用DPCM可显著压缩数据量。
2.8 直流：Huffman编码
霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
对DPCM后的差值再进行霍夫曼编码。
2.9 交流：Zigzag 扫描排序
观察示例可以看出，在经过DCT变换后，大部分非零数值集中在矩阵的左上角区域，通过Z型读取后可以将0更多的集中在一起，方便后续的游程编码。
代码实现：
2.10 交流：游程编码 RLC（Run Length Coding）
量化之后的 AC 系数的特点是， 63 个系数中含有很多值为 0 的系数。利用该编码方式，可以将一个字符串中重复出现的连续字符用两个字节来代替，其中，第一个字节代表重复的次数，第二个字节代表被重复的字符串。
2.11 交流：霍夫曼编码
JPEG 标准具体规定了两种熵编码方式：Huffman 编码和算术编码。
JPEG 基本系统规定采用Huffman编码（因为不存在专利问题），但JPEG标准并没有限制 JPEG算法必须用 Huffman 编码方式或者算术编码方式。
3. JPEG格式解析
SOI：Start of Image 图像开始 内容为固定值FFD8
APP0：应用程序保留标记 （版本参数信息）
DQT：DCT量化表，量化表长度、量化精度、量化表ID、表项（长度为64bit(8位精度)，记录了8*8DCT变换后每个像素的量化步长，由于DC、AC、亮度、色度使用不同的量化编，所有量化表最多有4个）
SOF0： 帧图像开始，记录每一帧图像的数据长度、样本数据的位数、图像的高度、图像的宽度、颜色分量数（JFIF使用YCbCr）、颜色分量信息（分量ID（Y、U、v）、采样因子（4：4：4、4：2：2、4：2：0）、量化表ID）
DHT0（定义huffman码表）：表长度、表ID（0：亮度 1：色度）、表类型（0：直流 1：交流）不同位数的码字数量（16字节分别记录了长度为1到16的码字的个数）、权值
DC表：权值的大小直流分量数值的二进制位数，读取后经过查表查得对应的DC值。权值的字节数为DC经DPCM编码后码字个数的总和
AC表：权值的高四位表示当前数值前面有多少个0，低4为表示交流分量数值的二进制位数。
SOS扫描开始：数据长度、颜色分量数（与SOF0相同）、颜色分量信息（颜色分量ID：１ ２ ３对应Ｙ Ｕ Ｖ）、表号：（高位为直流系数使用的ｈｕｆｍａｎ表数、低位为交流系数使用的ｈｕｆｆｍａｎ表数）、压缩图像数据
EOI：End of Image， 图像结束
二、JPG解码代码解析
1. 代码架构
1.1 main()
接受输入输出文件名称参数，打开TRACEFILE。通过输入参数选择要输出的文件格式（此实验为YUV420），调用convert_one_image（）
int main(int argc, char *argv[])
{
int output_format = TINYJPEG_FMT_YUV420P;
char *output_filename, *input_filename;
clock_t start_time, finish_time;
unsigned int duration;
int current_argument;
int benchmark_mode = 0;
#if TRACE
p_trace=fopen(TRACEFILE,"w");
if (p_trace==NULL)
{
printf("trace file open error!");
}
#endif
if (argc < 3)
usage();
current_argument = 1;
while (1)
{
if (strcmp(argv[current_argument], "--benchmark")==0)
benchmark_mode = 1;
else
break;
current_argument++;
}
if (argc < current_argument+2)
usage();
input_filename = argv[current_argument];
if (strcmp(argv[current_argument+1],"yuv420p")==0)
output_format = TINYJPEG_FMT_YUV420P;
else if (strcmp(argv[current_argument+1],"rgb24")==0)
output_format = TINYJPEG_FMT_RGB24;
else if (strcmp(argv[current_argument+1],"bgr24")==0)
output_format = TINYJPEG_FMT_BGR24;
else if (strcmp(argv[current_argument+1],"grey")==0)
output_format = TINYJPEG_FMT_GREY;
else
exitmessage("Bad format: need to be one of yuv420p, rgb24, bgr24, grey\n");
output_filename = argv[current_argument+2];
start_time = clock();
if (benchmark_mode)
load_multiple_times(input_filename, output_filename, output_format);
else
convert_one_image(input_filename, output_filename, output_format);
finish_time = clock();
duration = finish_time - start_time;
snprintf(error_string, sizeof(error_string),"Decoding finished in %u ticks\n", duration);
#if TRACE
fclose(p_trace);
#endif
return 0;
}
1.2 convert_one_image()
打开输入输出文件，初始化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:
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;
}
1.3 tinyjpeg_parse_header()
控制指针移动，调用parse_JFIF()
1.4 parse_JFIF()
在到达SOS之前，循环调用parse_SOF()，parse_DQT()，parse_SOS()，parse_DHT()，parse_DRI()
1.5 parse_DQT()
解码量化表，调用*build_quantization_table()*创建量化表。
static int parse_DQT(struct jdec_private *priv, const unsigned char *stream)
{
int qi;
float *table;
const unsigned char *dqt_block_end;
#if TRACE
fprintf(p_trace,"> DQT marker\n");
fflush(p_trace);
#endif
dqt_block_end = stream + be16_to_cpu(stream);
stream += 2; /* Skip length */
while (stream < dqt_block_end)
{
qi = *stream++;
#if SANITY_CHECK
if (qi>>4)
snprintf(error_string, sizeof(error_string),"16 bits quantization table is not supported\n");
if (qi>4)
snprintf(error_string, sizeof(error_string),"No more 4 quantization table is supported (got %d)\n", qi);
#endif
table = priv->Q_tables[qi];
build_quantization_table(table, stream);
stream += 64;
}
#if TRACE
fprintf(p_trace,"< DQT marker\n");
fflush(p_trace);
#endif
return 0;
}
1.6 parse_DHT()
解析霍夫曼码表，调用 *build_huffman_table()*创建表。
static int parse_DHT(struct jdec_private *priv, const unsigned char *stream)
{
unsigned int count, i;
unsigned char huff_bits[17];
int length, index;
length = be16_to_cpu(stream) - 2;
stream += 2; /* Skip length */
#if TRACE
fprintf(p_trace,"> DHT marker (length=%d)\n", length);
fflush(p_trace);
#endif
while (length>0) {
index = *stream++;
/* We need to calculate the number of bytes 'vals' will takes */
huff_bits[0] = 0;
count = 0;
for (i=1; i<17; i++) {
huff_bits[i] = *stream++;
count += huff_bits[i];
}
#if SANITY_CHECK
if (count >= HUFFMAN_BITS_SIZE)
snprintf(error_string, sizeof(error_string),"No more than %d bytes is allowed to describe a huffman table", HUFFMAN_BITS_SIZE);
if ( (index &0xf) >= HUFFMAN_TABLES)
snprintf(error_string, sizeof(error_string),"No more than %d Huffman tables is supported (got %d)\n", HUFFMAN_TABLES, index&0xf);
#if TRACE
fprintf(p_trace,"Huffman table %s[%d] length=%d\n", (index&0xf0)?"AC":"DC", index&0xf, count);
fflush(p_trace);
#endif
#endif
if (index & 0xf0 )
build_huffman_table(huff_bits, stream, &priv->HTAC[index&0xf]);
else
build_huffman_table(huff_bits, stream, &priv->HTDC[index&0xf]);
length -= 1;
length -= 16;
length -= count;
stream += count;
}
#if TRACE
fprintf(p_trace,"< DHT marker\n");
fflush(p_trace);
#endif
return 0;
}
2.结构体解析
2.1 huffman_table
用于存储霍夫曼码表，包含快速查找表lookup，存储码字长度的表code_size，慢速表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];
};
2.2 component
存储DCT变换后的数值及指向使用的量化表与霍夫曼码表
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
};
2.3 jdec_private
是一个完整的JPEG码流块的定义，其中也包含了components和huffman_table的结构体。
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];
};
2.TRACE
条件编译是指预处理器根据条件编译指令，有条件地选择源程序代码中的一部分代码作为输出，送给编译器进行编译。主要是为了有选择性地执行相应操作，防止宏替换内容（如文件等）的重复包含。
在本实验中，TRACE就使用了条件编译。
#define TRACE 1//add by nxn
定义TRACE为1
#if TRACE
p_trace=fopen(TRACEFILE,"w");
if (p_trace==NULL)
{
printf("trace file open error!");
}
#endif
在例如此处的地方，通过#if #endif的语句，更改宏定义TRACE值即可控制是否编写TRACE文件了。
常用的条件编译指令：
三、实验结果
1.输出YUV图像
输出图像的代码在函数*write_yuv()*中，简单的改写即可输出YUV图像。
static void write_yuv(const char *filename, int width, int height, unsigned char **components)
{
FILE *F;
char temp[1024];
//Y,U,V
//snprintf(temp, 1024, "%s.Y", filename);
//F = fopen(temp, "wb");
//fwrite(components[0], width, height, F);
//fclose(F);
//snprintf(temp, 1024, "%s.U", filename);
//F = fopen(temp, "wb");
//fwrite(components[1], width*height/4, 1, F);
//fclose(F);
//snprintf(temp, 1024, "%s.V", filename);
//F = fopen(temp, "wb");
//fwrite(components[2], width*height/4, 1, F);
//YUV
snprintf(temp, 1024, "%s.YUV", filename);
F = fopen(temp, "wb");
fwrite(components[0], width, height, F);
fwrite(components[1], width * height / 4, 1, F);
fwrite(components[2], width * height / 4, 1, F);
fclose(F);
}
输出图像：
分辨率为1024*1024较高，这里就不显示完整图像了。
2. 输出量化矩阵
量化表的代码在函数*build_quantization_table()*中，需添加代码输出
static void build_quantization_table(float *qtable, const unsigned char *ref_table)
{
int i, j;
static const double aanscalefactor[8] = {
1.0, 1.387039845, 1.306562965, 1.175875602,
1.0, 0.785694958, 0.541196100, 0.275899379
};
const unsigned char *zz = zigzag;
for (i=0; i<8; i++) {
for (j=0; j<8; j++) {
*qtable++ = ref_table[*zz++] * aanscalefactor[i] * aanscalefactor[j];
}
}
//输出量化表
#if TRACE
const unsigned char* zz1 = zigzag;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
fprintf(p_trace, "%-6d", ref_table[*zz1++]);
if (j == 7) {
fprintf(p_trace, "\n");
}
}
}
#endif
}
结果：
3. 输出HUFFMAN码表
输出霍夫曼码表的代码已在函数*build_huffman_table()*中写好，直接调用即可。
static void build_huffman_table(const unsigned char *bits, const unsigned char *vals, struct huffman_table *table)
{
unsigned int i, j, code, code_size, val, nbits;
unsigned char huffsize[HUFFMAN_BITS_SIZE+1], *hz;
unsigned int huffcode[HUFFMAN_BITS_SIZE+1], *hc;
int next_free_entry;
/*
* Build a temp array
* huffsize[X] => numbers of bits to write vals[X]
*/
hz = huffsize;
for (i=1; i<=16; i++)
{
for (j=1; j<=bits[i]; j++)
*hz++ = i;
}
*hz = 0;
memset(table->lookup, 0xff, sizeof(table->lookup));
for (i=0; i<(16-HUFFMAN_HASH_NBITS); i++)
table->slowtable[i][0] = 0;
/* Build a temp array
* huffcode[X] => code used to write vals[X]
*/
code = 0;
hc = huffcode;
hz = huffsize;
nbits = *hz;
while (*hz)
{
while (*hz == nbits)
{
*hc++ = code++;
hz++;
}
code <<= 1;
nbits++;
}
/*
* Build the lookup table, and the slowtable if needed.
*/
next_free_entry = -1;
for (i=0; huffsize[i]; i++)
{
val = vals[i];
code = huffcode[i];
code_size = huffsize[i];
#if TRACE
fprintf(p_trace,"val=%2.2x code=%8.8x codesize=%2.2d\n", val, code, code_size);
fflush(p_trace);
#endif
table->code_size[val] = code_size;
if (code_size <= HUFFMAN_HASH_NBITS)
{
/*
* Good: val can be put in the lookup table, so fill all value of this
* column with value val
*/
int repeat = 1UL<<(HUFFMAN_HASH_NBITS - code_size);
code <<= HUFFMAN_HASH_NBITS - code_size;
while ( repeat-- )
table->lookup[code++] = val;
}
else
{
/* Perhaps sorting the array will be an optimization */
uint16_t *slowtable = table->slowtable[code_size-HUFFMAN_HASH_NBITS-1];
while(slowtable[0])
slowtable+=2;
slowtable[0] = code;
slowtable[1] = val;
slowtable[2] = 0;
/* TODO: NEED TO CHECK FOR AN OVERFLOW OF THE TABLE */
}
}
}
结果：