改進(jìn)EZW算法及其應(yīng)用

趙雙雙

(金鄉(xiāng)縣人民醫(yī)院，山東 金鄉(xiāng) 272200)

改進(jìn)EZW算法及其應(yīng)用

趙雙雙

(金鄉(xiāng)縣人民醫(yī)院，山東 金鄉(xiāng) 272200)

數(shù)據(jù)壓縮；小波變換；EZW算法；改進(jìn)算法；EEG信號

近年來腦電圖已廣泛應(yīng)用于腦疾病的診斷，對腦電現(xiàn)在一般是采取長時間監(jiān)測，這就使得要存儲或傳輸?shù)臄?shù)據(jù)量較大。因此，有必要對EEG信號壓縮進(jìn)行研究，并取得了一定進(jìn)展[1-3]。數(shù)據(jù)壓縮就是減少必須分配給指定消息集合或數(shù)據(jù)采樣集合的信號空間的數(shù)值，數(shù)據(jù)壓縮屬于信源編碼的范疇[4]。目前對腦電的壓縮方法有矢量量化、多項(xiàng)式擬合、差分脈沖編碼調(diào)制、小波變換編碼等方法，其中小波變換在時域和頻域具有良好的壓縮特性，尤其適合于這種非平穩(wěn)信號的數(shù)據(jù)分析和壓縮，適用于生物醫(yī)學(xué)信號的分析與處理[5]。Shapiro提出的嵌入式零樹編碼算法是一種較為成功的二維圖像小波壓縮算法[6]，本文在探討小波變換和嵌入式零樹小波算法的基礎(chǔ)上，給出一種改進(jìn)算的嵌入式零樹小波算法，對改進(jìn)算法進(jìn)行分析并將其應(yīng)用于一維EEG信號傳輸壓縮中，以期對一維數(shù)據(jù)壓縮技術(shù)發(fā)展有所裨益。

1 基礎(chǔ)理論

1.1 小波變換 小波分析屬于時頻分析的一種。傳統(tǒng)信號分析是建立在傅立葉變換基礎(chǔ)上，而小波分析則克服了短時傅立葉變換在單分辨率上的缺陷，具有多分辨率分析的特點(diǎn)，在時域和頻域都有表征信號局部信息的能力，時間窗和頻率窗都可以根據(jù)信號的具體形態(tài)動態(tài)調(diào)整。目前小波已經(jīng)成為科學(xué)研究和工程技術(shù)應(yīng)用中涉及面極其廣泛的研究方向。它在數(shù)據(jù)壓縮、信號分析、語音合成、圖像識別、計算機(jī)視覺、海洋分析等方面的研究取得了有科學(xué)意義和應(yīng)用價值的成果。

小波變換的含義是：把某一被稱為基本小波(也叫母小波（motherwavelet)的函數(shù)φ(t)作位移b，再在不同尺度a下與待分析信號系統(tǒng)f(x)作內(nèi)積：

小波變換在頻域的等效表示如下：

式中 f(ω)，ψ(ω）分別是 f(ω)，ψ(x)的傅立葉變換。

小波變換具有多分辨率的特點(diǎn)，可以由粗及精逐步觀察信號。也可以看成用基本頻率特性為ψ(x)的帶通濾波器在不同尺度a下對信號作濾波。這組濾波器具有品質(zhì)因數(shù)恒定，即相對帶寬(帶寬與中心頻率之比)恒定的特點(diǎn)。a越大相當(dāng)于頻率越低。適當(dāng)?shù)剡x擇基本小波，使ψ(x)在時域上為有限支撐，ψ(ω)在頻域上也比較集中，便可以使在時頻域都具有表征信號局部特征的能力，因此有利于檢測信號的瞬態(tài)或奇異點(diǎn)。正是由于上述特性，小波變換才被譽(yù)為分析信號的數(shù)學(xué)顯微鏡。

理論上分析，只要基本小波滿足一定容許性條件的均可作為小波變換的母小波。對于不同的要求，應(yīng)當(dāng)使用相應(yīng)的母小波。采用不同的小波對信號進(jìn)行分析，其效果存在差異，甚至差異較大。選擇母小波時一般應(yīng)具有緊支性、正交性、對稱性、正規(guī)性、高階消失矩、理想帶通濾波器等特點(diǎn)。

