国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

無損圖像壓縮編碼方法及其比較

2014-12-25 07:11:12冉曉娟
重慶電力高等專科學校學報 2014年6期
關(guān)鍵詞:編碼方法游程字符串

冉曉娟

(四川旅游學院信息技術(shù),四川成都610000)

如今,信息早已成為一種重要的產(chǎn)品,其數(shù)量正以幾何級數(shù)的速度迅速增長。隨著多媒體技術(shù)與通訊技術(shù)的發(fā)展,人們對信息數(shù)據(jù)的存儲與傳輸提出了更高的要求,尤其是具有龐大數(shù)據(jù)量的數(shù)字圖像(其中往往存在著多種冗余信息)。如何快速有效地獲取、存儲并傳輸,對圖像通信的發(fā)展至關(guān)重要。

在保證復原圖像有較好質(zhì)量的前提下,通過刪除原始圖像數(shù)據(jù)中的冗余信息以減少圖像的數(shù)據(jù)量,提高存儲效率,實現(xiàn)圖像在網(wǎng)絡(luò)中的快速傳輸與實時處理的手段。圖像壓縮技術(shù)正受到人們越來越多的關(guān)注。

圖像壓縮技術(shù)的研究至今已有60多年的歷史,學者們提出并設(shè)計了多種實現(xiàn)圖像壓縮的方法。其中,根據(jù)壓縮過程中有無信息的損失,可將圖像壓縮技術(shù)分為無損壓縮和有損壓縮[7]。顧名思義,無損壓縮是指圖像在復原過程中不會產(chǎn)生任何失真;但有損壓縮則是通過損失圖像信息細節(jié)而換取較高壓縮比,此種壓縮方法在復原過程中會對原圖造成一定程度的失真,只能近似地恢復原圖像。

1 圖像壓縮原理

在信息論中,信息量是如下定義的:對于某一個離散無記憶信源a,它產(chǎn)生的消息集合為aiYi=1,2,…,NY,假設(shè)每個消息ai出現(xiàn)的概率為P(ai),則所有消息出現(xiàn)的概率之和應(yīng)為1,即由此,可推導出每個消息ai所攜帶的信息量為[1]:

可見,一個消息出現(xiàn)的可能性越小,其攜帶的信息量反而越多,對信息的貢獻量也越大。

若將信源所有信息量進行平均,則可以得到信源中每個消息的平均信息量,即信息的熵為:

根據(jù)香農(nóng)第一定理——可變長無失真信源編碼定理,對于熵為H的信號源,對其進行無失真編碼所可能達到的最低比特數(shù)為H+ε。這里為任意小的正數(shù),因此可能達到的最大壓縮比為[2]:

式中,B是原始圖像的平均比特率,壓縮比為[2]:

2 三種無損壓縮方法的原理

受數(shù)據(jù)冗余度的理論限制,無損壓縮一般只能獲得2~5倍的壓縮率。盡管如此,由于其還原后的文件可與原文件完全相同,可保證信息細節(jié)的不失真。因此,適用于壓縮文本、程序和對細節(jié)十分敏感且不允許出現(xiàn)失真的一些特殊領(lǐng)域的圖像數(shù)據(jù)。常用的無損壓縮方法主要分為基于字典和基于統(tǒng)計兩大類。

基于字典式的無損壓縮,其生成文件中通常含有12至16位定長碼。字典中每個定長碼代表原數(shù)據(jù)中的一個特定序列;而基于統(tǒng)計式的無損壓縮則是根據(jù)各個字符出現(xiàn)的概率,用變長碼來代替各個字符,實現(xiàn)數(shù)據(jù)壓縮。目前,常用的無損壓縮方法有算術(shù)編碼、香農(nóng)-范諾編碼、哈夫曼編碼、游程編碼和LZW編碼等。本文僅針對后述三種無損圖像壓縮方法的原理進行研究與比較,以突出無損圖像壓縮編碼方法在整個圖像信息處理中的重要作用。

2.1 哈夫曼(Huffman)編碼

哈夫曼編碼是美國數(shù)據(jù)家Huffman為解決當年遠距離通訊的數(shù)據(jù)傳輸?shù)淖顑?yōu)化問題,在1952年發(fā)明的一種基于統(tǒng)計的利用變長碼來使冗余量達到最小的無損編碼方法。信號源中字符出現(xiàn)的概率相差越大,Huffman編碼效果越好。

