Fetal Heart Rate Detection and Data Compression Scheme using Genetic Algorithm and RLE Technique

Fetal Heart Rate Detection and Data Compression Scheme using Genetic Algorithm and RLE Technique

1. Gowri /Assistant Professor Electronics and Communication Engineering

   KSRCE

   Namakkal, India

   S. Bharathi / student Electronics and Communication Engineering

   KSRCE

   Namakkal, India

   Abstract- A heart rate detection and separation framework for the fetal ECG extraction is been proposed, which uses genetic algorithm and wavelet signal analysis technique. The high frequency signal has most important information which is selected by using the wavelet transform. The features of the signal is extracted and then by using genetic algorithm approach the fetal and mother ECG is separated. Linear Predictive coding is the common technique used for QRS detection and compression scheme. Detection of QRS waveform in wearable device helps in the analysis of cardiac health of the patient. For wirelessly transmit the signal, run length encoding technique is used for compression. To recover the original signal run length decoding technique is used. PSNR measurement is used for finding the quality of the ECG signal

   keywordsECG-on-chip; QRS detection; wearable devices; MECG; FECG; Wavelet Transform; Genetic Algorithm; Run Length Encoding.

   1. INTRODUCTION

      An electrocardiogram is a simple, painless test that measure hearts electrical activity. Its also known as an ECG. Every heartbeat is triggered by an electrical signal that starts at the top of your heart and travels to the bottom. Heart problems often affect the electrical activity of your heart. The doctor may recommend an ECG if youre experiencing symptoms or signs that may suggest a heart problem, including:

      • Pain in chest

      • Trouble breathing

      • Feeling tired or weak

      • Pounding, Racing or Fluttering of your heart

      • A feeling that heart is beating unevenly

      An ECG will help to determine the cause of symptoms along with what type of treatment might be necessary. Healthcare spending is increasingly becoming the major contributor of expenditure in many countries. U.S. alone spends roughly 18% of its GDP on healthcare. Cardiovascular diseases are one of the leading causes of the overall expenditure. These expenses are expected to skyrocket in the coming years due to an aging population, as a result of increasing life expectancies. The quality of life in this scenario can be improved by focusing on prevention and early detection of diseases. This can be achieved by proactive and long-term monitoring of individuals cardiovascular health using low-cost wearable Electro Cardio Gram (ECG)

      sensor devices. The main features of the ECG, i.e., the P, Q, R, S, and T points give information about the cardiac health of the person. A wearable ECG sensor, as shown in can be used to acquire, process, and wirelessly transmit ECG signal to a monitoring center. The main challenge involved in the development of the sensor is to make the device low profile, unobtrusive, easy to use with long battery life for continuous usage. A high level of integration with inbuilt signal acquisition and data conversion is required to minimize the size, cost, and power consumption of such a sensor. lossy compression techniques provide higher compression ratios (CR), focus on lossless schemes so as to prevent the possibility of losing any patient information of potential diagnostic value. Also, it is worth noting that lossy compression techniques have not been approved by medical regulatory bodies in most countries and hence cannot be used in commercial devices. A joint approach for QRS detection and ECG compression algorithm for use in wireless sensors.

      1. ECG Waves

         The ECG signal comprises of various waves and these waves are explained given below

         • P wave: The sequential depolarization of the right and left atria

         • QRS complexes: Right and left Ventricular depolarization

         • P Wave: Ventricular Repolarisation

         • U wave: After depolarization in the ventricles.

      TABLE I. Values of ECG Waves

      Waves	Values
      P wave	0.25mv
      R Wave	1.60mv
      Q Wave	0.4mv
      T Wave	0.1mv-0.05mv

      ECG analysis tasks like QRS detection and RR interval estimation locally. This allows the transmission to be triggered only when it is deemed necessary based on cardiac rhythm analysis. Further, the large quantity of ECG data obtained by round the clock monitoring may need to be either stored locally in a flash device or transmitted wirelessly to a

      monitoring gateway for further analysis. The transmission of data incurs high power consumption, and the use of a local storage increases the device cost. The cost is further affected by the need for an on-chip SRAM which is typically used to interface the ECG chip with a microcontroller to support burst transfer.

      QRS detection and data compression, instead of using two distinct approaches. The algorithm lowers the average computational complexity per task by sharing the computational load among two operations. This is done using a shared adaptive linear predictor for performing both ECG beat detection and lossless data compression. In addition, a novel fixed -length data coding-packaging technique. A comprehensive review of existing approaches can be found in

      . However, most of the reported approaches are aimed at increasing the accuracy of detection by using complex signal- processing techniques. For ambulatory devices and sensors, another very important figure of merit is the power consumption. The central idea of the proposed algorithm is to use a single technique for processing of QRS detection and data compression, instead of using two distinct approaches. The algorithm lowers the average computational complexity per task by sharing the computational load among two operations. This is done using a shared adaptive linear predictor for performing both ECG beat detection and lossless data compression.

      The fetal psychological condition depends on the heart rate, which is most related to the mothers cardiogram signal. The Electro Cardiogram represents the electrical activity of the heart which is shown as the heart beat. The ECG records the electrical activity of the heart, where each heart beat is displayed as a series of electrical waves characterized by peaks and valleys. The ECG signal provides two kinds of information, the duration of the electrical wave crossing the heart which in turn decides whether the electrical activity is normal or irregular and the amount of electrical activity passing through the heart muscle which enables to find whether the parts of the heart is proper or not.

      Fig. 1. ECG waveform

      Wavelet transform is a signal processing technique used in various applications to decompose, filter, feature extraction etc.. Wavelet transform has a huge impact in biomedical systems for signal processing. For many signals, the low frequency content is the most important part. It is

      what gives the signal its identity. The high-frequency content, on the other hand, imparts flavour. To gain a better appreciation of this process, it is performed with a one-stage discrete wavelet transform of a signal. The decomposition process can be iterated, with successive approximations being decomposed in turn, so that one signal is broken down into many lower resolution components.

      Genetic algoithm is a common methodology using which the range of values can be fit into a specific function and evaluated using an another function. Using genetic algorithm the ECG signal can be evaluated as whether the signal can be assigned to mother cardiogram or fetal cardiogram. The genetic algorithm can be applied for the separation of signals of ECG as mother and fetal.

   2. JQDC SCHEME

      Several forward prediction-based approaches are used for QRS detection as reported. In these approaches, a forward predictor is used to estimate the current sample of the ECG signal, x (n), from its past m samples. x (n) is the estimate of x(n) and is the predictor coefficient. Upon convergence, the predictor is able to closely estimate the future samples, including the P, T wave segments and the slow baseline variations in the ECG signal.

      (n) (1)

      e (n) instantaneous prediction error , x(n) the predictor coefficient

      (n) the actual sample and its estimate.

      However, for signal regions with steep amplitude variations, like the QRS segment, the predictor statistics are considerably different and hence will result in a higher prediction error represents one of simulation results based on one dataset in the MIT/BIH database. The rest of the datasets show similar characteristics. Therefore, the prediction error can be used as a marker to locate the QRS complex in the ECG signal. Alternatively, the short-term linear predictor can be thought of being capable of predicting the low-frequency portion of the ECG signal, while most of the high-frequency signal content and noise remain in the instantaneous prediction error. With further processing, the QRS complex can be extracted from this high-pass filtered

      In the proposed JQDC scheme, a linear predictor is used to estimate the current sample based on previous m samples. The estimated value is subtracted from the actual sample to calculate the instantaneous prediction error, which after further processing is used for identifying the location of QRS complex. The prediction error is encoded and packaged so as to obtain a compressed lossless representation of the original data for wireless transmission or local storage.

      At the same time, we noticed that linear predictive coding is a main part of lossless data compression techniques for the redundancy reduction between neighboring signal samples. This prompts us to develop a new scheme that jointly performs QRS detection and lossless compression (JQDC) as This way, the computational load of the linear

      predictive coding can be shared between data compression and

      QRS detection. Several factors affect the detection accuracy, CR, and hardware complexity in the proposed joint detection and compression algorithm. In the following, we analyze the effect of linear predictor selection, order of the predictor, and step size.

      Fig. 2. JQDC scheme: Overall block diagram

      1. Adaptive Linear Prediction

         An adaptive predictor is used, so that predictor self-adjusts output based on the incoming signal statistics. Adaptive linear prediction is used in speech coding to remove redundancies from the speech signal. The linear predictor is used to estimate the current sample based on previous m samples. The estimated value is subtracted from the actual sample to calculate the instantaneous prediction error, which after further processing is used for identifying the location of QRS complex. The prediction error is encoded and packaged so as to obtain a compressed lossless representation of the original data for wireless transmission or local storage. Several factors affect the detection accuracy, CR, and hardware complexity in the proposed joint detection and compression algorithm. In the following, the effect of linear predictor selection, order of the predictor, and step size. The predictor is realized by using a tapped-delay line structure. For updating predictor weights, LMS algorithm and its variants were considered. chose Sign Sign Least Mean Square (SSLMS) algorithm as its implementation complexity is the lowest. The different LMS variants yielded comparable results based on simulations using the MIT/BIH database for detection and compression.

         Fig. 3. Adaptive linear predictor

      2. Linear Predictor Order

         The order of linear predictor is highly related to performance of proposed JQDC and hardware cost. It is necessary to analyze the relationship between the order and performance. This was carried out using the ECG signals from the MIT/BIH database, along with SSLMS predictor and initialization methodology mentioned in the next section. Figure shows the QRS detection performance and CR versus predictors order. As expected, the CR improves as the predictor order increases. This is because the predictor could more accurately predict the future data as predictor order increases. The QRS detection performance based on SE and

         +P, on the other hand, shows a different pattern. The performance increases as the order is increased till 4 and started to gradually decline thereafter. As the order increases QRS segment becomes more and more predictable, and hence, the instantaneous error contains less signal component of the QRS complex, which results in a lower detection accuracy.

         Fig. 4. Predictor order versus performance.

      3. Initialization and Step Size

      Adaptive techniques require several cycles to converge to the optimal point based on the incoming signal characteristics. In order to speed up the adaptation, we initialized the SSLMS predictor with pre-computed values

   3. QRS DETECTION

      The instantaneous prediction error, e(n), from the adaptive SSLMS predictor is used for locating the QRS complex. This is because the error corresponding to QRS segment is relatively higher than that of P, T wave and baseline variations. The prediction error also contains high frequency impulse noise, which has to be filtered out so as to easily locate the QRS complex. Typically, moving average filters are effective in removing impulse noises and smoothening of such signals. However in doing so, it also smoothens and distorts the shape and the height of the error peaks corresponding to the QRS complex. It is important to preserve the integrity of the signal content corresponding to QRS, while smoothening the high-frequency and impulse noise that corresponds to the other regions of ECG. To achieve these goals, a SavtizkyGolay (SG) filter is employed to remove the high-frequency impulse noise from the prediction error. Once the impulse noise is removed, the

      signal is further enhanced by using a squaring and moving sum operation for adaptive thresholding and peak detection.

      1. SG Filtering

         SG filters are known well in domains like analytical chemistry and has been of recent interest in ECG signal processing. SG filters smoothen the incoming signal by approximating the signal within a specified window of size L to a polynomial of order K, which best matches the given signal in a least-squares sense .In comparison with a moving average filter, SG filters are beneficial in maintaining the higher order moments in the input signal, as shown in. It preserves features of the distribution such as relative maxima, minima, and width and reduces the smoothening of peak heights, while suppressing the impulse noise. It can be seen from that the noise suppression capability of SG filters is not as good as moving average filter. However, once the impulse noise level relative to the QRS peaks is suppressed, a moving average operation can be used to further smoothen the signal

      2. Signal Enhancement by Squaring and Moving Sum

         Once the high-frequency impulse noise is suppressed, the signal is further enhanced by squaring and taking the moving sum of the signal before the thresholding operation. The instantaneous signal samples are squared, as in (13), to provide a nonlinear amplification to the prediction error, which helps to further magnify the QRS component in the signal relative to the other segment. Furthermore, moving window integration is done to obtain a smooth waveform for thresholding and peak detection.

      3. Adaptive Thresholding and Peak detection

      The enhanced signal, eno(n), is continuously scanned to find QRS peaks. As the signal amplitudes vary across patients and based on external conditions, an adaptive threshold is used for detection. The threshold is initialized with a default value, Thdef in the beginning, and a new threshold is computed based on the maximum value of the signal in a training period of first 2 s, i.e., the threshold is updated to 25% of the maximum value during this period. Every time the signal exceeds the threshold, the peak detection algorithm searches and locates the presence of a peak, Tamp, as described later. The average threshold Thavg is computed as 25% of the average of last four detected peaks,

      Fig. 5. Peak detection.

   4. GENETIC ALGORITHM FOR FETAL HEART RATE DETECTION

      The proposed method has four stages: in the first stage the signal is transformed using wavelet transform to boost the signals, in the second stage extract the features of the electrocardiogram signal, and in the third stage the boosted signals are applied with GA functions to evaluate the signal with the signals of the mother. Finally the fetal ECG is separated from mothers and combined to present the complete fetal ECG.

      Fig. 7. Proposed Block diagram

      1. Wavelet Transform

         The wavelet analysis is applied on the wave form to decompose signals into several frequency bands. The appropriate wavelet and the number of decomposition levels for the analysis of signals using DWT. The number of decomposition level is chosen based on the dominant frequency components of the signal. The levels are chosen such that those parts of the signal that correlate well with the frequencies necessary for classification of the signal are retained in the wavelet coefficients. Since the ECGs have little useful information above frequency 30 Hz of 173.6 Hz, selected 5 different bands and frequency ranges and one approximation range.

         Fig. 8. Raw ECG signal

      2. Feature Extraction

         The electrocardiogram contains various time domain and space domain values; they are amplitudes and intervals of various sectors. Extract P-R interval, R-R interval, Q-T interval, S-T interval, P-wave interval, RS interval and the

         amplitude values of P, R, S, Q, T, U waves. Each features extracted is stored in the data base for further manipulation.

         Fig. 9. ECG Signal Feature Extraction

      3. GA Based Fetal Heart Rates Detection

         The genetic algorithm based separation and fitness function separates the fetal heart electrocardiogram signals from mothers. The GA function has two set of six variables which represent the minimum and maximum values of the features of ECG signal. All the minimum and maximum values are initialized as follows: minPA, maxPA, minQA, maxQA, minRA, maxRA, minSA, maxSA, minTA, maxTA, minUA, maxUA. The GA function selects each signal amplitude which has less amplitude value than the minimum threshold. The amplitude values which are not selected from the fitness function forms the fetal wave form. The GA was seeded with the initial population with approximate mid range of these 6 variables as 2.5, 2.0, 12.0, 1.0, 3.0 2.2. The algorithm will search for optimal location for the signal to be placed and on each iteration; the best candidate location is selected based on the overall fitness value.

         Fig. 10. Mother And Fetal Ecg Extraction

      4. FHR Separation

      Identified P-wave and QRS-wave are grouped to form the Electrocardiogram wave of the fetal and separated from mother ECG. All identified wave forms of the fetal is joined to form the complete wave form to analyze the condition of the fetal for medical investigations

      Fig. 11. Separated Signals

   5. COMPRESSION

      In signal processing, data

      compression involves encoding information using fewer bits than the original representation. Compression can be either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information. In medical field lossless data compression is used because in the lossy compression technique the many of the important data may losed. ECG Data Compression is required to reduce the disk space required to store the data, as ECG is a continuous data taken for a very long interval of time. Also by compressing redundant data from the signal can be removed which actually takes considerably large area in memory. The need of signal transmission over telephone lines or antenna for remote analysis makes the compression and data reconstruction of the signal an important issue in signal processing. ECG is a graphic display of the electrical activity of the heart. Due to low cost and non invasion, ECG signal has been extended for heart disease diagnosis and ambulatory monitoring. For storage and transmission of large signal data, it is necessary to compress the ECG signal data.

      1. Run Length Encoding

         Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.

         Fig. 12. Compressed and Decompressed Signals

      2. Peak Signal to Noise ratio(PSNR)

         PSNR is most commonly used to measure the quality of reconstruction of compression codecs. The signal in this case is the original data, and the noise is the error introduced by compression. When comparing compression codecs, PSNR is an approximation to human perception of reconstruction quality. Although a higher PSNR generally indicates that the reconstruction is of higher quality, in some cases it may not. One has to be extremely careful with the range of validity of this metric; it is only conclusively valid when it is used to compare results from the same codec (or codec type) and same content.

         Fig. 13. PSNR of ECG Signal

   6. CONCLUSION

      The outputs of the extracted signal were recorded on MATLAB. Finally, the fetal ECG signal is extracted and heartbeat of the signal is calculated. The algorithm based on peak detection is proposed and implemented successfully. The performance of the algorithm has been verified successfully on MATLAB and the algorithm is found to be highly efficient. It is found after successful implementation that fetal ECG (FECG) signal can be successfully extracted by using genetic algorithm (GA). The RLE algorithm is implemented by MATLAB codes and hence the RLE algorithm implements compression the signals successfully. R peaks were also detected successfully giving the final heart rate of the signal.

   7. REFERENCES

