基于嵌入式零树小波的心电信号压缩算法及实现*

蒋国华，潘健勇，董齐芬，俞 立*

(1.浙江工业大学信息工程学院，杭州310023;2.杭州市特种设备检测院，杭州310023)

心脏疾病已经成为威胁人类健康和生命的头号杀手。心电监护通过连续观察监测心脏电活动情况，可实时观察病情，获得可靠且有价值的心电活动指标，因此给医生对心电活动异常者的诊断和处理，带来重要价值。现有大型心电监护设备虽然在精确度和可靠性等各方面具有优势，但是其体积庞大、价格昂贵，通常只有医院配备此类设备，患者必须去医院才能使用;而使用其他基于存储卡的便携式心电监护设备，患者必须定时去医疗中心提交其心电数据，便利性比较差。

近几年随着无线通信技术的快速发展，无线技术在医疗、监护领域得到广泛应用，基于无线通信的便携式心电监护设备应运而生。但受能量供应、处理能力、存储容量和通信带宽等方面的限制，要求传输和存储过程中数据量尽可能小，因此数据压缩显得十分重要。现有心电数据压缩算法主要分为直接压缩法和变换压缩法两大类［1-2］:前者通过直接去除原始数据中的冗余数据实现压缩，主要有FAN、AZTEC、CORTES、ASEC等，这类算法易于实现但很难同时保证较高的压缩率和保真度;后者则通过各种变换去除数据间的相关性，用少量变换域分量保持原始数据的信息，主要有 DFT、DCT、DWT、KLT等，它们能同时保证较高的压缩率和信息保真度，但是算法复杂度通常比较高。

Shapiro提出的EZW(Embedded Zero-tree Wavelet)算法［3］是最早实现的基于小波变换的嵌入式编码方法，是一种根据数据重要性进行编码的简单、有效的压缩算法［4］。EZW编码最早应用于二维图像压缩，图像的绝大部分信息集中于低频子带，即经过小波变换，低频子带中的小波系数通常要大于高频子带中相应的小波系数。正是从这个特点出发，产生了零树结构的概念，而大量零树的存在保证了较高的压缩率［5］。一维心电信号经小波变换产生的系数也具有类似的结构，因此也可利用EZW算法进行数据压缩。但直接使用基本的EZW算法对心电数据进行编码，不能充分发挥心电信号周期性好、信息集中于低频分量的特点，其压缩率仍有很大的提高空间。

针对以上问题，本文在研究EZW编码算法的基础上提出一种基于5/3提升小波变换的改进EZW压缩算法，应用于心电信号压缩，在保持基本算法高保真度的同时获得更高压缩率。最后通过仿真比较了基本EZW编码算法与改进算法的压缩效果，并在物理硬件上运行改进算法。

1 嵌入式零树小波编码算法

小波变换具有良好的时频聚集性能和信号逼近性能，因而在数据压缩领域获得了广泛应用［6］。近年来出现的第二代小波变换，也称整数小波变换，继承了第一代小波变换的优点，并且本身具有不依赖傅里叶变换、无需浮点运算、计算完全可逆以及可进行同址运算等优点，因此在工程应用中发挥着巨大作用［7］。

本文提出的算法基于5/3提升小波变换［8］对原始数据进行时频分析。5/3提升小波变换就是通过5/3提升算法实现的整数小波变换。相比于其他整数小波变换，5/3小波变换在计算复杂度和压缩性能上能更适合于心电信号的压缩［9］。由提升方案构成的整数小波变换包括分裂、预测和更新3个步骤。将2j个数据进行一次5/3提升小波正变换的过程如下:

Step 1:分裂。将原数据分为奇数列oi和偶数列ei。

Step 2:预测。由偶数序列预测奇数序列，得到细节系数，对应于原数据的高频部分，如式(1)。

Step 3:更新。由细节系数序列更新偶数序列，对应于原数据的低频部分，如式(2)。

