一、實驗目的

1. 掌握JPEG編解碼系統的基本原理，
2. 初步掌握復雜的資料壓縮演算法實作，并能根據理論分析需要實作所對應資料的輸出，

二、實驗內容

1、JPEG編解碼原理

JPEG編碼程序如上圖所示，解碼是編碼的逆程序，下面以編碼為例進行分析，

（1）零偏置電平下移

• 操作：先對8×8的像塊進行零偏置電平下移（Level Offset），即對于灰度級是2ⁿ的像素，通過減去 2^n-1，將無符號的整數值變成有符號數，
• 目的： 使像素的絕對值出現 3 位 10 進制的概率大大減少，
• 對于n=8，即將0～255的值域，通過減去128轉換為值域在-128～127之間的值

（2）8x8 DCT

• 將原始影像分為8x8的小塊, 每個block里有64個像素，
• 將影像塊作為2維離散余弦變換DCT的輸入，最后得到DCT變換的輸出，如圖所示：
  

（3）量化

• 因為人眼對亮度信號比對色差信號更敏感，因此使用了兩種量化表：亮度量化值和色差量化值，
• 根據人眼的視覺特性（對低頻敏感，對高頻不太敏感）對低頻分量采取較細的量化，對高頻分量采取較粗的量化，
• 如果原始圖象中細節豐富，則去掉的資料較多，量化后的系數與量化前差別較大，反之，細節少的原始圖象在壓縮時去掉的資料少些，量化后的系數與量化前差別較小，

（4）直流DC系數的DPCM編碼

由于8×8影像塊經過DCT變換之后得到的DC直流系數有兩個特點：

• 系數的數值比較大
• 相鄰 8 × 8 影像塊的 DC 系數值變化不大：冗余

根據這個特點，JPEG演算法使用了差分脈沖調制編碼（DPCM）技術，對相鄰影像塊之間量化DC系數的差值DIFF進行編碼：
D I F F k = D C k ? D C k ? 1 DIFF_k=DC_k-DC_{k-1} DIFFk?=DCk??DCk?1?

（5）AC系數的Z字掃描

• 由于經DCT變換后，系數大多數集中在左上角，即低頻分量區，因此采用Z字形按頻率的高低順序讀出，可以出現很多連零的機會，可以使用游程編碼，尤其在最后，如果都是零，給出EOB (End of Block)即可，
• 然后，系數序列分組，將非零系數和它前面的相鄰的全部零系數分在一組內；每組用兩個符號表示 [(Run, Size), (Amplitude)]

Amplitude：表示非零系數的幅度值；
Run：表示零的游程即零的個數；
Size：表示非零系數的幅度值的編碼位數，

（6）Huffman編碼

①DC系數的Huffman編碼

• 對DIFF用Huffman編碼：分成類別，類似指數Golomb編碼，
  類別ID：一元碼編碼
  類內索引：采用定長碼
  
• DC系數Huffman編碼舉例：
  

②AC系數的Huffman編碼

• 在JPEG和MPEG編碼種規定：（run, level）表示連續run個0，后面跟值為level的系數，
• 編碼時，run最大為15，用4位表示RRRR；level編碼類似DC，分成16個類別，用4位表示，SSSS表示類別號，再加上類內索引進行編碼，對（RRRR,SSSS）聯合用Huffman編碼；對類內索引采用定長編碼，
• AC系數Huffman編碼舉例：

2、JPEG檔案格式

（1）Segment的組織形式

JPEG在檔案中以Segment的形式組織 ，它具有以下特點：

• 均以0xFF開始，后跟1byte的Marker和2byte的Segment length（包含表示Length本身所占用的2byte，不含0xFF+Marker所占用的2byte）；
• 采用 Motorola序（相對于Intel序），即保存時高位在前，低位在后；
• Data部分中，0xFF后若為0x00，則跳過此位元組不予處理，

（2）JPEG的Segment Market

三、實驗步驟

0、程式準備

遵循程式要求，在除錯屬性內設定好命令引數，

• 第一個引數為要解碼的jpg檔案；
• 第二個引數為功能選項，此處選擇yuv420p，即轉換為yuv420格式的檔案；
• 第三個引數為輸出檔案，

