ALGORITMA PENCARIAN GREEDY GRAPH AUTOMATIC QRS COMPLEX DETECTION

 

Apa Itu EKG?

Sinyal elektrokardiogram (EKG) adalah alat non-invasif yang paling banyak digunakan untuk penyelidikan penyakit kardiovaskular. Penggambaran otomatis titik-titik fiducial EKG, khususnya R-peak, berfungsi sebagai dasar untuk pemrosesan dan analisis EKG. Studi ini mengusulkan metode baru analisis sinyal EKG dengan memperkenalkan kelas baru model grafis berdasarkan model deteksi titik perubahan yang optimal, yang diberi nama model deteksi titik perubahan terbatas grafik (GCCD). Model GCCD memperlakukan delineasi titik fidusia dalam sinyal EKG non-stasioner sebagai masalah deteksi titik perubahan. Model yang diusulkan mengeksploitasi jarangnya titik perubahan untuk mendeteksi perubahan mendadak

dalam sinyal EKG, dengan demikian tugas deteksi puncak-R dapat dilonggarkan dari langkah prapemrosesan apapun. Dalam pendekatan baru ini, pengetahuan biologis sebelumnya tentang urutan perubahan yang diharapkan dimasukkan ke dalam model menggunakan grafik kendala, yang dapat didefinisikan secara manual atau otomatis. Pertama, kita mendefinisikan grafik kendala secara manual; kemudian, kami menyajikan algoritma pembelajaran grafik yang dapat mencari grafik optimal dalam skema greedy. Akhirnya, kami membandingkan grafik yang ditentukan secara manual dan grafik yang dipelajari dalam hal struktur grafik dan akurasi deteksi. Kami mengevaluasi kinerja algoritme menggunakan Basis Data Aritmia MIT-BIH. Model yang diusulkan mencapai sensitivitas keseluruhan 99,64%, prediksi positif 99,71%, dan tingkat kesalahan deteksi 0,19 untuk grafik kendala yang ditentukan secara manual dan sensitivitas keseluruhan 99,76%, prediksi positif 99,68%, dan tingkat kesalahan deteksi 0,55 untuk grafik kendala pembelajaran otomatis.

Elektrokardiogram (EKG) adalah sinyal biomedis kuasi-periodik yang memberikan informasi tentang aktivitas listrik otot jantung. Satu siklus jantung dalam sinyal EKG khas digambarkan oleh pengaturan P, kompleks QRS, gelombang T, dan segmen PQ dan ST. Deteksi puncak R yang benar adalah langkah pertama dan paling kritis di hampir semua metode analisis EKG. Puncak-R adalah puncak tertinggi dan satu-satunya positif dalam Kompleks QRS, mencerminkan depolarisasi ventrikel dari aktivitas listrik jantung. Deteksi yang tepat dari lokasi puncak R memainkan peran penting dalam memperoleh morfologi kompleks QRS dan mengungkapkan lokasi titik-titik fidusial EKG lainnya. Selanjutnya, lokalisasi R-puncak berfungsi sebagai dasar untuk penentuan otomatis denyut jantung, yang merupakan kriteria signifikan untuk diagnosis aritmia jantung seperti kontraksi atrium prematur, takikardia, dan bradikardia. Banyak penyakit lain juga dapat didiagnosis dengan cara non-invasif menggunakan deteksi R-peak karena hubungan antara variabilitas denyut jantung dan beberapa sistem fisiologis (misalnya, vasomotor, pernapasan, saraf pusat, dan termoregulasi).

