幾種圖像壓縮算法

關(guān)于幾種圖像壓縮算法第1頁，課件共33頁，創(chuàng)作于2023年2月1.圖像數(shù)據(jù)壓縮方法的分類 數(shù)據(jù)壓縮的任務(wù)在不影響或少影響圖像質(zhì)量的前提下，盡量設(shè)法減少圖像數(shù)據(jù)中的數(shù)據(jù)量。其首要任務(wù)是設(shè)法去掉各種冗余的數(shù)據(jù)。第2頁，課件共33頁，創(chuàng)作于2023年2月數(shù)據(jù)壓縮實(shí)際是一個(gè)編碼的過程，即將原始數(shù)據(jù)進(jìn)行編碼壓縮。數(shù)據(jù)解壓縮是數(shù)據(jù)壓縮的逆過程，即將經(jīng)過壓縮的數(shù)據(jù)還原成原始數(shù)據(jù)。因此數(shù)據(jù)壓縮方法也稱編碼方法。評(píng)價(jià)壓縮方法的優(yōu)劣主要從以下3個(gè)方面來衡量。第3頁，課件共33頁，創(chuàng)作于2023年2月（1）壓縮比：壓縮比指原始圖像經(jīng)A/D轉(zhuǎn)換后未經(jīng)壓縮所產(chǎn)生的數(shù)據(jù)量與經(jīng)壓縮所產(chǎn)生的數(shù)據(jù)量之比。（2）圖像質(zhì)量：還原出來的圖像質(zhì)量比原始圖像有多大失真，一般采用人的視覺效果和信噪比兩個(gè)方法。前者是通過人在兩米內(nèi)觀察所作的評(píng)價(jià)，后者通過儀器測(cè)量。第4頁，課件共33頁，創(chuàng)作于2023年2月（3）實(shí)現(xiàn)難度：即實(shí)現(xiàn)壓縮及還原算法的難易程度，亦即完成壓縮所需要的時(shí)間與空間開銷或硬件實(shí)現(xiàn)的復(fù)雜性。壓縮的方法主要有以下幾種（見圖3.3）。第5頁，課件共33頁，創(chuàng)作于2023年2月第6頁，課件共33頁，創(chuàng)作于2023年2月無損編碼可以完全恢復(fù)原始圖像而不引入失真，它利用數(shù)據(jù)的統(tǒng)計(jì)特性來進(jìn)行數(shù)據(jù)壓縮，解壓縮后的還原圖像與原始圖像完全一致。有損編碼不能完全恢復(fù)原始數(shù)據(jù)，而是利用人的視覺特性使解壓縮后的圖像和原來一樣。把上述方法結(jié)合起來即為混合方法。下面介紹幾種常用的壓縮方法。第7頁，課件共33頁，創(chuàng)作于2023年2月2霍夫曼編碼 霍夫曼編碼是無損編碼的一種，是一種基于統(tǒng)計(jì)特性的可變字長(zhǎng)的編碼方法。屬于無損編碼的還有行程編碼、算術(shù)編碼等。下面來看霍夫曼編碼。第8頁，課件共33頁，創(chuàng)作于2023年2月設(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頁，課件共33頁，創(chuàng)作于2023年2月第10頁，課件共33頁，創(chuàng)作于2023年2月 數(shù)學(xué)上可以證明，符號(hào)序列{si}的任何一種編碼方案，其平均碼長(zhǎng)必定大于或等于H。也就是說，H是該符號(hào)序列的理想最小平均碼長(zhǎng)。平均碼長(zhǎng)越接近H，我們說該編碼方案越好。第11頁，課件共33頁，創(chuàng)作于2023年2月數(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)順序方式，即這是一種最接近于熵值的“最佳編碼”。霍夫曼編碼是實(shí)現(xiàn)上述最佳編碼的一種算法。下面看一個(gè)示例。第12頁，課件共33頁，創(chuàng)作于2023年2月大部分?jǐn)?shù)字信息的編碼都是采用定長(zhǎng)編碼。意即采用相同的位數(shù)對(duì)數(shù)據(jù)進(jìn)行編碼。如常用的ASCII就是定長(zhǎng)編碼，它用7位二進(jìn)制數(shù)來表示每一個(gè)字符。但是實(shí)際上在文章中每個(gè)字符出現(xiàn)的概率并不相等。我們現(xiàn)在假設(shè)有a，b，c，d，e5個(gè)字符。其出現(xiàn)概率分別為0.12,0.40,0.15,0.08，0.25。用以下方法來求得其霍夫曼編碼。第13頁，課件共33頁，創(chuàng)作于2023年2月將5個(gè)字符按其概率大小排序，然后把最小的兩項(xiàng)的概率值相加，歸并成新的一項(xiàng)。然后再選最小的兩項(xiàng)合并，一直重復(fù)作到只剩最后一項(xiàng)為止。本例實(shí)現(xiàn)過程參見圖3.4。下面再來構(gòu)造霍夫曼編碼樹。這是一棵二叉樹，我們從圖3.5中的右方開始向左取值，根結(jié)點(diǎn)概率為1.0，以下左分枝取概率小的項(xiàng)，右分枝取概率大的項(xiàng)。對(duì)于歸并項(xiàng)，按此規(guī)則一直分解到最右方為止。如圖3.5所示為構(gòu)造好的霍夫曼編碼樹。第14頁，課件共33頁，創(chuàng)作于2023年2月第15頁，課件共33頁，創(chuàng)作于2023年2月第16頁，課件共33頁，創(chuàng)作于2023年2月如圖3.5所示，我們給每個(gè)左分枝標(biāo)以0，給每個(gè)右分枝標(biāo)以1，則從根結(jié)點(diǎn)至每個(gè)葉結(jié)點(diǎn)的路徑即為該葉結(jié)點(diǎn)代表字符的編碼。如圖3.5右方所示。本例中熵的值為2.09，編碼的平均碼長(zhǎng)為2.15，非常接近?；舴蚵幋a的優(yōu)點(diǎn)是簡(jiǎn)單易行，缺點(diǎn)是解碼時(shí)必須知道所使用的碼表，這給存儲(chǔ)和通信帶來不便。另一個(gè)缺點(diǎn)是它依賴于原始數(shù)據(jù)的概率，這在實(shí)際應(yīng)用中受到許多限制。第17頁，課件共33頁，創(chuàng)作于2023年2月編碼實(shí)例(16色bmp數(shù)據(jù))：第一行：2424243060400922…46…46第二行：64656788888888…90780000：表示該行圖像數(shù)據(jù)已結(jié)束0001：表示整個(gè)圖像結(jié)束0002：用來轉(zhuǎn)義后面兩個(gè)字節(jié)，即表示其后的兩個(gè)字節(jié)分別表示下一個(gè)像素從當(dāng)前位置開始的水平與垂直位移00N：表示從當(dāng)前位置起，圖像數(shù)據(jù)存在連續(xù)N個(gè)不同的值（存放于N/2個(gè)字節(jié)中）3.行程長(zhǎng)度編碼5個(gè)第18頁，課件共33頁，創(chuàng)作于2023年2月行程編碼原理在給定的圖像數(shù)據(jù)中尋找連續(xù)重復(fù)的數(shù)值，然后用兩個(gè)字符值取代這些連續(xù)值“aaabbbbccccddd”=>”3a4b4c3d”處理包含大量重復(fù)信息時(shí)可以得到很好的壓縮效率，但在連續(xù)重復(fù)數(shù)據(jù)少時(shí)效果差PCX圖像文件的RLE壓縮算法第19頁，課件共33頁，創(chuàng)作于2023年2月4預(yù)測(cè)編碼 預(yù)測(cè)編碼用于圖像編碼時(shí)與聲音的壓縮編碼很類似，它也是根據(jù)過去已編碼的像素（也稱為參考像素）來預(yù)測(cè)當(dāng)前的像素值（稱為預(yù)測(cè)值），然后對(duì)當(dāng)前的像素值與預(yù)測(cè)值之差進(jìn)行編碼，這就是差分編碼（DPCM）。這種編碼是利用圖像本身的相關(guān)性及視覺的差值靈敏度特性，差值大時(shí)，可以粗量化。圖像編碼用地較多的是二維預(yù)測(cè)，如圖3.6所示。第20頁，課件共33頁，創(chuàng)作于2023年2月第21頁，課件共33頁，創(chuàng)作于2023年2月LZW壓縮算法