1、運行JPEG解碼程式，并輸出可供YUVviewer觀看的YUV檔案

觀察除錯解碼程式發現，Y、U、V分量輸出程序在如下所示的函式內，在//輸出yuv檔案后增加一段程式輸出YUV檔案，再次運行程式，

/**
 * Save a buffer in three files (.Y, .U, .V) useable by yuvsplittoppm
 */
static void write_yuv(const char* filename, int width, int height, unsigned char** components)
{
	FILE* F;
	char temp[1024];
	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);
	fclose(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);
}

運行完成后在根目錄中得到：

用YUVviewer觀看：

2、程式除錯程序的理解

（1）理解程式設計的整體框架

（2）理解三個結構體的設計目的

①struct huffman_table

用來存盤Huffman碼表，

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];
};

②struct component

儲存當前8×8塊中有關解碼的資訊，

struct component 
{
  unsigned int Hfactor; //水平采樣因子
  unsigned int Vfactor; //垂直采樣因子
  float *Q_table;		//8x8塊使用的量化表
  struct huffman_table *AC_table; //AC Huffman表
  struct huffman_table *DC_table; //DC Huffman表
  short int previous_DC;	//前一個塊的直流DCT系數
  short int DCT[64];		//DCT系數
#if SANITY_CHECK
  unsigned int cid;
#endif
};

③struct jdec_private

JPEG資料流結構體，

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];

};

（3）理解在視音頻編解碼除錯中TRACE的目的和含義

TRACE為活動前處理器塊，用來協助程式的除錯，在本程式的頭檔案tinyjpeg.h中將TRACE設為1，表示程式正常除錯運行，若想關閉，可設為0，

#define TRACE 1//add by nxn

3、輸出量化矩陣和Huffman碼表

在頭檔案tinyjpeg.h中宣告要輸出的檔案：

FILE* qfile;//量化矩陣txt檔案
FILE* hfile;//Huffman碼表txt檔案

（1）量化矩陣

1. 在創建量化矩陣的函式build_quantization_table()中添加量化矩陣輸出代碼；

	//輸出所有量化矩陣
	qfile = fopen("quan.txt", "a");
	for (i = 0; i < 8; i++) {
		for (j = 0; j < 8; j++) {
			fprintf(qfile, "%d\t", ref_table[*zz]);
			*qtable++ = ref_table[*zz++] * aanscalefactor[i] * aanscalefactor[j];
		}
		fprintf(qfile, "\n");
	}

2. 在運用此函式的地方，即量化表決議函式parse_DQT()中添加代碼進行量化矩陣檔案的更新寫入，

#if TRACE
	fprintf(p_trace, "< DQT marker\n");
	fflush(p_trace);
	//更新列印量化矩陣
	fprintf(qfile, "DQT ID: %d\n", qi);
	fflush(qfile);
#endif

（2）Huffman碼表

1. 在Huffman碼表創建的地方即函式build_huffman_table()內添加代碼列印輸出Huffman碼表，

if TRACE
		fprintf(p_trace, "val=%2.2x code=%8.8x codesize=%2.2d\n", val, code, code_size);
		fflush(p_trace);
		fprintf(hfile, "val=%2.2x code=%8.8x codesize=%2.2d\n", val, code, code_size);
		fflush(hfile);
#endif

2. 在Huffman碼表決議的地方，即函式parse_DHT()中添加代碼實作輸出Huffman碼表的分類（DC或AC及序號），

//輸出huffman碼表
	hfile = fopen("huff.txt", "a");
	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);
		fprintf(hfile, "Huffman table %s[%d] length=%d\n", (index & 0xf0) ? "AC" : "DC", index & 0xf, count);
		fflush(hfile);

（3）輸出結果

量化矩陣（0為DC，1為AC）：

Huffman碼表（展示部分）：

四、實驗結論

通過本次實驗：

1. 掌握了JPEG編解碼系統的基本原理，
2. 成功除錯了復雜的資料壓縮演算法實作的代碼，
3. 最后根據代碼理解進行了一定的修改，實作了實驗要求的資料輸出，