最近在看圖像的壓縮，就想著先實現(xiàn)一個jpeg文件的解碼。本來以為這種資料在網(wǎng)上會一搜一大堆，但搜了之后才發(fā)現(xiàn)很多網(wǎng)上的資料要么不夠全面在一些關鍵的地方模糊不清，要么就是在一些細枝末節(jié)的地方有些許錯誤。導致我在這些地方走了不少彎路，為了使后來之人少走這些許彎路，特寫此文記錄一下。下面這個項目中包含有C語言實現(xiàn)的jpeg解碼，可供大家參考：

• https://github.com/neoql/image

JPEG簡介

JPEG（Joint Photographic Experts Group）是聯(lián)合圖像專家小組的英文縮寫。它由國際電話與電報咨詢委員會CCITT（The International Telegraph and Telephone Consultative Committee）與國際標準化組織ISO于1986年聯(lián)合成立的一個小組，負責制定靜態(tài)數(shù)字圖像的編碼標準。

小組一直致力于標準化工作，開發(fā)研制出連續(xù)色調、多級灰度、靜止圖像的數(shù)字圖像壓縮編碼方法，即JPEG算法。JPEG算法被確定為國際通用標準，其適用范圍廣泛，除用于靜態(tài)圖像編碼外，還推廣到電視圖像序列的幀內圖像壓縮。而用JPEG算法壓縮出來的靜態(tài)圖片文件稱為JPEG文件，擴展名通常為.jpg、.jpe*.jpeg。

JPEG專家組開發(fā)了兩種基本的壓縮算法、兩種數(shù)據(jù)編碼方法、四種編碼模式。具體如下：

壓縮算法：

• 有損的離散余弦變換（Discrete Cosine Transform，DCT）
• 無損的預測技術壓縮

數(shù)據(jù)編碼方法：

• 哈夫曼編碼
• 算術編碼

編碼模式：

• 基于DCT順序模式：編/解碼通過一次掃描完成
• 基于DCT遞進模式：編/解碼需要多次掃描完成，掃描效果從粗糙到精細，逐級遞進
• 無損模式：基于DPCM，保證解碼后完全精確恢復到原圖像采樣值
• 層次模式：圖像在多個空間多種分辨率進行編碼，可以根據(jù)需要只對低分辨率數(shù)據(jù)作解碼，放棄高分辨率信息

一般情況下，JPEG圖像使用離散余弦變換、哈夫曼編碼、順序模式。

JPEG文件結構分析

JPEG文件使用的數(shù)據(jù)存儲方式有多種。最常用的格式稱為JPEG文件交換格式（JPEG File Interchange Format，JFIF）。而JPEG文件大體上可以分成兩個部分：標記碼(Tag)和壓縮數(shù)據(jù)。

標記碼由兩個字節(jié)構成，其前一個字節(jié)是固定值0xFF，后一個字節(jié)則根據(jù)不同意義有不同數(shù)值。在每個標記碼之前還可以添加數(shù)目不限的無意義的0xFF填充，也就說連續(xù)的多個0xFF可以被理解為一個0xFF，并表示一個標記碼的開始。而在一個完整的兩字節(jié)的標記碼后，就是該標記碼對應的壓縮數(shù)據(jù)流，記錄了關于文件的諸種信息。

常用的標記有SOI、APP0、DQT、SOF0、DHT、DRI、SOS、EOI。

注意，SOI等都是標記的名稱。在文件中，標記碼是以標記代碼形式出現(xiàn)。例如SOI的標記代碼為0xFFD8，即在JPEG文件中的如果出現(xiàn)數(shù)據(jù)0xFFD8，則表示此處為一個SOI標記。

以下是常用標記的標記代碼和表示的意義：

其他資料里還有一些常用標記如APPn、DRI、RSTn，不過我在實際應用中并沒有碰到過這些標記，在此就不過多的介紹了，如果想要了解可以查看此文。

下面將介紹常用標記的具體內容。

SOI ( Start of Image )

圖像開始

APP0 ( Application 0 )

應用程序保留標記0

