 Open Access
 Total Downloads : 591
 Authors : Ms. Anaya A. Dange, Prof. Swarali P. Sheth, Prof. Dr. S. L. Nalbalwar
 Paper ID : IJERTV3IS050578
 Volume & Issue : Volume 03, Issue 05 (May 2014)
 Published (First Online): 20052014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Detection of Qrs Complexes in Ecg Signal Using KMeans 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 nonQRSregions in the ECG signal, K means algorithm is used. The performance of the algorithm is validated using MITBIH Database. The efficiency of QRS detection is evaluated based on two parameters namely sensitivity and detection rate.
Keywords ECG, MITBIH database, KMeans algorithm, detection rate
Fig 1.An ECG signal

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 MITBIH 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 QRScomplexes 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, QRSdetection 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.

KMEANS ALGORITHM
This section describes an outline of Kmeans 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, Kmeans 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 Kmeans 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 Kmeans 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.

MITBIH ARRYTHMIA DATABASE
In this paper, ECG signals are taken from MITBIH 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 twochannel ambulatory ECG recordings, obtained from 47 subjects studied at the laboratories of Beth Israel Hospital. The 360 samples per second digitized recordings have 11bit 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 analogtodigital converter (ADC) saturation and for antialiasing, 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 bandpassfiltered 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 batterypowered, 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.

IMPLEMENTATION OF QRS DETECTION
METHOD
This section consists of two sub sections namely implementation of digital filters (IVA) and implementation of kmeans algorithm (IVB). Sub section IVA describes the implementation of digital filters whereas sub section IV B describes the implementation of KMeans algorithm.
IVA. 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 MITBIH 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 cutoff 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.
IVB. IMPLEMENTATION OF KMEANS
ALGORITHM
Ths section implements an algorithm developed for the detection and delineation of QRScomplexes 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 QRScomplex. 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 QRSregion 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 Kmeans algorithm as described in section 2 are followed in order to find the two cluster centers namely the QRScluster center and the non QRScluster center.
Step 3: After finding two cluster centers using Kmeans 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 QRScluster and output is 0 if it belongs to a nonQRScluster. Thus, a continuous train of 1s is obtained in the QRSregion and 0s is obtained in the nonQRS region. Fig. 3 shows the output of KMeans algorithm. It is seen that, Kmeans algorithm not only detects the QRS complexes of ECG, but also delineate them accurately.
Fig 2.Steps involved in kmeans 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 Kmeans algorithm

RESULTS AND DISCUSSIONS
Detection is said to be true positive (TP) if the algorithm correctly identifies the QRScomplex 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 QRSwave is detected as a QRScomplex.
The ECG signals used for analysis and detection in this work are a part of MITBIH Arrhythmia Database given on the website of MITBIH [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

CONCLUSION
Kmeans clustering algorithm is implemented and simulated in this paper using MATLAB. It is observed that this algorithm simultaneously detects and delineates the QRScomplexes 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 MITBIH 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

Sweta abrahim, Anita Titus QRS Based Arrhythmia Classification Using KNN Architecture IJREAT International Journal of Research in Engineering & Advanced Technology, Volume 1, Issue 3, JuneJuly, 2013.

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.

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

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

SS Mehta, DA Shete, NS Lingayat & VS Chouhan Kmeans algorithm for the detection and delineation of QRScomplexes in Electrocardiogram, IRBM, 2009.

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

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

J.PAN & W. J.TOMPKINS, A real time QRS detection algorithm,
IEEE Trans., BME, vol. 32, pp. 230236, 1985.

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

Leif Sornmo, & Pablo Laguna, Electrocardiogram (ECG) Signal Processing. Wiley Encyclopedia of Biomedical Engineering, 2006 John Wiley & Sons, Inc., pp116

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,pp35665.

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

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 454995, 1998.

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

S. S. Mehta and N. S. Lingayat SVMbased algorithm for recognition of QRS complexes in Electrocardiogram, ITBMRBM (2008), doi:10.1016/j.rbmret.2008.03.006

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

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, pp125132.

J. M. Bland, D. G., Altman, Statisticl Methods for assessing agreement between two methods of clinical Measurement ,
Lancet,pp. 307310, 1986

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. 8598, 1990.