CN101268936A - ECG compression method and decoding method for wireless ECG monitor - Google Patents

Abstract

Translated fromChinese

本发明属于生物医学工程及计算机领域，涉及一种基于提升小波包最优空间进行嵌入式零树编码实现心电数据高效压缩方法，对预处理得到的心电信号进行奇偶序列分解，通过提升算法获取一阶概貌和一阶细节节点；根据代价函数分析一阶父节点是否需要分解为子结点，将需要分裂的一阶父结点通过提升算法分解为二阶子结点；以此类推，直到获取最低信息熵的提升小波包空间结构；最后依据上述获取的最优提升小波包基下的低冗余映射关系，进行嵌入式零树编码算法实现心电数据的高效压缩。本发明针对远程心电监护终端的系统特性，实现了具有可移植入监护终端的心电数据高效压缩算法，从而解决了远程心电监护中数据存储和实时传输问题。

The invention belongs to the fields of biomedical engineering and computer, and relates to a method for efficiently compressing electrocardiogram data by embedded zero-tree coding based on the optimal space of lifting wavelet packets, decomposing the odd-even sequence of the electrocardiogram signal obtained by preprocessing, and using the lifting algorithm Obtain the first-order overview and first-order detail nodes; analyze whether the first-order parent node needs to be decomposed into child nodes according to the cost function, and decompose the first-order parent node that needs to be split into second-order child nodes through the promotion algorithm; and so on, Until the lifting wavelet packet space structure with the lowest information entropy is obtained; finally, according to the low-redundancy mapping relationship under the optimal lifting wavelet packet base obtained above, an embedded zero-tree coding algorithm is performed to realize efficient compression of ECG data. Aiming at the system characteristics of the remote ECG monitoring terminal, the invention realizes an efficient compression algorithm of ECG data that can be transplanted into the monitoring terminal, thereby solving the problems of data storage and real-time transmission in the remote ECG monitoring.

Description

Translated fromChinese

无线心电监护仪的心电压缩方法和解码方法ECG compression method and decoding method for wireless ECG monitor

技术领域technical field

本发明属于生物医学工程技术领域，具体涉及无线心电监护仪的心电压缩方法和解压缩方法。The invention belongs to the technical field of biomedical engineering, and in particular relates to a method for compressing and decompressing an electrocardiogram of a wireless electrocardiogram monitor.

背景技术Background technique

近年来，随着人们生活工作压力的增大以及社会的老龄化发展，各类心脏疾病的发病率呈逐年上升趋势。传统的患者与医生之间面对面的诊断模式已经不能满足人们对健康保健日益增长的巨大需求，医疗体系逐渐向以家庭为中心倾斜，人们也更加重视对疾病的预防。这些变化直接驱使心电监护从非实时非在线监护发展到基于移动通信网络的远程心电监护，穿戴式无线心电监护仪由此应运而生。In recent years, with the increase of people's life and work pressure and the aging of society, the incidence of various heart diseases has been increasing year by year. The traditional face-to-face diagnosis mode between patients and doctors can no longer meet the huge growing demand for health care. The medical system is gradually tilted towards family-centered, and people are paying more attention to disease prevention. These changes directly drive the development of ECG monitoring from non-real-time off-line monitoring to remote ECG monitoring based on mobile communication networks, and wearable wireless ECG monitors emerge as the times require.

穿戴式无线心电监护仪作为远程医疗和移动家庭保健系统的诊断监护终端，不仅需要完成大量心电数据的记录和存储，而且，为了实现对患者及时有效的监护，甚至是24小时全天候监护，更需要具备心电数据的实时传输能力。因此，为了达到上述目的，必须在监护终端进行心电数据的高效压缩：一方面通过提高数据压缩比，增强心电监护仪的数据存储能力，并以此减少传输同等信息时所需要的数据量，提升心电数据的实时传输能力；另一方面，通过提高压缩算法的执行效率，大大缩短心电数据压缩需要的耗时，进一步提升监护终端的数据传输实时性。由此可见，实现适用于心电监护终端的高效数据压缩算法，是实现远程实时心电监护的关键技术。As a diagnostic monitoring terminal for telemedicine and mobile home health care systems, wearable wireless ECG monitors not only need to complete the recording and storage of a large amount of ECG data, but also, in order to achieve timely and effective monitoring of patients, even 24 hours a day, It is more necessary to have the real-time transmission capability of ECG data. Therefore, in order to achieve the above goals, it is necessary to efficiently compress the ECG data in the monitoring terminal: on the one hand, by increasing the data compression ratio, the data storage capacity of the ECG monitor can be enhanced, and the amount of data required to transmit the same information can be reduced. , improve the real-time transmission capability of ECG data; on the other hand, by improving the execution efficiency of the compression algorithm, the time-consuming required for ECG data compression is greatly shortened, and the real-time data transmission of the monitoring terminal is further improved. It can be seen that realizing an efficient data compression algorithm suitable for ECG monitoring terminals is a key technology for realizing remote real-time ECG monitoring.

目前心电数据压缩算法主要分为两大类，一类是时域压缩算法，其中应用最多的是折线拟合。该算法执行效率高，压缩比大，适合移植到系统资源紧张的监护终端，但这种方法存在一个无法克服的问题，即解压后有很大的信号失真。另一类是变换域压缩算法，主要包括KL(Karhunen-Loeve)变换，离散余弦变换和传统小波变换。其中KL变换和离散余弦变换具有很好的静态压缩性能，较早被引入心电压缩中，但因为这两种算法不能做局部分析与分层处理，无法实时地以逐步浮现方式传送数据，大大影响了数据传输效率。而另一方面，这两种算法的复杂性程度高，要求占用较多的系统资源，因此很少用于监护终端的心电数据压缩。相对的，传统小波变换则因其在时、频域同时具有良好的局部化特性，可以采用子频带、层次编码技术实现累进传输编码以解决传输实时性问题，由此产生了小波域嵌入式零树编码算法。该方法借助于小波变换的时频分析优势已经成功应用于图像压缩JPEG2000中，而在心电信号压缩方面，该算法的应用也取得了一定的进展，但到目前为止，该算法主要应用于系统资源丰富的服务端心电存储备份系统，如果要应用于监护端的心电压缩，该算法必须解决自身存在的两大问题：首先，小波域嵌入式零树编码算法存在压缩结果有较大冗余的瓶颈问题：从信息论角度看数据压缩实质是提取信号的有序性，去除冗余，也即是降低信息熵的过程。在信息论中，信息熵反映了信号的无序程度，信息熵越大，信号越无序。由于传统小波域嵌入式零树编码采用固定频带分解方式往往会导致编码流中高信息熵孤立零的产生，这必然会使得信息熵无法充分地降低、压缩结果仍有较大冗余。其次，小波域嵌入式零树编码算法仍然存在较高的算法复杂性和资源占用率：算法过程中采用浮点数计算，不仅占用大量资源，而且执行效率低；算法过程中仍然存在很多冗余步骤，比如算法中采取先作各尺度变换，而后二抽取扔掉各尺度上的一半冗余数据，大量浪费了内存空间，而且增加了运算量。At present, the ECG data compression algorithm is mainly divided into two categories, one is the time domain compression algorithm, and the most widely used one is the polyline fitting. The algorithm has high execution efficiency and high compression ratio, and is suitable for porting to monitoring terminals with tight system resources. However, there is an insurmountable problem in this method, that is, there is a large signal distortion after decompression. The other is the transform domain compression algorithm, mainly including KL (Karhunen-Loeve) transform, discrete cosine transform and traditional wavelet transform. Among them, KL transform and discrete cosine transform have very good static compression performance, and were introduced into ECG compression earlier. However, because these two algorithms cannot do local analysis and hierarchical processing, they cannot transmit data in real-time in a gradual and emergent manner. It affects the data transmission efficiency. On the other hand, these two algorithms are highly complex and require more system resources, so they are rarely used for ECG data compression of monitoring terminals. In contrast, the traditional wavelet transform has good localization characteristics in both the time and frequency domains, and can use sub-band and hierarchical coding techniques to realize progressive transmission coding to solve the problem of real-time transmission. Tree encoding algorithm. This method has been successfully applied to image compression JPEG2000 by virtue of the time-frequency analysis advantages of wavelet transform. In the aspect of ECG signal compression, the application of this algorithm has also made some progress, but so far, this algorithm is mainly used in system resources. Rich ECG storage and backup system at the server side, if it is to be applied to ECG compression at the monitoring side, the algorithm must solve two major problems: First, the embedded zero-tree coding algorithm in the wavelet domain has large redundancy in the compression results Bottleneck problem: From the perspective of information theory, the essence of data compression is to extract the order of signals and remove redundancy, that is, the process of reducing information entropy. In information theory, information entropy reflects the degree of disorder of the signal, the greater the information entropy, the more disorder the signal. Because traditional wavelet domain embedded zero tree coding adopts fixed frequency band decomposition method, it often leads to the generation of isolated zeros with high information entropy in the coded stream, which will inevitably make the information entropy unable to be fully reduced, and the compression results still have large redundancy. Secondly, the embedded zerotree coding algorithm in the wavelet domain still has high algorithm complexity and resource occupancy: floating-point calculations are used in the algorithm process, which not only takes up a lot of resources, but also has low execution efficiency; there are still many redundant steps in the algorithm process , for example, in the algorithm, the scale transformation is performed first, and then the second extraction discards half of the redundant data on each scale, which wastes a lot of memory space and increases the amount of calculation.

