Unraveling the JPEG file

(文章還剩實踐部分沒寫，答辯過后補上...)

JPEG文件在當下數字化生活中是無處不在的，但是在熟悉的JPEG面紗背后，隱藏著一些算法，它們去除了人類眼中無法察覺到的細節。這產生了最高的視覺質量與最小的文件大小。讓我們來看看這一算法。

引言

我們發送圖片給朋友的時候，并不需要擔心哪個設備或者瀏覽器或者操作系統的兼容性，我們只是把圖片"發出去"。但是就像網絡傳輸一樣，只是傳輸卻沒有其他的措施會造成兼容性極差，所以需要一種協議或者一種標準。于是一組人在1992年創建了JPEG，一種數字圖像壓縮的標準。任何曾經使用過互聯網的人都可能看到過JPEG編碼的圖像。它是迄今為止最普遍的編碼、發送和存儲圖像的方式。從網頁到電子郵件到社交媒體，JPEG每天被使用數十億次-幾乎每次我們在網上查看或發送圖片。沒有JPEG，網絡就會少一點色彩并且慢很多。

所以這篇文章里將介紹一下關于如何將存儲在計算機上的壓縮數據轉換為顯示在屏幕上的圖像。當然此文首先會對該文進行部分翻譯、然后結合MROS大神寫的一個JPEG教程進行講解，當然其中會加上自己的理解進行整理和驗證。如果能夠真正理解圖像的壓縮步驟，感覺對之后的圖像處理這一部分的學習也是有幫助的。

開始

首先雙手奉上女神的照片：

接下來我們就拿這張圖片作為例子來講解，如果我們用文字編輯器打開圖片就會發現是一堆亂碼：

因為這是文字編輯器不能識別的格式，用文字編輯器打開圖片，既讓計算機感到疑惑同時也不能讓我們得到正確的可視結果。因為我們的打開方式不正確，我們如果要理解JPEG圖像是如何解碼的，我們需要查看原始流，即查看二進制數據。可以利用專門查看hex編碼的編輯器來查看：

我們現在隨意修改其中的一些數字，可以發現有些數字的更改是無傷大雅的，但是有一些數字一旦修改可能會損壞整個圖像，或者造成圖像顏色和位置發生變動。

很難通過這樣的方式來解釋如何從這些字節中重建圖像，因為jpeg壓縮實際上是由三種不同的壓縮技術組成的，它們被應用在連續的層中。我們將分別查看每一層壓縮，以解開我們正在看到的神秘行為。

JPEG壓縮的三層

1.色度次采樣(Chrominance Subsampling)

2.離散余弦變換(Discrete Cosine Transform & Quantization)

3.掃描寬度、霍夫曼編碼(Run-length,Delta&Huffman Encoding)

首先我們需要了解這種壓縮的規模，請注意上面的圖像是使用確切的79，819個數字表示的，大約是79千字節。如果沒有壓縮存儲，則每個像素需要三個數字-每個紅色、綠色和藍色組件都需要一個數字。這意味著總共有917，700個數字，約917千字節。使用jpeg壓縮，結果文件要小十倍以上！而jpeg被稱為有損壓縮技術，圖像由于壓縮而改變并丟失了一些細節

Chrominance Subsampling

現在破譯要簡單一些。這幾乎是一個簡單的顏色列表，每個字節只改變一個像素，但它已經幾乎是未壓縮圖像的兩倍(對于這個較小的大小，大約是300 kb)。可以看出，這些數字并不代表標準的紅色、綠色和藍色組件，因為用0替換所有數字會使圖像變成綠色(而不是黑色)。這是因為這些字節表示圖像的y(亮度)、cb(相對藍度)和cr(相對紅度)。為什么不直接用RGB呢？畢竟，這就是大多數現代屏幕的工作原理。您的顯示器可以通過打開每個像素的不同強度的紅色、綠色和藍色燈來顯示任何顏色。白色是通過打開顯示的。

這也和人類眼睛的工作原理非常相似。我們眼中的顏色受體被稱為“錐”，分為三種類型，每種類型對紅色、綠色或藍色都很敏感。我們眼中的另一種感受器-棒，只能檢測到亮度的變化，但它們要敏感得多。我們的眼睛里有大約1.2億根棒狀物。

