本論文提出一種基於心電訊號之時頻轉換圖結合人工智慧演算法的睡眠呼吸中止症偵測演算法。本論文提出的方法主要包括訊號前處理程序(signal pre-processing)、心電訊號時頻圖產生程序(ECG time-frequency transformation)、詞袋模型特徵萃取(bag of feature model-based feature transformation)、人工智慧辨識器辨識程序(AI-based classification)、交叉驗證程序等部分。在訊號前處理部分，本論文將心電圖進行零平均的轉換(zero-mean)；接著在心電訊號時頻圖產生程序部分，本論文透過連續小波轉換的時頻轉換方式產生心電訊號時頻圖，將心電訊號時頻圖中的0.5-50 Hz、8-50 Hz、0.8-10 Hz、0-0.8 Hz等特定頻段分別萃取出來成為時頻圖，接著透過詞袋模型特徵萃取特定頻帶之時頻圖圖像特徵，最後再將時頻圖圖像特徵輸入到人工智慧辨識器(SVM、Ensemble learning、KNN)進行有無發生睡眠中止的辨識程序。然後以K-fold交叉驗證以及Leave one subject out交叉驗證進行結果探討。在驗證結果的資料選擇部分，為了與相關文獻有一致的條件可供比較，本論文使用Physionet的數據庫進行測試。除去有問題的兩筆資料，以數據庫中33位受試者，每個約7-8小時的睡眠心電訊號作為驗證資料，平均AHI是30.23，平均年齡46.85歲。在60秒的時間片段部分，使用5-fold交叉驗證方式時，搭配SVM分類器在8-50Hz跟0.8-10Hz頻段可分別得到91.11%以及90.58%的正確率。使用Leave-one subject-out交叉驗證方式時，搭配SVM分類器得到70%的正確性。在10秒的時間片段部分，我們選出的8個受試者加上5-fold交叉驗證方式，可以在0.5-50Hz跟0.8-10Hz頻段達到84%的正確性。文獻探討中，使用同樣數據庫的演算法最佳準確率為Manrique在2009年以Spectral centroids和Energy of spectral centroids等動態特徵(dynamic features)達到89.02% [15]，而此篇研究的結果以一分鐘的時間長度同樣可以達相近甚至更好的準確率。另外，有別傳統利用心電變異性參數來分析心電圖的生理意義，僅以R波的間距作為探討的依據，忽略了心電訊號的其他波形可能具有的生理性質，此篇論文利用時頻圖轉換的方式，可以將完整心電圖波型的訊息以能量的分布來呈現，當異常發生時，可以能量分布的變化觀察。而加上人工智慧演算法的應用，則可以以機器取代人眼，加快分類的效率，且明確抓取有利於分類的特徵，有利後續分析所代表的生理意義。因此，此篇論文的貢獻在於，開發了一種新穎並有利於觀察完整心電圖生理意義的演算法，未來的工作分為兩大方向，第一是將目前以人工智慧演算法抓取的特徵，與生理意義作連結，並找出睡眠呼吸中止症的表徵，第二則是實際應用臨床資料作驗證，佐證此方法在臨床上的可行性。

