幾種圖像壓縮算法

1、關(guān)于幾種圖像壓縮算法第1頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四1. 圖像數(shù)據(jù)壓縮方法的分類數(shù)據(jù)壓縮的任務(wù)在不影響或少影響圖像質(zhì)量的前提下，盡量設(shè)法減少圖像數(shù)據(jù)中的數(shù)據(jù)量。其首要任務(wù)是設(shè)法去掉各種冗余的數(shù)據(jù)。第2頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四數(shù)據(jù)壓縮實(shí)際是一個(gè)編碼的過(guò)程，即將原始數(shù)據(jù)進(jìn)行編碼壓縮。數(shù)據(jù)解壓縮是數(shù)據(jù)壓縮的逆過(guò)程，即將經(jīng)過(guò)壓縮的數(shù)據(jù)還原成原始數(shù)據(jù)。因此數(shù)據(jù)壓縮方法也稱編碼方法。評(píng)價(jià)壓縮方法的優(yōu)劣主要從以下3個(gè)方面來(lái)衡量。第3頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四（1）壓縮比：壓縮比指原始圖像經(jīng)A/D轉(zhuǎn)換后未經(jīng)壓縮所產(chǎn)

2、生的數(shù)據(jù)量與經(jīng)壓縮所產(chǎn)生的數(shù)據(jù)量之比。（2）圖像質(zhì)量：還原出來(lái)的圖像質(zhì)量比原始圖像有多大失真，一般采用人的視覺效果和信噪比兩個(gè)方法。前者是通過(guò)人在兩米內(nèi)觀察所作的評(píng)價(jià)，后者通過(guò)儀器測(cè)量。第4頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四（3）實(shí)現(xiàn)難度：即實(shí)現(xiàn)壓縮及還原算法的難易程度，亦即完成壓縮所需要的時(shí)間與空間開銷或硬件實(shí)現(xiàn)的復(fù)雜性。壓縮的方法主要有以下幾種（見圖3.3）。 第5頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第6頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四無(wú)損編碼可以完全恢復(fù)原始圖像而不引入失真，它利用數(shù)據(jù)的統(tǒng)計(jì)特性來(lái)進(jìn)行數(shù)據(jù)壓縮，解壓縮

3、后的還原圖像與原始圖像完全一致。有損編碼不能完全恢復(fù)原始數(shù)據(jù)，而是利用人的視覺特性使解壓縮后的圖像和原來(lái)一樣。把上述方法結(jié)合起來(lái)即為混合方法。下面介紹幾種常用的壓縮方法。第7頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四2 霍夫曼編碼霍夫曼編碼是無(wú)損編碼的一種，是一種基于統(tǒng)計(jì)特性的可變字長(zhǎng)的編碼方法。屬于無(wú)損編碼的還有行程編碼、算術(shù)編碼等。下面來(lái)看霍夫曼編碼。第8頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四設(shè)被編碼的符號(hào)如下。s1，s2，s3，sn它們出現(xiàn)的概率分別為：p1，p2，p3，pn假設(shè)采用不等字長(zhǎng)編碼，每個(gè)符號(hào)的碼長(zhǎng)分別為：m1，m2，m3，mn第9頁(yè)，共3

4、3頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第10頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四數(shù)學(xué)上可以證明，符號(hào)序列 si 的任何一種編碼方案，其平均碼長(zhǎng)必定大于或等于H。也就是說(shuō)，H是該符號(hào)序列的理想最小平均碼長(zhǎng)。平均碼長(zhǎng)越接近H，我們說(shuō)該編碼方案越好。第11頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四數(shù)學(xué)上還可以證明，在可變字長(zhǎng)編碼中，對(duì)于出現(xiàn)概率大的符號(hào)編碼成短字長(zhǎng)的編碼，對(duì)于概率小的符號(hào)，編以較長(zhǎng)的字長(zhǎng)編碼。如果碼字長(zhǎng)嚴(yán)格按照所對(duì)應(yīng)符號(hào)的出現(xiàn)概率的大小逆序列排列，則平均碼長(zhǎng)一定小于其他任何符號(hào)順序方式，即這是一種最接近于熵值的“最佳編碼”?；舴蚵幋a

5、是實(shí)現(xiàn)上述最佳編碼的一種算法。下面看一個(gè)示例。第12頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四大部分?jǐn)?shù)字信息的編碼都是采用定長(zhǎng)編碼。意即采用相同的位數(shù)對(duì)數(shù)據(jù)進(jìn)行編碼。如常用的ASCII就是定長(zhǎng)編碼，它用7位二進(jìn)制數(shù)來(lái)表示每一個(gè)字符。但是實(shí)際上在文章中每個(gè)字符出現(xiàn)的概率并不相等。我們現(xiàn)在假設(shè)有a，b，c，d，e 5個(gè)字符。其出現(xiàn)概率分別為0.12,0.40,0.15, 0.08，0.25。用以下方法來(lái)求得其霍夫曼編碼。第13頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四將5個(gè)字符按其概率大小排序，然后把最小的兩項(xiàng)的概率值相加，歸并成新的一項(xiàng)。然后再選最小的兩項(xiàng)合并，一

