The constant evolution of mobile technologies has lead to several systems with focus on the mobile electrocardiogram (ECG) telemonitoring of patients. They usually present a client-server architecture, where a web server centralizes the storage, management and processing of the patient's signals, and a mobile phone is responsible for acquiring and transmitting the data over the internet (WAP or 3G) to the server. However, there are countries, like Brazil, whose mobile network services do not present full coverage, even in large urban areas. This leads to a lack of security under certain situations like emergency calls or critic patient's monitoring when the patient is in an area without mobile network coverage. In these situations, the patient's vital signals must be analyzed as soon as possible, in order to allow fast preventive or reactive actions to be taken. An alternative way to deal with this problem is to support the analysis of vital signals in a mobile phone which can be either offline or communicating through a cell phone network. Though, since mobile phones, compared to PCs, have slower CPUs and less internal memory, it's important to select an ECG wave analysis method that is not costly with respect to computation time and memory usage. In this paper, we present comparison study made in order to select a reliable method for ECG beat classification running in a mobile phone. Three ECG beat classification methods were selected to be analyzed and implemented in a mobile phone. Tests were made in regions with limited cell phone network coverage in south Brazil. Test results were compared in order to choose a method whose implementation is efficient enough to run in a mobile phone and can achieve high accuracy on the classification of the ECGs, even if running in a phone with limited CPU as well as memory resources.
2 I9Access Tecnologia Ltda
Heart and cardiocirculatory diseases are the most common
causes of death in the majority of western countries,
including Brazil where more than 30% of the deaths are
related to them [
Many computational methods have been proposed to automate the process of ECG waves analysis, helping physicians to diagnose anomalies on ECG exams. Although these methods have achieved very good performances, many of them rely on heavy computational algorithms and can be very costly in terms of CPU and memory usage. Considering this, we present, in this paper, a comparison of some of the most reliable ECG beat classification methods. Our main objective is to point out one or more methods that can successfully classify ECG beats with high accuracy and fast response even when implemented and running in a mobile phone with limited CPU as well as memory resources.
The next sections are organized as follows. Section 2 introduces the ECG beat classification problem and the most commonly used techniques to solve it. Section 3 is reports on the implementation of some classification methods in mobile devices. In section 4 we comment on the results obtained in the evaluation of the implemented methods. Finally, in Section 5 we present our conclusions and point out to future work.
The automatic ECG classification methods apply techniques from several computing areas, like computational statistics, pattern recognition, support vectors machines, etc. However, there is a basic set of common steps between these methods: Beat Detection, Feature Extraction and Beat Classification. The next sections will introduce the ECG classification process and review the most used techniques.
The Beat Detection step is usually made using common
annotated ECG database, easing the detection process and
unifying the data sets used amongst the majority of the
authors. When applied to real ECGs, this stage must be
made by a QRS detector algorithm, like the Pan Tompkins
method [
The Feature Extraction follows the beat detection, and it is responsible for transforming the raw ECG signal, mapping the original values to meaningful features. This is a very important stage, and the most successful classification methods rely on a good feature extraction stage to achieve high performances.
Finally, the Beat Classification stage will be performed over the features extracted on the second stage. The authors employ several classification and pattern recognition techniques, allowing them to distinguish the type of each beat that is being classified.
Many authors have already employed these steps on the past, building classifiers that can achieve high accuracy rates on the classification task. We analyzed the results and implementation of many methods, aiming the selection of one of them for the usage on a mobile system. Thus, the method must be efficient in time and in memory usage, at the same time as it must achieve high accuracy to guarantee that it can improve the capacity of the system to save human lives.
Mehmet Engin [
However there is a basic set of common steps between these methods: Beat Detection, Feature Extraction and Classification.
The Beat Detection is a signal processing consisting of QRS complex detection. The QRS complex detection methods already have excellent solutions and are not addressed in this work. What is true highlight is that the following step will process only segments of the QRS complexes. The feature extraction stage consists in transforming the signal into a suitable format to perform the classification. Finally we perform classification of extracted features in a certain class amongst the classes that the method is able to identify, such as normal beat, pacemaker beat, etc.
The three methods that this work analyzes uses discrete wavelet transform together with mathematical procedures to extract the features that will be classified. 2.2.1
The wavelet functions are widely used in signal processing. While the Fourier Transforms work only in frequency domain, the wavelet analysis works also in the time domain, a fact which facilitates the analysis of local characteristics of signal, what is very important for classification of ECG beats. Both the Fourier analysis and wavelet analysis intend to approximate a signal by a linear combination of sines and cosines (Fourier analysis) or wavelets. The approximation of the signal in wavelet analysis is performed by a process called wavelet transform which has the continuous and discrete variants.
The continuous wavelet transform (Continuous Wavelet
Transform - CWT) of a signal f is the inner product of the
signal by a wavelet, in this case called mother wavelet ψ, as
it appears in the following formula:
The mother wavelet ψ is given by the following formula:
The Discrete Wavelet Transform (DWT) of a signal
expressed as a vector of samples X = (x0, x1,, …, xT)t can
be expressed as:
However, in practice, this turns into the use of a pyramidal
algorithm, where a series of low pass and high-pass filters
are applied to the signal. The Pyramid algorithm that
computes the wavelet transform was proposed by Stephane
G. Mallat [
The filters depend on the type of wavelet-mother used on
the transform. The most commonly used is the Haar
wavelet, and its low-pass and high-pass filters are shown
below:
h = [0.70710678118654757, 0.70710678118654757]
l = [0.70710678118654757, 0.70710678118654757]
Some authors use the à trous wavelet transform [
Several statistical measurements are used by the ECG beat classification methods, including the variance, standard deviation, auto correlation and relative amplitudes. The variance is defined like the average of the square of the distance of each value from the mean, it shown the difference of a value in relation to the mean value. Can be expressed by the following formula: From the variance we can calculate the standard deviation which is defined as the square root of the variance, or even the average distance of each value to the average, which shows how the sample is distributed to the extent that deviates from the mean.
Another important measure is the auto correlation, which is considered a measure of similarity between a sample and its shifted version. The auto correlation can be expressed as follows: where x(n) is a sample of size N. This calculation tells how much a certain value influences the neighborhood values, i.e., how related are the values of a sample.
We still have the relative amplitude, which is nothing more than the ratio between the minimum and maximum value for a given sample, which shows morphological characteristics of the sample. 2.2.3
The Principal Component Analysis (PCA) reduces the dimension of matrices building a smaller matrix only with the principal information of the original one. For example, considering the training and testing sets that will be classified, it is possible to reduce a 10-dimensional feature set to a 5-dimension, extracting the higher five principal components. The process to find principal components is the process to find eigenvectors of a covariance matrix R formed by the feature set. The covariance matrix R is given by: The eigenvalues and eigenvectors are the obtained solving the eigenvalue problem. For this problem, ten eigenvalues and ten eigenvectors are obtained, the five eigenvectors corresponding to the highest five eigenvalues will be used to build a new feature set.
The new feature set is obtained by the multiplication of each sample by the five eigenvectors, yk: 2.2.4
A cumulant is a Higher Order Statistics measure that is
commonly used in physics. They can be seen as a set of
quantities that provide an alternative to the moments of the
signal, providing useful information about the probabilities
distribution of the signal [
The Probabilistic Neural Network (PNN) is a neural
network used primarily as a classifier, but it can also be
seen as an alternative way to implement a statistical
algorithm called discriminant [
The classification phase of this neural network is simple, yet costly. Each input from the training set will have its PDF estimated for every neuron from the Pattern Layer. The next layer, the Summation Layer will compute the probability of the sample of being of each class accumulating the values from the pattern layer and grouping them by class. Finally, the Output Layer will select the neuron with a higher value from the Summation Layer to be the class of the sample.
To estimate the probability density function of a given sample is performed using the kernel density estimation approach, also called Parzen window, which is basically a technique of data interpolation. Given an instance x, the Parzen window PDF estimates b fx(x) for each sample data set. As the following expression: where K is the kernel function, h is a smoothing parameter and n is the number of samples in the data set.
The kernel function most used is a Gaussian that can be represented by:
2.2.6
The K Nearest Neighbors algorithm calculates the
euclidean distance of a testing sample with all the training
samples. The input sample is classified with the same class
of the mode class of the k nearest neighbor according to the
euclidean distance [
The Multi-Layer Perceptron (MLP) is a neural network that is usually used to solve classification problems. A common type of MLP is the Feed forward Back propagation Neural Network (FFBNN), whose name is given because the input is forward propagated and the errors are back propagated to correct the neurons weights.
To explain the behavior of the FFBNN, consider the topology described in figure. The input layer propagates the input values to the hidden layer, multiplying the value of each neuron with the respective weight. The final value on the hidden layer neurons are obtained applying the activation function on the summation of all weighted values. The value of the output layer neurons are calculated with the same procedure, however, this value is compared with the desired value from the training set, and the difference (the error) is backpropagated to correct the neuron weights for all layers.
One efficient method to backpropagate the error,
minimizing the overall error of the network, was proposed
by Broyden-Fletcher-Goldfarb-Shanno (BFGS) as a generic
optimization algorithm. It is a quasi-Newton non-linear
method for optimization that transforms the error problem
on a minimization problem solving the hessian matrix
approximation problem [
Although in the previous sections we presented only a subset of the methods that have been proposed in the literature, we have chosen these methods relying on their accuracy and the sensitivity rates. Thus, the most efficient methods are covered by this study.
# beats
Accuracy (%)
Lesser Sensitivity Method
Minhas and Arif
4
4
6
6
6
6
98,0
96,94
99,65
99,51
99,70
99,49
95,3
95,56
99,04
98,24
98,88
98,92
measure can cause. Considering these facts, we decided to
choose three methods to compare and implement on a
mobile device, they are: Chen and Yu method [
The following subsections will review the selected methods.
The method proposed by Yu and Chen [
The DWT is applied on the raw ECG signals to perform the extraction of the features. From the first and second level wavelet (WT) detail coefficients (D1 and D2), and from the second level approximation coefficients (A2) several statistical measurements are calculated, including the variance of the coefficients, the variance of the auto correlation function of the coefficients, the ratio between the maximum and minimum values and the interval between the current beat and the last one.
The authors proposed two feature sets, namely: FS1 and FS2. FS1 includes the variance of the original signal, the variance of D1, D2 and A2, the variance of the autocorrelation of D1, D2 and A2 and the ration between the maximum and minimum values of D1, D2 and D3, for a total of 10 features. FS2 contains all the features of FS1 plus the instantaneous RR interval, since it is an important information for arrhythmias.
After the feature extraction, each feature is normalized, using the hyperbolic tangent sigmoid function to map the values of each feature to the range [-1, +1].
Yu and Chen use a PNN to perform the classification of the beats. All the training instances must be loaded on the network at the moment of the classification, thus, this method is very costly in terms of memory usage. The fact that the PNN is instance-based also implies that the method is costly in terms of time, because it needs to process the whole training set to classify each testing instance. For each sample that needs to be calculated, the algorithm needs to compute its PDF relative to each instance from the training set. After this phase, which is made on the Pattern Layer, the Summation layer will sum the results of all neurons from the Pattern Layer, grouping by the class of the neuron and making a weighted average of the value. Finally, the Decision Layer will classify the instance with the class that had the higher average on the Summation Layer.
The method developed by Minhas and Arif [
To perform the feature extraction the à trous DWT, using the Quadratic Spline Wavelet as the mother wavelet, is applied to the samples.
The first and second level detail coefficients, and the second level coefficients are selected as a base for the feature set. From them, the same statistical features as the FS2 from the Yu and Chen method are calculated. The authors also employed the Principal Component Analysis to generate a second feature set, with a reduced dimensionality. However, this procedure also reduced the accuracy of the method, thus, we will focus only on the original feature set, which contains 11 features for each sample.
Minhas and Arif employed a k-Nearest Neighbor algorithm to classify the testing set. This classifier is extremely easy to implement, since it’s depends only on a ordered list of distances between the sample that is being classified and all other samples from the training set. The Euclidean Distance was the selected distance metric, and the k parameter was set to 3.
The method proposed by Chen and Yu uses Higher Order Statistics with the DWT to build a large feature set for each ECG beat, what is classified by a Multilayer Perceptron. The classifier covers the same beat types set as the Yu & Chen method.
To be successful on the difficult task of finding a reliable feature set the authors employed Higher Order Statistics allied to the DWT.
Three higher order statistics features are selected to be help to build the feature set, namely: second order cumulant, third order cumulant and fourth order cumulant. The authors use the à trous DWT, with the ‘sym6’ as the mother wavelet, to calculate five levels of coefficients. The 2nd, 3rd and 4th order cumulants are extracted from the detail wavelet coefficients of level 3, 4 and 5. As a result, nine cumulants are calculated for each beat, and from them several features are calculated, including: Cumulant Variance and Normalized Summation for each cumulant, the Number of Zero-Crossings on the cumulants of the level 5 coefficients and the Symmetry of the 3rd and 4th order cumulants. Additionally, three RR-interval related features are defined, including: current RR interval, previous RR interval and the ratio between the current and the previous RR interval. In summary, the feature set is formed by 30 features.
The classification stage of this method is performed by a MLP, which is a neural network composed by, in this case, three layers of neurons. The first layer only propagates the inputs signal, while the hidden and output layers will combine the inputs with a set of neuron weights and apply an activation function to compute the output. The output is compared to the desired output and an error value is produced. This error is used to adjust the previous neurons weights in a process called Backpropagation training. The authors empirically defined that the hidden layer is formed by sixty neurons, and the activation function of the network is the hyperbolic tangent sigmoid. The Backpropagation training uses the BFGS method to minimize the error.
To evaluate the behavior of the implemented methods we
used 23 records from the MIT/BIH arrhythmia database
[
MIT/BIH Record # Training # Testing 103, 113, 115, 123, 220, 234 109, 111, 207, 214 118, 124, 212, 231 119 221 209 222 232 200, 233 107, 217 600 600 600 200 150 400 150 100 600 600 600 600 600 200 150 400 150 100 600 600 Type N LBBB RBBB PVC APB PB Total 11600 11600
Table 2 shows details of the records from the MIT/BIH database that were used to form the training and testing instance sets. Since neural networks need large training sets to achieve a good performance, we used 11,600 instances on each set.
Our implementation of the Chen and Yu method is not fully functional yet. We need to review the feature extraction phase in order to achieve better results. In our experiments, it achieved at most 89.52%, while the authors reported an accuracy of 99.70% in their work.
Statistical Measurement
Minhas and Arif
Yu Chen
and 99.0 Our experiments for the Minhas and Arif method and for the Yu and Chen methods were successful on the PC and on the mobile phone, achieving an accuracy of 99.0% and 98.67%, respectively.
Due to the heavy computations needed by the classification phase of the PNN and the KNN, the mobile phone needed too much time to classify each beat. For the Yu and Chen method, the PNN classifier needs to compute the PDF for each of the 11,600 neurons from the Pattern Layer, perform the summation and chose the desired class. The selected mobile phone (Motorola Milestone A853) took an average of 623ms to perform this task for each beat. The classifier used by the Minhas and Arif method is the KNN, a classifier that is similar to the PNN, however, instead of finding the PDF for each neuron, it needs to compute the distance of the beat to each other beat from the training set and select the class of the closest class to be the target class of the beat. The average time taken to classify each beat with this method was 573ms.
On an implementation that targets the monitoring of real patients, the CPU will also be busy acquiring and decoding the patient’s signal from the electrocardiographer, detecting the QRS complexes to find the bounds of each beat and extracting the features from the beat. As a result, all these operations, together with the classification phase, can take more than 800ms to be completed for each beat. A traditional heart rate of 75bpm will generate 1 beat each 800ms, in other words, on the selected phone, these methods would not be able to monitor patients with heart rates higher than 75bpm, turning their use impracticable in a real system.
In contrast to them, the Chen and Yu method could be able to classify each beat in a small time. Due the nature of the MLP classifier, that just needs to propagate the inputs through the network to find the target class, it achieved an average of 27ms to classify each beat. However, as we have already mentioned, our implementation of the method still needs to be reviewed in order to achieve the accuracy reported on the author’s paper.
In this paper, we presented a comparison study of ECG beat classification methods destined to detect arrhythmias running in a mobile phone. This study was motivated by the need for a rapid response for the analysis of the exams in some critical situations. Thus, our main objective was to point one or more methods that can successfully classify ECG beats on a mobile phone, with high accuracy fast response.
Relying on the specialized literature, we selected three methods from the authors that reported the higher accuracies together with high sensitivities, namely: Chen and Yu method, Minhas and Arif method and Yu and Chen method.
As we reported in Section 4, our implementation of the Chen and Yu method is not fully completed yet. By now, it achieves at most an accuracy of 89.52%. On the other hand, our implementation of both the Yu and Chen method, and the Minhas and Arif method were successful for both the PC and the mobile phone, achieving accuracies of 98.67% and 99.00%. This performance could be observed in both implementations, for the PC and for the mobile phone. However, these two methods, when running in the mobile phone were too slow to classify the beats. Both of them need more than 500ms. This is indeed a problem, since normal heart beat rates generate more than one beat per second, and fast heart rates will generate more than one beat per 500ms. Thus, both algorithms would not be able to process all beats when running in a cell phone, at least in our implementation.
To overcome the performance limitations found in our study so far, we will focus on the implementation of the Chen and Yu method in order to be able to test it in a mobile phone. Since the MultiLayer Perceptron’s classification phase is not instance-based, it is not costly in terms of CPU and memory usage. If we fail to fix our implementation of the Chen and Yu method, we’ll try to develop a novel ECG beat classification method to run with acceptable performance in a cell phone implementation. The new method will have to combine a fast classification algorithm with a feature set that provides better results. http://www.who.int/entity/healthinfo/statistics/bodgbd deathdalyestimates.xls.