臺灣博碩士論文加值系統

心電圖推導呼吸訊號（EDR）是一種用來從心電圖（ECG）中推導呼吸訊號的技術，它能夠克服傳統擷取呼吸方法的限制。經驗模態分解（EMD）是一個自適應的分析過程，它能夠應用在非線性與非穩態的資料上例如：心電圖，因此能夠用來處理EDR應用。EMD是藉由迭代地將資料分解成數個本質模態函數來分析。傳統上，EMD是序列的運算每一個資料點，因此造成它的執行時間與資料量呈正比關係。在這篇論文中，一個由CUDA語言實作且運作在通用圖形處理器(GPGPU)的平行化EMD演算法被提出，用以改善傳統EMD的效能。並且額外的合併式三次樣條插值與GPU加速技巧被加入用來達到高平行度與高精確度。資料庫測試顯示，我們的CUDA平行化EMD在一百萬個資料點數下達到6.6倍加速，且經過了50次的迭代後只有0.0003%誤差。對於EDR應用，我們的平行化EMD達到69.75%的準確率，並且只需要7.91秒即可處理一分鐘的ECG。

ECG-Derived Respiratory (EDR) is a technique to derive respiratory from electrocardiography (ECG), which can help to overcome limitation of traditional respiratory acquisition method. Empirical Mode Decomposition (EMD) is process of adaptive analysis applicable to non-linear and non-stationary data such as ECG, hence it can be used to deal with EDR application. EMD analyzes data by iteratively decomposing data into multiple Intrinsic Mode Functions (IMFs). Traditionally, EMD is computed on all data points in a serial manner, thus making its execution time grows linearly with the data size. In this work, a parallelized EMD algorithm working on a General-Purpose computing on Graphics Processing Units (GPGPU) in CUDA language is proposed to improve performance over traditional EMD. Moreover, additional merging cubic spline interpolation and GPU acceleration techniques are also incorporated for achieving high parallelism and high accuracy. Statistical result of database shows that our parallelized EMD in CUDA achieves 6.6X speedup with 0.0003% error after 50 times iteration on datasets of 1-million points. For EDR application, our parallelized EMD achieves average 69.75% accuracy with average execution time of 7.91 second for 1-minute windows ECG from Fantasia Database.

摘要.....................................................................i
Abstract................................................................ii
Acknowledgements........................................................iv
Contents.................................................................v
List of Tables.........................................................vii
List of Figures.......................................................viii
Chapter 1 Introduction...................................................1
1.1 ECG-Derived Respiratory Signal.......................................3
1.2 EDR Signal Evaluation using Empirical Mode Decomposition.............5
1.3 Thesis Organization..................................................9
Chapter 2 Empirical Mode Decomposition..................................11
2.1 Sifting Process.....................................................11
2.1.1 Extract Extrema...................................................13
2.1.2 Fundamental of Cubic Spline Interpolation.........................14
2.2 Stop Criteria.......................................................17
2.3 Previous Work Review................................................18
Chapter 3 Parallelized EMD in CUDA......................................21
3.1 Stage 1 - Parallel Extrema Extraction...............................22
3.1.1 Sorting-Based Solution............................................23
3.1.2 Prefix Sum-Based Solution.........................................25
3.2 Stage 2 - Merging Cubic Spline Interpolation........................29
3.3 Stage 3 - Parallel IMF Generation...................................31
3.4 Parallel Stop Criteria Computation..................................33
Chapter 4 EDR Signal Evaluation using Parallelized EMD..................35
4.1 Method Summary......................................................35
4.2 The Fantasia Database...............................................38
4.3 Database Result Evaluation..........................................39
Chapter 5 Conclusion and Future Work....................................46
Reference...............................................................47
Appendix................................................................49
A.1 Raw EDR Result of CUDA EMD and C++ EMD..............................49
A.2 Use Filters to Preprocess ECG Signals...............................50