其中，⎿」表示向下取整，di表示高频系数，ui表示低频系数。

对低频部分继续分裂、预测、更新，经过n次循环分解，数据按照从低频到高频排列，可表示为序列{X0，X1，X2，…，X2j-1}。可以发现，原始信号被分解成n层二叉树结构:除最低频部分外，第n层的系数对应两个第n-1层系数。其对应关系可用父节点和子节点的关系描述。以16点数据为例，经过3层小波分解得到如图1所示树形结构。

图1 小波分解示意

经过上述小波变换，父节点的数值有很大概率比其子孙节点的大。因此当一个节点比某阈值小时，很有可能其所有子孙节点也小于该阈值，这便形成一棵“零树”。可以发现心电信号数据经小波变换存在大量零树，可利用EZW算法对变换后的所有高频系数进行压缩。

完成EZW算法需要构建两张表:主表用于保存小波系数的类型;而副表用于确定重要系数的数值范围。小波系数有以下四种类型:①正重要系数(POS):若对于一个给定阈值T，小波系数xi≥T;②负重要系数(NEG):若对于一个给定阈值T，小波系数xi≤-T;③零树根(ZTR):小波系数xi和它的所有子孙均不是重要系数;④孤立零(IZ):小波系数xi不是重要系数，但它的后代中存在重要系数。其中，正重要系数和负重要系数统称为重要系数。由于只有4种类型，用2个比特位即可编码。EZW算法编码流程如图2实线部分。解压为压缩的逆过程。

图2 EZW算法及改进算法流程图

2 算法改进

由基本EZW算法的压缩结果可以看出，主表中大多是ZTR，而IZ、POS、NEG只占很少一部分，并且这种比例差异在第一次迭代时特别明显。随着迭代次数增加，ZTR所占比例越来越小。因此，在第一次迭代中，主表中大多数符号用于记录ZTR，并且其中的很大一部分在第二次迭代中变为 IZ、POS或NEG，即第一次迭代只为了少数几个大于初始阈值的系数而进行。另外，还有一部分ZTR在后续每一次迭代中仍是ZTR，即每次迭代重复扫描及编码一些始终处于零树中的数据。

针对以上发现，本文对基本EZW算法做以下改进:合并第一次和第二次迭代，判断第一次出现的非重要系数在第二次迭代中是否为重要系数;第一次迭代中出现的ZTR在最后一次迭代中是否仍为ZTR，若在最后一次迭代时为零树，则在前面迭代中阈值更大，必为零树。而后续的几次迭代则仍使用基本算法的方法进行编码。为此需要在合并的第一次迭代过程中引进几个新的编码符号:①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个编码符号，所以改进算法第一次迭代中每个数据类型需要三个比特位编码。

在上述前提下，本文提出改进算法的第一次迭代如图2虚线部分所示，步骤如下:

Step 1:初始化。算法必须先确定一个初始阈值，以后每次迭代的阈值由初始阈值计算得到。初始阈值的确定方法并不唯一，本文采用式(3)定义:

Step 2:主扫描。依次将未扫描系数与T0和T0/2比较，判断其类型。按照系数的类型做出相应处理:如果是 POS1、NEG1 或者 POS2、NEG2，相应类型编码保存至主表，保存系数绝对值，并将系数序列中相应的位置置0;如果是 IZ、ZTR1、ZTR2，仅将相应类型编码保存至主表中。每扫描一个数据，标记其状态为本次迭代已扫描，若其类型为ZTR1，标记其每个子孙为本次迭代已扫描，若其类型为ZTR2，标记其每个子孙为所有迭代已扫描。待所有系数均为已扫描，将阈值减半，进入副扫描。主扫描流程图如图3所示。

图3 改进算法第一次主扫描流程

Step 3:副扫描。副扫描和基本算法相同，只是由于主扫描结合了基本算法的两次迭代，所以改进算法相应的副扫描也要进行两次。需注意，在两次副扫描中间对阈值进行一次减半操作。基本算法的一次副扫描过程如图4所示。

