圖像壓縮的奧秘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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