圖像壓縮的奧秘

1、圖像壓縮的奧秘David Austin關(guān)鍵詞： 圖像壓縮，應(yīng)用數(shù)學(xué)，快速算法本文所有文字的HTML文件大約有25000個(gè)字節(jié)。這小于你從這個(gè)網(wǎng)頁(yè)上下載的任何一個(gè)圖像文件。因?yàn)閳D像文件通常比文字文件大得多，并由于網(wǎng)頁(yè)包含許多常被傳送因而傳速變慢的圖像，將圖像以一種壓縮快送方式傳送變得非常重要。在這篇文章中我們將看到一個(gè)JPEG文件怎樣利用盡量小的計(jì)算機(jī)存儲(chǔ)來(lái)表示圖像。我們也將討論一些JPEG背后的數(shù)學(xué)。被更廣泛地稱為數(shù)據(jù)壓縮的論題問(wèn)的是：“我們?cè)鯓右跃o湊、有效的方式表示信息？”除了圖像文件外，通常要壓縮數(shù)據(jù)、影像、音樂(lè)文件。例如，如何壓縮8個(gè)GB的iPod Nano的2000首歌曲？問(wèn)

2、題的關(guān)鍵是通過(guò)某種方式組織信息，揭示出可被消除的固有的多余之處。在這篇文章中，我們將用下圖作為例子，探討JPEG基線壓縮算法（JPEG為“聯(lián)合圖像專家組”的英文單詞第一個(gè)字母組成的縮寫(xiě)）。一些壓縮算法是無(wú)損的，它們保留所有的原始信息。其他的一些，如JPEG基線算法，是有損的，某些信息會(huì)被丟失，但僅僅是那些被判斷為不重要的信息。在著手之前，我們先天真地確定這張圖需要多少計(jì)算機(jī)存儲(chǔ)。首先，圖像被布置在一個(gè)矩形的像素網(wǎng)格，其尺寸為250×375，總共有93750像素。各像素的顏色通過(guò)指定多少比例的紅、綠和藍(lán)色的顏色混合在一起來(lái)確定。每個(gè)顏色分量被表示為0和255之間的一個(gè)整數(shù)，因此需要一個(gè)

3、字節(jié)的計(jì)算機(jī)存儲(chǔ)。因此，每個(gè)像素需要3個(gè)字節(jié)的存儲(chǔ)空間，這意味著整個(gè)圖像應(yīng)該要求93750×3=281250字節(jié)。然而，這里顯示的JPEG圖只有32414個(gè)字節(jié)，換言之，它已被壓縮了大約9倍。我們將描述怎樣用壓縮過(guò)的小文件表示圖像，并怎樣從被壓縮的文件重構(gòu)圖像。壓縮算法首先，圖像被分成8×8的塊狀像素。因?yàn)槊恳粔K都與其他塊無(wú)關(guān)地被處理，我們集中討論單獨(dú)一塊。特別，我們考察下圖中劃出陰影的那一塊。這里是同一小塊放大后的樣子，其中每個(gè)像素看上去更明顯。注意所有8×8像素之間沒(méi)有太大的變化（但其他塊則不一定）。記得數(shù)據(jù)壓縮的目的是以揭示一些多余性的方式表達(dá)數(shù)據(jù)。我們可以

4、想到把每個(gè)像素的顏色表示為由紅、綠、藍(lán)分量組成的一個(gè)三維向量(R,G,B)。在典型的圖像中，這些分量之間有巨大的相關(guān)性。由于這個(gè)理由，我們將使用一個(gè)顏色空間變換，它產(chǎn)生一個(gè)新的向量，其分量代表亮度Y及藍(lán)色和紅色的色度，分別記為Cb和Cr：YCbCr=0.299000.168740.500000.587000.331260.418690.114000.500000.08131RGB.亮度描述了像素的光亮性，而色度則攜帶有關(guān)色調(diào)的信息。這三個(gè)量通常比(R,G,B)的分量的相關(guān)性低。此外，心理視覺(jué)實(shí)驗(yàn)表明，人的眼睛對(duì)亮度比色度更加敏感，這意味著我們可以忽視色度較大的變化，而不會(huì)影響我們對(duì)圖像的感知。

