JPEG學(xué)習(xí)筆記
陳碩
chenshuo@chenshuo.com
2005年11月
JPEG靜態(tài)圖像壓縮的基本(baseline)算法分4個(gè)步驟[1]：1.按8×8象素分塊2.離散余弦變換(DCT)3.量化4.熵編碼
如果圖片是彩色的，那么通常在第一步同時(shí)做色彩空間變換（RGB→YCbCr）。編碼算法的框圖見(jiàn)圖1。
圖1-JPEG編碼器框圖[1]
解碼算法是編碼算法的逆過(guò)程，框圖見(jiàn)圖2。
圖2-JPEG解碼器框圖[1]
JPEG標(biāo)準(zhǔn)[2]中還定義了無(wú)損壓縮算法，不過(guò)基本沒(méi)人用。除了baseline方式，還有progressive方式和hierarchical方式，本文只談baseline方式。
目錄
1算法描述與比較............................
3
1.1分塊及預(yù)處理...............................31.2變換編碼..................................31.3量化.....................................61.4
行程編碼與熵編碼.............................
7
2實(shí)現(xiàn)細(xì)節(jié)................................
8
2.1
ijg-jpeg實(shí)現(xiàn)分析..............................92.1.1預(yù)處理...............................112.1.2色彩轉(zhuǎn)換..............................132.1.3擴(kuò)展邊界..............................142.1.4下采樣...............................152.1.5JPEG壓縮.............................172.1.6DCT與量化............................182.1.7“之”字型掃描與熵編碼......................202.1.8量化表的縮放...........................
232.2
pvrg-jpeg實(shí)現(xiàn)分析.............................
26
3MATLAB實(shí)現(xiàn)..............................284參考資料................................28
1.算法描述與比較
1.1分塊及預(yù)處理
JPEG可以壓縮連續(xù)色調(diào)的灰度圖像或彩色圖像。對(duì)于灰度圖像，每個(gè)象素可以是8-bit或12-bit的灰度值。baseline模式只要求處理8-bit圖像（某些醫(yī)學(xué)影像是12-bit的）。對(duì)于彩色圖像，原則上可以將每個(gè)色彩分量成分看作一幅灰度圖像，再進(jìn)行壓縮。不過(guò)由于人眼對(duì)于亮度變化比色彩變化更敏感，因此通常把RGB彩色信號(hào)變換為亮度和色差信號(hào)，并對(duì)色差信號(hào)進(jìn)行下采樣(downsampling)，這樣可以提高壓縮率。具體來(lái)講，如果輸入圖像用RGB色彩表示，那么要把它變換到Y(jié)CbCr色彩空間。每個(gè)象素(R,G,B)對(duì)應(yīng)的(Y,Cb,Cr)的計(jì)算公式[3]是：
YCbCr??=??0.29900.58700.1140?0.1687?0.33130.50000.5000?0.4187?0.0813??·??RGB??+??0128128??其中R,G,B和Y,Cb,Cr都是8-bit無(wú)符號(hào)整數(shù)，范圍從0到255。色彩變換基本不影響圖像的質(zhì)量，最多由于整數(shù)運(yùn)算的截?cái)鄷?huì)使解碼的圖像與原圖有些微差別。對(duì)于N×M的圖像，色彩變換的計(jì)算復(fù)雜度為O(MN)。
JPEG壓縮編碼的第一步是將輸入圖像按從左到右，從上到下的順序分成8×8大小的塊。編碼器本質(zhì)上是對(duì)一連串8×8大小的灰度圖像進(jìn)行編碼。對(duì)于彩色圖像，還涉及到各色彩分量的交織(interleaving)與下采樣處理，這留在“實(shí)現(xiàn)細(xì)節(jié)”一節(jié)中討論。
如果原圖像的寬度或高度不是8的整數(shù)倍，需要對(duì)原圖擴(kuò)大一圈，讓寬度和高度都是8的倍數(shù)，然后進(jìn)行壓縮。當(dāng)然，在生成的JPEG文件中要記錄原始圖像的大小，并把解壓縮的（大了一圈的）圖像剪裁到原大小。圖像的填補(bǔ)和分塊伴隨離散余弦變換一同進(jìn)行，可不計(jì)復(fù)雜度。
1.2變換編碼
JPEG是一種基于變換的圖像壓縮算法，它采用了離散余弦變換(DCT)。基于變換的一般編碼系統(tǒng)[9,Chap.8]的框圖見(jiàn)圖3。
“變換”的基本思想是，找到一組基，讓圖像在這組基下能量集中（少量系數(shù)值較大，其余系數(shù)接近0）。為了達(dá)到分離能量的目的，“變換”一般應(yīng)是正交的。變換必須是可逆的（否則無(wú)法解碼），因此變換本身不能壓縮信息。不過(guò)通過(guò)隨后的“量化”步驟將影響不大的系數(shù)略去，即可達(dá)到壓縮的目的。
適合圖像壓縮的變換有很多種[9,Chap.8]，例如Karhunen-Loève變換(KLT，即主成分分析)、離散傅立葉變換(DFT)、離散余弦變換(DCT)、Walsh-Hadamard變換(WHT)等等。
在數(shù)據(jù)壓縮方面最佳的變換是Karhunen-Loève變換，但實(shí)際系統(tǒng)中一般不用它。原因有兩點(diǎn)：1.KLT得到的基與輸入數(shù)據(jù)相關(guān)，意味著除了需要把系數(shù)傳給解碼器，還需要把基傳給解碼器。而且每個(gè)分塊的基往往是不同的！這使得壓縮效果大打折扣。2.KLT需要計(jì)算協(xié)方差矩陣的特征向量，計(jì)算量相當(dāng)大。
DFT、WHT、DCT的基是固定的，與輸入無(wú)關(guān)。在與輸入無(wú)關(guān)的各種變換中，非正弦變換（如WHT）最容易實(shí)現(xiàn)，正弦變換（如DFT和DCT）的信息壓縮能力更接近最佳的KLT方法。DFT是酉空間的正交變換（系數(shù)是復(fù)數(shù)），DCT是歐式空間的正交變換（系數(shù)是實(shí)數(shù)），因此DFT的系數(shù)比DCT多一倍。不過(guò)實(shí)數(shù)的DFT的系數(shù)是共扼對(duì)稱的，實(shí)際所需的存儲(chǔ)空間與DCT一樣。
圖像壓縮的質(zhì)量與所用的變換有關(guān)，也與分塊的大小有關(guān)，最常采用的分塊尺寸為8×8和16×16。圖4說(shuō)明了分塊尺寸對(duì)變換編碼重構(gòu)誤差的影響[9,p.478]。這里先計(jì)算各個(gè)分塊的變換，截取75%的系數(shù)，然后對(duì)截取后的數(shù)組進(jìn)行反變換，最后計(jì)算重構(gòu)出的圖像的誤差。
從圖4可以看出，據(jù)重構(gòu)誤差比較，DCT比DFT和WHT要好。DCT優(yōu)于DFT的另外一個(gè)原因是[9,p.477]，由于DFT的邊緣振鈴現(xiàn)象（Gibbs現(xiàn)象），相鄰圖像分塊之間的邊界變得可見(jiàn)。DCT減少了這種效應(yīng)，一是它的固有周期比DFT長(zhǎng)一倍，二是它的邊界不間斷，見(jiàn)圖5的比較。
圖5-一維DFT(a)和DCT(b)的固有周期
因此為了兼顧壓縮效果和計(jì)算復(fù)雜度，JPEG采用8×8的2-DDCT作為其核心，該變換的定義是
F(u,v)=14C(u)C(v)
7??x=07??y=0
f(x,y)cos(2x+1)uπ16cos(2y+1)vπ16其中當(dāng)u,v=0時(shí)C(u),C(v)=1
√2
，否則C(u),C(v)=1。在計(jì)算DCT之前，要
把輸入圖像的象素值減去128，讓它的取值范圍從[0,255]移到[?128,127]。
每個(gè)8×8的分塊經(jīng)過(guò)DCT運(yùn)算得到64個(gè)系數(shù)。其中F(0,0)稱為直流系數(shù)，其余63個(gè)系數(shù)稱為交流系數(shù)。在典型的連續(xù)色調(diào)圖像中，相鄰象素之間的差別往往不大。這意味著空間頻率的幅值集中在低頻部分。對(duì)典型的8×8圖像分塊而言，大多數(shù)空間頻率幅值是0或接近0，在編碼時(shí)可忽略。DCT本身并不降低圖像的質(zhì)量，最多由于整數(shù)運(yùn)算的舍入誤差導(dǎo)致重構(gòu)的圖像與原始圖像略有差別。
如果直接采用前面的公式計(jì)算，每個(gè)DCT系數(shù)F(u,v)需要64次乘法，計(jì)算全部64個(gè)DCT系數(shù)需要64×64=4096次乘法。計(jì)算DCT是整個(gè)JPEG壓縮過(guò)程中最耗時(shí)的一步，很多人研究快速算法[5,Item25]，也有人往CPU增加新指令，使之便于DCT運(yùn)算?；舅悸肥前?-DDCT分解為1-DDCT，再利用余弦函數(shù)的對(duì)稱性來(lái)減少計(jì)算量。每個(gè)分塊的計(jì)算復(fù)雜度為O(1)。對(duì)于N×M的圖像，共有
N8??×??M
8??個(gè)分塊，因此DCT這一步的計(jì)算復(fù)雜度為O(MN)。
1.3量化
量化(quantization)是JPEG壓縮過(guò)程中惟一會(huì)大幅損失信息的步驟。64個(gè)DCT系數(shù)會(huì)用8×8的量化表進(jìn)行均勻量化，量化表中的每個(gè)元素是1到255之間的整數(shù)，表示對(duì)應(yīng)的DCT系數(shù)的量化步長(zhǎng)。量化的作用在于降低DCT系數(shù)的精度，從而達(dá)到更好的壓縮率。量化是多對(duì)一映射，因此是有損的，它是基于變換的編碼器中導(dǎo)致信息損失的主要步驟，也是用戶惟一能參與控制壓縮質(zhì)量的步驟。
量化的過(guò)程是將每個(gè)DCT系數(shù)除以對(duì)應(yīng)的量化步長(zhǎng)，并四舍五入為整數(shù)：
FQ
(u,v)=round
F(u,v)Q(u,v)??
反量化(dequantization)是把量化后的系數(shù)乘以對(duì)應(yīng)的量化步長(zhǎng)：
F
(u,v)=FQ(u,v)·Q(u,v)隨后?F
(u,v)將作為IDCT的輸入。量化表理論上應(yīng)該根據(jù)輸入圖像確定，目標(biāo)是在基本不影響圖像的視覺(jué)效果的前提下，盡量提高壓縮率。量化步長(zhǎng)越大，壓縮率越大，圖像質(zhì)量越低。JPEG標(biāo)準(zhǔn)的正文中并沒(méi)有規(guī)定或推薦使用哪個(gè)量化表，不過(guò)在AnnexK中有一份量化表的例子（圖6），適用于大多數(shù)中等質(zhì)量的圖片。對(duì)于超高質(zhì)量和超低質(zhì)量的圖片，這份量化表不是最優(yōu)的[5,Item75]。通常亮度分量和色差分量各有一張量化表，而且對(duì)色差分量的將忽略更多的高頻成分。實(shí)際的JPEG實(shí)現(xiàn)都采用這一份量化表，因此壓縮后的數(shù)據(jù)中無(wú)須包含量化表。如果把下表中的量化步長(zhǎng)除以2，那么圖像質(zhì)量就接近完美了。
每個(gè)分塊有64個(gè)系數(shù)需要量化，需用64次除法和取整操作，因此每個(gè)分塊
的計(jì)算復(fù)雜度為O(1)。對(duì)于N×M的圖像，共有??N8??×??M
8??個(gè)分塊，因此量化
這一步的計(jì)算復(fù)雜度為O(MN)。
1.4行程編碼與熵編碼
JPEG壓縮的最后一步是對(duì)量化后的系數(shù)進(jìn)行熵編碼。這一步采用通用的無(wú)損數(shù)據(jù)壓縮技術(shù)，對(duì)圖像質(zhì)量沒(méi)有影響。
在熵編碼之前，需要把64個(gè)DCT系數(shù)轉(zhuǎn)換為一串中間符號(hào)。其中直流系數(shù)和交流系數(shù)的編碼方式不同。直流系數(shù)表示當(dāng)前分塊中64個(gè)象素的平均值，相鄰分塊的直流系數(shù)具有很強(qiáng)的相關(guān)性，因此在編碼時(shí)只需記錄與前一分塊的直流系數(shù)的差值，即直流系數(shù)的“中間符號(hào)”采用差分脈沖編碼(DPCM)，見(jiàn)圖7(a)。
對(duì)63個(gè)交流系數(shù)用“之”字型掃描，讓它變成一維數(shù)組，見(jiàn)圖7(b)。這樣做的目的是將低頻系數(shù)放在前面，高頻系數(shù)放在后面。因?yàn)楦哳l系數(shù)中有很多0，為了節(jié)約空間，所以交流系數(shù)的“中間符號(hào)”用零行程碼(ZeroRunLength)表示。
接下來(lái)對(duì)中間符號(hào)進(jìn)行熵編碼，這一步的目的是利用符號(hào)的統(tǒng)計(jì)特性，進(jìn)一步提高壓縮率。JPEG標(biāo)準(zhǔn)規(guī)定的熵編碼方式有兩種：Huffman編碼和算術(shù)編碼。這兩種編碼各有優(yōu)劣，見(jiàn)圖8
“正宗”的Huffman編碼過(guò)程要對(duì)輸入序列進(jìn)行兩遍掃描，第一遍統(tǒng)計(jì)各個(gè)符號(hào)出現(xiàn)的概率，構(gòu)造Huffman樹(shù)，得到碼書(shū)(codebook)；第二遍用碼書(shū)對(duì)符號(hào)進(jìn)行編碼。這么做的話，時(shí)間空間開(kāi)銷(xiāo)都較大。兩遍掃描意味著要把整幅圖像的“中間符號(hào)”都記錄下來(lái)，不能“隨到隨編(on-the-?y)”。而且要把碼書(shū)傳給解碼器，這會(huì)增加壓縮文件的大小。
JPEG的實(shí)際實(shí)現(xiàn)一般支持兩種Huffman方式，一種是前述的“正宗”Huffman編碼（稱為optimized方式），另一種則采用JPEG標(biāo)準(zhǔn)AnnexK中給出的缺省碼書(shū)。采用缺省碼書(shū)的好處是輸入序列只用掃描一遍，空間和實(shí)際開(kāi)銷(xiāo)都較小；缺點(diǎn)是，由于碼書(shū)不是根據(jù)當(dāng)前圖像的統(tǒng)計(jì)信息得到的，那么壓縮率會(huì)比“正宗”Huffman編碼低一些。不過(guò)由于Huffman編碼對(duì)概率誤差不敏感，因此實(shí)踐中常常采用缺省碼書(shū)進(jìn)行編碼（這樣還能省下保存碼書(shū)的空間）。
算術(shù)編碼和Huffman編碼都是變長(zhǎng)碼，符號(hào)出現(xiàn)概率越高，碼字越短。不同之處在于，Huffman編碼每個(gè)符號(hào)對(duì)應(yīng)的碼字是確定的，每個(gè)碼字的bit數(shù)為整數(shù)。算術(shù)編碼的基本思想是用一個(gè)精度足夠高的屬于[0,1)的實(shí)數(shù)來(lái)表示整個(gè)輸入序列，輸入序列中每個(gè)符號(hào)對(duì)應(yīng)的碼字是不確定的，總體上每個(gè)符號(hào)對(duì)應(yīng)的碼字長(zhǎng)度等于其信息熵（均以bit計(jì)），碼字平均長(zhǎng)度可能是小數(shù)。算術(shù)編碼的壓縮率通常高于Huffman編碼[11]。算術(shù)編碼的另一個(gè)好處是，它很容易做成自適應(yīng)的(adaptive)，因此只需掃描一遍輸入序列，空間開(kāi)銷(xiāo)小很多。算術(shù)編碼還有一個(gè)小問(wèn)題，IBM掌握了一大堆與算術(shù)編碼相關(guān)的專利[5,Item8]。要想實(shí)現(xiàn)JPEG中的算術(shù)編碼，不可能繞過(guò)這些專利。
Huffman編碼和算術(shù)編碼在任何一本信息論[11]或數(shù)據(jù)壓縮[12]教材中都能找到，其實(shí)現(xiàn)細(xì)節(jié)不是本文的重點(diǎn)。這兩種編碼方法的計(jì)算復(fù)雜度都和輸入序列的長(zhǎng)度成正比，每個(gè)分塊最多有64個(gè)符號(hào)（符號(hào)數(shù)通常遠(yuǎn)小于此數(shù)，因?yàn)镈CT系數(shù)當(dāng)中有很多連續(xù)的0），因此每個(gè)分塊的復(fù)雜度為O(1)。對(duì)于N×M的圖像，熵編碼的計(jì)算復(fù)雜度為O(MN)。
2.實(shí)現(xiàn)細(xì)節(jié)
我主要參考了兩份JPEG實(shí)現(xiàn)，分別來(lái)自IndependentJPEGGroup(IJG)[7]和StanfordPortableVideoResearchGroup(PVRG)[8]，以下簡(jiǎn)稱ijg-jpeg和pvrg-jpeg。這兩份實(shí)現(xiàn)都采用C語(yǔ)言，版本號(hào)分別為version6b和v1.2.1，最后更新時(shí)間分別為1998年3月和1995年3月。
從總體上看，ijg-jpeg是具有工業(yè)強(qiáng)度的程序庫(kù)，被廣泛使用，久經(jīng)考驗(yàn)；而pvrg-jpeg是實(shí)驗(yàn)性的庫(kù)，主要用作研究。這兩個(gè)庫(kù)都很久沒(méi)有更新了，因?yàn)镴PEG標(biāo)準(zhǔn)已經(jīng)出臺(tái)10多年，庫(kù)的功能都穩(wěn)定了。從我閱讀的體驗(yàn)看，ijg-jpeg的代碼要復(fù)雜得多，也完善得多，代碼行數(shù)幾乎是pvrg-jpeg的三倍。ijg-jpeg代碼中大量使用了函數(shù)指針，因此光閱讀代碼往往不知道它調(diào)用的到底是哪個(gè)函數(shù)，它這么做是為了使用上的靈活性，同一步驟有多種實(shí)現(xiàn)（對(duì)應(yīng)多個(gè)函數(shù)），在運(yùn)行時(shí)選擇到底采用哪種實(shí)現(xiàn)，并把函數(shù)指針指向選定的函數(shù)。相比之下，pvrg-jpeg的代碼要直接了當(dāng)?shù)枚?，結(jié)構(gòu)也清晰得多。
我在VisualC++2005ExpressEdition中為兩個(gè)程序庫(kù)分別建立了調(diào)試環(huán)境，通過(guò)單步跟蹤確定ijg-jpeg到底調(diào)用哪個(gè)函數(shù)，在代碼中標(biāo)注出來(lái)，并歸納成圖表。以下主要分析ijg-jpeg，適當(dāng)輔以pvrg-jpeg。這兩個(gè)函數(shù)庫(kù)大體上都可分為編碼器和解碼器兩部分。
2.1ijg-jpeg實(shí)現(xiàn)分析
下面以ijg-jpeg自帶的testimg.bmp的壓縮過(guò)程（Huffman編碼使用缺省碼書(shū)）為例，介紹編碼器工作流程。ijg-jpeg編碼的總體流程為：1.預(yù)處理
(a)色彩空間轉(zhuǎn)換(b)邊界擴(kuò)展(c)下采樣2.JPEG壓縮
(a)DCT(b)量化
(c)“之”字型掃描(d)熵編碼
編碼主循環(huán)為：從輸入文件讀入一行行象素，送到編碼器中緩存起來(lái)，編碼器湊夠8行就進(jìn)行一次壓縮。
以上代碼片段來(lái)自ijg-jpeg中cjpeg.c文件的第579行至590行，位于函數(shù)main()中（后略）。第584行的src_mgr->get_pixel_rows是函數(shù)指針，根據(jù)輸入圖像文件類(lèi)型的不同指向不同的文件讀取函數(shù)。該函數(shù)的作用是讀取一行象素，象素的RGB值保存在數(shù)組src_mgr->buffer中，供jpeg_write_scanlines()使用。
而jpeg_write_scanlines()把實(shí)際工作都交給cinfo->main->process_data處理，這個(gè)函數(shù)指針只會(huì)指向process_data_simple_main()。
從這個(gè)函數(shù)可以看出，每讀入一行象素，就進(jìn)行一次預(yù)處理（第122行），放入緩沖區(qū)。如果緩沖區(qū)中的數(shù)據(jù)不夠8行則返回（第131行），否則就進(jìn)行壓縮（第135行）。
第122行的cinfo->prep->pre_process_data指向pre_process_data()。第135行的cinfo->coef->compress_data指向compress_data()。process_data_simple_main()的函數(shù)調(diào)用關(guān)系為（紅色方塊為函數(shù)指針，橢圓為普通函數(shù)）：
預(yù)處理
預(yù)處理在pre_process_data()中進(jìn)行，主要做色彩轉(zhuǎn)換、邊界擴(kuò)展、下采樣，它的函數(shù)調(diào)用關(guān)系為：
這個(gè)函數(shù)中只做了下邊界擴(kuò)展expand_bottom_edge()，而右邊界擴(kuò)展留在下采樣時(shí)進(jìn)行。
第145行的cinfo->cconvert->color_convert指向rgb_ycc_convert()。第163行的cinfo->downsample->downsample指向sep_downsample()。色彩轉(zhuǎn)換
RGB→YCbCr的色彩轉(zhuǎn)換由rgb_ycc_convert()負(fù)責(zé)，轉(zhuǎn)換公式在第3頁(yè)給出。這里為了加快速度，預(yù)先把乘積算出來(lái)存入9張表中“rgb_ycc_start()”，在轉(zhuǎn)換時(shí)只用查表操作。
擴(kuò)展邊界
在ijg-jpeg的具體實(shí)現(xiàn)中，它先擴(kuò)展每一行的右邊界“expand_right_edge()”，讓行的長(zhǎng)度（也就是圖像的寬度）等于8的倍數(shù)。然后在圖像底部填充一些行，擴(kuò)展其下邊界“expand_bottom_edge()”，讓整個(gè)圖像的高度是8的倍數(shù)。這樣得到擴(kuò)展之后的圖像，它的寬度和高度都是8的倍數(shù)，便于分塊。
下采樣
下采樣的工作由sep_downsample()分派給別的函數(shù)來(lái)做，第127行用到的downsample->methods[]是函數(shù)指針數(shù)組，指向各分量所用的下采樣函數(shù)。
亮度分量無(wú)需下采樣，于是調(diào)用fullsize_downsample()。色差分量有4:1:1和4:2:2兩種下采樣方式，分別對(duì)應(yīng)h2v2_downsample()和h2v1_downsample()。這里實(shí)際調(diào)用的是h2v2_downsample()。
fullsize_downsample()只是簡(jiǎn)單地將輸入拷貝到輸出，并做右邊界擴(kuò)展。
h2v2_downsample()把輸入圖像分量按2×2分塊，計(jì)算每塊樣本的平均值，送到輸出中（第272行）。這樣得到的樣本數(shù)為原來(lái)的1/4。
設(shè)輸入為N×M的RGB圖像，共有3MN個(gè)輸入樣本；經(jīng)過(guò)色彩轉(zhuǎn)換后，Y、Cr、Cb分量各有MN個(gè)樣本；再經(jīng)過(guò)下采樣，Y分量有MN個(gè)樣本，Cr、Cb分量各有大約
N2
·
M2個(gè)樣本。輸出樣本總數(shù)約為32MN，是輸入的一半。
預(yù)處理中的每一個(gè)步驟的計(jì)算復(fù)雜度都與輸入樣本的個(gè)數(shù)成正比，對(duì)于N×M的圖像，預(yù)處理的計(jì)算復(fù)雜度為O(MN)。
PEG壓縮
預(yù)處理之后，JPEG壓縮由compress_data()實(shí)現(xiàn)。它調(diào)用forward_DCT()做離散余弦變換和量化。它在調(diào)用forward_DCT()之前，會(huì)對(duì)各色彩分量進(jìn)行交織。所謂“交織”，就是說(shuō)不是壓縮完Y分量再壓縮Cr和Cb分量，而是每次從Y分量中選幾個(gè)塊，和Cr、Cb中選出的分塊組成MCU(MinimumCodedUnit，最小編碼單元)。然后對(duì)MCU中的分塊進(jìn)行DCT，再以MCU為單位進(jìn)行熵編碼。交織的主要目的是為了在解碼時(shí)能一邊解壓一邊顯示（或進(jìn)行后續(xù)處理），而不用等整幅圖片都解壓完才顯示。（光解出Y分量和Cr分量是無(wú)法顯示的。）
compress_data()然后調(diào)用encode_mcu_huff()對(duì)一個(gè)MCU進(jìn)行Huffman編碼。后者會(huì)對(duì)MCU中的各個(gè)分塊調(diào)用encode_one_block()，由它來(lái)進(jìn)行Huffman編碼，這個(gè)函數(shù)還順便進(jìn)行“之”字型掃描。
compress_data()的函數(shù)調(diào)用關(guān)系為：
第177行的cinfo->fdct->forward_DCT指向forward_DCT()。第204行的cinfo->entropy->encode_mcu指向encode_mcu_huff()。DCT與量化
forward_DCT把DCT運(yùn)算交給do_dct所指向的函數(shù)來(lái)做（第224行），它自己只做量化，這個(gè)函數(shù)的調(diào)用頻率非常高，所以寫(xiě)得很緊湊。
量化是整個(gè)JPEG壓縮中惟一用到除法的地方，而各種機(jī)器的整數(shù)除法略有區(qū)別，因此需要特殊對(duì)待，代碼中的注釋說(shuō)得很清楚了。通常C語(yǔ)言中的整數(shù)除法是向下取整，并非四舍五入，因此第253行和第257行先給被除數(shù)加上除數(shù)的一半，這樣就能實(shí)現(xiàn)四舍五入。
第224行的do_dct指向快速DCT的具體實(shí)現(xiàn)，ijg-jpeg提供有C.Loef?er、A.Ligtenberg、G.Moschytz等的實(shí)現(xiàn)（jpeg_fdct_islow）和Arai、Agui、Nakajima等的實(shí)現(xiàn)（jpeg_fdct_ifast）。這里實(shí)際調(diào)用的是jpeg_fdct_islow。這兩份實(shí)現(xiàn)都是就地(in-place)計(jì)算的，代碼從略。
forward_DCT()的運(yùn)行時(shí)間為常數(shù)，它被調(diào)用的次數(shù)等于輸入圖像的分塊數(shù)。對(duì)于N×M的圖像，DCT的計(jì)算復(fù)雜度為O(MN)。
在執(zhí)行完forward_DCT之后，就該做熵編碼了。
之”字型掃描與熵編碼
compress_data()在第204行通過(guò)函數(shù)指針encode_mcu調(diào)用encode_mcu_huff()進(jìn)行Huffman編碼。encode_mcu_huff()對(duì)MCU中的各個(gè)分塊調(diào)用encode_one_block()，“之”字型掃描和Huffman編碼的具體工作由后者完成。
錄
1
算法描述與比較
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
1.1
分塊及預(yù)處理
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
1.2
變換編碼
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
1.3
量化
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
1.4
行程編碼與熵編碼
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
2
實(shí)現(xiàn)細(xì)節(jié)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
2.1
ijg-jpeg
實(shí)現(xiàn)分析
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
2.1.1
預(yù)處理
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
2.1.2
色彩轉(zhuǎn)換
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
2.1.3
擴(kuò)展邊界
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
2.1.4
下采樣
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
2.1.5
JPEG
壓縮
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
17
2.1.6
DCT
與量化
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
2.1.7
“
之
”
字型掃描與熵編碼
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
20
2.1.8
量化表的縮放
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
2.2
pvrg-jpeg
實(shí)現(xiàn)分析
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
3
M
ATLAB
實(shí)現(xiàn)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
4
參考資料
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
