QRStree: A prefix tree-based model to fetal QRS complexes detection

Autoři: Wei Zhong aff001;  Xuemei Guo aff001;  Guoli Wang aff001
Působiště autorů: School of Data and Computer Science, Sun Yat-sen University, Guangzhou, China aff001;  Key Laboratory of Machine Intelligence and Advanced Computing, Ministry of Education, Guangzhou, China aff002
Vyšlo v časopise: PLoS ONE 14(10)
Kategorie: Research Article
doi: https://doi.org/10.1371/journal.pone.0223057


Non-invasive fetal electrocardiography (NI-FECG) plays an important role in fetal heart rate (FHR) measurement during the pregnancy. However, despite the large number of methods that have been proposed for adult ECG signal processing, the analysis of NI-FECG remains challenging and largely unexplored. In this study, we propose a prefix tree-based framework, called QRStree, for FHR measurement directly from the abdominal ECG (AECG). The procedure is composed of three stages: Firstly, a preprocessing stage is employed for noise elimination. Secondly, the proposed prefix tree-based method is used for fetal QRS complexes (FQRS) detection. Finally, a correction stage is applied for false positive and false negative correction. The novelty of the framework relies on using the range of FHR to establish the connections between the FQRS. The consecutive FQRS can be considered as strings composed of alphabet items, thus we can use the prefix tree to store them. A vertex of the tree contains an alphabet, thus a path of the tree gives a string. Such that, by storing the connections of the FQRS into the prefix tree structure, the problem of FQRS detection converts to a problem of optimal path selection. Specifically, after selecting the optimal path of the tree, the nodes in the optimal path are collected as detected FQRS. Since the prefix tree can cover every possible combination of the FQRS candidates, it has the potential to reduce the occurrence of miss detections. Results on two different databases show that the proposed method is effective in FHR measurement from single-channel AECG. The focus on single-channel FHR measurement facilitates the long-term monitoring for healthcare at home.

Klíčová slova:

Built structures – Cardiology – Database and informatics methods – Electrocardiography – Heart rate – Pregnancy – Preprocessing – Scalp


1. Behar J, Andreotti F, Zaunseder S, Oster J, Clifford GD. A practical guide to non-invasive foetal electrocardiogram extraction and analysis. Physiol Meas. 2016;37(5):R1–R35. doi: 10.1088/0967-3334/37/5/R1 27067431

2. Clifford GD, Azuaje F, McSharry P. Advanced Methods And Tools for ECG Data Analysis. vol. 35. Norwood, MA, USA: Artech House, Inc.; 2006.

3. Hasan M, Reaz M, Ibrahimy M, Hussain M, Uddin J. Detection and Processing Techniques of FECG Signal for Fetal Monitoring. Biol Proced Online. 2009;11(1):263. doi: 10.1007/s12575-009-9006-z 19495912

4. Peters M, Crowe J, Piéri JF, Quartero H, Hayes-Gill B, James D, et al. Monitoring the fetal heart non-invasively: A review of methods. J Perinat Med. 2001;29:408–16. doi: 10.1515/JPM.2001.057 11723842

5. Johnson AEW, Behar J, Andreotti F, Clifford GD, Oster J. Multimodal heart beat detection using signal quality indices. Physiol Meas. 2015;36(8):1665–1677. doi: 10.1088/0967-3334/36/8/1665 26218060

6. Andreotti F, Riedl M, Himmelsbach T, Wedekind D, Wessel N, Stepan H, et al. Robust fetal ECG extraction and detection from abdominal leads. Physiol Meas. 2014;35(8):1551–1567. doi: 10.1088/0967-3334/35/8/1551 25071095

7. Behar J, Johnson A, Clifford GD, Oster J. A Comparison of Single Channel Fetal ECG Extraction Methods. Ann Biomed Eng. 2014;42(6):1340–1353. doi: 10.1007/s10439-014-0993-9 24604619

8. Assaleh K. Extraction of Fetal Electrocardiogram Using Adaptive Neuro-Fuzzy Inference Systems. IEEE Trans Biomed Eng. 2007;54(1):59–68. doi: 10.1109/TBME.2006.883728 17260856