1. AymanRabee and ImadBarhumi, ECG Signal Classification Using Support Vector Machine Based on Wavelet Multi resolution Analysis, The 11th International conference on Information Sciences, Signal Processing and their Applications 2012.

2. Can Ye, Miguel Tavares Coimbra and B.V.K. Vijaya Kumar, Arrhythmia Detection and Classification using Morphological and Dynamic Features of ECG Signals, 32nd Annual International Conference of the IEEE EMBS Buenos Aires, Argentina, 2010.

3. Chua. E, Fang. W, Mixed bio-signal lossless data compressor for portable brain-heart monitoring systems, IEEE Transactions on Consumer Electronics, vol. 57, no. 1, pp. 267273, 2011.

4. Deepu. C.J, Yong Lian, A Joint QRS Detection and Data Compression Scheme for Wearable Sensors, IEEE Transactions Biomedical Engineering vol. 62, no.1,2015.

5. Jas. A, Ghosh-Dastidar. J,M.-E. Ng, and N. a. A. Touba, An efficient test vector compression scheme using selective Huffman coding, IEEE Transactions Computer

   Aded Design and Integrated Circuits Systems, vol. 22, no. 6, pp. 2003.

6. JIA, W., C. Yang and G. Zhong, Fetal ECG Extraction Based on Adaptive Linear Neural Network, IEEE 3rd International Conference on Biomedical Engineering and Informatics, 2: 899-902, 2010.