LZW壓縮算法是一種新穎的壓縮方法，由Lemple-Ziv-Welch三人共同創(chuàng)造，用他們的名字命名。它采用了一種先進(jìn)的串表壓縮，將每個(gè)第一次出現(xiàn)的串放在一個(gè)串表中，用一個(gè)數(shù)字來表示串，壓縮文件只存貯數(shù)字，則不存貯串，從而使圖象文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過程中都能正確的建立這個(gè)串表，壓縮或解壓縮完成后，這個(gè)串表又被丟棄。

第22頁，課件共33頁，創(chuàng)作于2023年2月LZW算法中，首先建立一個(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，并將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。如"print"字符串，如果在壓縮時(shí)用266表示，只要再次出現(xiàn)，均用266表示，并將"print"字符串存入串表中，在圖象解碼時(shí)遇到數(shù)字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時(shí)，串表可以根據(jù)壓縮數(shù)據(jù)重新生成。第23頁，課件共33頁，創(chuàng)作于2023年2月壓縮算法的簡(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頁，課件共33頁，創(chuàng)作于2023年2月JPEG編碼二、JPEG算法的主要計(jì)算步驟JPEG壓縮編碼算法的主要計(jì)算步驟如下： （1）正向離散余弦變換（FDCT）。（2）量化（Quantization）。（3）Z字形編碼（ZigzagScan）。（4）使用差分脈沖編碼調(diào)制（DifferentialPulseCodeModulation，DPCM)對(duì)直流系數(shù)(DC)進(jìn)行編碼。（5）使用行程長(zhǎng)度編碼（Run-LengthEncoding，RLE）對(duì)交流系數(shù)（AC）進(jìn)行編碼。（6）熵編碼（EntropyEoding）。第25頁，課件共33頁，創(chuàng)作于2023年2月1.正向離散余弦變換（1）對(duì)每個(gè)單獨(dú)的彩色圖像分量，把整個(gè)分量圖像分成若干個(gè)8×8的圖像塊，如圖所示，并作為兩維離散余弦變換DCT的輸入。通過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頁，課件共33頁，創(chuàng)作于2023年2月2、量化量化是對(duì)經(jīng)過FDCT變換后的頻率系數(shù)進(jìn)行量化。量化的目的是減小非“0”系數(shù)的幅度以及增加“0”值系數(shù)的數(shù)目。量化是圖像質(zhì)量下降的最主要原因。對(duì)于有損壓縮算法，JPEG算法使用如下圖所示的均勻量化器進(jìn)行量化，量化步距是按照系數(shù)所在的位置和每種顏色分量的色調(diào)值來確定。因?yàn)槿搜蹖?duì)亮度信號(hào)比對(duì)色差信號(hào)更敏感，因此使用了兩種量化表：亮度量化值和色差量化值。此外，由于人眼對(duì)低頻分量的圖像比對(duì)高頻分量的圖像更敏感，因此圖中的左上角的量化步距要比右下角的量化步距小。下面2個(gè)表中的數(shù)值對(duì)CCIR601標(biāo)準(zhǔn)電視圖像已經(jīng)是最佳的。如果不使用這兩種表，你也可以把自己的量化表替換它們。亮度量化值表和色度量化值表第27頁，課件共33頁，創(chuàng)作于2023年2月3、Z字形編排量化后的系數(shù)要重新編排，目的是為了增加連續(xù)的“0”系數(shù)的個(gè)數(shù)，就是“0”的游程長(zhǎng)度，方法是按照Z字形的式樣編排，如下圖所示。這樣就把一個(gè)8×8的矩陣變成一個(gè)1×64的矢量，頻率較低的系數(shù)放在矢量的頂部。量化DCT系數(shù)序號(hào)0156141527252471316262942381217253041439111824314044531019233239455254202233384651556021343747505659613536484957586263第28頁，課件共33頁，創(chuàng)作于2023年2月4、直流系數(shù)的編碼8×8圖像塊經(jīng)過DCT變換之后得到的DC直流系數(shù)有兩個(gè)特點(diǎn)，一是系數(shù)的數(shù)值比較大，二是相鄰8×8圖像塊的DC系數(shù)值變化不大。根據(jù)這個(gè)特點(diǎn)，JPEG算法使用了差分脈沖調(diào)制編碼（DPCM）技術(shù)，對(duì)相鄰圖像塊之間量化DC系數(shù)的差值（Delta）進(jìn)行編碼。Delta＝DC(0,0)k-DC(0,0)k-1第29頁，課件共33頁，創(chuàng)作于2023年2月5、交流系數(shù)的編碼量化AC系數(shù)的特點(diǎn)是1×64矢量中包含有許多“0”系數(shù)，并且許多“0”是連續(xù)的，因此使用非常簡(jiǎn)單和直觀的游程長(zhǎng)度編碼(RLE)對(duì)它們進(jìn)行編碼。JPEG使用了1個(gè)字節(jié)的高4位來表示連續(xù)“0”的個(gè)數(shù)，而使用它的低4位來表示編碼下一個(gè)非“0”系數(shù)所需要的位數(shù)，跟在它后面的是量化AC系數(shù)的數(shù)值。第30頁，課件共33頁，創(chuàng)作于2023年2月6、熵編碼使用熵編碼還可以對(duì)DPCM編碼后的直流DC系數(shù)和RLE編碼后的交流AC系數(shù)作進(jìn)一步的壓縮。在JPEG有損壓縮算法中，使用霍夫曼編碼器來減少熵。使用霍夫曼編碼器的理由是可以使用很簡(jiǎn)單的查表（LookupTable）方法進(jìn)行編碼。壓縮數(shù)據(jù)符號(hào)時(shí)，霍夫曼編碼器對(duì)出現(xiàn)頻度