這意味著我們的眼睛在檢測亮度變化方面比在檢測顏色變化方面要好得多。如果我們能把顏色和亮度分開，我們就可以在沒有人注意到的情況下去除一點顏色。色度次采樣是以比亮度分量更低的分辨率來表示圖像的顏色分量的過程。在上面的例子中，每個像素都有一個y分量，而每個由四個像素組成的離散組正好有一個CB和一個cr分量。因此，圖像中包含的顏色信息只有最初的四分之一。這就是為什么從上面的編輯器中刪除一個數字完全破壞了顏色。在這里，組件存儲為y cbcr。刪除第一個數字將使CB值被解釋為y，cr被解釋為CB，并創建一個波動效應，在圖像中翻轉所有顏色。

Discrete Cosine Transform & Quantization

這一層壓縮很大程度上是jpeg的定義特性。在將顏色轉換為ycbcr之后，組件將被單獨壓縮，因此我們可以在本文的其余部分只關注y分量。下面是應用這個層的y組件的字節。

離散余弦變換是將圖像分解成8x8塊并將每個塊轉換成這64個系數的組合的過程。

如果我們并不是對8*8像素點而是對整個獨享進行離散余弦變換，得到的就為上圖。并且可以不斷刪除結尾處的數據，但是一旦變更開頭處的數據，就會造成肉眼可見的亮度變化。原因是開頭處為圖像的低頻變化，結尾處為高頻變化。

Run-Length, Delta & Huffman Encoding

run-length encoding是用三個bytes去指定顏色，還有一個byte去指定有多少個像素有這個顏色。

delta-encoding是記錄變化量而不是原值，比如說存儲值為12 13 14 13 2，則就可以表示為：12 1 1 -1 -1。每個DCT塊中的第一個值稱為dc值，每個dc值相對于前面的dc值進行增量編碼。因此，改變第一個塊的亮度將影響圖像中的所有塊。

JPEG解碼流程

正如前面所說的一樣，JPEG是一個標準，而不是單單一個算法。包含了多種壓縮算法以及編碼方式，也就是說兩張jpeg圖片之后使用的算法可能完全不同。

如果用壓縮算法進行區分的話，可以分為sequential、progressive、hierarchical和lossless，其中sequential會從上至下解碼：

progressive則會在解碼過程中，從模糊逐步變得清晰：

除了壓縮算法，還有編碼方式不同：霍夫曼編碼、算術編碼。除了壓縮算法和編碼方式，還有數據的粒度，可以理解為精度。先介紹所有JPEG規范組合中最簡單的一種：baseline，它使用的壓縮算法為sequential，編碼方式采用的為霍夫曼編碼，精度為8bit。而JPEG的編碼與解碼過程可以由下圖表示：

其中，DCT變換以及霍夫曼編碼都是完全可逆的運算，如果只有這兩個步驟，呢么得到的圖片就是無損的。但是為了進一步提高壓縮俠侶，baseline方法會拋棄掉一些"精細結構"，就像語音識別時會去掉音高等精細結構而只是保存采樣數據一樣。而從圖中可以看出將顏色從RGB空間轉換成YCbCr空間后降采樣 以及 在DCT變換后的量化數據都是去掉這些精細結構。

一些概念

降采樣

縮小圖像(降采樣)的目的主要有兩個：1.使得圖像符合顯示區域的大小；2.生成對應圖像的縮略圖。原理是這樣的：對于一幅圖像尺寸為M*N，對其進行s倍 的下采樣，即得到\((M/s)*(N/s)\) 儲存的分辨率圖像。如果考慮是矩陣形式的圖像，就是把原始圖像 \(s*s\)窗口內的圖像變成一個像素，這個像素點就是窗口內所有像素的均值\(P_k=\frac{\sum X_{i}}{S^{2}}\)

范式霍夫曼編碼

左邊就是霍夫曼樹，讓所有節點維持高度不變，但盡量往右移動，得到了右圖。由于兩棵樹的葉子節點高度相等，它們的壓縮率是完全相等的。我們用左側這棵樹來記錄編碼信息，需要把整棵樹的結構都記錄下來；但如果使用的是右側的樹，只需要記錄在高度h時有幾個葉子幾點，就能夠完全復原出右側的霍夫曼樹，所以范式霍夫曼樹能夠減少存儲編碼信息的空間用量。這個特性可以用于加速解碼。

例如用0b0代表A，0b10代表B，0b11代表C，則AABCAAA壓縮為0b001011000.

YCbCr色彩空間