6、直重復(fù)作到只剩最后一項(xiàng)為止。本例實(shí)現(xiàn)過(guò)程參見圖3.4。下面再來(lái)構(gòu)造霍夫曼編碼樹。這是一棵二叉樹，我們從圖3.5中的右方開始向左取值，根結(jié)點(diǎn)概率為1.0，以下左分枝取概率小的項(xiàng)，右分枝取概率大的項(xiàng)。對(duì)于歸并項(xiàng)，按此規(guī)則一直分解到最右方為止。如圖3.5所示為構(gòu)造好的霍夫曼編碼樹。第14頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第15頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第16頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四如圖3.5所示，我們給每個(gè)左分枝標(biāo)以0，給每個(gè)右分枝標(biāo)以1，則從根結(jié)點(diǎn)至每個(gè)葉結(jié)點(diǎn)的路徑即為該葉結(jié)點(diǎn)代表字符的編碼。如圖3.5右方所

7、示。本例中熵的值為2.09，編碼的平均碼長(zhǎng)為2.15，非常接近。霍夫曼編碼的優(yōu)點(diǎn)是簡(jiǎn)單易行，缺點(diǎn)是解碼時(shí)必須知道所使用的碼表，這給存儲(chǔ)和通信帶來(lái)不便。另一個(gè)缺點(diǎn)是它依賴于原始數(shù)據(jù)的概率，這在實(shí)際應(yīng)用中受到許多限制。第17頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四 編碼實(shí)例(16色bmp數(shù)據(jù))：第一行：24 24 24 30 60 40 09 224646第二行：64 65 67 88 88 88 88 90 7800 00：表示該行圖像數(shù)據(jù)已結(jié)束00 01：表示整個(gè)圖像結(jié)束00 02：用來(lái)轉(zhuǎn)義后面兩個(gè)字節(jié)，即表示其后的兩個(gè)字節(jié)分別表示下一個(gè)像素從當(dāng)前位置開始的水平與垂直位移00

8、 N：表示從當(dāng)前位置起，圖像數(shù)據(jù)存在連續(xù)N個(gè)不同的值（存放于N/2個(gè)字節(jié)中）3.行程長(zhǎng)度編碼5個(gè)第18頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四行程編碼原理在給定的圖像數(shù)據(jù)中尋找連續(xù)重復(fù)的數(shù)值，然后用兩個(gè)字符值取代這些連續(xù)值“aaabbbbccccddd”=”3a4b4c3d”處理包含大量重復(fù)信息時(shí)可以得到很好的壓縮效率，但在連續(xù)重復(fù)數(shù)據(jù)少時(shí)效果差PCX圖像文件的RLE壓縮算法第19頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四4 預(yù) 測(cè) 編 碼預(yù)測(cè)編碼用于圖像編碼時(shí)與聲音的壓縮編碼很類似，它也是根據(jù)過(guò)去已編碼的像素（也稱為參考像素）來(lái)預(yù)測(cè)當(dāng)前的像素值（稱為預(yù)測(cè)值）

9、，然后對(duì)當(dāng)前的像素值與預(yù)測(cè)值之差進(jìn)行編碼，這就是差分編碼（DPCM）。這種編碼是利用圖像本身的相關(guān)性及視覺的差值靈敏度特性，差值大時(shí)，可以粗量化。圖像編碼用地較多的是二維預(yù)測(cè)，如圖3.6所示。第20頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四第21頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四LZW壓縮算法 LZW壓縮算法是一種新穎的壓縮方法，由Lemple-Ziv-Welch 三人共同創(chuàng)造，用他們的名字命名。它采用了一種先進(jìn)的串表壓縮，將每個(gè)第一次出現(xiàn)的串放在一個(gè)串表中，用一個(gè)數(shù)字來(lái)表示串，壓縮文件只存貯數(shù)字，則不存貯串，從而使圖象文件的壓縮效率得到較大的提高。奇妙

10、的是，不管是在壓縮還是在解壓縮的過(guò)程中都能正確的建立這個(gè)串表，壓縮或解壓縮完成后，這個(gè)串表又被丟棄。第22頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四LZW算法中，首先建立一個(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來(lái)表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，并將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來(lái)代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。如print 字符串，如果在壓縮時(shí)用266表示，只要再次出現(xiàn)，均用266表示，并將print字符串存入串表中，在圖象解碼時(shí)遇到數(shù)字266，即可從串表中查出266所代表的字符串pr

11、int，在解壓縮時(shí)，串表可以根據(jù)壓縮數(shù)據(jù)重新生成。第23頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四壓縮算法的簡(jiǎn)單示例 對(duì)原始數(shù)據(jù)ABCCAABCDDAACCDB進(jìn)行LZW壓縮 原始數(shù)據(jù)中，只包括4個(gè)字符(Character),A,B,C,D,四個(gè)字符可以用一個(gè)2bit的數(shù)表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復(fù)字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,第24頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四JPEG編碼二、JPEG算法的主要計(jì)算步驟 JPEG壓

12、縮編碼算法的主要計(jì)算步驟如下： （1）正向離散余弦變換（FDCT）。 （2）量化（Quantization）。 （3）Z字形編碼（Zigzag Scan）。 （4）使用差分脈沖編碼調(diào)制（Differential Pulse Code Modulation，DPCM)對(duì)直流系數(shù)(DC)進(jìn)行編碼。 （5）使用行程長(zhǎng)度編碼（Run-Length Encoding，RLE）對(duì)交流系數(shù)（AC）進(jìn)行編碼。 （6）熵編碼（Entropy Eoding）。 第25頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四1.正向離散余弦變換 （1）對(duì)每個(gè)單獨(dú)的彩色圖像分量，把整個(gè)分量圖像分成若干個(gè)88的圖像塊

