ECG Compression by Efficient Coding Denner Guilhon2 , Allan K. Barros3, , and Silvia Comani1,2 2
1 Department of Clinical Sciences and Bio-imaging, Chieti University, Italy ITAB - Institute of Advanced Biomedical Technologies, University Foundation ‘G.D’Annunzio’, Chieti University, Italy
[email protected],
[email protected] http://www.unich.it/itab 3 Federal University of Maranh˜ ao - UFMA, S˜ ao Lu´ıs – MA, Brazil
[email protected] http://pib.dee.ufma.br
Abstract. The continuous demand for high performance and low cost electrocardiogram (ECG) processing systems have required the elaboration of more and more efficient and reliable ECG compression techniques. Such techniques face a tradeoff between compression ratio and retrieved quality, where the decrease of the last can compromise the subsequent use of the signal for clinical purposes. The objective of this work is to evaluate the validity and performance of an independent component analysis (ICA) based scheme used to efficiently compress ECG signals while introducing tests for a different type of record of the electrical activity of the heart, such as fetal magnetocardiogram (fMCG). As a result, the reconstructed signals underwent negligible visual deterioration, while achieving promising compression ratios. Keywords: independent component analysis, efficient coding, electrocardiogram, fetal magnetocardiogram.
1
Introduction
As the need for constantly larger quantities of ECG data increases, more efficient compression methods are required. Whether to optimize storage or to make online transmission possible over the public phone network, many efforts have been made in order to enhance ECG compression techniques. Consequently, throughout this process many other methods have emerged [1]. Recent works on ECG compression are related mainly to transform methods, as Karhunen-Loeve (KL) transform [2] and wavelet transforms [3][4][5]. Similarly to other compression techniques, electrocardiogram (ECG) compression aims to reduce data volume while preserving the morphological features of the signal after reconstruction. It implies that signal redundancy must be minimized without loss of the information contained therein. When discussing about the primary visual cortex, neuroscientists [6] argued that a primary function of visual neurons is to re-code the input in a way that
Corresponding author.
M.E. Davies et al. (Eds.): ICA 2007, LNCS 4666, pp. 593–600, 2007. c Springer-Verlag Berlin Heidelberg 2007
594
D. Guilhon, A.K. Barros, and S. Comani
reduces redundancy and maximizes the information transmitted to the output. It requires a redundancy reduction process in which the activation of each visual feature is supposed to be as statistically independent from the others as possible [7]. As for natural scenes, an efficient ECG compression method must take into account the high-order statistical dependencies in the data and safeguards its information content, in order to seek a minimum-entropy code [8]. In this work, we discuss a compression method that, for a given ECG signal, finds its basis functions (features) and then the coefficients of the projection of this signal onto a vector subspace spanned by the basis functions. This technique aims to obtain a less redundant and, therefore, more efficient code representation of the ECG source. To achieve this, independent component analysis (ICA) is used to find the vector subspace. Then the signal is projected on that subspace, estimating the projection coefficients in such a manner that they minimize a mean-square-error (MSE) cost function. The same reasoning has led to promising results on image compression [9]. Additionally, initial tests for the compression of fetal magnetocardiograms (fMCG) signals are introduced. Magnetocardiography is a noninvasive and riskfree technique that allows recording the magnetic fields associated with the spontaneous electrophysiological activity of the fetal heart during the second half of gestation [10]. ICA is particularly efficient to process the fMCG and to retrieve fetal cardiac signals that are undistorted by the tissues interposed between the fetal heart and the sensors. The retrieved fetal signals can complement diagnostic methods for pregnancies at risk, such as in the case of intra-uterine fetal growth retardation, or in the presence of fetal arrhythmias [11][12][13]. The use of ICA to extract the fetal signal from fMCG, in conjunction with the application of an ICA based compression algorithm, might permit the online reconstruction of the fetal cardiac signal, which would reveal extremely useful in those clinical cases for which the online monitoring of the fetal cardiac activity is required, such as life threatening fetal arrhythmias.
2 2.1
Methods Proposed Solution
Let e(t) be an ECG signal and assume that it can be divided in m windows of fixed length n. Let us also assume that we can find through ICA a vectorial subspace Φ = [φ1 (t), . . . , φn (t)], where the columns φi (t) are defined as the basis functions of e(t) (see Figure 1). Given that the projection of the ith window of e(t) into Φ is expressed by [14] eˆi (t) = w1 φ1 (t) + w2 φ2 (t) + . . . + wn φn (t)
i = 1, . . . , m,
(1)
where eiˆ(t) is the estimated version of ei (t) and each component wi is the projection coefficient for the ith base function of the subspace Φ. We will drop time index t, for convenience.
ECG Compression by Efficient Coding
595
Fig. 1. System block diagram. (a) The learning phase where the system learns the basis functions φi through the ICA algorithm. (b) The test phase, where the coefficients of the projection are calculated, through a simple mean-square error estimator.
Those coefficients can be calculated through mean-square estimation, where the signal ei is the desired one and input to the estimator. The vector which finds the minimum of the mean-square error, E[ε2 ], is given by wi = E[ΦΦT ]−1 E[ei Φ]
(2)
Here we assume that the desired signal spans the same subspace as the training one, otherwise the output would be null, and that the length of the training input has to be small enough so that in a specific time window, the signal is stationary [15]. The chosen ICA algorithm was FastICA [11][16]. 2.2
Efficient Coding
Let the mutual information of the random variables e1 , . . . , em be defined as I(e1 , . . . , em ) =
m
H(ei ) − H(e1 , . . . , em ),
(3)
i=1
where H(e1 , . . . , em ) is the joint entropy of e1 , . . . , em . The mutual information gives a measure of the dependency among variables. Since information cannot be lost, we recall that I(e1 , . . . , em ) ≥ 0.
(4)
Substituting (4) into (3) yields m
H(ei ) ≥ H(e1 , . . . , em ).
(5)
i=1
Likewise, let the mutual information of the random variables w1 , . . . , wm be defined as m H(wi ) − H(w1 , . . . , wm ), (6) I(w1 , . . . , wm ) = i=1
596
D. Guilhon, A.K. Barros, and S. Comani
where H(w1 , . . . , wm ) is the joint entropy of w1 , . . . , wm . If we assume that w1 , . . . , wm are independents [8], we can state that [17] I(w1 , . . . , wm ) = 0.
(7)
Then substituting (7) into (6) we get m
H(wi ) = H(w1 , . . . , wm ).
(8)
i=1
Given the linear transform ei = Φwi ,
(9)
H(e1 , . . . , em ) = H(w1 , . . . , wm )1 .
(10)
we have [18]
Hence, from (5), (8) and (10) we obtain m
=⇒
i=1 m
H(ei ) ≥ H(w1 , . . . , wm ) H(ei ) ≥
i=1
m
H(wi ).
(11a) (11b)
i=1
Since Lmin = H(ϑ), i.e., the average code length is minimum when it equals the entropy of the set, we can conclude that m i=1
Lmin (ei ) ≥
m
Lmin (wi ),
(12)
i=1
Eq.(12) establishes a relationship between the total code length required to represent e, by means of either ei or wi . We observe that both representations have the same length only when the total code length of ei is the minimum possible, for the representation of wi is already efficient [7]. Otherwise, the total code length of ei would be increased due to the presence of redundancies, that were not present in wi , according to Eq. (7).
3
Results
Our approach was first tested for the MIT Normal Sinus Rhythm Database and the MIT Supraventricular Arrhythmia Database, 15 records each. The first 30 minutes of each record were used in the learning phase, while the test phase used two minutes [14]. 1
The equantion is valid since the random variable wi is of discrete type and the transformation ei = g(wi ) has a unique inverse.
ECG Compression by Efficient Coding
597
Then, similar tests were performed for 15 fetal signals reconstructed from fMCG data recorded for a pregnancy at 35 weeks. The fetal cardiac signals were extracted according to [19]. The first 100 seconds of each record were used in the learning phase, while the test phase used 10 seconds. The coefficients found through Eq. (2) were quantized using as many levels as needed to properly reconstruct the ECG and the fMCG signals. Figure 2 shows that the method does not introduce errors that result in significant visual differences, indicating that the morphological characteristics of the fetal magnetocardiogram are preserved. The reconstruction errors, also shown in figure 2, confirm those results. Figures 3 and 4 show the mean values of 50 repetitions of the percent root-mean-square-difference (PRD) upon reconstruction of each record, defined as n 2 (i) − sigrec (i)] i=1 [sig norig 2 ∗ 100% (13) PRD = i=1 sigorig (i) where sigorig (i) is the original signal, and sigrec is the reconstructed one. (a) 1
0.5
0
−0.5
0
200
400
600
800
1000
1200
800
1000
1200
800
1000
1200
(b) 1
0.5
0
−0.5
0
200
400
600 (c)
1
0.5
0
−0.5
0
200
400
600
Fig. 2. Result of 1200 samples of a fMCG record. (a) Original signal. (b) Reconstructed signal, with CR = 2.66:1 and PRD = 3.43%. (c) Reconstruction error.
4
Discussion
ICA can be used to find a vectorial subspace where the component projections of the ECG signal are mutually independents. Therefore, the coefficients of the signal projected onto this subspace are independent as well. Coding that projection, as a whole or by its parts, results in the same code length [17].
598
D. Guilhon, A.K. Barros, and S. Comani
(a) −1
10
ICA PCA
0
5
10
15
10
15
10
15
PRD
(b)
−2
10
0
5 (c)
−2
10
0
5
Fig. 3. Percent root-mean-square-difference upon reconstruction of 15 records of the MIT Normal Sinus Rhythm Database. Full lines with circle marker stand for ICA results, whereas dashed-dot lines with square markers stand for PCA results. (a), (b) and (c) show results for compression ratios fixed at 3, 2.4 and 2, respectively. Notice the logarithm scale.
(a) ICA PCA
−1
10
0
5
10
15
10
15
10
15
(b) −1.2
PRD
10
−1.5
10
−1.8
10
0
5 (c)
−2
10
0
5
Fig. 4. Percent root-mean-square-difference upon reconstruction of 15 records of the MIT Supraventricular Arrhythmia Database. Full lines with circle marker stand for ICA results, whereas dashed-dot lines with square markers stand for PCA results. (a), (b) and (c) show results for compression ratios fixed at 2.5, 2 and 1.667, respectively. Notice the logarithm scale.
ECG Compression by Efficient Coding
599
Figures 3 an 4 refer to the reconstruction errors obtained when using either ICA or PCA to find a vectorial subspace associated with each one of the 15 ECG records of both databases. These results reflect the performance simulation of our method when compared to that of [2], excluding the contributions of classic compression algorithms. By using ICA, it is observed that the ECG reconstruction errors, even after the quantization process, are smaller than those calculated using PCA. Again, one can see that the method achieves data compression without adding relevant distortion to the signal, what can be confirmed by figure 2. Moreover, from (12) we observe that the average code length required to represent the original signal is larger than that required for represent its coefficients, unless the first is already efficiently coded. In that case, the left side of the equation equals the right one, which means that our method do not alter the representation code length, because it is minimum. Otherwise, due to the presence of redundancies, the code length of the original data representation would be larger than that achieved using our method.
5
Conclusion
We evaluated the validity and performance of an ICA based scheme used to compress ECG and fMCG data. It was verified that such a tool efficiently compresses those signals by means of non-redundant representations of them, ensuring both the reduction of the total data volume and the preservation of the morphological characteristics of the signals. From the perspective of clinical applications, the shown effectiveness of the described compression algorithm would be beneficial not only for adult ECG, but also for prenatal online monitoring of the fetal cardiac activity. A further step in the development of this tool might be its use as a preprocessing step for a classic compression algorithm; furthermore, a selection criterion might be included to allow also the reduction of the numbers of coefficients that should be stored.
Acknowledgements This work was supported by FAPEMA.
References [1]
[2]
Jalaleddine, S.M., Hutchens, C.G., Strattan, R.D., Coberly, W.A.: ECG data compression techniques-A unified approach. IEEE Trans. Biomed. Eng. 37(4), 329–343 (1990) Olmos, S., Millan, M., Garcia, J., Laguna, P.: ECG data compression with the Karhunen-Loeve transform. In: Computers in Cardiology, Menlo Park, CA, pp. 253–256. IEEE Comput. Soc. Press, Los Alamitos (1996)
600 [3]
[4]
[5] [6] [7]
[8] [9] [10] [11]
[12]
[13]
[14]
[15] [16] [17] [18] [19]
D. Guilhon, A.K. Barros, and S. Comani Miaou, S.G., Chao, S.N.: Wavelet-based lossy-to-lossless ECG compression in a unified vector quantization framework. IEEE Trans. Biomed. Eng. 52(3), 539–543 (2005) Blanco-Velasco, M., Cruz-Roldan, F., Godino-Llorente, J.I., Barner, K.E.: ECG compression with retrieved quality guaranteed. Electronics Letters 40(23), 1466– 1467 (2004) Rajoub, B.A.: An efficient coding algorithm for the compression of ECG signals using the wavelet transform. IEEE Trans. Biomed. Eng. 49(4), 355–362 (2002) Sekuler, A.B., Bennet, P.J.: Visual neuroscience: Resonating to natural images. Curr. Biol. 11, R733–R736 (2001) Bell, A.J., Sejnowski, T.J.: Edges are the independent components of natural scenes. In: Advances in neural information processing systems, vol. 9, pp. 831– 837. MIT Press, Cambridge (1997) Olshausen, B.A., Field, D.J.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381, 607–609 (1996) Souza, C.M., Cavalcante, A.B., Guilhon, D., Barros, A.K.: Image compression by Redundancy Reduction, submited to ICA (2007) Tavarozzi, I., et al.: Magnetocardiography: current status and perspectives: Part I. Physical principles and instrumentation, Ital. Heart J. 3, 75–85 (2002) Hild II, K.E., Alleva, G., Nagarajan, S.S., Comani, S.: Performance comparison of six Independent Components Analysis algorithms for fetal signal extraction from real fMCG data. Phys. Med. Biol. 52, 449–462 (2007) Comani, S., et al.: Time course reconstruction of fetal cardiac signals from fMCG: Independent Component Analysis vs. Adaptive Maternal Beat Subtraction, Physiol. Meas 25, 1305–1321 (2004) Comani, S., et al.: Characterization of fetal arrhythmias by means of fetal magnetocardiography in three cases of difficult ultrasonographic imaging. Pacing. Clin. Electrophysiol. 27, 1647–1655 (2004) Guilhon, D., Medeiros, E., Barros, A.K.: ECG Data Compression by Independent Component Analysis. In: IEEE Workshop on Machine Learning for Signal Processing, September 28-30, 2005, pp. 189–193 (2005) Barros, A.K., Ohnishi, N.: Single channel speech enhancement by efficient coding. Signal Processing 85(9), 1805–1812 (2005) Hyvarinen, A., Oja, E.: A fast fixed-point algorithm for independent component analysis. Neural Computation 9, 1483–1492 (1997) Hyvarinen, A., Karhunen, J., Oja, E.: Independent Component Analysis. John Wiley & Sons, New York (2001) Papoulis, A., Pillai, S.U.: Probability, Random Variables and Stochastic Processes, 4th edn. McGraw-Hill, New York (2002) Comani, S., et al.: Independent component analysis: fetal signal reconstruction from magnetocardiographic recordings. Comput. Meth. Prog. Biomed. 75, 163– 177 (2004)
