Detection of Qrs Complexes in Ecg Signal Using K-Means Algorithm

Detection of Qrs Complexes in Ecg Signal Using K-Means Algorithm

Ms. Anaya A. Dange

M Tech Student

Prof. Dr. S. L. Nalbalwar

Prof. & Head

Prof. Swarali P. Sheth

Assistant Professor

Department of Electronics & Telecommunication Engineering, Dr. B. A. T. U. Lonere, M.S., India

Abstract: This paper implements a simple method using K- means clustering algorithm for the detection of QRS- complexes in ECG signal. Butterworth digital filters are designed and implemented to remove the power line interference and baseline wander present in the ECG signal. To detect QRS and non-QRS-regions in the ECG signal, K- means algorithm is used. The performance of the algorithm is validated using MIT-BIH Database. The efficiency of QRS detection is evaluated based on two parameters namely sensitivity and detection rate.

Keywords ECG, MIT-BIH database, K-Means algorithm, detection rate

Fig 1.An ECG signal

1. INTRODUCTION

   Electrocardiogram (ECG) signals are used to analyze the cardiovascular activity in the human body and have a primary role in the diagnosis of several heart diseases. The QRS complex is the most important and distinguishable component in the ECG because of its spiked nature and high amplitude. Since it reflects the electrical activity within the heart during the ventricular contraction, the time of its occurrence as well as its shape provides much information about the current state of heart. The ECG recordings in MIT-BIH Database[4] may contain various challenging problems such as segment with high noise content, sudden change in QRS amplitude and morphology, or muscle and electrode artifacts which are not often detected correctly. Hence reliable and correct detection of QRS complexes, under various backgrounds, is very important in any algorithm used for ECG analysis. The correct performance of these systems depends on several important factors such as quality of ECG signal, the applied detection rule, the learning and testing dataset used. Once the positions of the QRS-complexes are found, the locations of other components of ECG like P, T waves and ST segment, etc. are found relative to the position of QRS, in order to analyze the complete cardiac period. In this sense, QRS-detection provides the fundamental for almost all automated ECG analysis algorithms. Mostly QRS detectors consist of two stages: preprocessing stage, including linear filtering followed by nonlinear transformation and decision rule[7].Automatic detection and delineation of the QRS complex in ECG is of extreme importance for computer aided diagnosis of cardiac disorder. The aim of the present work is to detect the QRS wave from electrocardiogram (ECG) signals.

2. K-MEANS ALGORITHM

   This section describes an outline of K-means algorithm used for the generation of feature signal[3]. When a number of samples are given and it is required to group them into K number of clusters, K-means algorithm can be used. It is based on the minimization of performance index, which is defined as the sum of squared distances from all points in a cluster domain to the cluster center. The various procedural steps of the K-means algorithm[3] are as follows.

   Step 1: Choose initially K cluster centers Z1(1), Z2(1). .

   .Zk(1). These are arbitrary and are usually selected as the first K samples of the given samples set X and Zl+1(1) Zl(1), for l = 1, 2,. . ., K1.

   Step 2: At the kth iterative step, distribute the samples X among the K cluster domain, using the following relation.

   X Sj(k) if ||X Zj(k)|| < ||X Zi(k)|| (1)

   For all i = 1, 2,. . ., K, i j, where Sj(k) denotes the set of samples whose cluster center is Zj(k).

   Step 3: from the results of step 2, compute the new cluster centers Zj(k + 1), j =1,2,. . .,K, such that the sum of the squared distances from all the points in Sj(k) to the new cluster center is minimized. In other words, the new center Zj(k + 1) is computed so that the performance index,

   Jj = ||X Zj (k + 1)||2

   X Sj (k)

   j = 1, 2, . . . , K is minimized. (2)

   The Zj(k + 1), which minimizes this performance index is simply the sample mean of Sj(k). Therefore, the new cluster

   center is given by,

   Zj(k + 1) = 1÷Nj X, j = 1, 2, . . . , K (3)

   X Sj (k)

   where, Nj is the number of samples in Sj(k). The name K means is obviously derived from the manner in which cluster are sequentially updated.

   Step 4: if Zj(k + 1) = Zj(k) for j=1, 2,. . ., K, the algorithm has converged and the procedure is terminated. The behavior of K-means algorithm is influenced by the number of cluster centers specified, the choice of initial cluster, the order in which the sample are taken and the geometrical properties of data.

3. MIT-BIH ARRYTHMIA DATABASE

   In this paper, ECG signals are taken from MIT-BIH database for QRS detection and arrhythmia classification. MIT (Massachusetts Institute of Technology) and Beth Israel Hospital (now the Beth Israel Deaconess Medical Center) have together put forward this database[4]. This was formed from 48 half an hour excerpts of two-channel ambulatory ECG recordings, obtained from 47 subjects studied at the laboratories of Beth Israel Hospital. The 360 samples per second digitized recordings have 11-bit resolution over a 10 mV range. In this paper recordings of 10 seconds duration have taken.

   The analog outputs of the playback unit were filtered to limit analog-to-digital converter (ADC) saturation and for anti-aliasing, using a passband from 0.1 to 100 Hz relative to real time, well beyond the lowest and highest frequencies recoverable from the recordings. The bandpass-filtered signals were digitized at 360 Hz per signal relative to real time using hardware constructed at the MIT Biomedical Engineering Center and at the BIH Biomedical Engineering Laboratory. The sampling frequency was chosen to facilitate implementations of 60 Hz (mains frequency) digital notch filters in arrhythmia detectors. Since the recorders were battery-powered, most of the 60 Hz noise present in the database arose during playback. In those records that were digitized at twice real time, this noise appears at 30 Hz (and multiples of 30 Hz) relative to real time.