本標記段可以包含圖像的一個微縮版本，存為24位的RGB像素。如果沒有微縮圖像（這種情況更常見），則字段⑦“縮略圖水平像素數(shù)目”和字段⑧“縮略圖垂直像素數(shù)目”的值均為0。

DQT ( Define Quantization Table )

定義量化表

其中字段②的內容為：

本標記段中，字段②中包含的內容可以循環(huán)出現(xiàn)，表示多個量化表，但最多只能出現(xiàn)4次。

SOF0 ( Start of Frame )

幀圖像開始

字段⑥中包含這些字段：

字段⑥中的內容會重復出現(xiàn)，有多少個顏色分量（字段⑤）就出現(xiàn)多少次（一般為3次）。

DHT ( Difine Huffman Table )

定義哈夫曼表

字段②包含下列字段：

此標記段中，字段②中的內容可以循環(huán)出現(xiàn)（一般為4次），也可以出現(xiàn)4次。例如，Adobe Photoshop 生成的JPEG圖片文件中只有1個DHT標記段，里邊包含了4個哈夫曼表；而Macromedia Fireworks生成的JPEG圖片文件則有4個DHT標記段，每個DHT標記段只有一個哈夫曼表。

這個標記段中的哈夫曼表為范氏哈夫曼表在下文中會有介紹。

SOS ( Start of Scan )

掃描開始

表a：

表b：

本標記段中，字段③應該重復出現(xiàn)，有多少個顏色分量，就出現(xiàn)多少次（一般為3次）。本段結束后就是真正的圖像信息了。圖像信息直至遇到一個標記代碼就自動結束，一般就是以EOI標記表示結束。

EOI ( End of Image )

圖像結束

由于在JPEG文件中0xFF具有標志性的意思，所以在壓縮數(shù)據(jù)流(真正的圖像信息)中出現(xiàn)0xFF，就需要作特別處理。具體方法是，在數(shù)據(jù)0xFF后添加一個沒有意義的0x00。所以在讀取圖像信息時如果遇到0xFF00其實際意義為0xFF。

JPEG解碼過程

解碼流程如下

系數(shù)解碼->差分解碼->反量化->反Zig-Zag->隔行正負糾正->IDCT->圖像拼接

讀入文件

JPEG文件格式一般為

• SOI(0xFFD8)
• APP0(0xFFE0)
• DQT(0xFFDB)
• SOF0(0xFFC0)
• DHT(0xFFC4)
• SOS(0xFFDA)
• 壓縮后的圖像數(shù)據(jù)
• EOI(0xFFD9)

備注：JPEG文件在存儲16位整型數(shù)據(jù)時使用的是大端字節(jié)序，而不是常用的小端字節(jié)序。如果不清楚什么是大小端字節(jié)序可以查看這篇大端序與小端序。

范氏哈夫曼編碼

哈夫曼編碼是一種最優(yōu)的前綴編碼技術，然而其存在的不足卻制約了它的直接應用。首先，其解碼時間為O(lavg), 其中l(wèi)avg為碼字的平均長度；其次，更為最重要的是，解碼器需要知道哈夫曼編碼樹的結構，因而編碼器必須為解碼器保存或傳輸哈夫曼編碼樹。對于小量數(shù)據(jù)的壓縮而言，這是很大的開銷。因而，應用哈夫曼編碼的關鍵是如何降低哈夫曼編碼樹的存儲空間。

范式哈夫曼編碼最早由Schwartz[1964]提出，它是哈夫曼編碼的一個子集。其中心思想是：使用某些強制的約定，僅通過很少的數(shù)據(jù)便能重構出哈夫曼編碼樹的結構。其中一種很重要的約定是數(shù)字序列屬性(numerical sequence property)，它要求相同長度的碼字是連續(xù)整數(shù)的二進制描述。例如，假設碼字長度為4的最小值為0010，那么其它長度為4的碼字必為0011, 0100, 0101, ...；另一個約定：為了盡可能的利用編碼空間，長度為i第一個碼字f(i)能從長度為i-1的最后一個碼字得出, 即: f(i) = 2(f(i-1)+1)。假定長度為4的最后一個碼字為1001，那么長度為5的第一個碼字便為10100。最后一個約定：碼字長度最小的第一個編碼從0開始。通過上述約定，解碼器能根據(jù)每個碼字的長度恢復出整棵哈夫曼編碼樹的結構。