由于基本算法第一次迭代中出现的非重要系数有很大一部分在第二次迭代中成为重要系数，因此改进算法的第一次迭代与基本算法的前两次迭代相比，记录类型的编码数据明显减少，即提高了压缩率。提前判断并标记第一次出现零树是否在整个过程中一直是零树，可以减少在后续迭代中对零树的判断及编码，以提高算法的压缩率和计算效率。

图4 基本算法副扫描流程

3 实验结果

3.1 算法评价标准

本文分别从仿真实验和实际物理实验对基本EZW算法和改进算法进行验证，以检验改进算法的有效性。实验以压缩比(Compression Radio，CR)、重构失真率(Percent Root-mean-square Difference，PRD)和重构相似度(Correlation Coefficient，CC)作为评估指标［10-11］，分别对应式(4)～(6):

其中，xi表示压缩前的小波系数，是经小波变换之后的高频分量数据是其平均值;yi表示压缩后的数据：表示解压后的数据?是其平均值。

3.2 仿真结果

本文以MATLAB作为仿真平台，以MIT-BIH心律不齐数据库［12］为样本数据集。首先以100号数据的前1 024个点定性验证算法的可行性。其原始数据(经偏移和放大的电压信号)和其经压缩、还原后的数据如图5所示。从图5可以发现，改进算法的数据失真度小，能保持很好的相似度，从而验证算法可用于心电信号的压缩。

图5 100号数据仿真图

进一步选取 100、101、113、124、217 等五个记录，在不同层次下定量计算和对比基本算法和改进算法。在每个记录中取500组互不包含的连续数据，每组取102 4个点。分别使用基本算法和改进算法对每组数据进行压缩并解压，然后分别计算其CP值、PRD值和CC值，最后求得500组数据的平均值。表1、表2、表3分别在4层、5层和6层编码下对比基本算法与改进算法的性能(未改进算法一次迭代视为一层编码，改进算法的第一次迭代视为两层编码)。

表1 4层编码算法比较

表2 5层编码算法比较

表3 6层编码算法比较

从上述实验数据可以看出，改进算法在保持解压前后失真度和相似度不变的同时提高了数据的压缩率。经对比发现，运行在5层编码时，同时具有理想的压缩率和保真度，压缩效果最佳，故本文采用5层编码的改进算法进行实际物理实验。

3.3 实际运行

本文提出的改进算法采用NesC语言实现，运行在Crossbow公司的MICAZ节点上，而上位机运行解码程序。在250 Hz的采样频率下每采样512个数据进行一次5层改进编码压缩，将压缩后的数据通过无线网络传输到上位机进行解码，同时将原始数据一并发往上位机以计算各指标。图6为MICAZ节点以及心电信号采集电路，图7为上位机显示的4 096个点原始信号(经偏移和放大的电压信号)和重构信号图，表4给出了5组实测数据的压缩情况。

图6 MICAZ节点图

图7 上位机的重构图

表4 实测数据

表4数据显示，本文提出的改进算法用于实际采样数据，可以得到满意的结果。

4 结束语

针对无线心电监护设备资源有限的特点和心电信号本身的特性，本文设计了一种基于5/3提升小波变换的改进EZW压缩算法。该算法将基本EZW算法第一次和第二次迭代加以合并，在保持信号失真度和相似度的同时提高数据压缩率。通过仿真实验比较和实际物理实验验证了算法的可行性和有效性，满足便携式心电监护设备对数据压缩的需求。

［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实现［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算法在红外人脸图象压缩中的应用［J］.传感技术学报，2006，19(6):2699-2706.

［6］ 赵安，吴宝明，卓豫.基于整数小波变换和嵌入式编码的ECG信号压缩［J］.北京生物医学工程，2006，25(6):606-610.

［7］ 张国华，张文娟，薛鹏翔.小波分析与应用基础［M］.西安:西北工业大学出版社.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.