ABSTRACT

This paper presents a hybrid technique for the compression of ECG signals based on DWT and exploiting the correlation between signal samples. It incorporates Discrete Wavelet Transform (DWT), Differential Pulse Code Modulation (DPCM), and run-length coding techniques for the compression of different parts of the signal; where lossless compression is adopted in clinically relevant parts and lossy compression is used in those parts that are not clinically relevant. The proposed compression algorithm begins by segmenting the ECG signal into its main components (P-waves, QRS-complexes, T-waves, U-waves and the isoelectric waves). The resulting waves are grouped into Region of Interest (RoI) and Non Region of Interest (NonRoI) parts. Consequently, lossless and lossy compression schemes are applied to the RoI and NonRoI parts respectively. Ideally we would like to compress the signal losslessly, but in many applications this is not an option. Thus, given a fixed bit budget, it makes sense to spend more bits to represent those parts of the signal that belong to a specific RoI and, thus, reconstruct them with higher fidelity, while allowing other parts to suffer larger distortion. For this purpose, the correlation between the successive samples of the RoI part is utilized by adopting DPCM approach. However the NonRoI part is compressed using DWT, thresholding and coding techniques. The wavelet transformation is used for concentrating the signal energy into a small number of transform coefficients. Compression is then achieved by selecting a subset of the most relevant coefficients which afterwards are efficiently coded. Illustrative examples are given to demonstrate thresholding based on energy packing efficiency strategy, coding of DWT coefficients and data packetizing. The performance of the proposed algorithm is tested in terms of the compression ratio and the PRD distortion metrics for the compression of 10 seconds of data extracted from records 100 and 117 of MIT-BIH database. The obtained results revealed that the proposed technique possesses higher compression ratios and lower PRD compared to the other wavelet transformation techniques. The principal advantages of the proposed approach are: 1) the deployment of different compression schemes to compress different ECG parts to reduce the correlation between consecutive signal samples; and 2) getting high compression ratios with acceptable reconstruction signal quality compared to the recently published results.

1. Introduction

In technical literatures, numerous ECG compression algorithms have been developed in the last thirty years. They may be defined either as reversible methods (offering low compression ratios but guaranteeing an exact or near-lossless signal reconstruction), irreversible methods

(designed for higher compression ratios at the cost of a quality loss that must be controlled and characterized), or scalable methods (fully adapted to data transmission purposes and enabling lossy reconstruction). Choosing one method mainly depends on the use of the ECG signal. In the case of diagnosis, a reversible compression would be most suitable. However, if compressed data has to be stored on low-capacity data supports, an irreversible compression would be necessary. The scalable techniques clearly suit data transmission. ECG compression techniques can be categorized into: direct time-domain techniques; transformed frequency-domain techniques and parameters optimization techniques.

1) Direct Signal Compression Techniques: Direct methods involve the compression performed directly on the ECG signal. Many of the time domain techniques for ECG signal compression are based on the idea of extracting a subset of significant signal samples to represent the original signal. The key to a successful algorithm is the development of a good rule for determining the most significant samples. Decoding is based on interpolating this subset of samples. The traditional ECG time domain compression algorithms all have in common that they are based on heuristics in the sample selection process. This generally makes them fast, but they all suffer from sub-optimality [1].

2) Transformed ECG Compression Methods: Transform domain methods, operate by transforming the ECG signal into another domain. These methods mainly utilize the spectral and energy distributions of the signal, and properly encoding the transformed output. Signal reconstruction is achieved by an inverse transformation process. This category includes traditional transform coding techniques applied to ECG signals such as the KarhunenLoève transform [2], Fourier transform [3], Cosine transform [4], subband-techniques [5], vector quantization (VQ) [6], and more recently the wavelet transform (WT) [7]. The wavelet decomposition splits the signal into approximation and detail coefficients, using finite impulse response digital filters. Wavelet-based ECG compression methods have been proved to perform well. The ability of DWT to separate out pertinent signal components has led to a number of wavelet-based techniques which supersede those based on traditional Fourier methods.

3) Optimization Methods for ECG Compression: More recently, many interesting optimization based ECG compression methods, the third category, have been developed. The goal of most of these methods is to minimize the reconstruction error given a bound on the number of samples to be extracted or the quality of the reconstructed signal to be achieved. In [8], the goal is to minimize the reconstruction error given a bound on the number of samples to be extracted. This leads to the best possible representation in terms of the number of extracted signal samples, but not necessarily in terms of bits used to encode such samples. In [9], the bit rate has been taken into consideration in the optimization process.

