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

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

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

3、一個獨立的函數(shù)(小波母函數(shù)(t 經(jīng)過平移和伸縮而得到的,如式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ù)交替的波動性。圖像的多分辨率分析(MultiResolution analysis采用不同分辨率下處理圖像中不同信息的方法,將圖像在各種分辨率下的細節(jié)提取出來,得到一個擁有不同分辨率的圖像細節(jié)序列再進行分析處理。與DCT 變換不適合于帶寬較寬(擁有較多邊緣輪廓信息的圖像信號不同,小波變換是一種不受帶寬約束的

4、圖像處理方法,即小波變換多分辨率的變換特性提供了利用人眼視覺特性的良好機制,從而使小波變換后圖像數(shù)據(jù)能夠保持原圖像在各種分辨率下的精細結(jié)構(gòu)。2.1快速小波變換算法(Mallat 算法 2Mallat 首先將多分辨率分析用于圖像數(shù)據(jù)的壓縮,他給出了信號分解與合成的快速算法,該算法在小波分析中的地位相當(dāng)于FFT 算法在傅立葉分析中的地位。Mallat 算法將數(shù)學(xué)領(lǐng)域的小波方法、計算機視覺中的多分辨率方法和信號處理中的子帶濾波方法完美的統(tǒng)一起來,它的出現(xiàn)使小波分析方法在信號處理領(lǐng)域真正得以實用化。根據(jù)多分辨率分析理論,可得出快速分解算法表達式:(=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)算法的表達式為:(+=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)圖像的二維小波變換實質(zhì)上就是對圖像進行離散二維小波變換。其二維小波變換就相當(dāng)于對二維圖像數(shù)據(jù)在水平方向和垂直方向各自獨立地進行一次一維小波變換。這樣,由前面介紹的一維小波變換的快速算法,相應(yīng)地就可以推出二維小波變換的快速算法。Mallat 的圖像小波變換塔式算法如下圖1和圖2所示3

6、。 其中,1 2表示每兩列中取出一列,2 1表示每兩行中取出一行,LL 表示低通子圖像,LH 表示水平邊緣子圖像,HL 表示垂直邊緣子圖像,HH 表示斜方向邊緣子圖像 圖1 Mallat 圖像小波變換分解算法 原始圖像其中,1 2表示每兩行中插入一行零,2 1表示每兩列中插入一列零圖2 Mallat圖像小波變換重建算法從濾波器的角度來看,上述過程可看成是對圖像二維數(shù)據(jù)進行橫向和縱向的濾波過程。由于h 具有低通濾波特性,g具有高通濾波特性,若將初始輸入矩陣(圖像的二維數(shù)據(jù)看作一個二維離散信號的話,則一次分解后得到的四部分輸出分別經(jīng)過了不同的濾波器,代表了原始圖像不同的信息。其中,LL是經(jīng)過行和列

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

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

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

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

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

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

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

14、壓縮標(biāo)準(zhǔ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