Berbagai pendekatan telah diusulkan dalam literatur untuk mendeteksi R-peaks dalam sinyal EKG. Biasanya, metode ini terdiri dari dua langkah utama: pra-pemrosesan dan deteksi. Pada langkah pra-pemrosesan, algoritme mencoba menghilangkan noise dan artefak dan menyoroti bagian EKG yang relevan. Pada langkah kedua, berbagai metode digunakan untuk menemukan R-puncak berdasarkan hasil dari langkah pra-pemrosesan, dan kemudian gelombang lain dideteksi dengan mendefinisikan seperangkat aturan heuristik. Namun, pendekatan ini memiliki beberapa kelemahan kritis yang membatasi kinerjanya dalam aplikasi praktis. Pertama, dalam pemrosesan data waktu nyata dan pengaturan perawatan rawat jalan, di mana data yang dikumpulkan sangat bising, algoritma berbasis pra-pemrosesan kurang efektif. Kedua, algoritme ini dapat gagal mendeteksi R-

Langkah deteksi R-peak umumnya dapat dicapai baik dengan menerapkan teknik berbasis ambang batas atau dengan menggunakan teknik ambang batas independen. Amplitudo puncak dan waktu durasi antara dua puncak R berturut-turut (yaitu, interval RR) biasanya digunakan untuk menentukan ambang batas yang sesuai.

Metodologi

Metode yang diusulkan memperlakukan deteksi gelombang EKG sebagai masalah deteksi titik perubahan untuk sinyal EKG non-stasioner. Ini mengekstrak R-puncak dalam sinyal EKG mentah dengan mewakili sinyal EKG non-stasioner periodik sebagai deret waktu stasioner lokal sepotong demi sepotong dengan nilai rata-rata konstan (yaitu, setiap bagian adalah rata-rata dari satu segmen titik data). Model mengambil sinyal EKG mentah dan grafik kendala sebagai input dan menghitung onset/offset dan rata-rata segmen yang diinginkan (yaitu, keadaan tersembunyi). Kemudian, pusat setiap bagian dikaitkan dengan lokasi puncak. Grafik kendala memungkinkan penggabungan pengetahuan sebelumnya ke dalam model dan mengatur model.

Ikhtisar model GCCD. Model GCCD mengambil grafik kendala dan sinyal EKG  mentah 

Struktur grafik kendala awal dengan dua node berlabel A dan R,

1.1.  Model deteksi titik perubahan yang dibatasi grafik

Deteksi titik fidusial EKG dapat didefinisikan sebagai masalah menemukan perubahan mendadak selama satu siklus jantung yang disebabkan oleh perubahan karakteristik statistik. Dari sudut pandang ini, algoritma deteksi titik perubahan yang tepat dapat digunakan untuk mendeteksi gelombang EKG dengan cara yang cepat dan efektif. Kami menerapkan model deteksi titik perubahan optimal yang diperkenalkan di Ref. untuk melokalisasi posisi R-peak dalam sinyal EKG.

Model ini, pengetahuan biologis sebelumnya tentang urutan perubahan yang diharapkan dimasukkan ke dalam model sebagai batasan grafik. Kemudian, algoritma pemrograman dinamis menggunakan pemangkasan fungsional menghitung model optimal global (rata-rata, perubahan, dan status tersembunyi) dengan cepat log-linear O(N log N) waktu. Secara matematis, diberikan sinyal input Y= {y₁, …, y_n } dan graf berarah G=(V, E) , masalah menemukan titik perubahan c, segmen berarti m, dan keadaan tersembunyi s dapat diselesaikan dengan menggunakan masalah optimasi berikut: 

Deteksi R-Peak

   1.2.   Constraint Graph

Grafik kendala G=(V,E) di dalam NS pengoptimalan masalah dari Persamaan (1) mengkodekan pengetahuan biologis sebelumnya tentang urutan perubahan yang diharapkan dalam satu siklus jantung. Itu bisa dirancang manual oleh seorang ahli Definisi Grafik Manual: Untuk mendefinisikan graf kendala G secara manual, kami memperhitungkan kemungkinan kategori morfologi untuk gelombang EKG (yaitu, gelombang P, QRS, dan T) dan sifat morfologi keseluruhan dari sinyal di setiap rekaman.