The key issue is to choose the most suitable method for the ECG signals application. What is intended through this paper is to obtain the highest data reduction by preserving the clinical characteristics of the signal.

2. Algorithm Description

The QRS complex of an ECG cycle occupies a relatively low percentage of the whole cycle, but it is the most important portion from a diagnostic point of view for many diseases. If this portion suffers from high error and other ECG cycle portions do not have errors, artificially wrong diagnostic decisions may happen. Hence, a given distortion in one portion does not inevitably have the same influence as the same distortion in another portion. For these reasons the proposed compression algorithm focuses on the provision of different compression ratios for different portions of the heart cycle, where the RoI is selected according to context information (disease/cardiac event to detect status of the patient).

Ideally we would like to compress the signal losslessly, but in many applications this is not an option. Thus, for a given fixed bit budget, it makes sense to spend more bits to represent those parts of the signal that belong to a specific clinically relevant parts, while allowing other parts to suffer larger distortion. Consequently, the performance assessment of the proposed methodology should take this into account. In general, the main goal for any compression procedure consists in reducing as much as possible the bit-rate of the signal by keeping an acceptable quality or, equivalently, by improving as much as possible the quality for a fixed assigned bit-rate. Thus, the two most important parameters are the compression ratio and the quality of the signal. The framework of the compression process is summarized in the following.

2.1. Patient Side

1) Capture the ECG signal from the patient or prepare an uncompressed signal from a database.

2) If the signal is captured from a patient, clean it from artifacts and remove the signal mean and normalize it. In case of picking the signal from a database, remove its mean and normalize the resulting mean-removed signal. In this paper, all signals considered are extracted from MIT-BIH database.

3) Segment the signal into RoI part (QRS-complex and possibly PT- and U-waves) and the NonRoI part (the remaining parts representing the difference between the original ECG signal and the RoI part).

4) Compress the RoI part using DPCM lossless compression method and applying proper quantization.

5) Encode the resulting quantized residuals into binary stream by run-length coding algorithm.

6) Compress the NonRoI part using DWT lossy compression technique and applying proper thresholding and quantization.

7) Encode the resulting quantized wavelet coefficients into binary stream by run-length coding algorithm.

8) Packetize the data and prepare the data header.

2.2. Transmission Side

1) Guarantee network connection (Intranet or Internet) and/or wireless transmission facilities.

2) Transmit the data header, the binary stream of the RoI part and that of the NonRoI part consecutively.

2.3. Reception Side

1) Depacketize the received binary stream into the header, binary stream of the RoI and that of the NonRoI parts respectively.

2) Convert the binary streams of the header into the basic information important for ECG signal reconstruction such as length of RoI stream, length of NonRoI stream, start and end of each wave in RoI and NonRoI parts.

3) Convert the binary streams of both RoI and NonRoI parts into their equivalent decimal numbers.

4) Apply inverse DPCM for RoI part and apply inverse wavelet transform for NonRoI part.

5) Decompose the resulting time-domain RoI and NonRoI parts into QRS-waves, T-waves, P-waves, Uwaves and isoelectric-waves.

6) Use the obtained data in the above steps to reconstruct the ECG signal.

7) Calculate the compression ratio and the error measures for evaluation and comparison.

8) Output the reconstructed ECG signal for medical investigation.

3. Features Extraction and Locating ECG Signal Critical Points

The significant features of the ECG signal, such as the R point, RR interval, and amplitude of R point, average RR interval, QRS duration and existence of QRS should be extracted for the next compression stage. The significant features are shown in Figure 1; where each heartbeat signal starts by the P wave and ends at the next P wave of the following heartbeat. Moreover, the heartbeat can be divided into a crucial part and a plain part [10].

The QRS complex wave is the most important part of the cardiology system to determine arrhythmia. The P and T waves also have high level of information and the remaining plane parts contain less information. Therefore, in this work, the ECG signal is segmented into parts and the number of bits is assigned differently according to the importance of each part. For example, more bits are assigned to the RoI part, and fewer bits are assigned to the NonRoI part. The critical points of the ECG signal are very important in defining its RoI and NonRoI parts. These critical points are namely; the P, Q, R, S, T and U

points. In the following a robust algorithm for the detection of the locations of these points using the properties of the real time analysis of the ECG signal is described.