发明内容Contents of the invention

本发明的主旨是提供一种适合于心电监护终端进行心电数据压缩和解码方法，以此提升远程心电监护终端的数据存储和实时传输能力。The gist of the present invention is to provide a method for compressing and decoding ECG data suitable for ECG monitoring terminals, thereby improving the data storage and real-time transmission capabilities of remote ECG monitoring terminals.

为此，本发明采用如下的技术方案：For this reason, the present invention adopts following technical scheme:

一种无线心电监护仪的心电压缩方法，包括下列步骤：An electrocardiographic compression method for a wireless electrocardiographic monitor, comprising the following steps:

(1)对采集到的心电信号进行预处理；(1) Preprocessing the collected ECG signals;

(2)对预处理得到的心电信号进行奇偶序列分裂，而后通过提升算法获取一阶细节信号节点和一阶概貌信号节点；(2) Split the odd-even sequence of the ECG signal obtained by preprocessing, and then obtain the first-order detail signal node and the first-order overview signal node through the lifting algorithm;

(3)根据代价函数判断一阶细节和一阶概貌父节点是否需要分解为子节点，如果需要，则将其进行奇偶序列分裂，而后通过提升算法获取相应的二阶子节点；(3) According to the cost function, it is judged whether the first-order detail and first-order overview parent nodes need to be decomposed into child nodes, and if necessary, split them into parity sequences, and then obtain the corresponding second-order child nodes through the promotion algorithm;

(4)根据代价函数判断二阶子节点中是否有需要继续分解为相应的三阶子节点，采用提升算法将这些二阶子节点进行分解，以此类推，直到获得最低信息熵的最优小波包空间结构；(4) According to the cost function, it is judged whether the second-order child nodes need to be further decomposed into corresponding third-order child nodes, and these second-order child nodes are decomposed by the lifting algorithm, and so on, until the optimal wavelet with the lowest information entropy is obtained package space structure;

(5)遍历小波包所有系数，求出系数绝对值的最大值，保留该数值二进制位的最高位，将其余低位置零，而后将所得结果作为初始阈值；建立主表、辅表存储空间，将上面获得的心电信号小波包分解结果存入主表，开启辅助扫描堆栈和编码结果存储空间；将初始阈值赋值给阈值(T)；(5) Traversing all the coefficients of the wavelet packet, finding the maximum value of the absolute value of the coefficients, retaining the highest bit of the binary digit of the value, and setting the remaining low positions to zero, and then using the obtained result as the initial threshold value; establishing the storage space of the main table and the auxiliary table, Store the decomposition result of the wavelet packet of the ECG signal obtained above into the main table, open the auxiliary scan stack and the storage space for the encoding result; assign the initial threshold to the threshold (T);

(6)对主表进行扫描，把表上的每个节点都依据阈值(T)分为正重要系数、负重要系数、零树根、孤立零，将扫描结果存入主表中；(6) Scan the main table, divide each node on the table into positive importance coefficient, negative importance coefficient, zero tree root, and isolated zero according to the threshold (T), and store the scanning result in the main table;

(7)将主表翻译成二进制码流存进编码结果存储空间中，将主表中标记为正重要系数和负重要系数的节点移至辅助扫描堆栈；(7) translate the main table into a binary code stream and store it in the encoding result storage space, and move the nodes marked as positive and negative important coefficients in the main table to the auxiliary scanning stack;

(8)对辅助扫描堆栈进行辅助扫描，根据阈值(T)和节点大小关系来进行“0”、“1”编码，同时将数据流存入编码结果存储空间中；(8) Auxiliary scanning is performed on the auxiliary scanning stack, and "0" and "1" are encoded according to the relationship between the threshold (T) and the node size, and the data stream is stored in the encoding result storage space at the same time;

(9)更新阈值(T)为当前阈值的1/2，返回步骤6，重复步骤(6)至(9)的主、辅扫描过程，直至阈值(T)为0；(9) Update the threshold (T) to be 1/2 of the current threshold, return tostep 6, and repeat the main and auxiliary scanning processes of steps (6) to (9) until the threshold (T) is 0;

(10)建立无线传输数据包，在头标记里记录最优小波包树结构以及数据量大小和初始阈值信息，通过无线网络发送数据包。(10) Establish a wireless transmission data packet, record the optimal wavelet packet tree structure, data size and initial threshold information in the header tag, and send the data packet through the wireless network.

本发明同时提供一种上述心电编码的解码方法，包括下来步骤：The present invention simultaneously provides a kind of decoding method of above-mentioned electrocardiogram, comprises following steps:

(1)接收经过无线网络传输的数据包；(1) Receive data packets transmitted through the wireless network;

(2)读取头标记，获取最优小波包树结构，获取数据量大小、初始阈值，将初始阈值赋值给阈值(T)；(2) Read the head mark, obtain the optimal wavelet packet tree structure, obtain the size of the data volume and the initial threshold, and assign the initial threshold to the threshold (T);

(3)读取主表数据流，对重构数据位置进行相应标记，重构数据，如果为正、负重要系数，则初始重构值为阈值(T)的正或负3/2倍，其余的位置均为零；(3) Read the data stream of the main table, mark the location of the reconstructed data accordingly, and reconstruct the data. If it is a positive or negative important coefficient, the initial reconstruction value is positive or negative 3/2 times the threshold (T), The rest of the positions are zero;

(4)读取辅表数据流，如果为“0”则重构值绝对值在原系数绝对值的基础上减去阈值(T)的1/4，否则在原来值的基础上加上阈值(T)的1/4，逐步精确重构值；(4) Read the auxiliary table data stream, if it is "0", then the absolute value of the reconstructed value is based on the absolute value of the original coefficient minus 1/4 of the threshold (T), otherwise the threshold is added to the original value ( 1/4 of T), gradually and accurately reconstructing the value;

(5)更新阈值(T)为当前阈值的1/2，返回步骤(3)至(5)的扫描码流过程，直到完成解码。(5) Update the threshold (T) to 1/2 of the current threshold, and return to the process of scanning the code stream from steps (3) to (5) until the decoding is completed.

