三種無損壓縮原理介紹

1、三種無損壓縮原理介紹1前言現(xiàn)代社會是信息社會，我們無時無刻都在跟信息打交道，如上網(wǎng)查閱圖文資 料，瀏覽最新的新聞，QQ聊天或者傳送文件等。人類對信息的要求越來越豐富， 希望無論何時何地都能夠方便、快捷、靈活地通過文字、語音、圖像以及視頻等 多媒體進行通信。在早期的通信領(lǐng)域中，能夠處理和傳輸?shù)闹饕俏淖趾吐曇簦?因此，早期的計算機和通信設(shè)備的處理能力跟人類的需求有相當大的差距。隨著 通信信道及計算機容量和速度的提高，如今圖像信息已成為通信和計算機系統(tǒng)的 一種處理對象，成為通信領(lǐng)域市場的熱點之一?？墒?，大數(shù)據(jù)量的圖像信息會給 存儲器的存儲容量、通信干線信道的帶寬以及計算機的處理速度增加極大的壓 力

2、。單純依靠增加存儲器容量、提高通信網(wǎng)絡(luò)帶寬和計算機處理速度來解決問題， 在技術(shù)和經(jīng)濟上都不太現(xiàn)實。顯然，在信道帶寬、通信鏈路容量一定的前提下， 采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段。2正文2.1圖像壓縮編碼的現(xiàn)狀和發(fā)展趨勢1948年提出電視數(shù)字化后，就開始對圖像壓縮編碼技術(shù)的研究工作，至今 已有50多年的歷史。圖像壓縮的基本理論起源于20世紀40年代末香農(nóng)的信息 理論。香農(nóng)的編碼定理告訴我們，在不產(chǎn)生任何失真的前提下，通過合理的編碼， 對于每一個信源符號分配不等長的碼字，平均碼長可以任意接近于信源的熵。在 五十年代和六十年代，圖像壓縮技術(shù)由于受到電路技術(shù)等的制約，僅僅停留

3、在預(yù) 測編碼、亞采樣以及內(nèi)插復(fù)原等技術(shù)的研究，還很不成熟。1969年在美國召開 的第一屆“圖像編碼會議”標志著圖像編碼作為一門獨立的學(xué)科誕生了。到了 70年代和80年代，圖像壓縮技術(shù)的主要成果體現(xiàn)在變換編碼技術(shù)上，矢量量化 編碼技術(shù)也有較大發(fā)展，有關(guān)于圖像編碼技術(shù)的科技成果和科技論文與日俱增， 圖像編碼技術(shù)開始走向繁榮。自80年代后期以后，由于小波變換理論，分形理 論，人工神經(jīng)網(wǎng)絡(luò)理論，視覺仿真理論的建立，人們開始突破傳統(tǒng)的信源編碼理 論，例如不再假設(shè)圖像是平穩(wěn)的隨機場。圖像壓縮編碼向著更高的壓縮比和更好 的壓縮質(zhì)量的道路前進，進入了一個嶄新的、欣欣向榮的大發(fā)展時期。如今圖像壓縮編碼技術(shù)廣泛地

4、被應(yīng)用在各個領(lǐng)域。女如電視計算機、多媒體 出版物、遙感圖像數(shù)據(jù)庫等。它已經(jīng)為開創(chuàng)新的應(yīng)用領(lǐng)域提供了良好的技術(shù)基礎(chǔ)。 到目前為止，圖像壓縮編碼技術(shù)已經(jīng)發(fā)展到第二代編碼技術(shù)。1、第一代編碼技術(shù)包括建立在shannon的碼率失真理論基礎(chǔ)上的預(yù)測編碼、變 換編碼、統(tǒng)計編碼及Oliver提出的PCM編碼理論。雖然這些編碼技術(shù)在中等壓 縮率的情況下，能提供非常好的圖像質(zhì)量，但在碼率非常低得情況下，無法提供 令人滿意的質(zhì)量。究其原因是由于這些技術(shù)沒有利用圖像的結(jié)構(gòu)特點，同時也沒 有考慮人類視覺系統(tǒng)的特性，因此它們也就只能以像素或塊作為編碼的對象。2、第二代編碼包括基于分形的編碼、基于模型的編碼、基于區(qū)域分割

