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

1、基于小波變換的圖像壓縮算法研究袁林 張國峰 戴樹嶺(北京航空航天大學(xué)先進(jìn)仿真技術(shù)實(shí)驗(yàn)室 北京 100083摘 要 小波變換是一種對信號的時(shí)間 -尺度 (時(shí)間 -頻率 進(jìn)行分析的方法,它具有多分辨率分析的特點(diǎn),而 且在時(shí)頻兩域都具有表征信號局部特征的能力。本文對基于小波變換的圖像數(shù)據(jù)壓縮編碼方法進(jìn)行研究, 首先利用小波變換對圖像進(jìn)行多分辨率分解, 然后對分解后的圖像數(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ù)雜,將有大量的圖像、語音等 多媒體的數(shù)據(jù)需要在網(wǎng)絡(luò)

2、上傳輸。在帶寬資源有限的情況下傳輸這些多媒體數(shù)據(jù)時(shí),需要對這些數(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í)域和頻域具有分辨率。對高頻分量用逐漸精細(xì)的時(shí)域或空域步長,可以聚焦 到分析對象的任意細(xì)節(jié),對于劇烈變換的邊緣,比常規(guī)的傅立葉變換具有更好的適應(yīng)性。由于小波 變換的優(yōu)良特性與 Mallat 算法的簡便易行,使得小波變換圖像編碼壓縮成為圖像壓縮領(lǐng)域的一個(gè)主 要研究方向。2小波變換 1與多分辨率分析小波變換就是將信號

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

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

5、速分解算法表達(dá)式:(=m mj k j mmj k j c k m g d c k m h c , 1, , 1, 22 (2-3其快速重構(gòu)算法的表達(dá)式為 :+=kk j k k j m j d c c , , , 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ì)上就是對圖像進(jìn)行離散二維小波變換。其二維小波變換就相當(dāng)于對二 維圖像數(shù)據(jù)在水平方向和垂直方向各自獨(dú)立地進(jìn)行一次一維小波變換。這樣,由前面介紹的一維小 波變換的快速算法,相應(yīng)地

6、就可以推出二維小波變換的快速算法。 Mallat 的圖像小波變換塔式算法 如下圖 1和圖 2所示 3。 其中, 表示每兩列中取出一列, 表示每兩行中取出一行, LL 表示低通子圖像, LH 表示水 平邊緣子圖像, HL 表示垂直邊緣子圖像, HH 表示斜方向邊緣子圖像 圖 1 Mallat圖像小波變換分解算法原始圖像 其中, 表示每兩行中插入一行零, 表示每兩列中插入一列零圖 2 Mallat圖像小波變換重建算法從濾波器的角度來看,上述過程可看成是對圖像二維數(shù)據(jù)進(jìn)行橫向和縱向的濾波過程。由于 h 具有低通濾波特性, g 具有高通濾波特性,若將初始輸入矩陣 (圖像的二維數(shù)據(jù) 看作一個(gè)二維離散信

7、號的話,則一次分解后得到的四部分輸出分別經(jīng)過了不同的濾波器,代表了原始圖像不同的信息。 其中, LL 是經(jīng)過行和列兩個(gè)方向的低通,對應(yīng)了原始離散圖像在下一尺度上的概貌, LH 經(jīng)過了行 方向上的低通和列方向上的高通, 對應(yīng)于水平方向的概貌和垂直方向上的細(xì)節(jié)信號。 以此類推得出, HL 對應(yīng)于水平方向的細(xì)節(jié)信號和垂直方向上的概貌, 而 HH 則表示的是沿對角線方向的細(xì)節(jié)。 小波 變換后小波系數(shù)分布可由圖 3表示3 圖像的量化編碼3.1 基于小波變換的編碼技術(shù)圖像經(jīng)多次小波分解后形成一系列處于不同空間、不同頻率的子圖像,然后可對這些子圖像進(jìn) 行某種形式的編碼,對系數(shù)的編碼是小波變換用于圖像壓縮的核

8、心。在對小波系數(shù)進(jìn)行處理時(shí),應(yīng) 該充分考慮并利用其統(tǒng)計(jì)特性,只有這樣才能得到高效而合理的結(jié)果。從對圖像變換后小波系數(shù)的 統(tǒng)計(jì)特性的分析中可以發(fā)現(xiàn),小波系數(shù)在零值附近高度集中,很好地去除了相關(guān)性。小波系數(shù)的數(shù) 據(jù)結(jié)構(gòu)十分有利于進(jìn)行編碼壓縮,并能較好的保持原圖像的特點(diǎn)。圖像經(jīng)過小波變換后生成的小波圖像的數(shù)據(jù)總量與原始圖像的數(shù)據(jù)量相等,即小波變換本身并 不具有壓縮功能。之所以將它用于圖象壓縮,是因?yàn)樯傻男〔▓D像具有與原圖像不同的特性,表 現(xiàn)在圖像上的能量主要集中于低頻部分,而水平、垂直和斜線部分的能則較少, LH j 、 HL j 和 HH j , 分別表征了原圖像在水平、垂直和斜線方向的邊緣信息

9、,具有明顯的方向特性。低頻部分稱作“模 圖 3 二維圖像分解小波系數(shù)糊圖像” ,水平、垂直和對角線部分稱作“細(xì)節(jié)圖像” 。對分解所得的各個(gè)子圖,需要根據(jù)人類視覺 生理和心理特點(diǎn)分別作不同策略的量化處理。3.2 小波系數(shù)的零數(shù)編碼Shapiro 4提出了零樹數(shù)據(jù)結(jié)構(gòu)來表征各級高頻子帶系數(shù)的自相似性,如下假設(shè)在很大概率下成 立:如果低頻子帶的小波系數(shù)小于某一閥值,則同方向上較高頻子帶的對應(yīng)相同位置的小波系數(shù)也 會小于該閥值。圖像的金字塔式分解從低頻到高頻子帶形成一個(gè)層次樹結(jié)構(gòu),最低頻子帶的結(jié)點(diǎn)有 3個(gè)子結(jié)點(diǎn)分別位于 3個(gè)方向次低頻子帶的相同位置,其余子帶(除最高頻子帶的結(jié)點(diǎn)都有 4個(gè) 子結(jié)點(diǎn)位于同

10、方向上高一級子帶的相應(yīng)位置。這里定義 了 POS 、 NEG 、 IZ 、 ZTR 四個(gè)符號:一個(gè) 小波系數(shù) x ,對于給定閥值 T ,若 T X |,則稱 x 不重要,相反稱為重要,根據(jù)系數(shù)符號正負(fù)定義 為 POS 和 NEC ;若根結(jié)點(diǎn)是不重要的且其所有后代結(jié)點(diǎn)也是不重要的,稱為零樹 ZTR ,若其后代 有重要系數(shù)則稱為孤立零數(shù),并建立兩個(gè)列表:主表放不重要系數(shù)或以其為根結(jié)點(diǎn)的樹,輔表存放 重要系數(shù)。系數(shù)掃描順序,采用從低頻到高頻,同一級各子帶按 HL 、 LH 、 HH 順序,子帶內(nèi)按迂回 掃描順序。利用上述層次樹結(jié)構(gòu)、符號和掃描順序定義,對于給定閥值 T 通過兩步實(shí)現(xiàn)編碼:(1 主掃描

11、按預(yù)先定義的順序掃描所有系數(shù),確立系數(shù)的類別并輸出相應(yīng)符號,若是 ZTR 則不必掃描其 后代系數(shù),否則繼續(xù)掃描其子代,直到分裂出后代中的所有重要系數(shù),掃描結(jié)束生成主表和輔表。(2輔掃描采用逐級逼近量化方法細(xì)化輔表中重要系數(shù)。4 圖像的熵編碼自適應(yīng)算術(shù)編碼根據(jù)混合編碼的思想,一個(gè)典型的靜態(tài)圖像壓縮編碼必須包括三個(gè)基本部分:變換、量化和編 碼。首先原始圖像經(jīng)過一些變換產(chǎn)生變換系數(shù),如果不考慮計(jì)算機(jī)計(jì)算精度損失的話,這一過程可 認(rèn)為是無損的;之后,變換系數(shù)被量化產(chǎn)生符號流(實(shí)際上,壓縮變換編碼過程中所有的信息損失 都發(fā)生在量化階段 ;編碼階段處理符號流則盡可能無損地描述數(shù)據(jù)流。算術(shù)編碼 5是一種變長

12、編碼,它使用長度可變的代碼來對以不同概率出現(xiàn)的樣本進(jìn)行編碼,用 于消除代碼冗余。 算術(shù)熵編碼是 Rissomen 提出的一種二元碼的編碼方法。 在不知信源統(tǒng)計(jì)的情況下, 通過監(jiān)視一段時(shí)間內(nèi)碼符號出現(xiàn)的頻度,不管統(tǒng)計(jì)是平穩(wěn)的還是非平穩(wěn)的,編成的碼率總能趨近于 信源熵值。每次迭代時(shí)編碼算法只處理一個(gè)數(shù)據(jù)符號,并且只有算術(shù)運(yùn)算。其基本原理是 :將被編碼 的信息表示成實(shí)數(shù) 0和 1之間的一個(gè)間隔 (Interval。信息越長,編碼表示的間隔就越小,表示這一 間隔所需的二進(jìn)制位就越多。信息源中連續(xù)的符號根據(jù)某一模式生成概率的大小來減少間隔,出現(xiàn) 概率大的符號比出現(xiàn)概率小的符號減少的范圍小,因此只增加較少

13、的比特位。自適應(yīng)二值算術(shù)編碼對一系列的二進(jìn)制符號進(jìn)行編碼。每個(gè)符號代表二進(jìn)制判定值的一種可能 結(jié)果。每個(gè)二進(jìn)制判定值提供兩種可能中的一種。遞歸概率區(qū)間劃分是二進(jìn)制算術(shù)編碼的基礎(chǔ)。對 于每個(gè)二進(jìn)制判定值,把當(dāng)前的概率空間劃分為兩個(gè)子區(qū)間,并且在必要時(shí)修改碼流,以便指向賦 給出現(xiàn)符號的概率子區(qū)間的基。自適應(yīng)算術(shù)編碼建立了一個(gè)統(tǒng)一模型,用于選擇每個(gè)二進(jìn)制判定值編碼用的條件概率估算值。 當(dāng)一個(gè)給定二進(jìn)制判定值的概率估算值取決于特定的特征或已編碼的特征時(shí),就以特征的性質(zhì)或值 為條件。 統(tǒng)計(jì)模型所要求的每個(gè)條件概率估算值被保存在獨(dú)立的存儲位置。 算術(shù)編碼器是自適應(yīng)的, 這意味著每個(gè)上下文索引處的概率估算值

14、由算術(shù)編碼系統(tǒng)創(chuàng)建和維護(hù), 它可以根據(jù)條件而自行改變。5 結(jié)束語圖像是人們傳遞信息的重要媒介,而數(shù)據(jù)量大又是數(shù)字圖像的一個(gè)顯著特點(diǎn),因此圖像壓縮對 于信息快速增長的今天來說顯得尤為重要。 小波變換是 80年代末發(fā)展起來的新興信號處理工具, 圖 像的小波分解非常適合于圖像數(shù)據(jù)的壓縮,而且已被 JPEG20006圖像壓縮標(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. Vol41(12, P3445-3462, 1993.5 I