JPEG文件的哈夫曼表存儲在DHT標記段中。在標記段DHT內，包含了一個或者多個的哈夫曼表。對于單一個哈夫曼表，應該包括了三部分：

• 哈夫曼表ID和表類型

  這個字節(jié)的值為一般只有四個0x00、0x01、0x10、0x11。

  0x00表示DC直流0號表

  0x01表示DC直流1號表

  0x10表示AC交流0號表

  0x11表示AC交流1號表

• 不同位數(shù)的碼字數(shù)量

  JPEG文件的哈夫曼編碼只能是1_{16位。這個字段的16個字節(jié)分別表示1}16位的編碼碼字在哈夫曼樹中的個數(shù)。

• 編碼內容

  這個字段記錄了哈夫曼樹中各個葉子結點的權。所以，上一字段（不同位數(shù)的碼字數(shù)量）的16個數(shù)值之和就應該是本字段的長度，也就是哈夫曼樹中葉子結點個數(shù)。

下面用一段哈夫曼表數(shù)據(jù)舉例說明（數(shù)據(jù)全部以16進制表示）：

紅色部分(第1字節(jié)): 為哈夫曼表ID和表類型，其值0x11表示此部分數(shù)據(jù)描述的是AC交流1號表。

藍色部分(2~17字節(jié)): 為不同位數(shù)的碼字的數(shù)量。這16個數(shù)值實際意義為：沒有1位和4位的哈夫曼碼字；2位和3位的碼字各有2個；5位碼字有5個；6位和8位碼字各有1個；7位碼字各有6個；沒有9位或以上的碼字。

綠色部分(18~34字節(jié)): 為編碼內容。由藍色部分數(shù)據(jù)知道，此哈夫曼樹有0+2+2+0+5+1+6+1=17個葉子結點，即本字段應該有17個字節(jié)。這段數(shù)據(jù)表示17個葉子結點按從小到大排列，其每每個節(jié)點所代表的值依次為0、1、11、2、21、3、31、41……

在讀出讀出哈夫曼表的數(shù)據(jù)后，就要建立哈夫曼樹，具體方法為：

1. 第一個碼字必定為0。

   如果第一個碼字位數(shù)為1，則碼字為0。

   如果第一個碼字位數(shù)為2，則碼字為00。

   如此類推。

2. 從第二個碼字開始

   如果它和它前面的碼字位數(shù)相同，則當前碼字為它前面的碼字加1。

   如果它的位數(shù)比它前面的碼字位數(shù)大，則當前碼字是前面的碼字加1后再在后邊添若干個0，直至滿足位數(shù)長度為止。

舉例說明

繼續(xù)以上邊的例子說明問題。

• 由于沒有1位的碼字，所以第一個碼字的位數(shù)為2，即碼字為00
• 由于2位的碼字有兩個，所以第二個碼字位數(shù)仍為2，即碼字為00+1=01
• 第三個碼字為3位，比第二個碼字長1位，所以第三個碼字為：01+1=10，然后再添1個“0”，得100
• ......

如此類推，最后得到哈夫曼編碼如下：

特別注意的是，如果中間有某個位數(shù)的碼字缺失，例如沒有4位碼字，則應該在3位碼字加1后，添加“00”補足5位，形成下一個5位碼字。

在建立好哈夫曼樹之后就可以對圖像數(shù)據(jù)進行解碼了。

圖像數(shù)據(jù)流的結構

分析圖像數(shù)據(jù)流的結構, 以一個從宏觀到微觀的順序來作詳細剖析, 即:

數(shù)據(jù)流→最小編碼單元→數(shù)據(jù)單元與顏色分量→顏色分量單元