5、的編碼， 以及基于神經(jīng)網(wǎng)絡(luò)的編碼等。這類編碼技術(shù)不再局限于信息論的框架，充分利用 了人類視覺以及圖像信源的各種特征，實現(xiàn)從“波形”編碼到“模型”編碼的轉(zhuǎn) 變，獲得了更高的壓縮比。2.2關(guān)于數(shù)據(jù)圖像無損壓縮編碼圖像編碼發(fā)展至今已經(jīng)非常成熟了，但新穎的編碼方法仍然層出不窮。不管 具體的編碼形式如何，它們都是力圖消除圖像中的一種或者多種冗余。根據(jù)由壓 縮數(shù)據(jù)恢復(fù)的圖像與原始圖像的差別，圖像數(shù)據(jù)壓縮可以簡單分為兩類：“有損 壓縮”和“無損壓縮”其中無損壓縮在信息論中就稱為“熵編碼”無損壓縮僅 僅是刪除圖像數(shù)據(jù)中的冗余信息，在可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真的條 件下使比特率最小的壓縮方法。由于壓縮率

6、受到數(shù)據(jù)統(tǒng)計冗余度的理論限制，壓 縮比一般為2:1到5： 1在眾多的應(yīng)用中，無損壓縮是僅有的可以接受的數(shù)據(jù)壓 縮方法，其中的一種應(yīng)用是醫(yī)療或商業(yè)文件的歸檔。在這些應(yīng)用場合中，有損壓 縮通常因為法律原因而被禁止。另一種應(yīng)用是衛(wèi)星成像處理。還有一類應(yīng)用是數(shù) 字X光照相術(shù)，這種應(yīng)用中信息的丟失會導(dǎo)致?lián)p壞診斷的精確性。在這一類的情 況下，無損壓縮的需要是由與其用戶和圖像性質(zhì)所推動的。無損壓縮廣泛地被應(yīng)用在各個所需的領(lǐng)域，適應(yīng)當前多媒體技術(shù)發(fā)展的需 要?？梢?，這一領(lǐng)域的突破對于通信和多媒體事業(yè)的發(fā)展將具有深遠的影響。經(jīng) 常使用的無損壓縮方法有游程編碼、霍夫曼編碼和算術(shù)編碼等。2.2.1游程編碼原理游程編

7、碼主要用于量化后出現(xiàn)概率大量零系數(shù)的情形，利用游程來表示連 零碼，以降低為表示零碼所用的數(shù)據(jù)量。游程編碼往往與其他編碼方法結(jié)合使用。 游程編碼通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字段再加上一個重復(fù) 字符標志實現(xiàn)壓縮。譯碼時按照與編碼時采用的相同規(guī)則進行，還原后得到的數(shù) 據(jù)與壓縮前的數(shù)據(jù)完全相同。因此，RLE是無損壓縮技術(shù)。游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。二元序列的游程：只有“0”和“1”兩種符號。連0的個數(shù)稱為0游程； 連1的個數(shù)稱為1游程。游程變換：二元序列000101110010001.、 可變換成如下游程序 列 30 11 10 31 20 11 30 11當游程很短，也就是像

8、素的灰度頻繁改變時，使用行程碼不適宜的。2.2.2霍夫曼編碼原理霍夫曼編碼屬于碼詞長度可變的編碼類，是霍夫曼在1952年提出的一種編碼 方法，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，可區(qū)別的不同 碼詞的生成是基于不同符號出現(xiàn)的不同概率。生成霍夫曼編碼算法基于一種稱為 “編碼樹(coding t ree)的技術(shù)。算法步驟如下：初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序。把概率最小的兩個符號組成一個新符號(節(jié)點)，即新符號的概率等 于這兩個符號概率之和。重復(fù)第2步，直到形成一個符號為止(樹)，其概率最后等于1。從編碼樹的根開始回溯到原始的符號，并將每一下分枝賦值為1，上 分

9、枝賦值為0。以下這個簡單例子說明了這一過程。.字母A,B,C,D,E已被編碼，相應(yīng)的出現(xiàn)概率如下：p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11. C和E概率最小，被排在第一棵二叉樹中作為樹葉。它們的根節(jié)點CE 的組合概率為0.20。從CE到C的一邊被標記為1，從CE到E的一邊被標記為0。 這種標記是強制性的。所以，不同的霍夫曼編碼可能由相同的數(shù)據(jù)產(chǎn)生。.各節(jié)點相應(yīng)的概率如下：p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13D和A兩個節(jié)點的概率最小。這兩個節(jié)點作為葉子組合成一棵新的二叉樹。根節(jié) 點

