Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device
Arrhythmia is less frequent than a normal heartbeat in an electrocardiogram signal, and the analysis of an electrocardiogram measurement can require more than 24 hours. Therefore, the efficient storage and transmission of electrocardiogram signals have been studied, and their importance has increase...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2019-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8894355/ |
| _version_ | 1798002047985909760 |
|---|---|
| author | Seungmin Lee Yoosoo Jeong Junho Kwak Daejin Park Kil Houm Park |
| author_facet | Seungmin Lee Yoosoo Jeong Junho Kwak Daejin Park Kil Houm Park |
| author_sort | Seungmin Lee |
| collection | DOAJ |
| description | Arrhythmia is less frequent than a normal heartbeat in an electrocardiogram signal, and the analysis of an electrocardiogram measurement can require more than 24 hours. Therefore, the efficient storage and transmission of electrocardiogram signals have been studied, and their importance has increased recently due to the miniaturization and weight reduction of measurement equipment. The polygonal approximation method based on dynamic programming can effectively achieve signal compression and fiducial point detection by expressing signals with a small number of vertices. However, the execution time and memory area rapidly increase depending on the length of the signal and number of vertices, which are not suitable for lightweight and miniaturized equipment. In this paper, we propose a method that can be applied in embedded environments by optimizing the processing time and memory usage of dynamic programming applied to the polygonal approximation of an ECG signal. The proposed method is divided into three steps to optimize the processing time and memory usage of dynamic programming. The first optimization step is based on the characteristics of electrocardiogram signals in the polygonal approximation. Second, the size of a data bit is used as the threshold for the time difference of each vertex. Finally, a type conversion and memory optimization are applied, which allow real-time processing in embedded environments. After analyzing the performance of the proposed algorithm for a signal length <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula> and number of vertices <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>, the execution time is reduced from <inline-formula> <tex-math notation="LaTeX">$O(L^{2}N)$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$O(L)$ </tex-math></inline-formula>, and the memory usage is reduced from <inline-formula> <tex-math notation="LaTeX">$O(L^{2}N)$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$O(LN)$ </tex-math></inline-formula>. In addition, the proposed method preserve a performance of fiducial point detection. In a QT-DB experiment provided by Physionet, achieving values of −4.01 ± 7.99 ms and −5.46 ± 8.03 ms. |
| first_indexed | 2024-04-11T11:45:59Z |
| format | Article |
| id | doaj.art-df2f4c0120fd491187132088e5d5ca90 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-11T11:45:59Z |
| publishDate | 2019-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-df2f4c0120fd491187132088e5d5ca902022-12-22T04:25:35ZengIEEEIEEE Access2169-35362019-01-01716285016286110.1109/ACCESS.2019.29523998894355Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded DeviceSeungmin Lee0https://orcid.org/0000-0002-5910-4387Yoosoo Jeong1Junho Kwak2Daejin Park3Kil Houm Park4Advanced Dental Device Development Institute, Kyungpook National University, Daegu, South KoreaSchool of Electronics Engineering, Kyungpook National University, Daegu, South KoreaSchool of Electronics Engineering, Kyungpook National University, Daegu, South KoreaSchool of Electronics Engineering, Kyungpook National University, Daegu, South KoreaSchool of Electronics Engineering, Kyungpook National University, Daegu, South KoreaArrhythmia is less frequent than a normal heartbeat in an electrocardiogram signal, and the analysis of an electrocardiogram measurement can require more than 24 hours. Therefore, the efficient storage and transmission of electrocardiogram signals have been studied, and their importance has increased recently due to the miniaturization and weight reduction of measurement equipment. The polygonal approximation method based on dynamic programming can effectively achieve signal compression and fiducial point detection by expressing signals with a small number of vertices. However, the execution time and memory area rapidly increase depending on the length of the signal and number of vertices, which are not suitable for lightweight and miniaturized equipment. In this paper, we propose a method that can be applied in embedded environments by optimizing the processing time and memory usage of dynamic programming applied to the polygonal approximation of an ECG signal. The proposed method is divided into three steps to optimize the processing time and memory usage of dynamic programming. The first optimization step is based on the characteristics of electrocardiogram signals in the polygonal approximation. Second, the size of a data bit is used as the threshold for the time difference of each vertex. Finally, a type conversion and memory optimization are applied, which allow real-time processing in embedded environments. After analyzing the performance of the proposed algorithm for a signal length <inline-formula> <tex-math notation="LaTeX">$L$ </tex-math></inline-formula> and number of vertices <inline-formula> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula>, the execution time is reduced from <inline-formula> <tex-math notation="LaTeX">$O(L^{2}N)$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$O(L)$ </tex-math></inline-formula>, and the memory usage is reduced from <inline-formula> <tex-math notation="LaTeX">$O(L^{2}N)$ </tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">$O(LN)$ </tex-math></inline-formula>. In addition, the proposed method preserve a performance of fiducial point detection. In a QT-DB experiment provided by Physionet, achieving values of −4.01 ± 7.99 ms and −5.46 ± 8.03 ms.https://ieeexplore.ieee.org/document/8894355/Dynamic programmingelectrocardiogramembedded systemfiducial pointoptimizationpolygonal approximation |
| spellingShingle | Seungmin Lee Yoosoo Jeong Junho Kwak Daejin Park Kil Houm Park Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device IEEE Access Dynamic programming electrocardiogram embedded system fiducial point optimization polygonal approximation |
| title | Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device |
| title_full | Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device |
| title_fullStr | Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device |
| title_full_unstemmed | Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device |
| title_short | Advanced Real-Time Dynamic Programming in the Polygonal Approximation of ECG Signals for a Lightweight Embedded Device |
| title_sort | advanced real time dynamic programming in the polygonal approximation of ecg signals for a lightweight embedded device |
| topic | Dynamic programming electrocardiogram embedded system fiducial point optimization polygonal approximation |
| url | https://ieeexplore.ieee.org/document/8894355/ |
| work_keys_str_mv | AT seungminlee advancedrealtimedynamicprogramminginthepolygonalapproximationofecgsignalsforalightweightembeddeddevice AT yoosoojeong advancedrealtimedynamicprogramminginthepolygonalapproximationofecgsignalsforalightweightembeddeddevice AT junhokwak advancedrealtimedynamicprogramminginthepolygonalapproximationofecgsignalsforalightweightembeddeddevice AT daejinpark advancedrealtimedynamicprogramminginthepolygonalapproximationofecgsignalsforalightweightembeddeddevice AT kilhoumpark advancedrealtimedynamicprogramminginthepolygonalapproximationofecgsignalsforalightweightembeddeddevice |