• 在圖片像素數(shù)據(jù)流中, 信息可以被分為一段段最小編碼單元( Minimum Coded Unit, MCU) 數(shù)據(jù)流。所謂 MCU, 是圖像中一個正方矩陣像素的數(shù)據(jù)。這些矩陣的大小是這樣確定的:

  查閱標記 SOF0 得到圖像不同顏色分量的采樣因子。大多圖片的采樣因子為 4: 1: 1 或 1: 1: 1。記三個分量中水平采樣因子最大值為 Hmax, 垂直采樣因子最大值為 Vmax, 則單個 MCU 矩陣的寬就是 Hmax×8像素, 高就是 Vmax×8 像素。

  如果整幅圖像的寬度和高度不是 MCU 寬度和高度的整數(shù)倍, 那么編碼時會用某些數(shù)值填充進去, 保證解碼過程中 MCU 的完整性。

  另外, 在數(shù)據(jù)流中, MCU 的排列方法是從左到右, 從上到下。

• 每個 MCU 又分為若干個數(shù)據(jù)單元。數(shù)據(jù)單元的大小必定為 8×8。

  JPEG 文件與 BMP 文件有所不同, 它把圖片分成 Y、Cr、Cb 三張子圖, 然后分別壓縮。三個顏色分量的采樣因子可能一樣( 如 1: 1: 1) , 也可能不一樣( 如 4: 1: 1) 。

  每個 MCU 內部, 數(shù)據(jù)的順序是 Y、Cr、Cb。如果一個顏色分量有多個數(shù)據(jù)單元, 則順序是從左到右, 從上到下。

舉例說明：

下面通過一幅 32px×35px 的圖像, 對上面兩個問題作具體說明。

image

圖 1 中灰色部分為實際圖像大小 ( 32px×35px) ;粗虛線表示各個 MCU 的分界; 細虛線表示 MCU 內部數(shù)據(jù)單元的分界。

假設此圖的采樣因子為 4: 1: 1, 即 (2×2): (1×1):(1×1)。此時, Hmax=2, Vmax=2。所以, MCU 的寬為 16像素, 高為 16 像素。圖像實際的寬剛好是 2 個 MCU,但高則稍稍大于 2 個 MCU 的高度, 所以要補足 3 行
MCU。

在數(shù)據(jù)流中,MCU 的 順 序 是 MCU1→MCU2→MCU3→MCU4→MCU5→MCU6。

每個 MCU 又分為 4 個數(shù)據(jù)單元。采樣因子 4: 1: 1表示 Y 分量的水平和垂直方向都是每 2 個像素采樣2 次; Cr 分量和 Cb 分量的水平和垂直方向都是每 2個像素采樣 1 次。因此, Y 分量取滿 256 個采樣點; Cr分量和 Cb 分量各自只有 64 個采樣點, 取法如圖 2 的灰色點。

如果以 MCU1 說明 MCU 數(shù)據(jù)的次序, 則依次為Y1、Y2、Y5、Y6、Cb1256、Cr1256。圖 2 中全部 256 個點均是 Y的采樣點, 灰色部分為 Cr 分量和 Cr 分量的采樣點。

對于整張圖片來說, 數(shù)據(jù)流的數(shù)據(jù)依次是:

[Y1、Y2、Y5、Y6、Cb1256、Cr1256]、[Y3、Y4、Y7、Y8、Cb3478、
Cr3478]、[Y9、Y10、Y13、Y14、Cb9101314、Cr9101314]、……

切記每個MCU里面顏色分量的順序，是Y、Cb、Cr。Cb在前Cr在后，許多資料這里都寫反了，導致最后解碼出的圖像無法還原到原來的色彩。

若采樣因子為1：1：1，則Hmax=max（1，1，1）=1，Vmax=max（1，1，1）=1。所以，MCU的寬為Hmax8=8像素，高為Vmax8=8像素。圖像實際的寬剛好是4個MCU，但高則稍稍大于4個MCU的高度，所以要補足5行MCU。

在數(shù)據(jù)流中，MCU的順序是：

MCU1→MCU2→MCU3→MCU4→ ………… →MCU18→MCU19→MCU20。

因此，對于整張圖片來說，數(shù)據(jù)流的數(shù)據(jù)依次是：

[Y1 、Cb1、Cr1] 、[Y2 、Cb2 、Cr2] 、[Y3 、Cb3、Cr3] 、………… [Y19 、Cb19、Cr19]、[Y20 、Cb20、Cr20]。

同理，這里也是Cb在前，Cr在后。