发明人针对远程心电监护终端系统中存在的数据存储和心电实时传输的问题，力图从理论分析和实践论证的角度找出一种高效的心电压缩算法。首先通过分析传统小波变换的特点，找出它在心电监护终端的数据压缩应用中存在的问题，而后分别从解决传统小波压缩方法的压缩比瓶颈问题以及提升算法执行效率、降低资源占用率方面着手，提出了基于最优小波包空间进行快速提升嵌入式零树编码算法实现心电数据的高效压缩，同时实现了信源重构质量可伸缩的累进传输编码。经过实验数据分析验证，本发明提供的基于快速提升小波包嵌入式零树编码方法，不仅充分利用了心电信号的频域相关性，大大降低了心电信号的信息熵，而且通过引入蝶形算法原址操作和整数运算的优势，有效的提高了算法执行效率，实现了心电监护终端的心电数据高效压缩，从而能够实现客户端心电监护终端与服务器端的心电监护专家系统实时准确交互，使心脏病患者获得全天候心电数据的有效监控和记录。Aiming at the problems of data storage and real-time transmission of ECG in the remote ECG monitoring terminal system, the inventor tries to find out an efficient ECG compression algorithm from the perspective of theoretical analysis and practical demonstration. First, by analyzing the characteristics of the traditional wavelet transform, find out the problems existing in the data compression application of the ECG monitoring terminal, and then solve the bottleneck problem of the compression ratio of the traditional wavelet compression method, improve the execution efficiency of the algorithm, and reduce the resource usage. , a fast-enhancing embedded zero-tree coding algorithm based on the optimal wavelet packet space is proposed to achieve high-efficiency compression of ECG data, and at the same time, a progressive transfer coding with scalable quality of source reconstruction is realized. After experimental data analysis and verification, the embedded zero-tree coding method based on the fast lifting wavelet packet provided by the present invention not only makes full use of the frequency domain correlation of the ECG signal, greatly reduces the information entropy of the ECG signal, but also introduces a butterfly The advantages of algorithm in-site operation and integer operation effectively improve the efficiency of algorithm execution and realize the efficient compression of ECG data in the ECG monitoring terminal, so as to realize the real-time and accurate interaction between the ECG monitoring terminal on the client side and the ECG monitoring expert system on the server side , enabling heart disease patients to obtain effective monitoring and recording of ECG data around the clock.

附图说明Description of drawings

图1：小波分解示意图，图1(a)为小波分解树结构，图1(b)小波分解系数关系图；Figure 1: Schematic diagram of wavelet decomposition, Figure 1(a) is the tree structure of wavelet decomposition, Figure 1(b) is the relationship diagram of wavelet decomposition coefficients;

图2：小波包分解结构示意图；Figure 2: Schematic diagram of wavelet packet decomposition structure;

图3：小波包变换中父子结点的代价曲线示意图；Figure 3: Schematic diagram of the cost curve of parent-child nodes in wavelet packet transform;

图4：Le_Gall 5/3小波提升结构图；Figure 4: Le_Gall 5/3 wavelet lifting structure diagram;

图5：三种算法的心电数据压缩结果对比。Figure 5: Comparison of the ECG data compression results of the three algorithms.

具体实施方式Detailed ways

下面结合附图、原理和实施例从几个方面对本发明做进一步详述。The present invention will be further described in detail from several aspects below in conjunction with the accompanying drawings, principles and embodiments.

1.压缩比瓶颈问题的突破-最优小波包空间的心电数据零树编码1. A breakthrough in the compression ratio bottleneck problem - the zero-tree coding of ECG data in the optimal wavelet packet space

在多分辨率的理论框架下，S.Mallat设计出来基于正交滤波器组的小波分解和重构算法，即所调的Mallat算法。Mallat算法下对心电信号s(n)的小波变换为Under the theoretical framework of multi-resolution, S. Mallat designed a wavelet decomposition and reconstruction algorithm based on orthogonal filter banks, namely the adjusted Mallat algorithm. The wavelet transform of the ECG signal s(n) under the Mallat algorithm is

${\mathrm{<span><span>s</span>the\; s</span>}}^{<span><span>(</span>(</span>\mathrm{<span><span>j</span>j</span>}<span><span>)</span>)</span>}<span><span>(</span>(</span>\mathrm{<span><span>n</span>no</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\underset{\mathrm{<span><span>k</span>k</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}\mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>s</span>the\; s</span>}}^{<span><span>(</span>(</span>\mathrm{<span><span>j</span>j</span>}<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}<span><span>)</span>)</span>}<span><span>(</span>(</span>\mathrm{<span><span>n</span>no</span>}<span><span>-</span>-</span>{\mathrm{<span><span>2</span>2</span>}}^{\mathrm{<span><span>j</span>j</span>}<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>1</span>1</span>}<span><span>)</span>)</span>$

${\mathrm{<span><span>d</span>d</span>}}^{<span><span>(</span>(</span>\mathrm{<span><span>j</span>j</span>}<span><span>)</span>)</span>}<span><span>(</span>(</span>\mathrm{<span><span>n</span>no</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\underset{\mathrm{<span><span>k</span>k</span>}}{\mathrm{<span><span>\&Sigma;</span>\&Sigma;</span>}}\mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>s</span>the\; s</span>}}^{<span><span>(</span>(</span>\mathrm{<span><span>j</span>j</span>}<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}<span><span>)</span>)</span>}<span><span>(</span>(</span>\mathrm{<span><span>n</span>no</span>}<span><span>-</span>-</span>{\mathrm{<span><span>2</span>2</span>}}^{\mathrm{<span><span>j</span>j</span>}<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}\mathrm{<span><span>k</span>k</span>}<span><span>)</span>)</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>2</span>2</span>}<span><span>)</span>)</span>$

式中j为小波变换尺度；h(k)是低通滤波器，信号通过h(k)逐级平滑，反映出原始信号的概貌信息；而g(k)是高通滤波器，d^(j)(n)是s^(j-1)(n)和s^(j)(n)之间的差异，反映了信号的细节部分。图1(a)为小波分解示意图，其中结点S代表原始信号；结点L_j表示在尺度j上的概貌信息，即s^(j)(n)；结点H_j表示在尺度j上的细节信息，即d^(j)(n)。In the formula, j is the wavelet transform scale; h(k) is a low-pass filter, and the signal is smoothed step by step through h(k), reflecting the general information of the original signal; and g(k) is a high-pass filter, d^(j) (n) is the difference between s^(j-1) (n) and s^(j) (n), reflecting the detailed part of the signal. Figure 1(a) is a schematic diagram of wavelet decomposition, where node S represents the original signal; node L_j represents the profile information on scale j, that is, s^(j) (n); node H_j represents the profile information on scale j Details, ie d^(j) (n).

Shapiro发现，在对信号做小波变换的过程中，跨频带的小波系数之间具有显著的相关特性。如图1(b)中所示，在Mallat算法下，采样过程中得到的小波系数呈倒金字塔结构，且其总数不变，这些小波系数的相关性表现在两个方面：①对于每个细节信息系数H_j，k(j尺度上的第k个系数)必可找到相邻小尺度下与之对应的两个相关系数H_j-1，2k和H_j-1,2k+1。而概貌信息与同尺度的细节信息具有一一对应的系数关系。②一般而言，如果小波系数H_j，k在给定编码阈值下无意义，则其所对应的相关系数H_j-1，2k和H_j-1，2k+1在该阈值下一般也无意义。Shapiro found that in the process of wavelet transforming the signal, there is a significant correlation between the wavelet coefficients across frequency bands. As shown in Figure 1(b), under the Mallat algorithm, the wavelet coefficients obtained during the sampling process have an inverted pyramid structure, and the total number remains unchanged. The correlation of these wavelet coefficients is manifested in two aspects: ① For each detail The information coefficient H_j,k (the kth coefficient on the j scale) must be able to find two corresponding correlation coefficients H_j-1,2k and H_j-1,2k+1 in the adjacent small scales. The general information has a one-to-one correspondence coefficient relationship with the detailed information of the same scale. ② Generally speaking, if the wavelet coefficient H_{j, k} is meaningless under a given coding threshold, then its corresponding correlation coefficients H_{j-1, 2k} and H_{j-1, 2k+1} are generally meaningless under this threshold significance.

Shapiro利用小波变换的上述特性，实现信息熵的降低，提出了小波域嵌入式零树编码算法，特点②所对应的小波系数H_j，k称为零树根，H_j，k与它的所有相关系数构成了零树，而零树具有很低的信息熵，只需要非常少的比特流表示，这正是该方法实现压缩的基本条件。但是由于一般的小波分解尚未实现充分的熵减，因此会存在冗余信息，使其小波系数可能出现一些特殊情况：当小波系数H_j，k在给定编码阈值下无意义，而其所对应的相关系数中却出现有意义的情况，这种系数H_j，k被称为孤立零。孤立零的存在，使得无法根据H_j，k直接判断其相关系数的信息，因此不能仅仅编码H_j，k还必须考查H_j，k所对应的所有相关系数，这必将增加所需编码的系数，同时也将增加运算工作量，这些都不利于高效压缩的实现。Shapiro uses the above characteristics of wavelet transform to reduce information entropy, and proposes an embedded zerotree coding algorithm in wavelet domain. The wavelet coefficients H_{j and k} corresponding to feature ② are called zero tree roots. H_{j, k} and all its The correlation coefficient constitutes a zero tree, and the zero tree has very low information entropy, and only needs very little bit stream representation, which is the basic condition for this method to achieve compression. However, because the general wavelet decomposition has not yet achieved sufficient entropy reduction, there will be redundant information, which may cause some special cases in its wavelet coefficients: when the wavelet coefficients H_{j, k} are meaningless under a given coding threshold, and their corresponding However, there is a meaningful case in the correlation coefficient of , and this coefficient H_j,k is called an isolated zero. The existence of isolated zero makes it impossible to directly judge the information of its correlation coefficient according to H_{j, k} , so it is not possible to only encode H_{j, k,} but also to examine all the correlation coefficients corresponding to H_{j, k} , which will increase the required encoding. coefficient, and will also increase the computational workload, which is not conducive to the realization of efficient compression.