哈夫曼編碼算法的基本思路是利用最優(yōu)二叉樹進行編碼,出現(xiàn)頻率越高的值,其對應(yīng)的二進制編碼長度越短;反之,出現(xiàn)頻率越低的值,其對應(yīng)的二進制編碼長度越長。因此,在產(chǎn)生哈夫曼編碼的實際工作中需要對原始圖像進行兩次掃描。第一次掃描的目的是要精確地統(tǒng)計出原始圖像中每個灰度值出現(xiàn)的概率;第二次掃描則是建立哈夫曼樹并進行編碼。由于需要建立二叉樹并遍歷二叉樹生成編碼,因此Huffman編碼方式在數(shù)據(jù)壓縮和還原速度方面都較慢,但由于其簡單有效,因而得到廣泛的應(yīng)用。其操作步驟如下:(1)掃描原始圖像,對其進行灰度值分布概率統(tǒng)計,得到N個信息符號的不同概率Pi(i=1,2…,N);(2)將N個信息符號按其概率值Pi遞減的順序進行排列;(3)將兩個概率值最小的信號進行合并,形成一個新信號,設(shè)置新信號的概率值為此二信號的概率值之和,且概率個數(shù)減少為N-1個;(4)將新概率值放入集合后,重新按概率值遞減順序進行排列;(5)重復第3、4步,直到概率值相加為1時為止;(6)對生成二叉樹的左右分支,按照統(tǒng)一規(guī)律進行二進制碼元0,1賦值(如左分支代表0,右分支代表1);(7)從根結(jié)點開始到葉結(jié)點,將樹枝上的值按順序組成二進制值,生成Huffman編碼。

2.2 游程編碼(RLE)

數(shù)字圖像中,每一掃描行中具有相同灰度值的相鄰像素組成的序列稱為一個游程,因此,可用灰度游程串來表示圖像數(shù)據(jù)。游程編碼技術(shù)(Run Length Encoding)正是利用了游程的特點,在對圖像數(shù)據(jù)編碼時,只存儲每個游程的灰度值及組成該游程的相鄰像素的個數(shù),從而達到縮減重復出現(xiàn)的灰度值數(shù)量的目的,實現(xiàn)圖像壓縮??梢姡攬D像中含有少量灰度級,或者圖像是由灰度相同或很多塊顏色的大面積區(qū)域組成時,尤其是二值圖像時,采用游程編碼能獲得效果最佳的壓縮比。實際應(yīng)用中,游程編碼分為兩大類:定長游程編碼和變長游程編碼,并且常常和其他編碼方法結(jié)合使用。游程編碼的基本步驟如下:(1)讀入一副圖像并對其進行轉(zhuǎn)換,將其轉(zhuǎn)換為二值圖像;(2)對轉(zhuǎn)換后的二值圖像,按位進行掃描,判斷是否值得壓縮;(3)若第二步判定為真,則掃描圖像每一行,并對相同灰度值的相鄰像素進行計數(shù)統(tǒng)計,按照灰度值及像素個數(shù)進行統(tǒng)一編碼,直至圖像掃描結(jié)束。

2.3 LZW編碼

LZW編碼是在以色列人Lemple和Ziv共同提出的LZ壓縮技術(shù)(即查找冗余字符并用較短代碼代替冗余字符)基礎(chǔ)上,經(jīng)美國人Welch擴充而形成的一種先進的串表壓縮方法,簡稱為LZW壓縮方法,被廣泛應(yīng)用于圖像壓縮領(lǐng)域。其原理是讓每個字符都與下個字符配成一個字符對,并為每個字符對設(shè)定一個數(shù)字。當相同字符對再次出現(xiàn)時,就用數(shù)字來替換,然后再將這個數(shù)字與下一個字符繼續(xù)配對,生成的壓縮文件只存儲數(shù)字不存儲字符對,從而大大提高了圖像文件的壓縮比。故采用LZW編碼時,首先需要建立一個用以存儲字符串及其對應(yīng)數(shù)字代碼的字符串表,然后把每一個首次出現(xiàn)的字符串放入字符串表中,并用一個與該字符串在字符串表中的位置有關(guān)的數(shù)字來代表此字符串,并將這個數(shù)字存入文件中;如果再次出現(xiàn)該字符串,則用代表它的數(shù)字來代替該字符串,并將數(shù)字存入字符串表中。

