i
UCAPAN TERIMA KASIH Puji syukur kita panjatkan kehadirat Tuhan Yang Maha Esa atas segala rahmat dan hidayah-Nya penulis dapat menyelesaikan tesis dengan judul Sistem Deteksi Garis Pantai Dengan Algoritma Self Organizing Map dan K-Nearest Neighbor Untuk Sistem Monitoring Video. Dalam menyelesaikan tesis ini penulis mendapatkan banyak bantuan, bimbingan dan dorongan dari berbagai pihak. Oleh karena itu penulis ingin mengucapkan terima kasih kepada semua pihak yang telah membantu dalam penyelesaian tesis ini, antara lain Rektor Universitas Udayana Prof.Dr.dr. Ketut Suastika, Sp.PD.KEMD atas kesempatan dan fasilitas yang diberikan kepada penulis untuk mengikuti dan menyelesaikan pendidikan Program Magister di Universitas Udayana. Direktur Program Pascasarjana Universitas Udayana yang dijabat oleh Prof. Dr. dr. A.A. Raka Sudewi, Sp.S(K) dan Prof. Dr. Made Budiarsa, M.A., sebagai Asisten Direktur I Program Pasca Sarjana Universitas Udayana atas kesempatan yang diberikan kepada penulis untuk menjadi mahasiswa Program Magister pada Program Pascasarjana Universitas Udayana. Dr. I Made Oka Widyantara, S.T., M.T., selaku dosen pembimbing I, atas bimbingan, pengarahan, saran, dan dukungan selama penyusunan tesis ini. NMAE Dewi Wirastuti, S.T., M.Sc., Ph.D., selaku dosen pembimbing II yang dengan penuh perhatian dan kesabaran telah memberikan bimbingan dan saran kepada penulis. Seluruh Dosen khususnya dosen Program Magister Teknik Elektro Universitas Udayana atas ilmu yang telah diberikan. Prof. Ir. Rukmi Sari Hartati, M.T., Ph.D, Prof. Ir. I. A. Dwi Giriantari, M.Eng.Sc., Ph.D., Ir. Linawati, M.Eng.Sc., Ph.D., yang telah memberikan masukan, saran, sanggahan, dan koreksi sehingga tesis ini dapat terwujud. Pada kesempatan ini, penulis juga menyampaikan rasa terima kasih kepada Orang tua I Made Astawadana (Alm), dan Dra. Luh Gede Budi Utami, M.Hum.,
ii
yang tiada hentinya memberikan doa, semangat, dan pengorbanan yang sangat besar. Istri Ni Komang Ayu Sri Wahyuni yang selalu memberikan semangat dan dukungan hingga tesis ini selesai. Kedua Saudara I Dana Utama dan Ni Nyoman Astrini Utami yang selalu menjadi motivasi selama pengerjaan tesis. Temanteman seperjuangan Manajemen Bisnis Telekomunikasi 2014 atas semangat dan dukungannya. Semua pihak yang telah membantu dalam penyusunan laporan ini yang tidak dapat penulis sebutkan satu per satu. Penulis menyadari bahwa penulisan tesis yang telah dibuat masih jauh dari kesempurnaan. Oleh karena itu, penulis sangat mengharapkan kritik dan saran yang membangun dari pembaca.
ABSTRAK SISTEM DETEKSI GARIS PANTAI DENGAN ALGORITMA SELF ORGANIZING MAP DAN K-NEAREST NEIGHBOR UNTUK SISTEM MONITORING VIDEO
Perubahan garis pantai merupakan salah satu dasar informasi tentang permasalahan yang terjadi pada kawasan pantai. Perubahan garis pantai yang terjadi dapat menandakan kawasan pantai terjadi pengikisan badan pantai (abrasi) dan penambahan badan pantai (akresi). Dibutuhkan sebuah media pemantauan perubahan garis pantai, agar dapat dilakukan penanggulangan yang cepat dan tepat dari pihak yang berkepentingan. Untuk mengetahui perubahan garis pantai dengan cepat tanpa harus kelokasi maka dibangun sistem pemantauan garis pantai yang dapat dipantau dari jarak jauh. Pada sistem pemantauan garis pantai, daerah yang menjadi fokus pemantauan adalah garis pantai, sehingga sistem harus dapat mendeteksi letak garis pantai pada data hasil monitoring. Sistem deteksi yang dibangun menerapkan metode Self Organizing Map (SOM) dalam melakukan segmentasi kawasan pantai menjadi tiga daerah. Kemudian hasil segmentasi diklasifikasi dengan algoritma K-Nearest Neighbor (KNN) sehingga kawasan hasil segmentasi dapat dikenali sebagai laut, daratan, dan langit. Penentuan letak garis pantai dilakukan dengan mengambil pixel pada daerah daratan yang pixel tetangganya adalah daerah lautan. Fitur yang digunakan dalam segmentasi dengan SOM adalah ciri RGB dengan preprocessing contrast stretching dan morphological contrast enhancement. Fitur yang digunakan pada sistem pelatihan data kawasan pantai adalah ciri tekstur dengan menggunakan nilai contrast, energy, homogeneity, dan entropy. Kinerja SOM dalam proses segmentasi kawasan pantai diukur dengan metode silhouette coefficient dan pengukuran kinerja KNN dalam proses klasifikasi digunakan ROC dan AUC. Sistem deteksi garis pantai dengan SOM dan KNN yang telah dibangun dapat menampilkan letak garis pantai pada data hasil pemantauan (frame) dengan warna merah. Sistem yang telah dibangun juga dapat memberikan informasi perubahan garis pantai berdasarkan perbandingan frame referensi dengan frame inputan. Teknik preprocessing yang diusulkan pada penelitian ini yaitu kombinasi contrast stretching dan morphological contrast enhancement, berhasil membantu proses segmentasi dengan SOM, sehingga sistem dapat menemukan garis pantai. Nilai silhouette coefficient yang dihasilkan oleh SOM pada segmentasi kawasan pantai adalah 0,5304 dari rentang 0 sampai dengan 1 yang merupakan kategori reasonable cluster. Hasil pengujian KNN pada proses klasifikasi daerah hasil segmentasi, mendapatkan nilai AUC 0,90 dari rentang nilai 0 sampai dengan 1 yang merupakan kategori klasifikasi baik. Kata kunci — Garis Pantai, Perubahan Garis Pantai, Self Organizing Map, KNearest Neighbor, Contrast Streching, Morphological Contrast Stretching.
118
119
ABSTRACT COASTAL LINE DETECTION SYSTEM WITH SELF ORGANIZING MAP AND K - NEAREST NEIGHBOR ALGORITHM FOR VIDEO MONITORING SYSTEM Coastline change is one of the basic information about problems that occur in coastal areas. Coastline change could be indicate erosion and the addition of beach bodies. And we need a media coastal line change monitoring in order to do fast and precise response from management agencies. To determine the coastline changes quickly without having to localized, then need to built coastline monitoring system that can be monitored remotely. In a system of monitoring the coastline , the area that became the focus of the monitoring is the coastline , so the system must be able to detect the location of the shoreline on the monitoring records. The coastline detection system constructed applying Self Organizing Map method (SOM) in segmenting the coastal area into three regions. Then segmentation results classified by K Nearest Neighbor (KNN) so that the region segmentation results can be recognized as a sea , land and sky . Determining the location of the coastline is done by taking the pixel neighbor's land area is a pixel in area of the ocean . Features used in segmentation with SOM is RGB feature with contrast stretching and morphological contrast enhancement preprocessing. Features used on the training system of data coastal region is texture features by using the value of contrast , energy , homogeneity , and entropy. SOM Performance in the coastal region segmentation process is measured by the method of silhouette coefficient and performance measurement of KNN classification process used ROC and AUC . The coastline detection system with SOM and KNN has been built to show the location of the coastline on the frame with red color . The system has been constructed can also provide information coastline changes based on the comparison of the reference frame with the input frame . Preprocessing techniques proposed in this study is a combination of contrast stretching and morphological contrast enhancement , helped segmentation process with SOM , so that the system can find the coastline. Silhouette coefficient value generated by SOM on the beach area segmentation is 0.5304 of the value range 0 to 1 which is reasonable cluster category . The test results on the KNN classification process, gaining 0.90 AUC values of the value range 0 to 1 which is good classification category . Keywords—coastline, coastline change, Self Organizing Map, K-Nearest Neighbor, Contrast Stretching, Morphological Contrast Stretching.
120
DAFTAR ISI
SAMPUL DALAM .................................................................................................. i Lembar Pengesahan ...............................................Error! Bookmark not defined. Tesis Ini Telah Diuji pada ......................................Error! Bookmark not defined. SURAT KETERANGAN BEBAS PLAGIAT ......Error! Bookmark not defined. UCAPAN TERIMA KASIH .................................................................................... i ABSTRAK .......................................................................................................... 118 ABSTRACT ........................................................................................................ 119 DAFTAR ISI ....................................................................................................... 120 DAFTAR TABEL ............................................................................................... 123 DAFTAR GAMBAR .......................................................................................... 124 BAB I PENDAHULUAN ....................................................................................... 1 1.1
Latar Belakang ........................................................................................................1
1.2
Rumusan Masalah ...................................................................................................6
1.3
Tujuan Penelitian ....................................................................................................7
1.4
Manfaat Penelitian ..................................................................................................7
1.5
Ruang Lingkup Penelitian .......................................................................................8
1.6
Keaslian Penelitian ..................................................................................................9
BAB II TINJAUAN PUSTAKA ........................................................................... 11 2.1
State of The Art .....................................................................................................11
2.2
Pantai .....................................................................................................................15
2.3
Sistem Monitoring Video ......................................................................................17
2.4
Pengertian Citra Digital.........................................................................................19
2.5
Operasi Morfologi .................................................................................................24
2.6
Perbaikan Kualitas Gambar (Image Enhancement) ..............................................28
2.7
Ekstraksi Ciri .........................................................................................................32
2.8
Jaringan Syaraf Tiruan ..........................................................................................33
2.9
K-Nearest Neighbor ..............................................................................................41
2.10 Min-Max Normalization ........................................................................................42 2.11 Silhouette Coefficient ............................................................................................43
121
2.12 Confusion Matrix & Kurva ROC (Receiver Operating Characteristic) ...............45
BAB III METODOLOGI PENELITIAN.............................................................. 49 3.1
Tempat dan Waktu Penelitian ...............................................................................49
3.2
Data .......................................................................................................................49
3.2.1 Sumber Data.....................................................................................................49 3.2.2 Jenis Data .........................................................................................................50 3.2.3 Teknik Pengumpulan Data ...............................................................................51 3.3
Gambaran Umum Sistem ......................................................................................51
3.4
Alur Penelitian ......................................................................................................56
3.4.1 Contrast Stretching (Peregangan Kontras) ......................................................58 3.4.2 Morphological Contrast Enhancement ............................................................58 3.4.3 Transformasi Grayscale ...................................................................................59 3.4.4 Ekstraksi Ciri ...................................................................................................60 3.4.5 Algoritma Self Organizing Map (SOM) ..........................................................60 3.4.6 Algoritma K-Nearest Neighbor (KNN) ...........................................................63 3.4.7 Penentuan Garis Pantai ....................................................................................65 3.4.8 Silhouette Coefficient .......................................................................................65 3.4.9 Confusion Matrix & ROC (Receiver Operating Characteristic) .....................66 3.5
Jadwal Pelaksanaan Kegiatan ...............................................................................68
BAB IV HASIL DAN PEMBAHASAN .............................................................. 69 4.1
Gambaran Umum Sistem Deteksi Garis Pantai ....................................................70
4.2
Sistem Pelatihan Klasifikasi Daerah Pantai ..........................................................71
4.3
Sistem Deteksi Garis Pantai ..................................................................................74
4.4
Perbandingan Hasil Sistem Deteksi Garis Pantai Berdasarkan Proses Preprocessing ........................................................................................................89
4.5
Pengujian Algoritma SOM ....................................................................................92
4.6
Perbandingan Nilai Silhouette Coefficient Algoritma SOM Berdasarkan Proses Preprocessing ........................................................................................................94
4.7
Pengujian Algoritma SOM dengan Frame Rekonstruksi ...................................102
4.8
Pengujian Algoritma KNN ..................................................................................104
BAB V SIMPULAN DAN SARAN ................................................................... 118 5.1
Simpulan .............................................................................................................118
5.2
Saran ....................................................................................................................120
122
DAFTAR PUSTAKA ......................................................................................... 122
123
DAFTAR TABEL Tabel 2.1 Penelitian yang Telah Dilakukan ..........................................................13 Tabel 2.2 Silhouette Coefficient ............................................................................44 Tabel 2.3 Silhouette Width ....................................................................................45 Tabel 2.4 Model Confusion Matrix .......................................................................46 Tabel 3.1 Confusion Matrix ...................................................................................67 Tabel 3.2 Jadwal Pelaksanaan Kegiatan ................................................................68 Tabel 4.1 Hasil Pengujian Algoritma SOM Pada Sistem Deteksi Garis Pantai ....92 Tabel 4.2 Hasil Perbandingan Nilai Silhouette Coefficient Algoritma SOM Berdasarkan Proses Preprocessing ........................................................94 Tabel 4.3 Hasil Pengujian Algoritma SOM dengan Frame Rekonstruksi ..........102 Tabel 4.4 Confusion Matrix Label Laut ..............................................................104 Tabel 4.5 Hasil Pengujian Label Laut .................................................................106 Tabel 4.6 Confusion Matrix Label Daratan .........................................................108 Tabel 4.7 Hasil Pengujian Label Daratan ............................................................109 Tabel 4.8 Confusion Matrix Label Langit ...........................................................112 Tabel 4.9 Hasil Pengujian Label Langit ..............................................................113 Tabel 4.10 Rangkuman Pengujian KNN .............................................................115 Tabel 4.11 Rangkuma Hasil Pengujian KNN......................................................116
124
DAFTAR GAMBAR Gambar 1.1 Diagram Fishbone Penelitian ...........................................................10 Gambar 2.1 Diagram Fishbone Penelitian ...........................................................14 Gambar 2.2 Terminologi Pantai untuk Keperluan Pengelolaan Pantai ................15 Gambar 2.3 Terminologi Pantai untuk Keperluan Rekayasa Pantai ....................16 Gambar 2.4 Citra Biner ........................................................................................22 Gambar 2.5 Citra Grayscale .................................................................................23 Gambar 2.6 Macam-Macam Aplikasi dari Image Enhancement .........................29 Gambar 2.7 Feedforward Network dengan Satu Lapisan Neuron Tunggal .........35 Gambar 2.8 Multi Layer Feedforward Networks .................................................35 Gambar 2.9 Arsitektur Self Organizing Map........................................................38 Gambar 2.10 Ilustrasi Silhouette Coefficient ........................................................44 Gambar 3.1 Salah Satu Frame Video dari Pantai Egmond en Zee, Belanda ........51 Gambar 3.2 Gambaran Umum Penelitian.............................................................52 Gambar 3.3 Gambaran Umum Pengolahan Frame Video ....................................53 Gambar 3.4 Gambaran Umum Sistem Pelatihan ..................................................54 Gambar 3.5 Gambaran Umum Sistem Deteksi Garis Pantai Dengan Algoritma SOM dan KNN .................................................................................55 Gambar 3.6 Flowchart Implementasi Algoritma SOM ........................................62 Gambar 3.7 Flowchart Implementasi Algoritma KNN ........................................64 Gambar 3.8 Ilustrasi Silhouette Coefficient ..........................................................66 Gambar 4.1 Alur Pembahasan ..............................................................................69 Gambar 4.2 Sistem Deteksi Garis Pantai dengan Algoritma SOM dan KNN .....70 Gambar 4.3 Sistem Pelatihan Klasifikasi Daerah Pantai ......................................71 Gambar 4.4 Alur Sistem Pelatihan Klasifikasi Daerah Pantai .............................72 Gambar 4.5 (a) Potongan Gambar Bagian Laut, (b) Potongan Gambar Bagian Daratan, (c) Potongn Gambar Bagian Langit ...................................73 Gambar 4.6 Hasil Transformasi Grayscale ..........................................................73 Gambar 4.7 Sistem Deteksi Garis Pantai..............................................................75 Gambar 4.8 Alur Sistem Deteksi Garis Pantai .....................................................75 Gambar 4.9 Frame Video Monitoring Pantai .......................................................76 Gambar 4.10 Hasil Operasi Contrast Stretching Pada Frame Video Monitoring77 Gambar 4.11 Hasil Operasi Morphological Contrast Enhancement ....................77 Gambar 4.12 (a) Hasil Segmentasi 1, (b) Hasil Segmentasi 2, (c) Hasil Segmentasi 3 ...................................................................................80 Gambar 4.13 Daerah dengan Label Kelas Daratan ..............................................81 Gambar 4.14 (a) Hasil Segmentasi SOM, (b) Transformasi Citra Biner, (c) Operasi Opening, (d) Operasi Closing, (e) Operasi Imfill, (f) Hasil Akhir Segmentasi ...........................................................................81 Gambar 4.15 Citra Biner Daerah Daratan ............................................................84 Gambar 4.16 Hasil Penentuan Letak Garis Pantai ...............................................85 Gambar 4.17 Hasil Sistem Deteksi Garis Pantai ..................................................86 Gambar 4.18 Frame Referensi .............................................................................86
125
Gambar 4.19 (a) Daerah Daratan Frame Referensi, (b) Daerah Daratan Frame Inputan, (c) Selisih Daerah Daratan Frame Referensi dan Inputan ........................................................................................................87 Gambar 4.20 Perubahan Garis Pantai ...................................................................88 Gambar 4.21 Data Uji ...........................................................................................89 Gambar 4.22 (a) Hasil Tanpa Preprocessing, (b) Hasil Preprocessing Contrast Stretching, (c) Hasil Preprocessing Contrast Stretching dan Morphological Contrast Enhancement ..........................................90 Gambar 4.23 Data Uji Kedua ...............................................................................91 Gambar 4.24 (a) Hasil Tanpa Preprocessing, (b) Hasil Preprocessing Contrast Stretching, (c) Hasil Preprocessing Contrast Stretching dan Morphological Contrast Enhancement ..........................................91 Gambar 4.25 Perbandingan Nilai Silhouette Coefficient Dalam Bentuk Grafik ..97 Gambar 4.26 Pengelompokan Data Berdasarkan Urutan Nilai Silhouette Coefficient.......................................................................................98 Gambar 4.27 Hasil Pengujian Deteksi Garis Pantai Pada Data Uji dengan Kategori Strong Cluster ................................................................100 Gambar 4.28 Hasil Pengujian Deteksi Garis Pantai dengan Preprocessing Contrast Stretching Pada Data Uji dengan Kategori Strong Cluster ......................................................................................... 100 Gambar 4.29 Hasil Pengujian Deteksi Garis Pantai dengan Preprocessing Contrast Stretching dan Morphological Contrast Enhancement Pada Data Uji dengan Kategori Strong Cluster ............................101 Gambar 4.30 Kurva ROC Label Laut .................................................................107 Gambar 4.31 Kurva ROC Label Daratan ...........................................................111 Gambar 4.32 Kurva ROC Label Langit..............................................................114