为了克服小波域嵌入式零树编码压缩算法的瓶颈，本发明首先通过数据测试和理论分析找出并验证了该算法无法突破瓶颈的关键因素，即在对心电数据降低信息熵的过程中，小波域嵌入式零树编码压缩算法采取固定的频带分解方式，没有充分考虑频带间的差异性，从而无法实现信息熵的进一步降低。因此，本发明考虑采用新方法来取代传统小波变换的固定频带分解方式，以减少传统小波域嵌入式编码中孤立零的出现以确保编码压缩后信号的熵减。而小波包变换正好能满足这个需要，因为它可根据心电信号的频域自相关性，获得相应的最优小波包频带分解结构，构造对应的最优频域结构码，达到信息熵的进一步降低，这样就可望解决信号压缩的瓶颈。In order to overcome the bottleneck of the embedded zerotree coding compression algorithm in the wavelet domain, the present invention first finds out and verifies the key factor that the algorithm cannot break through the bottleneck through data testing and theoretical analysis, that is, in the process of reducing the information entropy of the ECG data, The wavelet domain embedded zerotree coding compression algorithm adopts a fixed frequency band decomposition method, which does not fully consider the differences between frequency bands, so that the further reduction of information entropy cannot be realized. Therefore, the present invention considers adopting a new method to replace the fixed frequency band decomposition method of the traditional wavelet transform, so as to reduce the occurrence of isolated zeros in the traditional wavelet domain embedded coding and ensure the entropy reduction of the coded compressed signal. The wavelet packet transform can just meet this need, because it can obtain the corresponding optimal wavelet packet frequency band decomposition structure according to the frequency domain autocorrelation of the ECG signal, construct the corresponding optimal frequency domain structure code, and achieve a further increase in information entropy. Reduced, so it is expected to solve the bottleneck of signal compression.

为了获得这种最优频域结构码，需将传统小波变换(图1(a))中的高频细节也加以考虑，进行适当的分解。当所有的结点都需要分解时，可以得到如图2所示的完整小波包分解结构。In order to obtain this optimal frequency-domain structure code, it is necessary to consider the high-frequency details in the traditional wavelet transform (Fig. 1(a)) and perform proper decomposition. When all nodes need to be decomposed, the complete wavelet packet decomposition structure shown in Figure 2 can be obtained.

在实际应用中，获取最优频域结构码的过程是从频域分解的根结点出发，通过衡量每一层尺度上的结点是否值得进行分解，将完整小波包结构进行逐层修剪以获得最优结构。修剪过程中需借助适当的代价函数作为搜索最优频域结构的依据，即要从判断压缩性能优劣的准则出发，充分协调失真率和压缩比来构建代价函数。In practical applications, the process of obtaining the optimal frequency-domain structure code is to start from the root node of the frequency-domain decomposition. By measuring whether the nodes on each scale are worth decomposing, the complete wavelet packet structure is pruned layer by layer. to obtain the optimal structure. In the pruning process, an appropriate cost function should be used as the basis for searching the optimal frequency domain structure, that is, the cost function should be constructed by fully coordinating the distortion rate and compression ratio based on the criteria for judging the compression performance.

有了代价函数之后，就可以通过衡量分解代价，获取最优的小波包空间结构。如下给出了代价函数的推导过程。With the cost function, the optimal wavelet packet space structure can be obtained by measuring the decomposition cost. The derivation process of the cost function is given as follows.

定义D为数据失真率，R为经量化后的数据量，则压缩目的可以表达为：在满足失真要求前提下(D≤D_b，D_b为最大容许失真)，达到最大程度的压缩(minR)。综合考虑失真率和数据量，可以得到相应的拉格朗日代价函数Define D as the data distortion rate, R as the amount of quantized data, then the purpose of compression can be expressed as: under the premise of meeting the distortion requirements (D≤D_b , D_b is the maximum allowable distortion), to achieve the maximum compression (minR ). Considering the distortion rate and the amount of data comprehensively, the corresponding Lagrangian cost function can be obtained

J＝D+λR        (3)J＝D+λR (3)

式中：J为压缩代价，λ为拉格朗日因子(λ≥0)，表示将数据比特率转换到失真率表述空间的质量，定义λ＝ΔD/ΔR，可以根据压缩质量要求来选取。由此，上述压缩目的可转换为：在失真满足要求的前提下，找到最小压缩代价J所对应的频域分解结构。如图3所示，如果D_c1+λ₂R_c1)+(D_c2+λ₃R_c2)≤D_P+λ₁R_P，则将父结点分解成为两个子结点。In the formula: J is the compression cost, λ is the Lagrangian factor (λ≥0), which represents the quality of converting the data bit rate to the distortion rate expression space, and defines λ=ΔD/ΔR, which can be selected according to the compression quality requirements. Therefore, the above-mentioned purpose of compression can be transformed into: on the premise that the distortion meets the requirements, find the frequency-domain decomposition structure corresponding to the minimum compression cost J. As shown in Figure 3, if D_c1 +λ₂ R_c1 )+(D_c2 +λ₃ R_c2 )≤D_P +λ₁ R_P , then the parent node is decomposed into two child nodes.

依据上面给出的最优空间获取准则，对心电信号进行小波包最优空间分解，而后依照各频带空间之间对应的相关性关系，进行嵌入式零树编码，以此突破原有的压缩比瓶颈，实现心电数据的高效压缩。According to the optimal space acquisition criterion given above, the wavelet packet optimal space decomposition is performed on the ECG signal, and then the embedded zero-tree coding is performed according to the corresponding correlation relationship between the frequency band spaces, so as to break through the original compression Compared with the bottleneck, the efficient compression of ECG data is realized.

2.算法执行效率的突破-最优小波包空间提升算法2. Breakthrough in algorithm execution efficiency - optimal wavelet packet space improvement algorithm