7. Jothi, S.H., K.H. Prabha, 2012. Fetal Electrocardiogram Extraction Using Adaptive Neuro-fuzzy Inference Systems and Undecimated Wavelet Transform. IETE J Res., 58: 469-75.

8. Kohler. B.U , Hennig. C and Orglmeister. R, The principles of software QRS detection, IEEE Engineering in Medicine and Biology, vol. 21, no. 1. pp. 4257, 2002.

9. Kumari. G.S, Kuswanth Kumar. S, Anusha. J and M.P.Rao, Electrocardiographic Signal Analysis Using Wavelet

   Transforms, International Conference on Electrical, Electronics, Signals, Communication and Optimization (EESCO) 2015.

10. Martín Clemente Mellado, Fast technique for non invasive fetal ECG extraction, IEEE Transactions on Biomedical Engineering, 58(2): 227- 230, 2011.

11. Moody. G.B and Mark. R.G, The impact of the MIT- BIH Arrhythmia database, IEEE Engineering Medical Biology, vol. 20, no. 3. pp. 45 50,2001.

12. Rigler. S,Bishop. W, and Kennings. A, FPGA-based lossless data compression using Huffman and LZ77 algorithms, in Canadian conference on Electronics and Computer Engineering, pp. 12351238, 2007.

13. Sahin. I, Yilmazer. N, Simaan. M.A, A method for subsample fetal heart rate estimation under noisy conditions, IEEE Transactions Biomedical Engineering, 58(4): 875-883, 2011.

