基于嵌入式零樹小波的心電信號壓縮算法及實現(xiàn)*

蔣國華，潘健勇，董齊芬，俞 立*

(1.浙江工業(yè)大學(xué)信息工程學(xué)院，杭州310023;2.杭州市特種設(shè)備檢測院，杭州310023)

心臟疾病已經(jīng)成為威脅人類健康和生命的頭號殺手。心電監(jiān)護通過連續(xù)觀察監(jiān)測心臟電活動情況，可實時觀察病情，獲得可靠且有價值的心電活動指標(biāo)，因此給醫(yī)生對心電活動異常者的診斷和處理，帶來重要價值?，F(xiàn)有大型心電監(jiān)護設(shè)備雖然在精確度和可靠性等各方面具有優(yōu)勢，但是其體積龐大、價格昂貴，通常只有醫(yī)院配備此類設(shè)備，患者必須去醫(yī)院才能使用;而使用其他基于存儲卡的便攜式心電監(jiān)護設(shè)備，患者必須定時去醫(yī)療中心提交其心電數(shù)據(jù)，便利性比較差。

近幾年隨著無線通信技術(shù)的快速發(fā)展，無線技術(shù)在醫(yī)療、監(jiān)護領(lǐng)域得到廣泛應(yīng)用，基于無線通信的便攜式心電監(jiān)護設(shè)備應(yīng)運而生。但受能量供應(yīng)、處理能力、存儲容量和通信帶寬等方面的限制，要求傳輸和存儲過程中數(shù)據(jù)量盡可能小，因此數(shù)據(jù)壓縮顯得十分重要?，F(xiàn)有心電數(shù)據(jù)壓縮算法主要分為直接壓縮法和變換壓縮法兩大類［1-2］:前者通過直接去除原始數(shù)據(jù)中的冗余數(shù)據(jù)實現(xiàn)壓縮，主要有FAN、AZTEC、CORTES、ASEC等，這類算法易于實現(xiàn)但很難同時保證較高的壓縮率和保真度;后者則通過各種變換去除數(shù)據(jù)間的相關(guān)性，用少量變換域分量保持原始數(shù)據(jù)的信息，主要有 DFT、DCT、DWT、KLT等，它們能同時保證較高的壓縮率和信息保真度，但是算法復(fù)雜度通常比較高。

Shapiro提出的EZW(Embedded Zero-tree Wavelet)算法［3］是最早實現(xiàn)的基于小波變換的嵌入式編碼方法，是一種根據(jù)數(shù)據(jù)重要性進行編碼的簡單、有效的壓縮算法［4］。EZW編碼最早應(yīng)用于二維圖像壓縮，圖像的絕大部分信息集中于低頻子帶，即經(jīng)過小波變換，低頻子帶中的小波系數(shù)通常要大于高頻子帶中相應(yīng)的小波系數(shù)。正是從這個特點出發(fā)，產(chǎn)生了零樹結(jié)構(gòu)的概念，而大量零樹的存在保證了較高的壓縮率［5］。一維心電信號經(jīng)小波變換產(chǎn)生的系數(shù)也具有類似的結(jié)構(gòu)，因此也可利用EZW算法進行數(shù)據(jù)壓縮。但直接使用基本的EZW算法對心電數(shù)據(jù)進行編碼，不能充分發(fā)揮心電信號周期性好、信息集中于低頻分量的特點，其壓縮率仍有很大的提高空間。

針對以上問題，本文在研究EZW編碼算法的基礎(chǔ)上提出一種基于5/3提升小波變換的改進EZW壓縮算法，應(yīng)用于心電信號壓縮，在保持基本算法高保真度的同時獲得更高壓縮率。最后通過仿真比較了基本EZW編碼算法與改進算法的壓縮效果，并在物理硬件上運行改進算法。

1 嵌入式零樹小波編碼算法

小波變換具有良好的時頻聚集性能和信號逼近性能，因而在數(shù)據(jù)壓縮領(lǐng)域獲得了廣泛應(yīng)用［6］。近年來出現(xiàn)的第二代小波變換，也稱整數(shù)小波變換，繼承了第一代小波變換的優(yōu)點，并且本身具有不依賴傅里葉變換、無需浮點運算、計算完全可逆以及可進行同址運算等優(yōu)點，因此在工程應(yīng)用中發(fā)揮著巨大作用［7］。