The R-wave detection is the most important process in the segmentation algorithm because all coming processes are based on the locations of the R-peaks. This has been carried out by adaptive thresholding the ECG signal. The threshold levels used in this work are not constant for all ECG signal beats. This overcomes the error in detecting the R-wave as a result of the unexpected changes in the ECG signal from beat to beat. Each beat is defined by the R-R interval that has a length from about 0.14 sec up to 1.2 sec (corresponds to 144 samples to 432 samples). To carry out the R-peak detection process, a window of length greater than 432 samples should be used. The width of the widow must be selected carefully to avoid error detection of the R-wave of the ECG signal. In this study a window of width 500 samples is selected. Then the maximum value of the ECG signal within this window is calculated.

The window is slide to the right by one sample and the maximum value within the new window is calculated. This process is repeated until the left edge of the window reaches the last sample of the signal. This process yields to the upper threshold levels of each beats. The lower threshold levels are calculated as a factor of the upper threshold levels. It has been found that a factor of half is suitable for detecting the R-peaks. The next step is the thresholding of the ECG signal with the resulted threshold levels and finding the maximum points of the resulting signal that represents the R peaks.

Detecting the Q and S waves is basically based on the detection of the R-peaks locations. The Qand S-peaks locations are obtained by searching for the minimum points surrounding the R peaks. The duration of the QRS complex is 0.04 - 0.11 sec (15 - 40 samples). Similar search process to that described before for finding the R-peaks is made in the 40 samples before and in the 40 samples after the location of the R-peak has been carried out for detecting the Qand S-peaks.

The T-, Uand P-peaks are located between the Qand next S-peaks. Firstly, we define the SQ segment as the region from the location of the current S-peak up to the location of the following Q-peak. The of maximum and minimum points in the SQ segment are determined by adopting the same method used to find the R-peaks where the sliding window width used is selected to be equal to one-tenth the width of the SQ segment. The points of the maximum of the windows is picked and considered as the T-, Uand P-peaks after avoiding multipoint problems. According to the morphology of the ECG signal and after the consultations with cardiologists, the detected peaks are considered as the peaks of the T-, Uand P-waves according to the following rules.

• If there are no peaks detected, then no T-, Uor P-peak exists.

• If there is only one peak detected, then this peak will be the T-peak and there is no U-peak or P-peak.

• If there are two peaks detected, the first peak will be the T-peak and the next peak will be the P-peak and there is no U-peak.

• If there are three peaks or more detected the first peak will be the T-peak and the next peak will be the Upeak and the last peak will be the P-peak.

Figure 2 illustrates the ECG signal with P, Q, R, S, T and U points indicated.

4. Segmentation of ECG Signal into Waves

The ECG segment is defined as the period between the end of a wave to the start of the next wave. After finding the P-, Q-, R-, S-, Tand U-peaks locations, the segments PQ, ST, TU, and UP are defined as the portions of the ECG signal between the two adjacent peak locations. In each of these segments, an isoelectric wave exists. If the

start and end locations of each isoelectric wave is determined, the starts and ends locations of all other waves can be determined. The idea of finding the start and end locations of isoelectric waves is centered in finding the longest period with lowest standard deviation (STD) in each segment. This is carried out as follows:

• Locate the interval V between the two adjacent points defining the segment, (i.e. P and Q, S and T, T and P).