5、由于這種轉(zhuǎn)變是可逆的，我們將能夠從向量(Y,Cb,Cr)恢復(fù)向量(R,G,B)。當(dāng)我們希望重建圖像時(shí)，這是很重要的。（確切地說(shuō)，我們通常會(huì)讓色度分量加上128，使得它們表示為0和255之間的數(shù)。）當(dāng)我們將這種變換用到我們的塊中的每個(gè)像素后，我們得到對(duì)應(yīng)于每個(gè)分量的三個(gè)新塊。這些由下圖所示，較亮的像素對(duì)應(yīng)較大的值。如通常所見(jiàn)的，亮度比色度具有較多的變化。由此緣故，通過(guò)假設(shè)色度在2×2小塊上為常數(shù)，有時(shí)可以得到較大的壓縮比，因此記錄較少的值。例如，圖像編輯軟件Gimp當(dāng)將一個(gè)圖像存為JPEG文件時(shí)，提供了以下的菜單：“Subsampling”選項(xiàng)允許抽取色度值不同方式的選擇。這里同樣值得

6、注意的是“Quality”參數(shù)，它的重要性在下面將變得很清楚。離散余弦變換現(xiàn)在我們到達(dá)壓縮算法的核心。我們的期望是，這塊8×8像素上向量(Y,Cb,Cr)分量的變化相當(dāng)溫和，如上例所示。我們不記錄各個(gè)分量的值，而是記錄比方說(shuō)平均值以及每個(gè)像素值與平均值相差多少。在許多情況下，我們能期待與這些平均值的差相當(dāng)小，因此可以安全地忽略。這是現(xiàn)在將要解釋的離散余弦變換(DCT)的本質(zhì)。我們先集中于這塊中某一行的三個(gè)分量當(dāng)中的一個(gè)，想象這8個(gè)值由f0,f1,f7代表。我們想以某種方式表示這些值使得它們的變化變得更明顯。為此，我們把這些值視為由一個(gè)函數(shù)fx給出，其中x從0到7之間取值，并把該函數(shù)寫(xiě)

7、出余弦函數(shù)的一個(gè)線性組合：fx=12w=07CwFwcos(2x+1)w16.不要擔(dān)心Cw（除了C0=1/2外，對(duì)所有w都有Cw=1）前面的因子1/2。這個(gè)表達(dá)式的重要之處在于它把fx用具有變化的頻率、帶有系數(shù)Fw的余弦函數(shù)的一個(gè)線性組合來(lái)表示。下圖顯示的是對(duì)應(yīng)于頻率w的其中4個(gè)余弦函數(shù)的圖像：當(dāng)然，具有較高頻率的余弦函數(shù)顯示了更快的變化。因此，如果值fx相對(duì)慢地改變，較大頻率的系數(shù)Fw將相對(duì)小。故我們可以不記錄這些系數(shù)以便減少圖像文件的尺寸。這些DCT系數(shù)可以通過(guò)利用反變換Fw=12Cwx=07fxcos(2x+1)w16得到。注意這隱含DCT是可逆的。例如，我們從fx開(kāi)始，記錄Fw。然而，

8、當(dāng)我們希望重建圖像時(shí)，我們將有Fw，并重新計(jì)算fx。我們并不是僅僅對(duì)每塊的行運(yùn)用DCT，而是將探討圖像的二維特性。離散余弦變換首先用到我們這塊像素的所有行。如果在垂直方向上圖像變化不是太快的話，系數(shù)的變化亦然。由此原因，我們可以固定w的一個(gè)值，把離散余弦變換運(yùn)用到從8行像素得到的8個(gè)Fw值。這導(dǎo)致了系數(shù)Fw,u，其中w是水平頻率，u是垂直頻率。我們把這些系數(shù)存到下圖所示的另一個(gè)8×8塊中。注意到在該塊中向下和向右移動(dòng)時(shí)，我們遇到較高頻率的系數(shù)，它們的重要性如所期望地將變小。DCT系數(shù)可由快速離散余弦變換有效地計(jì)算，這與用快速傅里葉變換有效計(jì)算離散傅里葉系數(shù)具有同一思想。量化當(dāng)然，系數(shù)