13、，如圖所示，并作為兩維離散余弦變換DCT的輸入。通過(guò)DCT變換，把能量集中在少數(shù)幾個(gè)系數(shù)上。（2）DCT變換使用下式計(jì)算： 它的逆變換使用下式計(jì)算： 上面兩式中， C(u)，C(v) = (2)-1/2，當(dāng)u, v = 0； C(u)，C(v) = 1，其他。 f(i, j)經(jīng)DCT變換之后，F(xiàn)(0，0)是直流系數(shù)，其他為交流系數(shù)。（3）在計(jì)算兩維的DCT變換時(shí)，可使用下面的計(jì)算式把兩維的DCT變換變成一維的DCT變換： 第26頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四2、量化 量化是對(duì)經(jīng)過(guò)FDCT變換后的頻率系數(shù)進(jìn)行量化。量化的目的是減小非“0”系數(shù)的幅度以及增加“0”值系數(shù)

14、的數(shù)目。量化是圖像質(zhì)量下降的最主要原因。 對(duì)于有損壓縮算法，JPEG算法使用如下圖所示的均勻量化器進(jìn)行量化，量化步距是按照系數(shù)所在的位置和每種顏色分量的色調(diào)值來(lái)確定。因?yàn)槿搜蹖?duì)亮度信號(hào)比對(duì)色差信號(hào)更敏感，因此使用了兩種量化表：亮度量化值和色差量化值。此外，由于人眼對(duì)低頻分量的圖像比對(duì)高頻分量的圖像更敏感，因此圖中的左上角的量化步距要比右下角的量化步距小。下面2個(gè)表中的數(shù)值對(duì)CCIR 601標(biāo)準(zhǔn)電視圖像已經(jīng)是最佳的。如果不使用這兩種表，你也可以把自己的量化表替換它們。 亮度量化值表和色度量化值表 第27頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四3、Z字形編排 量化后的系數(shù)要重新編

15、排，目的是為了增加連續(xù)的“0”系數(shù)的個(gè)數(shù)，就是“0”的游程長(zhǎng)度，方法是按照Z(yǔ)字形的式樣編排，如下圖所示。這樣就把一個(gè)88的矩陣變成一個(gè)164的矢量，頻率較低的系數(shù)放在矢量的頂部。 量化DCT系數(shù)序號(hào) 0 1 5 6 14 15 27 25 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63 第28頁(yè)，共33頁(yè)，2022年，5月

16、20日，10點(diǎn)49分，星期四4、直流系數(shù)的編碼 88圖像塊經(jīng)過(guò)DCT變換之后得到的DC直流系數(shù)有兩個(gè)特點(diǎn)，一是系數(shù)的數(shù)值比較大，二是相鄰88圖像塊的DC系數(shù)值變化不大。根據(jù)這個(gè)特點(diǎn)，JPEG算法使用了差分脈沖調(diào)制編碼（DPCM）技術(shù)，對(duì)相鄰圖像塊之間量化DC系數(shù)的差值（Delta）進(jìn)行編碼。 DeltaDC(0,0)k-DC(0,0)k-1 第29頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四5、 交流系數(shù)的編碼 量化AC系數(shù)的特點(diǎn)是164矢量中包含有許多“0”系數(shù)，并且許多“0”是連續(xù)的，因此使用非常簡(jiǎn)單和直觀的游程長(zhǎng)度編碼(RLE)對(duì)它們進(jìn)行編碼。 JPEG使用了1個(gè)字節(jié)的高4位來(lái)表示連續(xù)“0”的個(gè)數(shù)，而使用它的低4位來(lái)表示編碼下一個(gè)非“0”系數(shù)所需要的位數(shù)，跟在它后面的是量化AC系數(shù)的數(shù)值。 第30頁(yè)，共33頁(yè)，2022年，5月20日，10點(diǎn)49分，星期四6、熵編碼 使用熵編碼還可以對(duì)DPCM編碼后的直流DC系數(shù)和RLE編碼后的交流AC系數(shù)作進(jìn)一步的壓縮。 在JPEG有損壓縮算法中，使用霍夫曼編碼器來(lái)減少熵。使用霍夫曼編碼器的理由是可以使用很簡(jiǎn)單的查表（Lookup Table）方法進(jìn)行編碼。壓縮數(shù)據(jù)符號(hào)時(shí)，霍夫曼編碼器對(duì)出現(xiàn)頻度比較高的符號(hào)分配比較短的代碼，