• Calculate the STD of the regions whose start is the first sample of the interval V and whose ends are points after the first point; e.g. Std(1) = STD(V(1:2), std(2) = STD(V(1:3)), std(3) = STD(V(1:4)), ... std(n) = STD(V(1:n + 1)).

• Repeat the last step for the next sample of the interval V and so on until the last sample of the interval V.

The decomposition of the ECG signal into its waves is illustrated in the flowchart shown in Figure 3. As a result, the start and end locations of the ECG waves are detected.

Pwave_st=Waves{1}; Pwave_ed=Waves{2};

QRSwave_st=Waves{3}; QRSwave_ed=Waves{4};

Twave_st = Waves{5}; Twave_ed= Waves{6};

Uwave_st= Waves{7}; Uwave_ed  = Waves{8};

isoelectric_st = SEG{1}; and isoelectric_ed = SEG{2};

After finding the region that achieves lowest STD and longest length; the start and end of each isoelectric wave is determined. Consequently, the starts and ends of all other waves are determined. To illustrate the importance of the ECG signal’s components, the energy and the number of samples (wave length) of each component are calculated. Table 1 includes the calculated energies and wave lengths of different ECG components for 1460 samples from record 103. From this table it can be observed that the longest component is the isoelectric wave in which about 45% of the ECG signal energy and number of samples are concentrated. Fortunately, these waves have no clinical importance. Thus, it will be considered as the main component of the Non-RoI part. In contrary to that the energy of the QRS-complexes is about 36% of the signal energy with smallest number of samples (about 8%). This part of the signal is very important from clinical point of view. So, it will be considered as the main component of the RoI part. The Tand P-waves contributed by 5.8% and 8.1% of the energy respectively; however the length of the T-waves is 1.7 times that of the P-waves. Thus, P-wave is a candidate for RoI part and T-wave is a candidate for NonRoI part. Considering either of them in RoI or NonRoI depends on the patient’s case and the patient’s heart disease [10]. Table 2 includes the 74 start and end indices of all the ECG signal waves. Investigation of this table reveals that, among these 36 indices are for isoelectric-waves and there exists an isoelectric-wave between each two other waves. Since

the start of each wave is less than the end of the preceding wave by one, the start of the next wave can be directly determined. The only two exceptions are the start index of the first wave that is 1 and the end index of the last wave that is the signal length. Using these facts, the 74 entries of Table 2 can be obtained from only 36 entries.

From the above discussion, it can be deduced that only the 36 entries need to be included in HeaderW and no need to transmit the start and end of isoelectric waves. It should be noticed that the starts and ends of isoelectric waves are generated in the receiver side using the following Matlab code.

n = length (HeaderW); SortedHW = sort (HeaderW); k = 0;

for i = 2 : 2 : n − 1 k = k + 1; startiso (k) = SortedHW (i) + 1; endiso(k) = SortedHW (i + 1) − 1; end Running the above code results the following starts and ends of the isoelectric waves.

startiso = [90 154 226 286 388 456 537 592 690 758 838 893 993 1070 1143 1196 1300 1370]

endiso = [125 191 251 330 422 500 562 634 721 802 863 935 1034 1107 1167 1239 1336 1410]

These indices will be deployed in the reconstruction of the signal in the receiver side. To finalize this section, the preparation for ECG signal segmentation into RoI and NonRoI parts is summarized in the following:

1) The ECG signal is decomposed into its waves and these waves are stored in the vectors: Twaves, Uwaves, Pwaves, and QRSwaves. These waves will be grouped into RoI and NonRoI parts.

2) The numbers of sub-waves are included in the first part of the header (Header1) that includes No_of_Twaves, No_of_Uwaves, No_of_Pwaves, and No_of_QRSwaves. Each is represented by 4-bits. Since each ECG beat has only one of these waves, the 4-bits can accommodate a signal of length 15 beats. For longer ECG signals, this number should be increased.

3) The starts and ends of all sub-waves are defined and stored in HeaderW, e.g. the first QRS sub-wave starts at EQwave₁ and ends at EQwave₁. Each value is represented by 11-bits. The 11-bits can accommodate a signal of length 2048. For longer ECG signals, this number should be increased.

4) The starts and ends of the isoelectric waves are deduced from HeaderW using the Matlab code described above.

5. Compression of ECG Signal Based on Segmentation into RoI and NonRoI Parts

5.1. Signal Segmentation into RoI and NonRoI Parts

In the previous section segmentation of ECG signal into its waves has been discussed. For the purpose of signal compression, the following three cases of constructing the RoI and NonRoI parts from these waves are:

1) QRS-waves are considered in RoI and the remaining waves are in NonRoI.

(1)

2) QRSand T-waves are considered in RoI and the remaining waves are in NonRoI.

(2)

3) QRS-, Tand P-waves are considered in RoI and the remaining waves are in NonRoI.

(3)

Since the RoI is the most important part of the signal for medical diagnostic purposes, it must be coded with a lossless compression algorithm. The NonRoI part of the ECG signal has not had a considerable effect of medical diagnostic. For this reason, this part is compressed by using lossy compression technique. For this purpose DPCM technique is used for compressing the ROI part of the signal. However, the NonRoI part of the signal is compressed using wavelet based compression technique. To send the information related to the compression stage, the number of signal samples in the RoI (Len_RoI) and the number of signal samples in the NonRoI (Len_ NonRoI) should be added to Header1 and each is represented by 11-bits. In the following subsections the algorithms developed for the compression of RoI part using DPCM and NonRoI part using DWT are presented. Although the discussion presented in the following subsections is limited to the first case described by Equation (1), all algorithms that will be discussed can be adopted by reconstructing RoI and NonRoI vectors according to Equations (2) and (3). Figure 4 illustrates the ECG signal after its decomposition into RoI and NonRoI parts, where all P waves, QRS waves, T waves, U waves, and isoelectric waves are arranged in groups.