顏色分量單元的內部解碼

“顏色分量單元”約定為說明問題而建立的概念,指的是 MCU 中某個顏色分量中的一個 8×8 數(shù)據(jù)塊,例如上面提到的 Y1、Cr1256、Cb1256 都是一個顏色分量單元。

圖像數(shù)據(jù)流是以位( bit) 為單位存儲信息的, 并且內部的數(shù)據(jù)都是在編碼時通過正向離散余弦變換( FDCT) 得到的結果, 所以顏色分量單元應該由兩部分組成: 1 個直流分量和 63 個交流分量。

解碼的過程其實就是哈夫曼樹的查找過程。首先查閱標記段 SOS 中的顏色分量信息, 可以得出各個顏色分量對應使用的直流分量和交流分量使用的哈夫曼樹編號。一般來說,

• Y 分量: 直流分量: 直流 0 號哈夫曼樹, 交流分量: 交流 0 號哈夫曼樹
• Cb 分量: 直流分量: 直流 1 號哈夫曼樹, 交流分量: 交流 1 號哈夫曼樹
• Cr 分量: 直流分量: 直流 1 號哈夫曼樹, 交流分量: 交流 1 號哈夫曼樹

顏色分量單元內部綜合運用了 RLE 行程編碼和哈夫曼編碼來壓縮數(shù)據(jù)。每個像素的數(shù)據(jù)流由兩部分構成: 編碼和數(shù)值。具體讀入單個顏色分量單元的步
驟如下:

1. 從此顏色分量單元的起點為單位讀入, 直到讀入編碼與該分量的直流哈夫曼樹的某個碼字一致, 然后用查得該碼字對應的值。值表示該直流分量數(shù)值的二進制位數(shù), 也就是接下來需要讀入的位數(shù)。假如是n位，則繼續(xù)讀入n位數(shù)據(jù)。再根據(jù)下文給出的表查詢出所對應的值，這個值就是直流分量的值。

2. 繼續(xù)讀入位數(shù)據(jù), 直到讀入的編碼與該分量交流哈夫曼樹的某個碼字一致, 然后查得該碼字對應的值。值的高 4 位表示當前數(shù)值前面有多少個連續(xù)的零, 低 4 位表示該交流分量數(shù)值的二進制位數(shù), 也就是接下來需要讀入的位數(shù)。假如是n位，則繼續(xù)讀入n位數(shù)據(jù)。再根據(jù)下文給出的表查詢出所對應的值，這個值就是對應位置交流分量的值。

3. 不斷重復步驟②, 直到滿足交流分量數(shù)據(jù)結束的條件。結束條件有兩個, 只要滿足其中一個即可

   • 當讀入碼字的值為零, 表示往后的交流變量全部為零
   • 已經讀入 63 個交流分量

各個數(shù)值的譯碼是按下表進行的：

其實對二進制比較熟悉的人一眼就可以看出這張表的究竟。對于正數(shù)使用原碼編碼，對于負數(shù)使用反碼編碼。

舉例說明：

某個顏色分量單元數(shù)據(jù)如下:

D3 5E 6E 4D 35 F5 8A

若以二進制表示，則為：

1101 0011 0101 1110 0110 1110 0100 1101 0011 0101 1111 0101 1000 1010

假設該顏色分量單元對應以下直流哈夫曼樹和交流哈夫曼樹，則可將各個以位為單位的數(shù)據(jù)流拆分如下：

<u>110 1001101</u> <u>01 1</u> <u>11001 101</u> <u>11001 001</u> <u>101 00</u> <u>11010 1</u> <u>1111010 11</u> <u>00</u> 01010

直流哈夫曼樹：

交流哈夫曼樹：

詳細說明：

讀入數(shù)據(jù)流并對照直流哈夫曼樹，第一個哈夫曼編碼為110，其權值為7，所以往后讀入7位數(shù)據(jù)“1001101”，譯碼成數(shù)值為77。因為每個顏色分量單元只有一個直流分量，所以下一個就是第一個交流分量了。