9、Fw,u是實(shí)數(shù)，存儲(chǔ)為整數(shù)。這意味著我們需要將系數(shù)四舍五入；我們的舍入方法有利于更大的壓縮。我們不是僅僅簡(jiǎn)單地四舍五入系數(shù)Fw,u，而是用一個(gè)量化因子除它，然后記錄round(Fw,u/Qw,u).這容許我們對(duì)另一些頻率而言更有所強(qiáng)調(diào)。更具體地說(shuō)，人類的眼睛對(duì)圖像的迅速變化并不敏感。這意味著，通過(guò)對(duì)高頻選擇一個(gè)較大的量化因子，我們可以降低較高頻率的重要性。這樣做并不會(huì)顯著地影響圖像的視覺(jué)質(zhì)量。當(dāng)一個(gè)JPEG文件被產(chǎn)生后，算法訴諸一個(gè)參數(shù)來(lái)控制圖像質(zhì)量及圖像的壓縮比例。我們稱為q的這個(gè)參數(shù)是從1到100的一個(gè)整數(shù)。你應(yīng)該把q看成圖像質(zhì)量的一個(gè)測(cè)度：較高的q值對(duì)應(yīng)于較高質(zhì)量的圖像和較大的文件尺寸。

10、q產(chǎn)生了另一個(gè)量=50q250qif1q50if50q100.下面是作為q的函數(shù)的圖像：注意較大的q值給出較小的值。然后我們將權(quán)舍入成round(Fw,u/Qw,u).自然地，通過(guò)這個(gè)舍入過(guò)程，信息將被失去。當(dāng)或Qw,u增加時(shí)（記得較大的值對(duì)應(yīng)于較小的質(zhì)量參數(shù)q值），更多的信息失去了，且文件尺寸也減少。這里是JPEG標(biāo)準(zhǔn)所推薦的典型Qw,u值。比如考慮亮度系數(shù)：和色度系數(shù)：這些值被選取以強(qiáng)調(diào)較小頻率的影響。讓我們看看這在上面的例子中怎樣工作。記得我們有下面的三塊數(shù)值：用q=50量化，得到下面的三塊：左上角的元素本質(zhì)上表示了整塊的平均。向右移增加水平頻率，而向下移增加垂直頻率。這里重要之處是有許

11、多個(gè)0?，F(xiàn)在我們按如下方式對(duì)系數(shù)排序，使得較小的頻率首先出現(xiàn)。對(duì)亮度系數(shù)，我們可以簡(jiǎn)記為20711011000000021100000.我們不必把所有的0都記下，而只需告訴多少0出現(xiàn)（注意在色度權(quán)中有更多的0）。以這種方式，DCT系數(shù)的序列大大地縮短了，而這就是壓縮算法的目的。事實(shí)上，JPRG算法運(yùn)用特別有效的方法像這樣對(duì)序列譯碼。當(dāng)重建DCT系數(shù)時(shí)，我們發(fā)現(xiàn)從信息中重建圖像是相當(dāng)直接的。量化矩陣存儲(chǔ)在文件中，故DCT系數(shù)的近似值可被重新計(jì)算出。從這里，向量(Y,Cb,Cr)通過(guò)逆離散余弦變換而找到。然后，向量(R,G,B)通過(guò)對(duì)顏色空間變換求逆而再次獲得。這里是取q=50的8×8像

12、素塊的重建：下圖的重建是當(dāng)質(zhì)量參數(shù)q=10時(shí)的情形。如所期待的，較高的參數(shù)q值給出較高質(zhì)量的圖像。JPEG 2000雖然JPEG壓縮算法已經(jīng)取得相當(dāng)?shù)某晒Γ袔讉€(gè)因素導(dǎo)致了我們構(gòu)造新算法的想法。下面描述其中的兩個(gè)因素。首先，DCT在JPEG算法中的運(yùn)用導(dǎo)致8×8像素塊之間邊界的不連續(xù)性。例如，在某塊邊緣處的一個(gè)像素的顏色可以被該塊中任何地方的其他像素的顏色所影響，但卻不會(huì)被臨近的其他塊的像素左右。這導(dǎo)致了阻礙之物，可從從質(zhì)量參數(shù)設(shè)置為q=5所得到的圖像上看出來(lái)（順提一句，該圖像文件的尺寸僅為1702比特），也解釋了為何JPEG不是存儲(chǔ)線狀藝術(shù)的理想形式。此外，JPEG算法只允許我們以