5.2. Compression of RoI Part Using Differential Pulse Code Modulation

Amongst the different direct data compression techniques, which are based on the detection of redundancies on the original signal, pulse code modulation (PCM) provides simple and fast compression schemes. In PCM technique each sample of the waveform is encoded independently of any other sample. An encoding scheme that exploits the redundancy in the samples will result in higher compression ratio and a lower bit rate for the source output. A relatively simple solution is to encode the differences between successive signal samples rather than the samples themselves, rendering the differential pulse code modulation (DPCM) technique. The equation for calculating a DPCM sequence is

(4)

where, e(n) is the prediction error. Since differences between samples are expected to be smaller than the actual sampled amplitudes, fewer bits are required to represent the differences. A block diagram of a DPCM encoder and decoder used in this subsection is shown in Figure 5(a). A natural extension of the DPCM operation is to predict the value of the current sample based on the previous m samples using Linear Prediction (LP) technique, as shown in Figure 5(b).

(5)

where, is the estimate of the current sample at discrete time instant n and is the predic-

tor weights. The samples of the estimation error sequence are less correlated with each other compared to the original signal, as the predictor removes the unnecessary information which is predictable portion of the sample,. The coefficients of the LP model are determined by minimizing the error between the original and estimated signal in the least squares sense. The block diagram of the LP implementation is shown in Figure 5(b). In both of the above DPCM systems, is normally quantized using a predefined number of bits. If the calculated difference between the current sample and the predicted value of the current sample is too large to be represented by the number of bits chosen for quantization, then data loss occurs. For this reason DPCM is normally considered to be a nearly lossless coding scheme. Therefore, in order to keep the DPCM operation completely lossless, the output would need more predefined bits to guarantee that there will not be data loss. In [11], Jalaleddine showed that for ECG signals, a first order linear predictor (DPCM) yields better results compared to LP models of higher orders. However, for other set of signals, a second order prediction model achieved best results. Figure 6 illustrates the ROI signal before and after DPCM.

5.3. Compression of NonRoI Part Using DWT

As it is mentioned before, the NonRoI part is compressed using DWT-based compression technique. For all signals considered through the paper, signals are decomposed up to the 6 levels using Daubitches “db6” wavelet filters. Then the wavelet coefficients are thresholded, quantized and coded using run-length coding technique. The approximation and details coefficients obtained by wavelet transformation must be quantized for the purpose of compression. The quantization process on the subbands of the ECG signal gives a small number of bits (short codewords) to represent the small numbers when they mostly occur and a larger number of bits (long code-

words) to represent the less probable large numbers. For the run-length coding of the thresholded wavelet coefficients of NonRoI part, each coefficient is represented in the forum of (counts, values). Then, each non-negative value is represented by “1” concatenated with nbitsNonRoI binary representation of that value and each negative value is represented by “0” concatenated with nbitsNoRoI binary representation of that value. Here, nbitsNonRoI is determined such that the absolute value of the maximum thresholded wavelet coefficient is represented correctly. Consequently, counts are again run-length coded.

6. Data Packetization Process

From the above discussion it can be observed that it is necessary to prepare a header to be sent to the receiver before transmitting the coded signal. The header is constructed from four parts. The first part of the header (Header1) defines the number of T-, P-, QRSand T-waves. Table 3 illustrates the construction of the first part of the header including the required number of bits. The second part of the header (Header2) packetize the number of bits required for representing the length of RoI residuals (Len_of_RoI), the value of the first sample, the number of bits for RoI residual (nbitsRoI) as shown in Table 4. Before quantizing the residuals of the theRoI part, each residual element is multiplied by a scale factor of value 100. The required number of bits necessary to represent each element of the scaled depends mainly on the maximum value of.

6.1. Packtization of Transmitted Signal

