{'fraction_non_alphanumeric': 0.031059226732355148, 'fraction_numerical': 0.01028167505622791, 'mean_word_length': 4.7853159851301115, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ECG Beat Classification using a Sliding Window and Correlation of the Three-bit Linear Prediction Error Signal

Sudden cardiac arrest (SCA) is responsible for half of all deaths due to heart disease. Most SCAs could be avoided by obtaining an early diagnosis from ECG recordings. The long-term monitoring systems record a large number of beats and require automatic detection and classification of the premature ventricular contraction (PVC) beats. Several ECG beat classification algorithms based on different methodologies have been developed and implemented. This paper presents a novel algorithm for automatic recognition of a premature ventricular contraction (PVC) beat based on a three-bit linear prediction error signal (LPES). The algorithm is composed of three main stages: signal denoising and QRS detection; nonlinear transformation of the linear prediction error signal e(n); and a sliding window. The proposed algorithm was tested using ECG signals from two recognized arrhythmia databases, MIT-BIH and AHA. The selected signals contained normal beats as well as abnormal beats. Sensitivity and specificity parameters were used to measure the accuracy of the proposed classifier. The sensitivity achieved using the proposed algorithm was 96.3% and the specificity was 99.0%. In addition to its accuracy, the main advantages of using the proposed algorithm are its simplicity and robustness. Key-Words: ECG, QRS detection, Signal processing, PVC recognition, Linear Prediction, LPES, Sliding Window, Autocorrelation. Received: August 22, 2019. Revised: January 3, 2020. Accepted: January 10, 2020. Published: January 31, 2020.


Introduction
A recorded ECG signal arises from the activities of the myocardium (heart muscle). The signal consists of three main waves, referred to as P, QRS complex and T waves, where the P wave represents the depolarisation of the atrium, the QRS complex wave represents the ventricular depolarisation and the T wave reflects repolarisation of the ventricles. The contraction and expansion process of the myocardium normally starts after receipt of a trigger signal from the sinoatrial (SA) node, which serves as an internal pacemaker. However, the heartbeat can also be initiated by the Purkinje fibres rather than by the SA node. This initiation causes ventricle contraction without a prior atrium contraction, and the resulting beat is called premature ventricular contraction (PVC). A single PVC beat does not usually pose a danger; however, frequent or consecutive PVC beats may be an indication of a heart malfunction that can lead to sudden cardiac arrest (SCA) and sudden death.
SCA is one of the main causes of natural death: in the USA, as about 325,000 adults die of SCA each year. SCA is responsible for half of all deaths due to heart disease [1], so the detection of PVC beats is critical in clinical cardiology [2]. Indeed, most SCAs could be avoided by obtaining an early diagnosis from ECG recordings. However, some heart disorders cannot be detected by analysing short ECG recordings and require long-term recording for diagnosis. The purpose of long-term recording (normally 24 hours) is to observe the heart function while the patients perform their daily activities and is known as ambulatory, or Holter, monitoring. The PVC beats can easily be recognised by eye on recorded ECG signals, because they are very different from normal heart beats. However, longer-term monitoring systems, such as Holter monitoring, record a large number of beats and demand automatic detection and classification.
In the last few decades, several ECG beat classification algorithms based on different methodologies for ECG beat classification have been developed and implemented. For example, Chiu et al. [3] used correlation coefficients to recognise PVC beats, whereas Al-Shrouf [4] and Martis et al. [5] used wavelet transform and neural networks for ECG beat classification. Javadi et al. [2] used a combination of neural networks and expert systems to distinguish between normal beats and PVC beats, whereas Das and Ari [6] proposed a combination of S-transform and wavelet transforms for classifying normal heartbeats, PVC arrhythmias and other abnormalities of the heart. Nikan et al. [7] applied pattern recognition for ECG arrhythmia classification, and Chen et al. [8] used a combination of projected and dynamic features for heartbeat classification. Elhaj et al. [9] used combined linear and nonlinear features of the ECG signals for arrhythmia recognition and classification. Surveys of heartbeat classifications for arrhythmia detection have been published [10], [11]. In the present paper, ECG beat classification is performed using a sliding window and the three-bit linear prediction error signal (LPES).
The next sections introduce the linear prediction and the sliding window. The proposed method was detailed and the results and discussion was presented.

Linear Prediction
Linear prediction is one of the essential tools used in the digital signal processing field. It is the process whereby we attempt to predict the value of a sample x(n) using a linear combination of N previous samples [12]. Let x(n) be a wide sense stationary (WSS) real random process. The estimated (predicted) value is a linear combination of p samples and has the form where p is an integer value called the prediction order, and a(k) are prediction coefficients k = 1,2,…,P The estimation error, called the linear prediction error signal, is The prediction error signal should have a minimum value "in the sense of a mean square". The mean square of the error signal is denoted as: The expected value for the square error signal is ( ) Prewriting equation ( 1) in vector form : is a vector of P-past samples, and and the autocorrelation matrix as: Using equations (9) and (10), equation (8) (11) Equation (11) is a quadratic function of the prediction coefficient vector a . The optimum predictor coefficients vector is the one that minimises this mean squared value. The gradient of equation (11) is Equalising the gradient in equation (12) to zero gives the necessary condition to get minimum values of This gives the following normal linear equation r Ra = (14) We define R(k) to be the autocorrelation function of the real WSS process x(n), that is we can rewrite equation (14) as The autocorrelation matrix is a Toeplitz matrix, so the normal equation (15) could be solved using the Durbin recursive procedure, which is the most efficient method for solving this type of equation. The other issue is the choice of the predictor order P. The choice of the predictor order value depends on the purpose of the prediction process. For example, Frankiewich and Al-Shrouf [19] proved that the second order prediction (p = 2) is sufficient for ECG signal classification, whereas the third order is used for ECG data compression. However, the highest value of parameter p is required for system identification. Based on the work of Frankiewich and Al-Shrouf, the second order prediction (p=2) is used for ECG beat classification in the present study.

Siding Window
In each movement, the sliding window moves L time steps. Consequently, the number of subsequences, M, is The values of the parameters L and q s hould be chosen based on the application to which the sliding window is applied. Using a low value for r (e.g. L= 1) guarantees that no abnormal subsignals are missed, but the consequence of a high number of subsignals is greater time consumption. Conversely, using a high value for r (e.g., L=q) generates a lower number of subsignals and, despite the lower processing time, a risk remains of losing some anomalous subsignals. A trade-off between accuracy and processing time can be considered. The length q of the sliding window is an important parameter that should be selected based on the application purpose. Selecting a value of r as proportional to the length of subsignals is a reasonable choice, i.e. a higher value of r is selected for longer subsignals and a lower value of r for shorter subsignals.
The present study considers the MIT-BIH and AHA arrhythmia data for shape anomaly detection. The MIT-BIH data set is composed of 48 half-hour annotated ECG signals. Four signals comprising some visible anomalies were selected from the ECG signals in this data set. The processing time is reduced by resampling the signal from MIT-BIH from 360 Hz to 180 Hz; however, the AHA signals are resampled from 250 Hz to 125 Hz. The length of the sliding window was set to around 1.2 times the average length of the RR peaks to ensure that longer beats (e.g. PVC) can be incorporated into one subsequence. Moreover, the sliding window moves around 5% of the length of subsequences in each movement. After generating the subsequences, normalisation is employed and each subsequence is represented using its autocorrelation coefficients.

Methods
The proposed automated classification system is depicted in Figure 1. I t starts with different preprocessing procedures, followed by linear prediction and linear transformation; the last stage is calculation of the correlation coefficient and decision making. The work concerning each part is explained in detail in the following sections.

Pre-processing
During recording, the ECG signal is usually disrupted by one or more kinds of noise or artefacts, such as: power-line interference, baseline drift, electrode motion artefact, data-collecting device noise and electromyogram (EMG) noise due to motion artefacts and muscle contraction [14], [15]. EMG noise is the factors that most severely affects the value of the ECG signal. The existence of any kind of noise on t he ECG signal reduces the accuracy of QRS detection and/or ECG beat classification; therefore, the precision of the diagnosis of cardiovascular disease will be decreased. To avoid this, noise should be eliminated.

Denoising
A second order error predictor could be treated as a finite impulse response filter (FIR) with transfer function H(z).
After calculating the optimal parameters a(1) and a(2) for several normal and abnormal ECG beats, the frequency response is tested and shows that the prediction error filter possesses a h igh pass filter characteristic. The magnitude response of the predictor filter for both normal and abnormal ECG cases is illustrated in figure 2.

Fig.2. Magnitude response of the second order predictor
Since the second order error predictor of the ECG signal serves as a high-pass filter, the low frequency noises have no effect on it; therefore, no high-pass filter is required. The only filter needed is a low-pass filter. In the present work, the ECG signal is passed through a low-pass filter with a cutoff frequency of 45 Hz, because the information above 45 Hz is not important for either the QRS or arrhythmia detection.

QRS-complex Detection
QRS detection is performed using the algorithm proposed by Pan-Tompkins [16]. The Pan-Tompkins detector is the best known QRS detector. The algorithm consists of several stages: bandpass filtering with a centre frequency of 17 Hz, which is the estimated frequency of the QSR complex; a derivative filter to focus the high slopes; a nonlinear operation which focuses on the higher values that are mainly present because of the QRS complexes; and a moving average filter. The resulting signal is called the detection function (DF), which should possess a sm ooth peak in each ECG cycle corresponding to each QRS complex. To find the nth local maximum point, an adaptive threshold is determined, as follows: where Th n is the nth threshold and max (DF n−1 ) is the local maximum of the detection function corresponding to the previous beat. The first local maximum is defined as the maximum point during the first two seconds. The efficiency of the detector is increased by adopting two strategies: the search back strategy (SBS) and the turn off strategy (TOS). The SBS is used to avoid missing any lowamplitude QRS, and involves reducing the threshold value and restarting the search for the local maximum. The SBS is activated if the RR interval exceeds a specified time: this time is two seconds in the proposed QRS detector. The TOS is used to reduce the computation time and is achieved by halting the search for the local maximum for 0.2 seconds.

Segmentation
After detection of the QRS complex and localisation of the R peak, 50 samples are chosen from the left side of the R peak and 50 samples after it, to give a segment or beat of 101 samples.

Three bit (five level) Error Signal
Instead of the ECG itself, the beat classification puts an emphasis on the five level signal T(n). This signal is obtained from a nonlinear transformation of the second order linear prediction error, which transforms the prediction error signal to a set of five state pulse code trains relative to the original ECG signal, based on the following transformation (19)  where E is the energy of the prediction error signal for given segment of a tested ECG beat. Each sample of the T(n) pulse can be written in a three bit word length (110, 101, 000, 001 and 010). The main advantage of the above transformation is that it can be implemented in a r eal time automated ECG classification. Figures 3 & 4 s how normal and abnormal ECG beats, their prediction error signals and their corresponding three bit signal T(n) taken from two different ECG records: N12 and V72 respectively.

Application of the Sliding Window
In this paper, a sliding window is applied to the T(n) signal to detect abnormal ECG beats, namely, PVC beats. The sliding window parameters should be chosen to guarantee coverage of the QRS complex in each ECG beat. We fulfil this requirement, in this paper, by choosing a length of the sliding window q = 0.20 sec and a value for step L = 0.05 sec.

Correlation based Classification
Detection of abnormality in ECG signals in the time domain is mainly based on two objectives: detection of anomalies in the signal amplitude and detection of anomalies in the signal shape.
For detecting anomalies in the signal amplitude, the Euclidean distance can be considered as a suitable similarity measure and the generated subsequences can be employed in classification process without any further preprocessing. Conversely, when detecting anomalies in shape is of concern, the generated subsequences cannot be employed directly. The reason is that the generated subsequences are not synchronised, so using the Euclidean distance function is not efficient as a similarity measure.
In this paper, we confine the recognition of the abnormal signals to their shapes, so we eliminate the amplitude objective. The reason is that the amplitude aspect dominates in the five-level signal T(n). The signals, based on their shape information, are compared by representing each subsequence using a set of cross-correlation coefficients between the template beats and the tested one. The template beats are considered as a T(n) sequence of a normal ECG beat, as well as the T(n) sequence of the PVC beat. Considering x k as a subsequence with length q, its cross-correlation coefficient for lag s c an be calculated using (20). In fact, the cross-correlation coefficient gives an estimation of how well the tested signal or its timeshifted version matches the template. As a result of considering different values of time shifting (s = 1,2,...,q -1), each subsignal is represented with two q-1 dimension cross-correlation coefficient vectors (V n & V ab ), where these vectors represent the cross correlation between the normal and abnormal templates, respectively. The tested beat is classified as normal if max[max(V n )] ≥ max[max(V ab )] otherwise, beat is classified as PVC beat.

Results and Discussion
The ECG signals from the AHA and MIT-BIH databases were used to examine the applicability and efficiency of the proposed PVC classification algorithm. The results obtained were compared with the results from the study by Awandekar et al. [17] and the results obtained by Al-Shrouf [18]. A meaningful comparison was achieved by using the same two performance parameters: sensitivity and specificity. Sensitivity measures the accuracy of detecting the PVC beats, while specificity represents the accuracy of rejecting normal beats as non-PVC beats. The sensitivity parameter S e is calculated using the following equation: The specificity parameter S p is calculated as follows: and are true positive, false negative and false positive, respectively. True positive is the number of true classified PVC beats, false negative is the number of PVC beats not classified as PVC beats and false positive is the number of non-PVC beats that are classified as PVC beats. The results of the PVC classification testing are shown in Table 1. The results obtained by Awandekar et al. [17] were S e = 96.2% and S p = 93.6%. However they did not mention which ECG records they used or the number of beats they considered. In this paper, the testing data were the same data used by Al-Shrouf [18]. We achieved a sensitivity of 96.3% and a specificity of 99.0%, whereas Al-Shrouf achieved 97.4% and 99.1% for sensitivity and specificity, respectively. The more accurate results obtained by Al-Shrouf may be caused by the number of features, so future work will integrate the present method and the method in [18] to achieve a m ore accurate classifier.

Conclusion
This paper proposes a new concept of ECG beat classification to recognise PVC beats. The introduced classification algorithm is based on a three bit pulse signal T(n), and a sliding window. A three-level signal is obtained using a nonlinear transformation of the second order linear prediction error signal. However, a sliding window was used to generate a se t of subsignals from the T(n) signal having highest number of unexpected changes in morphology in the QRS region.
PVC beats were recognized by taking the maximum value of the cross-correlation coefficients between the generated subsignals of a tested T(n) signal and the template T(n) signals. Employing the five-level error T(n) signal was simple, effective and robust. Only bit samples of the signal were required, instead of the original signal, which used two bytes for each sample. The proposed algorithm was tested using ECG signals from the MIT-BIH and AHA databases. Six ECG signal records were taken from each database, containing a total of 11,901 beats. The obtained results show that the proposed system can effectively and accurately recognise PVC beats. However, further feature extraction and artificial intelligence techniques should be used to improve the efficiency of the PVC classifier in the future.