1.2 嵌入式零樹小波 基于小波變換的主要編碼方法有嵌入式零樹小波編碼[7](EZW，Embedded ZerotreeWaveletCoding)算法、多級樹集合分裂算法(SPIHT，SetPartitioning in Hierarchical Trees)，可逆的嵌入小波壓縮法(CREW，Compression with reversible embedded wavelets)等。其中，零樹小波編碼的成功之處在于合理地利用了零值小波系數(shù)具有的零樹結(jié)構(gòu)，使得大量樹結(jié)構(gòu)的零系數(shù)只用一個零樹根符號來表示，從而其編碼效率大大超過了基于DCT變換的JPEG壓縮標(biāo)準(zhǔn)。EZW不僅具有高的壓縮比，還滿足漸進(jìn)編解碼和算法復(fù)雜度低特點(diǎn)。

嵌入式零樹小波編碼的完整過程如下：1)找出子波系數(shù)的最大值，得到最大門限T，作為首次掃描閾值[8]。2)主掃描：按照前述的掃描順序，用當(dāng)前閾值分別掃描判別各子像系數(shù)的節(jié)點(diǎn)類型，最高分辨率子像系數(shù)的節(jié)點(diǎn)類別只有3類(零樹根-ZT、正值-P、負(fù)值-N)，此外，其他子像系數(shù)的節(jié)點(diǎn)類型分為4類(零樹根-ZT、正值-P、負(fù)值-N、孤立零點(diǎn)-IZ)。將節(jié)點(diǎn)類型存入主表。對重要系數(shù)的節(jié)點(diǎn)，將其絕對值和當(dāng)前閾值存入副表(閾值作為有效值所在區(qū)間的起點(diǎn))，并將該點(diǎn)的小波系數(shù)置為“0”。3)副掃描：所有的子波系數(shù)均分類完畢后，用各有效值所在區(qū)間的起點(diǎn)加上當(dāng)前閾值的一半，分別對副表中絕對值進(jìn)行細(xì)化，將其不確定區(qū)間減為當(dāng)前閾值的一半。處在不確定區(qū)間高端的有效值編碼為“1”，低端的編碼為“0”。4)對主表節(jié)點(diǎn)類型和副表細(xì)化編碼進(jìn)行自適用算術(shù)編碼輸出。5)根據(jù)細(xì)化后副表中各有效值所在的區(qū)間將它們從高到低排序。6)用閾值的一半作為新的當(dāng)前閾值，重復(fù)(2～4)，直到達(dá)到所需的比特率和圖像質(zhì)量。

在譯碼恢復(fù)圖像的過程中，對系數(shù)的恢復(fù)也是“一節(jié)一節(jié)”進(jìn)行的。首先恢復(fù)最重要的系數(shù)，再恢復(fù)出閾值減半后的控制輸出的系數(shù)，依次重復(fù)，也可以根據(jù)圖像的質(zhì)量隨時停止譯碼。例如，譯碼恢復(fù)時，當(dāng)發(fā)現(xiàn)閾值為Tk=t0/2k時，圖像效果己很好，則可以抹去其后的碼字，保留Tk之前的碼字作為壓縮代碼文件。

EZW算法是針對二維圖像，在對一維EEG信號進(jìn)行小波變換后發(fā)現(xiàn)，一維EEG信號的小波域同樣存在相互對應(yīng)的關(guān)系。一維信號小波變換后的系數(shù)呈金字塔結(jié)構(gòu)，每個較粗尺度上的系數(shù)看作父結(jié)點(diǎn)，它在較細(xì)一尺度對應(yīng)位置上有兩個子結(jié)點(diǎn)，而低頻系數(shù)在下一尺度上只有一個子結(jié)點(diǎn)，從而構(gòu)成一個一維小波系數(shù)的樹結(jié)構(gòu)。

2 改進(jìn)EZW算法