9. Andreotti F, Behar J, Zaunseder S, Oster J, Clifford GD. An open-source framework for stress-testing non-invasive foetal ECG extraction algorithms. Physiol Meas. 2016;37(5):627. doi: 10.1088/0967-3334/37/5/627 27067286

10. Liu C, Li P, Maria CD, Zhao L, Zhang H, Chen Z. A multi-step method with signal quality assessment and fine-tuning procedure to locate maternal and fetal QRS complexes from abdominal ECG recordings. Physiol Meas. 2014;35:1665–1683. doi: 10.1088/0967-3334/35/8/1665 25069817

11. Lewis MJ. Review of electromagnetic source investigations of the fetal heart. Med Eng Phys. 2003;25(10):801–810. https://doi.org/10.1016/S1350-4533(03)00121-8 14630467

12. Hamilton PS. A comparison of adaptive and nonadaptive filters for reduction of power line interference in the ECG. IEEE Trans Biomed Eng. 1996;43(1):105–109. doi: 10.1109/10.477707 8567001

13. Dessì A, Pani D, Raffo L. An advanced algorithm for fetal heart rate estimation from non-invasive low electrode density recordings. Physiol Meas. 2014;35(8):1621. doi: 10.1088/0967-3334/35/8/1621 25069583

14. Pan J, Tompkins WJ. A Real-Time QRS Detection Algorithm. IEEE Trans Biomed Eng. 1985;BME-32(3):230–236. doi: 10.1109/TBME.1985.325532

15. Behar J, Oster J, Li Q, Clifford GD. ECG Signal Quality During Arrhythmia and Its Application to False Alarm Reduction. IEEE Trans Biomed Eng. 2013;60(6):1660–1666. doi: 10.1109/TBME.2013.2240452 23335659

16. Andreotti F, Gräßer F, Malberg H, Zaunseder S. Non-invasive Fetal ECG Signal Quality Assessment for Multichannel Heart Rate Estimation. IEEE Trans Biomed Eng. 2017;64(12):2793–2802. doi: 10.1109/TBME.2017.2675543 28362581

17. Clifford GD, Silva I, Behar J, Moody GB. Non-invasive fetal ECG analysis. Physiol Meas. 2014;35(8):1521. doi: 10.1088/0967-3334/35/8/1521 25071093

18. Zhang N, Zhang J, Li H, Mumini O, Samuel O, Ivanov K, et al. A Novel Technique for Fetal ECG Extraction Using Single-Channel Abdominal Recording. Sensors. 2017;17(3):457. doi: 10.3390/s17030457

19. Behar J, Oster J, Clifford GD. Non-invasive FECG extraction from a set of abdominal sensors. In: Computing in Cardiology 2013; 2013. p. 297–300.

20. Najafabadi FS, Zahedi E, Ali MAM. Fetal Heart Rate Monitoring Based on Independent Component Analysis. Comput Biol Med. 2006;36(3):241–252. doi: 10.1016/j.compbiomed.2004.11.004 16446158

21. Sameni R. Extraction of Fetal Cardiac Signals from an Array of Maternal Abdominal Recordings [Theses]. Institut National Polytechnique de Grenoble—INPG; Sharif University of Technology (SUT); 2008. Available from: https://tel.archives-ouvertes.fr/tel-00373361.

22. Widrow B, Glover JR, McCool JM, Kaunitz J, Williams CS, Hearn RH, et al. Adaptive noise cancelling: Principles and applications. Proc IEEE. 1975;63(12):1692–1716. doi: 10.1109/PROC.1975.10036

23. Sameni R, Clifford GD. A Review of Fetal ECG Signal Processing Issues and Promising Directions. Open Pacing Electrophysiol Ther J. 2010;3:4–20. doi: 10.2174/1876536X01003010004 21614148

24. Vahidi A, Stefanopoulou A, Peng H. Recursive least squares with forgetting for online estimation of vehicle mass and road grade: theory and experiments. Veh Syst Dyn. 2005;43(1):31–55. doi: 10.1080/00423110412331290446