RGB、YUV和YCbCr都是人為規定的色彩模型或顏色空間（有時也叫彩色系統或彩色空間）。它的用途是在某些標準下用通常可接受的方式對彩色加以描述。本質上，色彩模型是坐標系統和子空間的闡述。

其中RGB是我們常見的紅藍綠，依據人眼識別的顏色定義出的空間。但是RGB的細節很難進行數字化的調整，它將色調、亮度、飽和度三個量放在一起表示。是最通用的面向硬件的彩色模型。該模型用于彩色監視器和一大類彩色視頻攝像。每個像素點需要8bits*3 = 24bits

而YUV空間中，每一個顏色有一個亮度信號Y和兩個色度信號U和V，亮度信號時強度的感覺，和色度信號斷開，這樣的話強度就能夠在不影響顏色的情況下改變。YUV使用RGB的信息，如果只有Y信號分量而沒有U、V分量，那么這樣表示的圖像就是黑白灰度圖像。彩色電視采用YUV空間正是為了用亮度信號Y解決彩色電視機與黑白電視機的兼容問題，使黑白電視機也能接收彩色電視信號。

YUV和RGB的轉換:Y = 0.299 R + 0.587 G + 0.114 BU = -0.1687 R - 0.3313 G + 0.5 B + 128V = 0.5 R - 0.4187 G - 0.0813 B + 128R = Y + 1.402 (V-128)G= Y - 0.34414 (U-128) - 0.71414 (V-128)B= Y + 1.772 (U-128)

YCbCr 其實是YUV經過縮放和偏移的翻版。其中Y與YUV 中的Y含義一致,Cb,Cr 同樣都指色彩，只是在表示方法上不同而已。YCbCr其中Y是指亮度分量，Cb指藍色色度分量，而Cr指紅色色度分量。JPEG、MPEG均采用此格式。

 YCbCr與RGB的相互轉換Y=0.299R+0.587G+0.114BCb=0.564(B-Y)Cr=0.713(R-Y)R=Y+1.402CrG=Y-0.344Cb-0.714CrB=Y+1.772Cb

YCbCr 有許多取樣格式，主要的采樣格式有YCbCr 4:2:0、YCbCr 4:2:2、YCbCr 4:1:1和 YCbCr 4:4:4。其中YCbCr 4:1:1 比較常用，其含義為：每個點保存一個 8bit 的亮度值（也就是Y值），每 2x2 個點保存一個 Cr 和Cb 值，圖像在肉眼中的感覺不會起太大的變化。所以，原來用 RGB(R,G,B 都是 8bit unsigned) 模型，每個點需要 8x3=24 bits（如下圖第一個圖）. 而僅需要 8+（8/4）+（8/4）=12bits，平均每個點占12bits。這樣就把圖像的數據壓縮了一半。

再來具體解釋一下主要的采樣格式：

(1)YUV 4:4:4

YUV三個信道的抽樣率相同，因此在生成的圖像里，每個象素的三個分量信息完整（每個分量通常8比特），經過8比特量化之后，未經壓縮的每個像素占用3個字節。
下面的四個像素為： [Y0 U0 V0] [Y1 U1 V1] [Y2 U2 V2] [Y3 U3 V3]
存放的碼流為： Y0 U0 V0 Y1 U1 V1 Y2 U2 V2 Y3 U3 V3

(2)YUV 4:2:2

每個色差信道的抽樣率是亮度信道的一半，所以水平方向的色度抽樣率只是4:4:4的一半。對非壓縮的8比特量化的圖像來說，每個由兩個水平方向相鄰的像素組成的宏像素需要占用4字節內存。
下面的四個像素為：[Y0 U0 V0] [Y1 U1 V1] [Y2 U2 V2] [Y3 U3 V3]
存放的碼流為： Y0 U0 Y1 V1 Y2 U2 Y3 V3
映射出像素點為：[Y0 U0 V1] [Y1 U0 V1] [Y2 U2 V3] [Y3 U2 V3]

(3)YUV 4:1:1

4:1:1的色度抽樣，是在水平方向上對色度進行4:1抽樣。對于低端用戶和消費類產品這仍然是可以接受的。對非壓縮的8比特量化的視頻來說，每個由4個水平方向相鄰的像素組成的宏像素需要占用6字節內存
下面的四個像素為：[Y0 U0 V0] [Y1 U1 V1] [Y2 U2 V2] [Y3 U3 V3]
存放的碼流為： Y0 U0 Y1 Y2 V2 Y3
映射出像素點為：[Y0 U0 V2] [Y1 U0 V2] [Y2 U0 V2] [Y3 U0 V2]