由此可見,字符串表是在壓縮過程中動態(tài)生成的,因此當壓縮結(jié)束后,可丟棄字符串表;同樣,解壓過程能根據(jù)壓縮數(shù)據(jù)正確地重構(gòu)字符串表,因而也不需存儲字符串表。這樣,就不需要占用額外的空間來存儲字符串表,從而減少了壓縮文件的大小。

3 三種無損壓縮方法的分析比較

以上的三種無損壓縮編碼在一定程度上都實現(xiàn)了對圖像數(shù)據(jù)的壓縮,用盡可能少的信息量來實現(xiàn)數(shù)據(jù)的無損存儲與傳輸,起到了很好的作用。但各種編碼方法根據(jù)其適用對象又各具特點。

3.1 Huffman編碼方法

根據(jù)前面的介紹可知,Huffman編碼更適合于對概率分布不均勻的信源進行編碼。它的不足之處主要體現(xiàn)在以下幾個方面。

(1)必須精確地統(tǒng)計出原始文件中每個值的出現(xiàn)頻率,如果沒有這個精確統(tǒng)計,壓縮的效果就會大打折扣,甚至根本達不到壓縮的效果。由于哈夫曼編碼要進行二次掃描,這樣一來,對較大的文件進行編碼時,頻繁的磁盤讀寫訪問必然會降低數(shù)據(jù)編碼的速度,不利于網(wǎng)絡(luò)實時壓縮和傳輸。

(2)對位的增刪敏感。哈夫曼編碼將所有位合在一起不考慮字節(jié)分位,因此增加或者減少編碼的位都會使譯碼結(jié)果面目全非。

(3)需要用額外的位保存和傳輸Huffman樹,從而“浪費”掉一些存儲位,把本已減少的數(shù)據(jù)量又增加了一些。如果文件比較大,這一點多余的數(shù)據(jù)所占比例很小,但如果壓縮的文件本來就很小的話,增加的多余存儲數(shù)據(jù)會明顯影響壓縮效果。

基于Huffman算法的這些缺陷,不少人提出了一些自適應(yīng)算法。自適應(yīng)算法不必等到全部數(shù)據(jù)輸入完成才開始樹的構(gòu)造,可以根據(jù)后面輸入的數(shù)據(jù)動態(tài)的對Huffman樹進行調(diào)整。實際上,實用的Huffman樹都是經(jīng)過某種優(yōu)化后的動態(tài)算法。

3.2 游程編碼方法

作為壓縮文件最簡單的方法之一,游程編碼簡單直觀、編碼速度快,容易實現(xiàn),對于具有長重復值的串的壓縮尤其有效。常見的BMP和TIFF格式文件均采用RLE編碼,另外視頻文件AVI也將RLE作為其缺省壓縮方式。但是對于灰度圖及顏色豐富的彩色圖像進行壓縮時,單純使用RLE壓縮算法無法取得很好的效果。

3.3 LZW編碼方法

LZW編碼原理的一個重要特征是,代碼不僅僅能取代一串同值的數(shù)據(jù),也能夠代替一串不同值的數(shù)據(jù)。在圖像數(shù)據(jù)中若有某些不同值的數(shù)據(jù)經(jīng)常重復出現(xiàn),也可編寫一個代碼來取代這些數(shù)據(jù)串。因此,LZW壓縮編碼很適合壓縮有大塊相同色彩或重復顏色圖案的點陣圖,相同的色塊越多,壓縮比也越大。LZW壓縮技術(shù)比其他大多數(shù)壓縮技術(shù)都復雜,壓縮效率也較高。它一般包含在TIFF和GIF文件格式中:在TIFF中,LZW壓縮只是一個選項,可執(zhí)行可不執(zhí)行;而在GIF文件格式中,它作為缺省方式存在。此外,LZW編碼是可逆的。

4 結(jié)束語