小波系數(shù)之間具有一定的關(guān)聯(lián)性，可以通過構(gòu)建小波樹結(jié)構(gòu)的方式來加快我們對重要系數(shù)的篩選，而在信號壓縮中我們要做的就是在一定的壓縮比下優(yōu)先選出最能代表整個信號特征的那些點(diǎn)，所以可以利用小波樹的特點(diǎn)來篩選這些點(diǎn)，使篩選出來的這些點(diǎn)能有效的反映整個信號的特征。改進(jìn)EZW算法描述如下：1)輸入壓縮倍數(shù)和小波系數(shù)矩陣，求出壓縮后需要的小波系數(shù)數(shù)據(jù)長度。2)找出小波系數(shù)的最大值，得到最大門限T，作為首次掃描閾值。3)掃描過程。按照Morton掃描順序，用當(dāng)前閾值分別掃描判別各子像系數(shù)的節(jié)點(diǎn)，對重要系數(shù)的節(jié)點(diǎn)，將其值和在原矩陣中的位置坐標(biāo)存入重要系數(shù)列表，弱重要系數(shù)列表的元素個數(shù)達(dá)到了所要求的壓縮倍數(shù)則停止掃描，否則繼續(xù)掃描，若掃描次序表掃描結(jié)束，則將閾值減半后再進(jìn)入下一次掃描，最終得到的此表就是壓縮后的數(shù)據(jù)。4)還原過程。構(gòu)造一個與原矩陣大小相同的零矩陣，掃描重要系數(shù)列表并根據(jù)其各元素在原矩陣中的坐標(biāo)位置將各元素的值賦予所構(gòu)造的零矩陣。5)重構(gòu)過程。賦值完成后，對此矩陣進(jìn)行小波重構(gòu)，即得到壓縮數(shù)據(jù)。算法流程如圖1。

圖1 改進(jìn)EZW算法流程圖

3 實(shí)例分析

3.1 試驗(yàn)場景 數(shù)據(jù)來自某醫(yī)院EEG信號，其系統(tǒng)架構(gòu)見圖2。首先通過傳感器采集原始EEG信號，從數(shù)據(jù)源將源信號以十進(jìn)制的形式讀取出來，以便做進(jìn)一步分析。然后分析源信號得到采樣頻率、數(shù)據(jù)長度、幅值系數(shù)及時域信號等所需數(shù)據(jù)，存入本地數(shù)據(jù)庫。最后當(dāng)客戶端發(fā)出請求時，服務(wù)器按照設(shè)定好的壓縮方法對相應(yīng)數(shù)據(jù)進(jìn)行壓縮并傳輸?shù)娇蛻舳?。本文其研究重點(diǎn)其數(shù)據(jù)傳輸過程中的壓縮方法。

圖2系統(tǒng)結(jié)構(gòu)圖

3.2 壓縮技術(shù)評價指標(biāo) 評價恢復(fù)信號保真度的方法之一就是找出原始信號和重建信號之間的差別。大多數(shù)算法采用數(shù)字指標(biāo)，主要原因是數(shù)字指標(biāo)易于定義和計算，無主觀因素干擾，能客觀地進(jìn)行比較。壓縮比(Compression Ration,CR)是評價壓縮效率的常用指標(biāo)，能較準(zhǔn)確地反映壓縮前后數(shù)據(jù)量的變化。

在相同壓縮算法情況下，CR的大小受到原始數(shù)據(jù)采樣率、量化精度等影響，有時不能做出很客觀的衡量。另一種比較客觀的評價方法是恢復(fù)后數(shù)據(jù)占原數(shù)據(jù)的剩余能量百分比。其中，g(x)為恢復(fù)后數(shù)據(jù)，f(x)為原數(shù)據(jù)。

3.3 方法對比 為比較三種算法的壓縮效果，抽取兩組不同測試數(shù)據(jù)，一組為數(shù)據(jù)含有較大噪聲的EEG信號（簡稱MN）使用的小波基為bior3.1；另一組為含有較少噪聲的EEG信號（簡稱LN），使用的小波基為db3。用三種方法分別對其進(jìn)行壓縮，結(jié)果見表1、2。

表1 對MN信號進(jìn)行壓縮(bior3.1)

表2 對LN信號進(jìn)行壓縮(db3)