(4)YUV 4:2:0

4:2:0并不意味著只有Y,Cb而沒有Cr分量。它指得是對每行掃描線來說，只有一種色度分量以2:1的抽樣率存儲。相鄰的掃描行存儲不同的色度分量，也就是說，如果一行是4:2:0的話，下一行就是4:0:2，再下一行是4:2:0...以此類推。對每個色度分量來說，水平方向和豎直方向的抽樣率都是2:1，所以可以說色度的抽樣率是4:1。對非壓縮的8比特量化的視頻來說，每個由2x2個2行2列相鄰的像素組成的宏像素需要占用6字節內存。
下面八個像素為：[Y0 U0 V0] [Y1 U1 V1] [Y2 U2 V2] [Y3 U3 V3] [Y5 U5 V5] [Y6 U6 V6] [Y7U7 V7] [Y8 U8 V8]
存放的碼流為：Y0 U0 Y1 Y2 U2 Y3
Y5 V5 Y6 Y7 V7 Y8
映射出的像素點為：[Y0 U0 V5] [Y1 U0 V5] [Y2 U2 V7] [Y3 U2 V7] [Y5 U0 V5] [Y6 U0 V5] [Y7U2 V7] [Y8 U2 V7]

讀取區段

JPEG壓縮文件可能是由以下幾個區段組成的：

除此之外，我們需要在JPEG開始和結尾處加上"文件開始"和"文件結束"標記，并且采用何種算法會和降采樣在同一個區段；壓縮圖像數據會前準一個SOS區段，告知解碼器接下來該如何讀取。綜上可以將JPEG壓縮文件表示為：

在一個JPEG文件中，一定會出現SOF0、SOF1....SOF16其中一個區段，如果出現的是SOF0就說明使用的為baseline。DQT和DHT都可能不止一個：

區段名稱	標記碼	有無數據
SOI	0xFFD8	NO
EOI	0xFFD9	NO
DQT	0xFFDB	YES
DHT	0xFFC4	YES
SOF0	0xFFC0	YES
SOS	0xFFDA	YES

如果圖像信息里包含了0xff怎么辦？所以在規定壓縮圖像時會在0xff后加上一個0x00的字節，檢測時如果遇到0xff00直接跳過就行了。而又因為這里一個碼有2個字節，所以在寫程序是可以兩個字節兩個字節的讀。

而在baseline中，文件開頭、文件結尾、JFIF特有資訊實際上都已經確定了，所以接下來只需要確定量化表(DQT)、霍夫曼表、壓縮數據、SOF0和SOS就行了，一步一步來。

讀取DQT

一個DQT里最多可能有4個量化表，所以量化表的存放在不同程序下可能會使用不同的方式下面是一個量化表的內容：

代號	大小	描述
①	1 byte	高 4 bits 表示每個量化值的大小，0 代表 1 byte，1 代表 2 bytes 低 4 buts 表示本量化表的 id ， id 可爲 0, 1, 2, 3
②	64 或 128 byte	64 個 1 或 2 bytes 的量化值，是 1 byte 還是 2 bytes 取決於 ① 的高 4 bits

讀取霍夫曼編碼表

代號	大小	描述
①	1 byte	高 4 bits 代表本表是直流還是交流， 0 是直流， 1 是交流 低 4 bits 代表是 0 號表還是 1 號表， 0 是 0 號 ， 1 是 1 號
②	16 bytes	第 n 個 byte 代表高度爲 n 時，霍夫曼樹有幾個葉子節點
③	葉子節點數量bytes	代表葉子節點所對應的信源符號，葉子從低到高，從左到右

紅色就是直流1號，紫色部分就為形成的范式霍夫曼樹的葉節點數目，葉子節點應該有2+2+5+1+5+1=16，所以綠色部分應該有16個數值代表葉子節點上對應的信源符號；如果不足16個數值，說明這個DHT區段可能包含多個霍夫曼表，在下一個霍夫曼表中繼續讀取。

讀取SOF0區段

SOF0區段記錄了圖片寬高以及各個顏色分量的信息，有了這些數據我們才能夠讀取SOS段中的壓縮圖像數據，不過先看SOF0區段：