[1] 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,” Proc. Royal Society, pp. 903-995, 1998.
[2] C. O’Brien, C. Heneghan, “A comparison of algorithms for estimation of a respiratory signal from the surface electrocardiogram,” Computers in Biology and Medicine, vol. 37, pp. 305-314, 2007.
[3] W. J. Yi, and K. S. ParkZ, “Derivation of Respiration from ECG Measured Without Subject’s Awareness Using Wavelet Transform,” 24th Annual Conference and the Annual Fall Meeting of the Biomedical Engineering Society EMBS/BMES Conference, vol. 1, pp. 130-131, 2002.
[4] M. Campolo, D. Labate, F. L. Foresta, F. C. Morabito, A. L.-Ekuakille, and P. Vergallo “ECG-Derived Respiratory Signal using Empirical Mode Decomposition,” IEEE International Workshop on Medical Measurements and Applications Proceedings (MeMeA), Bari, pp. 399-403, May, 2011.
[5] D. Labate, F. L. Foresta, G. Occhiuto, F. C. Morabito, A. L.-Ekuakille, and P. Vergallo “Empirical Mode Decomposition vs. Wavelet Decomposition for the Extraction of Respiratory Signal from Single-Channel ECG: A Comparison,” IEEE Sensors Journal, vol. 13, pp. 2666-2674, July, 2013.
[6] K. Ramya and K. Rajkumar, “Respiration Rate Diagnosis Using Single Lead ECG in Real Time,” Global Journal of Medical research, vol. 13, 2013
[7] A. E. Santo, and C. Carbajal, “Respiration Rate Extraction from ECG Signal via Discrete Wavelet Transform,” Circuits and Systems for Medical and Environmental Applications Workshop (CASME), Merida, 2010.
[8] J. H. Mathews, K. D. Fink, Numerical Methods Using Matlab, 3rd Ed, Prentice Hall, 1998.
[9] D. M. Klionski, N. I. Oreshko, V. V. Geppener, and A. V. Vasiljev, “Applications of Empirical Mode Decomposition for Processing Nonstationary Signals,” Pattern Recognition and Image Analysis, vol. 18, pp. 390-399, 2008.
[10] G. Rilling, P. Flandrin, and P. Gonsalves, “On Empirical Mode Decomposition and Its Algorithms,” IEEE-EURASIP Workshop on Nonlinear Signal and Image Processing (NSIP), Grado, 2003.
[11] P. Waskito, S. Miwa, Y. Mitsukura, and H. Nakajo, “Parallelizing Hilbert-Huang Transform on a GPU,” First International Conference on Networking and Computing (ICNC) Washington, D.C., pp. 184-190, 2010.
[12] W. M. Yu, K. Xie, H. Q. Yu, P. Wu, T. Li, and M. F. Peng, “Hilbert-Huang transformation of large seismic data based on GPU,” International Conference on Intelligence Science and Information Engineering (ISIE), Wuhan, pp. 249-252, Aug. 2011.
[13] On the computational complexity of the empirical mode decomposition algorithm
[14] Khronos, “OpenCL,” available in https://www.khronos.org/opencl/.
[15] NVIDIA Corporation, “CUDA,” available in http://www.nvidia.com/object/cuda_home_new.html.
[16] NVIDIA Corporation, “Thrust Library,” available in https://developer.nvidia.com/Thrust.
[17] NVIDIA Corporation, “CUDA C Programming Guide 5.5,” available in http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf.
[18] M. Harris, “Parallel Prefix Sum (Scan) with CUDA,” NVIDIA Corporation, April, 2007.
[19] N.-F. Chang, C.-Y. Chiang, T.-C. Chen and L.-G. Chen, “Cubic spline interpolation with overlapped window and data reuse for on-line hilbert huang transform biomedical microprocessor,” International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC), Boston, pp. 7091-7094, 2011.
[20] P.-Y. Huang, H.-P. Wen and H. Chiueh, “Flexible Parallelized Empirical Mode Decomposition in CUDA for Hilbert Huang Transform,” International Conference on High Performance Computing and Communications (HPCC), Paris, pp. 1157-1165, 2014.
[21] Free Software Foundation, Inc., “GCC Complier Optimization,” available in https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html.
[22] Iyengar N, Peng C-K, Morin R, Goldberger AL, Lipsitz LA. Age-related alterations in the fractal scaling of cardiac interbeat interval dynamics. Am J Physiol 1996;271:1078-1084.
[23] Goldberger AL, Amaral LAN, Glass L, Hausdorff JM, Ivanov PCh, Mark RG, Mietus JE, Moody GB, Peng C-K, Stanley HE. PhysioBank, PhysioToolkit, and PhysioNet: Components of a New Research Resource for Complex Physiologic Signals. Circulation 101(23):e215-e220 [Circulation Electronic Pages; http://circ.ahajournals.org/cgi/content/full/101/23/e215]; 2000 (June 13).
[24] Wikipedia, “Sleep apnea,” available in http://en.wikipedia.org/wiki/Sleep_apnea
[25] Y. L. Chen and J. C. Chiou, “Switchable Multi-Frequency Portable Wireless Device in Remote Detection of Respiration and Heartbeat,” Institute of Electrical and Control Engineering National Chiao Tung University, 2011.
[26] “Sleep Apnea: What Is Sleep Apnea?,” NHLBI: Health Information for the Public. U.S. Department of Health and Human Services. May 2009.