本文提出的算法基于5/3提升小波變換［8］對原始數(shù)據(jù)進行時頻分析。5/3提升小波變換就是通過5/3提升算法實現(xiàn)的整數(shù)小波變換。相比于其他整數(shù)小波變換，5/3小波變換在計算復(fù)雜度和壓縮性能上能更適合于心電信號的壓縮［9］。由提升方案構(gòu)成的整數(shù)小波變換包括分裂、預(yù)測和更新3個步驟。將2j個數(shù)據(jù)進行一次5/3提升小波正變換的過程如下:

Step 1:分裂。將原數(shù)據(jù)分為奇數(shù)列oi和偶數(shù)列ei。

Step 2:預(yù)測。由偶數(shù)序列預(yù)測奇數(shù)序列，得到細節(jié)系數(shù)，對應(yīng)于原數(shù)據(jù)的高頻部分，如式(1)。

Step 3:更新。由細節(jié)系數(shù)序列更新偶數(shù)序列，對應(yīng)于原數(shù)據(jù)的低頻部分，如式(2)。

其中，?」表示向下取整，di表示高頻系數(shù)，ui表示低頻系數(shù)。

對低頻部分繼續(xù)分裂、預(yù)測、更新，經(jīng)過n次循環(huán)分解，數(shù)據(jù)按照從低頻到高頻排列，可表示為序列{X0，X1，X2，…，X2j-1}?？梢园l(fā)現(xiàn)，原始信號被分解成n層二叉樹結(jié)構(gòu):除最低頻部分外，第n層的系數(shù)對應(yīng)兩個第n-1層系數(shù)。其對應(yīng)關(guān)系可用父節(jié)點和子節(jié)點的關(guān)系描述。以16點數(shù)據(jù)為例，經(jīng)過3層小波分解得到如圖1所示樹形結(jié)構(gòu)。

圖1 小波分解示意

經(jīng)過上述小波變換，父節(jié)點的數(shù)值有很大概率比其子孫節(jié)點的大。因此當(dāng)一個節(jié)點比某閾值小時，很有可能其所有子孫節(jié)點也小于該閾值，這便形成一棵“零樹”。可以發(fā)現(xiàn)心電信號數(shù)據(jù)經(jīng)小波變換存在大量零樹，可利用EZW算法對變換后的所有高頻系數(shù)進行壓縮。

完成EZW算法需要構(gòu)建兩張表:主表用于保存小波系數(shù)的類型;而副表用于確定重要系數(shù)的數(shù)值范圍。小波系數(shù)有以下四種類型:①正重要系數(shù)(POS):若對于一個給定閾值T，小波系數(shù)xi≥T;②負重要系數(shù)(NEG):若對于一個給定閾值T，小波系數(shù)xi≤-T;③零樹根(ZTR):小波系數(shù)xi和它的所有子孫均不是重要系數(shù);④孤立零(IZ):小波系數(shù)xi不是重要系數(shù)，但它的后代中存在重要系數(shù)。其中，正重要系數(shù)和負重要系數(shù)統(tǒng)稱為重要系數(shù)。由于只有4種類型，用2個比特位即可編碼。EZW算法編碼流程如圖2實線部分。解壓為壓縮的逆過程。

圖2 EZW算法及改進算法流程圖

2 算法改進

由基本EZW算法的壓縮結(jié)果可以看出，主表中大多是ZTR，而IZ、POS、NEG只占很少一部分，并且這種比例差異在第一次迭代時特別明顯。隨著迭代次數(shù)增加，ZTR所占比例越來越小。因此，在第一次迭代中，主表中大多數(shù)符號用于記錄ZTR，并且其中的很大一部分在第二次迭代中變?yōu)?IZ、POS或NEG，即第一次迭代只為了少數(shù)幾個大于初始閾值的系數(shù)而進行。另外，還有一部分ZTR在后續(xù)每一次迭代中仍是ZTR，即每次迭代重復(fù)掃描及編碼一些始終處于零樹中的數(shù)據(jù)。

針對以上發(fā)現(xiàn)，本文對基本EZW算法做以下改進:合并第一次和第二次迭代，判斷第一次出現(xiàn)的非重要系數(shù)在第二次迭代中是否為重要系數(shù);第一次迭代中出現(xiàn)的ZTR在最后一次迭代中是否仍為ZTR，若在最后一次迭代時為零樹，則在前面迭代中閾值更大，必為零樹。而后續(xù)的幾次迭代則仍使用基本算法的方法進行編碼。為此需要在合并的第一次迭代過程中引進幾個新的編碼符號:①POS1:若xi≥T0，其中 T0為初始閾值;②NEG1:若 xi≤-T0;③POS2:若 xi＜T0且 xi≥T0/2，即基本算法中第二次迭代的 POS;④NEG2:若 xi＞-T0且 xi≤-T0/2，即基本算法中第二次迭代的NEG;⑤IZ:以T0/2為閾值的孤立零;⑥ZTR1:以T0/2為閾值的零樹根;⑦ZTR2:若原本為ZTR1的點，在最小可能達到的閾值下仍為零樹根。以上總共7個編碼符號，所以改進算法第一次迭代中每個數(shù)據(jù)類型需要三個比特位編碼。