代號	大小	描述	備註
①	1 byte	精度	baseline 流程的精度固定爲 8 ，也就是說用 1 byte 來存取色彩空間的數值即可
②	2 bytes	圖片高度
③	2 bytes	圖片寬度
④	1 byte	有幾個顏色分量	JFIF 規定顏色空間爲 YCbCr 因此顏色分量數量固定爲 3
⑤	9 bytes	各個顏色分量的詳細資訊	見下一張表

上表中的5是下表重復三次，因為需要分別描述3個顏色分量的信息：

代號	大小	描述	備註
①	1 byte	顏色分量 id	1 表示 Y ， 2 表示 Cb ， 3 表示 Cr
②	1 byte	採樣率	高 4 bit 代表水平採樣率 ，低 4 bit 代表垂直採樣率。採樣率可以是 1, 2, 3, 4
③	1 byte	量化表 id	最後解碼時，要選擇哪一個量化表對該顏色分量進行量化

讀取SOS區段

代號	大小	描述	備註
①	1 byte	有幾個顏色分量
②	2 * 3 bytes	顏色分量對應的霍夫曼表	每個顏色分量佔用 2 bytes ， 見下一張表
③	3 bytes	baseline 流程用不到	在 baseline 流程固定爲 0x003F00

② 的內容爲下表重重復3 次：

代號	大小	描述	備註
①	1 byte	顏色分量 id	1 表示 Y，2 表示 Cb，3 表示 Cr
②	1 byte	對應的霍夫曼表 id	高 4 bit 代表直流（DC）霍夫曼表，低 4 bit 代表交流（AC）霍夫曼表

讀取壓縮圖像數據

數據流切割來看，可以看成一個接一個的 MCU 串:

[MCU1], [MCU2], [MCU3], [MCU4], ....

而一個 MCU 又可以進一步切割成（假設 Y 水平、垂直採樣率爲 2 ，Cb, Cr 水平、垂直採樣率爲 1）不同顏色分量的串連，以 Y -> Cb -> Cr 的順序:

[Y1, Y2, Y3, Y4, Cb1, Cr1]

這裏的 Y1, Y2, .... Cr1 ，都是一個 8 * 8 的 block 了，所以之後我們只要瞭解一個 block 如何讀取，就大功告成了。

讀取一個block

每個block都是8*8的，最左上角的數值就是直流變量，要使用直流霍夫曼表來解碼，而與下的63個數值為交流變量。

JPEG分塊機制

因為再sequential算法中，是從上至下邊收數據邊進行解碼的，所以說明JPEG文件必然是分塊進行壓縮的，因為不需要知道所有的數據就已經可以開始解碼：

MCU是最小編碼單元Minimum Coded Unit的縮寫(通信協議上某一層上所能通過的最大數據包大小的概念為MTU)。MCU的寬高并不固定為16px也不一定是正方形，而是取決于顏色分量的采樣率。

JPEG使用的為YCbCr色彩空間，采樣圖如上。每個顏色分量的最基本單元是block，一個block的寬、高固定為8*8：

MCU的寬 = 8 * 最高水平采樣率
MCU的高 = 8 * 最高垂直采樣率

Cb、Cr的最左上角對應到了MCU的左上4個px：

MCU從左到右、再從上到下：

一個顏色分量內部各個block的順序一樣是從左到右、從上到下：

MCU、顏色分量、block關系

讀取圖像壓縮數據時，需要先讀取MCU信息，在讀取MCU時又需要讀取block的信息。

解碼 decode!

由于已經將JPEG文件的所有區段全部讀取出來了，接下來就是簡單的轉換，就能夠還原為原始圖像數據，接下來將按照步驟來依次轉換。

反量化

從DQT區段中已經讀出了量化表，在SOF0區段中也知道了各個顏色分量所對應的量化表id，一個block和一個量化表都是8*8，將它們對應的位置相乘就完成這個轉換了。

反zigzag

zigzag時，會將一個block以下圖的順序重新排列：

反zigzag就是要將這個過程逆轉過來進行還原

反向DCT變換

升采樣與YCbCr轉RGB顏色空間

照著公式來變換即可。

最后將圖像的各個MCU拼接起來就可以得到原圖了。

一個實例

下面給出一個將JPEG文件轉換成bmp文件的程序：https://github.com/MROS/jpeg_decoder/blob/master/main.cpp