通过将嵌入式零树编码算法引入到频带分解结构灵活多变的小波包空间，本发明突破了小波空间零树编码算法的压缩比瓶颈，大大减少了同等信息传输时所需的数据量。但是，相对小波域零树编码算法，影响小波包域的嵌入式零树编码执行效率的核心算法没有改变，而且编码算法部分的复杂性增加了，这就使压缩算法的执行效率进一步降低。因此，本发明在突破传统方法的压缩比瓶颈之后，为了研发出适合于心电监护终端的高效数据压缩方法，对压缩算法的执行过程进一步分析，在通过不断的理论分析和实践论证过程中，最终找出了影响算法执行效率的关键因素：虽然在前面步骤中，通过将嵌入式零树编码算法引入到频带分解结构灵活多变的小波包空间，突破了压缩比瓶颈，但是核心算法仍然采用Mallet算法流程，即采用一种双子带变换方案来分步计算实现，在每一步中，都把信号分解为高频子带和低频子带，然后对其进行抽取采样，对低频子带不断进行递归运算，直到达到所需的分解级数。但如果应用上述算法进行监护终端心电数据压缩编码，就会暴露出很多缺点和不足之处，主要包括如下几个方面：(1)每一级滤波后都将有一半的数据被丢弃，也就是说有一半的乘法计算是无效的；(2)因为浮点系数的存在，传统小波几乎不可能实现整数到整数的小波变换；(3)当对心电数据进行解压缩时，由于传统小波的逆变换实现起来需要二插值后由重建滤波器获得，使用起来麻烦，运算量大；(4)在边界的处理上会产生边界效应，不同的延拓方式会有不同的结果，无法完全实现信号的无损重构；(5)每级变换用到多出低频子带一倍的数据，数据的滤波操作前后相互关联，需要另外的存储单元。By introducing the embedded zerotree coding algorithm into the wavelet packet space with flexible and changeable frequency band decomposition structure, the invention breaks through the compression ratio bottleneck of the wavelet space zerotree coding algorithm, and greatly reduces the amount of data required for the same information transmission. However, compared with the zerotree coding algorithm in the wavelet domain, the core algorithm that affects the execution efficiency of the embedded zerotree coding in the wavelet packet domain has not changed, and the complexity of the coding algorithm has increased, which further reduces the execution efficiency of the compression algorithm. Therefore, after breaking through the bottleneck of the compression ratio of the traditional method, the present invention further analyzes the execution process of the compression algorithm in order to develop an efficient data compression method suitable for the ECG monitoring terminal. During the process of continuous theoretical analysis and practical demonstration, Finally, the key factors affecting the execution efficiency of the algorithm were found: Although in the previous steps, the compression ratio bottleneck was broken through introducing the embedded zero-tree coding algorithm into the wavelet packet space with flexible and variable frequency band decomposition structures, the core algorithm still uses The Mallet algorithm flow is to use a two-subband transformation scheme to realize step-by-step calculation. In each step, the signal is decomposed into high-frequency sub-band and low-frequency sub-band, and then it is extracted and sampled, and the low-frequency sub-band is continuously performed. Operate recursively until the desired number of decomposition levels is reached. However, if the above algorithm is used to compress and encode the ECG data of the monitoring terminal, many shortcomings and deficiencies will be exposed, mainly including the following aspects: (1) half of the data will be discarded after each level of filtering, and That is to say, half of the multiplication calculations are invalid; (2) because of the existence of floating point coefficients, it is almost impossible for the traditional wavelet to realize the wavelet transform from integer to integer; (3) when decompressing the ECG data, due to the traditional wavelet The implementation of the inverse transformation of 2 needs to be obtained by the reconstruction filter after two interpolations, which is troublesome to use and requires a large amount of calculation; (4) There will be boundary effects in the processing of the boundary, and different extension methods will have different results, which cannot be fully realized Lossless reconstruction of the signal; (5) Each level of transformation uses twice as much data as the low-frequency sub-band, and the filtering operation of the data is correlated with each other before and after, requiring an additional storage unit.

由此，针对算法中存在的上述缺点，需要引入一种算法提升机制，提升压缩编码的执行效率，即算法的提升思想。目前，在提升思想的运用方面，快速傅立叶变换对传统傅立叶变换的提升，提升小波变换对传统小波变换的提升都在算法执行效率的提高方面获得了很大的成功，但是，提升思想在小波包空间的运用至今未见报道，而为了保持本发明中已经突破小波域零树编码压缩比的优势，必须将提升思想引入到小波包空间，提出基于提升最优小波包空间的嵌入式零树编码算法。Therefore, in view of the above shortcomings in the algorithm, it is necessary to introduce an algorithm improvement mechanism to improve the execution efficiency of compression coding, that is, the idea of algorithm improvement. At present, in terms of the application of the lifting idea, the improvement of the traditional Fourier transform by the fast Fourier transform and the improvement of the traditional wavelet transform by the lifting wavelet transform have achieved great success in improving the execution efficiency of the algorithm. The use of space has not been reported so far, and in order to maintain the advantages of the present invention that has broken through the wavelet domain zerotree coding compression ratio, the idea of lifting must be introduced into the wavelet packet space, and an embedded zerotree coding based on lifting the optimal wavelet packet space is proposed algorithm.

在进行心电数据压缩时，为了获取心电信号的无损编码，本发明引入了目前JPEG2000推荐的无损编码小波滤波器，Le_Gall 5/3小波，其中5代表低通滤波器长度，3代表高通滤波器长度，具体的小波系数如下表1所示。When compressing ECG data, in order to obtain lossless encoding of ECG signals, the present invention introduces the lossless encoding wavelet filter recommended by JPEG2000 at present, Le_Gall 5/3 wavelet, wherein 5 represents the length of the low-pass filter, and 3 represents the length of the high-pass filter The length of the filter, the specific wavelet coefficients are shown in Table 1 below.

表1Le_all 5/3小波滤波器系数Table 1 Le_all 5/3 wavelet filter coefficients

  NN  分解低通滤波器Decomposed low-pass filter  重建低通滤波器Rebuild the low-pass filter  NN  分解低通滤波器Decomposed low-pass filter  NN  重建低通滤波器Rebuild the low-pass filter  00  3/43/4  1 1  -1 -1  1 1  +1+1  3/43/4  +1，-1+1, -1  1/41/4  1/21/2  0，-20, -2  -1/2-1/2  +2，0+2,0  -1/4-1/4  +2，-2+2, -2  -1/8-1/8  +3，-1+3, -1  -1/8-1/8

表1中的上述系数可以用矩阵形式表示，即：The above coefficients in Table 1 can be expressed in matrix form, namely:

$\mathrm{<span><span>P</span>P</span>}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\left[\begin{array}{cc}<span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>8</span>8</span>}}{\mathrm{<span><span>Z</span>Z</span>}}^{<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}<span><span>+</span>+</span>\frac{\mathrm{<span><span>3</span>3</span>}}{\mathrm{<span><span>4</span>4</span>}}<span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>8</span>8</span>}}\mathrm{<span><span>Z</span>Z</span>}& \frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}<span><span>+</span>+</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}\mathrm{<span><span>Z</span>Z</span>}\\ <span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>Z</span>Z</span>}}^{<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}<span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>4</span>4</span>}<span><span>)</span>)</span>$

为了将提升思想应用于小波包空间，首先需要将能够上述FIR滤波器组计算分解成若干提升步骤，通过分解这些滤波器使得计算过程更加简洁，以此将Mallet算法中先滤波后抽取的步骤替换为先抽取再滤波的新算法。因此，本发明根据提升思想(获取各因子的主对角线为单位1)将P(z)进行分解，得到如下由3部分因式(从左到右分别命名为奇偶分解因式、概貌因式、细节因式)组成的表达式In order to apply the lifting idea to the wavelet packet space, it is first necessary to decompose the calculation of the above-mentioned FIR filter bank into several lifting steps. By decomposing these filters, the calculation process is more concise, so as to replace the steps of filtering first and then extracting in the Mallet algorithm A new algorithm for decimation first and then filtering. Therefore, the present invention decomposes P(z) according to the idea of promotion (obtaining the main diagonal of each factor as unit 1), and obtains the following three-part factor (named from left to right as parity factorization factor, profile factor formula, detail factor) composed of expressions

$\mathrm{<span><span>P</span>P</span>}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\left[\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]\left[\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}& \frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}<span><span>+</span>+</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}\mathrm{<span><span>Z</span><figure-callout\; label="Z"\; filenames="A20081005233700142.png"\; state="\{\{state\}\}">Z</figure-callout></span>}\\ \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]\left[\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>0</span>0</span>}\\ <span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>Z</span>Z</span>}}^{<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}<span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>5</span>5</span>}<span><span>)</span>)</span>$

从第一个因式(奇偶分解因式)可以发现，只要将心电信号分解成奇数序列和偶数序列，就可以省去后抽取步骤，直接获得高频细节和低频概貌信号，即可以采用合并过程替代分裂后再排除冗余数据的过程，降低算法的复杂性。因此，对于心电信号X(z)，通过分解为奇序列X_e(z)和偶序列X_o(z)，就可以采用提升方法分布实现：From the first factor (odd-even decomposition factor), it can be found that as long as the ECG signal is decomposed into an odd sequence and an even sequence, the post-extraction step can be omitted, and the high-frequency details and low-frequency overview signals can be directly obtained, that is, the combined The process replaces the process of splitting and then eliminating redundant data, reducing the complexity of the algorithm. Therefore, for the ECG signal X(z), by decomposing it into an odd sequence X_e (z) and an even sequence X_o (z), it can be realized by using the lifting method distribution:

$\mathrm{<span><span>P</span>P</span>}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span>\mathrm{<span><span>X</span>x</span>}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\left[\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}& \frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}<span><span>+</span>+</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>4</span>4</span>}}\mathrm{<span><span>Z</span><figure-callout\; label="Z"\; filenames="A20081005233700142.png"\; state="\{\{state\}\}">Z</figure-callout></span>}\\ \mathrm{<span><span>0</span>0</span>}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]\left[\begin{array}{cc}\mathrm{<span><span>1</span>1</span>}& \mathrm{<span><span>0</span>0</span>}\\ <span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}{\mathrm{<span><span>Z</span>Z</span>}}^{<span><span>-</span>-</span>\mathrm{<span><span>1</span>1</span>}}<span><span>-</span>-</span>\frac{\mathrm{<span><span>1</span>1</span>}}{\mathrm{<span><span>2</span>2</span>}}& \mathrm{<span><span>1</span>1</span>}\end{array}\right]\left[\begin{array}{c}{\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>e</span>e</span>}}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span>\\ {\mathrm{<span><span>X</span>x</span>}}_{\mathrm{<span><span>o</span>o</span>}}<span><span>(</span>(</span>\mathrm{<span><span>z</span>z</span>}<span><span>)</span>)</span>\end{array}\right]<span><span>-</span>-</span><span><span>-</span>-</span><span><span>-</span>-</span><span><span>(</span>(</span>\mathrm{<span><span>6</span>6</span>}<span><span>)</span>)</span>$

第一步，把信号分解成奇偶序列：d(0，r)＝x_n(2r+1)；s(0，r)＝x_n(2r)；The first step is to decompose the signal into a parity sequence: d(0,r)=x_n (2r+1); s(0,r)=x_n (2r);

第二步，实现细节因式$\left[\begin{array}{cc}1& 0\\ -\frac{1}{2}{Z}^{-1}-\frac{1}{2}& 1\end{array}\right]$的时域计算结果：The second step is to realize the detail factor$\left[\begin{array}{cc}1& 0\\ -\frac{1}{2}{Z}^{-1}-\frac{1}{2}& 1\end{array}\right]$ The time domain calculation result of :

d(j，r)＝d(j，r)-[s(j，r)+s(j，r+1)+1]/2，j＝1，即第一阶尺度的细节信息。d(j, r)=d(j, r)-[s(j, r)+s(j, r+1)+1]/2, j=1, that is, the detailed information of the first-order scale.

第三步，实现概貌因式$\left[\begin{array}{cc}1& \frac{1}{4}+\frac{1}{4}Z\\ 0& 1\end{array}\right]$的时域计算结果：The third step is to realize the profile factor$\left[\begin{array}{cc}1& \frac{1}{4}+\frac{1}{4}\mathrm{<figure-callout\; label="Z"\; filenames="A20081005233700142.png"\; state="\{\{state\}\}">Z</figure-callout>}\\ 0& 1\end{array}\right]$ The time domain calculation result of :

s(j，r)＝s(j，r)-[d(j，r)+d(j，r-1)]/4，j＝1，即第一阶尺度的概貌信息。s(j, r)=s(j, r)-[d(j, r)+d(j, r-1)]/4, j=1, that is, the profile information of the first-order scale.

上述步骤可以用蝶形变换结构图表示，如图4所示。The above steps can be represented by a butterfly transformation structure diagram, as shown in FIG. 4 .

从图中我们可以看出：原始数据分解成奇偶序列d_o⁰、s_o⁰后，经过初次提升计算的结果为d_o¹，它覆盖存储在d_o⁰的原址上，d_o¹、s_o¹(s_o¹＝s_o⁰)二次提升计算的结果为s_l¹，它覆盖存储在s_o⁰的原址上，两者交替进行，互不冲突，这就是所谓的原址操作。这种方法不用新开空间，原始数据逐步被小波系数所取代。上述算法因为出现了因子1/2、1/4，计算结果很可能出现小数，这在数据压缩中就会导致截断效应，引入量化误差，使得压缩过程不可逆。为了解决这个问题，在已有小波的基础上构造了拥有“整数到整数变换性质”的小波。即对每次乘法后的计算结果取整，由此，相应的概貌信号和细节信号分别转换为：We can see from the figure that after the original data is decomposed into parity sequences d_o⁰ and s_o⁰ , the result of the initial lifting calculation is d_o¹ , which is overwritten and stored on the original address of d_o⁰ , and d_o¹ and s_o¹ (s_o¹ =s_o⁰ ) The result of the secondary lifting calculation is s_l¹ , which is overwritten and stored in the original address of s_o⁰ , and the two are performed alternately without conflicting with each other. This is the so-called original address operation. This method does not need to open a new space, and the original data is gradually replaced by wavelet coefficients. Due to the factors 1/2 and 1/4 in the above algorithm, the calculation result is likely to have decimals, which will lead to a truncation effect in data compression, introduce quantization errors, and make the compression process irreversible. In order to solve this problem, a wavelet with "integer-to-integer transformation properties" is constructed on the basis of existing wavelets. That is, the calculation result after each multiplication is rounded, so that the corresponding overview signal and detail signal are respectively converted into:

概貌：s(j，r)＝s(j，r)-integral{[d(j，r)+d(j，r-1)]/4}Overview: s(j, r)=s(j, r)-integral{[d(j, r)+d(j, r-1)]/4}

细节：d(j，r)＝d(j，r)-integral{[s(j，r)+s(j，r+1)+1]/2}Details: d(j,r)=d(j,r)-integral{[s(j,r)+s(j,r+1)+1]/2}

这种在提升过程中实现数“整数到整数变换”是完全可行的：由于在提升过程中，总有一个分量保持不变，因此只要对此提升过程的最终结果取整即可保证每一步结果都是整数，而且此过程完全可逆---一个整数集合通过整数提升小波变换得到的结果仍然是整数集合。反变换时，只需要逐步从结果中减去integral{[d(j，r)+d(j，r-1)]/4}和integral{[s(j，r)+s(j，r+1)+1]/2}即可，整个过程不会出现小数。This kind of "integer-to-integer conversion" in the promotion process is completely feasible: since there is always a component that remains unchanged during the promotion process, as long as the final result of the promotion process is rounded, the result of each step can be guaranteed They are all integers, and this process is completely reversible---a set of integers is still a set of integers obtained by integer lifting wavelet transform. When inverting, you only need to subtract integral{[d(j,r)+d(j,r-1)]/4} and integral{[s(j,r)+s(j,r) from the result step by step +1)+1]/2} is enough, and there will be no decimals in the whole process.

当需要进行下一尺度的小波包变换时，只需要将上一尺度的所有滤波输出(包括概貌信号和细节信号)再次进行奇偶序列分裂，而后作为图4中的输入序列，即可获得所需尺度的小波包变换结果。When it is necessary to perform wavelet packet transformation at the next scale, it is only necessary to split all the filtered outputs of the previous scale (including the overview signal and the detail signal) into parity sequences again, and then use them as the input sequence in Figure 4 to obtain the required Scaled wavelet packet transform results.

3.算法与流程3. Algorithm and process

在给出本发明的算法流程之前，首先对心电信号零树编码过程中的四类小波包系数给出定义。根据小波包系数与阈值T的关系，可以分为下面4类系数：Before giving the algorithm flow of the present invention, the four types of wavelet packet coefficients in the zero-tree coding process of ECG signals are firstly defined. According to the relationship between the wavelet packet coefficient and the threshold T, it can be divided into the following four types of coefficients:

(1)POS，正重要系数(大于阈值T的正系数)；(1) POS, positive important coefficient (a positive coefficient greater than the threshold T);

(2)NEG，负重要系数(绝对值大于阈值T的负系数)；(2) NEG, negative importance coefficient (negative coefficient whose absolute value is greater than the threshold T);

(3)ZTR，零树根(其后代均为次要系数的次要系数)；(3) ZTR, zero tree root (the secondary coefficient whose descendants are all secondary coefficients);

(4)IZ，孤独零(其后代中有重要系数的次要系数)。(4) IZ, lone zero (minor coefficient with significant coefficient in its offspring).

系数分类通过主扫描进行。对一个系数，将它和阈值相比较，按照上面的方法进行分类，假如每一次扫描都不考虑前面已经进行的比较而单独进行，算法将执行很多重复操作。为了减少运算量，对每次扫描的结果都应该进行标记：如果是重要系数就按照符号标记为POS或NEG，并将绝对值压入堆栈供辅助扫描用，同时还要将相应系数置零；如果是孤独零则标记IZ；如果是零树则标记为ZTR，其子孙都不再被扫描。Coefficient sorting is performed through the main scan. For a coefficient, it is compared with the threshold value and classified according to the above method. If each scan is performed independently without considering the previous comparisons, the algorithm will perform many repeated operations. In order to reduce the amount of calculation, the result of each scan should be marked: if it is an important coefficient, it will be marked as POS or NEG according to the sign, and the absolute value will be pushed into the stack for auxiliary scanning, and the corresponding coefficient will be set to zero at the same time; If it is a lone zero, it is marked IZ; if it is a zero tree, it is marked as ZTR, and its descendants are no longer scanned.