在上述前提下，本文提出改進算法的第一次迭代如圖2虛線部分所示，步驟如下:

Step 1:初始化。算法必須先確定一個初始閾值，以后每次迭代的閾值由初始閾值計算得到。初始閾值的確定方法并不唯一，本文采用式(3)定義:

Step 2:主掃描。依次將未掃描系數(shù)與T0和T0/2比較，判斷其類型。按照系數(shù)的類型做出相應(yīng)處理:如果是 POS1、NEG1 或者 POS2、NEG2，相應(yīng)類型編碼保存至主表，保存系數(shù)絕對值，并將系數(shù)序列中相應(yīng)的位置置0;如果是 IZ、ZTR1、ZTR2，僅將相應(yīng)類型編碼保存至主表中。每掃描一個數(shù)據(jù)，標(biāo)記其狀態(tài)為本次迭代已掃描，若其類型為ZTR1，標(biāo)記其每個子孫為本次迭代已掃描，若其類型為ZTR2，標(biāo)記其每個子孫為所有迭代已掃描。待所有系數(shù)均為已掃描，將閾值減半，進入副掃描。主掃描流程圖如圖3所示。

圖3 改進算法第一次主掃描流程

Step 3:副掃描。副掃描和基本算法相同，只是由于主掃描結(jié)合了基本算法的兩次迭代，所以改進算法相應(yīng)的副掃描也要進行兩次。需注意，在兩次副掃描中間對閾值進行一次減半操作?；舅惴ǖ囊淮胃睊呙柽^程如圖4所示。

由于基本算法第一次迭代中出現(xiàn)的非重要系數(shù)有很大一部分在第二次迭代中成為重要系數(shù)，因此改進算法的第一次迭代與基本算法的前兩次迭代相比，記錄類型的編碼數(shù)據(jù)明顯減少，即提高了壓縮率。提前判斷并標(biāo)記第一次出現(xiàn)零樹是否在整個過程中一直是零樹，可以減少在后續(xù)迭代中對零樹的判斷及編碼，以提高算法的壓縮率和計算效率。

圖4 基本算法副掃描流程

3 實驗結(jié)果

3.1 算法評價標(biāo)準

本文分別從仿真實驗和實際物理實驗對基本EZW算法和改進算法進行驗證，以檢驗改進算法的有效性。實驗以壓縮比(Compression Radio，CR)、重構(gòu)失真率(Percent Root-mean-square Difference，PRD)和重構(gòu)相似度(Correlation Coefficient，CC)作為評估指標(biāo)［10-11］，分別對應(yīng)式(4)～(6):

其中，xi表示壓縮前的小波系數(shù)，是經(jīng)小波變換之后的高頻分量數(shù)據(jù)是其平均值;yi表示壓縮后的數(shù)據(jù)：表示解壓后的數(shù)據(jù)?是其平均值。

3.2 仿真結(jié)果

本文以MATLAB作為仿真平臺，以MIT-BIH心律不齊數(shù)據(jù)庫［12］為樣本數(shù)據(jù)集。首先以100號數(shù)據(jù)的前1 024個點定性驗證算法的可行性。其原始數(shù)據(jù)(經(jīng)偏移和放大的電壓信號)和其經(jīng)壓縮、還原后的數(shù)據(jù)如圖5所示。從圖5可以發(fā)現(xiàn)，改進算法的數(shù)據(jù)失真度小，能保持很好的相似度，從而驗證算法可用于心電信號的壓縮。

圖5 100號數(shù)據(jù)仿真圖

進一步選取 100、101、113、124、217 等五個記錄，在不同層次下定量計算和對比基本算法和改進算法。在每個記錄中取500組互不包含的連續(xù)數(shù)據(jù)，每組取102 4個點。分別使用基本算法和改進算法對每組數(shù)據(jù)進行壓縮并解壓，然后分別計算其CP值、PRD值和CC值，最后求得500組數(shù)據(jù)的平均值。表1、表2、表3分別在4層、5層和6層編碼下對比基本算法與改進算法的性能(未改進算法一次迭代視為一層編碼，改進算法的第一次迭代視為兩層編碼)。