Before quantizing the DWT coefficient of the NonRoI part, each coefficient is multiplied by a scale factor of value 100. The third part of the header (Header3) packetize the number of bits required for representing the NonRoI scaled DWT coefficients. In this case, the coding process using run-length algorithm is applied twice. The first, results in values and counts of the scaled DWT coefficients. The required number of bits necessary to represent each value depends mainly on the maximum absolute value the scaled DWT coefficient. The Matlab function dec2bin is adopted for determining nbitsvalue. This function is also used to define the number of bits required to represent the number of these values (nbitsvlength). The resulting counts vector may have too many successive zeros. So, another run-length coding round for counts is adopted. This results in values and counts of counts. Thus we have to define the number of bits re-

quired for representing the length and the value of values of the scaled DWT coefficients, together with the value and count of their counts. The last count value that represents the number of zeros at the end of scaled DWT coefficients vector is high; thus it will be represented by more bits. Table 5 illustrates the number of bits assigned for NonRoI coded DWT coefficient. The fourth part of the header (HeaderW) contains the start and end indices of all ECG waves except the isoelectric waves; where each is represented by 11-bits (See the formula in the bottom).

Following the four header parts, the binary stream of the coded RoI residuals and the binary stream of the coded DWT coefficients are packetized consequently. Table 6 summarizes the bit allocation, which is transmitted (stored) for every ECG signal block. The gray areas in the table denote the parameters that are not always transmitted.

6.2. Illustrative Example of Packetization Process

To illustrate the packetization process, consider the above mentioned ECG signal (1460 samples from record 103). The signal contains 5 T-waves, 5 U-waves, 5 Pwaves, and 4 QRS-waves. So, the binary stream of the first part of the header is Header1 = [0101 0101 0101 0100].

The signal also has 120 RoI residuals and a first sample of value −0.237 The absolute value of the maximum element of the RoI residual is 30, so nbitsRoI = 6-bits. Thus, the binary stream of the second part of the header is Header2 = [01111000 10100010 00111100110 11110 000011110]. For the considered signal the number of

NonRoI samples is 1340. Among them, 318 samples represent the T-waves, 165 samples representing the Uwaves, 190 samples representing the P-waves and 667 samples representing the isoelectric-waves. When wavelet transformed using “db6” up to the 6^th level, 1403 wavelet coefficients result. These wavelet coefficients are thresholded using 0.0485 threshold level, where those less than this value are set to zero. This level is calculated using the energy packing efficiency principle described in [18]. As a result of this step, only 80 coefficients from the 1403 wavelet coefficients are non-zeros

and the remaining 1323 coefficients are zeros. However these zeros are distributed between the non-zero coefficients. Using the run-length encoding, all the wavelet coefficients are grouped into 81 values with 81 counts. Thus, the 1403 wavelet coefficients are coded to 162 values and counts.

Table 7 includes the 162 run-length codes of the NonRoI wavelet coefficients. In this table the wavelet coefficient of value −231 with count zero means that there are no zeros between this coefficient and the preceding coefficient (−225). However, the wavelet coefficient of value 74 with count 5 means that there are 5 zeros between this coefficient and the preceding coefficient (−213). Investigations of Table 7 reveal that, the counts have many repeated successive zeros. Consequently, the run-length method is adopted once again for counts vector. As a result, the 81 counts are coded into 23 counts_ values and 23 counts_counts. Moreover the values of the resulting representation are much smaller than that of counts. Thus, the 1403 wavelet coefficients are coded by 81 coefficient values, 23 counts values and 23 counts counts. Table 8 includes the run-length coding of the coefficients counts; which is counts_counts and counts_ values. The last counts_values (1105) represents the

number of zeros at the end of the thresholded NonRoIcoefficients. In fact this value is the maximum value of the vector counts_values and needs 11 bits for binary representation. Excluding this value from vector counts_ values yields that the maximum value of the remaining elements is 107, so only 7 bits is enough for representing each element in counts_values. Thus, Header3 is [(10, 81) (7, 23) (5, 22) 11] which is equivalent to [1010 1010001 0111 10111 0101 10110 1011].

The fourth part of the header is devoted to the binary stream of the start and end locations of the 5 T-waves, 5 U-waves, 5 P-waves, and 4 QRS-waves. These locations are respectively at the indices [1 331 635 936 1240 89 387 689 992 1299 126 423 722 1035 1337 153 455 757 1069 1369 192 501 803 1108 1411 225 536 837 1142 1460 252 563 864 1168 285 591 892 1195]. Representing each index by 11-bits, yield HeaderW =

[00000000001 00101001011 01001111011 ··· 01101111100 10010101011].