4. IMPLEMENTATION OF QRS DETECTION

   METHOD

   This section consists of two sub sections namely implementation of digital filters (IV-A) and implementation of k-means algorithm (IV-B). Sub section IV-A describes the implementation of digital filters whereas sub section IV- B describes the implementation of K-Means algorithm.

   IV-A. IMPLEMENTATION OF DIGITAL

   FILTERS

   This subsection describes filter design and implementation required for removal of power line interference and baseline wander. A raw ECG signal from MIT-BIH database is selected. Fig. 2(a) shows raw ECG signal selected from database (Record No. 101). As we know that this ECG signal is often contaminated by power line interference of 60 Hz, therefore to get rid of this interference, a Butterworth digital notch filter of 60 Hz frequency is designed and implemented in MATLAB. The output of notch filter is shown in Fig. 2(b).

   To get rid of baseline wander which is generally found in the range of 0 to 0.5 Hz, a digital low pass Butterworth filter of cut-off frequency 0.5 Hz is designed and implemented in MATLAB. The output of notch filter (Fig. 2(b)) is further passed through this low pass digital Butterworth filter to remove the baseline wander. Fig. 2(c) displays the resultant signal after removal of baseline drift.

   IV-B. IMPLEMENTATION OF K-MEANS

   ALGORITHM

   Ths section implements an algorithm developed for the detection and delineation of QRS-complexes in single lead ECG signal.

   Step1: The absolute slope i.e. absolute value of the difference between two consecutive samples is calculated to enhance the signal in the region of QRS-complex. The absolute value of slope of the ECG signal is used as an important discriminating feature because absolute slope of the signal is much more in the QRS-region than in the rest of the region. Fig. 2(d) shows the absolute slope of the filtered ECG signal. To enhance this absolute slope this paper uses moving average criteria. Due to this it is observed that the smoother version of QRS complex is obtained, which is shown in Fig. 2(e).

   These absolute slope values are then normalized to reduce the burden of the classifier to form the complicated decision boundary.

   Step 2: The various steps of K-means algorithm as described in section 2 are followed in order to find the two cluster centers namely the QRS-cluster center and the non- QRS-cluster center.

   Step 3: After finding two cluster centers using K-means algorithm, the slope curve shown in Fig. 2(e) is scanned. The membership of slope, at a given sampling instant, is found. An output is 1 if a sample belongs to a QRS-cluster and output is 0 if it belongs to a non-QRS-cluster. Thus, a continuous train of 1s is obtained in the QRS-region and 0s is obtained in the non-QRS region. Fig. 3 shows the output of K-Means algorithm. It is seen that, K-means algorithm not only detects the QRS complexes of ECG, but also delineate them accurately.

   Fig 2.Steps involved in k-means algorithm: (a) raw ECG signal, (b) notch filtered ECG signal, (c)baseline wonder removed ECG signal (d) absolute slope curve,

   (e) QRS enhanced signal (f) normalized signal

   Fig 3. Output of K-means algorithm

5. RESULTS AND DISCUSSIONS

   Detection is said to be true positive (TP) if the algorithm correctly identifies the QRS-complex and it is said to be false negative (FN) if the algorithm fails to detect the QRS- complex. False positive (FP) detections are obtained if non- QRS-wave is detected as a QRS-complex.

   The ECG signals used for analysis and detection in this work are a part of MIT-BIH Arrhythmia Database given on the website of MIT-BIH [4].

   The said algorithm is applied on total of 48 records from database. It is observed that, in the case of normal beats (i.e. for Record numbers 100, 101, 102, 103, 104, 105, 106, 107,

   112, 113, 115, 117, 119, 121, 122, 123, 201, 202, 209, 212,

   213, 215, 217, 219, 220, 221, 222, 223, 228, 230, 231, 232,

   234) and right bundle branch block (i.e. for record numbers 118,124), the results are encouraging and almost all the beats were detected successfully. Similarly, in the case of left bundle branch block also (i.e. for record numbers 111, 207, 214), the total number of complexes detected are accurate and percentage range of Se and P+ is satisfactory.

   As the algorithm has been implemented in MATLAB working environment, therefore the part of the whole signal of each data set has been operated.

   In order to evaluate the accuracy of detection of QRS complex, two essential parameters: sensitivity Se and the positive predictivity P+ (detection rate), are used. These parameters describe the overall performance of the detector and their values are calculated as follows:

   Se = TP / (TP + FN) P+ = TP / (TP + FP)

   Using these expressions, the average detection rate obtained for all 48 records is 97% also the percentage of false positive detection and false negative detection for all records are 4.06% and 0.00% respectively, as listed in Table 1.

   Therefore, from the table, it is observed that, the results obtained (listed in Table1) from the implemented algorithm provide satisfying accuracy level.

   Out of analysed 48 records, for record numbers 109, 200, 203, 210 and 233 it is seen that, the predictivity is not 100% and instances of False Positive detection are seen. This may be because of slope of non QRS regions of these five ECG records falling in the range of absolute slope values chosen for detection of QRS region.

   Table 1: QRS detected in ECG signal