隨著通信技術(shù)和多媒體技術(shù)的飛速發(fā)展,數(shù)字圖像已成為人類獲取和傳遞信息的重要手段之一。日益精細的圖像中包含了越來越豐富且巨大的數(shù)據(jù)量,這對圖像的高效存儲與快速傳輸提出了更高的要求,圖像壓縮技術(shù)恰好為解決這一難題提供了強有力的支撐。本文針對三種常用無損壓縮編碼方法的原理及操作步驟進行研究、分析與比較,介紹了各自的特點及不足。由此可見,豐富的圖像數(shù)據(jù)單純依靠某一種壓縮算法,都無法得到理想的壓縮效果。因此,在選擇具體算法的過程中,應(yīng)根據(jù)實際圖像的特點,選擇最合適的壓縮算法,有時往往還不只一種方法,才能獲得最好的壓縮效果。此外,由于受數(shù)據(jù)冗余度的理論限制,如果直接對圖像采用無損壓縮編碼,得到的壓縮比不可能有很大的提高。因此,可考慮先對圖像采用基于小波變換的圖像去噪算法來減少其中的冗余信息量,然后再采用上述無損壓縮算法對圖像進行壓縮的處理方案。如今,在數(shù)字圖像壓縮領(lǐng)域,人們除了要求高壓縮比以外,還越來越重視圖像壓縮的可靠性——要求圖像具有完全的可復原性和高度的保真效果,以及壓縮的實時性。因此,迫切需要對高效的無損壓縮算法進行深入的研究。

[1] 夏良正.數(shù)字圖像處理(修訂版).南京:東南大學出版社,2002.

[2] 艾海舟.數(shù)字圖像處理(多媒體課件)(第二版)[DB/OL].http://media.cs.tsinghua.edu.cn/~ ahz/digitalimageprocess/chapter14/chapt14_ahz.htm,2001-07-19/2014-11-01.

[3] 汪煉,韓震宇.無損圖像壓縮技術(shù)[J].實用測試技術(shù),2002,(5):33-34.

[4] W K普拉特.數(shù)字圖像處理學[M].北京:科學出版社,1984.

[5] 陳衍儀.圖像壓縮的分形理論和方法[M].北京:國防工業(yè)出版社,1997.

[6] 黃賢武.數(shù)字圖像處理與壓縮編碼技術(shù)[M].四川:電子科技大學出版社,2000.

[7] 馮希.幾種圖像無損壓縮與編碼方法的比較研究[D].北京:中國科學院研究生院,2008.

[8] 籍俊偉.無損圖像壓縮技術(shù)的研究與應(yīng)用[D].北京:北京化工大學,2004.

[9] 張玉彬.LZW數(shù)據(jù)壓縮算法的原理分析[EB/OL].http://www.cnblogs.com/jillzhang/archive/2006/11/06/551298.html,2006-11-06/2014-11-01.

猜你喜歡
編碼方法游程字符串
基于劃分組參考數(shù)的差值編碼壓縮方法
中國羽毛球組合鄭思維/黃雅瓊連續(xù)得失分規(guī)律研究
可變摩擦力觸感移動終端的漢語盲文編碼設(shè)計
改進型相對游程長度編碼方法
毫米波大規(guī)模MIMO系統(tǒng)中低復雜度混合預編碼方法
電信科學(2016年9期)2016-06-15 20:27:30
一種新的基于對稱性的字符串相似性處理算法
基于游程數(shù)的非參數(shù)隨機性檢驗
一種新的星載InSAR直接地理編碼方法
淺析公路工程物資的分類及編碼方法
依據(jù)字符串匹配的中文分詞模型研究
永州市| 犍为县| 东丰县| 文登市| 莲花县| 霍林郭勒市| 桐庐县| 手游| 大竹县| 永和县| 东兴市| 荥经县| 曲麻莱县| 庐江县| 香格里拉县| 乌什县| 南和县| 乳源| 天津市| 晋城| 策勒县| 申扎县| 临澧县| 尉氏县| 安义县| 苗栗市| 西华县| 长宁县| 张家港市| 玛多县| 新乡市| 施秉县| 明水县| 阿拉善左旗| 贵州省| 沧源| 呼玛县| 宣城市| 青冈县| 基隆市| 积石山|