Following the transmission of the four header parts, the binary stream of the scaled RoI residuals is transmitted. The number of these elements is 120 and each is represented by 6 bits including the sign bit. Thus the 120 residual elements are represented by a binary stream of length 720 bits. The first 10 residual elements after scaling are [0 −3.0 −2.0 −1.0 2.0 3.0 5.0 9.0 15.0 19.0] and the corresponding binary stream is [100000 000011 000010 000001 100010 100011 100101 101001 101111 110011].

Following the transmission of the RoI residuals, the binary stream of the coded NonRoI part is transmitted. Adding the 11-bits required for the last counts value (1105), a sum of 165 bits represents counts-values vector. For counts-counts vector, the maximum element is 31, so 5 bits are enough to represent each element. Consequently 110 bits represents the counts-counts vector. Thus, 275 bits are needed after run-length encoding of counts vector. The maximum absolute value of the values vector is 282. This value is represented by 9 bits plus one more bit for sign. The last element of the vector values is zero and the remaining 80 elements need 800 bits for binary representation. Summing up all together, the 1403 thresholded DWT coefficients are represented by 1082 bits.

7. Numerical Results

In this section, the performances of the proposed compression algorithm is presented and will be compared with other known compression algorithms. Records from MITBIH Arrhythmia database is used for evaluating the proposed compression algorithm. The performance of compression algorithms is tested by means of the quantitative performance measures; namely, in terms of the compression ratio and the distortion metrics. The compression ratio (CR) is defined as the ratio of the number of bits representing the original signal to the number required for representing the compressed signal. So, it can be calculated from:

(6)

where, is the number of bits representing each original ECG sample. For MIT-BIH database, is 11 bits., , and are the number of bits representing HeaderW, RoI stream and NonRoI stream respectively. It should be noted that and are the lengths of the binary streams representing Header1, Header2 and Header3. They are not included in (6), since they are fixed and send to the receiver once. To be able to compare different compression algorithms, it is imperative that an error criterion is defined such that it will measure the ability of the reconstructed signal to preserve the relevant diagnostic information. The distortion resulting from the ECG processing is frequently measured by the percent root-mean-square difference (PRD).

(7)

where, is the original signal, is the reconstructed signal and N is the length of the window over which the PRD is calculated.

7.1. Illustrative Example of Compression Algorithm

As an illustrative example, consider the compression of 2000 samples extracted from record 100 of MIT-BIH database. Thus, these samples are represented by 22000 bits. The signal is segmented into RoI and NonRoI parts. Considering the RoI part to include the QRS-waves and the NonRoI part to include the remaining waves, the length of RoI part is 180 samples and that of NonRoI part is 1820 samples as shown in Figure 7. In this case, the Rpeaks locations and the QRS starts and ends locations are required to be determined. Those are: R-peaks = [266 577 878 1182 1484 1796], QRS-starts = [252 563 864 1168 1470 1781] and QRS-ends = [285 591 892 1195 1497 1812]. Each QRS start and end value is represented by 11-bits yielding. The RoI part is decorrelated using DPCM and this yields first-sample = −0.2375 and the residual waveform shown in Figure 8(a). The NonRoI part is wavelet transformed up to the 6^th level using Daubechies (db6) wavelet and the resulting waveform coefficients (1884) are shown in Figure 8(b).

The threshold level is calculated such that 99.7% of

energy of the NonRoI part is reserved. The maximum absolute value of the residuals of the RoI part after scaling and rounding is 15. Thus, length of the RoI stream is = 900 bits. The wavelet coefficients whose absolute values are less than the resulting threshold level (0.0592) are set to zero. As a result, among the 1884 waveform coefficients, only 84 coefficients are non-zero. However, they are distributed between the waveform coefficients.

After running the first round run-length coding algorithm, 85 values and 85 counts results. Concerning the 85 values, the maximum absolute value is 185. Thus each value is represented by 9-bits including the sign bit and the binary stream of the values is of length 765 bits. After the second round of run-length coding algorithm on the 85 counts, the following 20 values and 20 runs result respectively;

Counts_values = [5 6 3 1 1 1 2 7 2 6 3 2 6 2 3 1 12 10 48 1678]

Counts_counts = [0 0 0 1 0 0 0 0 0 0 3 1 8 0 0 1 3 1 8 39]

The maximum value of the first 19 counts-values is 48 and each can be represented by 6-bits yielding 114-bits for representing the counts-values stream. The last counts-values is 1678 which is represented by 11-bits. Similarly, the maximum value of the first counts-counts is 8 and each can be represented by 4-bits yielding 76- bits for representing the counts-values stream. The last counts-counts is 39 which is represented by 6-bits. Summing all together, and