繼續(xù)讀入數(shù)據(jù)流并對照交流哈夫曼樹，得哈夫曼編碼為01，其權值為1，所以它的前面沒有零，并往后讀如1位數(shù)據(jù)“1”，譯碼成數(shù)值為1。如此往復，最后讀到哈夫曼編碼“00”，其權值為0，所以滿足交流變量結束條件（最后剩余的“01010”對本顏色分量單元來說是冗余的，它可能屬于下一個顏色分量單元）。

實際上，這段數(shù)據(jù)譯碼為：

77，（0，1），（0，5），（0，-6），（0，-3），（5，1），（2，3）

因此，把它置于1個8*8的矩陣中應為：

image

如果你的解碼已經進行到了這里，那么恭喜你，整個程序最麻煩的部分你已經完成了，剩下的只是一些簡單的矩陣變換。

直流系數(shù)差分編碼

每一種顏色分量內, 相鄰的兩個顏色分量單元的直流變量是以差分來編碼的。也就是說，通過上一個步驟解碼出來的直流變量數(shù)值只是當前顏色分量單元的實際直流變量減去前一個顏色分量單元的實際直流變量。也就是說，當前直流變量要通過前一個顏色分量單元的實際（非解碼）直流分量來校正：

DCn=DCn-1+Diff

其中Diff為差分校正變量，也就是直接解碼出來的直流系數(shù)。但如果當前顏色分量單元是第一個單元，則解碼出來的直流數(shù)值就是真正的直流變量。

注意, 3 個顏色分量的直流變量是分開進行差分編碼的。也就是說, 1 張圖片有 3 個直流校正變量。特別特別注意 ,在采樣比為4：1：1中也只有3個直流校正變量，比如有一張采樣比為4：1：1的圖像，他的每個MCU內部是[Y1,Y2,Y3,Cb,Cr],那么每個mcu的的Y2實際值為Y1+Diff，它的Y1為上一個mcu的Y3+Diff。

反量化

不同的顏色分量使用不同的量化表，這個可以從標記段SOF中的顏色分量信息字段查得。一般是Y分量使用量化表0，而Cr、Cb兩個分量共同使用量化表1。反量化的過程比較簡單。只需要對8*8的顏色分量單元的64個值逐一乘以對應的量化表內位置相同的值則可。圖像內全部的顏色分量單元都要進行反量化。

反Zig-Zag

下圖中從左圖到右圖就是正向Zig-Zag，從右圖的順序恢復到左圖的順序就是反向Zig-Zag。

image

在完成上一個步驟后就需要將每個MCU中的每個顏色分量矩陣進行反向Zig-Zag。

IDCT

之前提到，文件中的數(shù)據(jù)是在編碼時通過正向離散余弦變換（FDCT）進行時空域向頻率域變換而得到的結果，所以現(xiàn)在解碼就必須將其反向離散余弦變換（IDCT），就是把顏色分量單元矩陣中的頻率域數(shù)值向時空域轉換。

YCrCb向RGB轉換

要在屏幕上顯示圖像, 就必須以 RGB 模式表示圖像的顏色, 所以, 解碼時需要把 YCrCb 模式向 RGB模式轉換。

正如前面提到, 并不是每種顏色分量的采樣因子都一樣, 所以轉換時需要注意。由本文第 3 節(jié)對 4: 1: 1的采樣因子的分析, 可以知道一個 MCU 里有 4 個 Y分量單元, 而 Cr 分量和 Cb 分量各自只有 1 個分量單元。以圖 2 為例, 僅有的一個 Cr 分量單元應該平鋪用于 4 個 Y 分量單元, 即左上角 16 個值用于 Y1, 右上角 16 個值用于 Y2, 左下角 16 個值用于 Y5, 右下角
16 個值用于 Y6。對于 Cb 分量, 道理一樣。

下面是YCrCb向RGB轉換的公式:

R = Y + 1.402 * Cr + 128;
G = Y - 0.3441363 * Cb - 0.71413636 * Cr + 128;
B = Y + 1.772 * Cb + 128);

算出來的RGB值如果小于0則為0,如果大于255則為255.

至此, 每個 MCU 的解碼已經完成。只要將每個MCU 組成一幅完整的圖像就完成了一張 JPEG 圖像的解碼了。