14. Sargolzaei. A, A new method for foetal electrocardiogram extraction using adaptive neuro fuzzy interference system trained with PSO algorithm in IEEE International Conference on Electro/Information Technology, EIT, pp: 1- 5.2011

15. Winokur. E.S, Delano. M.K and Sodini. C.G, A wearable cardiac monitor for long-term data acquisition and analysis, IEEE Transactions Biomedical Engineering, vol. 60, no. 1, pp. 189192, 2013.

16. Zhang. D.R, Deepu. C.J, Xu. X.Y, and Lian. Y, A wireless ECG plaster for real-time cardiac health monitoring in body sensor networks, in Proc. IEEE Biomedical Circuits Systems Conference, 2011, pp. 205208.

17. S. Mathen, Wavelet transform based adaptive image compression on FPGA, Masters thesis, Unviersity of Calicut, 1996,

18. J. Nikara, Parallel Huffman decoder with an optimize look up table option on FPGA, Ph.D. dissertation, Tampere University of Technology, 2004.

19. M. W. E. Jamro and K. Wiatr, FPGA implementation of the dynamic Huffman encoder, Proceedings of IFAC Workshop on Programmable Devices and Embedded Systems, 2006.

20. S. Sun and S. Lee, A JPEG chip for image compression and decompression, Journal of VLSI Signal Processing Systems, vol. 35, no. 1, pp. 4360, 2003. 1238