通過以上分析可知，對含有較大噪聲的EEG信號壓縮，在壓縮比較大時，改進(jìn)算法要比小波算法剩余更多的能量，在壓縮比較小時，改進(jìn)算法在剩余能量方面依然優(yōu)勢顯著，但在兩種情況下其運(yùn)行時間相對較長，而EZW算法的最大壓縮比僅為4，雖然它保存了較多的剩余能量，但其運(yùn)行時間比起前兩種算法長得多。

當(dāng)對含有較小噪聲的EEG信號進(jìn)行壓縮時，三種算法都能對數(shù)據(jù)進(jìn)行大幅壓縮，在較高壓縮比下都保持了較多的剩余能量，但相比較而言，小波算法在時間和剩余能量上都有較大優(yōu)勢，而EZW算法相對效果較差。當(dāng)進(jìn)一步加大壓縮比后，EZW算法已經(jīng)無法勝任，小波算法剩余能量下降明顯，而改進(jìn)算法則依然能夠保持較高的剩余能量。

分析可知，小波算法時間效率最高，適宜在數(shù)據(jù)量大，硬件條件有限的情況下使用，而且對噪聲小的數(shù)據(jù)效果更好。改進(jìn)算法是剩余能量最多，但時間效率相對較低，適宜在數(shù)據(jù)量不是很大，但對數(shù)據(jù)精確度要求高的情況下使用，它對不同噪聲的數(shù)據(jù)壓縮效果相對來說都不錯。EZW算法時間效率和剩余能量相對前兩種算法都沒有優(yōu)勢，但它確可以得到不同恢復(fù)精度的數(shù)據(jù)，在對壓縮比和數(shù)據(jù)精度要求都不高時可以嘗試使用。

本文在研究小波分析和嵌入式零樹小波算法的基礎(chǔ)上，給出一種改進(jìn)EZW算法。改進(jìn)EZW算法能夠在保證信號主要特征基本不變的前提下提高其壓縮比，減少數(shù)據(jù)量，改善其存儲、傳輸、檢索及分類等問題。改進(jìn)算法實(shí)現(xiàn)簡單，運(yùn)行速度快，可根據(jù)需要選擇不同的壓縮比，對日益發(fā)展的一維EEG信號數(shù)據(jù)的大規(guī)模存儲和遠(yuǎn)程傳輸?shù)扔幸欢ǖ膽?yīng)用價值。對一維信號的壓縮算法所做的研究尚處于不斷發(fā)展中，新的理論、方法會不斷涌現(xiàn)。對于小波數(shù)據(jù)壓縮方法而言，如何進(jìn)一步結(jié)合信號特性，提高壓縮比等方面，如何找到更加合適的小波基，實(shí)現(xiàn)一維信號的近無損壓縮有待進(jìn)一步研究。

[1]Antoniol G,Tonella P.EEG data compression techniques[J].IEEE Transon Biomed Eng,1997,44(2):105-114.

[2]SHI Liying, WANG Youyun. EEG data compression by high- order polynomials approximation [J]. Space Medicine ＆ Medical Engineering,1995,8(4) :168-272.

[3]路淼,周衛(wèi)東.基于嵌入式零樹編碼（EZW）的腦電信號壓縮算法[J].航天醫(yī)學(xué)與醫(yī)學(xué)工程，2004,17(3）:232-234.

[4]陳仲英,巫斌.小波分析[M].北京:科學(xué)出版社,2007.

[5]李良成,劉秋宏,張璟.小波變換在生物醫(yī)學(xué)信號中的應(yīng)用[J].2008,14(8):24-25.

[6]Shapiro JM. Embedded image coding using zerotrees of wavelet coefficients[J]. IEEE Transactions on Signal Processing,1993,41 (12):3445-3462.

[7]李世雄.小波變換及其應(yīng)用[M].北京：高等教育出版社,2000.

[8]Rosanna MR. Silveira. A genetic algorithm to compress electrocardiograms using parameterized wavelets[C]. IEEE international symposium on signal processing and information technology,2007.

TP301.6

A

1008-4118（2014）01-0069-04

10.3969/j.issn.1008-4118.2014.01.39

2013-12-27