Peringatan dengan definisi manual grafik kendala adalah bahwa hal itu dapat menjadi tidak efisien untuk analisis sinyal EKG mengingat berbagai pola morfologi untuk setiap bentuk gelombang. Selanjutnya, kinerja model tergantung pada pengetahuan ahli yang dikodekan ke dalam grafik kendala. Untuk mengevaluasi model GCCD terdiri dari : 48 rekaman ECG dari 47 subjek, masing-masing rekaman berdurasi 30 menit, 360 Hz = 360 x 60 x 30 = 648000 gelombang, Resolusi lebih dari 10 MV, 2 ambulatory (MLII dan salah satu dari V1, V2, V4, V5) dan dataset dinotasi oleh expert.

Deteksi posisi R-puncak untuk Rekam 219 dari dataset MIT-BIH-AR 

 2. Kompleksitas komputasi

Seperti yang bisa dilihat di Algoritma 1, kompleksitas waktu algoritma GCCD secara teoritis sebanding dengan jumlah kandidat graf pada setiap iterasi (Baris 9) dan jumlah iterasi yang diperlukan untuk mencapai graf optimum dengan label error yang minimum (Baris 4).

Perbandingan struktur grafik kendala (a) didefinisikan secara manual dan (b) dipelajari menggunakan algoritma pembelajaran grafik yang diusulkan untuk Record 100 dari dataset MIT-BIH-A

Kesimpulan

model grafis baru berdasarkan teknik deteksi changepoint untuk mendeteksi R-puncak dalam sinyal EKG non-stasioner. Model yang diusulkan sangat berhasil dalam mendeteksi puncak-R dalam data EKG yang bising tanpa menerapkan langkah-langkah prapemrosesan apa pun

Sepengetahuan kami, ini adalah pertama kalinya model deteksi titik perubahan diterapkan untuk deteksi titik fidusial EKG. Dalam kerangka kerja baru ini, pengetahuan biologis sebelumnya tentang urutan perubahan yang diharapkan dimasukkan ke dalam model menggunakan grafik. Model yang dikembangkan berhsail mendekati puncak-R pada data ECG tanpa perlu langkah preprocessing. Menggunakan algoritma pembelajaran grafik yang diusulkan, struktur grafik awal dapat berkembang menjadi struktur yang berisi parameter tepi dengan akurasi deteksi maksimum untuk sebuah record. Pertama kalinya penerapan model pendeteksian changepoint pada data ECG.

Mendefinisikan graf batasan secara manual, lalu secara otomatis menggunakan algoritma pencarian greedy graph, dengan algoritma graph learning struktur graf awal memiliki edge parameter dengan akurasi maksimum. Hasil eksperimen yang diberikan dalam makalah ini menunjukkan bahwa model GCCD dapat menjadi pendekatan yang menjanjikan untuk mendeteksi gelombang EKG dan mengembangkan alat berbasis grafik baru untuk analisis EKG lebih lanjut. Pendekatan model grafis yang diusulkan dapat dikembangkan dengan mempelajari grafik kendala multi-jalur dan menyesuaikan model kurva multi-Gaussian dengan sinyal EKG, yang harus dipertimbangkan dalam studi masa depan.

Referensi

[1] I. Beraza, I. Romero, Comparative study of algorithms for ecg segmentation, Biomed. Signal Process Contr. 34 (2017) 166–173.

[2] D. Castells-Rufas, J. Carrabina, Simple real-time qrs detector with the mamemi filter, Biomed. Signal Process Contr. 21 (2015) 137–145.

[3] T. Sharma, K.K. Sharma, Qrs complex detection in ecg signals using locally adaptive weighted total variation denoising, Comput. Biol. Med. 87 (2017) 187–199.

[4] Z. Hou, Y. Dong, J. Xiang, X. Li, B. Yang, A real-time qrs detection method based on phase portraits and box-scoring calculation, IEEE Sensor. J. 18 (9) (2018) 3694–3702.