Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
A CONTEMPORARY APPROACH FOR ECG SIGNAL COMPRESSION USING WAVELET TRANSFORMS Pranob K Charles1, Rajendra Prasad K2 1
Assoc.Prof, Dept of ECE, K.L University Asst.Prof, Dept of ECE, K.L University
2
1
[email protected]
ABSTRACT Signal compression is an important problem encountered in many applications. Various techniques have been proposed over the years for addressing the problem. In this project Transform based signal compression is proposed. This method is used to exploit the redundancy in the signal. This Paper uses Wavelet Transform to compress the signals. We compare the two existing wavelet methods with the proposed algorithm to determine which of them has better compression ratio (CR) and percent root mean square difference (PRD). The proposed method is significantly more efficient in compression, computation and it can attain exact bit rate control and generate a bit streams progressive in quality.In order to assess the performance of the algorithm the data sequences are taken from MIT-BIH and AHA arrhythmia database.
KEY WORDS CR, PRD, MIT-BIH and AHA
I. INTRODUCTION Compression connotes the process of starting with a source of data in digital form (usually either a data stream or a stored file) and creating a representation for that uses fewer bits than the original. The aim is to reduce storage requirements or transmission time when such information is communicated over a distance. Ideally one needs the compression process to be reversible. Suppose a discrete time signal s(n) is compressed and then reconstructed (that is ,the inverse of the compression process is performed to yield s^(n). The error signal is defined as e(n) = s(n) – s^(n)
(1)
The reconstructed signal can be alternatively as an additive noise contaminated version of the original by rewriting the above equation as s^(n) = s(n) + w(n)
(2)
Where w (n) = - e (n) is the noise. For a loss less compression e (n) is identically zero. A typical computerized signal processing system acquires a large amount of data that is difficult to store and transmit. Data compression is nothing more-or-less than effective coding DOI : 10.5121/sipij.2011.2113
178
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
designed to correct the over representation that occurs in digital data handling systems. Data compression is going to increase (a) The storage efficiency. (b) Transmission bandwidth conservation. (c) Reducing the transmission time. The main goal of any compression technique is to achieve maximum data volume reduction while preserving the significant features. Data compression is the process of detecting and eliminating redundancies in a given data set. Compression techniques broadly fall into two categories: loss less and lossy. Lossy compression is useful in certain applications like broadcast television, where a certain amount of error is acceptable for increased compression performance. Loss less or information preserving compression is used in the storage of medical or legal records. Data compression techniques are mainly classified into three categories. 1. Direct data compression methods 2. Transformation methods 3. Parameter extraction methods Direct data compression methods rely on prediction or interpolation algorithms, which try to diminish redundancy in a sequence of data by looking at successive neighboring samples. Prediction algorithms employ a prior knowledge of previous samples, where as interpolation algorithms use a prior knowledge of both previous and future samples. The direct data compression methods base their detection of redundancies on direct analysis of actual sample. Direct signal compression methods are also known as time domain techniques dedicated to compression of signals. The mode of operation is to extract a subset of significant samples from the original sample set. Which samples are significant, depends on the underlying criterion for the sample selection process. Transformation methods involve processing of the input signal by a linear orthogonal transformation and encoding of output using an appropriate error criterion. For signal reconstruction an inverse transformation is carried out and the signal is recovered with some error. Various orthogonal transformations include DCT, DST, FFT and WAVELET transforms etc. The parameter extraction method includes extracting a particular parameter of the signal. The extracted parameters are subsequently utilized for classification based on a prior knowledge of the signal features. Direct and transformation methods are reversible, while parameter extraction method is irreversible. In this project, the signal we had taken is an ECG signal and it is compressed using the Discrete Cosine Transform, Discrete sine Transform, Fast Fourier Transform. Encoding method used in this procedure is Entropy encoding. For signal compression using wavelet transform we proposed new algorithm.
179
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
II. REQUIREMENTS OF ECG REPRESENTATION A typical electro cardiogram (ECG) monitoring device generates massive volumes of digital data. Depending on the intended application for the data, the sampling rate ranges from 125 to 500 Hz. Each data sample may be digitized to a 8 to 12 bit binary number. Furthermore, up to 12 different streams of data may be obtained from various sensors placed on the patient’s body. Even at the lowest sampling rate in the range and assuming just one sensor that generates 8-bit data, we would accumulate ECG data at a rate of 7.5 KB per minute or 450 KB per hour. At the other extreme (12 sensors generating 12-bit values at 500 Hz), data is generated at a rate of 540 KB per minute or more than 30 MB per hour. If we wish to store an ECG recording that spans more than a few minutes, some form of data compression is highly desirable. Recordings over quite long periods, as much as 24 hours, may be needed when a patient has complained of irregular heart rhythms. Doctors may wish to build a database of ECG recordings for their patients so that two ECG traces taken on different dates may be compared. Compression is also desirable if a doctor wishes to transmit ECG over a telephone line to a cardiac specialist for an expert opinion. An ECG trace is a digitized version of a continuous signal. Therefore compression techniques applicable to such signals are also applicable to ECG traces. For example, DPCM (Differential Pulse Code Modulation) and various versions of that technique are eminently suitable. Another possibility based on signal processing techniques is to apply a transform coding and to encode the subsequent coefficients in a lossy manner. For example, a Cosine Transform (CT) or Fourier series transformation may be applied. The Karhunen-Loeve transform (KLT) appears to be particularly suitable and is often used for ECG compression because (to quote [5]) “... the least number of orthonormal functions is needed to represent the input signal for a given rms error.”
III. NEED FOR ECG SIGNAL COMPRESSION The need for ECG signal compression exists in many transmitting and storage applications. Transmitting the ECG signal through telephone lines, for example, may save a crucial time and unnecessary difficulties in emergency cases. Effective storage is required of large quantities of ECG information in the intensive coronary care unit, or in Long-term (24–48 hours) wearable monitoring tasks (Holter). Holter monitoring usually requires continuous 12 or 24-hours ambulatory recording. For good diagnostic quality, each ECG lead should be sampled at a rate of 250–500 Hz with 12 bits resolution. The information rate is thus approximately 11–22 Mbits/hour/lead. The monitoring device (“Holter”) must have a memory capacity of about 100– 200 Mbytes for a 3-lead recording. Memory costs may render such a solid state Holter device impractical. In practice, efficient data compression may be achieved only with lossy compression techniques (which allow reconstruction error). In ECG signal compression algorithms the goal is to achieve a minimum information rate, while retaining the relevant diagnostic information in the reconstructed signal. All ECG compression algorithms have used simple mathematical distortion measures such as the percentage rms difference (PRD) for evaluating the reconstructed signal. It is used to evaluate the compression result.
180
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
.
Fig 1: Some of the diagnostic features used by the WDD (and beat segmentation)
IV. MEASURES OF PERFORMANCE A. Error criterion and the distortion methods: One of the most difficult problems in ECG compression applications and reconstruction is defining the error criterion. The purpose of the compression system is to remove redundancy and irrelevant information. Consequently the error criterion has to be defined so that it will measure the ability of the reconstructed signal to preserve the relevant information. Since ECG signals generally are compressed with lossy compression algorithms, we have to have a way of quantifying the difference between the original and the reconstructed signal, often called distortion. The most prominently used distortion measure is the Percent Root mean square Difference (PRD) that is given by 1
2 Lb 2 ∑ [x(n) - x` (n)] PRD = n=1 Lb 2 [x(n)] ∑ n =1
(3)
Where x (n) is the original signal, x’ [n] is the reconstructed signal and N is the length of the block or sequence over which PRD is calculated. Another definition of error measure called PRD2, is same as PRD but it subtracts the average value of the signal from the signal in the denominator and is given by 1 2 Lb 2 ∑ [x(n) - x` (n)] X 100 PRD2 = n=1 Lb - 2 [x(n) x ] ∑ n =1
(4)
x - is the average value of the signal. PRD provides a numerical measure of the residual root mean square (rms) error.
V. TRANSFORMATION METHODS A. Wavelet transforms Mathematical Transformations are applied to signals to obtain further information from that signal that is not readily available in the raw signal. There are numbers of transformation that can be applied among which the Fourier Transform (FT) are probably by far the most popular. If the FT of a signal in the time domain is taken, the Frequency – Amplitude representation of 181
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
that signal is obtained. In other words, we now have a plot with one axis being the frequency and other being the amplitude. This plot tells how much of each frequency exists in our signal. But it does not tell us when in time these frequency components exist. This information is not required when the signal is so called stationary. That is FT gives the spectral content of the signal, but it gives no information regarding when in time those spectral components appear. Therefore FT is not a suitable technique for non-stationery signal. When the time localization of the spectral compounds is needed, a transform giving the TIME-FREQUENCY REPRESENTATION of the signal is needed. This leads to a revised version of the Fourier Transform, so called “The short time Fourier Transform (STFT). There is only a minor difference between STFT & FT. In STFT, the signal is divided into small enough segments, where the segments (portions) of the signal can be assured to be stationary. For this purpose, a window Function “W” is chosen. The width of this window must be equal to the segment of the signal when its stationary is valid, after that FT is to be taken. Therefore, we will obtain a True-TIME-FREQUENCY representation of the signal. Contrary to STFT, which provides a fixed resolution at all times, wavelet transform gives a variable resolution as follows. The wavelet transform comprises the coefficients of the expansion of the original signal x( t) with respect to a basis Ψ w,n(t), each element of which is a dilated and translated version of a function Ψ called the mother wavelet, according to 1
Ψω,n(t) = Ψ((t-2ωn)/ 2ω) , ω, n, ∈ Z,
(5)
ω
√2
where Z is the set of integers. Depending on the choice of the mother wavelet appropriately, the basis can be orthogonal or biorthogonal. The wavelet transform coefficients, given by the inner product of x(t) and the basis functions, W(ω, n) =< x(t), Ψω,n(t) >
(6)
Comprise the time-frequency representation of the original signal. The wavelet transform has good localization in both frequency and time domains, having fine frequency resolution and coarse time resolution at lower frequency, and coarse frequency resolution and fine time resolution at higher frequency. Since this matches the characteristic of most signals, it makes the wavelet transform suitable for time-frequency analysis. In data compression, the wavelet transform is used to exploit the redundancy in the signal. After the original signal is transformed into the wavelet domain, many coefficients are so small that no significant information is lost in the signal reconstructed by setting these coefficients to zero. In the biorthogonal case, there are two scaling functions
, which may generate different
multiresolution analyses, and accordingly two different wavelet functions numbers M, N of coefficients in the scaling sequences must satisfy the following biorthogonality condition
.
. So the
may differ. The scaling sequences
(7) 182
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
Then the wavelet sequences can be determined as , n=0,...,M-1 and , n=0,....,N-1.
(8)
In digital signal processing, the fast forward and inverse wavelet transforms are implemented as tree-structured, perfect-reconstruction filter banks. The input signal is divided into contiguous, non overlapping blocks of samples called frames and is transformed frame by frame for the forward transform. Within each frame, the input signal is filtered by the analysis filter pair to generate low pass and high pass signals , which are then down sampled by a factor of two. Then this analysis filter pair is applied to the down sampled lowpass signal recursively to generate layered wavelet coefficients shown in Figure 1. In different layers, the coefficients have different frequency and time resolution. In layer i, each coefficient corresponds to two coefficients in layer i + 1 in the time domain. For the inverse transform, the coefficients in the highest layer are upsampled by a factor of two (zeros are inserted between successive samples), filtered by the low- and high-pass synthesis filter and added together to get the low pass signal for next layer. This process is repeated for all layers until the full size signal is reached to complete the inverse transform. The selection of different analysis-synthesis filter pairs, which correspond to different wavelet bases, is very important for obtaining effective data compression. In implementation, the frame size, number of layers of the wavelet transforms and the filter pair needs to be appropriately selected. The number of layers determined the coarsest frequency resolution of the transform and should be at least four for adequate compression. The frame size is taken to be a power of 2 that exceeds the number of layers.
VI. IMPLEMENTATION This project uses four different Transforms to Compress an ECG Signal Discret Cosine Transform, discrete sine Transform, Fast Fourier transform and Wavelet Transform and compare the four methods to determine which of them has better Percent Root Mean Square Difference (PRD) and Compression Ratio (C.R).
ECG Database The public American Heart Association (AHA) ECG database consists of eighty recordings each of three hour duration. Each recording in the series consists of two channels of ECG sampled and digitized at 250 samples per second. The database was recorded under different conditions. The database is generally available as an arrhythmia category. Arrhythmia analysis is used for long term monitoring in the intensive care unit. In this one or two ECG leads are monitored or recorded to look for life threatening disturbances in the rhythm of the heartbeat.
183
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
A. Procedure followed for the compression of the signal using Wavelet Transform After the wavelet transform, we use the Proposed algorithm to encode thewavelet coefficients. Here we apply the Proposed algorithm to the wave (purely dyadic) transform of ECG signals.
Fig2: The diagram of the proposed encoder and decoder The principles of the Proposed algorithm are partial ordering of the transform coefficients by decomposition, ordered bit plane transmission and exploitation of self similarity across different layers.
B. Proposed Algorithm Step 1 Loading of signal is done The signal which is taken from the AHA (American Heart Association) database as a dat file and is copied into notepad and taken it as an M-file. Step 2 Setting the value of number of Decomposition levels. Step 3 Defining the wavelet name. Step 4 Coding of Quantized Coefficients will be done Creating a temporary register and taking the values of significant pixels and setting the threshold 2n with n = [log2 (max (i)|ci|)]. Step 5 Quantizes the wavelet decomposed coefficients. Step 6 decoding of Coded coefficients if done. Step 7 Dequantization is done. Step 8 Calculation of Percent Mean Square Difference (PRD) is done. Step 9 Calculation of Compression Ratio (CR) is done. Step 10 Displaying the results. 184
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
VII. RESULTS Data in the American heart association Electrocardiograph (AHA) database is used to test the performance of these coding schemes. All ECG data used here are sampled at 250Hz and a resolution of each sample is 12 bits per sample, so that the total bit rate of these data is 3000 bps. The tables given indicate the performance of the compression algorithm for different sequence of samples. From the theoretical background of measures of performance it can be concluded that neither high values of PRD guarantee a truly distorted signal nor lower values of PRD guarantee a clinically acceptable signal quality. The efficiency of the compression algorithm can be better analyzed by visual similarity between the original signal and the reconstructed signal. The visual assessment of the quality of the reconstructed signal is presented in figures for different reconstructed signals.
Fig 3: Comparison of Average Test results of SPIHT,JPEG2000 and Proposed
185
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
TABLE I Comparison of Average PRD results of SPIHT, JPEG2000 with Proposed Algorithm CR
SPIHT
JPEG
PROPOSED
PRD
2000
ALGORITHM
PRD
PRD
4:1
1.19
0.78
0.29
5:1
1.56
0.99
0.42
6.6:1
--
1.28
0.65
8:1
2.46
1.52
0.7195
10:1
2.96
1.86
1.024
12:1
3.57
2.19
1.34
16:1
4.85
2.74
2.877
20:1
6.49
3.26
3.22
Fig4: Compression using wavelet with CR = 10:1 and PRD = 1.02
186
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
Fig5: compression using WT with CR = 12:1 and PRD = 1.34
Fig 6: Compression using wavelet transform with CR = 16:1 and PRD = 2.9
VIII. CONCLUSIONS Results were obtained by running the compressor on different sets of data taken from MIT-BIH and AHA arrhythmia database. These results shows that the proposed ECG data compression algorithm is capable of achieving good compression ratio values compared to SPIHT Algorithm and JPEG 2000 algorithm. 187
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
The algorithm compresses all kinds of ECG data very efficiently, perhaps more efficiently than any previous ECG compression methods. The user can truncate the bit stream at any point and obtain the best quality reconstruction for the truncated file size.
REFERENCES [1]
Simon Haykin, Neural Networks: a comprehensive foundation, 2nd ed., Upper Saddle River,
NJ: Prentice Hall, 1999 [2]
Paul S. Addison, The Illustrated Wavelet Transform Handbook: Introductory Theory and
Applications in Science, Engineering, Medicine and Finance, London, UK: The Institute of Physics Publishing, 2002 [3]
F. B. Tuteur, ‘Wavelet transforms in signal detection’, Wavelets, Berlin: Springer, pp. 132-138,
1989 [4]
Y. Mallet, D. Coomans, J. Kautsky and O. De Vel, ‘Classification Using Adaptive Wavelets for
Feature Extraction’, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no.10, Oct. 1997 [5]
S. M. S. Jalaleddine, C. G. Hutchens, R. D. Strattan and W. A. Coberly. ECG Data Compression
Techniques – A Unified Approach. IEEE Trans. on Biomedical Eng., vol. 37, 4 (April 1990), pp. 329341. [6]
J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Trans. on
Information Theory, vol. 23, 3 (1977), pp. 337-343. [7]
J. Cox, F. Noelle, H. Fozzard, and G. Oliver, \AZTEC: A preprocessing program for real-time
ECG rhythm analysis," IEEE Trans. Biomed. Eng., vol. BME-15, pp. 128{129,1968. [8]
J. Abenstein and W. Tompkins, \New data-reduction algorithm for real-time ECG analysis,"
IEEE Trans. Biomed. Eng., vol. BME-29, pp. 43{48, 1982. [9]
W. Mueller, \Arrhythmia dectection program for an ambulatory ECG monitor," Biomed.Sci.
Instrument, [10]
D. A. Dipersio and R. C. Barr, \Evaluation of the fan method of adaptive sampling on human
electrocardiograms," Medical & Biological Engineering & Computing, pp. 401{410, September 1985. [11]
D. Haugland, J. Heber, and J. Hus_y, \Optimisation algorithms for ECG data compression,"
Medical & Biological Engineering & Computing, vol. 35, pp. 420{424, July 1997. [12]
C. P. Mammen and B. Ramamurthi, \Vector quantization for compression of multichannel
ECG," IEEE Trancations on Biomedical Engineering, vol. 37, pp. 821{825,September 1990. [13]
M. C. Aydin, A. E. C_ etin, and H. K}oymen, \ECG data compression by sub{band coding,"
Electronics Letter, vol. 27, pp. 359{360, February 1991.
188
Signal & Image Processing : An International Journal(SIPIJ) Vol.2, No.1, March 2011
[14]
S. C. Tai, \Six-band sub-band coder on ECG waveforms," Medical & Biological Engineering &
Computing, vol. 30, pp. 187{192, March 1992. [15]
D. C. Thomson, D. J. Hamilton, andW. A. Sandham, \Electrocardiagram data compression
using artificial neural networks," Int. J. Applied Sig. Proc., vol. 2, no. 1, pp. 16{23,1995. [16]
D. J. Hamilton, D. C. Thomson, and W. A. Sandham, \ANN compression of morphologically
similar ECG complexes," Medical & Biological Engineering & Computing, vol. 33,pp. 841{843, 1995. [17]
Z. Lu, D. Y. Kim, and W. A. Pearlman, “Wavelet compression of ECG signals by the set
partitioning in hierarchical trees algorithm”, IEEETrans. on Biomedical Engineering, vol. 47, pp. 849856, July 2000. [18]
David Taubman, Member, IEEE “High Performance Scalable Image Compression with
EBCOT” IEEE Trans. on Image Processing, vol. 9, no. 7, July 2000. [19]
Ali Bilgin, Member, IEEE, Michael W. Marcellin, Fellow, IEEE and Maria I. Altbach, Member,
IEEE “Compression of Electrocardiogram Signals using JPEG2000” IEEE Transactions on Consumer Electronics, Vol. 49, No. 4, November 2003. [20] Konstantinos Konstantinides and Balas K. Natarajan “An Architecture For Lossy Signal Compression” 1992 IEEE Workshop on VLSI Signal processing, Oct. 92.
189