6. CONCLUSION

K-means clustering algorithm is implemented and simulated in this paper using MATLAB. It is observed that this algorithm simultaneously detects and delineates the QRS-complexes present in the ECG signal. This paper also designs and implements digital notch and low pass Butterworth filters required for removal of power line interference and baseline wander respectively. A detection rate of 97% is obtained for MIT-BIH database[4], which seems to be significant. It is observed that the information

obtained through this algorithm is very useful for ECG classification and diagnosis. It is also possible to extend this method for automatic ECG signal analysis and diagnosis.

REFERENCES

1. Sweta abrahim, Anita Titus QRS Based Arrhythmia Classification Using K-NN Architecture IJREAT International Journal of Research in Engineering & Advanced Technology, Volume 1, Issue 3, June-July, 2013.

2. Ida Laila binti Ahmad, Masnani binti Mohamed, Norul Ain binti Ab Ghani Development of a Concept Demonstrator for QRS Complex Detection using Combined Algorithms, 2012 IEEE EMBS International Conference on Biomedical Engineering and Sciences | Langkawi | 17th – 19th December 2012.

3. S. S. Mehta and Swati Sharma & N.S.Lingayat Development of FCM based algorithm for the delineation of QRS-complexes in Electrocardiogram 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009).

4. www.physionet.org/physiobank/database/mitdb MIT Database.

5. SS Mehta, DA Shete, NS Lingayat & VS Chouhan K-means algorithm for the detection and delineation of QRS-complexes in Electrocardiogram, IRBM, 2009.

6. B.U. Kohler, C. Hennig, and R. Orglmeister, The principles of software QRS detection, IEEE Eng Biol. Mag, vol. 21, pp. 4257, 2002.

7. F. Gritzali, Towards a generalized scheme for QRS Detection in ECG waveforms, in Signal Processing, vol. 15, 1988, pp. 183-192.

8. J.PAN & W. J.TOMPKINS, A real time QRS detection algorithm,

   IEEE Trans., BME, vol. 32, pp. 230-236, 1985.

9. Matlab help, MATLAB MATHWORKS. http://www.mathworks.com

10. Leif Sornmo, & Pablo Laguna, Electrocardiogram (ECG) Signal Processing. Wiley Encyclopedia of Biomedical Engineering, 2006 John Wiley & Sons, Inc., pp-1-16

11. Mahesh S. Chavan, R. A. Aggarwala, M. D. Uplane, Suppression Of Baseline Wander And Power Line Interference in ECG Using Digital IIR Filter, International Journal of Circuits, Systems And Signal Processing, Issue 2, Volume 2, 2008,pp-356-65.

12. I.S.N. MURTHY & G.S.S. DURRGA PRASAD, Analysis of ECG from Pole-Zero models, IEEE transaction on biomedical engineering, vol. 39, N° 7, 1992.

13. N.E. Huang, Z.Shen, S.R. Long, M.C. Wu, H.H. Shih, Q.Zheng,

    N.C. Yen, C.C. Tung and H.H. Liu, The empirical mode decomposition and the Hilbert spectrum for nonlinear and non stationary time series analysis, Proceedings of the Royal Society of London, pp 454-995, 1998.

14. Lisette P. Harting et al., On Baseline drift Suppressing In ECG Recordings, Proceedings of the 2004 IEEE Benelux Signal Processing Symposium, pp133-136

15. S. S. Mehta and N. S. Lingayat SVM-based algorithm for recognition of QRS complexes in Electrocardiogram, ITBM-RBM (2008), doi:10.1016/j.rbmret.2008.03.006

16. P. E. Trahanias, An approach to QRS complex detection using mathematical morphology, IEEE Trans. Biomed. Eng., vol . 40, pp.201-205, 1993.

17. G Vijaya, V. Kumar, and H. K. Verma, Artificial Neural Network Based Wave Complex Detection in Electrocardiograms, Int. J. of System Science, vol. 28, 1997, pp125-132.

18. J. M. Bland, D. G., Altman, Statisticl Methods for assessing agreement between two methods of clinical Measurement ,

    Lancet,pp. 307-310, 1986

19. G. M. Friesen, T. C. Jannett, M. A. Jadallah, S. L. Yates, S. R. Quint, and H. T. Nagle, A Comparison of noise sensitivity of nine QRS detection algorithms, IEEE trans on Biomed. Engg.vol. 37, pp. 85-98, 1990.