10、AD的組合概率為0.29。由AD到A的一邊標記為0,由AD到D的一邊標記為1。 如果不同的二叉樹的根節(jié)點有相同的概率，那么具有從根到節(jié)點最短的最大路徑 的二叉樹應(yīng)先生成。這樣能保持編碼的長度基本穩(wěn)定。.剩下節(jié)點的概率如下：p(AD)=0.29, p(B)=0.51, p(CE)=0.20AD和CE兩節(jié)點的概率最小。它們生成一棵二叉樹。其根節(jié)點ADCE的組合概率 為0.49。由ADCE到AD 一邊標記為0,由ADCE到CE的一邊標記為1。.剩下兩個節(jié)點相應(yīng)的概率如下：p(ADCE)=0.49, p(B)=0.51它們生成最后一棵根節(jié)點為ADCEB的二叉樹。由ADCEB到B的一邊記為1,由ADCE

11、B 到ADCE的一邊記為0。.圖2-1為霍夫曼樹結(jié)構(gòu)。編碼結(jié)果被存放在一個表中：w(A)=001, w(B)=0, w(C)=111, w(D)=100, w(E)=011P(A)=0.1 P(B)=0.51P(C)=0.09P(A)=0.1 P(B)=0.51P(C)=0.09 1P(D)=0.13(0.29)(0.2)1(0.49)(1.00)P(E)=0.11 0圖2-1霍夫曼樹結(jié)構(gòu)符號概率霍夫曼編碼A0.16001B0.510C0.09111D0.13100E0.11011表2-2霍夫曼編碼表2.2.3算術(shù)編碼原理算術(shù)編碼是20世紀80年代發(fā)展起來的一種熵編碼方法，它已漸漸受到人們 的

12、注意。它的基本原理是，任何一個數(shù)據(jù)序列均可表示成0和1之間的一個間隔, 該間隔的位置與輸入的概率分布有關(guān)。可以根據(jù)信源的統(tǒng)計特性來設(shè)計具體的編 碼器，也可以針對未知概率的信源設(shè)計能夠自適應(yīng)適配其分布的算術(shù)編碼器，這 兩種形式的編碼器均可以用硬件實現(xiàn)，有關(guān)的實驗數(shù)據(jù)表明，在未知信源概率分 布的大部分情形下，算術(shù)編碼優(yōu)于霍夫曼編碼。算術(shù)編碼的基本規(guī)則如下：初始狀態(tài)：編碼起點co=o,區(qū)間寬度A0=1.新編碼點：Ci二Ci_+(Ai-1)*Pi式中：Ci-1是原編碼點，Ai-1是原區(qū)間寬度，Pi為所編符號對應(yīng)的積累概 率。新區(qū)間寬度：Ai=Ai-1*Pi式中：Pi為所編符號對應(yīng)的概率。3、結(jié)論目前，

13、圖像壓縮技術(shù)已經(jīng)得到了廣泛的推廣應(yīng)用，對人們的日常生活產(chǎn)生了 重要的影響VCD、DVD和各種檔次的數(shù)字點數(shù)都是圖像壓縮技術(shù)的應(yīng)用實例?！皥D 像壓縮編碼”是圖像處理的重要內(nèi)容，隨著通信技術(shù)和多媒體技術(shù)的發(fā)展，圖像 壓縮編碼技術(shù)已進入實用階段，圖像編碼可以看作是一維信號編碼或三維的推 廣。在當前數(shù)字圖像壓縮領(lǐng)域中，無損壓縮由于具有高度的保真效果，完全的可 復(fù)原性，獲得了越來越多的關(guān)注。在衛(wèi)星科學(xué)探測領(lǐng)域，數(shù)據(jù)存儲和傳輸必須用 無損壓縮技術(shù)才能保證圖像細節(jié)不被破壞。企事業(yè)單位的數(shù)據(jù)存檔必須是無損 的，這樣才能完全復(fù)原而不至于丟失重要信息。因此，對高效的無損壓縮方法有 著越來越迫切的需要，除了對壓縮比

14、的要求外，還需要壓縮的實時性好，可靠性 高等。研究高性能的無損壓縮算法，具有一定的理論意義和實用價值。4、參考文獻1、賈永紅，數(shù)字圖像處理，武漢：武漢大學(xué)出版社，2003.92、黃賢武，王佳俊，李家華，數(shù)字圖像處理與壓縮編碼技術(shù)，四川：電子科技 大學(xué)出版社，2000年。3、Tinku Acharya Ajoy K.Ray著，田浩等譯，Image Processing Principles and Applications，北京：清華大學(xué)出版社，2007.74、C算法.第一卷。基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、排序和搜索，Robert Sedgewick著，周良 忠譯，北京：人民郵電出版社，2004.65、籍俊偉無損壓縮技術(shù)的研究與應(yīng)用【期刊論文】-北京工業(yè)大