13、一種分辨率恢復(fù)圖像。在一些例子中，希望的是以低分辨率恢復(fù)圖像，同時(shí)允許在整個(gè)圖像被下載過(guò)程中以逐步提高的分辨率展示圖像。為了這些及其他需要，JPEG 2000標(biāo)準(zhǔn)于2000年12月推出。雖然這兩個(gè)算法之間有些不同，我們集中于這個(gè)事實(shí)：JPEG 2000用小波變換取代了DCT。在解釋用于JPEG 2000的小波變換之前，我們考慮小波變換的一個(gè)較簡(jiǎn)單的例子。如前一樣，想象我們與每個(gè)像素的亮度-色度值打交道。DCT把其變換每次用到一行，然后變換列。小波變換將以類似方式工作。為此目的，我們想象有一個(gè)序列f0,f1,fn描繪像素中一行三個(gè)分量之一的值。與以前一樣，我們想將序列中的快速變化與緩慢變化分別開(kāi)

14、來(lái)。為此目的，我們產(chǎn)生一個(gè)小波系數(shù)序列：a0=(f0+f1)/2a1=(f0f1)/2a2=(f2+f3)/2a3=(f2f3)/2=注意到偶數(shù)下標(biāo)系數(shù)記錄了兩個(gè)相鄰值的平均數(shù)-我們把此稱為低通過(guò)帶，因?yàn)楦哳l率變化的信息喪失-而奇數(shù)下標(biāo)系數(shù)記錄了兩個(gè)相鄰值的差-我們把此稱為高通過(guò)帶，因?yàn)楦哳l率信息通過(guò)。低通過(guò)系數(shù)的個(gè)數(shù)為原先序列中值的個(gè)數(shù)的一半（和高通過(guò)系數(shù)一樣）。重要的是注意到我們能夠從小波系數(shù)恢復(fù)原先的f值，因?yàn)楫?dāng)我們重建圖像是需要這樣做的：f0=a0+a1f1=a0a1我們重新排序小波系數(shù)，把低通過(guò)系數(shù)列在高通過(guò)系數(shù)之前。恰如在二維DCT的情形，我們現(xiàn)在可以把同樣的運(yùn)算垂直地變換小波系數(shù)

15、。這導(dǎo)致小波系數(shù)的二維網(wǎng)格，通過(guò)低通過(guò)帶和高通過(guò)帶分成四塊：如前，我們利用人類的眼睛對(duì)圖像的迅速變化并不敏感這一事實(shí)，通過(guò)與在JPEG算法里見(jiàn)到的類似的量化過(guò)程，讓在高通過(guò)系數(shù)中見(jiàn)到的迅速變化不顯重要性。注意LL區(qū)域由2×2像素塊中的值的平均化得到，因此表示了圖像的一個(gè)低分辨率版本。在實(shí)際中，我們的圖像被分成許多瓦片，通常具有尺寸64×64。選擇2的冪次的理由馬上就會(huì)明了。我們將用這里指定了瓦片的圖像來(lái)說(shuō)明之。（這個(gè)瓦片是128×128，故在此網(wǎng)頁(yè)上可以更清楚地看到。）注意，如果首先在LL區(qū)域傳遞系數(shù)，我們能在所有系數(shù)已經(jīng)到達(dá)之前低分辨率地重建圖像，這是JPEG

16、2000算法的目的之一。我們現(xiàn)在能在LL區(qū)域內(nèi)對(duì)低分辨率圖像執(zhí)行同樣的運(yùn)算，因而得到越來(lái)越低的分辨率圖像。小波系數(shù)可以通過(guò)如下的提升過(guò)程計(jì)算：a0=(f0+f1)/2,   a1=a0f1,其益處是不必占用額外的計(jì)算機(jī)內(nèi)存計(jì)算這些系數(shù)-a0首先取代f0，然后，a1取代f1。并且，JPEG2000算法所運(yùn)用的小波變換中，提升運(yùn)算使得系數(shù)的計(jì)算更快。JPEG 2000小波變換上面描述的小波變換雖然與JPEG 2000標(biāo)準(zhǔn)中的小波變換精神相似，但比后者簡(jiǎn)單。例如，有必要對(duì)兩次以上逐次得到的值再平均，以便重建的圖像具有更大的連續(xù)性，因此避免像阻礙物這樣的現(xiàn)象。用到的一種小波變換是Le Gall(5,3)樣條，其中低通過(guò)（偶）和高通過(guò)（奇）系數(shù)由下式計(jì)算：a0=18f2+14f1+34f018f1,a1=12f1+f012f1.和前面一樣，這個(gè)變換是可逆的，且存在提升方案使之有效運(yùn)行。包含在標(biāo)準(zhǔn)中的另一個(gè)小波變換是Cohen-Daubechies-Faura