25. Cerutti S, Baselli G, Civardi S, Ferrazzi E, Marconi AM, Pagani M, et al. Variability analysis of fetal heart rate signals as obtained from abdominal electrocardiographic recordings. J Perinat Med. 2009;14(6):445–452. https://doi.org/10.1515/jpme.1986.14.6.445.

26. Kanjilal PP, Palit S, Saha G. Fetal ECG extraction from single-channel maternal ECG using singular value decomposition. IEEE Trans Biomed Eng. 1997;44(1):51–59. doi: 10.1109/10.553712 9214783

27. Vullings R, Peters CHL, Sluijter RJ, Mischi M, Oei SG, Bergmans JWM. Dynamic segmentation and linear prediction for maternal ECG removal in antenatal abdominal recordings. Physiol Meas. 2009;30(3):291. doi: 10.1088/0967-3334/30/3/005 19223679

28. Castillo E, Morales DP, García A, Parrilla L, Ruiz VU, Álvarez-Bermejo JA. A clustering-based method for single-channel fetal heart rate monitoring. PLoS One. 2018;13(6):1–22. doi: 10.1371/journal.pone.0199308

29. Oudijk MA, Kwee A, Visser GHA, Blad S, Meijboom EJ, Rosen KG. The effects of intrapartum hypoxia on the fetal QT interval. BJOG-Int J Obstet Gy. 2004;111(7):656–660. doi: 10.1111/j.1471-0528.2004.00178.x

30. Zhong W, Liao L, Guo X, Wang G. A deep learning approach for fetal QRS complex detection. Physiol Meas. 2018;39(4):045004. doi: 10.1088/1361-6579/aab297 29485406

31. Pyun G, Yun U, Ryu KH. Efficient frequent pattern mining based on Linear Prefix tree. Knowl-Based Syst. 2014;55:125–139. doi: 10.1016/j.knosys.2013.10.013

32. Uno T, Kiyomi M, Arimura H. LCM ver.3 Collaboration of Array, Bitmap and Prefix Tree for Frequent Itemset Mining. In: Proceedings of the 1st international workshop on open source data mining frequent pattern mining implementations—OSDM '05. ACM Press; 2005.

33. Pham TT, Luo J, Hong TP, Vo B. An efficient method for mining non-redundant sequential rules using attributed prefix-trees. Eng Appl Artif Intell. 2014;32:88–99. doi: 10.1016/j.engappai.2014.02.019

34. Feng J, Wang J, Li G. Trie-join: a trie-based method for efficient string similarity joins. VLDB J. 2011;21(4):437–461. doi: 10.1007/s00778-011-0252-8

35. Van TT, Vo B, Le B. Mining Sequential Rules Based on Prefix-Tree. In: New Challenges for Intelligent Information and Database Systems. Springer Berlin Heidelberg; 2011. p. 147–156.

36. Bodon F, Rónyai L. Trie: An alternative data structure for data mining algorithms. Math Comput Modell. 2003;38:739–751. doi: 10.1016/0895-7177(03)90058-6

37. Behar J, Oster J, Clifford GD. Combining and benchmarking methods of foetal ECG extraction without maternal or scalp electrode data. Physiol Meas. 2014;35(8):1569–1589. doi: 10.1088/0967-3334/35/8/1569 25069410

38. von Steinburg SP, Boulesteix AL, Lederer C, Grunow S, Schiermeier S, Hatzmann W, et al. What is the “normal” fetal heart rate? PeerJ. 2013;1:e82. doi: 10.7717/peerj.82

39. Goldberger A, Amaral L, Glass L, Hausdorff JM, Ivanov P, Mark R, et al. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. Circulation. 2000;101(23):215–220. doi: 10.1161/01.CIR.101.23.e215

40. Silva I, Behar J, Sameni R, Zhu T, Oster J, Clifford GD, et al. Noninvasive fetal ECG: The PhysioNet/Computing in Cardiology Challenge 2013. In: Computing in Cardiology 2013; 2013. p. 149–152.

Článek vyšel v časopise


2019 Číslo 10
Nejčtenější tento týden