基于小波變換的圖像壓縮算法研究

1、基于小波變換的圖像壓縮算法研究袁林 張國(guó)峰 戴樹嶺(北京航空航天大學(xué)先進(jìn)仿真技術(shù)實(shí)驗(yàn)室 北京 100083摘 要 小波變換是一種對(duì)信號(hào)的時(shí)間-尺度(時(shí)間-頻率進(jìn)行分析的方法,它具有多分辨率分析的特點(diǎn),而且在時(shí)頻兩域都具有表征信號(hào)局部特征的能力。本文對(duì)基于小波變換的圖像數(shù)據(jù)壓縮編碼方法進(jìn)行研究,首先利用小波變換對(duì)圖像進(jìn)行多分辨率分解,然后對(duì)分解后的圖像數(shù)據(jù)進(jìn)行小波零數(shù)編碼和自適應(yīng)算術(shù)編碼,從而實(shí)現(xiàn)圖像壓縮的目的。關(guān)鍵詞 虛擬現(xiàn)實(shí) 小波變換 圖像壓縮 零數(shù)編碼 算術(shù)編碼1 引言在分布式虛擬環(huán)境中,隨著應(yīng)用的日益廣泛和系統(tǒng)結(jié)構(gòu)的日漸復(fù)雜,將有大量的圖像、語(yǔ)音等多媒體的數(shù)據(jù)需要在網(wǎng)絡(luò)上傳輸。在帶寬資源

2、有限的情況下傳輸這些多媒體數(shù)據(jù)時(shí),需要對(duì)這些數(shù)據(jù)進(jìn)行有效的壓縮和解壓,以達(dá)到快速傳輸?shù)男Ч?。因?在虛擬現(xiàn)實(shí)系統(tǒng)中進(jìn)行有關(guān)多媒體數(shù)據(jù)壓縮的研究是非常有應(yīng)用價(jià)值的。近幾年,小波變換作為一種新興的信息處理方法,已經(jīng)受到廣泛重視。具有“數(shù)學(xué)顯微鏡”之稱的小波變換同時(shí)在時(shí)域和頻域具有分辨率。對(duì)高頻分量用逐漸精細(xì)的時(shí)域或空域步長(zhǎng),可以聚焦到分析對(duì)象的任意細(xì)節(jié),對(duì)于劇烈變換的邊緣,比常規(guī)的傅立葉變換具有更好的適應(yīng)性。由于小波變換的優(yōu)良特性與Mallat 算法的簡(jiǎn)便易行,使得小波變換圖像編碼壓縮成為圖像壓縮領(lǐng)域的一個(gè)主要研究方向。2小波變換1與多分辨率分析小波變換就是將信號(hào)在一個(gè)函數(shù)族上作分解,該函數(shù)族是由

3、一個(gè)獨(dú)立的函數(shù)(小波母函數(shù)(t 經(jīng)過(guò)平移和伸縮而得到的,如式2-1所: (|(2/1ab t a t = 0,a R b a (2-1 其中,分別為伸縮和平移尺度,(t 的傅立葉變換必須滿足容許性條件:<=d C R 2|(| (2-2 此式隱含了0(=dt t R ,表明小波具有正負(fù)交替的波動(dòng)性。圖像的多分辨率分析(MultiResolution analysis采用不同分辨率下處理圖像中不同信息的方法,將圖像在各種分辨率下的細(xì)節(jié)提取出來(lái),得到一個(gè)擁有不同分辨率的圖像細(xì)節(jié)序列再進(jìn)行分析處理。與DCT 變換不適合于帶寬較寬(擁有較多邊緣輪廓信息的圖像信號(hào)不同,小波變換是一種不受帶寬約束的

4、圖像處理方法,即小波變換多分辨率的變換特性提供了利用人眼視覺(jué)特性的良好機(jī)制,從而使小波變換后圖像數(shù)據(jù)能夠保持原圖像在各種分辨率下的精細(xì)結(jié)構(gòu)。2.1快速小波變換算法(Mallat 算法 2Mallat 首先將多分辨率分析用于圖像數(shù)據(jù)的壓縮,他給出了信號(hào)分解與合成的快速算法,該算法在小波分析中的地位相當(dāng)于FFT 算法在傅立葉分析中的地位。Mallat 算法將數(shù)學(xué)領(lǐng)域的小波方法、計(jì)算機(jī)視覺(jué)中的多分辨率方法和信號(hào)處理中的子帶濾波方法完美的統(tǒng)一起來(lái),它的出現(xiàn)使小波分析方法在信號(hào)處理領(lǐng)域真正得以實(shí)用化。根據(jù)多分辨率分析理論,可得出快速分解算法表達(dá)式:(=m mj k j mmj k j c k m g d

5、 c k m h c ,1,1,22 (2-3其快速重構(gòu)算法的表達(dá)式為:(+=kk j k k j m j k m g d k m h c c 22,1 (2-4其中,k j c ,、k j d ,分別是尺度j 上的尺度系數(shù)和小波系數(shù);而m j c ,1,為尺度j-1上的尺度系數(shù)。2.2二維圖像的小波變換的分解與重構(gòu)圖像的二維小波變換實(shí)質(zhì)上就是對(duì)圖像進(jìn)行離散二維小波變換。其二維小波變換就相當(dāng)于對(duì)二維圖像數(shù)據(jù)在水平方向和垂直方向各自獨(dú)立地進(jìn)行一次一維小波變換。這樣,由前面介紹的一維小波變換的快速算法,相應(yīng)地就可以推出二維小波變換的快速算法。Mallat 的圖像小波變換塔式算法如下圖1和圖2所示3

6、。 其中,1 2表示每?jī)闪兄腥〕鲆涣?2 1表示每?jī)尚兄腥〕鲆恍?LL 表示低通子圖像,LH 表示水平邊緣子圖像,HL 表示垂直邊緣子圖像,HH 表示斜方向邊緣子圖像 圖1 Mallat 圖像小波變換分解算法 原始圖像其中,1 2表示每?jī)尚兄胁迦胍恍辛?2 1表示每?jī)闪兄胁迦胍涣辛銏D2 Mallat圖像小波變換重建算法從濾波器的角度來(lái)看,上述過(guò)程可看成是對(duì)圖像二維數(shù)據(jù)進(jìn)行橫向和縱向的濾波過(guò)程。由于h 具有低通濾波特性,g具有高通濾波特性,若將初始輸入矩陣(圖像的二維數(shù)據(jù)看作一個(gè)二維離散信號(hào)的話,則一次分解后得到的四部分輸出分別經(jīng)過(guò)了不同的濾波器,代表了原始圖像不同的信息。其中,LL是經(jīng)過(guò)行和列

7、兩個(gè)方向的低通,對(duì)應(yīng)了原始離散圖像在下一尺度上的概貌,LH經(jīng)過(guò)了行方向上的低通和列方向上的高通,對(duì)應(yīng)于水平方向的概貌和垂直方向上的細(xì)節(jié)信號(hào)。以此類推得出, HL對(duì)應(yīng)于水平方向的細(xì)節(jié)信號(hào)和垂直方向上的概貌,而HH則表示的是沿對(duì)角線方向的細(xì)節(jié)。小波變換后小波系數(shù)分布可由圖3表示 3 圖像的量化編碼3.1 基于小波變換的編碼技術(shù)圖像經(jīng)多次小波分解后形成一系列處于不同空間、不同頻率的子圖像,然后可對(duì)這些子圖像進(jìn)行某種形式的編碼,對(duì)系數(shù)的編碼是小波變換用于圖像壓縮的核心。在對(duì)小波系數(shù)進(jìn)行處理時(shí),應(yīng)該充分考慮并利用其統(tǒng)計(jì)特性,只有這樣才能得到高效而合理的結(jié)果。從對(duì)圖像變換后小波系數(shù)的統(tǒng)計(jì)特性的分析中可以發(fā)

8、現(xiàn),小波系數(shù)在零值附近高度集中,很好地去除了相關(guān)性。小波系數(shù)的數(shù)據(jù)結(jié)構(gòu)十分有利于進(jìn)行編碼壓縮,并能較好的保持原圖像的特點(diǎn)。圖像經(jīng)過(guò)小波變換后生成的小波圖像的數(shù)據(jù)總量與原始圖像的數(shù)據(jù)量相等,即小波變換本身并不具有壓縮功能。之所以將它用于圖象壓縮,是因?yàn)樯傻男〔▓D像具有與原圖像不同的特性,表現(xiàn)在圖像上的能量主要集中于低頻部分,而水平、垂直和斜線部分的能則較少,LH j、HL j和HH j,分別表征了原圖像在水平、垂直和斜線方向的邊緣信息,具有明顯的方向特性。低頻部分稱作“模糊圖像”,水平、垂直和對(duì)角線部分稱作“細(xì)節(jié)圖像”。對(duì)分解所得的各個(gè)子圖,需要根據(jù)人類視覺(jué)生理和心理特點(diǎn)分別作不同策略的量化處

9、理。3.2 小波系數(shù)的零數(shù)編碼Shapiro 4提出了零樹數(shù)據(jù)結(jié)構(gòu)來(lái)表征各級(jí)高頻子帶系數(shù)的自相似性,如下假設(shè)在很大概率下成立:如果低頻子帶的小波系數(shù)小于某一閥值,則同方向上較高頻子帶的對(duì)應(yīng)相同位置的小波系數(shù)也會(huì)小于該閥值。圖像的金字塔式分解從低頻到高頻子帶形成一個(gè)層次樹結(jié)構(gòu),最低頻子帶的結(jié)點(diǎn)有3個(gè)子結(jié)點(diǎn)分別位于3個(gè)方向次低頻子帶的相同位置,其余子帶(除最高頻子帶的結(jié)點(diǎn)都有4個(gè)子結(jié)點(diǎn)位于同方向上高一級(jí)子帶的相應(yīng)位置。這里定義 了POS 、NEG 、IZ 、ZTR 四個(gè)符號(hào):一個(gè)小波系數(shù)x ,對(duì)于給定閥值T ,若T X <|,則稱x 不重要,相反稱為重要,根據(jù)系數(shù)符號(hào)正負(fù)定義為POS 和NE

10、C ;若根結(jié)點(diǎn)是不重要的且其所有后代結(jié)點(diǎn)也是不重要的,稱為零樹ZTR ,若其后代有重要系數(shù)則稱為孤立零數(shù),并建立兩個(gè)列表:主表放不重要系數(shù)或以其為根結(jié)點(diǎn)的樹,輔表存放重要系數(shù)。系數(shù)掃描順序,采用從低頻到高頻,同一級(jí)各子帶按HL 、LH 、HH 順序,子帶內(nèi)按迂回掃描順序。利用上述層次樹結(jié)構(gòu)、符號(hào)和掃描順序定義,對(duì)于給定閥值T 通過(guò)兩步實(shí)現(xiàn)編碼:(1主掃描按預(yù)先定義的順序掃描所有系數(shù),確立系數(shù)的類別并輸出相應(yīng)符號(hào),若是ZTR 則不必掃描其后代系數(shù),否則繼續(xù)掃描其子代,直到分裂出后代中的所有重要系數(shù),掃描結(jié)束生成主表和輔表。(2輔掃描采用逐級(jí)逼近量化方法細(xì)化輔表中重要系數(shù)。4 圖像的熵編碼自適應(yīng)算

11、術(shù)編碼根據(jù)混合編碼的思想,一個(gè)典型的靜態(tài)圖像壓縮編碼必須包括三個(gè)基本部分:變換、量化和編碼。首先原始圖像經(jīng)過(guò)一些變換產(chǎn)生變換系數(shù),如果不考慮計(jì)算機(jī)計(jì)算精度損失的話,這一過(guò)程可認(rèn)為是無(wú)損的;之后,變換系數(shù)被量化產(chǎn)生符號(hào)流(實(shí)際上,壓縮變換編碼過(guò)程中所有的信息損失都發(fā)生在量化階段;編碼階段處理符號(hào)流則盡可能無(wú)損地描述數(shù)據(jù)流。算術(shù)編碼5是一種變長(zhǎng)編碼,它使用長(zhǎng)度可變的代碼來(lái)對(duì)以不同概率出現(xiàn)的樣本進(jìn)行編碼,用于消除代碼冗余。算術(shù)熵編碼是Rissomen 提出的一種二元碼的編碼方法。在不知信源統(tǒng)計(jì)的情況下,通過(guò)監(jiān)視一段時(shí)間內(nèi)碼符號(hào)出現(xiàn)的頻度,不管統(tǒng)計(jì)是平穩(wěn)的還是非平穩(wěn)的,編成的碼率總能趨近于信源熵值。每

12、次迭代時(shí)編碼算法只處理一個(gè)數(shù)據(jù)符號(hào),并且只有算術(shù)運(yùn)算。其基本原理是:將被編碼的信息表示成實(shí)數(shù)0和1之間的一個(gè)間隔(Interval。信息越長(zhǎng),編碼表示的間隔就越小,表示這一間隔所需的二進(jìn)制位就越多。信息源中連續(xù)的符號(hào)根據(jù)某一模式生成概率的大小來(lái)減少間隔,出現(xiàn)概率大的符號(hào)比出現(xiàn)概率小的符號(hào)減少的范圍小,因此只增加較少的比特位。自適應(yīng)二值算術(shù)編碼對(duì)一系列的二進(jìn)制符號(hào)進(jìn)行編碼。每個(gè)符號(hào)代表二進(jìn)制判定值的一種可能結(jié)果。每個(gè)二進(jìn)制判定值提供兩種可能中的一種。遞歸概率區(qū)間劃分是二進(jìn)制算術(shù)編碼的基礎(chǔ)。對(duì)于每個(gè)二進(jìn)制判定值,把當(dāng)前的概率空間劃分為兩個(gè)子區(qū)間,并且在必要時(shí)修改碼流,以便指向賦給出現(xiàn)符號(hào)的概率子區(qū)

13、間的基。自適應(yīng)算術(shù)編碼建立了一個(gè)統(tǒng)一模型,用于選擇每個(gè)二進(jìn)制判定值編碼用的條件概率估算值。當(dāng)一個(gè)給定二進(jìn)制判定值的概率估算值取決于特定的特征或已編碼的特征時(shí),就以特征的性質(zhì)或值為條件。統(tǒng)計(jì)模型所要求的每個(gè)條件概率估算值被保存在獨(dú)立的存儲(chǔ)位置。算術(shù)編碼器是自適應(yīng)的,這意味著每個(gè)上下文索引處的概率估算值由算術(shù)編碼系統(tǒng)創(chuàng)建和維護(hù),它可以根據(jù)條件而自行改變。5 結(jié)束語(yǔ)圖像是人們傳遞信息的重要媒介,而數(shù)據(jù)量大又是數(shù)字圖像的一個(gè)顯著特點(diǎn),因此圖像壓縮對(duì)于信息快速增長(zhǎng)的今天來(lái)說(shuō)顯得尤為重要。小波變換是80年代末發(fā)展起來(lái)的新興信號(hào)處理工具,圖像的小波分解非常適合于圖像數(shù)據(jù)的壓縮,而且已被JPEG20006圖像

14、壓縮標(biāo)準(zhǔn)采用。因此研究基于小波變換的圖像壓縮算法具有重要意義。參考文獻(xiàn)1 程正興小波分析算法與應(yīng)用,西安交通大學(xué)出版社,1998.52 Mallat, S.G, “A theory for multiresolution signal decomposition: the wavelet representation”. IEEE Trans Pattern Analysis and Machine Intelligence, 1989.11(7: 674-693.3 美Kenneth R.Castleman著,朱志剛等譯,數(shù)字圖像處理,電子工業(yè)出版社,2002.24 Shapiro, J.M., "Embedded image coding using zerotrees of wavelet coefficients", IEEE Trans. Signal Processing. V ol41(12, P3445-3462, 1993.5 Ian H. Wi