This thesis proposes a sleep apnea detection algorithm based on time-frequency transformation spectrogram of ECG signal combined with artificial intelligence algorithm. The methods proposed in this thesis mainly include signal pre-processing, ECG time-frequency transformation, and a bag of feature model-based feature transformation, AI-based classification, cross-validation procedures, etc. In the signal pre-processing, this thesis will perform zero-mean conversion on the electrocardiogram; then in the ECG time-frequency transformation, this thesis generates the time-frequency transformation spectrogram of ECG signal through the continuous wavelet transform. The specific frequency bands 0.5-50 Hz, 8-50 Hz, 0.8-10 Hz, and 0-0.8 Hz in the spectrograms of the ECG signal are separately divided. Then image features of the specific frequency band are extracted by a bag of feature mode. Finally, the image features of spectrogram are input to the artificial intelligence classifiers (SVM, Ensemble learning, KNN) for identification procedures with or without sleep apnea. The results were validated by K-fold cross-validation and Leave one subject out cross-validation.
For the same condition to compare with the existing literature, this thesis uses the Physionet database for verification. Thrity-three subjects each with 7-8 hours of sleep ECG as verification data had an average AHI of 30.23 and an average age of 46.85 years in the database. In the 60-second time segment, the accuracy of 91.11% and 90.58% can be obtained in the 8-50 Hz and 0.8-10 Hz bands by using the 5-fold cross-validation method with the SVM classifier, respectively. When using the Leave-one subject-out cross-validation method with the SVM classifier, the result had 70% accuracy. In the 10- second time segment, the eight subjects selected can achieve 84% accuracy in the 8-50 Hz and 0.8-10 Hz frequency bands with 5-fold cross-validation method.
In the literature discussion, the best accuracy using the same database reached 89.02% in Manrique's paper which used dynamic features such as spectral centroids and energy of spectral centroids in 2009 [15]. In this thesis, the results can achieve the better accuracy in one minute. Also, the traditional method like heart rate variability parameters only use the variation of RR interval to analysis ECG signals and ignore the physiological properties of other waveforms of ECG signals. This thesis use time-frequency spectrogram to present the information of complete ECG signals by the distribution of energy. Also, the application of artificial intelligence algorithm can replace the human eye with the machine to speed up the classification efficiency and extract the characteristics that are important for classification. Therefore, the contribution of this paper is to develop a novel algorithm that is useful for observing the physiological significance of complete ECG. There are two major directions for future work. The first one is to find the physiological meaning of features the artificial intelligence algorithm extracted, and to find the characterization of sleep apnea. The second one is using the clinical data for verification to solve the limitation of the current database and support the clinical feasibility of this method.

摘 要 i
Abstract iii
誌謝 vi
Table of Contents vii
List of Tables ix
List of Figures x
Chapter 1 Introduction 1
1.1 Introduction 1
1.2 Sleep apnea 2
1.2.1 Background 2
1.2.2 Diagnosis method 3
1.3 Surveys of related works in the literature 6
1.3.1 HRV analysis applied in sleep apnea 6
1.3.2 EDR signals applied in sleep apnea 7
1.4 Motivation 8
1.5 Organization of this thesis 9
Chapter 2 Methodology 10
2.1 Time-frequency transform 10
2.1.1 Basic theory 10
2.1.2 Application in physiology 13
2.1.3 Application in this study 13
2.2 Visual classification 17
2.2.1 Bag of features 17
2.2.2 Speeded up robust features (SURF) 19
2.2.2.1 Keypoints detection 19
2.2.2.2 Keypoints description 20
2.2.3 Application in this study 22
Chapter 3 Proposed algorithm 25
3.1 Data description 25
3.2 Spectrogram production 25
3.2.1 Preprocess 25
3.2.2 Segmentation 25
3.2.3 Time-frequency transformation 26
3.3 Model training 31
3.3.1 Feature extraction 31
3.3.2 Classifier construction 32
3.3.2.1 Support vector machine (SVM) 32
3.3.2.2 Ensemble learning 34
3.3.2.3 k-nearest neighbor (KNN) 35
3.4 Validation 36
3.4.1 k-fold cross validation 37
3.4.2 Leave one subject out 38
Chapter 4 Experimental result 39
4.1 Data source 39
4.2 Data graphics 40
4.3 Experimental results 43
4.3.1 5-fold cross validation with 60 second time window 43
4.3.2 LOSO with 60s time window 47
4.3.3 5-fold cross validation with 10s time window 50
Chapter 5 Discussion and conclusion 52
5.1 Discussion 52
5.1.1 Comparison of different frequency bands in 60 seconds 52
5.1.2 Comparison of different frequency bands in 10 seconds 55
5.1.3 Comparison with existing literature 57
5.2 Conclusion and future work 58
References 59