编码的过程不但包括对系数进行分类的主扫描，还要对重要系数逐次量化，针对入栈的每个重要系数进行区间标记，逐次量化的过程被称为辅助扫描。所谓逐次量化是逐次使用阈值T(0)，T(1)，T(2)......T(n)，来决定重要系数是属于下半区[T，3T/2]还是上半区[3T/2，2T]，如果在上半区就往辅表写入“1”，否则就写入“0”。其中，阈值序列的选取是按照下面的公式进行：The encoding process not only includes the main scan to classify the coefficients, but also quantizes the important coefficients successively, and marks intervals for each important coefficient that is loaded into the stack. The process of successive quantization is called auxiliary scan. The so-called successive quantization is to use the thresholds T(0), T(1), T(2)...T(n) successively to determine whether the important coefficients belong to the lower half [T, 3T/2] or the upper half Half area [3T/2, 2T], if it is in the upper half area, write "1" to the auxiliary table, otherwise write "0". Among them, the selection of the threshold sequence is carried out according to the following formula:

初始阈值是T(0)＝2B，其中B＝integral(log2(max|X|))，X为存放小波包系数的数组，max|X|为求数组中元素绝对值的最大值；integral为取整操作。其余由递推公式T(i+1)＝T(i)/2获得。随着逐次量化次数N的增加，编码后输出的比特数也将随之增加，小波包系数的重建值也越接近原始值，恢复心电信号的质量也就越高。在解码时，可以根据需要随时截断码流，用尽可能少的比特数来恢复心电信号。The initial threshold is T(0)=2B, where B=integral(log2(max|X|)), X is an array storing wavelet packet coefficients, max|X| is the maximum value of the absolute value of elements in the array; integral is rounding operation. The rest are obtained by the recursive formula T(i+1)=T(i)/2. With the increase of successive quantization times N, the number of encoded output bits will increase accordingly, and the closer the reconstructed value of the wavelet packet coefficient is to the original value, the higher the quality of the restored ECG signal will be. When decoding, the code stream can be truncated at any time according to the need, and the ECG signal can be recovered with as few bits as possible.

下面给出本发明的算法流程，具体如下，Provide the algorithm flow of the present invention below, specifically as follows,

(一)基于提升小波包嵌入式零树编码压缩算法流程：(1) Process flow of embedded zerotree coding compression algorithm based on lifting wavelet packet:

(1)心电信号预处理：滤除基线漂移和工频干扰；(1) ECG signal preprocessing: filter baseline drift and power frequency interference;

(2)对预处理得到的心电信号进行奇偶序列分裂，而后通过提升算法获取一阶细节信号节点和一阶概貌信号节点；(2) Split the odd-even sequence of the ECG signal obtained by preprocessing, and then obtain the first-order detail signal node and the first-order overview signal node through the lifting algorithm;

(3)根据代价函数判断一阶细节和一阶概貌父节点是否需要分解为子节点，如果需要，则将其进行奇偶序列分裂，而后通过提升算法获取相应的二阶子节点。(3) According to the cost function, it is judged whether the first-order detail and first-order overview parent nodes need to be decomposed into child nodes, and if so, split them into parity sequences, and then obtain the corresponding second-order child nodes through the lifting algorithm.

(4)根据代价函数判断二阶子节点中是否有需要继续分解为相应的三阶子节点，采用提升算法将这些二阶子节点进行分解。以此类推，直到获得最低信息熵的最优小波包空间结构。(4) According to the cost function, it is judged whether the second-order child nodes need to be further decomposed into corresponding third-order child nodes, and the lifting algorithm is used to decompose these second-order child nodes. By analogy, until the optimal wavelet packet space structure with the lowest information entropy is obtained.

(5)初始化阈值T，建立主表、辅表存储空间，将上面获得的心电信号小波包分解结果存入主表，开启辅助扫描堆栈和编码结果存储空间。(5) Initialize the threshold T, establish the storage space of the main table and the auxiliary table, store the decomposition result of the wavelet packet of the ECG signal obtained above into the main table, and open the auxiliary scanning stack and the storage space of the encoding result.

(6)对主表进行扫描，把表上的每个节点都依据阈值T分为正重要系数、负重要系数、零树根、孤立零，将扫描结果存入主表中。(6) Scan the main table, divide each node on the table into positive important coefficient, negative important coefficient, zero tree root, and isolated zero according to the threshold T, and store the scanning results in the main table.

(7)将主表翻译成二进制码流存进编码结果存储文件中。将主表中标记为正重要系数和负重要系数的节点移至辅助扫描堆栈。(7) Translate the main table into a binary code stream and store it in the encoding result storage file. Move the nodes marked positive and negative significance coefficients in the main table to the auxiliary scan stack.

(8)对辅助扫描堆栈进行辅助扫描，根据阈值和节点大小关系来进行“0”、“1”编码，同时将数据流存入编码结果存储文件中。(8) Auxiliary scanning is performed on the auxiliary scanning stack, and "0" and "1" are encoded according to the relationship between the threshold and the node size, and the data stream is stored in the encoding result storage file at the same time.

(9)改变阈值，重复主、辅扫描(即返回步骤6)，直至T＝0。(9) Change the threshold, repeat the main and auxiliary scans (that is, return to step 6), until T=0.

(10)建立无线传输数据包，在头标记里记录最优小波包树结构以及数据量大小和初始阈值信息，通过无线网络发送数据包。(10) Establish a wireless transmission data packet, record the optimal wavelet packet tree structure, data size and initial threshold information in the header tag, and send the data packet through the wireless network.

(二)基于提升小波包嵌入式零树编码解压缩算法流程：(2) Decompression algorithm flow based on lifting wavelet packet embedded zerotree coding:

(1)接收经过无线网络传输的数据包；(1) Receive data packets transmitted through the wireless network;

(2)读取头标记，获取最优小波包树结构，获取数据量大小、初始阈值等信息。(2) Read the head mark, obtain the optimal wavelet packet tree structure, and obtain information such as data size and initial threshold.

(3)读取主表数据流，对重构数据位置进行相应标记，重构数据，如果为正、负重要系数，则初始重构值为正或负的3T/2，其余的位置均为零。(3) Read the data stream of the main table, mark the location of the reconstructed data accordingly, and reconstruct the data. If the important coefficient is positive or negative, the initial reconstruction value is positive or negative 3T/2, and the rest of the positions are zero.

(4)读取辅表数据流，如果为“0”则重构值绝对值在原系数绝对值的基础上减去T/4，否则在原来值的基础上加上T/4，逐步精确重构值。(4) Read the auxiliary table data stream, if it is "0", the absolute value of the reconstructed value will be subtracted T/4 from the absolute value of the original coefficient, otherwise, T/4 will be added to the original value, and the reconstruction will be gradually and accurately structure value.

(5)更新阈值，重复扫描码流。直到完成解码。(5) Update the threshold, and scan the code stream repeatedly. until decoding is complete.

远程心电监护终端包括DSP数据采集处理模块、主控制器模块和MC35无线发送模块三大模块。其中DSP模块处于算法设计的核心，它一方面从采集模块获取数据，另一方面又给上位机提供数据压缩包。本发明将算法进行DSP硬件平台下的移植，而后利用CCS辅助开发软件提供的函数来估计算法的时间和空间开销。The remote ECG monitoring terminal includes three modules: DSP data acquisition and processing module, main controller module and MC35 wireless transmission module. Among them, the DSP module is at the core of the algorithm design. On the one hand, it obtains data from the acquisition module, and on the other hand, it provides data compression packages to the host computer. The invention transplants the algorithm under the DSP hardware platform, and then uses the function provided by the CCS auxiliary development software to estimate the time and space expenses of the algorithm.