. Thus, from Equation (6), the compression ratio is.

Reconstructing the ECG signal from the header and the binary streams representing the RoI and NonRoI parts follows reverse processes. This is namely, decoding of header, RoI and NonRoI streams. Then, the RoI and NonRoI parts are reconstructed using inverse DPCM and inverse DWT respectively. The QRS-starts, QRS-ends and the reconstructed RoI and NonRoI parts are used to reconstruct the ECG signal. Figure 9 illustrates the original and reconstructed RoI part of the signal. This figure shows that the original and the reconstructed QRS-waves are almost identical. Figure 10 illustrates the original and reconstructed T-, P-, Uand isoelectric waves together with the reconstruction error of the NonRoI part. Figure 11 illustrates original and the reconstructed ECG waveforms results from inserting the RoI and NonRoI parts in their prober positions.

7.2 Effect of Selecting the Wavelet Family

The Wavelet Toolbox™ software includes a large number of wavelets that you can be used for ECG signal compression. Examples include: orthogonal wavelets (Daubechies’ and Symlets wavelets) and biorthogonal wavelets. The choice of wavelet is dictated by the signal characteristics and the nature of the application. The wavelet families adopted in this paper are listed in Table 9. Table 10 depicts the wavelets used for testing the effect of varying the wavelet filters on the compression performances. Figures 12 and 13 illustrate the dependence of the CR and PRD on the adopted wavelet filters. These

figures show that as the filters order increase, the CR increases. However, this increases the compression errors. They also show that Daubechies’ and Symlets families outperforms biorthogonal family; where higher CRs and lower reconstruction errors result.

7.3. Comparison with Other Methods

In technical literatures, many interesting ECG signal compression algorithms have been introduced. In this section the result of several experiments of the proposed method are compared with other ECG compression algorithms already realized [12-21]. In addition, the ECG signals used should be sampled with the same sampling rate and each sample is quantized by the same number of bits. The proposed algorithm was tested and evaluated using actual data from MIT-BIH arrhythmia database; where the sampling rate is 360 Hz, and the resolution is 11-bit. The performance of the algorithm is measured and compared with other methods used the same records according to its PRD and CR for each experiment. The dataset adopted consist of 10 seconds of data from records 100 and 117. Tables 11 and 12 depict the comparison of performance results of CR and PRD with those in literature for record 117 and 100 respectively. From this table, it can be deduced that the proposed method got higher compression ratios compared to the other wavelet transformation techniques. Moreover, the proposed method possesses lower PRD. This is due to the fact that the proposed method is combined approach of

lossy compression (DPCM) and lossless compression (DWT) techniques.

8. Conclusions

This paper presents a hybrid technique for the compression of ECG signals based on DWT and exploiting the correlation between ECG samples; where lossless com-

pression is adopted for clinically relevant parts and lossy compression is adopted for other parts. The ECG signal is segmented into P-waves, QRS-complexes, T-waves, U-waves and isoelectric waves. They are grouped into Region of Interest (RoI) and Non Region of Interest (NonRoI) parts. For a given a fixed bit budget, more bits are devoted to represent RoI parts, while allowing other parts to suffer larger distortion. For this purpose the correlation between the successive samples of the ROI part has been utilized by adopting DPCM approach and the NonRoI part is compressed using DWT, thresholding and coding techniques. Compression is then achieved by selecting a subset of the most relevant coefficients which afterwards are efficiently coded. Illustrative examples are given to demonstrate thresholding based on energy packing efficiency strategy, coding of DWT coefficients and data packetizing. The principal advantages of the proposed approach are: 1) the deployment of different compression schemes to compress different ECG parts to reduce the correlation between consecutive signal samples; and 2) getting high compression ratios with acceptable reconstruction signal quality compared to the recently published results.

The performances of the proposed compression algorithm are evaluated and compared with other known compression algorithms adopting records from MIT-BIH Arrhythmia database. The quality of the proposed compression algorithm is tested in terms of the compression ratio and the PRD distortion metrics using 10 seconds of data from records 100 and 117. The obtained results revealed that the proposed method possesses higher compression ratios and lower PRD compared to the other wavelet transformation techniques. This is due to the fact that the proposed method is a combined approach of lossy compression (DPCM) and lossless compression (DWT) techniques.

REFERENCES