表1 4層編碼算法比較

表2 5層編碼算法比較

表3 6層編碼算法比較

從上述實驗數(shù)據(jù)可以看出，改進算法在保持解壓前后失真度和相似度不變的同時提高了數(shù)據(jù)的壓縮率。經(jīng)對比發(fā)現(xiàn)，運行在5層編碼時，同時具有理想的壓縮率和保真度，壓縮效果最佳，故本文采用5層編碼的改進算法進行實際物理實驗。

3.3 實際運行

本文提出的改進算法采用NesC語言實現(xiàn)，運行在Crossbow公司的MICAZ節(jié)點上，而上位機運行解碼程序。在250 Hz的采樣頻率下每采樣512個數(shù)據(jù)進行一次5層改進編碼壓縮，將壓縮后的數(shù)據(jù)通過無線網(wǎng)絡(luò)傳輸?shù)缴衔粰C進行解碼，同時將原始數(shù)據(jù)一并發(fā)往上位機以計算各指標(biāo)。圖6為MICAZ節(jié)點以及心電信號采集電路，圖7為上位機顯示的4 096個點原始信號(經(jīng)偏移和放大的電壓信號)和重構(gòu)信號圖，表4給出了5組實測數(shù)據(jù)的壓縮情況。

圖6 MICAZ節(jié)點圖

圖7 上位機的重構(gòu)圖

表4 實測數(shù)據(jù)

表4數(shù)據(jù)顯示，本文提出的改進算法用于實際采樣數(shù)據(jù)，可以得到滿意的結(jié)果。

4 結(jié)束語

針對無線心電監(jiān)護設(shè)備資源有限的特點和心電信號本身的特性，本文設(shè)計了一種基于5/3提升小波變換的改進EZW壓縮算法。該算法將基本EZW算法第一次和第二次迭代加以合并，在保持信號失真度和相似度的同時提高數(shù)據(jù)壓縮率。通過仿真實驗比較和實際物理實驗驗證了算法的可行性和有效性，滿足便攜式心電監(jiān)護設(shè)備對數(shù)據(jù)壓縮的需求。

［1］ Tohumoglu G，Sezgin K E.ECG Signal Compression by Multi-Iteration EZW Coding for Different Wavelets and Thresholds［J］.Computers in Biology and Medicine，2007(37):173-182.

［2］ 凌朝東，劉蓉，錢江，等.基于5/3提升小波變換的心電信號壓縮算法及 VLSI實現(xiàn)［J］.信號處理，2006，26(6):930-935.

［3］ Shapiro J M.Embedded Image Coding Using Zero-Trees of Wavelet Coefficients［J］.IEEE Transactions on Signal Processing，1993，41(12):3445-3462.

［4］ Low Y，Besar R.Wavelet-Based Medical Image Compression Using EZW［C］//The 4th National Conference on Telecommunication Technology(NCTT 2003).Malaysia，2003:203-206.

［5］ 張雷，陳向東，畢雪.改進的EZW算法在紅外人臉圖象壓縮中的應(yīng)用［J］.傳感技術(shù)學(xué)報，2006，19(6):2699-2706.

［6］ 趙安，吳寶明，卓豫.基于整數(shù)小波變換和嵌入式編碼的ECG信號壓縮［J］.北京生物醫(yī)學(xué)工程，2006，25(6):606-610.

［7］ 張國華，張文娟，薛鵬翔.小波分析與應(yīng)用基礎(chǔ)［M］.西安:西北工業(yè)大學(xué)出版社.2006:1-3.

［8］ Dabechies I，Swedens W.Factoring Wavelet Trans-Forms into Lifting Steps［J］.Fourier Anal，1988，4(3):247-269.

［9］ Adams M D，Kossentni F.Reversible Integer-to-Integer Wavelet Transforms for Image Compression:Performance Evaluation and A-nalysis［J］.IEEE Transactions on Image Processing，2000，9(6):1010-1024.

［10］ Bilgin A，Marcellin M W，Altbach M I.Compression of Electrocardiogram Signals Using JPEG 2000［J］.IEEE Transactions on Consumer Electronics，2003，49(4):833-840.

［11］ Ebrahimzadeh A，Azarbad M.ECG Compression Using Wavelet Transform and Three-Level Quantization［C］//2010 6th International Conference on Digital Content，Multimedia Technology and its Applications(IDC2010).Korea，2010:250-254.

［12］ MIT.MIT-BIH Arrhythmia Database［OL/DB］.http://www.physionet.org/physiobank/database/mitdb/，2011-12-28.