实验数据取自MIT心率失常数据库，由PC机通过JTAG口下载到系统中，共有十组数据，每次处理数据段为12000字节。DSP外频为20MHz，启用内部PLL＝5，因此指令周期为10ns。利用TI提供的开发工具CCS，使用BIOS系统内部的监控模块来探测程序，获取运行时间。因为BIOS系统采用空闲周期对程序运行进行监控，因此不会影响程序的正常运行。The experimental data is taken from the MIT arrhythmia database and downloaded to the system by the PC through the JTAG port. There are ten sets of data in total, and each processing data segment is 12000 bytes. DSP external frequency is 20MHz, enable internal PLL = 5, so the instruction cycle is 10ns. Using the development tool CCS provided by TI, use the monitoring module inside the BIOS system to detect the program and obtain the running time. Because the BIOS system uses the idle cycle to monitor the running of the program, it will not affect the normal running of the program.

为了给出本发明的压缩效果，我们对每一组数据都采用三种算法进行计算：传统小波嵌入式零树编码算法，传统小波包嵌入式零树编码算法以及本发明的提升小波包嵌入式零树编码算法，计算结果如图5所示。In order to give the compression effect of the present invention, we all adopt three kinds of algorithms to calculate for each group of data: traditional wavelet embedded zero tree coding algorithm, traditional wavelet packet embedded zero tree coding algorithm and the present invention's lifting wavelet packet embedded Zero tree coding algorithm, the calculation result is shown in Figure 5.

从图5可以看出，通过将零树编码算法引入到传统小波包空间，可以获得更好的压缩效果(传统小波包零树编码获得的平均压缩比为13.9，相对于传统小波零树编码的9.8，有了很大的提高)，但是采用传统小波包零树编码方法，所需要的压缩时间却增加了(平均压缩时间为8.7秒，而采用小波零树编码算法只需要6.1秒)。It can be seen from Figure 5 that by introducing the zerotree coding algorithm into the traditional wavelet packet space, a better compression effect can be obtained (the average compression ratio obtained by the traditional wavelet packet zerotree coding is 13.9, compared with the traditional wavelet zerotree coding 9.8, which has been greatly improved), but using the traditional wavelet packet zero-tree coding method, the required compression time has increased (the average compression time is 8.7 seconds, while the wavelet zero-tree coding algorithm only needs 6.1 seconds).

通过采用本发明提供的基于提升小波包空间的嵌入式零树编码算法，心电数据的平均压缩比达到了16.3，而相应所需要的平均压缩时间减少到5.4秒。由此可见，本发明算法能够实现心电数据的实时高效压缩。By adopting the embedded zero-tree encoding algorithm based on the lifting wavelet packet space provided by the present invention, the average compression ratio of ECG data reaches 16.3, and the corresponding average compression time is reduced to 5.4 seconds. It can be seen that the algorithm of the present invention can realize real-time and efficient compression of ECG data.

Claims (2)

Translated fromChinese

1.一种无线心电监护仪的心电压缩方法，包括下列步骤：1. an electrocardiographic compression method of a wireless ECG monitor, comprising the following steps:(1)对采集到的心电信号进行预处理；(1) Preprocessing the collected ECG signals;(2)对预处理得到的心电信号进行奇偶序列分裂，而后通过提升算法获取一阶细节信号节点和一阶概貌信号节点；(2) Split the odd-even sequence of the ECG signal obtained by preprocessing, and then obtain the first-order detail signal node and the first-order overview signal node through the lifting algorithm;(3)根据代价函数判断一阶细节和一阶概貌父节点是否需要分解为子节点，如果需要，则将其进行奇偶序列分裂，而后通过提升算法获取相应的二阶子节点；(3) According to the cost function, it is judged whether the first-order detail and first-order overview parent nodes need to be decomposed into child nodes, and if necessary, split them into parity sequences, and then obtain the corresponding second-order child nodes through the promotion algorithm;(4)根据代价函数判断二阶子节点中是否有需要继续分解为相应的三阶子节点，采用提升算法将这些二阶子节点进行分解，以此类推，直到获得最低信息熵的最优小波包空间结构；(4) According to the cost function, it is judged whether the second-order child nodes need to be further decomposed into corresponding third-order child nodes, and these second-order child nodes are decomposed by the lifting algorithm, and so on, until the optimal wavelet with the lowest information entropy is obtained package space structure;(5)遍历小波包所有系数，求出系数绝对值的最大值，保留该数值二进制位的最高位，将其余低位置零，而后将所得结果作为初始阈值；建立主表、辅表存储空间，将上面获得的心电信号小波包分解结果存入主表，开启辅助扫描堆栈和编码结果存储空间；将初始阈值赋值给阈值(T)；(5) Traversing all the coefficients of the wavelet packet, finding the maximum value of the absolute value of the coefficients, retaining the highest bit of the binary digit of the value, and setting the remaining low positions to zero, and then using the obtained result as the initial threshold value; establishing the storage space of the main table and the auxiliary table, Store the decomposition result of the wavelet packet of the ECG signal obtained above into the main table, open the auxiliary scan stack and the storage space for the encoding result; assign the initial threshold to the threshold (T);(6)对主表进行扫描，把表上的每个节点都依据阈值(T)分为正重要系数、负重要系数、零树根、孤立零，将扫描结果存入主表中；(6) Scan the main table, divide each node on the table into positive importance coefficient, negative importance coefficient, zero tree root, and isolated zero according to the threshold (T), and store the scanning result in the main table;(7)将主表翻译成二进制码流存进编码结果存储空间中，将主表中标记为正重要系数和负重要系数的节点移至辅助扫描堆栈；(7) translate the main table into a binary code stream and store it in the encoding result storage space, and move the nodes marked as positive and negative important coefficients in the main table to the auxiliary scanning stack;(8)对辅助扫描堆栈进行辅助扫描，根据阈值(T)和节点大小关系来进行“0”、“1”编码，同时将数据流存入编码结果存储空间中；(8) Auxiliary scanning is performed on the auxiliary scanning stack, and "0" and "1" are encoded according to the relationship between the threshold (T) and the node size, and the data stream is stored in the encoding result storage space at the same time;(9)更新阈值(T)为当前阈值的1/2，返回步骤6，重复步骤(6)至(9)的主、辅扫描过程，直至阈值(T)为0；(9) Update the threshold (T) to be 1/2 of the current threshold, return to step 6, and repeat the main and auxiliary scanning processes of steps (6) to (9) until the threshold (T) is 0;(10)建立无线传输数据包，在头标记里记录最优小波包树结构以及数据量大小和初始阈值信息，通过无线网络发送数据包。(10) Establish a wireless transmission data packet, record the optimal wavelet packet tree structure, data size and initial threshold information in the header tag, and send the data packet through the wireless network.2.一种无线心电监护仪的解码方法，用于解压缩采用权利要求1所述的压缩方法得到的编码，其特征在于包括下列步骤：2. a decoding method of a wireless ECG monitor, for decompressing the encoding that adopts the compression method described in claim 1 to obtain, it is characterized in that comprising the following steps:(1)接收经过无线网络传输的数据包；(1) Receive data packets transmitted through the wireless network;(2)读取头标记，获取最优小波包树结构，获取数据量大小、初始阈值，将初始阈值赋值给阈值(T)；(2) Read the head mark, obtain the optimal wavelet packet tree structure, obtain the size of the data volume and the initial threshold, and assign the initial threshold to the threshold (T);(3)读取主表数据流，对重构数据位置进行相应标记，重构数据，如果为正、负重要系数，则初始重构值为阈值(T)的正或负3/2倍，其余的位置均为零；(3) Read the data stream of the main table, mark the location of the reconstructed data accordingly, and reconstruct the data. If it is a positive or negative important coefficient, the initial reconstruction value is positive or negative 3/2 times the threshold (T), The rest of the positions are zero;(4)读取辅表数据流，如果为“0”则重构值绝对值在原系数绝对值的基础上减去阈值(T)的1/4，否则在原来值的基础上加上阈值(T)的1/4，逐步精确重构值；(4) Read the auxiliary table data stream, if it is "0", then the absolute value of the reconstructed value is based on the absolute value of the original coefficient minus 1/4 of the threshold (T), otherwise the threshold is added to the original value ( 1/4 of T), gradually and accurately reconstructing the value;(5)更新阈值(T)为当前阈值的1/2，返回步骤(3)至(5)的扫描码流过程，直到完成解码。(5) Update the threshold (T) to 1/2 of the current threshold, and return to the process of scanning the code stream from steps (3) to (5) until the decoding is completed.

Images