[1] https://www.dgbas.gov.tw/lp.asp?CtNode=3293＆CtUnit=400＆BaseDSD=7＆mp=1
[2] http://www.tssm.org.tw/resource_03.php
[3] A. Qaseem, P. Dallas, D. K. Owens, M. Starkey, J. C. Holty, P. Shekelle, Diagnosis of obstructive sleep apnea in adults: a clinical practice guideline from the American College of Physicians, Ann. Intern. Med., vol. 161, no. 3, pp. 210-220, 2014.
[4] L. J. Epstein, D. Kristo, P. J. Strollo, N. Friedman, A. Malhotra, S. P. Patil, K. Ramar, R. Rogers, R. J. Schwab, E. M. Weaver, M. D. Weinstein, Clinical guideline for the evaluation, management and longterm care of obstructive sleep apnea in adults, Journal of Clinical Sleep Medicine, vol. 5, no. 3, pp. 263-276, 2009.
[5] https://sciencebasedmedicine.org/dental-management-of-obstructive-sleep-apnea/
[6] L. P. Chuang, S. C. Hsu, S. W. Lin, W. S. Ko, N. H. Chen, Y. H. Tsai. “Prevalence of Snoring and Witnessed Apnea in Taiwanese Adults, Chang Gung Med J, vol. 31, no.2, pp. 175-181, 2008
[7] P. E. Peppard, T Young, J. H. Barnet, M Palta, E. W. Hagen, K. M. Hla, “Increased prevalence of sleep-disordered breathing in adults, AMJ Epidemiol, vol. 177, no. 9, pp. 1006-1014, May. 2013.
[8] C. V Senaratna, J. L. Perret, C.J. Lodge, A. J. Lowe, B. E. Campbell, M. C. Matheson, G. S. Hamilton, S. C. Dharmage, Prevalence of obstructive sleep apnea in the general population: A systematic review, Sleep Med. Rev., vol. 34, pp. 70-81, Aug. 2017.
[9] S. M. Caples, Sleep-disordered breathing and cardiovascular risk, Sleep, vol. 30, no. 3, pp. 291-303, Mar. 2007.
[10] T. Penzel, G. B. Moody, R. G. Mark, A. L. Goldberger, J. H. Peter, “The apnea-ECG database, Proc. Comput. Cardiol, pp. 255-258, 2000.
[11] https://www.physionet.org/physiobank/database/apnea-ecg/annotations.shtml
[12] https://www.physionet.org/physiobank/database/apnea-ecg/
[13]C. Varon, A. Caicedo, D. Testelmans, B. Buyse, S. Van, A Novel Algorithm for the Automatic Detection of Sleep Apnea From Single-Lead ECG, IEEE Transactions on Biomedical Engineering, vol. 62 pp.2269-2278, 2015.
[14]P. Langley, E. J. Bowers, A. Murray, “Principal component analysis as a tool for analyzing beat-to-beat changes in ECG features: Application to ecg-derived respiration, IEEE Trans. Biomed. Eng., vol. 57, no. 4, pp. 821-829, Apr. 2010.
[15]Q. Manrique, A. Hernandez, T. Gonzalez, F. Pallester and C. Dominquez, “ Detection of Obstructive Sleep Apnea in ECG Recordings Using Time-Frequency Distributions and Dynamic Features, Proceedings of the IEEE International Conference on Engineering in Medicine and Biology Society, pp. 5559-5562, Sep. 2009.
[16]T. Penzel, J. W. Kantelhardt, L. Grote, J. H. Peter, A. Bunde,“Comparison of detrended fluctuation analysis and spectral analysis for heart rate variability in sleep and sleep apnea IEEE Trans. Biomed. Eng., vol. 50, no. 10, pp. 1143-1151, Oct. 2003.
[17] P. de Chazal, T. Penzel, C. Heneghan, “Automated detection of obstructive sleep apnoea at different time scales using the electrocardiogram, Physiol. Meas., vol. 25, no. 4, pp. 967-983, Aug. 2004.
[18]M. A. Al-Abed, K. Behbehani, J. Burk, E. Lucas, M. Manry, “A Method to Detect Obstructive Sleep Apnea Using Neural Network Classification of Time-Frequency Plots of the Heart Rate Variability, Conference Proceedings 29th Annual International Conference of the IEEE EMBS, pp. 6101-6104, 2007.
[19] P. S. Addison, Wavelet transforms and the ECG: A review, Physiol. Meas., vol. 26, no. 5, pp. 155-199, 2005.
[20] C. Li, C. X. Zheng, C. F. Tai, Detection of ECG characteristic points using wavelet transforms, IEEE Trans. Biomed. Eng., vol. 42, no. 1, pp. 21-28, Jan. 1995.
[21] L. Y. Shyu, Y. H. Wu, W. Hu, “Using wavelet transform and fuzzy neural network for VPC detection from the Holter ECG, IEEE Trans. Biomed. Eng., vol.51 1269-73,2004
[22] I. R. Legarreta, P. S. Addison, M. I. Reed, N. Grubb, G. R. Clegg, C. E. Robertson, J. N. Watson, Continuous wavelet transform modulus maxima analysis of the electrocardiogram: beat characterisation and beat-to-beat measurement, International Journal of Wavelets Multiresolution and Information Processing, vol. 03, no. 1, pp. 19-42, 2005.
[23] N. Uchaipichat, S. Inban, “Development of QRS detection using short-time fourier transform based technique, IJCA,Special Issue on CASCT, no. 1, pp. 7-10, 2010.
[24] G. Csurka, C. Dance, L. Fan, J. Willamowski, C. Bray, Visual categorization with bags of keypoints, Proc. Workshop Statist. Learning Comput. Vis. Eur. Conf. Comput. Vis., vol. 1, pp. 22, 2004.
[25] https://www.mathworks.com/help/vision/exam
[26] H. Bay, A. Ess, T. Tuytelaars, L. V. Gool, “Speeded-Up Robust Features (SURF), Comput. Vis. Image Underst., vol.110, pp. 346-359, 2008.
[27]https://ww2.mathworks.cn/help/stats/support-vector-machines-for-binary-classification.html
[28] http://svsleepcenter.com/procedures.html
[29] E. Pereira, H. Driver, S. Stewart, M. Fitzpatrick, Comparing a Combination of Validated Questionnaires and Level III Portable Monitor with Polysomnography to Diagnose and Exclude Sleep Apnea, Journal of Clinical Sleep Medicine, vol. 9, no. 12, pp.1259-1266, 2013.
[30] F. Roche, J. M. Gaspoz, I. Court-Fortune, P. Minini, V. Pichot, D. Duverney, F. Costes, J. R. Lacour, J. C. Barthelemy, Screening of obstructive sleep apnea syndrome by heart rate variability analysis, Circulation, vol. 100, no. 13, pp. 1411-1415, 1999.
[31] T. Penzel, J. W. Kantelhardt, L. Grote, J. H. Peter, and A. Bunde, “Comparison of detrended fluctuation analysis and spectral analysis for heart rate variability in sleep and sleep apnea, IEEE Trans. Biomed. Eng., vol. 50, no. 10, pp. 1143-1151, Oct. 2003.
[32]https://en.wikipedia.org/wiki/Ensemble_learning.
[33] https://www.mathworks.com/help/stats/ensemble-algorithms.html
[34]https://www.mathworks.com/help/stats/classification-using-nearest-neighbors.html? searchHighlight=k%20nearest＆s_tid=doc_srchtitle
[35] A. R. Hassan, Computer-aided obstructive sleep apnea detection using normal inverse Gaussian parameters and adaptive boosting, Biomed. Signal Process. Control, vol. 29, pp. 22-30, 2016.
[36] MATLAB and Signal Processing Toolbox Release 2017b, The MathWorks, Inc., Natick, Massachusetts, United States.
[37] MATLAB and Computer Vision System Toolbox Release 2017b, The MathWorks, Inc., Natick, Massachusetts, United States.
[38] MATLAB and Statistics and Machine Learning Toolbox Release 2017b, The MathWorks, Inc., Natick, Massachusetts, United States.